מימוש של MUTEX

[danby]

מימוש של MUTEX

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

 

[VoidMain]

החבר צודק לדעתי

גם עם נניח שפעולת ההשמה נעשתה באופן אטומי (דבר שלא נראה לי סביר להניח בגלל שמעבדים יכולים להריץ כמה פקודות במקביל בימינו), פעולת הבדיקה האם המיוטקס היה נעול והמתנה אם כן הינה פעולה מורכבת ומסועפת שהיא בוודאי אינה אטומית. כראיה לכך, ניתן להריץ שני טרדים ששניהם מקדמים משתנה גלובלי משותף חמישים פעמים ולראות כי במרבית המקרים ערכו של המשתנה בסופו של עניין לא יהיה מאה וזאת פעולה הרבה יותר פשוטה מאשר התנייה. לכן לעניות דעתי, נדרשת פה גישה לרמות נמוכות של החומרה/מע"ה לצורך ממימוש מיוטקסים. בנוסף יש מצב (אני ממש לא בטוח) שמימוש בסיסי ע"י הצבה כפי שהצעת יתקע (הרעבה) את הטרדים שלך במקרה של מיוטקסים רבים, לצורך כך מע"ה ממשות מיוטקס ע"י שימוש באלגוריתמים מיוחדים כגון אלגוריתם המאפייה (למידע נוסף: http://en.wikipedia.org/wiki/Lamport's_bakery_algorithm)

 

[VoidMain]

אבל נראה לי שגם אתה צודק ../images/Emo13.gif

אלגוריתם המאפייה כפי שמוסבר בוויקי (ראה קישור הודעה קודמת), מאפשר ליצור מיוטקסים גם כאשר לא ניתן להניח אטומיות של פעולות בתנאי שהכתיבה מתבצעת למקומות לא משותפים בזיכרון ורק הקריאה יכולה להיות משותפת, או כפי שמוסבר בוויקי: Each thread only writes its own storage, only reads are shared. Remarkable is that this algorithm is not built on top of some lower level 'atomic' operation, e.g. compare-and-swap.

 

[johnny d]

דעה ?

או שאפשר או שלא, ובמקרה אפשר כמו שכבר ציינו לפני

 

[danby]

אתם לא משאירים לי שום ברירה

אני מרגיש שאני חייב להוכיח ייתכנות ע"י מימוש....

 

[johnny d]

אי אפשר לזרוק כ3000 שנים של מסורת

טענת: קיים x מוכיחים ע"י הצגת x שכזה.

 

[the new L]

אפשר

עשו את זה כשהוסיפו למתמטיקה את אקסיומת הבחירה.

 

[ron369]

זה אפור

יש אנשים שלא מאמינים בה, לא?

 

[the new L]

לא כל כך

במאה ה-19 ובתחילת המאה ה-20 היו כאלה. היום כמות האנשים האלה היא אינפיניטסימלית.

 

[ron369]

אה

אז אין קורסים לתואר שני שאחת מדרישות הקדם שלהם היא הסכמה עם אקסיומת הבחירה?

 

[the new L]

כל הזמן

משתמשים בה, אז אפשר להגיד שזו דרישת קדם לרובם

 

[VoidMain]

הוכחה תיכנותית

http://www.developer.com/lang/jscript/article.php/3592016 המאמר מראה בנייה של מיוטקסים בגאווה סקריפט ד"א בגאווה סקריפט אין אפשרות למיוטקסים ממע"ה