שאלות על Threadים

[טשרםמ1]

שאלות על Threadים

שלום, סיימתי תואר במדעי המחשב ומשום מה לא למדנו על threadים. אחרי שנפלתי בשתי ראיונות בגלל שלא ידעתי כל כך איך להשתמש בזה, החלטתי ללמוד מה זה. 1) בטכניון כן למדתי על סמפור ו multi procces, זה מקביל ל multi thread? 2) אם אפשר, לקבל קישור על העקרונות של זה? (הסבר כללי, לא "מולטי thread ב java/c"). 3) אם אפשר, לקבל פתרון לשאלות הבאות (אלה השאלות שנפלתי עליהם): I) יש hash table שהרבה קליינטים יכולים לגשת אליה. כל אחד מבצע את הדבר הבא: 1) find key 2) אם key לא נמצא add key . כאשר הפעולה add יקרה, ו find זולה. (הבעייה כמובן היא שלא יקראו ל add אם אותו key בו זמנית) אפשר לשנות/להוסיף לקוד. צריך להשתמש במשתנים מסוג lock שאפשר לעשות להם lock=1 או lock=0 בפעולה אטומית. הפתרון שלי היה להגדיר N משתנים מסוג lock כש N זה גודל הטבלה. ולקרוא ל lock ל L[key] בין שורה 1 ל 2 ואח"כ לשחרר אותו. אבל לפתרון יותר טוב לא הצלחתי להגיע. 2) מימוש של socket. יש n אפליקציות, ויש buffer אחד שמקבל הודעות. כל אפליקציה קוראת ל receive, ורק ברגע שיש הודעה בשבילה receive צריכה להסתיים. (receive מקבלת בתור פרמטר את מספר האפליקציה). כאשר ה buffer מקבל הודעה מופעלת פונקציה rec_, שגם אותה צריך לממש. שוב הפתרון שלי היה ליצור n לוקים (locks(, שהמצב ההתחלתי שלהם נעול. receive תקרא לlock של מספר האפליקציה, rec_ תשחרר אותו. שוב אמרו לי שיש פתרון יותר טוב ולא הגעתי אליו. למישהו יש תשובות?

 

[ה עוד אחד]

אתה בטוח שלא למדתם threads?

כי אז אני לא מבין מה יש לעשות עם סמפור....

 

[טשרםמ1]

סמפור זה לprocces לא ל thread

 

[DadleFish]

זה גם לזה וגם לזה.

 

[טשרםמ1]

מנעול זה בעצם סמפור בינארי

עדיין, הבנתי, שיש הבדל בין multi threads ל multi processes

 

[ה עוד אחד]

הבדל :

multi-threads : תהליך "גדול" שמכיל תהליכונים "קטנים" שיכולים לרוץ "במקביל". יש להם משאבים משותפים כמו זיכרון, זמן מעבד ועוד... multi-process : כמה תהליכים שונים עם PID שונה שיכולים לתקשר ביניהם ע"י סיגנלים הודעות, pipe ועוד. לכל אחד מהם יש זמן מעבד משלו וזיכרון משלו.

 

[ה עוד אחד]

ל process-ים שונים אין משאבים

משותפים, אז בשביל מה צריך סמפורים? בשביל נעילת קבצים?

 

[ClownOfDestruction]

אני לא מבין איך הפיתרון שלך

לשאלה הראשונה עוזר לך (מצד שני, יכול להיות שאני סתם לא מבין). קודם כל, אני לא ממש מבין איך אפשר לנעול key.. אני מניח שמה שאתה אומר זה מן כזה "אם מפתח נעול, חכה עד שהוא לאיהיה נעול ורק אז תמשיך". עכשיו זה סבבה, הבעיה לדעתי היא שלא שמת את הנעילה במקום הנכון. אם אתה נועל רק את ההוספה, אז יכול להיות מצב שבו: 1. thread ראשון בודק אם מפתח X קיים. 2. thread שני בודק באותו הרגע גם אם מפתח X קיים. 3. thread ראשון גילה שמפתח X לא קיים ועושה נעילה. 4. thread שני גם מנסה לנעול אבל לא מצליח כי נעול ע"י thread ראשון. 5. thread ראשון מוסיף את המפתח X. 6. הנעילה משתחררת וגם thread שני מוסיף את X --> בעיה. לדעתי צריך לנעול גם את הfind. ככה thread ראשון קודם מוסיף נעילה, ורק אח"כ בודק. ככה כאשר thread שני ינסה לבדוק הוא לא יצליח עד אשר thread ראשון כבר הוסיף את המפתח והוריד את הנעילה.

 

