Chapter 6 - Dijkstra
Dijkstra was one of the geniuses of computer programming. He taught briefly at the University Texas, which make it even more pertinent to research some of his work. (??)
After researching his work, try to find the solution to his famous "Sleeping Barber" and or "Dining Philosophers" problems. As always include a summaryk, a relevant URL, and your name.
Blog on!
15 Comments:
Dijkstra's "Dining Philosophers" problem is 5 people sitting at a round table that has a bowl of spaghetti with only 5 forks for the whole table. The only way they can eat is to have 2 forks; they obviously can't all eat at once because there won’t be enough forks. He uses this analogy, which in computer terms translates to a “deadlock.” One possible way to resolve this issue is to come up with an eating schedule with a time limit. For example, in the first round, philosopher 1 and 3 could eat; in round 2 philosopher 2 and 4 could eat, round 3, philosopher 3 and 5 and so on.
http://www.technologyforall.com/TechForAll/Dining.html
Dijkstra's problem arises with attempting to coordinate this activity without bringing about any race conditions, and in this way is similar to many queueing problems. In fact, it is a classic example of a double rendezvous problem. Not implementing a proper solution can lead to the usual inter-process communication problems of starvation and deadlock. For example, the barber could end up waiting on a customer and a customer waiting on the barber, resulting in deadlock. Alternatively, customers may not decide to approach the barber in an orderly manner, leading to process starvation as some customers never get the chance for a haircut even though they have been waiting.
Modern Operating Systems (2nd Edition) by Andrew S. Tanenbaum
The Dining Philosopher problem is simply a time coordination matter.
If all of the philosophers try to eat at the same time deadlock occurs and they all starve.
If the maximum number of philosophers eat with no break the others starve.
To solve this problem, a simple time limit starting from a designated point has to be initiated, with enough time allowed for each successive diner to eat without starving the others out, or causing deadlock.
The solution comes in several steps.
Each philosopher will be designated by positions 1 through 5.
Each philosopher will have a limited number of time to eat before he will put the forks down and allow the next in line to have the forks.
Positions 1 and 3 will have the 2 pair of forks first, and a semaphore will indicate to the other 3 diners that they are now line and the 1 and 3 positions will change from 0 to 1 status. After a clock cycle, the 1 and 3 dine will be forced to place the forks down and go into the wait queue. A semaphore will indicate to diners 2 and 4 that the forks are ready, 1 and 3 change from status 1 to 0…and for 2 and 4 from 0 to 1 indicating that they have the forks. After a clock cycle 2 and 4 will put the forks down and indicate to the rest that the forks are free. Diners 5 and 2 will no be allocated the forks and their status will change indicated by a semaphore. This will continue in a subsequent sequence that will both provide fair processor time and avoid starvation and deadlock until system completes its processing.
http://www.isi.edu/~faber/cs402/notes/lecture8.pdf
http://www.doc.ic.ac.uk/~jnm/concurrency/classes/Diners/Diners.html
According to Wikipedia.org, Edsger W. Dijkstra was a Dutch computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages. He was the Schlumberger Centennial Chair of Computer Sciences at University of Texas at Austin from 1984 to 2000.
He is well known for his works like Dijkstra’s algorithm, Structured programming, Multiprogramming systems, and Semaphore.
Dijkstra’s “Dining Philiosophers” problem: According to Wikipedia.org, in computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes. The problem is analogous to that of keeping a barber working when there are customers, resting when there are none and doing so in an orderly manner.
The Solution: a possible solution according to Wikipedia involves using three semaphores: one for any waiting customers, one for the barber (to see if he is idle), and the third ensures mutual exclusion. When a customer arrives, he attempts to acquire the mutex, and waits until he has succeeded. The customer then checks to see if there is an empty chair for him (either one in the waiting room or the barber chair), and if none of these are empty, the customer leaves. Otherwise the customer takes a seat which reduces the number available (a critical section). The customer then signals the barber to awaken through his semaphore, and the mutex is released to allow other customers (or the barber) the ability to acquire it. If the barber is not free, the customer then waits. The barber sits in a perpetual waiting loop, being awakened by any waiting customers. Once he is awoken, he signals the waiting customers through their semaphore, allowing them to get their haircut one at a time.
This problem involves only one barber, and it is therefore also called the single sleeping barber problem. A multiple sleeping barber’s problem is similar in the nature of implementation and pitfalls, but has the additional complexity of coordinating several barbers among the waiting customers.
Michael Simpson
References:
http://en.wikipedia.org/wiki/Edsger_W._Dijkstra
http://en.wikipedia.org/wiki/Sleeping_barber_problem
The sleeping barber problem is a synchronization problem. The problem revolves around a barber shop that has one barber, one barber chair, and several waiting chairs. When there are no customers, the barber sits in his chair and sleeps. As soon as a customer arrives, he either awakens the barber or if the barber is cutting someone's hair, he sits down on one of the waiting chairs (or he leaves if the waiting chairs are all occupied). The problem consists of engaging in the activity without any race conditions. The solution involves using semaphores and mutexes to guard the critical region where starvation and deadlock could occur.
The most common solution involves using three semaphores: one for any waiting customers, one for the barber (to see if he is idle), and a mutex. When a customer arrives, he attempts to acquire the mutex, and waits until he has succeeded. The customer then checks to see if there is an empty chair for him (either one in the waiting room or the barber chair), and, if none of these are empty, leaves. Otherwise the customer takes a seat – thus reducing the number available (a critical region). The customer then signals the barber to awaken through his semaphore, and the mutex is released to allow other customers (or the barber) the ability to acquire it. If the barber is not free, the customer then waits. The barber sits in a perpetual waiting loop, being awakened by any waiting customers. Once he is awoken, he signals the waiting customers through their semaphore, allowing them to get a hair cut one at a time.
http://en.wikipedia.org/wiki/Sleeping_barber_problem
Timothy
The dining philosophers problem is summarized as five philosophers sitting at a table doing one of two things: eating or thinking. While eating, they are not thinking, and while thinking, they are not eating. The five philosophers sit at a circular table with a large bowl of spaghetti in the center. A fork is placed in between each pair of adjacent philosophers, and as such, each philosopher has one fork to his left and one fork to his right. As spaghetti is difficult to serve and eat with a single fork, it is assumed that a philosopher must eat with two forks. Each philosopher can only use the forks on his immediate left and immediate right.
Illustration of the dining philosophers problemThe dining philosophers problem is sometimes explained using rice and chopsticks rather than spaghetti and forks, as it is more intuitively obvious that two chopsticks are required to begin eating.
The philosophers never speak to each other, which creates a dangerous possibility of deadlock when every philosopher holds a left fork and waits perpetually for a right fork (or vice versa).
Originally used as a means of illustrating the problem of deadlock, this system reaches deadlock when there is a 'cycle of unwarranted requests'. In this case philosopher P1 waits for the fork grabbed by philosopher P2 who is waiting for the fork of philosopher P3 and so forth, making a circular chain.
http://en.wikipedia.org/wiki/Dining_philosophers_problem
Sleeping barber problem
The problem:
The analogy is based upon a hypothetical barber shop with one barber, one barber chair, and a number of chairs for waiting customers. When there are no customers, the barber sits in his chair and sleeps. As soon as a customer arrives, he either awakens the barber or, if the barber is cutting someone else's hair, sits down in one of the vacant chairs. If all of the chairs are occupied, the newly arrived customer simply leaves. The problem arises with attempting to coordinate this activity without bringing about any race conditions, and in this way is similar to many queueing problems. In fact, it is a classic example of a (double) rendezvous problem. Not implementing a proper solution can lead to the usual inter-process communication problems of starvation and deadlock. For example, the barber could end up waiting on a customer and a customer waiting on the barber, resulting in deadlock. Alternatively, customers may not decide to approach the barber in an orderly manner, leading to process starvation as some customers never get the chance for a hair cut even though they have been waiting. The Sleeping Barber Problem is often attributed to Edsger Dijkstra (1965), one of the pioneers in fundamental programming.
The solution:
The most common solution involves using three semaphores: one for any waiting customers, one for the barber (to see if he is idle), and a mutual exclusion (mutex). When a customer arrives, he attempts to acquire the mutex, and waits until he has succeeded. The customer then checks to see if there is an empty chair for him (either one in the waiting room or the barber chair), and, if none of these are empty, leaves. Otherwise the customer takes a seat – thus reducing the number available (a critical region). The customer then signals the barber to awaken through his semaphore, and the mutex is released to allow other customers (or the barber) the ability to acquire it. If the barber is not free, the customer then waits. The barber sits in a perpetual waiting loop, being awakened by any waiting customers. Once he is awoken, he signals the waiting customers through their semaphore, allowing them to get a haircut one at a time.
It all ends up as an exercise in synchronization (timing is everything).
Ted McHugh
http://www.bookrags.com/wiki/Sleeping_barber_problem
http://www.economicexpert.com/a/Sleeping:barber:problem.htm
The dining philosophers problem is summarized as five philosophers sitting at a table doing one of two things: eating or thinking. While eating, they are not thinking, and while thinking, they are not eating. The five philosophers sit at a circular table with a large bowl of spaghetti in the center. A fork is placed in between each pair of adjacent philosophers, and as such, each philosopher has one fork to his left and one fork to his right. As spaghetti is difficult to serve and eat with a single fork, it is assumed that a philosopher must eat with two forks. Each philosopher can only use the forks on his immediate left and immediate right.
Illustration of the dining philosophers problemThe dining philosophers problem is sometimes explained using rice and chopsticks rather than spaghetti and forks, as it is more intuitively obvious that two chopsticks are required to begin eating.
The philosophers never speak to each other, which creates a dangerous possibility of deadlock when every philosopher holds a left fork and waits perpetually for a right fork (or vice versa).
Originally used as a means of illustrating the problem of deadlock, this system reaches deadlock when there is a 'cycle of unwarranted requests'. In this case philosopher P1 waits for the fork grabbed by philosopher P2 who is waiting for the fork of philosopher P3 and so forth, making a circular chain.
http://en.wikipedia.org/wiki/Dining_philosophers_problem
The sleeping barber problem is a synchronization and inter-process communication problem between multiple system processes. A barber shop has one barber chair and multiple chairs in the waiting room. The barber goes to sleep after he checks his waiting room for customers and there are none. If a customer arrives, they wake the barber up. If he is already cutting someone elses hair, they sit down in the waiting area, and if there are no seats available, they leave. The solution is: when a customer arrives, he attempts to acquire the mutex, and waits until he has done so. He then checks to see if there is an open chair in the building, if there is he sits down. This reduces the number available. The customer then signals the barber to wake up, and the chair is up for grabs to another customer. This makes sure that waiting customers always wake up the barber, and it insures that everyone gets a haircut.
We went over the dining philosophers in class where everyone sits at a table and each has to have two forks to eat with. -5 people- One person can’t begin until the person sitting beside him finishes because there is only one fork to the left of each plate. The philosophers never speak to eachother causinjg a risk for deadlock.
Without Wikapedia I would have been completely lost on the Barber problem!
http://en.wikipedia.org/wiki/Sleeping_barber_problem
Ryan O’Neal
The dinning philosophers problem involves five philosophers sitting around a bowl of food with only five forks. Each person can only eat when they have two forks.
This is essentially a metaphor for deadlock and starvation. Sometimes a philosopher is blocked by his peers and can not get any forks symbolizing starvation. Another possibility is that each man could only have one fork, blocking them all from eating symbolizing deadlock.
To counter this, resources must be allocated for equal amounts of time.
http://en.wikipedia.org/wiki/Dining_philosophers_problem
Born May 11, 1930 in Rotterdam, Netherlands – Died August 6, 2002. Dijkstra received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000Just before His death , he received the ACM PODC Influential Paper Award in distributed computing for his work on self-stabilization of program computation. This annual award was renamed the Dijkstra Prize the following year, in his honor. While he had programmed extensively in machine code in the 1950s, he was known for his low opinion of the GOTO statement in computer programming, writing a paper in 1965, and culminating in the 1968 article "A Case against the GO TO Statement", regarded as a major step towards the widespread deprecation of the GOTO statement and its effective replacement by structured control constructs, such as the while loop. This methodology was also called structured programming, the title of his 1972 book, coauthored with C.A.R. Hoare and Ole-Johan Dahl. The March 1968 ACM letter's famous title, "Go To Statement Considered Harmful",[1] was not the work of Dijkstra, but of Niklaus Wirth, then editor of Communications of the ACM. Dijskra also strongly opposed the teaching of BASIC,[2] a language whose programs are typically GOTO-laden.
The Dinning Philosophers problem consists of a finite set of processes which share a finite set of resources, each of which can be used by only one process at a time, thus leading to potential deadlock The problem visualizes this as a number of philosophers sitting round a dining table with a fork between each adjacent pair. Each philosopher may arbitrarily decide to use either the fork to his left or the one to his right but each fork may only be used by one philosopher at a time.
Some potential solutions have been come up with to solve the problem.
. Semaphores - a simple, but unfair solution where each resources is a binary semaphore and additional semaphores are used to avoid deadlock and/or starvation.
Critical Regions - each processor is protected from interference while it exclusively uses a resource.
Monitors - the process waits until all required resources are available then takes all of the resources for use.
The best solution allows the maximum parallelism for any number of processes (philosophers), by using an array to track the process' current state (i.e. hungry, eating, and thinking). This solution maintains an array of semaphores, so hungry philosophers trying to acquire resources can block if the needed forks are busy.
The dining philosophers was a problem of waiting. Each philosopher had to use two forks. The problem arises when each philosopher picks the first fork, there are no more forks to use so none of them can eat. This originally was used to describe dead lock, philosopher 1 waits for philosopher 2 to put his fork down with philosopher 2 waits for philosopher 3 to his fork down and so on. This is also call a cycle of unwarranted requests. One possible solution to this is to implement a "waiter" to give each philosopher permission to pick up both forks. For example, if P1 and P2 are eating there are four forks in use. if P3 were to pick up the 5th fork this was cause a likelihood for dead lock. But, if P3 asked the waiter to eat and was told to wait the next time there were 2 forks available one of the philosophers would definitely get to eat. Therefore, dead lock could not happen.
http://en.wikipedia.org/wiki/Dining_philosophers_problem
Jesse L.
Bijkstra,he recieveded the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.
Shortly before his death in 2002, he received the ACM PODC Influential Paper Award in distributed computing for his work on self-stabilization of program computation. This annual award was renamed the Dijkstra Prize the following year, in his honour
www.personal.kent.edu
www.itl.nist.gov/div897
Catherine Alexander
The problem
The analogy is based upon a hypothetical barber shop with one barber, one barber chair, and a number of chairs for waiting customers. When there are no customers, the barber sits in his chair and sleeps. As soon as a customer arrives, he either awakens the barber or, if the barber is cutting someone else's hair, sits down in one of the vacant chairs. If all of the chairs are occupied, the newly arrived customer simply leaves. The problem arises with attempting to coordinate this activity without bringing about any race conditions, and in this way is similar to many queueing problems. In fact, it is a classic example of a (double) rendezvous problem. Not implementing a proper solution can lead to the usual inter-process communication problems of starvation and deadlock. For example, the barber could end up waiting on a customer and a customer waiting on the barber, resulting in deadlock. Alternatively, customers may not decide to approach the barber in an orderly manner, leading to process starvation as some customers never get the chance for a hair cut even though they have been waiting. The Sleeping Barber Problem is often attributed to Edsger Dijkstra (1965), one of the pioneers in fundamental programming.
A solution
The most common solution involves using three semaphores: one for any waiting customers, one for the barber (to see if he is idle), and a mutex. When a customer arrives, he attempts to acquire the mutex, and waits until he has succeeded. The customer then checks to see if there is an empty chair for him (either one in the waiting room or the barber chair), and if none of these are empty, leaves. Otherwise the customer takes a seat – thus reducing the number available (a critical section). The customer then signals the barber to awaken through his semaphore, and the mutex is released to allow other customers (or the barber) the ability to acquire it. If the barber is not free, the customer then waits. The barber sits in a perpetual waiting loop, being awakened by any waiting customers. Once he is awoken, he signals the waiting customers through their semaphore, allowing them to get their hair cut one at a time. This problem involves only one barber, and it is therefore also called the single sleeping barber problem. A multiple sleeping barbers problem is similar in the nature of implementation and pitfalls, but has the additional complexity of coordinating several barbers among the waiting customers.
http://www.bookrags.com/wiki/Sleeping_barber_problem
Richard
The analogy is based upon a hypothetical barber shop with one barber. The barber has one barber chair and a waiting room with a number of chairs in it. When the barber finishes cutting a customer's hair, he dismisses the customer and then goes to the waiting room to see if there are other customers waiting. If there are, he brings one of them back to the chair and cuts his or her hair. If there are no other customers waiting, he returns to his chair and sleeps in it.
Each customer, when he arrives, looks to see what the barber is doing. If the barber is sleeping, then he wakes him up and sits in the chair. If the barber is cutting hair, then he goes to the waiting room. If there is a free chair in the waiting room, he sits in it and waits his turn. If there is no free chair, then the customer leaves. On a naive analysis, the above description should ensure that the shop functions correctly, with the barber cutting hair of anyone who arrives until there are no more customers, and then sleeping until the next customer arrives. In practice there are a number of problems that can occur, which are illustrative of general scheduling problems.
The problems are all related to the fact that the actions by both the barber and the customer (checking the waiting room, entering the shop, taking a waiting room chair etc.) all take an unknown amount of time. For example, a customer may arrive and observe that the barber is cutting hair, so he goes to the waiting room. While he is on his way, the barber finishes the haircut he is doing and goes to check the waiting room. Since there is no-one there, (the customer hasn't arrived yet) he goes back to his chair and sleeps. The barber is now waiting for a customer and the customer is waiting for the barber. In another example, two customers may arrive at the same time, observe that the barber is cutting hair and there is a single seat in the waiting room, and go to the waiting room. They will both then attempt to occupy the single chair.
"wikipedia.org"
Post a Comment
<< Home