Operating Systems Homework
Sey_ Gozubuyuk
14501044
December 1, 2015
1 Dining Philosophers Problem
1.1 Problem De_nition
The Dining Philosophers Problem is often used to clarify synchronization prob- lems in concurrent algorithm design. [1]
In the problem there are _ve philosophers. They sit on chairs around a circu- lar table, and they either think or eat spaghetti. On the table there is spaghetti and _ve chopsticks, as shown in the Figure 1. The philosophers think until they are hungry. When a philosopher gets hungry, he tries to take the nearest two chopsticks. If he is able to pick up both of the left and right chopsticks, he eats for sometime. When he _nishes eating he drops the chopsticks, and make them available for other philosophers …show more content…
This solution avoids deadlocks. However, the concurrency is reduced because of the arbitrator. Philosohers may be prevented from using available chopsticks. 1.2.3 Chandy/Misra solution
K. M. Chandy and J. Misra proposed another solution for The Drinking Phliso- phers Problem, which is a special case of Dining Philosophers Problem [4].
Chopsticks can either be clead or dirty. Initially, all forks are dirty. Every philosopher has an id. The following steps performed.
1. Each chopstick is given to the philosopher who is near to the chopstick, and has a smaller id.
2. When a philosopher wants to get chopstick, he request it from his neighbor.
3. When a chopstick is requested, the holder of the chopstick
(a) keeps the chopstick, if it is clean
(b) cleans and gives the chopstick to the requesting philosopher, if it is dirty. 2 The Banker's Algorithm
2.1 Problem De_nition
The Banker's algorithm aims to avoid deadlocks; and it is used for resource allocation. It also known for avoidance algorithm [5]. This algorithm can also
2
be used in banking system in order to prevent the bank from running out of money. It should guarantee that the bank is always in a safe state.
The Banker Algorithm found by Edsger Dijkstra. In this algorithm, …show more content…
These are;
_ The amount of each resource that the new process requires [REQUEST]
_ The amount of each resource that each process could request [MAX]
_ The amount of each resource that each process is using [ALLOCATED]
_ The amount of each resource that available in the system [AVAILABLE]
_ The amount of each resource that needed by the system [NEEDED]
Resources can be allocated only when REQUEST _ NEEDED and REQUEST
_ AVAILABLE
If all of the processes can terminate in a _nite time, the state can be referred as safe state. In other words, if there exists a set of requests from processes that the maximum resource requirement of each process can be satis_ed, and the processes can terminate by releasing resources; the state is determined as safe state. If there is no such set, then the state is an unsafe state[5].
The operating system runs the Banker's algorithm every time it receives a request. As a result, it decides whether the state is safe or unsafe. If the state is safe, the operating system allocates resources to the request. Otherwise, the request is denied[5].
There are some disadvantages of the Banker's algorithm, which makes the algorithm impractical. These disadvantages can be listed as
Sey_ Gozubuyuk
14501044
December 1, 2015
1 Dining Philosophers Problem
1.1 Problem De_nition
The Dining Philosophers Problem is often used to clarify synchronization prob- lems in concurrent algorithm design. [1]
In the problem there are _ve philosophers. They sit on chairs around a circu- lar table, and they either think or eat spaghetti. On the table there is spaghetti and _ve chopsticks, as shown in the Figure 1. The philosophers think until they are hungry. When a philosopher gets hungry, he tries to take the nearest two chopsticks. If he is able to pick up both of the left and right chopsticks, he eats for sometime. When he _nishes eating he drops the chopsticks, and make them available for other philosophers …show more content…
This solution avoids deadlocks. However, the concurrency is reduced because of the arbitrator. Philosohers may be prevented from using available chopsticks. 1.2.3 Chandy/Misra solution
K. M. Chandy and J. Misra proposed another solution for The Drinking Phliso- phers Problem, which is a special case of Dining Philosophers Problem [4].
Chopsticks can either be clead or dirty. Initially, all forks are dirty. Every philosopher has an id. The following steps performed.
1. Each chopstick is given to the philosopher who is near to the chopstick, and has a smaller id.
2. When a philosopher wants to get chopstick, he request it from his neighbor.
3. When a chopstick is requested, the holder of the chopstick
(a) keeps the chopstick, if it is clean
(b) cleans and gives the chopstick to the requesting philosopher, if it is dirty. 2 The Banker's Algorithm
2.1 Problem De_nition
The Banker's algorithm aims to avoid deadlocks; and it is used for resource allocation. It also known for avoidance algorithm [5]. This algorithm can also
2
be used in banking system in order to prevent the bank from running out of money. It should guarantee that the bank is always in a safe state.
The Banker Algorithm found by Edsger Dijkstra. In this algorithm, …show more content…
These are;
_ The amount of each resource that the new process requires [REQUEST]
_ The amount of each resource that each process could request [MAX]
_ The amount of each resource that each process is using [ALLOCATED]
_ The amount of each resource that available in the system [AVAILABLE]
_ The amount of each resource that needed by the system [NEEDED]
Resources can be allocated only when REQUEST _ NEEDED and REQUEST
_ AVAILABLE
If all of the processes can terminate in a _nite time, the state can be referred as safe state. In other words, if there exists a set of requests from processes that the maximum resource requirement of each process can be satis_ed, and the processes can terminate by releasing resources; the state is determined as safe state. If there is no such set, then the state is an unsafe state[5].
The operating system runs the Banker's algorithm every time it receives a request. As a result, it decides whether the state is safe or unsafe. If the state is safe, the operating system allocates resources to the request. Otherwise, the request is denied[5].
There are some disadvantages of the Banker's algorithm, which makes the algorithm impractical. These disadvantages can be listed as