תכנות עם חוטים

תכנות עם חוטים

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

יצירת חוט חדש:

typedef DWORD WINAPI (LPTHREAD_START_ROUTINE*)(void* argument); HANDLE CreateThread( LPCTSTR security_attributes, SIZE_T stack_size, LPTHREAD_START_ROUTINE function, LPVOID function_argument, DWORD creation_flags, LPDWORD thread_id);

קריאת המערכת הזו יוצרת חוט חדש. החוט החדש מריץ את השגרה funcion, המקבלת מצביע ללא טיפוס (void*) כארגומנט יחיד ומחזירה שלם אי-שלילי. הארגומנט הרביעי של קריאת המערכת הוא המצביע שיועבר כארגומנט ל--funcion. השגרה מחזירה HANDLE, מזהה שמייצג את החוט החדש שנוצר, או NULL אם קריאת המערכת נכשלה.

הארגומנט הראשון של קריאת המערכת מאפשר לציין הרשאות עבור החוט החדש---בתרגיל יש להעביר NULL. הארגומנט השני מציין את גודל המחסנית של החוט החדש בבתים, והערך 0 מורה למערכת ההפעלה להקצות מחסנית בגודל סטנדטי. הארגומנט החמישי מאפשר לשלוט באופן יותר מדוייק על יצירת החוט החדש: הקבוע CREATE_SUSPENED מורה למערכת ההפעלה שהחוט החדש לא יתחיל לרוץ מייד, אלא יווצר כשהוא מושעה, והקבוע STACK_SIZE_PARAM_IS_A_RESERVATION (רק בחלונות xp ואילך) מורה למערכת ההפעלה להקצות מרחב כתובות עבור המחסנית, אך לא להקצות מסגרות פיזיות עד שאלא דרושות. אם יוצרים חוט מושעה, יש לקרוא ל--ResumeThread(HANDLE) על מנת שיתחיל לרוץ. הערך 0 מורה ששני הדגלים הללו אינם בתוקף. הארגומנט האחרון מאפשר למערכת ההפעלה להחזיר מזהה מספרי לחוט החדש. בדרך כלל אין צורך במזהה הזה, וניתן להעביר את הערך NULL, שמורה למערכת ההפעלה שלא להחזיר את המזהה המספרי, אלא רק את ה--HANDLE.

המתנה (כמעט לכל דבר) ונעילת מנעולים. במערכות חלונות יש קריאות מערכת שגורמות לתוכנית לחכות לאירוע כלשהוא, כגון סיום פעולת חוט, לנעילת מנעול, לאירוע, ועוד. בחלונות, כל עצם יכול להמצא באחד משני מצבים: מסומן (signaled) או לא מסומן. חוט או תהליך אינם מסומנים כל זמן שהם רצים או עשויים לרוץ בעתיד, ומסומנים כאשר הם מסיימים את פעולתם. מנעול (mutex) מסומן כאשר הוא נעול ואינו מסומן כאשר הוא חופשי. אירוע (event) הוא פשוט עצם שיכול להמצא באחד משני המצבים הללו, ואין לו משמעות פרט לסימון זה.

קריאת המערכת שנשתמש בה על מנת להמתין שעצם יגיע למצב מסומן היא WaitForSingleObject. הקריאה ממתינה שחוט יסיים את פעולתו, או שמנעול ינעל על ידי החוט הקורא, או שאירוע (event) מסויים יסומן. אם העצם הוא מנעול, הקריאה חוזרת בהצלחה רק כאשר הוא ננעל על ידי החוט הקורא, וממתינה אם המנעול נעול על ידי חוט אחר. כלומר, על מנעולים קריאת המערכת הזו שקולה לחלוטין ל--lock(m).

DWORD WaitForSingleObject( HANDLE object, DWORD timeout_in_milliseconds);

הארגומנט הראשון הוא המזהה של העצם שמבקשים לחכות לאירוע הקשור בו, והארגומנט השני הוא זמן ההמתנה המקסימלי באלפיות שניה, או הקבוע INFINITE אם ההמתנה אינה מוגבלת בזמן. השגרה מחזירה אחד משלושה ערכים: WAIT_OBJECT_0 אם ההמתנה הסתיימה בהצלחה, WAIT_TIMEOUT אם ההמתנה הסתיימה בגלל שפרק הזמן המקסימלי שציינו עבר, או WAIT_ABANDONED, שמוחזר רק כאשר העצם הוא מנעול (mutex), אם המנעול ננעל בהצלחה משום שהחוט הקודם שנעל את המנעול סיים את פעולתו בלי לשחרר את המנעול. מצב כזה נקרא נטישה של המנעול.

