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

Operating Systems

by: Mrs. Carolyne Abbott

Operating Systems CS 4414

Mrs. Carolyne Abbott
GPA 3.71

Sang Son

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

Sang Son
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 13 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 4414 at University of Virginia taught by Sang Son in Fall. Since its upload, it has received 56 views. For similar materials see /class/209669/cs-4414-university-of-virginia in ComputerScienence at University of Virginia.


Reviews for Operating Systems


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/21/15
CS 414 Operating Systems UNIVERSITY OF VIRGINIA Department of Computer Science Spring 2008 Topic 12 Sharing Main Memory Segmentation a Goal let several processes coexist in memory a Issues a Transparency No process should need to be aware of the fact that memory is shared Each must run regardless of the number andor locations of processes 0 Protection processes must not be able to corrupt each other a Ef ciency both of CPU and memory shouldn t be degraded badly by sharing After all what is the purpose of sharing a Simple uniprogramming with a single segment per process 0 Highest memory holds OS 0 Process is allocated memory staiting at 0 up to the OS area a When loading a process just bring it in at 0 0 Relocation 0 Because several processes share memory we can t predict in advance where a process will be loaded in memory This is similar to a compiler s inability to predict where a subroutine will be after linking 0 Relocation adjusts a program to run in a different area of memory Linker is an example of static relocation used to combine modules into programs 0 Static relocation 0 Highest memory holds OS 0 Processes allocated memory staiting at 0 up to the OS area 71217 When a process is loaded relocate it so that it can run in its allocated memory area Problem not much protection hard to relocate later once it starts running a Dynamic relocation instead of changing the addresses of a program before it s loaded change the address dynamically during every reference Under dynamic relocation each programgenerated address called a logical or virtual address is translated in hardware to a physical or real address This happens as part of each memory reference Dynamic relocation leads to two views of memory called address spaces A good case of a problem solved by indirection What is the name of the game Flexi bility to move things around freely a Base amp limit relocation Two hardware registers base address for process limit register that indicates the last valid address the process may generate Each process must be allocated contiguously in real memory On each memory reference the virtual address is compared to the limit register then ad ded to the base register A limit violation results in an error trap Each process appears to have a completely private memory of size equal to the limit re gister plus 1 Processes are protected from each other No address relocation is neces sary when a process is loaded OS runs with relocation turned off a bit in the processor status word controls reloca tion It is called unmapped Why is it necessary OS must prevent users from turning off relocation or modifying the base and limit regis ters Problem how do you get kernel bit on when you jump Base amp limit is cheap only 2 registers and fast the add and compare can be done in parallel a Problem with base amp limit relocation Only one segment How can two processes share code while keeping private data areas eg shared editor 71227 a Multiple segments Permit process to be split between several areas of memory Use a separate base and limit for each segment and also add two protection bits read and write Each memory reference indicates a segment and offset a Top bits of address select segment low bits the offset Segment table holds the bases and limit for all the segments of a process Memory mapping procedure consists of table lookup add compare a Segmentation example 3bit segment number 9bit offset 0 Segment table all numbers in octal Segment Base Limit RW 0 4000 577 10 1 1000 777 11 2 2000 677 10 3 0 777 11 4 00 5 00 6 00 7 3000 777 11 a Main program addresses are Virtual octal 242 PUSH 3106 246 CALL SIN 250 a SIN procedure addresses are Virtual 2360 MOVE 2 SPR2 2364 MOVE R2R3 RETURN i 123 i CS 414 Operating Systems UNIVERSITY OF VIRGINIA Department of Computer Science Spring 2008 Topic 8 CPU Scheduling Readings for this topic Chapter 5 OS typically consists of two paits 1 Process coordination and 2 Resource Management Resources fall into two classes a Preemptible vs Nonpreemptible a Is this distinction absolute Real issue OS makes two related kinds of decisions about resources What is the goal a Allocation who gets what Implication 0 Scheduling how long can they keep it Implication Resource 1 Processes may be in any one of three general scheduling states a Running a Ready a Blocked Goals for scheduling disciplines a Ef ciency of resource utilization keep CPU and disks busy 0 Minimize overhead context switching a Minimize response time De ne response time a Distribute cycles equitably What does this mean 7817 FIFO also called FCFS run until nished 0 Usually nished means blocked a Problem Solution limit maximum amount of time that a process can run without a context switch This time is called a time slice Round Robin run process for one time slice then move to back of queue Each process gets equal share of the CPU What if the slice isn t chosen carefully a T 00 long 0 Too small Originally Unix had 1 sec time slices Right size Most systems today use time slices of 10000 100000 instructions How to implement priorities in R Is RR always better than FIFO What is the best we can do Is there quotperfectquot scheduling algorithm ST CF shortest time to completion rst with preemption In what sense is it the best Example two processes one doing 1 ms computation followed by 10 ms IO one doing all computation Suppose we use 100 ms time slice IO process only runs at 1 10th speed IO devices are only utilized 10 of time Suppose we use 1 ms time slice then computebound process gets interrupted 9 times unnecessarily for each valid interrupt STCF works well Why not using STCF Rule of thumb Give the most to those who need the least What s the idea here The strategy 7827 CS 414 Operating Systems UNIVERSITY OF VIRGINIA Department of Computer Science Fall 2005 Topic 2 Processes o Context switching saving the state to where and restoring it What gets saved Everything that next process could damage 0 program counter processor status word registers 0 all of memory all disks all the stuff on tape 0 options for memory contents a trust next process b move everything to disk Alto sys tem 0 memory protection 0 Why tricky o All machines provide some special hardware support 0 Motorola 68000 hardware just moves PC and status word to the stack OS then handles rest of state itself Must be done carefully Why 0 Intel 432 hardware does all state saving and restoring into process control block and even dispatching Desirable o Ugly issue of performance sometimes making dirty shortcuts o Biith of a process creating it from scratch o Allocate memory 0 Load code and data into memory 0 Create empty call stack 0 Create and initialize process control block 0 Make process known to dispatcher 7217 o Forking copying existing process 0 Make sure process to be copied isn t running and has all state saved 0 Make a copy of code data stack 0 Copy PCB into new PCB 0 Make process known to dispatcher What s missing 0 Independent process neither affect nor affected by the rest of the universe 0 its state is not shared in any way with other processes 0 deterministic o reproducible o scheduling does not affect the result 0 There are many different ways in which a collection of independent processes might be exe cuted on a processor 0 How often are processes independent 0 Cooperating processes 0 cooperating processes share state May or may not actually be cooperating o nondeterministic depends on relative execution sequence 0 irreproducible 0 example one process writes ABC to the monitor another writes CBA 0 Why allow processes to cooperate 0 want to share resources 0 one computer many users 0 one le of checking account records many tellers 0 want to do things faster 0 read next block while processing current one o divide job into subjobs execute in parallel 0 Basic assumption for cooperating process systems is that the order of some operations is ir relevant certain operations are independent of certain other operations Only a few things matter 0 example A l B 2 has same result as B 2 A l 7227 CS 414 Operating Systems UNIVERSITY OF VIRGINIA Department of Computer Science Fall 2005 Topic 13 Sharing Main Memory Paging o Readings for this topic Ch8 84 amp 85 o Paging goal is to make allocation and swapping easier 0 Make all chunks of memory the same size call them pages Typical sizes range from 5128k bytes 0 For each process a page table de nes the base address of each of that process pages along with readonly and existence bits Translation process page number always comes directly from the address Since page size is a power of two no comparison or addition is necessary Just do table lookup and bit substitution 0 Easy to allocate keep a free list of available pages and grab the rst one Easy to swap since everything is the same size which is usually the same size as disk blocks to and from which pages are swapped 0 Problems ofpaging 0 Internal fragmentation The larger the page the worse this is o Ef ciency of access even small page tables are generally too large to load into fast memory in the relocation box Instead page tables are kept in main memory and the re location box only has the page table s base address It thus takes one overhead reference for every real memory reference 0 Table space Page tables are big How big Consider a 32bit addresss space with 4k pages as in Windows NT 71317 Paging with segmentation use two levels of mapping to make tables manageable 0 Each segment contains one or more pages 0 Segments correspond to logical units code data stack Segments vary in size and are often large Pages are for the use of the OS they are xedsize to make it easy to manage memory 0 Going from paging to PS is like going from single segment to multiple segments ex cept at a higher level Instead of having a single page table have many page tables with a base and bound for each Call the stuff associated with each page table a segment We can share at two levels single page or single segment whole page table Pages eliminate external fragmentation and make it possible for segments to grow without any reshuf ing If page size is small compared to most segments then internal fragmentation is not too bad The user is not given access to the paging tables Problem with segmentation and paging extra memory references to access translation tables can slow programs down by a factor of two or three Too many entries in translation tables to keep them all loaded in fast processor memory Multilevel paging paging the page table 0 For big address space twolevel paging may not be enough The notion of locality at any given time a process is only using a few pages or segments Solution Translation Lookaside Buffer TLB A translation buffer is used to store a few of the translation table entries It s very fast but only remembers a small number of entries On each memory reference 0 First ask TB if it knows about the page If so the reference proceeds fast 0 If TB has no info for page must go through page and segment tables to get info Refer ence takes a long time but give the info for this page to TB so it will know it for next 71327 reference TB must forget one of its current entries in order to record new one TB Organization Virtual page number goes in physical page location comes out Similar to a cache usually directmapped TB is just a memory with some comparators Typical size of memory 2k entries Each entry holds a virtual page number and the corresponding physical page number How can memory be organized to nd an entry quickly 0 One possibility search whole table from start on every reference 0 A better possibility restrict the info for any given virtual page to fall in exactly one lo cation in the memory Then only need to check that one location Eg use the low order bits of the virtual page number as the index into the memory This is the way real TB s work Why loworder instead of highorder bits Disadvantage of TB scheme if two pages use the same entry of the memory only one of them can be remembered at once If process is referencing both pages at same time TB doesn t work very well Example TB with 64 entries Suppose the following virtual pages are referenced octal 621 2145 621 2145 321 2145 321 621 In practice TB s have been extremely successful 98 hit ratio is typical for 128 entries TBs are a lot like hash tables except simpler must be to be implemented in hardware Some hash functions are better than others 0 Is it better to use low page number bits than high ones Another approach let any given virtual page use either of two slots in the TB Make memory wider use two comparators to check both slots at once i 133 i CS 414 Operating Systems UNIVERSITY OF VIRGINIA Department of Computer Science Fall 2005 Topic 11 Dynamic Storage Allocation 0 Two aspects of memory allocation 0 Static allocation nding a slot in memory big enough to load aout 0 Dynamic allocation while executing the program nding space for additional memory requests 0 Why isn t static allocation suf cient for everything 0 Recursive procedures e g factorial 0 Complex data structures e g symbol table 0 What is the probelm if all storage must be reserved in advance statically OS cannot predict when a process will come and ask for storage space Need dynamic memory allocation both for main memory and for le space on disk Two basic operations in dynamic storage management 0 Allocate 0 Free In general dynamic allocation can be handled in one of two general ways 0 Stack allocation hierarchical LIFO restricted but simple and ef cient o Heap allocation more general but less ef cient more dif cult to implement Stack organization memory allocation and freeing are paItially predictable we do better when we can predict the future 71117 Allocation is hierarchical memory is freed in opposite order from allocation If allocA then allocB then allocC then it must be freeC then freeB then freeA Stacks are also useful for lots of other things tree traversal expression evaluation top down recursive descent parsers etc A stackbased organization keeps all the free space together in one place Why is it im portant o Heap organization allocation and release are unpredictable Heaps are used for arbitrary list structures complex data organizations Example payroll system Don t know when employees will join and leave the com pany must be able to keep track of all them using the least possible amount of storage Memory consists of allocated areas and free areas or holes Inevitany end up with lots of holes Goal reuse the space in holes to keep the number of holes small their size large Fragmentation inef cient use of memory due to holes that are too small to be useful In stack allocation all the holes are together in one big chunk Typically heap allocation schemes use a free list to keep track of the storage that is not in use Algorithms differ in how they manage the free list Best t keep linked list of free blocks search the whole list on each allocation choose block that comes closest to matching the needs of the allocation save the excess for later During release operations merge adjacent free blocks First t just scan list for the rst hole that is large enough Merge on releases Is best t better than rst t First t tends to leave average size holes while best t tends to leave some very large ones some very small ones The very small ones can t be used very easily 71127 0 Bit Map used for allocation of storage that comes in xedsize chunks eg disk blocks or 32byte chunks Keep a large array of bits one for each chunk If bit is 0 it means chunk is in use if 1 it means chunk is free When freeing no need to merge Problems with BF FF and bitmap o Pools keep a separate allocation pool for each popular size Allocation is fast no frag mentation It may get some inef ciency if some pools run out while other pools have lots of free blocks get shuf e between pools o Reclamation Methods How do we know when dynamicallyallocated memory can be freed 0 It s easy when a chunk is only used in one place 0 Reclamation is hard when information is shared it can t be recycled until all of the sharers are nished Sharing is indicated by the presence of pointers to the data 0 Two problems in reclamation o Dangling pointers better not recycle storage while it s still being used 0 Memory leaks better not lose storage by forgetting to free it 0 Two approaches reference counts and garbage collection 0 Reference Counts keep track of the number of outstanding pointers to each chunk of memory When this goes to zero free the memory 0 Garbage Collection no explicit free operation When the system needs storage it searches through all of the pointers must be able to nd them all and collects things that aren t used If structures are circular then this is the only way to reclaim space Makes life easier on the application programmer but garbage collectors are incredibly dif cult to program and debug especially if compaction is also done 71137


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

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

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.