Download Operating Systems: CS414 Class Notes - Virtual Memory and File Systems - Prof. Marty A. Hu and more Study notes Operating Systems in PDF only on Docsity! 1 CS414: Operating Systems Today’s Class •Last time (Tues) Virtual memory (chapt 10) •This time Finish Virtual memory (chapt 10) File systems interface and implementation •Next time (tonight OLS 120 6pm / tomorrow OLS 120 3pm) File systems – interface and implementation (Chapts 11/12) CS414: Operating Systems Before we start •No class next week (Tues and Thurs), no office hours for me next mon/tues – some email availability Yes, blake will have office hours: Wed Nov 14 5-8pm 002a Mon Nov 19 5-8pm I will have office hours Mon Nov 19 1-4pm, Tue Nov 20 10- 11am ALSO: tomorrow (Nov 9) noon – 3pm CS414: Operating Systems Schedule Sun Tues Thurs Fri No class – marty at conference Virtual memory 6 8 13 15 20 22 protection, security PA#6 due, PA#7 out 27 29 protection, security 4 protection, security File systems File sys, I/O sys File sys I/O sys 9 No class – marty at conference I/O sys,Mass-storage PA#5 due, PA#6 out No class – Thanksgiving 14 Final exam 10:00-noon 6 Wrap-up PA#7 due protection, security protection, security 30 CS414: Operating Systems Before we start: PA#5 •You can use C, C++, Java, or a .NET language, with a monitor or just semaphores, on any/all of the 3 problems (can be the same language for all three) Focus on algorithmic design, not “sidetracked” by language “idiosyncratic behavior” •Dorm-matching is a different beast than the other two (which are simulations) CS414: Operating Systems Before we start •FYI: page tables can be huge; e.g., logical address space = 232, page size = 212 (4K), then page table is How big?; answer: 220; (1 Meg entries)! Solution: two or more levels (page the page table) CS414: Operating Systems Overview of Page Replacement Algorithms On a page fault, we need to choose a page to kick out •[Random] questionable performance •[Optimal] (aka MIN) Look into the future and throw out the page that will be accessed furthest into the future •[LRU] Throw out the page that has not been used in the longest time. This is too expensive. Why? •[LFU] must overcome “inertia” •[FIFO] Throw out the oldest page. 2 CS414: Operating Systems Examples: FIFO •3 page frames (F1, F2, F3) •100 word pages (Note: this is not an OS-oriented page size!) •reference string: 642 402 403 404 180 256 401 360 401 •page trace: 6 4 4 4 1 2 4 3 4 F1 F2 F3 FIFO Number of page faults: CS414: Operating Systems Examples: Optimal 6 4 4 4 1 2 4 3 4 F1 F2 F3 Optimal Number of page faults: CS414: Operating Systems Examples: LRU 6 4 4 4 1 2 4 3 4 F1 F2 F3 LRU Number of page faults: 1 2 3 4 1 2 3 4 1 F1 F2 F3 When will LRU perform poorly? Number of page faults: CS414: Operating Systems Adding Memory: FIFO A B C D A B E A B C D E F1 F2 F3 Number of page faults: A B C D A B E A B C D E F1 F2 F3 F4 Number of page faults: CS414: Operating Systems Adding Memory •Does adding memory always reduce the # of page faults? [Yes] for LRU and MIN, and other stack-based algorithms. [No] for FIFO (Belady's anomaly) • With FIFO, the contents of memory can be completely different with a different number of page frames. •In contrast, LRU, MIN, and other stack-based algorithms ensure that the contents of memory with X frames is a subset of the contents with X+1 page frames, so adding memory reduces the number of page faults. CS414: Operating Systems Implementing LRU •LRU is most widely used; however, an approximation is used because of space and time considerations •Perfect LRU -- Keep a time stamp for each page with the time of the last access. Throw out the LRU page. •LRU Approximations [Hardware Support] a reference bit. Each access to a page causes the HW to set the reference bit to 1 (periodically resetting to 0) [Additional-Reference-Hits] OS shifts reference bit right in a counter. Lowest numbered page is kicked out. [Second Chance] FIFO queue with a reference bit. Keep pages in a circular queue. If reference bit is 1, set it to 0. If reference bit is 0, kick out the page.