[טשרםמ1]

יש פה קצת אי הבנה

ה key לא קשור ל lock, הוא קשור ל hashtable. לצורך העניין key=hash(value). ז"א שהוא int. אני רוצה לחפש ולהכניס key לטבלה. עשיתי בעצם מערך של lockים ולפני כל הכנסה אני נועל את ה lock ה keyי. יש אפשרות לנעול את ה find אבל הפעולה של find היא זולה, והמטרה היא לאפשר הרבה פעולות במקביל. בכל מקרה, לפי מה שרמזו לי בראיון, הפתרון צריך להיות שינוי בקוד, הוספה של find או add או שינוי סדר

 

[ClownOfDestruction]

ברור לי לגמרי למה התכוונת

לא אמרתי שהנעילה קשורה למפתח. התכוונתי שכשאתה נועל את המפתח זה אומר שאם thread מסוים רוצה לעשות find על מפתח נעול הוא לא יוכל, אבל אם הוא רוצה לעשות find על מפתח לא נעול הוא יוכל. אם אתה יכול להוסיף find וadd, תוכל לייעל את הקוד בכך שתעשה:

if (!find(key)) { lock(key); if (!find(key)) add(key); unlock(key); }​

ככה, אפשר לגשת במידה והמפתח קיים אין בעיה ששני threads יעשו עליו find (וככה אתה לא חוסם thread שרוצה לעשות find יחד עם עוד thread, ובכך מייעל את הביצועים). הfind הכפול הוא בעצם שכדי שאם מפתח מסוים לא נמצא אז בעצם עושים את הפעולה המקורית שהצעתי, ובשביל שלא יהיה מצב ששני threads נכנסים ומוסיפים צריך את זה (אם תחשוב על זה תבין שזה הגיוני, במידה וזה לא נשמע הגיוני בהתחלה)..

 

[טשרםמ1]

הייתה לי טעות מקודם

הפתרון שלי היה: key=hash(val) lock L[key] //where L is an arrays of locks if(!find val) then add value unlock L[key] //the end הקטע שבגלל שיש פיזור טוב סביר שרוב הזמן לא find יחכה רק אם הוא מחפש שם שמוסיפים או שמחפשים. הבעיה גם בפתרון שלי וגם בשלך הוא שיש שימוש במערך של lock. יכול להיות שאתה מתכוון ל lock אחד, אבל אז אי אפשר לעשות add לשני ערכים שונים בו זמנית. יכול להיות שלזה מתכוונים, וזה הפתרון.

 

[ClownOfDestruction]

אני לא מבין מה לא טוב שאני משתמש

בהרבה נעילות. לא נתת הגבלה על מספר הנעילות. וחוצמיזה, מה שאתה כתבת עכשיו זה בדיוק הפיתרון הראשון שכתבתי, שהחיסרון בו זה זthread שרוצה לעשות find בזמן שthread אחר עושה find או add לא יכול לעשות את זה.

 

[ClownOfDestruction]

בקשר לחידה השנייה

קצת מוזר לי שאמרו שאפשר לשנות את הreceive.. אבל בכל מקרה גם אם אפשר וגם אם אי אפשר, אפשר לעשות נעילה לא על כל הbuffer אלא על חלקים ממנו, לפי כמה שהאפליקציה צריכה. בשביל זה צריך לבדוק כמה בתים יש לקריאה בsocket של האפליקציה ולשמור מקום עבורם לפי זה. לאחר הטיפול מפנים את המקום. במידה ואפליקציה צריכה N בתים אבל אין N בתים פנויים היא מחכה עד שיהיו וכך הלאה... נשמע רעיון נחמד..

 

