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 client’s. 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.
Get Help With Your Essay
If you need assistance with writing your essay, our professional essay writing service is here to help!
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 Dijkstra’s 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.
Here’s 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 it’s 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 there’s room to spare. Whether I go or I expect;
When I’m 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 client’s arrival, the second for his departure.
Here’s 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 client’s 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.
Find Out How UKEssays.com Can Help You!
Our academic experts are ready and waiting to assist with any writing project you may have. From simple essay plans, through to full dissertations, you can guarantee we have a service perfectly matched to your needs.
View our academic writing services
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 can’t 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 hasn’t 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
Cite This Work
To export a reference to this article please select a referencing style below:
