סיבוכיות סנכרון
סיבוכיות סנכרון הוא מושג מתחום הנדסת תוכנה המתייחס לסוג של סיבוכיות קוד, אשר מודד את השפעת השימוש באמצעי סנכרון על הקושי לבדוק את המוצר הסופי בתחום התוכנה המקבילית.
הנוסחה פותחה לראשונה במחלקה למדעי המחשב של האוניברסיטה הפתוחה בישראל. הרעיון הכללי הוא להרחיב את הסיבוכיות הציקלומטית של מקקייב למערכות מקביליות המשתמשות באמצעי סנכרון בקוד.
דוגמאות לאמצעי סנכרון בקוד הן, למשל, נעילות הדדיות, שימוש בזיכרון משותף, תקשורת בין תהליכים וכדומה.
אופן פעולה
עריכההנוסחה פותחה בהתבסס על הנוסחאות הקיימות לחישוב סיבוכיות ציקלומטית של גרף המייצג מסלול בקרה של התוכנה הנבדקת. הסיבוכיות הציקלומטית היא מספר המייצג את סיבוכיות הגרף כתלות במספר הקשתות והצמתים בו, ואם לתרגם את זה לעולם התוכנה - כתלות במספר מבני הבקרה (מבנים מסוג if...then, while וכדומה). סיבוכיות סנכרון באה להרחיב את המודל למצב בו יש יותר ממסלול בקרה אחד בתוכנה (כל מסלול כזה נקרא interleaving), והמסלולים מצטלבים בנקודות מוגדרות (נקודות סנכרון - synchronization points). המדד מבוסס על כך שנקודות הסנכרון האלה הן מוגדרות מראש ובעלי מאפיינים ידועים. דוגמאות לנקודות סנכרון הן למשל השהיה (פקודת sleep), נעילה הדדית (mutex), או גישה לזיכרון משותף (shared memory, volatile variable).
מאפייני נקודת סנכרון
עריכהלנקודות סנכרון מוגדרים שני מאפיינים:
- פוטנציאל שחלוף (interleaving potential) - מאפיין זה אחיד לכל מופעי סוג נקודת הסנכרון בתוכנה הספציפית, אך יכול להשתנות ממערכת אחת לאחרת כתלות בגורמים מערכתיים (תזמון תהליכים, תמיכה בעדיפויות ריצה, וכדומה). המאפיין מתאר את התנהגות המערכת בנקודת הסנכרון: האם המערכת בהכרח תבצע העברת בקרה לתהליך אחר (context switching), ואם כן - מה מספר המתחרים המינימלי שיכול להיות. עבור מערכת שלא מאפשרת תוכנות מקביליות, המאפיין הזה יהיה 1.
- פוטנציאל תחרותיות (competition potential) - מאפיין זה משתנה ממופע למופע של נקודת סנכרון בקוד. המאפיין הזה מתאר את מספר התהליכים התלויים בנקודת הסנכרון. למשל, במקרה של נעילה הדדית, המאפיין יתאר את מספר התהליכים המשתמשים במנעול המדובר. הערכים יכולים להשתנות עבור מופעי נקודת סנכרון שונים בתוך הקוד, כתלות בלוגיקה של התוכנה. בתוכנה שאינה מקבילית, המאפיין הזה יהיה 1.