יצירת מנעול (mutex):

HANDLE CreateMutex( LPSECURITY_ATTRIBUTES security_attributes, BOOL initial_ownership, LPCTSTR name);

הקריאה יוצרת מנעול חדש, שניתן לתת לו שם גלובלי (הארגומנט השלישי) והרשאות (הארגומנט הראשון). הארגומנט השני מאפשר ליצור מנעול שנעול באופן התחלתי על ידי החוט היוצר. הקריאה מחזירה מזהה או NULL אם היא נכשלת. את המזהה יש לשחרר בעזרת הקריאה CloseHandle(HANDLE). מערכת ההפעלה משחררת את המנעול כאשר לא נשארים מזהים (handles) שמתייחסים אליו. שחרור מנעול נעול מתבצע בעזרת הקריאה ReleaseMutex(HANDLE).

יצירת אירוע (event) ושינוי מצבם:

HANDLE CreateEvent( LPSECURITY_ATTRIBUTES security_attributes, BOOL manual_reset, BOOL initially_signaled, LPCTSTR name);

הקריאה יוצרת אירוע חדש, שניתן לתת לו שם גלובלי (הארגומנט הרביעי) והרשאות (הארגומנט הראשון). הארגומנט השלישי מאפשר ליצור מנעול שהמצב ההתחלתי שלו מסומן. הארגומנט השני מציין האם האירוע הוא מסוג איפוס ידני או איפוס אוטומטי. הקריאה מחזירה מזהה או NULL אם היא נכשלת. את המזהה יש לשחרר בעזרת הקריאה CloseHandle(HANDLE). מערכת ההפעלה משחררת את המנעול כאשר לא נשארים מזהים (handles) שמתייחסים אליו.

אירוע שמסומן כאשר יש קבוצת חוטים שממתינה לו מעיר את כולם. אירוע שמסומן כאשר אין ממתינים נשאר מסומן, וחוטים שיקראו לשגרת המתנה לא ימתינו כלל.

את שני סוגי האירועים (איפוס ידני ואוטומטי) מסמנים בעזרת הקריאה SetEvent(HANDLE). אירוע מסוג איפוס ידני מעבירים למצב לא מסומן בעזרת הקריאה ResetEvent(HANDLE). ניתן להעביר גם אירוע מסוג איפוס אוטמטי למצב לא מסומן בעזרת ResetEvent, אבל אירוע כזה גם עובר למצב לא מסומן ברגע שהוא מעיר חוט אחד או יותר מהמתנה.

בתרגיל זה נממש ספרית שגרות המאפשרת לתכנית לבצע פעולות קלט פלט ללא להמתין, תוך שימוש ב--posix threads. ביצוע פעולות בצורה כזו נקרא ביצוע אסינכרוני או nonblocking. הספריה תשתמש בחוטים, כך שפעולת קריאה או כתיבה של התכנית תתבצע למעשה על ידי חוט של הספריה. החוט הוא שימתין לביצוע קריאות המערכת read או write בעוד שהתכנית תוכל להמשיך בפעולות אחרות.

הממשק לספריה שעליכם לממש. עליכם לממש ספריה בת 5 שגרות:

int nb_init (int min_threads, int max_threads); int nb_finalize(); int nb_read (HANDLE f, void* buf, SIZE_T count, DWORD offset); int nb_write (HANDLE f, void* buf, SIZE_T count, DWORD offset); int nb_wait (int request);

השגרה nb_init מאתחלת את הספריה. השגרה מאתחלת את מבני הנתונים של הספריה ויוצרת חוטים שיבצעו את פעולות הקלט/פלט עבור לקוחות הספריה. הפרמטר הראשון הוא מספר החוטים שיווצרו בזמן האיתחול, והפרמטר השני הוא המספר המקסימלי שמותר לספריה ליצור. השגרה nb_finalize דואגת לסיום מסודר של כל החוטים של הספריה ומשחררת משאבים שהוקצו על ידי הספריה (כגון זיכרון). השגרות האלו צריכות להחזיר 0 במקרה של הצלחה ו---1 במקרה של כשל.

