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

Peter Chen

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

Peter Chen
Class Notes
25 ?




Popular in Course

Popular in Engineering Computer Science

This 24 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 Peter Chen in Fall. Since its upload, it has received 18 views. For similar materials see /class/231519/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
Address spaces and memory management Review of processes process one or more threads in an address space thread stream of execution unit of concurrency address space memory space that threads use unit of data Address space abstraction address space all the data the process can use as it runs Includes program code stack data segment hardware interface physical reality one memory of small size shared between processes application interface abstraction provided by OS each process has its own memory as large as the Virtual address space Illusions provided by address spaces address independence same numeric address can be used in different address spaces ie different processes yet remain logically distinct virtual memory an address space can be larger than the amount of physical memory on the machine protection one address spaces can t access data in another address space actually controlled sharing EECS 482 Uni r0 rammin 1 process runs at a time viz one process occupies memory at a time Always load process into the same spot in memory and reserve some space for the OS fffff high memory operating system 80000 7ffff user process OOOOO low memory Achieves address independence by always loading process into same physical memory location Problems with uniprogramming Peter M Chen Multiprogramming and address translation Multi programming more than 1 process is in memory at a time need to support address translation need to support protection Must translate addresses issued by a process so they don t con ict with addresses issued by other processes static address translation translate addresses before exe cution translation remains constant during execution dynamic address translation translate addresses during execution translation may change during execution Is it possible to run two processes at the same time both are in memory and provide address independence with only static address translation EECS 482 some work 011 every memory reference Does this achieve the other address space abstractions Achieving all the address space abstractions requires doing Peter M Chen Dynamic address translation Translate eVery memory reference from Virtual address to physical address Virtual address an address Viewed by the user process the abstraction provided by the OS physical address an address Viewed by the physical memory user translator physical process Virtual MMU physical memory address address Translation enforces protection one process can t eVen refer to another process s address space Translation enables Virtual memory a Virtual address only needs to be in physical memory when it s being accessed change translations on the y as different Virtual addresses occupy physical memory Many ways to implement translator Does dynamic address translation require hardware support EECS 482 Address translation Lots of ways to implement the translator Remember big pic ture user translator physical process Virtual MMU physical memory address address Tradeoffs exibility e g sharing growth Virtual memory size of translation data speed of translation Peter M Chen Base amp bounds Load each process into contiguous regions of physical mem ory prevent each process from accessing data outside its region if virtual address gt bound kill process core dump else physical address virtual address base Process has illusion of running on its own dedicated machine with memory 0 bound physical memory physical memory size base bound Virtual bound memOIy base 0 0 EECS 482 This is similar to linkerloader but also protect processes from each other As with all translation data only kernel can change base and bounds During context switch must change all translation data base and bounds registers What to do when address space grows Low hardware cost 2 registers adder comparator low over head add and compare on each memory reference Peter M Chen Hard for a single address space to be larger than physical memory But sum of all address spaces can be larger than physical mem 01 swap an entire address space out to disk swap address space for new process in Can t share part of an address space between processes physical memory data P2 Virtual address Virtual address process 1 process 2 Virtual Virtual memory data P1 memory data code data code 0 code EECS 482 External fragmentation processes come and go leaVing a mishmash of aVailable memory regions process 1 startleO KB phys mem 0 99 KB process 2 start2200 KB phys mem 100 299 KB process 3 start2300 KB phys mem 300 599 KB process 4 startz400 KB phys mem 600 999 KB process 3 exits frees phys mem 300 599 KB process 5 startleO KB phys mem 300 399 KB process 1 exits frees phys mem 0 99 KB process 6 start2300 KB 300 KB are free 400 599 KB 0 99 KB but not contiguous this is called external fragmentation wasted memory between allocated regions Can waste lots of memory Allocation strategies to minimize external fragmentation best t allocate the smallest memory region that can sat isfy the request least amount of wasted space rst t allocate the memory region that you nd rst that can satisfy the request in worst case must reallocate existing memory regions by copying them to another area Peter M Chen Hard to grow address space might have to move to different region of physical mem ory which is slow what parts of the address space might grow as the process runs EECS 482 6 Peter M Chen Segmentation Virtual phys1cal memory memory Segment a region of contiguous memory fff segment 3 Base amp bounds used a single segment Let s generalize this to allow multiple segments described by a table of base amp StaCk 461 d b d I co e oun pairs 0 4 0 segment base bound description 0 4000 700 code segment 1 0 500 data segment 2f Virtual 2 unused memory stack 3 2000 1000 stack segment 4ff segment 1 data 200 In segmentation a Virtual address takes the form 0 Virtual segment offset could specify Virtual segment Via the high bits of the address or Via a special register or implicit to the instruction opcode Virtual memory 6ff segment code 4f data EECS 482 7 Peter M Chen Note that not all Virtual addresses are valid eg no valid data in segment 239 no valid data in segment 1 above 4ff valid means the region is part of the process s virtual address space Invalid means this virtual address is ille gal for the process to access and will cause a core dump if accessed possible to deliberately allow invalid addresses to auto matically extend the address space e g in Unix access ing invalid stack address right above stack bound will trap to the kernel and automatically increase the stack size Protection different segments can have different protection eg code can be readonly allows instruction fetch load eg data is readwrite allows fetch load store in contrast baseampbounds gives same protection to entire address space What must be changed on a context switch EECS 482 Pros and cons works well for sparse address spaces with big gaps of invalid areas easy to share whole segments without sharing entire address space complex memory allocation Can a single address space be larger than physical memory How to make memory allocation easy and allow an address space easily be larger than physical memory Peter M Chen Paging Allocate physical memory in terms of xedsize chunks of memory called pages xed unit makes it easier to allocate any free physical page can store any Virtual page Virtual address Virtual page high bits of address e g bits 3112 offset low bits of address e g bits llO for 4 KB page Translation data is the page table data Virtual page physical page 0 10 l 15 2 20 3 invalid invalid 1048575 inVahd EECS 482 Translation process if Virtual page is invalid trap to OS fault handler else physical page pageTableVirtual page physPageNum What must be changed on a context switch Each Virtual page can be in physical memory or paged out to disk just like segments could be swapped out to disk Peter M Chen Valid vs resident How does processor know that Virtual page is not in physical 1119111013 Resident means a Virtual page is in memory It is NOT an error for a program to access a nonresident page Valid means a Virtual page is not currently legal for the pro gram to access Who makes a Virtual page residenUnon resident Like segments pages can haVe different protections eg read write execute Who makes a Virtual page ValidinValid Why would a process want one of its Virtual pages to be inValid EECS 482 10 Peter M Chen Page size What happens if page size is small What happens if page size is really big Could we use a large page size but let other processes use the leftover space in the page Page size is typically a compromise e g 4 KB or 8 KB EECS 482 Fixed vs variable size partitions xed size pages must be compromise eg 4 or 8 KB Too small a size leads to a large translation table while too large a size leads to internal fragmentation variable size segments can adapt to the need but it s hard to pack these variable size partitions into physical memory leading to external fragmentation What happens to paging if the virtual address space is sparse most of the address space is invalid with scattered valid regions Paging pros and cons simple memory allocation can share lots of small pieces of an address space easy to grow the address space Simply add a virtual page to the page table and nd a free physical page to hold the virtual page before accessing it big page tables Peter M Chen Comparing basic translation schemes baseampbound unit of translation and swapping is an entire address space segments unit of translation and swapping is a segment a few large variablesized segments per address space page unit of translation and swappingpaging is a page lots of small xedsized pages per address space How to modify paging to take less space EECS 482 Multilevel translation Standard page table is a simple array one degree of indirec tion Multi level translation changes this into a tree mul tiple degrees of indirection Eg twolevel page table indeX into the level 1 page table using Virtual address bits 3 l 22 indeX into the level 2 page table using Virtual address bits 21 l 2 page offset bits 110 4 KB page What information is stored in the level 1 page table What information is stored in the level 2 page table Peter M Chen This is a twolevel tree level 1 page table level 2 page tables O l 2 3 1 1 NULL NULL Virtual Virtual address physical address physical bits 21 page bits 21 page 12 12 0 10 0 30 1 15 1 4 2 20 2 8 3 2 3 3 How does this allow the translation data to take less space EECS 482 How to use share memory when using multilevel page tables What must be changed on a context switch Another alternative use segments in place of the levell page table This uses pages on level 2 ie break each segment into pages 13 Peter M Chen Pros and cons spaceef cient for sparse address spaces easy memory allocation lots of ways to share memory two extra lookups per memory reference EECS 482 Translation lookaside buffer TLB Translation when using paging involves l or more additional memory references How to speed up the translation pro cess TLB caches translation from Virtual page to physical page TLB conceptually caches the entire page table entry e g dirty bit reference bit protection If TLB contains the entry you re looking for can skip all the translation steps above On TLB miss gure out the translation by getting the user s page table entry store in the TLB then restart the instruc tion Does this change what happens on a context switch Peter M Chen Replacement One design dimension in Virtual memory and any cache is which page to replace ie eVict when you need a free Page Goal is to reduce the number of page faults Random replacement easy to implement but poor results FIFO replace the page that was brought into memory the long est time ago unfortunately this can replace popular pages that are brought into memory a long time ago and used fre quently since then OPT replace the page that won t be used for the longest time this yields the minimum number of misses but requires knowledge of the future EECS 482 LRU least recently used use past references to predict the future temporal local ity if a page hasn t been used for a long time it probably won t be used again for a long time this yields low miss rate similar to OPT but is hard to implement exactly LRU is an approximation to OPT Can we approximate LRU to make it easier to implement without increasing miss rate by too much Basic idea is to replace an old page not necessarily the oldest page Peter M Chen Clock To nd a page to eVict Most lVlMUs maintain referenced bit for each resident page 39 100k at Page being POinted to by CIOCk hand which is set automatically when the page is referenced 39 referencezo means Page hasn t been accessed in a long Reference bit can be Cleared by os time since last sweep so this is your Victim referencel means page has been accessed since your Why is hardware support needed to maintain the reference bit last sweep What to do How can you identify an old page Try to do this work incrementally rather than all at once Can this in nite loop What if it nds all pages referenced since the last sweep A F T B E C D New pages are put behind the clock hand with referencel EECS 482 16 Peter M Chen Pageout While eVicted page is being written to disk the page being What to do with page when it s eVicted brought into 1119111013 mUSt wait may be able to reduce total work by giVing preference to dirty pages eg could eVict clean pages before dirty pages if system is idle might spend time pro tably by writing back dirty pages Why not write pages to disk on every store EECS 482 17 Peter M Chen Page table contents Data stored in the hardware page table resident bit true if the Virtual page is in physical memory physical page if in physical memory dirty bit set by MMU when page is written reference bit set by MMU when page is read or written protection bits readable writable set by operating sys tem to control access to page Checked by hardware on each access lVlMU memory management unit of the CPU is responsible for checking if the page is resident checking if the page protections allow this access and setting the dirtyrefer ence bits if page is resident and access is allowed then lVlMU translates the Virtual address into a physical address using info from the TLB and page table and issues the physical memory address to the memory controller if page is not resident or protection bits disallow the access the lVlMU generates an exception page fault Operating system maintains additional information for each Virtual page disk block if on disk which Virtual pages are Valid EECS 482 Do we really need hardware to maintain a dirty bit How to reduce of faults required to do this Do we really need hardware to maintain a reference bit Peter M Chen Kernel vs user mode Who sets up the data used by translator Kernel is allowed to modify any memory including translation tables How can kernel refer to translation table Translation table is not really in any process s address space It is often in physical ie untranslated memory kernel can issue untranslated addresses ie bypass the translator kernel can map physical memory into a portion of its address space How does machine know that the kernel is running machine must know to allow kernel to bypass translator and to allow kernel to execute priVileged instructions e g halt IO need hardware support two processor modes kernel and user EECS 482 How have we handled the problem of protection so far implement protection by translating all addresses But who can modify data used by translator only kemel can modify translator s data but how does processor know if kernel is running mode bit distinguishes between kernel and user But who is allowed to modify mode bit Peter M Chen Switching from user process into kernel Sequence of events that take place when C program calls What causes a switch from a user process into the kernel Gin C code calls cin cin is a standard library function that calls read read is a standard library function that executes the assemblylanguage instruction syscall with parame ters SYSread le number size in registers or on the stack when processor executes syscall instruction it traps to the kernel at a prespeci ed location kernel syscall handler receives the trap and calls the ker nel s read function Details of what happens when trapping to kernel set processor mode bit to kernel save current registers SP PC general purpose registers set SP to the kernel s stack change address spaces to the kernel s address space by changing some data used by the translator jump to kernel exception handler Does this look familiar How does processor know exception handler s address EECS 482 Peter M Chen Passing arguments to system call and getting return values can store arguments in registers or memory according to agreedupon convention if pass arguments Via memory which address space holds the arguments how does kernel access user s address space kernel cannot assume arguments are valid It must be paranoid and check them all Otherwise process could crash kernel with bogus arguments EECS 482 Process creation Steps in creating and starting a process allocate process control block read code from disk and store into memory initialize machine registers initialize translator data e g page table and PTBR set processor mode bit to user jump to start of program Need hardware support for last few steps otherwise processor executing in user mode can t access the kernel s jump instruction Switching from kernel to user process e g after a system call completes is the same as last 4 steps above Peter M Chen Multiprocess issues How to allocate physical memory between processes resource allocation is an issue whenever sharing a single resource among multiple users e g CPU scheduling often a tradeoff between globally optimal best overall performance and fairness Global vs local replacement policy global replacement consider all pages equally when looking for a page to evict local replacement only consider pages belonging to the process needing a new page when looking for a page to evict But how to set the of pages assigned to a pro cess generally global has lower overall miss rate but local is more fair EECS 482 Thrashing What would happen with lots of big processes all actively using lots of virtual memory Usually performance degrades rapidly as you go from having all programs t in memory to not quite tting in memory This is called thrashing Average access time hit rate hit time miss rate miss time eg hit time 0001 ms miss time 10 ms 100 hit rate average access time is 0001 ms 99 hit rate 90 hit rate Solutions to thrashing if a single process is actively using more pages than can t there s no solution that process at least will thrash if problem is caused by the combination of several pro cesses can alleviate thrashing by swapping all pages of a process out to disk That process won t run at all but other processes will run much faster Overall perfor mance improves Peter M Chen Working set What s meant by a process actively using a lot of Virtual pages Working set all pages used in last T seconds or T instruc tions larger working set gt process needs more physical memory to run well ie avoid thrashing Sum of all working sets should t in memory otherwise sys tem will thrash only run a set of processes whose working sets all t in memory this is called a balance set How to pick T What does larger T mean EECS 482 How to measure the size of a process s working set Peter M Chen Examples of process creation Unix separates process creation into two steps Unix fork create a new process with one thread Address space of new child process is a copy of the parent process Unix exec overlay the new process s address space with the speci ed program and jump to its starting PC this loads the new program Eg parent process wants to fork a child to do a task Any problem with having the new process be an exact copy of the parent EECS 482 Why does Unix fork copy the parent s entire address space just to throw it out and start with the new address space Unix provides the semantic of copying the parent s entire address space but does not physically copy the data until needed separating fork and exec gives maximum exibility for the parent process to pass information to the child common special case fork a new process that runs the same code as parent Alternative Windows creates new processes with a single call CreateProcess Unix s approach gives the exibility of sharing arbitrary data with child process Window s approach allows the program to share the most common data via parameters Peter M Chen


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

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I 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!"


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