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


by: Dr. Garrison Mohr


Dr. Garrison Mohr
GPA 3.87

Alan Madison

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

Alan Madison
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 6 page Class Notes was uploaded by Dr. Garrison Mohr on Saturday September 26, 2015. The Class Notes belongs to CP SC 322 at Clemson University taught by Alan Madison in Fall. Since its upload, it has received 47 views. For similar materials see /class/214261/cp-sc-322-clemson-university in ComputerScienence at Clemson University.

Similar to CP SC 322 at Clemson




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: 09/26/15
Deadlock chapter 7 Deadlock when a set of processes each holding a resource are waiting to acquire a resource held by another process Blocks execution deadlock prevention ensuring that the system will never enter a deadlock state by restraining the ways requests can be made Usually restrain hold and wait by requiring process to allocate all resources before hand Starvation possible Also can use no preemption where processes that are waiting must release all current resources Restart when regain old and new resources not practical deadlock avoidance crystal ball Keep track of resources to determine if a deadlock could happen keep in safe state Requires information in advance a priori Simplest model requires that each process declare max resources High overhead and loss of concurrency Essentially if in an unsafe state deadlock possible Keep out of unsafe state For single instance of resource type use resource allocation graph For multiple instances use bankers algorithm deadlock detection determining if there is a deadlock in the system easier to do and most common in OS s including UNIX Cheaper to detect and then kill one process to remove deadlock deadlock recovery after detection kill one of processes in deadlock This allows other processes to finish resource allocation graph Visualization tool for processes and resources Edges between processes and resources show claims and requests For deadlock avoidance use claim edges These convert to request edges nondotted then to assignment edge switch direction when allocated Only grant request if converting to an assignment edge will not result in a cycle in the graph This means that deadlock is possible So delay request linear ordering technique for deadlock prevention organize semaphores in order for each process so they don t block each other in deadlock Banker39 s algorithm deadlock avoidance for multiple instances of a resource For each process you keep track per resource of the MAXIMUM resources needed the current ALLOCATION of resources to each process and the AVAILABLE resources in the whole system also keep track of NEED which is MAX ALLOCATION Keep track per time step Circular wait deadlock prevention where you impose a total ordering of all resource types and require that each process requests resources in an increasing order of enumeration consumable resource created and consumed by a process hold and wait Deadlock prevention Guarantee whenever a process requests a resource it does not hold any other resources reusable resource fixed number of resources neither created or destroyed dining philosophers N philosophers and N chopsticks philosophers either are eating or thinking But need two chopsticks to eat Multiple solutions to problem Sub optimal solutions include one philosopher left handed or only allowing four philosophers at the table at once Linear memory management sections of chapters 8 and 9 used to allocate small chunks of memory to the CPU called frequently and sequentially Cant predict order of allocs and frees Fragmentation memory is broken up into chunks too small to be usable external fragmention space outside of allocated blocks that are too small to be usable internal fragmentation space inside of the allocated block that is unused in excess Caused by algorithm Compaction moves all fragments to end of memory combining holes Overhead of moving pointers etc Have to keep track of pointers or not possible buddy system power of 2 method designed to efficiently coalesce blocks Blocks can only coalesce with its buddy Use a tag at the front of a block Can only coalesce if our buddies tag is free and the same size To figure out if it s a left or right buddy just take into account the pointer of the block subtract the start of linear memory pointer and then divide by the block size This gives you the block number if it is even then it s a left buddy if it s odd right buddy To free a block we first make sure that our buddy is totally free if not we add block to appropriate free list and exit If buddy is free we remove buddy from its free list coalesce blocks to a bigger block and update the tag THEN repeat by check buddy of larger block Lazy buddysystem buddy system has problems with coalescing too much and wasting time So lazy buddy system only coalesces when there is excessive fragmentation Used in early linux Have thresholds of ratio of free to allocated blocks per free list When a free occurs if below threshold then don t attempt coalesce if around threshold coalesce one level if above threshold coalesce aggressively Memory Allocation Strategies r st t algorithm pick rst block encountered on free list and divide best t algorithm search free list for smallest block that is big enough to honor request next t algorithm start search for right sized block with the next block after last Keep track of index Variant of first fit boundarytag all blocks allocated or free contain a tag containing status information size and whether free or allocated bit map keep list of ones and zeros whether free or allocated Advantage is less memory overhead but bad in that more work is required to coalesce and determine size of blocks being freed powerofZ technique memory management technique multiple free lists are maintained each for free blocks of the same power of 2 size Fastest allocation and frees good for multiprocessors because lists can be accessed concurrently Space efficient cause you don t have tags except for buddy system Advantage of quickly finding blocks instead of having to search through all of them Disadvantage is internal fragmentation Superblocks may not be all used McKussickKarl allocator used to solve the problem of multi processor contention for free lists Power of 2 method with free lists per processor call and global free lists Requests serviced from local lists first requiring no locking if cant be serviced lock and access global lists Splitting and coalescing only done at global level slab allocator first in Solaris then Linux Most requests are for space for objects that are known So keep lists of different object sizes PCB Network CB etc per processor Virtual Memory chapter 8 fetch policy when is a page retrieved from disk Prefetch guess which pages will be used and fetch them Or demand paging demand paging bring a page in only when needed Prepaging placement policy which available frame should be allocated when a page fault occurs Doesn t actually matter replacement policy when all frames are currently allocated which frames get out least recently used LRU not able to bne implemented in hardware least frequenty used LFU kick out page that has been used the least Not effective FIFO Simple clock policy gets the frame after the last loaded frame Modi ed clock policy 4pass same as simple clock get the frame after the last loaded most recently loaded that is not have the reference or modi ed bit optimal policy optimal page replacement is where you replace the page that will be not be referenced for the longest time in the future hit ratio virtual page logical address page frame physical page in memory page management table reference use bit this page was just referenced Set to l by MMU when page referenced modi ed bit this page was modi ed or changed valid bit bit that keeps track of whether this page is in the processes logical address space Legal or not Valid is in memory invalid is not translation lookaside buffer TLB associative hardware implemented lookup cache Give it page number it gives you physical frame Locality page fault interrupt If there is a reference to a page that is invlaid traps to operating system if page soes not eXit abort else try to fetch the frame Page replacement policies thrashing working set locality page fault frequency PFF algorithm mernory mapped les Process Synchronization you should also review many of the terms covered by the last test binary semaphore general or counting semaphore mutex mutual exclusion producerconsumer semaphore operations semWaitO semSignalO sernInit CPS C 322 Final Exam Study Guide Test 1 Material Test 2 Material Mass Storage Transfer rate rate at which data ows between drive and computer Seek time time it takes to move the disk reader head to the right place Rotational delay time required for the addressable area ofa computer s disk drive to rotate into a position where it is accessible to the read write head Transfer time time it takes to transfer the data into memory Disk Scheduling Policies the operating system is responsible for using hardware efficiently for the disk drives this means having a fast access time and disk bandwidth Essentially want to minimize seek time So we need a policy to govern how to service requests for things from and too memory Illustrated with a request queue FCFS first come first serve It is fair but it requires excessive head movement FIFO LIFO SSTF Shortest Seek Time First Good in that it reduces seek time bad in that starvation is possible SCAN the disk starts at one end of the disk and moves toward the other end servicing requests until it gets to the other end of the disk where the head movement is reversed and servicing continues Also called the elevator algorithm CScan provides a more uniform wait time than SCAN the head moves from one end of the disk to the other servicing requests as it goes when it reaches the end it returns immediately back to the beginning without servicing requests on the return trip Circular Scan CLOOK version of CSCAN where arm only goes as far as the last request in each direction then reverses direction immediately without first going to the end of the disk SSTF is common and has natural appeal SCAN and CSCAN perform better for systems that place a heavy load on the disk The algorithm should be modular and easily replaceable so a new algorithm can be used if necessary SSTF or LOOK are good defaults Seek time rotational delay transfer time all in uence diskscheduling policies RAID Redundant Array of Inexpensive Drives Multiple disk drives provide reliability through redundancy Arranged into six different levels to achieve better performance or reliability or both Techniques Striping files are broken into several small parts each part is put on a different RAID disk This allows better performance because data access is faster Mirroring each file has an exact copy on another disk Redundancy Parity Parity data is special code generated when data is written to the array that allows it to rebuild a whole disk if one should fail RADI 0 aka Striping setup where data is striped across two or more disks Faster but a lot less safer All the data is corrupted ifjust one disk fails RAID 1 Mirroring All the data is mirrored Much safer redundant but not faster Sometimes slower in some cases because of time for memory access RAID 5 Striping with Parity requires at least three disks making it more affordable in terms of disks to operate than RAID 01 or 10 Operates by striping a given amount of data on each disk that way the array can still function if one disk is lost So provides striping increase speed and has good redundancy So essentially a disk s worth ofparity data is all that s required Not as fast as RAID 0 but faster than a single disk drive Systems Security Con icting Goals of Securing a System choose two cheap usable secure Symmetric Encryption same key used to encryp 0t and decryprt Asymmetric Encryption public key encryption based on each user having two keys Public key is published private key is only know to individual users RSA block cipher Access Matrix ACL s Access Control List holds list ofusers associated with their rights to an object Capabilities Authentication verifying the user is who they say they are Homework Review Programming Review


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

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

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!"


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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.