השגרות nb_read ו--nb_write מתחילות פעולות קריאה או כתיבה. הפעולות חוזרות מייד ללא המתנה, פרט למקרים שיפורטו בהמשך. השגרות מעבירות לספריה מזהה של קובץ פתוח שעליו יש לבצע את הפעולה, מצביע לחוצץ שאליו או ממנו יועברו הנתונים, מספר הבתים שיש להעביר, והמיקום מתחילת הקובץ שממנו או אליו יש להעביר את הנתונים. השגרות מחזירות מזהה פעולה אי-שלילי שמאפשר לתכנית להמתין לסיום הפעולה. במקרה של שגיאה השגרות מחזירות -1.

השגרה nb_wait ממתינה לסיום פעולת קריאה או כתיבה. הפרמטר הוא מזהה פעולה שהוחזר על ידי nb_read או nb_write.

קריאה ל--nb_read או nb_write מכניסה לתור את פרטי הבקשה. החוטים של הספריה מוציאים בקשות מהתור ומבצעים אותן. מותר להגביל את גודל התור ל--52 בקשות על מנת למנוע בזבוז זיכרון בתור שהולך ומתארך. קריאה ל--nb_read או nb_write שמגלה שהתור מלא ממתינה עד שמתפנה מקום בתור. זה המקרה היחיד שבו קריאות אלה לא יחזרו מייד לתכנית.

מותר גם להגביל את מספר החוטים שהספריה יכולה ליצור ל--52.

תכנית הבדיקה. עליכם לבדוק את הספריה בעזרת תכנית בדיקה בשם tst-win32aio.c שניתן להוריד מהאתר של הספר. התוכנית יוצרת קובץ גדול ולאחר מכן מבצעת עליו עיבודים שונים בשלושה שלבים. השלב הראשון הוא קריאה של כל הקובץ וכתיבתו לדיסק (בבלוקים של kb 512). השלב השני הוא קריאת כל בלוק בקובץ, טיפול (כבד יחסית) בבלוק בזיכרון, וכתיבתו מחדש. שני השלבים הרשונים יחד מאפשרים להעריך את הזמן שלוקחת הקריאה והכתיבה מהקובץ ואת הזמן שלוקח הטיפול בכל בלוק. בשלב השלישי התכנית קוראת את הבלוקים בצורה אסינכרונית תוך שימוש בספריה שלכם, מטפלת בכל בלוק בזיכרון, וכותבת אותו חזרה בצורה אסינכרונית. בכל איטרציה בשלב זה מתרחשות שלוש פעולות במקביל: קריאה של הבלוק הבא בקובץ, טיפול בבלוק הנוכחי, וכתיבה של הבלוק הקודם. כל שלב בתכנית מתבצע פעמיים וזמן הריצה שלו מודפס, על מנת שניתן יהיה להעריך בצורה מדוייקת את העלות של כל שלב.

אנו מצפים שעיבוד אסינכרוני יוריד את זמן הריצה של הטיפול בקובץ. נסמן את זמן הריצה הממוצע של השלב הראשון (שרק קורא וכותב לקובץ) ב--t₁, את זמן הריצה של השלב השני ב--t₂, ואת זמן הריצה של השלב השלישי ב--t₃. אנו מעריכים שזמן הריצה הנדרש לטיפול בבלוקים בזיכרון הוא t₂-t₁. זמן הריצה של השלב השלישי חייב לכן לקיים t₃³max{ t₂-t₁,t₁}. אנו מקווים ש--t₃»max{ t₂-t₁,t₁}, אך בפועל זמן הריצה יהיה לרוב גדול יותר. בכל מקרה שבו t₃<t₂ נדע שזמן הריצה ירד הודות לביצע קלט/פלט בצורה אסינכרונית. הנה פלט אופייני של תכנית הבדיקה, שמראה שזמן הריצה אכן יורד, אך החישוב בזיכרון לא מתבצע במקביל לחלוטין לקלט/פלט:

