Operating Systems Lecture Notes PDF

Agenda November 21 – Lecture 25 Reminders Read 3 EP: Chapters 20 – 22 Virtual Memory Module 8 Chapters 36, 37 Devices Project 5 – Implementing a Simple File System 3rd / Final deliverable 12/4 LAST DEMO 12/9 Attendance No Classes Next Week QUIZ 12/4 SFF: class & lab Final E...

Agenda November 21 – Lecture 25 Reminders Read 3 EP: Chapters 20 – 22 Virtual Memory Module 8 Chapters 36, 37 Devices Project 5 – Implementing a Simple File System 3rd / Final deliverable 12/4 LAST DEMO 12/9 Attendance No Classes Next Week QUIZ 12/4 SFF: class & lab Final Exam: Thursday 12/12 10:30 – 12:30 Beury 160 Enjoy the Thanksgiving Holiday 1 Last Time Page Replacement FIFO Optimal LRU LRU Approximations Policies for managing memory allocation Today Page Replacement Policies for managing memory allocation Fetch Resident Set Management Fixed/Variable Allocation Local/Global Scope Working Set Strategy Memory Mapped Files Device Management QUIZ 9 T / F Storage block allocation in a file system using multi-level indexing wastes space for the several types of indirect addressing if the file is very small (e.g., only 5 data blocks in size). T / F When using a FAT implementation for a filesystem, the size (number of bits) of each FAT entry is determined by the number of bytes in a file system block. T / F A clock algorithm, such as second chance, used for page replacement records the time of reference for each page in order to determine the LRU page. T / F The present bit is added to each page table entry of a process to indicate that the page is a valid part of the process virtual address space. Fetch Policy REFRESH The Fetch Policy determines when a page should be brought into main memory Two Common alternatives & could be used together Demand Paging Prepaging Demand Paging only brings pages into main memory when a reference is made to a location on the page many page faults when process is first started principle of locality suggests that as more and more pages are brought in, most future references will be to pages that have recently been brought in, and page faults should drop to a very low level  Fetch Policy Prepaging (sometimes pages are organized in clusters of contiguous pages on storage device) pages other than the one demanded by a page fault are brought to memory exploits the characteristics of most secondary memory devices if pages of a process are stored contiguously in secondary memory it is more efficient to bring in a number of pages at one time ineffective if extra pages are not referenced once loaded in memory not to be confused with “swapping” Where the entire resident set is moved out and brought back when resumed  Resident Set Management The OS must decide how many pages to bring into main memory for a process The smaller the amount of memory allocated to each process, the more processes can reside in memory Trade-Offs Small number of pages loaded, increases # of page faults Beyond a certain size, further allocations of frames will not affect the page fault rate Resident Set => Set of pages of a process currently in physical memory  Policies for Resident Set Size Fixed-allocation Variable-allocation Gives a process a fixed Allows the number of number of frames in page frames allocated to main memory within a process to be varied which to execute over the lifetime of the process When a page fault occurs, one of the pages of that process must be replaced Replacement Scope The scope of a replacement strategy can be categorized as global or local For each type, replacement is activated by a page fault when there are no free page frames for the process Local Chooses only among the resident pages of the process that generated the page fault Global Considers all unlocked pages in main memory  Local Replacement Global Replacement Fixed Allocation Number of frames allocated Not possible. to a process is fixed. Page to be replaced is chosen from among the frames allocated to that process. Variable Allocation The number of frames Page to be replaced is chosen from allocated to a process may be all available frames in main changed from time to time to memory; this causes the size of the maintain the working set of resident set of processes to vary. the process. Page to be replaced is chosen from among the frames allocated to that process. Resident Set Management Policy  Fixed Allocation, Local Scope Necessary to decide ahead of time the amount of allocation to give a process If allocation is too small, there will be a high page fault rate If allocation is too large, there Increased processor idle time will be too few Increased time spent in programs in swapping main memory  Variable Allocation Global Scope Easiest to implement Adopted in a number of operating systems OS maintains a list of free frames A Free frame is added to resident set of process when a page fault occurs. [the faulting process grows in size] How/When If no frames are available, the OS must choose a page does it shrink? currently in memory to replace choosing a global page can have negative affect on victim process One way to counter potential problems is to use page buffering: if it was a bad choice, the page still in memory  Variable Allocation Local Scope When a new process is loaded into main memory, allocate to it a certain number of page frames as its resident set When a page fault occurs, select the page to replace from among the resident set of the process that suffers the fault Reevaluate (periodically or ?) the allocation provided to the process and increase or decrease the allocation to improve overall performance  Variable Allocation Local Scope Decision to increase or decrease a resident set size is based on the assessment of the likely future demands of active processes The Working Set Key elements: Strategy is a good example of Criteria used to determine Variable Allocation, Local resident set size Scope The timing of when changes are made  Working Set Concept A program needs a certain set of pages resident in memory to run efficiently. If not enough page frames are available, the page fault rate becomes too high What if it has too many frames? the process spends much of the time waiting for pages to be loaded The optimal working set of a process is the set of pages that will be needed in the immediate future and thus should be resident. The size of the working set varies with the program's behavior.: IF execution is highly localized, the set contains a small number of repeated page numbers. When execution involves many branches or highly dynamic data structures, the set contains many different page numbers. Locality of Reference Working Set To determine the optimal working set at time t, a window of size Δ is superimposed on the page reference string. ( Δ is a time interval ) Pages visible in the window belong to the working set. The size and composition of the set of pages change automatically as the window slides forward in time with each memory reference Window Size (width) is determined by the typical behavior of a newly started program. During the first few memory operations of a program, the number of pages referenced increases rapidly, but the rate of increase diminishes with time. Δ must be chosen to cover the period of rapid growth but not past the point where adding more pages is of only marginal benefit  Working set changes for a fixed △ Working Set Size The particular Pages in the WS are changing also Transient Transient Transient Transient Time Stable Stable Stable Stable Figure 8.18 Typical Graph of Working Set Size [MAEK87]  Working Set Algorithm Working Set Size As K (window size) becomes large it is a non-decreasing monotonic function and approaches the number of frames in the process. The working set is the set of pages used by the k or Δ most recent memory references. The function w(k,t) is the size of the working set at time t.  Working Set Strategy A strategy of variable allocation, local scope Working set parameter  for a process at virtual time t, w( ,t ) is the set of pages for that process that have been referenced in the last  virtual time units (t- , t). Virtual time could be instruction cycles with 1 instruction per cycle, or any other consistent unit. Virtual time is time elapsing while the process executes Basic Working Set concept Monitor the working set of each process Periodically remove from the working set of a process pages that are no longer in the working set A process may execute only if its working set is in main memory (i.e., the working set is the resident set). Working-set model ce string ∆ = 10 references  Working-Set Model working-set window - a fixed number of page references Example: 10,000 instructions (or references) WSSi (working set size of Process Pi) = total number of pages referenced in the most recent interval (# pages varies in time) if too small will not encompass entire locality if too large will encompass several localities if => infinity: will encompass entire program D = Sum(WSSi) - total demand frames if D > m → Thrashing (m = # frames in memory) Policy if D > m: suspend one of the processes Thrashing A state in which the To avoid this, the operating system system spends most tries to guess, based of its time swapping on recent history, process pieces which pieces are rather than executing least likely to be instructions used in the near future  Thrashing Processor Utilization Multiprogramming Level Figure 8.19 Multiprogramming Effects Working-set model ce string ∆ = 10 references Page Replacement using the Working Set Strategy Find a page not in WS & Evict At page fault Reset R to 0 age = current_virtual_time - time of last use Hardware sets the R & M bits 𝛕 some system defined Timer interrupt periodically – if R is 1, reset the R bit interval At a Page Fault – look for page (s) to evict  Sequence of Page Window Size, D References 2 3 4 5 Time 24 24 24 24 24 15 24 15 24 15 24 15 24 15 18 15 18 24 15 18 24 15 18 24 15 18 23 18 23 15 18 23 24 15 18 23 24 15 18 23 24 23 24 18 23 24 17 18 24 17 17 18 23 24 17 24 17 18 18 23 24 17 15 18 23 24 17 18 23 24 17. Implies unchanged 24 18 24 24 17 18 from previous 18 18 24 24 17 18 17 18 17 24 18 17 17 17 18 17 15 17 15 17 15 18 17 15 24 18 17 15 24 15 24 17 15 24 17 15 24 17 24 17 17 15 24 24 24 17 18 24 18 17 24 18 17 24 18 15 17 24 18 Figure 8.17 Working Set of Process as Defined by Window Size