Introdctn to Operating Systems
Introdctn to Operating Systems EECS 678
Popular in Course
Popular in Elect Engr & Computer Science
This 16 page Class Notes was uploaded by Melissa Metz on Monday September 7, 2015. The Class Notes belongs to EECS 678 at Kansas taught by Prasad Kulkarni in Fall. Since its upload, it has received 64 views. For similar materials see /class/182479/eecs-678-kansas in Elect Engr & Computer Science at Kansas.
Reviews for Introdctn to 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/07/15
EECS 678 Introduction to Operating Systems Tutorial C 10 for C Programmers Many students reach EECS 678 without encountering C 10 output functions instead C streamoriented 10 is the familiar lO model for use with the console and les EECS 678 projects eg the lPC puzzle and NACHOS projects will include example or stubbed code containing many uses of C lOi This tutorial is intended to introduce students to the C 10 functions in order to mitigate that unfamiliarityls role in the course projectsi Perhaps even better reasons to encourage understanding of C 10 is its heavy usage in past and even present CC code as well as its in uence on features of new languages including Python and PHP Prelude Strings When the C 10 functions were developed there existed no standard string object other than the character arrayi Hence most lO functions accept a char bu er and a int size parameteri Students bridging this gap may wish to review the C String functions eg strcpy strcat etc Part I String Output p ntf and friends The grunts of C 10 are the formattedprinting functions printf sprintf and fpn39ntf int printf const char fmt pn39ntf exempli es the basic concept embodied by this family of functions The input param eter fmt is a NULLterminated stringi After a transformation this string is printed to stdout analogous to amt The steps of the transformation are determined by the format string in a precise way When certain characters are encountered in the format string they are replaced by a string representation of their corresponding argument in the variable argument list For instance char szName quotNickquot printf quotHello Zsquot szName would print quotHello Nickquot to stdout The s in the format string is called a type speci eri There are many type speci ers erg d for integers see the table at the end of this Part or check on the Internetijust search for 77printf type specifiers77 and a full table will be a click or two awayi int sprintf char buffer const char fmt int fprintf FILE file const char fmt sprintf and fpn39ntf behave just like printf except that sprintf outputs to a string and fprz39ntf outputs to a le pointer which is discussed below With sprintf be sure the nal string will t in the speci ed buffer The FILE le parameter of fprz39ntf is discussed in the next section scanf and friends do for input what pn39ntf and friends do for output The scan functions can be used to parse strings iiei quotNick ran 25quot could be used to set the values of a string variable for the name and a distance variable for the number of miles Look at the scanf man page man 3 scanfl or online for more information Literal percent sign ire s chm string pointer eigi argv0 c Character d lnteger u Unsigned integer f Floatingpointer number x Hexidecmal representation of a number Table 1 Common Format String Type Speci ers Part II File Handling File descriptors are the mechanism by which processes identify character streams les sockets etc when cooperating with the operating systemi The system calls open close read and write work with le de cliptoi As the l t l l 39 le de cliptoi are not the most convenient le abstraction with which to programi The FILE le argument in the prototype of fpn39ntf above is called a le pointer and is the most common element of lebased 10 in C It is the C Standard Library s abstraction built on top of le descriptorsi Functions such as fopen fclose fgets or fputs create or target le pointersi There are three global le pointers stdz39n stdout and stderr which correspond to cm cout and Gen respectively from Ci Again extensive reference material is available The most signi cant difference between le descriptors and le pointers is that le pointers are buffered and le descriptors are not Consider a program that prompts the user for input If that program is written with le descriptors and le descriptors system calls there is no buffering and writeing to the console before reading from it will certainly show the user the prompt string before expecting a response If the program uses le pointers instead lO buffering may cause a delay in the presentation of the prompt to the user It might expect a response before the user sees the request to type int fflush FILE file This kind of situation can be avoided by use of flush it forces a buffer to be written and it can help in situations where buffering could cause confusion In the interactive program example the code would write to the screen via the le pointer and flush the le pointer before reading input to be certain that the user sees the prompt before needing to type a response These le pointer functions are discussed in the following paragraphs FILE fopen const char filename const char mode char fgets char buffer int n FILE file int fclose FILE file fopen creates le pointersi The le name parameter is the absolute or relative with respect to the working directory of the process path to the le and the mode parameter speci es what kind of interface this le pointer will provide to the le quotrquot is a mode for reading a le quotwquot writes and quotaquot appendsi Including a in the mode means read or write or random access so quotTquot quot111quot and quotaquot are just about the same Including a quotbquot in the mode means its a binary le instead of a le with only text in it fgets is the simplest way to use a le pointeri It reads at most a 1 characters from the le and stores them in the buffer It will stop reading at a newline or end of le which could be less than a 1 characters Any error will cause fgets to return NULL otherwise it will return bu er and the input string will be NULLterminated int fputs coast char bu er FILE le writes the NULLterminated string to the le Be sure to close les with fclose and to remember that these le including stdout stain and stderr functions provide a buffered interface to the underlying system calls Mixing these buffered functions with unbuffered system calls like read or unite can cause some confusing outputi a Virtual Memory Outline I Background l Demand Paging l CopyonWrite l Page Replacement l Allocation of Frames l Thrashing l MemoryMapped Files I Allocating Kernel Memory l Other Considerations l OperatingSystem Examples EECS 678 Introduction to Operating Systems 7 Spring 2009 a Background l Virtual memory separation of user logical memory from physical memory 0 only part of the program needs to be in memory for execution o logical address space can therefore be much largerthan physical address space 0 allows address spaces to be shared by several processes 0 allows for more efficient process creation I Benefits of not requiring the entire program in memory before execution 0 programs can be largerthan the physical address space 0 more programs can be resident in memory at the same time o faster program startup EECS 678 Introduction to Operating Systems 7 Spring 2009 s l Space between heap and Max l Shared memory Virtualaddress Space stack is not used unless the heap or stack grows stack 0 virtual memory does not require physical pages for such holes 0 pages can be easily shared by virtual memory 0 shared libraries can be mapped readonly into address space of heap each process 0 shared memory IPC can be data implemented easily code 0 parent pages can be shared with 0 child during fork EECS 678 Introduction to Operating Systems 7 Spring 2009 gsShared Library Using Virtual Memory stack stack shared I shared library pages shared library heap heap data data code code EECS 678 Introduction to Operating Systems 7 Spring 2009 g Demand Paging gs Demand Paging System I Bring a page into memory only when it is needed 0 less lO needed 0 less memory needed 0 faster response program swap out 0D 1D 2D 3D 0 more applications simultaneously resident in memory A 4 5 6 7 I Page is needed gt reference to it 8D 9D10D11El O invalid reference gt abort 12D13D14D15E O notinmemory gt bring to memory pmggam x swapm 16Ih7 18 19 l Lazy swapper never swaps a page into memory 20D21D22D23El unless page will be needed 0 Swapper that deals with pages is a pager mZ a l rv EECS 678 Introduction to Operating Systems 7 Spring 2009 5 EECS 678 Introduction to Operating Systems 7 Spring 2009 Valid39ana39id Bit 9 Page Table When Some Pages Are Not in Main Memory l Each page table entry associated with a valid invalid bit 0 v gt inmemory i gt notinmemory 7 0 Initially set to Invalid for all page table entries Frame validinvand bit 0 validiimand 2 l Example of a page table snapshot 1 frame it a 2 A A 3 5 4 6 C 5 7 6 8 7 9 F logical page able 10 memory 4 page 11 12 l Valid invalid bit in page table set to I during address 13 translation causes a page fault 14 15 ohvsical memorv EECS 678 Introduction to Operating Systems 7 Spring 2009 7 EECS 678 Introduction to Operating Systems 7 Spring 2009 5 Steps in Handling a Page Fault page is on backing store operating system reference load M instruction page table free frame reset page bring in table missing page physical memory EECS 678 Introduction to Operating Systems Spring 2009 9 3 Steps in Handling a Page Fault 2 1 First reference to data or instructions on a page occurs 2 Memory access traps to the 08 with a page fault 0 operating system looks at anothertable to decide gt invalid reference gt abort orjust not in memory Find a free frame in physical memory Read page from disk into free frame Update page table validinvalid bit to 39v39 Restart the instruction that caused the page fault mow ho EECS 678 Introduction to Operating Systems Spring 2009 10 5 Performance of Demand Paging l Page Fault Rate 0 s p s 10 o ifp 0 no page faults o ifp 1 every reference is a fault I Effective Access Time EAT EAT 1 p x memory access p page fault overhead swap page out swap page in restart overhead EECS 678 Introduction to Operating Systems Spring 2009 11 3 Demand Paging Example I Memory access time 200 nanoseconds l Average pagefault service time 8 milliseconds l EAT 1 p x 200 p 8 milliseconds 1 p x 200 p x 8000000 200 p x 7999800 I If one access out of 1000 causes a page fault then EAT 82 microseconds This is a slowdown by a factor of 40 EECS 678 Introduction to Operating Systems Spring 2009 12 3 Process Creation CopyonWrite 3 Process 1 Modifies Page C physical I Original process creation 0 fork system called duplicates parent address space for child PageA o demand paging with copy on write allow sharing address spaces I Copy on Write COVV allows both parent and child processes to initially share the same pages in memory page C 0 shared pages marked as copy on write pages 0 if either process modifies a shared page then the page is copied 0 only the modified pages are copied I COW allows more efficient process creation as only modified pages are copied I Free pages are allocated from a pool of zeroed out pages Before Page B physical Afte r EECS 678 Introduction to Operating Systems 7 Spring 2009 13 EECS 678 Introduction to Operating Systems 7 Spring 2009 14 5 Need For Page Replacement Page Replacement I Review of demand paging I Page replacement is needed when a page fault occurs 0 separates logical memory from physical memory and there are no free frames to allocate 0 allows logical address space gt physical address space terminate user process 7 0 enables a greater degree of multiprogramming SWap OUt an entire process 7 gt higher CPU utilization and throughput 0 find some page in memory hopefully not really in use and swap 0 allows fast process startup it out Drawbacks of demand paging I Same page may be brought into memory several times 0 may increase later individual memory access times 0 potential for overallocation of physical memory I Over allocation of memory 0 currently active processes may reference more pages than room in physical memory 0 pages from active processes may need to be replaced EECS 678 Introduction to Operating Systems 7 Spring 2009 15 EECS 678 Introduction to Operating Systems 7 Spring 2009 16 3 Basic Page Replacement 1 Find the location of the desired page on disk 2 Find afree frame If there is a free frame use it If there is no free frame use a page replacement algorithm to select a victim frame 3 Bring the desired page into the newly free frame update the page and frame tables 4 Restart the process I Reducing page fault overhead 0 use modify bit to with each frame 0 only copy the replacement page to memory if modi ed EECS 678 Introduction to Operating Systems 7 Spring 2009 17 9 Basic Page Replacement 2 frame valid invalid bit A swap out change victim to invalid D I f victim c I reset page x table for page table new page 6 swap D desired pagein physical memory EECS 678 Introduction to Operating Systems 7 Spring 2009 5 Page Replacement Algorithms l Criteria 0 get the lowest page fault rate I Page replacement schemes 0 rst in rst out FIFO 0 optimal page replacement 0 least recently used LRU c LRU approximation algorithms 0 counting based replacement I Evaluation of replacement algorithm 0 simulate it on a particular string of memory page references 0 compute the number of page faults on the reference string I In all our examples the reference string is 7 o 1 2 o 3 o 4 2 3 o 3 2 1 2 o 1 7 01 EECS 678 Introduction to Operating Systems 7 Spring 2009 19 a Expected Graph of Page Faults Versus The Number of Frames number of page faults l l i l i l i l i i i 1 2 3 4 5 6 number of frames EECS 678 Introduction to Operating Systems 7 Spring 2009 FirstlnFirstOut FIFO Algorithm I Simplest page replacement algorithm 0 each page associated a time when it was brought in memory 0 replace the oldest page during page replacement 0 implemented using a FIFO queue of all pages 0 replacement page found from the head of the queue 0 new page added to the tail of the queue 3 o 3 2 1 2 0 1 7 o 1 3042 El I EECS 678 Introduction to Operating Systems Spring 2009 21 reference string 1 2 O 0 all page frames Belady39s Anomaly I For some page replacement algorithm the page fault rate may increase as the number of frames increases 0 can happen with FIFO replacement scheme I Example 0 reference string 1 2 3 4 1 2 5 1 2 3 4 5 o FIFO replacement algorithm 16 14 12 1O 8 number of page laulls 8 4 2 number of frames EECS 67 8 Introduction to Operating Systems Spring 2009 22 5 Optimal Page Replacement I Algorithm with the lowest page fault rate Q replace the page that will not be used for the longest period 0 provably optimal 0 does not suffer from Belady39s anomaly 0 needs future information reference string page frames EECS 67 8 Introduction to Operating Systems Spring 2009 23 Least Recently Used LRU Algorithm I Approximate the optimal page replacement algorithm 0 detect and store when each page is used 0 replace page that has not been used for the longest period 0 a very good replacement policy 0 requires hardware support to be accurate and fast 0 does not suffer from Belady39s anomaly reference string 7 0 1 2 o 3 o 4 2 3 o 3 2 1 2 o 0 a o o o o o 3 3 a a I 1 1 3 3 2 2 2 pageframes EECS 67 8 Introduction to Operating Systems Spring 2009 24 1539 l Counter implementation every page table entry has a timeof use field copy the clock into the timeof use field on every page access LRU Implementation for replacement find the page with the smallest timeof use field replacement algorithm requires search of the full page table each memory access needs additional write to timeof use field counter overflow EECS 678 Introduction to Operating Systems Spring 2009 25 a l Stack implementation 0 keep a stack of page numbers in a linked list move page to top of stack when referenced find replacement page from bottom of stack LRU Implementation 2 no search for replacement reference string 4 7 O 7 1 O 1 2 1 2 7 1 EECS 678 Introduction to Operating Systems Spring 2009 each update is more expensive due to stack operations 59 LRU Approximation Algorithms l Reference bit algorithm 0 associate reference bit with each page 0 set bit when page is references clear all bits occasionally 0 replace page that has reference bit 0 if one exists 0 cannot store the order of accesses in one bit l Record reference bit algorithm 0 each page associated with a 8bit field for recording reference bit 0 at regularintervals gt right shift 8bit field gt move reference bit into highest order bit 0 page with lowest value in 8bit field is the LRU page 0 Example reference bit 8bit field 110101100a 01101110 gt 0 11001101a 0 01100110 EECS 678 Introduction to Operating Systems Spring 2009 27 Q LRU Approximation Algorithms 2 reference pages reference pages I Secondchance algorithm bus 0 single reference RF bit E 0 basic FIFO replacement algo E 0 find replacement page gt proceed if RF0 gt give page 2nd chance if RF1 and move onto next page clear reference bit E o circular queue of pages 0 pointer indicates next replacement page 0 what is all bits are set I circular queue of pages a EECS 678 Introduction to Operating Systems Spring 2009 bits I am E a E a g circular queue of pages b gt CountingBased Algorithms I Keep a counter of the number of references that have been made to each page I Least frequently used 0 replace page with the smallest count 0 most active page should have largest count I Most frequently used 0 replace page with the largest count 0 page with smallest count was brought in last and will be accessed next I Not very popular algorithms spur 2007 29 35 Page Buffering Algorithms l Optimizations by maintaining a list of victim frames l Scheme1 0 bring new page into one ofvictim frame slots 0 then copyout the replacement page to memory 0 memory access to new page does not wait for copyout l Scheme 2 O copyout modi ed pages to disk when paging device is idle 0 replacement is now faster I Scheme 3 o rememberwhich page is in each victim frame 0 if new page is in one ofvictim frame then use directly 0 works well if replacement algorithm replaces a page that is needed a er a erwards 5M 2009 3quot J Allocation of Frames I How many frames in physical memory should the OS allocate to each process l Minimum number of frames 0 is there a minimum number offrames a process needs 0 depends of the maximum number of pages any instruction in the ISA can reference at a time gt what can happen ifwe do not provide this minimum 0 direct addressing loadstore need 2 frames i one for instruction and onefor memory reference 0 onelevel indirect addressing needs 3 frames i o e for instruction one for address and one for memory reference 0 PDP11 needs 6 frames IBM 370 needs 8 frames 0 should there be a maximum number spur 2007 ii 3 Frame Allocation Algorithms l Equal allocation 0 divide m frames equally among n processes 0 each process gets about mn frames 0 may give some process more frames than it needs I Proportional allocation 0 each process may need different amounts ofmemory o allocate memory proportional to process size 0 Example m 64 s size of pmcessp 5 i0 2 s 52 i27 m lolalnumberofframes a x a 5 s ia7 a allocallonfor p 4x m m 3 a2 Ex 64 z 59 5M 2009 32 3 Other Frame Allocation Issues l Global Vs local allocation 0 global replacement process selects a replacement frame from the set of all frames gt one process can take a frame from another gt process cannot control its own page fault rate 0 local replacement each process selects from only its own set of allocated frames gt may hinder progress by not allowing high priority process access to frames of low priority process I Nonuniform memory access 0 memory may be distributed on multiprocessor systems 0 how to assign frames in such situations o assign memory which is close to where a process is running EECS 678 Introduction to Operating Systems 7 Spring 2009 33 a Thrashing l A process is thrashing if it spends more time paging than executing 0 process keeps swapping active pages in and out leads to a very high page fault rate I Causes of thrashing behavior process does not have enough pages I Vicious cycle of thrashing not having enough frames cause more page faults lowers CPU utilization operating system thinks that it needs to increase the degree of multiprogramming another process added to the system even less frames per process leads to more page faults cycle continues EECS 678 Introduction to Operating Systems 7 Spring 2009 34 19 Thrashing 2 l Thrashing becomes more likely with increasing degree of multiprogramming A CPU utilization thrashing degree of multiprogramming I Can we prevent thrashing by using a local replacement algorithm EECS 678 Introduction to Operating Systems 7 Spring 2009 35 35 Preventing Thrashing Behavior I Give a process as many frames as it needs 0 how to know how many frames a process needs l WorkingSet model 0 based on the locality model of process execution gt each process phase uses a small set of memory references frames gt execution moves from one program phase to another 0 the number of frames required for each phase is called the working set 0 Implementation gt assume a particular working set window A gt WSS working set of Process P total number of pages referenced in the most recent A gt D 2 W88 E total demand frames gt If D gt m gt Thrashing then suspend one of the processes EECS 678 Introduction to Operating Systems 7 Spring 2009 36 Working Sets and Page Fault Rates 9 Preventing Thrashing Behavior 2 l Page faults spike at the start of every new program I PageFault frequency scheme work39ng set also called a phase 0 working set model is needs several assumptions and is 0 page fault rate falls until the next program phase compllcated 0 measure the page fault rate routinely o establish acceptable pagefault rate 0 behavior repeats working set gt If actual rate too low process loses frame or increase processes 1 gt If actual rate too high process gains frame or suspend processes A page fault w rate 3 Increase number of frames E upper bound lt13 O Q me lower bound decrease number of frames number of frames EECS 678 Introduction to Operating Systems 7 Spring 2009 37 EECS 678 Introduction to Operating Systems 7 Spring 2009 MemoryMapped Files 5 Memory Mapped Files 2 l Memorymapped file lO allows file lO to be treated as l Allows several processes to map the same file allowing routine memory access by mapping a disk block to a the pages in memory to be shared page In memory 0 removes the need to read write system calls 0 converts disk access to memory access 0 simplifies disk access for the user I Mechanism details 0 a file is initially read using demand paging O a pagesized portion of the file is read from the file system into a virtptiaolcrensesmporyl physical frame o subsequent readswrites tofrom the file are treated as ordinary 39 memory accesses 39rI t39l IL393939I39391391 r process B virtual memory L I physical memory disk file EECS 678 Introduction to Operating Systems 7 Spring 2009 39 EECS 678 Introduction to Operating Systems 7 Spring 2009 5 MemoryMapped Files 3 I Examples of 08 using memorymapped files 0 Solaris Unix and Linux provide the mmap system call to create a memorymapped file 0 files accessed using open read write are mapped to kernel address space in Solaris 0 Windows NT and XP use memory mapped files to accomplish shared memory EECS 678 Introduction to Operating Systems 7 Spring 2009 41 MemoryMapped NO I Special lO instructions may be available to transfer data and control messages to the HO controller I Memorymapped HO 0 lO device registers mapped to logical memory address spaces 0 convenient and fast I There may be a control bit to indicate if data is available in the data register 0 if CPU polls the control bit then method of operation is called programmed HO 0 if device sends interrupt to CPU to indicate data availability then mode of operation is interrupt driven IIO EECS 678 Introduction to Operating Systems 7 Spring 2009 42 5 Allocating Kernel Memory I Kernel memory often allocated from a free memory pool 0 not using demand paging I Reasons for treating kernel memory allocation differently 0 some kernel memory needs to be contiguous o attempt to minimize memory waste due to internal fragmentation gt kernel requests memory for structures of varying size gt do not use paging system I Strategies for managing free memory 0 buddy system 0 slab allocator EECS 678 Introduction to Operating Systems 7 Spring 2009 43 5 Buddy System I Powerof2 allocator physicallycontiguous pages 0 satisfies requests in units 256 KB srzed as power of 2 0 request rounded up to next highest poweron 0 when smaller allocation i28KB 128KB needed than is available AL An current chunk split into two buddies of nextlower H H poweron 64 KB 64 KB gt continue until appropriate 3H sized chunk available BL I Example 0 21kb requested from 256kb eon L H EECS 678 Introduction to Operating Systems 7 Spring 2009 44 Slab Allocator l Slab contains several physically contiguous pages I Cache consists of one or more slabs l Single cache for each unique kernel data structure 0 cache filled with instantiations of the data structure objects I Slab allocation algorithm 0 create cache of objects in contiguous space mark as free 0 store objects in free slots mark as used 0 if current slab is full of used objects allocate next object from empty slab o if no empty slabs go to free slots in the next slab l Benefits 0 no fragmentation 0 fast memory request satisfaction EECS 678 Introduction to Operating Systems 7 Spring 2009 45 g Slab Allocation 2 kernel objits caches slabs 3 KB objects physical contiguous pages 7 KB objects EECS 678 Introduction to Operating Systems 7 Spring 2009 46 15 Other Virtual Memory Issues l Prepaging 0 reduce page faults at process startup o prepage all or some process pages before they are referenced gt HO and memory wasted if prepaged pages are unused l Issues in deciding a page size 0 internal fragmentation gt small page size preferred to reduce memory lost on the final page 0 page table size gt large page size preferred to reduce size of page table 0 HO overhead gt large page size preferred to reduce disk latency and seek time o Page faults gt large page size reduces number of generated page faults EECS 678 Introduction to Operating Systems 7 Spring 2009 47 5 Other Virtual Memory Issues 2 l TLB Reach 0 amount of memory accessible from the TLB o TLB Reach TLB Size X Page Size 0 ideally the working set of each process is stored in the TLB o improving TLB reach gt increase the page size gt provide multiple page sizes I lO interlock 0 pages must sometimes be locked into memory 0 consider lO Pages that are used for copying a file from a device must be locked from being selected for eviction by a page replacement algorithm 0 provide a lock bit with every page frame EECS 678 Introduction to Operating Systems 7 Spring 2009 48 it Other Virtual Memory Issues 3 I Program structure I being aware ofthe paging structure can help performance 0 example Int128 128 0 Each row is stored in one page 0 program 1 128 1 128 16 384 page faults for 1 r 0 j lt128 jgt 11 for r 0 1 lt data139 ta 128 1gt r 0 0 Program 2 128 page faults for 11 r 0 1 lt 128 1 1139s 0 j lt 128 jgt data1j r 0 spam 2007
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'