Y:\Courses\os\exercises\win32aio\Release>win32aio 100 1 4 starting worker 0 temporary file name=<c:\temp\delete.me> writing 100 MB (200 ios of 512 KB each) Time = 6.109 seconds Syncronous Processing, no computation Time = 14.718 seconds Syncronous Processing, no computation Time = 14.546 seconds Syncronous Processing, with computation (x1024) flag = 1 (ignore) Time = 27.499 seconds Syncronous Processing, with computation (x1024) flag = 1 (ignore) Time = 27.718 seconds Asyncronous Processing, with computation (x1024) creating another worker (1) creating another worker (2) flag = 1 (ignore) Time = 15.046 seconds Asyncronous Processing, with computation (x1024) flag = 1 (ignore) Time = 14.968 seconds NB Worker <0>: stopping NB Worker <2>: stopping NB Worker <1>: stopping

כאן t₁»14.5, t₂»25.5, ו--t₃»15.0 (בשניות). כלומר t₃<t₂ אבל t₃>max{ t₂-t₁,t₁}.

תכנית הבדיקה מקבלת שלושה ארגומנטים מספריים: גודל הקובץ ב--mb ומספר החוטים המינימלי והמקסימלי.

ציון המקום בקובץ שממנו צריך לקרוא או לכתוב. הארגומנט החמישי של קריאות המערכת ReadFile ו--WriteFile הוא מצביע למבנה מטיפוס OVERLAPPED שמכיל חמישה איברים:

typedef struct { ULONG_PTR Internal, InternalHigh; DWORD Offset, OffsetHigh; HANDLE event; } OVERLAPPED;

שני השדות הראשונים הם לשימוש המערכת. שני השדות הבאים מציינים את 32 הסיביות התחתונות ו--32 הסיביות העליונות של המיקום. הספריה שלנו תאפשר לגשת לקבצים בגודל gb 4 בלבד, כך שהסיביות העליונות יהיו תמיד 0. השדה האחרון מאפשר להעביר מזהה של אירוע שמערכת ההפעלה תעביר למצב מסומן כאשר פעולת הקלט או הפלט תסתיים---אנו לא נשתמש במנגנון הזה ולכן יש למלא את השדה הזה בערך 0.

אנו נפתח את הקובץ בלי הדגל FILE_FLAG_OVERLAPPED. העברת מצביע למבנה OVERLAPPED בפעולה על קובץ שנפתח ללא הדגל הזה גורמת לפעולת הקלט/פלט להתבצע מהמיקום המצויין בשדות ה--Offset, וקריאות הקלט/פלט יחזרו לחוט הקורא רק כאשר הפעולות יסתיימו. הדגל הזה מאפשר לבצע קלט/פלט ללא המתנה ללא שימוש בחוטים, אך כאמור אנו לא נשתמש במנגנון זה.

התרגיל. כתוב/כיתבי ספריה בשם ex-aio-win32.c המממשת את הספריה כפי שהוגדרה.

ניתן לממש את התרגיל בשתי רמות. ברמת המימוש הפשוטה יש ליצור את מספר החוטים המינימלי שמצוין בקריאה ל--nb_init ותו לא. ברמת המימוש המלאה יש ליצור מספר זה של חוטים ב--nb_init, אך קריאה ל--nb_read או nb_write שמגלה שכל החוטים הקיימים עסוקים ושנוצרו פחות חוטים מהמספר המקסימלי שצויין בקריאה ל--nb_init, חייבת ליצור חוט נוסף שיבצע קלט/פלט.

בכל מקרה יש לממש תור בקשות. הקריאות nb_read ו--nb_write צריכות להכניס את הבקשה לתור ולאותת במידת הצורך שאינו ריק. חוטי הקלט/פלט של הספריה צריכים למשוך בקשות מהתור ולבצע אותן. כאשר מוצאת בקשה מהתור יש לאותת, במידת הצורך, שניתן להכניס בקשות נוספות לתור.

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

יש להריץ את תכנית הבדיקה תוך שימוש בספריה שלכם על קובץ גדול. על מנת לקבל תוצאות משמעותיות, הריצו את גרסת ה--Release ולא את גרסת ה--Debug. כדאי להתבונן בחיוויי הביצועים במנהל המשימות בזמן ריצת התוכנית. יש לצרף לתכנית המוגשת, בהערות, את הפלט של התכנית בהרצות עם מינימום ומקסימום של חוט אחד ועם מינימום ומקסימום של ארבעה חוטים. למי שמגיש את רמת המימוש המלאה, יש להגיש גם פלט עם מינימום של אפס חוטים ומקסימום של ארבעה.

Copyright Sivan Toledo 2004