The Sleeping Barber Problem Philosophy Essay

The Sleeping Barber Problem Philosophy Essay This report includes concurrent programming and deadlocks that were created and analysed throughout the report. There are two parts that include in the report; The Sleeping Barber Problem and The Dining Philosophers. The report includes every method that was used to complete both parts; this includes explaining and describing. For my references I used a couple of websites to help me understand more about the concept. Introduction In this report I have included two parts these are as follows: The Sleeping Barber Problem The 1st part of my assignment is about a barber shop. I have written a program to simulate the use of a monitor to coordinate the operation of the barber and the clients. The barber shop includes only one barber that works.  The living room is divided into a waiting room with a fixed number of chairs and a table with comics, and a workroom where the barber cuts hair of a customer.  Incidentally this work room serves as bedroom when it was not customer as our barber has the nasty habit of partying all night, so it catches up on sleep lost when the room is quiet.   When a customer arrives, it opens the door to the salon.  If no space is available, it remains outside. Otherwise it will sit in an empty chair.  At the opening of the door chime sounds to awaken our Venetian barber if he had bitten a nap.  When the barber releases a client, it does not have the right to sleep if there is room in the world.   When the barber finished cutting a customer, it pays 10 francs. Then he leaves the room.  The barber takes the next customer, if he goes to bed   and so on. The Dining Philosophers The 2nd part of the report is about one of Dijkstras more delightful contributions is his problem of the Dining Philosophers. It illustrates many of the subtle problems inherent in concurrent programming. The Sleeping Barber Problem Approach to the program and Analysis The barber shop has many different types of solutions as many different types of program languages can be used to solve the problem. I had many different types of thought, but then came to a stage and chose to use Java coding as I have more experience in this program. The threads Our program will be divided into two types of threads.  On one side there will be the barber, represented by a single thread looping constantly to see if a customer expects, take care of him if necessary or when going to bed.  On the other side there will be a thread per client, which simulate the physical customer.  He will try to return to the store, will sit if he can, will shave and disappear.   While our program will have one barber, there may be as many customers as men on the planet (or at least memory space).  Threads so customers will stack until the space become available in the waiting room, and then the barber takes care of them. I will now show what each the barber and customers role are inside the program: What is the barber? The thread symbolizing the barber will be unique.  It will START s launch, customer foremost and will loop on itself for eternity.   Heres what our barber is to spend his life on: Is there anyone in the waiting room?  If so I take care of his case, if I not go to bed and have a nap When a client I do is enter the slaughterhouse; I cut hair I get my money then he leaves Obviously, when you get to the end we re-loop. This re-loop is done as many different actions are taken therefore its needed in Java programming. What is the customer? Here are the actions that realize the thread symbolizing each client.  If there are multiple clients, identical threads will compete: I look in the salon to see if theres room to spare.  Whether I go or I expect; When Im inside I sit on a chair I expect that the barber is free; I get up from my chair (and thus frees up) and I enter the room; I let his beard trimmed; When he finished, I pay and I get home. Read comics if seat available at waiting room Looking at the size difference between the action list of the barber and the customer, we note that the customer is more things.  In fact, the customer must manage additional resources from the barber the free space in the waiting room when present at the exhibition entrance. Resources Writing and explaining how the program will be running plays a big role in having a successful program. I have to know what type of resources and the needs of the program I need to make it work perfectly. The needs: Firstly it is clear that we will have a semaphore on the number of seats available in the waiting room.  It will limit the number client can find the room simultaneously.  When a client is present supernumerary the thread will wait for the release of the resource (the chair).   Now we must manage the sleep of the barber.  We need a semaphore blocking the barber when there is no client.  It must be incremented to the arrival of each client and initialized to zero.   Must thread the barber and the customer have a time in common when haircuts takes place.  There are a myriad of  bitouilles  possible, but the simplest is to have two semaphores: one for the clients arrival, the second for his departure.   Heres how the four semaphores will be used in our  virtual barber: places Number of seats available in the waiting room of the exhibition upon arrival of a client, it performs a  wait  on the semaphore.  If the number is zero free space on his arrival, he will wait for a client releases a chair.  The client makes a  post  when he managed to enter the room of the barber (so it rises from the chair). salle_vide The semaphore  salle_vide  corresponds to a value equal to the number of customers in the waiting room.  it is 0 when the latter does not have any customer.  The barber performs a  wait  on the semaphore and crashes (goes to sleep) when the room is empty. room This semaphore is initialized to 0.  Any customer arriving in the waiting room waits for the release of this resource.  He was released by the barber when it is ready to receive a clients piece of work. Out The purpose of this semaphore is very similar to the previous one.  The client performs a  wait  is over and the barber freeing this resource by a  post  when he finished shaving the customer.  While the semaphore before the start synchronization shaving, it synchronizes the end. I will now present a summary of the evolution of each of these semaphores during the passage of a client in the salon.  I guess the room is empty before it happened and that no other client comes while he is there.  I do not dà ©crierai lock operation, it is quite explicit.   places salle_vide room out action initial state 8 0 0 0 exec (hand) barber lying 8 (0) 0 0 b:  wait (salle_vide) arrival of a customer (8) (0) 0 0 c:  wait (squares) the client asseoie 7 + (0) 0 0 c:  post (salle_vide) the client waits 7 0 (0) 0 c:  wait (piece) Client Home 7 0 + (0) 0 b:  post (piece) between the customer 7 0 0 0 c:  post (places) shaving client 8 0 0 (0) c:  wait (outside) the barber shaves 8 0 0 (0) b:  sleep () it releases its customer 8 0 0 + (0) b:  post (outside) Semaphores framed by a pair of parentheses mean that  wait  has been done on this resource and a thread is blocked, waiting for the release of this resource.  + Means that the  post  has been taken. Program Organisatized Our program virtual the barber  has three global variables: Four semaphores The lock to the body The value of the fund It also has two functions:  proc_barbier  and  proc_client  respectively procedures barber and client.  The main program (main) deals first initialize the semaphore and lock.  Then it creates the thread corresponding to the barber.  It goes straight to bed since no customer has yet been created.  Simulating client threads are created one by one dynamically when the user presses the I entry.  If he lets his finger pressed the button a few seconds can quickly create a large number of clients.  The results of the application are sent to standard output (stdout). Instructions for use:  On a fast station this small program can quickly make mistakes.  Under the Linux operating system the machine uses the kernel call  clone ()  to create a new thread, which has the effect of creating a new process.  In my tests I found (after falling asleep myself on the  entry   key) with more than 200 client process waiting for my poor barber. There are two main methods used inside the program this includes the following; Barber; while(1) { P(Customers) //wait for C and sleep P(accessSeats) //mutexprotect the number of available seats NumberOfFreeSeats++ //one chair gets free V(Barber) //Bring in a C for haircut V(accessSeats) //release the mutexon the chairs à ¢Ã¢â€š ¬Ã‚ ¦Ãƒ ¢Ã¢â€š ¬Ã‚ ¦. //here the B is cutting hair This green highlighted writing is showing the comments of the codes.} //while(1) Customers while(1) { P(accessSeats) //mutexprotect the number of available seats if ( NumberOfFreeSeats> 0 ) { //if any free seats NumberOfFreeSeats //sitting down on a chair V(Customers) //notify the B V(accessSeats) //release the lock P(Barber) //wait if the B is busy à ¢Ã¢â€š ¬Ã‚ ¦. //here the C is having his hair cut } else { //there are no free seats V(accessSeats)//release the lock on the seats //C leaves without a haircut } }//while(1) The Dining Philosophers The example below shows a solution where the forks are not explicitly represented. Philosophers can eat if you eat any of its neighbors. This is comparable to a system where the philosophers who cannot get the second fork must leave the first fork before they try again. In the absence of locks associated with the forks, philosophers must ensure that the decision to start eating is not based on stale information on the state of the neighbors. Eg if philosopher B sees that A does not eat, then turns and looks C, A could begin eating while B looks at C. This solution avoids this problem by using a single mutex lock. This lock has nothing to do with the holders, but with the decision procedures that can change the states of the philosophers. This is ensured by the monitor. The test procedures, collection and observation are local offensive to monitor and share a mutex lock. Note that philosophers who want to eat do not hold a fork. When the monitor allows a philosopher who wants to continue eating, the philosopher acquires again the first fork before picking up the second fork now available. When done eating, the philosopher will signal to the monitor that both forks are available now. Note that this example does not address the problem of hunger. For example, the philosopher B can wait forever if meal periods of philosophers A and C always overlap. To also ensure that no philosopher is hungry, you could keep track of the number of times that a philosopher cannot eat when hungry neighbors leave their holders. If this number exceeds some threshold, the state of the philosopher could change to Hunger, and the decision procedure for collecting holders could be increased to require that none of the neighbors go hungry. This further reduces dependence coincidence. The lifting of the threshold for the transition to the Hungry reduces this effect. In 1984, K. Mani Chandy and J. Misra proposed a different solution to the problem of dining philosophers have considered arbitrary reagents (numbered P , P) compete for an arbitrary number of resources, unlike Dijkstra solution. Also fully distributed and does not require any central authority after initialization. However, violates the requirement that the philosophers do not speak to each other (due to the prompts). For each pair of philosophers who compete for a resource, create a fork and give it to the philosopher with the lower ID. Each holder may be either dirty or clean. Initially, all forks are dirty. When a philosopher wants to use a set of resources (ie eating), must obtain the holders of its neighbors that fall. When a philosopher with a fork receives a request message, keeps the fork if it is clean, but leaves when it is dirty. If you send the fork, the fork cleans before doing so. After a philosopher is done eating, all his forks become dirty. If another philosopher had previously requested one of the forks, clean the fork and sends it. This solution also has a large level of coincidence and has solved a problem arbitrarily large. It also solves the problem of hunger. The clean / dirty labels serve as a way to give preference to process more hungry and a disadvantage to processes that just eat. One might compare its solution one where the philosophers are not allowed to eat twice in a row while others use forks between. Their solution is more flexible than this, but has an element that tends in that direction. In their analysis take a tiered distribution preferred holders and their states clean / dirty. They show that this system can describe an acyclic graph, and if so, the operations in their protocol cannot convert that one cyclic graph. This ensures that the deadlock cannot occur. However, if the system is initialized to an absolutely symmetrical, like all philosophers holding their forks on the left, then the graph is cyclic in the beginning, and its solution cannot prevent a deadlock. Initializing the system so that the IDs below philosophers holders have dirty ensures that the top graph is acyclic. Implementations of a typical philosopher I will now be commenting on some of the implementations of a typical philosopher: Figure 2.2 1 typicalPhilosopher() //Name 2 { 3 while ( true ) // while loop used 4 { 5 think(); //typical philosopher is thinking 6 7 pickUpLeftFork(); //typical philosopher picks up the left fork 8 pickUpRightFork(); //typical philosopher pick up the right fork 9 10 eat(); //typical philosopher is now eating 11 12 putDownLeftFork(); //typical philosopher puts down the left fork 13 putDownRightFork();//typical philosopher puts down the right fork 14 } // end while 15 16 } // end typicalPhilosopher Figure 2.3 1 typicalPhilosopher()//Name 2 { 3 while ( true ) // while loop used 4 { 5 think();//typical philosopher is thinking 6 7 pickUpBothForksAtOnce(); //typical philosopher picks up both folks 8 9 eat();//typical philosopher is now eating 10 11 putDownBothForksAtOnce();//typical philosopher puts both folks down 12 } // end while 13 14 } // end typicalPhilosopher Figure 2.4 1 typicalPhilosopher()//Name 2 { 3 while ( true ) // while loop used 4 { 5 think();//typical philosopher is thinking 6 7 while ( notHoldingBothForks ) //while loop used so that typical philosopher cant pick up both folks at once 8 { 9 pickUpLeftFork();//typical philosopher pick up the left fork 10 11 if ( rightForkNotAvailable ) //he picks up the left for in the previous if he hasnt got the right fork available 12 { 13 putDownLeftFork();//typical philosopher puts the left fork down 14 } // end if 15 else //if else statement used to make it work properly 16 { 17 pickUpRightFork();//typical philosopher picks up the right for 18 } // end while 19 } // end else 20 21 eat(); 22 23 putDownLeftFork();//typical philosopher puts the left fork down 24 putDownRightFork();//typical philosopher puts the right fork down 25 } // end while 26 27 } // end typicalPhilosopher Figure 2.5 1 typicalPhilosopher() 2 { 3 while ( true ) 4 { 5 think();//typical philosopher is thinking 6 7 if ( philosopherID mod 2 == 0 )//if the remainder is not 0 it performs action if 0 then performs the action 8 { 9 pickUpLeftFork();//typical philosopher picks up the left fork down 10 pickUpRightFork();//typical philosopher picks up the right fork down 11 12 eat(); 13 14 putDownLeftFork();//typical philosopher puts the left fork down 15 putDownRightFork();//typical philosopher puts the right fork down 16 } // end if 17 else 18 { 19 pickUpRightFork();//typical philosopher picks up the right fork 20 pickUpLeftFork();//typical philosopher picks up the left fork 21 22 eat();//typical philosopher is eating 23 24 putDownRightFork();//typical philosopher puts the left fork down 25 putDownLeftFork();//typical philosopher puts the right fork down 26 } // end else 27 } // end while 28 29 } // end typicalPhilosopher As you can see from the above figure of the typical philosopher different types of condition and statements were used. These statements and conditions allow the program to implement different types of actions. Conclusion Recommendation