代写 R algorithm operating system security Go Operating Systems Lecture 6a

Operating Systems Lecture 6a
Dr Ronald Grau School of Engineering and Informatics Spring term 2018

Previously 1 Process Synchronisation
 Critical Section problem
 Synchronisation primitives:
 Mutex, Semaphore, Monitor, Condition Variable, . . .  Transactional Memory
 Message Passing

Recap: Synchronisation primitives 2 Which synchronisation primitive would you use?
1. Public transport rules
No more than the max. amount of people allowed enter a bus.
2. Commissioning warehouse
Always put the same number of items in every box.
3. Paying the parking fine
Customers get served individually in the order of their arrival.
4. Occupied!
Only a single person can enter the bathroom at a time.
5. Taking everyone onboard
A ship will only depart once all crew are back from land leave.
6. Putting the cart before the horse
Before you can peel an egg you need to boil it first.

Today 3 Deadlocks
 Deadlock conditions
 Methods of handling deadlocks

Recap: Resources 4 Related operations
 Request: The process requests the resource. If the request cannot be granted immediately (for example, if the resource is being used by another process), then the requesting process must wait until it can acquire the resource.
 Use: The process can operate on the resource (for example, if the resource is a printer, the process can print on the printer).
 Release: The process releases the resource.

Synchronisation and Priority Scheduling 5 Scenario
 Low-priority process L acquires resource R
 L is preempted by long-running medium-priority process M  High-priority process H wants to acquire R, but is blocked  H has to wait until M finishes before L can release R
Problem: Priority inversion
 Higher priority process has to wait because lower priority process holds the resource it wants to access
Solution: Priority inheritance protocol
 Temporarily raise the priority of L to the maximum priority of all processes accessing the same resource
 Avoids priority inversion

Dining Philosophers Problem (Dijkstra 1965) 6 Rules
 The philosophers can either think or eat
 Each philosopher needs two chopsticks to eat
 They can pick up chopsticks from the left and the right as they become available
 How can we make sure they keep thinking and eating in turn, and no-one starves?

Deadlocks 7 A set of processes is deadlocked if each process in the set is waiting for
an event that only another process in the set can cause. Necessary and sufficient conditions:
 Mutual exclusion: Each resource is either currently assigned to exactly one process or is available.
 Hold-and-wait: Processes currently holding resources that were granted earlier can request new resources.
 No-preemption: Resources previously granted cannot be forcibly taken away from a process. They must be explicitly released by the process holding them.
 Circular wait: There must be a circular list of two or more processes, each of which is waiting for a resource held by the next member of the chain.

How do deal with deadlocks? 8 Unfortunately, there is no general solution.
 Deadlock prevention:
 Design the system so that at least one of the four conditions never arises.
 Deadlock avoidance:
 Do not approve resource requests that might lead to a deadlock (Safety).
 Deadlock detection:
 Always approve resource requests if resources are available.  Periodically check whether there is a deadlock.
 If there is a deadlock, perform deadlock recovery.

Deadlock Prevention – Mutual Exclusion 9 System designed such that one of the four conditions never occurs
 Can we build a system with shared resource access not requiring mutual exclusion?
No, it is always necessary to prevent race conditions
 General precautions:
 Make any data resources read-only where there is no need for modification  Acquire only those resources that are really needed

Deadlock Prevention – H&W and NP 10  Hold-and-wait
 Acquire all resources at once, i.e. block until all resources are available
+ Process can execute once all required resources are held – Long delays
– Bad resource utilisation
– Advance knowledge needed about the resources required
 No-preemption
(a) Process releases resources when it fails to acquire a resource, and re-tries later (b) Resource request forces another process to release a resource
Only possible if the state of the resource can be saved and restored

Deadlock Prevention – Circular wait 11  Enforce linear ordering of requests to resource types Ri
e.g. O(disk drive) = 5, O(printer) = 12
 Process has to acquire all resources of type Ri at once
 After having acquired Ri it can only request resources of type Rj where O( Rj ) > O( Ri )
