Operating Systems CSCI 444
Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 35 page Class Notes was uploaded by Aliza Ruecker on Thursday October 29, 2015. The Class Notes belongs to CSCI 444 at College of William and Mary taught by Staff in Fall. Since its upload, it has received 12 views. For similar materials see /class/231168/csci-444-college-of-william-and-mary in ComputerScienence at College of William and Mary.
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: 10/29/15
Secondary Storage CSCI 444544 Operating Systems Fall 2008 Overview of secondary storage disks 0 Disk structure 0 Disk performance 0 Disk scheduling Disk management 0 RAID Redundant Arrays of Inexpensive Disks Secondary storage typically 0 is anything that is outside of primary memory 0 does not permit direct execution of instructions or data retrieval via machine loadstore instructions Characteristics 0 its large 2001000GB 0 it s cheap 045GB 0 it s persistent data survives power loss 0 its slow milliseconds to access Disk capacity 19751989 0 doubled every 3 years 0 25 improvement each year 0 factor of 10 every decade 0 Still exponential but far less rapid than processor rformance Disk capacity since 1990 o doubling every 12 months 0 100 improvement each year 0 factor of 1000 every decade 0 10x as fast as the increase of processor performance Memory Hierarchy 100033 Secondary Storage 10 quot 5 11000TB 15quot Each level acts as a cache of lower levels Disks and the OS Disks are messy messy devices errors bad blocks missed seeks etc Job of OS is to hide this mess from higherlevel software lowlevel device drivers initiate a disk read etc higherlevel abstractions files databases etc 08 may provide different levels of disk access to different clients physical disk block surface cylinder sector disk logical block disk block file logical filename block or record or byte Physical Disk Structure arm assembl rotation Disk Controller Responsible for interface between 08 and disk drive Common interfaces ATAIDE vs SCSI ATAIDE used for personal storage SCSI for enterpriseclass storage Basic operations Read block Write block 08 does not know of internal complexity of disk Disk exports array of Logical Block Numbers LBNs Disks map internal sectors to LBNs Disk performance depends on a number of operations seek moving the disk arm head to the correct cylinder depends on how fast disk arm can move rotation latency waiting for the sector to rotate under head depends on rotation rate of disk transfer sequentially moving data from surface into disk controller and from there sending it backto host depends on density of bytes on disk When the OS uses the disk it tries to minimize the cost of all of these operations particularly seeks and rotation Positioning head Seek Rotation Positioning time Seektime Rotational Delay How long to read or write n sectors Positioning time Transfertime n Implicit contract 0 Large sequential accesses to contiguous LBNs achieve much better performance than small transfers or random accesses Goal Minimize positioning time FCFS Schedule requests in order received Advantage Fair Disadvantage High seek cost and rotation Shortest seek time first SSTF Handle nearest cylinder next Advantage Reduces arm movement seek time Disadvantage Unfair can starve some requests queue 98 183 37 122 14 124 65 67 head starts at 53 0 14 37 536567 98 122124 188199 I I I II I II I I I I SST queue 98 183 37 122 14 124 65 67 head starts at 53 O 14 l l 37 536567 98 122124 l I i ll I ll q r Diek Scheduling all SCAN elevator algorithm move arm from one end toward the other end 183199 service requests until reach the other end then reverse skews wait times nonuniformly CSCAN CircularScan Like scan but only go in one direction then start over again typewriter uniform wait times 0 LOOK and CLOOK similar to SCAN and CSCAN except stop at the last request look for a request before continue to move in a give direction SCAN 3186AM queue 98 183 37 122 14 124 65 67 queue 98 18337 122 14 124 65 67 head starts at 53 head Starts at 53 O 14 37 53 65 67 98 122124 183199 0 14 37 536567 98 122124 183199 H H l l I ll l l l l l Semaphores CSCI 444544 Operating Systems Fall 2008 What is semaphore Two basic operations Two types of semaphores Usage of semaphores I like a generali Semaphores have two purpo Semaphore a synchronization primitive higher level of abstraction than lo 395 zedlock invented by Dijkstra in 1968 as part of the THE operating system Locks only provide mutual exclusion Ensure only one thread is in critical section at a time Mutex Ensure threads don t access critical section at same tim Scheduling constraints Ensure threads execute in specifc order Semaphore implementation Producerconsumer problem A semaphore is opera IOnS p an integer variable that is manipulated through two and V Dutch for wait and signal Psem waitJdo ck until sem gt 0 then subtract 1 from sem and Vsemsignalup dd Do these operations atomically Binary semaphore aka mutex semaphore sem is initialized to 1 guarantees mutually exclusive access to resource eg a critical section of code only one threadprocess allowed entry at a time Counting semaphore sem is initialized to N N number ofunits available represents resources with many identical units available allows threads to enter as long as more units are available To achieve mutual exclusion ensure that only 1 thread or more generally less than N threads is in critical section initial value of semaphore is set to l or more generally N wait ltcritical sectiongt signal Like lockunlock but more general To achieve scheduling constraints used when a thread should wait for some event notjust another thread leaving critical section initial value of semaphore is set to 0 usually but not always Thread A Thread B wait Do task continue execution signal l n us The function wait waitS l while S lt 0 noeop see The function Signal 5ignalS l s Ts typedef struct l Walt semaphore 5 l Must be executed atom1ca11y sagtva1ue7 1f segtva1ue lt o l add th1s process to sagtt11st b1ock l Slgnal semaphore 5 l Must be executed atom1ca11y 1f segtva1ue lt o i remove thread t from segtt11str wakeupt Each semaphore has an associated queue of threads 0 when P sem is called by a thread ifsem was available gt0 decrement sem and let thread inue ifsem was unavailable lt0 block thread and place it on associated queue run some other thread 0 when V sem is called by a thread ifthreads are waiting on the associated queue unblock one place 39t on the ready queue might as well let the quoting thread continue execution otherwise when no threads are waiting on the sem Incremen sem the signal is remembered for next time Psem is called Sem value is negative gt Number of waiters on queue Sem value is positive gt Number of threads that can be in critical section at same time Threads that are blocked at the level of program logic are placed on queues rather than busywaiting Busywaiting may be used for the real mutual exclusion required to implement P and V but these are very short critical sections totally independent of program logic Deadlock CSCI 444544 Operating Systems Fall 2008 Definition of deadlock Conditions for deadlock Deadlock prevention Deadlock avoidance Deadlock detection and recovery MW I Formal definition A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the se can cause Usually the event is release of a currently held resource Informal Every process is waiting for resource held by another process none release until it gets what it is waiting for None of the processes can I run release resources be awakened Representing Deadlock Two common ways of representing deadlock Vertices Threads or processes in system Resources anythin ofvalue including locks and semaphores Edges Indicate thread is waiting for the other waitin Forquot waiting Forquot WaitFor Graph ResourceAllocation Graph Mutual exclusion R source can not be shared Requests are delayed until resource is released Holdandwait Thread holds one resource while waits for another No preem tion Previously granted resources cannot forcibly taken away Circular wait Circular dependencies exist in waitsforquot or resourceallocationquot graphs ALL four conditions MUST hold Ignore Deadlock only affects threads that cause it Deadlock prevention Ensure deadlock does not happen Ensure at least one of4 conditions does not occur Deadlock avoidance Ensure deadlock does not happen Use information about resource requests to dynamically avoid unsafe situations Deadlock detection and recovery Allow deadlocks but detect when occur Recover and continue No mutual exclusion gt Make resource sharable Example Readonly les No holdandwait gt Two possibilities 1 Only request resources when have none Release resource before requesting next one 2 Atomically acquire all resources at once Eg single lock to protect all Low resource utilization Starvation If need many resources others might keep getting one ofthem No no preemption gt Preempt resources Example A waiting for something held by B then take resource away from B and give to A Only works for some resources eg CPU and memory Not possible if resource cannot be saved and restored Can39t take away a lock without causing problems No circular wait gt Impose ordering on resources Give all resources a ranking must acquire highest ranked rst Requires that the system has some additional a priori information available Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need The deadlockavoidance algorithm dynamically examines the resourceallocation state to ensure that there can never be a circularwait condition Resourceallocation state is de ned by the number of available and allocated resources and the maximum demands of the processes System is in safe state if there exists a safe sequence of all processes Avoid unsafe states of processes holding resources Unsafe states might lead to deadlock if processes make certain future requests When process requests resource only give if doesn t cause unsafe state Problem Requires processes to specify all possible future resource demands Dijkstra s Banker s Algorithm If a system is in safe state gt no deadlocks If a system is in unsafe state gt possibility of deadlock Avoidance gt ensure that a system will never enter an unsafe state u nsafe deadlock Similar to reserving all resources at beginning but more efficient Each process must state maximum resource needs in advance but don t actually acquire the resources When thread later tries to acquire a resource determine when it is safe to satisfy the request block the thread if it is not safe CSCI444544 Fall 2007 Pintos Grading Adapted from the Pintos Project Document of Ben Pfa You need to read this section to know how your work will be graded We will grade your assignments based on test results and design quality each of which comprises 50 of your grade 1 Testing Your test result grade will be based on our tests Each project has several tests each of which has a name beginning with quottestsquot To completely test your submission invoke make check from the project quotbuildquot directory This will build and run each test and print a quotpassquot or quotfailquot message for each one When a test fails make check also prints some details of the reason for failure After running all the tests make check also prints a summary of the test results For project 1 the tests will probably run faster in Bochs For the rest of the projects they will run much faster in QEMU make check will select the faster simulator by default but you can override its choice by specifying quotSIMULATOR bochsquot or quotSIMULATOR qemuquot on the make command line You can also run individual tests one at a time A given test twrites its output to quott outputquot then a script scores the output as quotpassquot or quotfailquot and writes the verdict to quottresultquot To run and grade a single test make the quot resultquot le explicitly from the quotbuildquot directory eg make teststhreadsalarm multipleresult lf make says that the test result is up to date but you want to re run it anyway either run make clean or delete the quot outputquot le by hand By default each test provides feedback only at completion not during its run If you prefer you can observe the progress of each test by specifying quotVERBOSE1quot on the make command line as in make check VERBOSE1 You can also provide arbitrary options to the pintos run by the tests with quotPINTOSOPTS quot eg make check PINTOSOPTS j 1 to select a jitter value of 1 All of the tests and related les are in quotpintossrctestsquot Before we test your submission we will replace the contents of that directory by a pristine unmodi ed copy to ensure that the correct tests are used Thus you can modify some of the tests if that helps in debugging but we will run the originals All software has bugs so some of our tests may be awed If you think a test failure is a bug in the test not a bug in your code please point it out We will look at it and x it if necessary Please don t try to take advantage of our generosity in giving out our test suite Your code has to work properly in the general case not just for the test cases we supply For example it would be unacceptable to explicitly base the kernels behavior on the name of the running test case Such attempts to side step the test cases will receive no credit If you think your solution may be in a gray area here please ask us about it 2 Design We will judge your design based on the design document and the source code that you submit We will read your entire design document and much of your source code 21 Design Document We provide a design document template for each project For each signi cant part of a project the template asks questions in four areas 0 Data Structures The instructions for this section are always the same Copy here the declaration of each new or changed struct or struct member global or static variable typedef or enumeration Identify the purpose of each in 25 words or less The rst part is mechanical Just copy new or modi ed declarations into the design document to highlight for us the actual changes to data structures Each declaration should include the comment that should accompany it in the source code see below We also ask for a very brief description of the purpose of each new or changed data structure The limit of 25 words or less is a guideline intended to save your time and avoid duplication with later areas Algorithms This is where you tell us how your code works through questions that probe your under standing of your code We might not be able to easily gure it out from the code because many creative solutions exist for most OS problems Help us out a little Your answers should be at a level below the high level description of requirements given in the assignment We have read the assignment too so it is unnecessary to repeat or rephrase what is stated there On the other hand your answers should be at a level above the low level of the code itself Don t give a line by line run down of what your code does Instead use your answers to explain how your code works to implement the requirements Synchronization An operating system kernel is a complex multithreaded program in which synchronizing multiple threads can be dif cult This section asks about how you chose to synchronize this particular type of activity Rationale Whereas the other sections primarily ask 77what77 and 77how77 the rationale section concen trates on 77why77 This is where we ask you to justify some design decisions by explaining why the choices you made are better than alternatives You may be able to state these in terms of time and space complexity which can be made as rough or informal arguments formal language or proofs are unnecessary An incomplete evasive or non responsive design document or one that strays from the template without good reason may be penalized lncorrect capitalization punctuation spelling or grammar can also cost points 22 Source Code The most important aspects of source code design are those that speci cally relate to the operating system issues at stake in the project For example the organization of an inode is an important part of le system design so in the le system project a poorly designed inode would lose points O Systems CSCI 444544 Operating Systems Agenda l lO Hardware 0 Storage devices disks tapes 0 Transmission devices network cards modems o Humaninterface devices monitor keyboard mouse l Application lO Interface l Kernel lO Subsystem Fa 2008 l Transforming lO Requests to Hardware Operations l Performance Objectives O Hardware l Explore the structure of an operating system s lO subsystem l Discuss the principles of HO hardware and its omplexity l Provide the performance aspects of lO hardware and software l Incredible variety of HO devices I Common concepts Port 0 Bus daisy chain or shared direct access 0 Controller host adapter I lO instructions control devices I Devices have addresses used by 0 Direct IIO instructions 0 Memorymapped IIO no special IIO instructions eeded A Typical PC BUS Structure Device O chFrDtaIFtoSStions on PCs IO address range hexadecimal device OOO OOF DMA controller monitor processor Y 020 021 interrupt controller l l l Che 040 043 timer h39 b 39d o l 3333quot l 20W gamemiei 2F8 2FF serial port secondary l l am it i 320 32F harddlsk controller 37amp37F parallel port 3DCP3DF graphics controller 3F0 3F7 diskettedrive controller SFB SFF serial port primary parallel serial port port Registers in an IIO Port Polling l Determines state of device I Datain register is read by the host to get input 0 commandready I Dataout register is written by the host to r Host signals its wish through this bit in command 39 t send output reg39s er 0 Busy l Status register contains bits indicating the r Controller indicates its state throughthis bit 39 tat 39 t states of the HO deVIce m S 5 reg39s er 0 Error I contrOI command reg39Ster3 can be wr39tten by l Busywait cycle to wait for O from device the host to start a command or change the mode Interrupts InterruptDriven IO Cycle CPU ir39O controller I CPU Interruptrequest line a wire triggered by IO device device drtuer tntltzttes lie I Interrupt handler receives interrupts InitiatesIo r CPU exacullng checks tot interrupts between lnslmctrons l Maskable to ignore or delay some interrupts input readyr output complete or error generates interrupt etgnel u receiving interrupt transters control to interrupt handler l Interrupt vectorto dispatch interrupt to correct handler 0 Based on priority 7 0 Some nonmaskable interrupt handler I processes a a returns trorn interrupt l Interrupt mechanism also used to support exceptions opu resumes procesetng or interrupted task Intel Pentium Processor Event Vector Table Direct Memory Access I Used to avoid programmed IIO for large data vector number description o divide error move ment 1 debug exception 2 null interrupt a breakpoinl 4 INTodetectedovemow l Requrres DMA controller 5 bound range exception 6 invalid agenda 7 device not available 8 WWW l Bypasses CPU to transfer data directly between 9 coprocessor segment overrun reserved 10 tnvattdteskstetesegment O devce and memory it segment not pr 12 slacklault 13 general protection 14 page uIl 15 Intel reserved do not use 16 rloetingrpornter r 17 alignment check 18 machine check 19 31 Intel reserved do not use 324255 maskable tnlerrupts Six Step Process to Perform DMA 1 device driver is told to transfer disk data CPU to buffer at address X 5 DMA controller 2 device driver tells transfers bytes to disk controller to buffer X increasing transler C bytes cache I interrupts CI Utosigrial mte rmpt C U a o transiercompletiori conr er aim 3 disk controller initiates IDE disk DMA transfer CONFOHQI 4 disk controller sends D memory ad ress rn iskto buffer and decreasing C at address X until C 0 DMAb U5 x when G 0 DMA 7 memory buffer controller Application IO Interface l IO system calls encapsulate device behaviors in generic classes I Devicedriver layer hides differences among IO controllers from kernel I Devices vary in many dimensions 0 Characterstream or block 0 Sequential or randomaccess o Sharable or dedicated 0 Speed of operation 0 readwrite read only or write only A Kernel IO Structure kernel E M g kernel IO subsystem 3 SCSI keyboard mouse PCI bus floppy ATAF39I device device device device device device driver driver driver driver driver driver SCSI keyboard mouse PCI bus oppy ATAF39I device vice devlce 39 device evice devlce m controller controller controller controller controller controller i I E E SI keyboard mouse PCI bus devices Block and Character Devices l Block devices include disk drives 0 Commands include read write seek 0 Raw IO or filesystem access 0 Memorymapped file access possible I Character devices include keyboards mice serial ports 0 Commands include get put 0 Libraries layered on top allow line editing Network Devices l Varying enough from block and character to have own interface I Unix and Windows NT9x2000 include socket interface 0 Separates network protocol from network operation 0 Includes select functionality gt Manage a set of sockets l Approaches vary widely pipes FlFOs streams queues mailboxes Blocking and Nonblocking O l Blocking synchronous process suspended waits until O completed 0 Easy to use and understand 0 Insufficient for some needs I Nonblocking O call returns as much as available 0 User interface data copy buffered HO 0 Implemented via multithreading 0 Returns quickly with count of bytes read or written I Asynchronous process runs while O executes 0 An asynchronous call returns immediately without waiting for lO o O subsystem signals process when lO completed gt Data transfer will be performed in its entirety but will complete at some future time Two IO Methods I el user requesting process er e n I wamng Hrequesting process us device driver device driver I I I l interrupt handler I linterrupt handler kernel I 39 hardware l l hardware data transfer data transfer time gt time gt a b Synchronous Asynchronous Kernel O Subsystem l Scheduling 0 Some lO request ordering via perdevice queue 0 Some OSs try fairness l Buffering store data in memory while transferring between devices 0 To cope with device speed mismatch 0 To cope with device transfer size mismatch 0 To maintain copy semanticsquot Kernel IIO Subsystem l Caching fast memory holding copy of data 0 Always just a copy 0 Keyto performance I Spooling hold output for a device 0 If device can serve only one request at a time 0 Le Printing l Device reservation provides exclusive access to a device 0 System calls for allocation and deallocation 0 Watch out for deadlock Error Handling l 08 can recoverfrom disk read device unavailable transient write failures l Most return an error number or code when lO requestfails l System error logs hold problem reports IO Protection l User process may accidentally or purposefully attempt to disrupt normal operation via illegal lO instructions 0 All IIO instructions de ned to be privileged o IIO must be performed via system calls r Memorymapped and lo port memory locations must be protected too Kernel Data Structures l Kernel keeps state info for Ho components including open file tables network connections character device state I Many many complex data structures to track buffers memory allocation dirty blocks I Some use objectoriented methods and message passing to implement lO UNIX lO Kernel Structure quot0 Requests to Hardware Operations I Consider reading a file from diskfor a process systemAWide openfile table perprocess 0 Determine device holding file 0 Translate name to device representation 0 Physically read data from disk into buffer 0 Make data available to requesting process 0 Return control to process Life Cycle of An O Request Performance system mll ieium ironi svsterii call l lO a major factor in system performance I39D subsystem f apnggg 330 Send request Io device 0 Demands CPU to execute device driver kernel lO driver block process ll39 WW cede appmpna e i o subsystem o Context swrtches due to interrupts pmcessmquegv lssue determine wtiicri lD commandslo coniroiiei meme mm mm nmca e slam 3335333333533 driver changemlrosunsvstem Data copymg 0 Network traffic especially stressful receive interrupL smre dala in ueviceuriver miner at ll lock inieriu t devicercumro er commands handing rrinput sign to HD aevme drivel interrupt devrce marinarueviae mnimiie interrupt wrien l39O we completed Completed genera e n elmpl Memory Management CSCI 444544 Operating Systems Fall 2008 Background 0 Address space 0 Static vs Dynamic allocation Contiguous vs noncontiguous allocation Program must be brought into memory and placed within a process for it to be run Uniprogramming one process runs at a time Multiprogramming several processes coexist in main memory Address binding of instructions and data to memory addresses can happen at three different stages Compile time If memory location known a priori absolute code can be generated must recompile code if starting location changes Load time Must generate relocatable code if memory location is not known at compile t39me Execution time Binding delayed until run time ifthe process can be moved during its execution from on memory segment to another Need hardware support for address maps eg base and limit registers lil il compile time r Sharing allocate scarce memory resources among competing processes maximizing memory utilization and system throughput Transparency a convenient abstraction for programming and for compilers etc Protection provide isolation between processes we have come to view addressability and protection as inextricably linked even though hey re really orthogonal Low overhead fast address translation and fast updating in context switching Remember what a process is address space 1 or more threads Address space unit of protection memory space that the threads use including all the data the program uses as it runs program code stack data segments Illusions provided by address spaces address independence each process use addresses starting at 0 virtual memory much larger than available physical memory protection process can only access data in its own address space r 2 Wk 5 a y a l The concept of a logical address spacethat is bound to a separate physical address space is central to proper memory management 39 Logical address generated by the CPU also referred to as virtual address Physical address address seen by the memory unit Logical and physical addresses are the same in compiletime and loadtime addressbinding schemes logical virtual and physical addresses differ in executiontime addressbinding scheme fl l l i iyzl garment Ll quot ivll vlltll Hardware device that maps logical to physical address In MMU scheme the value in the relocation register is added to every address generated by a user process at the time it is sent to memory The user program deals with logical addresses it never sees the real physical addresses titllocair 3 r Goal Allowtransparent sharing Each address space may be placed anywhere in memory 0 OS finds free space for new process 0 Modify addresses statically similar to linker when load process Process 3 OS Discussion oi Advantages o Requires no hardware support Disadvantages o No protection Process can destroy OS or other processes No privacy 0 Address space must be allocated contiguously Allocate space forworstcase stack and heap 0 Cannot move address space after it has been placed May not be able to allocate new process mic Allin Oil Goal Protect processes from one another Requires hardware support Memory Management Unit MMU MMU dynamically changes process address at every memory reference Process generates logical or virtual addresses Memory hardware uses physical or real addresses Process runs here OS can control MMU Logical address Physical address tr Dynar riic Two operating modes Privileged protected kernel mode OS runs When enter OS trap system calls interrupts exceptions Allows certain instructions to be executed 0 Can manipulate contents of MMU Allows OS to access all of physical memory User mode User processes run Perform translation of logical address to physical address MMU contains base and limit registers base start location for address space limit size limit of address space Shhquot WEBB rfri MEI l lQl Ej lb 1 s34 Base and limit registers Swapping Paging and page tables and TLBs Segmentation and segment tables Page fault handling gt Virtual memory Translation on every memory access of user process MMU compares logical address to limit register if logical address is greater then generate error MMU adds base register to logical address to form physical address I base base limil trap to operating system monitor addressing error memory M With Big se and erriit Contextswitch Add base and limit registers to PCB Steps Change to privileged mode Save base and limit registers of old process Load base and limit registers of new process Change to user mode and jump to new process What if don t change base and limit registers when switch rill n s 21 i n O l3 i Protection requirement User process cannot change base and limit registers User process cannot change to privileged mode Advantages Provides protection both read and write across address spaces Supports dynamic relocation Can move address spaces Simple inexpensive implementation Few registers little logic in MMU Fast Add and compare can be done in parallel Disadvantages Each process must be allocated contiguously in physical memory Must allocate memory that may not be used by process No partial sharing Cannot share limited parts of address space A process can be swapped temporarily out of memory to a backing store and then brought back into memory for continued execution Backing store swap space fast disk large enough to accommodate copies of all memory images for all users must provide direct access to these memory images Roll out roll in swapping variant used for prioritybased scheduling algorithms lowerpriority process is swapped out so higherpriority process can be loaded and executed Major part of swap time is transfer time total transfer time is directly proportional to the amount of memory swapped Modified versions of swapping are found on many systems ie UNIX Linux and Windows operating system swap out swap in backing store 4 A a I Pat 5 Main memory usually into two partitions Resident operating system usually held in low memory with interrupt vector User processes then held in high memory Singlepartition allocation baseregister scheme used to protect user processes from each other and from changing operatingsystem code and data base register contains value of smallest physical address limit register contains range of logical addresses Multiplepartition allocation Fixed partition Variable partition in Physical memory is broken up into fixed partitions partitioning never changes either each partition has separate input queue or all partitions with a single input queue how do we provide protection use base limit registers Advantages Simple Problems internal fragmentation the xed size partition is larger than what was re ested external fragmentation two small partitions left but one big job lelt Physical memory is broken up into variablesized partitions quot ns are created dynamically each process is loaded into a partition of exactly the same size as the proc Advantages no internal 39agmentation simply allocate partition size to be just big enough for process Problem external fragmentation as we load and unload jobs holes are left scattered throughout physical memory a y 39 Ileupaniiiull systems Variable partition allocation Hole block of available memory holes ofvarious size are scattered throughout memory When a process arrives it is allocated memory from a commodate it ystem maintains information about b free partitions hole hole large enough to ac Operatin a allocated partitions How to satisfy a request of size n from a list of free holes Firstfit Allocate the first hole that is big enough Bestfit Allocate the smallest hole that is big enough must earch entire list unless ordered by size Produces the smallest leftover hole Worstfit Allocate the largest hole must also search entire list Produces the largest leftove ole Firstfit and bestfit better than worstfit in terms of speed and storage utilization External Fragmentation total memory space exists to satisfy a request but it is not contiguous Internal Fragmentation allocated memory may be slightly largerthan requested memory this size difference is memory internal to a partition but not being used Reduce external fragmentation by compaction Shuf e memory contents to place all 39ee memory together in one large block Compaction is possible only if relocation is dynamic and is done at execution time Paging 0 address translation 0 page table 0 hardware support Translation lookaside buffers TLBs Segmentation o segmented addressing o segmentation with paging Solve the external fragmentation problem by using fixed sized units in both physical and virtual memory 0 physical address space of a process can be noncontiguous 0 Divide physical memory into fixedsized blocks called frames Divide logical memory into blocks of same size called pages 0 Set up a page table to translate logical to physical addresses 0 Internal fragmentation Processes View memory as a contiguous address space from bytes 0 through N In reality logical pages are scattered across physical memory frames not contiguous as earlier 0 virtualtophysical mapping page table 0 this mapping is invisible to the program lagin ng View Goal Eliminate external fragmentation Idea Divide memory into xedsized pages Size 2quot Exam le4KB Physical page page frame Physical View Process 1 Process 3 Process 2 Logical View l Addl quot Logical address generated by CPU is divided into 0 Page number p used as an index into a page table which contains base address of each page pages corresponding frame number f in physical memory 0 Page offset d combined with base address to define the physical memory address that is sent to the memory unit Physical address is fd m Fate 4 o managed by the OS 0 map logical page number p to physical frame number 0 p is simply an index into the page table 0 one page table entry PTE per page in logical address space ie each p has PTE in the table PTE s control mapping the valid bit says whether or not the PTE can be used says whether or not a virtual address is valid it is checked each time a virtual address is used the referenced bit says whether the page has been accessed it 39s t een read or written to the modi ed bit says whether or not the page is dirty it is set when a write to the page has occurred the protection bits control which operations are allowed read write execute the frame number determines the physical frame physical frame start address ltdechanism gr Address Trar islation logical physical address address physical memory Paging Example page 0 page 1 page 0 page 2 page 3 page table page 2 logical page 1 memory page 3 physical lrnpierrtehtatlon of Page Table 0 Page table is kept in main memory Pagetable base register PTBR points to the page table Pagetable length register PRLR indicates size of the page table 0 In this scheme every datainstruction access requires two memory accesses One for the page table and one for the datainstruction The two memory access problem can be solved by the use of a special fastIookup hardware cache called translation lookaside buffers TLBs Translation LppkAsirle Baifl er TLle Goal Avoid page table lookups in main memory Idea Hardware cache of recent page translations Typical size 64 2K entries Why does this work process references few unique pages in time interval spatial temporal locality On each memory reference check TLB for translation If present hit use cached frame number and append page offset Else miss Use page tables to get frame number Update TLB for next access replace some entry frame TLB hit physical physical page table Easy to allocate physical memory 0 physical memory is allocated from free list of frames to allocate a frame just remove it from the free list 0 external fragmentation is not a problem Leads naturally to virtual memory entire program need not to be memory resident take page faults using valid bit 0 but paging was originally introduced to deal with external fragmentation not to allow programs to be partially resident Can still have internal fragmentation process may not use memory in exact multiples of pages Memory reference overhead 2 references per address lookup page table then memory solution use a hardware cache to absorb page table lookups translation lookaside buffer TLB Memory required to hold page tables can be large need one PTE per page in address space 32 bit AS with 4KB pages 220 PTEs 1048576 PTEs 4 bytesPTE 4MB per page table OS s typically have separate page tables per process 25 processes 100MB of page tables Divide address space into logical segments 0 A program is a collection of segments 0 Each segment corresponds to logical entity in address space code stack heap Each segment can independently be placed separately in physical memory grow and shrink Be protected separate readwriteexecute protection its subroutine symbol table main program sqrf logical addiess 11 g user space physical memory space Paging mitigates various memory allocation complexities eg fragmentation view an address space as a linear array of bytes divide it into pages of equal size eg 4KB use a page table to map virtual pages to physical page frames page logical gt page frame physical Segmentation partition an address space into logical units stack code heap subroutines a virtual address is ltsegment offsetgt More logical a logical address space is a collection of variablesize segments they are really independent no necessary order among segments Facilitates sharing and reuse a segment is a natural unit of sharing a subroutine or function Different protection for different segments readonly status for code A natural extension of variablesized partitions variablesized partition 1 segmentprocess segmentation many segmentsprocess Protection and Security CSCI 444544 Operating Systems Fall 2008 0 Protection goals and principle 0 User authentication and access control 0 Security vulnerabilities o Cryptography as a security tool Protection more important as computer systems develop Multiple users have access to same resources Computers connected to network Increasing importance to electronic commerce Goals Ensure users only do what they are supposed to do Prevent accidental misuse Example Mistakenly overwrite command interpreter Relatively easy to solve by making hard to do Prevent malicious abuse Example Break into accounting system and transfer 1million Hard to completely eliminate Guiding principle principle of least privilege 0 Programs users and systems should be given just enough privileges to perform their tasks Authentication 0 Make sure system knows who are you Authorization 0 Determine what the user is and is not allowed to do Access enforcement 0 Make sure no loopholes in the system Auditing 0 Record Vinat users and programs are doing for later analysisprosecution How do you prove Vino you are Passwords Secret piece ofinformation known only by user System should not store in readable form Oneway transformations must be used when check Disadvantage Relatively easy to crack mans choose poor passwords Short passwords are easy to find Wlth brute force Common words found in dictionaries Physical possession of item proves identity Should not be forgeable or able to be copied Advantage If stolen user is aware Disadvantage Relatively expensive to make Access rights represented with access matrix 0 One domain eg user per row One resource eg files per column Each entry indicates privileges of domain for resource File A File B File C File D User 1 RW RW RW RW User 2 RW RW User 3 RW R User 4 RW R RW User 5 RW R RW Access matrix is sparsely populated Condense information by expressing in two forms Access control list Per column Capability Per row Access Control Lists ACLs For each resource indicate users that can perform operations General form Each resource has list of ltuser privilegegt pairs Disadvantage Tedious to have separate entry for every user Optimization Group users into classes UNIX example 0 Three classes of users self group everyone else 0 Three privileges read write execute Advantage Easy to revoke privileges Owner Process A R BRW CR BRWX c RX User space Kernel space Use of access control lists for managing file access Capabilities For each user indicate resources that can be accessed General form Each user has list of ltresource privilegegt pairs 0 Compare against ACL May builtin with handle to resources More efficient access right checking Disadvantage Difficult to revoke capabilities since they are distributed throughout the system 0 Important concern a user should not be able to tamper its capabilities Kernelspace capability list Clist User programs use handles eg file descriptor to refer to them C list User space Ke m el space ln lltgilEi liaz liiFl quot l Tagged architecture 0 Memory words containing capabilities are tagged user programs can only read those words Only kernel can change those words Cryptographicallyprotected capabilities Clist is in user space but capability is formed cryptographically so that user cannot tamper it does not require hardware support Protection can be applied to non le resources Solaris 10 provides rolebased access control to implement least privilege Privilege is right to execute system call or use an option within a system call 0 Can be assigned to processes 0 Users assigned roles granting access to privileges and programs executes with role 1 privileges Access List Delete access rights from access list 0 Simple Immediate Capability List Scheme required to locate capability in the system before capability can be revoked Responsibilities of security kernel 0 Protecting identification and authorization information o Enforcing access controls Requirements 0 Must run in protected mode 0 As small and simple as possible Paradox o More powerful protection mechanism gt Larger and more complex security kernel gt More likely to have implementation bugs gt More security holes Security must consider external environment of the system and protect the system resources Intruders crackers attempt to breach security Threat is potential security violation Attack is attempt to breach security Attack can be accidental or malicious Easier to protect against accidental than malicious misuse Categories Breach of con dentiality Breach of integri y Breach of availability Theft of service Denial of service Methods Masquerading breach authentication Replay attack Message modi cation Maninthemiddle attack Session hijacking Trojan Horse Code segment that misuses its environment u er I be executed by other users Spyware popup browser windows covert channels Trap Door pea u er iuemillel u r procedures Could be included in a compiler Logic Bomb Program that initiates a security incident under certain circumstances Stack and Buffer Over ow Exploits a bug in a program over ow either the stack or memory buffers
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'