Concurrency and Scheduling Flashcards
What are the 6 scheduling algorithms that the CPU could use in order to decide the order in which processes should run?
- First Come First Serve (FCFS):
Could be implemented with a queue. disadvantage - Waiting time is too long, short processes have to wait for long processes to be over.
- Shortest Job First (SJF):
The algorithm orders the jobs by size. Advantage - many jobs don’t get stuck behind a large job. This algorithm minimizes response time (the time until the process gets the CPU for the first time) as well as the waiting time (the overall time that a process is in the “ready” state).
- Shortest Remaining Time First (SRTP):
בכל פעם שמגיעה משימה חדשה (אונליין) והמתזמן מתבקש לבצע קביעה, נחליף למשימה שנותרה לה הכי קצת זמן. האלגוריתם מאפשר לטפל בתהליכים בזמן די מהיר. הבעיה כאן היא שאנחנו לא יודעים את העתיד - כמה זמן משימה תיקח, מתי לעצור משימות ארוכות (אנחנו לא יודעים מי ארוכה) ולכן משימות קצרות נתקעות מאחורי ארוכות. אבל, יש דרך לשערך את הזמן שיקח לתהליך לרוץ.
- Priority Scheduling:
כל תהליך מקבל עדיפות כלשהי, ומריצים את התהליך עם העדיפות הגבוהה
- Round Robin:
מקצים קוואנטום (יחידת זמן) לכל תהליך, ובסוף הריצה שלו מכניסים אותו חזרה לתור.
- Multilevel Feedback Queue:
הרעיון הוא ליצור מספר תורים, ולכל תור לעשות אלגוריתם תזמון משלו, כך שתור בעל עדיפות גבוהה יותר רץ קודם לכן. הרעבה תלויה במימוש
לדעתי זה לא יכול להיות פיפו, כי בפיפו משימות מסתיימות ולא חוזרות להיות רדי.
תשובה ד לא נכונה. החלפה בין תרדים ברמת הקרנל יותר איטית מאשר החלפת תרדים ברמת היוזר, כי בהעברת תרדים בקרנל יש יותר פעולות משמירה של מספר רגיסטרים
תשובה א נכונה כנראה בגלל שבקרנל לבל תרדס , מספר תרדס יכולים לרוץ באמת במקביל אם יש מספר ליבות - זה לא כמו בטיים שרינג שאין באמת שני תהליכים שרצים במקביל.
מה תרד מחזיק בפני עצמו ומה הוא חולק עם שאר התהליך
Are the marked commands atomic commands?
What would they look like in assembly?
They are not atomic.
c += b + a
could be broken up into:
lw a
lw b
Add
Sw c
OR
lw b
lw a
Add
Sw c
Define: preemptive vs. non preemptive scheduling algorithms. Give examples.
What is a semaphore?
What is MapReduce?
What functions are used to switch between user level threads?
What do they do?
What is the meaning of “flag[]” and “turn” in mutex algorithms?
Flag is an array in which in the index i is a boolean indicating whether or not thread number i is waiting to enter the critical section.
Turn says which thread’s turn it is to enter.
What is Peterson’s algorithm for thread mutual exclusion?
The trick is to be a gentleman, and even though, you are waiting to go in to the critical code - to give the other thread a chance to go in first by setting “turn” to be the other thread’s.
Both answers are incorrect and they stem from the fact that rd_count is not protected, so two readers could enter at the same time and skip putting down the lock on writers which is done only if one reader has entered.
a - a writer could enter, and then two readers could start reading.
b - a writer could go in and then two readers will go through the reader code and up wrt_lock at the end - letting in another writer.
What is the return value of the fork() function?
What to things will be printed?
The variable 0 will be printed, and then the virtual address of v will be printed.