[טשרםמ1]

לא הסברתי כמו שצריך

א) את ה receive (את כל המנגנון בעצם צריך לתכנן מאפס) ב) יש buffer שמדי פעם מתמלא בהודעה ובמספר האפליקציה אליו היא מיועדת. ג) צריך לממש גם פונקציה _rec שהחומרה תקרא לה ברגע שהיא ממלאת את ה buffer. ד) אני ממשתי ככה שבתוך מערך בגודל n, נשמור את ההודעה שמיועדת ל i בתא ה i. (לצורך העניין כל app תקבל מקסימום הודעה אחת לפני שתקרא אותה). ה) כעת נוצרות שתי בעיות. אחת איך גורמים לפונקציה receive(i) לחכות עד שתגיע הודעה לאפליקציה i. בעיה שנייה, זה ש rec_ יכולה תוך כדי הקריאה של ההודעה לקבל הודעה חדשה עבור האפליקציה, ואז היא תדרוס את ההודעה במערך. ז"א בקטע קוד של receive: msg=MsgArr _rec will run: MsgArr=newmsg. אז חוץ מזה שהשתמשתי ב n מנעולים, עכשיו אני צריך להשתמש ב 2*n , שוב אמרו לי לנסות לשפר ולא הצלחתי.

 

[ClownOfDestruction]

מה רע בפיתרון שלי?

בסדר אז צריך לתכנן receive מאפס, אז בתוך הreceive שאתה בונה אתה בודק כמה בתים אתה יכול לקרוא מהsocket של האפליקציה, ובודק אם אתה יכול לנעול על הbuffer את מספר הבתים הזה (באופן רציף כמובן). במידה וכן אתה קורא לreceive של הsocket. (אני לא מניח שהreceive שאתה רוצה לבנות מאפס הוא זה של הsocket נכון?), במידה ולא אתה מחכה עד שיהיה מקום על הbuffer. לא מבין למה צריך מערך של הודעות. יכול להיות שאתה מדבר על משהו מופשט ותלוש מהמציאות (כמו שאני מכיר אותה כמובן), שבו יש מצב שמספר אפליקציות (processes) ישתמשו באותו הsocket, כי אז אין בכלל בעיה, כי כל socket יכול להביא רק הודעה אחת בקריאה (אני מניח שקיימת תמיד הודעה אחת בsocket), וכאן אין שום קטע של סנכרון.

 

[טשרםמ1]

ניסיון אחרון

1) בקשר לשאלה הראשונה - זו שאלה מראיון עבודה לא ממבחן, אין הגבלה על מספרים המנעולים, אבל אחרי שהצגתי את הפתרון אמרו לי שזה פתרון סביר אבל לנסות לשפר. 2) בקשר ל socket, צריך לממש את את כל המנגנון מאפס, receive גם של ה socket וגם של האפליקציה. בעצם צריך לתכנן איזה רכיב ברשת. בכל פעם ה buffer יכול לקבל רק הודעה אחת, אבל ברגע שהוא מקבל אותה הוא קורא לפונקציה rec שתטפל בה, פונ' שגם אותה הייתי צריך לממש. בכל מקרה תודה על התשובות.

 

[ClownOfDestruction]

יכולה להיות הגבלה על המנעולים

גם בשאלה ששואלים בראיון עבודה. אומרים לך "תממש את זה בעזרת שני מנעולים בלבד". בקשר לשאלה השנייה, יפה שהם ביקשו שתממש חלק ממערכת ההפעלה.. בכל מקרה החידות היו נחמדות..

 

[BugoK]

תגובה

שלום, הספר של הקורס של מערכות הפעלה שאני למדתי איתו מסביר את הנושא (בין השאר). ספר משעמם טיכו - אבל יש בו את החומר: "מערכות הפעלה" מאת סיון טולדו.

 

[טשרםמ1]

יש לקורס אצלכם אתר באינטרנט?