Matt Ramsay CS470 Homework #6 3/13/02 #1: p. 267, Problem 8.4: a. • Mutual Exclusion: The traffic jam example satisfies the mutual exclusion requirement for deadlock because at least one resource is nonsharable. Only one car can occupy each intersection at a time. If another car needs access to the intersection, it must wait until the current car has vacated the intersection before it can proceed. • Hold & Wait: The hold and wait definition: a process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes. In the traffic example, the cars traveling east/west are holding two intersections and are waiting to acquire two other intersections. The same holds for the north/south traveling traffic. Therefore, the traffic jam example satisfies the hold and wait requirement for deadlock. • No Preemption: No preemption definition: resources cannot be preempted; that is, a resource can be released only voluntarily by the process holding it, after that process has completed its task. The traffic jam example satisfies this condition in two ways: first, a car cannot be preempted, basically meaning that God can’t come down and remove a car from blocking the intersection to free up traffic. Second, the cars that are in the intersections cannot backup and remove themselves to help the flow of traffic. They are blocked by the cars behind them and can only give up the intersection by going through it, not by backing out. • Circular Wait: Circular wait definition: A set of waiting processes must exist such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, etc and Pn is waiting for a resource held by P0. The traffic jam example satisfies this definition because the northbound cars are waiting for the westbound cars, the westbound cars are waiting on the southbound cars, the southbound cars are waiting on the eastbound cars and the eastbound cars are waiting on the northbound cars. b. A very simple rule to eliminate deadlock in this system is to add stop signs at each intersection for the east/west bound traffic. This system might not be too popular with people traveling north/south, but would always give priority to the north/south bound traffic and prevent deadlock.#2: p. 267-268, Problem 8.6: a. Increase Available: This change should be able to be made at any time. It only adds the resources of the system and should not increase the likelihood of deadlock. b. Decrease Available: This change can be completed without causing deadlock, but must be done during certain conditions. The resources must only be decreased by an amount less than the currently available resources during any safe state. c. Increase Max for one process: This change can be completed without causing deadlock, but only under certain conditions. The Max for a process cannot exceed the total resources of the system. Also, the Max for a process must not be increased while that process is running. d. Decrease Max for one process: This change should be able to be made any time that the process is not running. The Max for a process should not be changed while the process is running. e. Increase the number of processes: This change can only be made under certain restrictions to avoid deadlock. New processes can only be added during a safe state. The processes added must declare valid Max values. f. Decrease the number of processes: This change can only be made under certain restrictions to avoid deadlock. Processes must only be removed when they are not active, thus not occupying any resources. They must also only be removed during a safe state. #3: p. 268, Problem 8.8: In this system, only two processes can be running at the same time because of limited resources. The remaining process is waiting on two resources, so it will grab the two resources given up by the first process to finish. Since there will only be one process waiting at a time and it will be waiting on the exact number of resources released by the next completed process, deadlock will never occur. If there were more than three processes in the system, this would not be true.#4: p. 269, Problem 8.13: a. Need Matrix: A B C D P0 0 0 0 0 P1 0 7 5 0 P2 1 0 0 2 P3 0 0 2 0 P4 0 6 4 2 b. Yes, because the Need for both P0 and P3 are less than or equal to Available. c. Yes, because each element of the request is less than or equal to the corresponding element in Available and this request added to the resources currently held by P1 is less than or equal to P1’s