עצים בינארים

צביקה ברגר

רקורסיות

צביקה ברגר

מערכות הפעלה

Deadlock

צביקה ברגר

בס"ד

בס"ד

Deadlock Characterization

• Mutual exclusion: only one process at a time can use (an instance of) a resource
• Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes
• No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task
• Circular wait: there exists a set {P₀, P₁, …, P_n} of waiting processes such that:�P₀ is waiting for a resource that is held by P₁, �P₁ is waiting for a resource that is held by P₂, …, �P_n–1 is waiting for a resource that is held by P_n, �and P_n is waiting for a resource that is held by P₀.

​

Deadlock can arise if four conditions hold simultaneously.

מדיניות

מצב ספציפי

בס"ד

Methods for Handling Deadlocks

• מניעה – נבטיח שהמערכת לעולם לא תיכנס למצב של deadlock
• תקיפת ארבעת התנאים ל- deadlock
• שמירת המערכת מכניסה ל- deadlock

​

• התאוששות – לא נמנע מהמערכת להיכנס למצב deadlock, ולכשנזהה מצב כזה נתאושש ממנו

​

• התעלמות – נתעלם מהאפשרות שהמערכת עלולה להיכנס למצב של deadlock (לדוגמה ב- Unix)�

​

בס"ד

מניעה - Deadlock Prevention

• Mutual Exclusion – not required for sharable resources (e.g., read-only files); must hold for non-sharable resources
• Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold any other resources
• Many solutions, e.g.:
• Require process to request and be allocated all its resources before it begins execution
• Allow process to request resources only when the process has none allocated to it.
• Low resource utilization; starvation possible

גישה ראשונה – הגבלת הצורה שבה תהליכים מבקשים משאבים:

בס"ד

Deadlock Prevention (Cont.)

• No Preemption –
• If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released
• Preempted resources are added to the list of resources for which the process is waiting
• Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting
• Circular Wait – impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration

​

בס"ד

Deadlock Avoidance

• Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need
• The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition
• Resource-allocation state is defined by: (a) the number of available resources (b) the number of allocated resources, and (c) the maximum demands of the processes

גישה שניה – שמירה על המערכת מפני כניסה למצב של deadlock (לאורך פעולתה)

מחייב שלמערכת מידע נוסף לגבי התהליכים שרצים

בס"ד

Dining Philosophers Problem

בס"ד

Dining Philosophers Problem

בס"ד

Dining Philosophers Problem

בס"ד

בס"ד

LCA

בס"ד

בס"ד

Question 1

2020 מועד א

בס"ד

פתרון

בס"ד

פתרון

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 2

2019 מועד א

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 3

2021 מועד ב

בס"ד

פתרון

בס"ד

2019 מועד ב

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 4

מועד א 2021

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 5

2018 מועד ב

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 6

מועד ב 2022

בס"ד

פתרון

בס"ד

מועד ב 2022

בס"ד

פתרון

בס"ד

מועד ב 2022

בס"ד

פתרון

בס"ד

מועד ב 2022

בס"ד

פתרו

בס"ד

LCA

בס"ד

בס"ד

Question 7

מבחן 2020 מועד א

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 8

2022 מועד א

בס"ד

פתרון

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 9

2022 מועד ב

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

שאלות?