Yes
waits for resource Ri held by process R(i+1)mod n
 Our ordering ensures that for each i we have O( Ri ) < O(R(i+1)mod n) This would mean O(R0 ) < ... < O(Rn-1 ) < O(R0 )  Impossible  circular wait condition does not hold However, there can be inefficiencies if ordering is poorly chosen Does this prevent deadlocks?  Assuming circular wait condition holds: Each process Pi of processes P0 ... Pn-1 Deadlock Avoidance 12 Do not approve resource requests that might lead to a deadlock  When do we know that the system is in a state that might lead to a deadlock?  Deadlock example with two processes: P1 P2 ... ... acquire B acquire A ... ... acquire A release A ... ... release B acquire B ... ... release A release B ... ... Resource Trajectories 13 Resource Trajectories 14 Safe and unsafe system states 15  Deadlock or unavoidable-deadlock state  The system is deadlocked or it will be deadlocked on all trajectories.  Unreachable state  No trajectory can reach such a state, e.g. because of mutual exclusion.  Safe state:  All possible trajectories starting in a safe state are guaranteed to be deadlock-free  Unsafe state:  Existing trajectories starting in unsafe state that lead to deadlock  Depends on scheduler Banker's Algorithm 16 An algorithm for avoiding deadlocks  There are Available[j] instances of each resource type Rj  Each process Pi declares the maximum of instances Maximum[i][j] of each resource type Rj required  Allocation[i][j] is the number of instances of resource type Rj held by process Pi Available R0 R1 R2 3 3 2 Maximum R0 R1 R2 P0 7 5 3 P1 3 2 2 P2 9 0 2 P3 2 2 2 P4 4 3 3 Allocation R0 R1 R2 P0 0 1 0 P1 2 0 0 P2 3 0 2 P3 2 1 1 P4 0 0 2 Banker's Algorithm 17 An algorithm for avoiding deadlocks  Need[i][j] = Maximum[i][j] - Allocation[i][j] Need R0 R1 R2 P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 Maximum R0 R1 R2 P0 7 5 3 P1 3 2 2 P2 9 0 2 P3 2 2 2 P4 4 3 3 Allocation R0 R1 R2 P0 0 1 0 P1 2 0 0 P2 3 0 2 P3 2 1 1 P4 0 0 2 = - Banker's Algorithm – Checking Safety 18 1. Work := Available Finish[i] := false for i = 0 ... n-1 2. Find an index i such that Finish[i] = false ^ Need[i] <= Work If no such i exists, go to step 4. 3. Work := Work + Allocation[i] Finish[i] := true Go to step 2. 4. If Finish[i] = true for all i , then the system is in a safe state. Component-wise ordering on vectors: X<=Y ifforalli:X[i]<=Y[i] Banker's Algorithm 19 Allocation R0 R1 R2 P0 0 1 0 P1 2 0 0 P2 3 0 2 P3 2 1 1 P4 0 0 2 Need R0 R1 R2 P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 Work R0 R1 R2 3 3 2 Finish P0 false P1 false P2 false P3 false P4 false Is there are process that can finish with the resources available (Work)? Banker's Algorithm 20 Allocation R0 R1 R2 P0 0 1 0 P1 2 0 0 P2 3 0 2 P3 2 1 1 P4 0 0 2 Need R0 R1 R2 P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 Work R0 R1 R2 3 3 2 Finish P0 false P1 false P2 false P3 false P4 false Yes,P1 Banker's Algorithm 21 Allocation R0 R1 R2 P0 0 1 0 P1 0 0 0 P2 3 0 2 P3 2 1 1 P4 0 0 2 Need R0 R1 R2 P0 7 4 3 P1 0 0 0 P2 6 0 0 P3 0 1 1 P4 4 3 1 Work R0 R1 R2 5 3 2 Finish P0 false P1 true P2 false P3 false P4 false Finish the process and then release all resources previously allocated to P1 , i.e. add previous allocation (2,0,0) to Work and set Finish = true Banker's Algorithm 22 Allocation R0 R1 R2 P0 0 1 0 P1 0 0 0 P2 3 0 2 P3 2 1 1 P4 0 0 2 Need R0 R1 R2 P0 7 4 3 P1 0 0 0 P2 6 0 0 P3 0 1 1 P4 4 3 1 Work R0 R1 R2 5 3 2 Finish P0 false P1 true P2 false P3 false P4 false Banker's Algorithm 23 Allocation R0 R1 R2 P0 0 1 0 P1 0 0 0 P2 3 0 2 P3 0 0 0 P4 0 0 2 Need R0 R1 R2 P0 7 4 3 P1 0 0 0 P2 6 0 0 P3 0 0 0 P4 4 3 1 Work R0 R1 R2 7 4 3 Finish P0 false P1 true P2 false P3 true P4 false Banker's Algorithm 24 Allocation R0 R1 R2 P0 0 1 0 P1 0 0 0 P2 3 0 2 P3 0 0 0 P4 0 0 2 Need R0 R1 R2 P0 7 4 3 P1 0 0 0 P2 6 0 0 P3 0 0 0 P4 4 3 1 Work R0 R1 R2 7 4 3 Finish P0 false P1 true P2 false P3 true P4 false Banker's Algorithm 25 Allocation R0 R1 R2 P0 0 0 0 P1 0 0 0 P2 3 0 2 P3 0 0 0 P4 0 0 2 Need R0 R1 R2 P0 0 0 0 P1 0 0 0 P2 6 0 0 P3 0 0 0 P4 4 3 1 Work R0 R1 R2 7 5 3 Finish P0 true P1 true P2 false P3 true P4 false Banker's Algorithm 26 Allocation R0 R1 R2 P0 0 0 0 P1 0 0 0 P2 3 0 2 P3 0 0 0 P4 0 0 2 Need R0 R1 R2 P0 0 0 0 P1 0 0 0 P2 6 0 0 P3 0 0 0 P4 4 3 1 Work R0 R1 R2 7 5 3 Finish P0 true P1 true P2 false P3 true P4 false Banker's Algorithm 27  Safe! Allocation R0 R1 R2 P0 0 0 0 P1 0 0 0 P2 0 0 0 P3 0 0 0 P4 0 0 0 Need R0 R1 R2 P0 0 0 0 P1 0 0 0 P2 0 0 0 P3 0 0 0 P4 0 0 0 Work R0 R1 R2 10 5 7 Finish P0 true P1 true P2 true P3 true P4 true Banker's Algorithm – Checking requests 28 Request[i] for process Pi 1. If Request[i] <= Need[i], go to step 2. Otherwise, error (maximum exceeded). 2. If Request[i] <= Available, go to step 3. Otherwise, Pi must wait (resources not available). 3. Pretend to fulll request: Available := Available - Request[i] Allocation[i] := Allocation[i] + Request[i] Need[i] := Need[i] - Request[i] Approve request if resulting state is safe. Otherwise, restore state and Pi has to wait. Banker's Algorithm – Checking requests 29 Allocation R0 R1 R2 P0 0 1 0 P1 2 0 0 P2 3 0 2 P3 2 1 1 P4 0 0 2 Need R0 R1 R2 P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 Available R0 R1 R2 3 3 2  Assume request (1 0 2) by P1 Banker's Algorithm – Checking requests 30 Allocation R0 R1 R2 P0 0 1 0 P1 2 0 0 P2 3 0 2 P3 2 1 1 P4 0 0 2 Need R0 R1 R2 P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 Available R0 R1 R2 3 3 2  Assume request (1 0 2) by P1 Request can be served Allocation R0 R1 R2 P0 0 1 0 P1 3 0 2 P2 3 0 2 P3 2 1 1 P4 0 0 2 Need R0 R1 R2 P0 7 4 3 P1 0 2 0 P2 6 0 0 P3 0 1 1 P4 4 3 1 Available R0 R1 R2 2 3 0 Banker's Algorithm – Checking requests 31 Allocation R0 R1 R2 P0 0 1 0 P1 3 0 2 P2 3 0 2 P3 2 1 1 P4 0 0 2 Available R0 R1 R2 2 3 0 Need R0 R1 R2 P0 7 4 3 P1 0 2 0 P2 6 0 0 P3 0 1 1 P4 4 3 1  Assume request (3 3 0) by P4 Request cannot be granted (insufficient resources)  Assume request (0 2 0) by P0 Request cannot be granted (would result in unsafe state) Summary 32 Deadlocks  Deadlock conditions:  Mutual exclusion  Hold-and-wait  No preemption  Circular wait  Methods for handling deadlocks  Deadlock prevention  Deadlock avoidance  Deadlock detection and recovery (next lecture) Read 33  Tanenbaum & Bos., Modern Operating Systems  Chapter 6  Silberschatz et al., Operating System Concepts  Chapter 7 Next Lecture 34  Introduction  Operating System Architectures  Processes  Threads - Programming  Process Scheduling - Evaluation  Process Synchronisation  Deadlocks (continued)  Memory Management  File Systems  Input / Output  Security and Virtualisation