New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Intro Oper System

by: Ophelia Ritchie

Intro Oper System EECS 482

Ophelia Ritchie
GPA 3.8


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Engineering Computer Science

This 11 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 482 at University of Michigan taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/231546/eecs-482-university-of-michigan in Engineering Computer Science at University of Michigan.

Similar to EECS 482 at UM

Popular in Engineering Computer Science


Reviews for Intro Oper System


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: 10/29/15
Deadlocks and Starvation Readings Chapter on Deadlocks in Tanenbaum You can skip Deadlock Detection and Banker s Algorithm 0 We looked at solving synchronization problems using monitors and semaphores 0 Unfortunately problems can arise Example 1 Recall our solution to the readerwriter problem It was possible for readers to wait inde nitely if new writers kept coming in On the other hand writers would not wait inde nitely as long as ready threads are served in order Why Example 2 Thread A Thread B lockX Locky locky LockX Use resource X and Y Use resource X and Y Unlocky UnlockX UnlockX Unlocky In this case it is possible that both Thread A and Thread B wait inde nitely for each other with no progress being made What is common and different between the above examples Common aspect Both problems involve threads waiting for resources to become available They can also involve 0 Resources things needed by a thread to do its job a thread waits for resources 0 eg locks AWWW 0 ie database is free from active or waiting writers disk blocks memory pages inde nitely Differences between the two examples The type of waiting is different Indefinite wait In both examples a thread may end up waiting 0 Starvation A thread may wait inde nitely because other threads keep coming in and getting the requested resources before this thread does Note that resource is being actively used and the thread will stop waiting if other threads stop coming in 0 Deadlocks A group of threads are waiting for resources held by others in the group None of them will ever make progress Example 1 has starvation but Example 2 does not A solution to a synchronization problem suffers from the starvation problem if starvation is a possibility Usually differences in priorities can lead to starvation Lower priority threads starve if higher priority threads keep requesting the resources A solution suffers from the deadlock problem if a deadlock is a possibility In Example 2 will a deadlock always occur In Example 2 can a deadlock occur Realistically on any one run of the two threads is a deadlock a low probability event or a highprobability event What is the sequence of events that must occur for a deadlock to happen assuming Thread 1 starts out rst If a deadlock does happen is it a serious event Avoiding starvation 0 Switch priorities so that every thread has a chance to have high priority 0 Eg Readers give priority to waiting writers but active writers give priority to waiting readers When both are waiting they will end up alternating o Raise priority if a thread has been waiting too long 0 Use FIFO order among competing requests Preventing deadlocks To understand how to prevent deadlocks one must gure out necessary conditions for a deadlock to occur There are four necessary conditions all of which must hold for a deadlock to occur If any one condition fails then you cannot have a deadlock p t Limited shared resource ie not enough to serve all threads simultaneously Otherwise there s no waiting 2 N0 preemption Preemption means you forcefully take away the resource from someone Hard to do that with locks 3 Hold and wait Threads in a deadlock hold a resource and wait for another resource 4 Circular wait Lock X Thread A thread A is waiting for resource y resource y is held by thread B thread B is waiting for resource X resource X is held by thread A 0000 The above is called a wait for graph Are the conditions independent Or does one condition imply another If they are not independent why list all of them Example 3 circular waiting for resources eg both EECS 484 and EECS 482 are full 0 you want to switch from EECS 484 to EECS 482 but want to be sure that you end up in either 484 or 482 0 someone else wants to switch from EECS 482 to EECS 484 To switch you want to add the new course then drop the old course don39t want to drop the old course and not be able to add the new course Both of you are waiting for each other to drop the course will wait forever The shared resources in this case is spot in the two classes Deadlock always leads to starvation but not necessarily Vice versa Example 4 dining philosophers This is a classic problem also due to Dijkstra 5 philosphers sitting around a round table 1 chopstick in between each 5 chopsticks total each philosopher needs two chopsticks to eat Algorithm for philosopher wait for right chopstick to be free then pick it up wait for left chopstick to be free then pick it up eat put both chopsticks down Can this deadlock If so how What to do about deadlocks l Ignore them this is actually a pretty common solution because the others are hard and costly If you have two processes waiting for each other those processes just hang other processes can run ne though 2 detect and X 3 prevent Detect and fix 0 detect the easy part 0 Scan the waitfor graph and detect cycles 0 X the hard part I shoot the thread force it to give up the resources that it s holding This isn39t always possible e g if you shoot a thread that s holding a lock the shared data is left in an inconsistent state 2 rollback actions of l or more threads try again common technique in databases transactions This solves the quotinconsistent statequot problem in 1 by rolling back the thread to before it held the lock Not always possible to roll back a thread Eg how do you undo the ring of a missile Deadlock prevention and avoidance Basic ide a is to get rid of one of the 4 necessary conditions 1 Make resources unlimited or at least enough that there s no waiting 2 A110 0 Frequently impossible but this is the best solution Even if you can t make it so deadlock is impossible you can make it very unlikely E g large classrooms Still possible to have full classes but unlikely Sometimes if you cannot make resources unlimited you can reduce the number of threads competing for them Dining Philosophers w preemption can preempt CPU save its state in its thread control block and switch get back to it later can preempt memory eg by saving it to disk and loading it back later can t preempt the holding of a lock Usually not applicable to synchronization problems because it is dangerous to preempt locks A thread may be in the middle of a critical section 3 Eliminate hold and wait 0 Eliminate hold if can t satisfy resource right away thread dies E g phone company If it can t get all the lines needed to call California you get a busy signal 0 Timeout requests for each lock and retry Will this work in Example 2 This is just another form of waiting if some resources are still held This is sometime called a livelock 0 On a timeout threads must be prepared to back out all the way giVing up all the held resources and retry 0 Eliminate wait while holding Request all resources at beginning Eg grab both chopsticks at same time or grab one chopstick If the other is busy drop the one you grabbed This could be Viewed as undoing its recent actions 0 hard to predict the future Tend to overestimate how many resources need Inefficient because it reserves all resources at beginning 4 Circular chain of requests Impose an ordering between resources and ensure that you always request resources in order


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.