Class Note for CMPSCI 377 at UMass(48)
Class Note for CMPSCI 377 at UMass(48)
Popular in Course
Popular in Department
This 2 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 13 views.
Reviews for Class Note for CMPSCI 377 at UMass(48)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI 377 Operating Systems Fall 2008 Lecture 11 October 7 Lecturer Prashzmt Sherwy Scribe Shashi Singh 1 11 ReadersWriters Problem In computer science the readerswriters problems are examples of a common computing problem in concur rency The two problems deal with situations in which many threads must access the same shared memory at one time some reading and some writing with the natural constraint that no process may access the share for reading or writing while another process is in the act of writing to it ln particular it is allowed for two readers to access the share at the same time 1111 Three types of solutions l Reader preferred waiting readers go before waiting writers A constraint is added that no reader shall be kept waiting if the share is currently opened for reading 2 Writer preferred waiting writers go before waiting readers A constraint is added that no writer once added to the queue shall be kept waiting longer than absolutely necessary 3 Neither preferred try to treat readers and writers fairly a simple queue is not good enough we want parallel readers whenever possible In fact the solutions implied by both problem statements reader preferred and writer preferred result in starvation the reader preferred problem may starve writers in the queue and the writer preferred problem may starve readers Therefore neither preferred problem is sometimes proposed which adds the constraint that no thread shall be allowed to starve that is the operation of obtaining a lock on the shared data will always terminate in a bounded amount of time Solutions to this will necessarily sometimes require readers to wait even though the share is opened for reading and sometimes require writers to wait longer than absolutely necessary Look at the lecture slides for pseudocodes for these three different solutions 1112 pthreads ReadWrite Locks pthread library supports readwrite lock So you donlt have to care for the synchronization among the readers and the writers A thread can acquire a read lock or a write lock Multiple threads can hold the same read lock concurrently but only one thread can hold a write lock Following are the pthread routines pthreadrwlock init pthreadrwlockrdlock pthreadrwlockwrlock pthreadrwlockunlock lll 112 Lecture 11 October 7 112 Dining Philosophers Problem The dining philosophers problem is an illustrative example of a common computing problem in concurrency It is a classic multiprocess synchronization problemi The dining philosophers problem is summarized a bunch of 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 philosophers sit at a circular table with a large bowl of spaghetti in the center A chopstick is placed in between each philosopher and as such each philosopher has one chopstick to his or her left and one chopstick to his or her right As spaghetti is dif cult to serve and eat with a single chopstick it is assumed that a philosopher must eat with two chopsticks The philosopher can only use the chopstick on his or her immediate left or right The philosophers never speak to each other which creates a dangerous possibility of deadlock when every philosopher holds a left chopstick and waits perpetually for a right chopstick or vice versa Originally used as a means of illustrating the problem of deadlock this system reaches deadlock when there is a 7cycle of unwarranted requestsli In this case philosopher P1 waits for the chopstick grabbed by philosopher P2 who is waiting for the chopstick of philosopher P3 and so forth making a circular chaini Starvation might also occur independently of deadlock if a philosopher is unable to acquire both chopsticks due to a timing issue For example there might be a rule that the philosophers put down a chopstick after waiting ve minutes for the other chopstick to become available and wait a further ve minutes before making their next attempti This scheme eliminates the possibility of deadlock the system can always advance to a different state but still suffers from the problem of livelock A livelock is similar to a deadlock except that the states of the processes involved in the livelock constantly change with regard to one another none progressing If all the philosophers appear in the dining room at exactly the same time and each picks up their left chopstick at the same time the philosophers will wait ve minutes until they all put their chopsticks down and then wait a further ve minutes before they all pick them up again The lack of available chopsticks is an analogy to the locking of shared resources in real computer programming a situation known as concurrency Locking a resource is a common technique to ensure the resource is accessed by only one program or chunk of code at a time When the resource a program is interested in is already locked by another one the program waits until it is unlocked When several programs are involved in locking resources deadlock might happen depending on the circumstances For example one program needs two les to process When two such programs lock one le each both programs wait for the other one to unlock the other le which will never happen 1121 Solution to the Dining Philosophers problem A naive solution is to rst wait for the left chopstick using a semaphore After successfully acquiring it wait for the right chopsticki After both chopsticks have been acquired eati When done with eating release the two chopsticks in the same order one by one by call to signal Though simplistic this solution might lead to a deadlock when every philosopher around the table is holding hisher left chopstick and waiting for the right one A variation of this solution makes a philosopher release the left chopstick if it can7t acquire the right one But even this can lead to livelock because of timing issues as explained before The correct solution is to let a philosospher acquire both the chopsticks or none This can be done within a monitor wherein only one philosopher is allowed to check for availability of chopsticks at a time within a test function Look at lecture slide for the complete pseudocodei
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'