OS2
Terms
undefined, object
copy deck
- What is the TLB Reach formula?
- TLB Reach = (TLB Size) X (Page Size)
- What is Virtual memory?
- Separation of user logical memory from physical memory. Only part of the program needs to be in memory for execution Logical address space can therefore be much larger than physical address space Allows address spaces to be shared by several processes Allows for more efficient process creation Virtual memory can be implemented via: Demand paging Demand segmentation
- What is Demand Paging?
- Bring a page into memory only when it is needed. Less I/O needed, Less memory needed, Faster response, More users
- What is a Lazy Swapper?
- never swaps a page into memory unless page will be needed Swapper that deals with pages is a pager.
- What kind of bits are on each page table?
- Valid and Invalid Bits. V or I.
- If there is a reference to a page, first reference to that page will trap to operating system and cause what?
- A page fault.
- What happens when a page fault is encountered?
- 1.Operating system looks at another table to decide: - Invalid reference -> abort. -Just not in memory 2.Get empty frame 3.Swap page into frame 4.Reset tables 5.Set validation bit = v 6.Restart the instruction that caused the page fault
- What range of values is a page fault rate, p?
- 0 <= p <= 1.0 if p = 0 no page faults. if p = 1, every reference is a fault.
- What is the Effective Access Time (EAT) formula?
- EAT = (1 – p) x memory access + p (page fault overhead + swap page out + swap page in + restart overhead)
- Demand Paging example:
- Memory access time = 200 nanoseconds Average page-fault service time = 8 milliseconds EAT = (1 – p) x 200 + p (8 milliseconds) = (1 – p x 200 + p x 8,000,000 = 200 + p x 7,999,800 If one access out of 1,000 causes a page fault, then EAT = 8.2 microseconds. This is a slowdown by a factor of 40!!
- What does page replacement complete?
- Page replacement completes separation between logical memory and physical memory – large virtual memory can be provided on a smaller physical memory.
- As far as page faults are concerned, what do more frames mean?
- More page faults!
- What is the Least Recently Used (LRU) Algorithm?
- It's an algorithm for reducing page faults. It orders the reference string and reuses the frames until there is a number not in the frame, then it replaces the least used part of the frame with the new number.
- Stack implementation of LRU?
- Stack implementation – keep a stack of page numbers in a double link form: Page referenced: move it to the top requires 6 pointers to be changed No search for replacement
- What is equal frame allocation algorithm?
- For example, if there are 100 frames and 5 processes, give each process 20 frames.
- What is the proportional allocation algorithm?
- Allocate according to the size of process. Si = Size of process Pi S=sum of Si m = total number of frames Ai = allocation for Pi = Si/S * M
- What is thrashing?
- A process is busy swapping pages in and out
- If a process does not have “enough†pages, the page-fault rate is very high. This leads to?
- - low CPU utilization - operating system thinks that it needs to increase the degree of multiprogramming - another process added to the system
- Why does thrashing occur?
- Sigma(sum of) size of locality > total memory size
- Working Set Model?
- working-set window = a fixed number of page references Example: 10,000 instruction WSSi (working set of Process Pi) = total number of pages referenced in the most recent delta (varies in time) -if delta too small will not encompass entire locality -if delta too large will encompass several localities -if delta = infinite then it will encompass entire program - D = Sum of( WSSi )= total demand frames -if D > m then Thrashing - Policy if D > m, then suspend one of the processes
- What is TLB reach?
- The amount of memory accessible from the TLB.
- 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 time. - Execution time: Binding delayed until run time if the process can be moved during its execution from one memory segment to another. Need hardware support for address maps (e.g., base and limit registers).
- Define physical and logical addresses.
- Logical address – generated by the CPU; also referred to as virtual address Physical address – address seen by the memory unit.
- What is a memory management unit?
- Hardware device that maps virtual to physical address. The user program deals with logical addresses; it never sees the real physical addresses
- What is a backing store?
- fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images
- What is a major part of swap time?
- Major part of swap time is transfer time; total transfer time is directly proportional to the amount of memory swapped.
- What is external fragmentation?
- total memory space exists to satisfy a request, but it is not contiguous.
- What is internal fragmentation?
- allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used.
- What is paging?
- Divide physical memory into fixed-sized blocks called frames (size is power of 2, between 512 bytes and 8,192 bytes) Divide logical memory into blocks of same size called pages. To run a program of size n pages, need to find n free frames and load program. Set up a page table to translate logical to physical addresses. It has internal fragmentation.
- Performance Evaluation - Quantitative Approach equations
- A - Arrivals C - Completions T - Time the system is observed B - Busy; fraction of time system is being used S - Avg. service time, S = B/C X - Throughput, X = C/T Lamda - Arrival rate, Lamda = A/T U - Utilization, U = S*X = B/C*C/T = B/T Average Residence Time - R = W/C Little's law - N = X*R = W/T R - Response Time, R = N/X - Z Z - Average think time, no formula Forced Flow Law - Xk = VkX
- Example one, Quantitative.
- Determine avg. system response time for an interactive system with following characteristics 25 terminals (N = 25) 18 sec average think time (Z = 18) 20 visits to specific disk per interaction (Vd = 20) 30% utilization of disk (Ud = .30) 25 millisecond – avg. service requirement per visit to disk (Sd = .025 sec) Find R, Xd, X Xd = Ud/Sd = .30/.025 = 12 req/sec X = Xd/Vd = 12/20 = 0.6 interactions/sec R = N/X – Z = 25/0.6 -18 = 23.7 secs
- Performance Evaluation - Analytical Approach equations
- T Time we observe the system A # of Arrival C # of Completions S Service Time Lamda: Arrive Rate, lamda = A/T Mew: Completion rate, mew = 1/S Response Time with a bar over top: R = 1/(mew - lamda) Average waiting time in the queue (Wq) = U/(mew-lamda) Average number of IORB's in the queue: Nq = U^2/(1-U)