tailieunhanh - Lecture Operating system concepts - Lecture 13

In this chapter, we begin a discussion of file systems at the lowest level: the structure of secondary storage. We first describe the physical structure of hard disks and magnetic tapes. We then describe disk-scheduling algorithms, which schedule the order of disk I/Os to maximize performance. Next, we discuss disk formatting and management of boot blocks, damaged blocks, and swap space. We conclude with an examination of the structure of RAID systems. | CSC 322 Operating Systems Concepts Lecture - 14: by Ahmed Mumtaz Mustehsan Special Thanks To: Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. (Chapter-3) Ahmed Mumtaz Mustehsan, CIIT, Islamabad 1 Chapter 3 Memory Management Virtual Memory (Inverted Page Table) Page Replacement Algorithms lECTURE-14 Ahmed Mumtaz Mustehsan, CIIT, Islamabad 2 Multi-level page table works for 32 bit memory Doesn’t work for 64 bit memory 264 bytes and 4 KB pages => 252 entries in page table If each entry is 8 bytes => 30 million GB or 30PB for page table Need a new solution Multi-level page table gets too big lECTURE-14 3 Ahmed Mumtaz Mustehsan, CIIT, Islamabad Keep one entry per (real) page frame in the “inverted” table Entries keep track of (process, virtual page) associated with page frame Need to find frame associated with (n, p) for each memory reference process n, virtual page number p Inverted Page Table lECTURE-14 4 Ahmed Mumtaz Mustehsan, CIIT, Islamabad Search page frames | CSC 322 Operating Systems Concepts Lecture - 14: by Ahmed Mumtaz Mustehsan Special Thanks To: Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. (Chapter-3) Ahmed Mumtaz Mustehsan, CIIT, Islamabad 1 Chapter 3 Memory Management Virtual Memory (Inverted Page Table) Page Replacement Algorithms lECTURE-14 Ahmed Mumtaz Mustehsan, CIIT, Islamabad 2 Multi-level page table works for 32 bit memory Doesn’t work for 64 bit memory 264 bytes and 4 KB pages => 252 entries in page table If each entry is 8 bytes => 30 million GB or 30PB for page table Need a new solution Multi-level page table gets too big lECTURE-14 3 Ahmed Mumtaz Mustehsan, CIIT, Islamabad Keep one entry per (real) page frame in the “inverted” table Entries keep track of (process, virtual page) associated with page frame Need to find frame associated with (n, p) for each memory reference process n, virtual page number p Inverted Page Table lECTURE-14 4 Ahmed Mumtaz Mustehsan, CIIT, Islamabad Search page frames on every memory reference How to do this efficiently? Keep heavily used frames in TLB (Translation is very fact) If miss, then can use and associative search to find virtual page to frame mapping Use a hash table hashed on virtual address. Use linked list. (If hash table entries equal page frame number, average chain will just have just one entry) Inverted Page Table is common on 64 bit machines Need to search inverted table efficiently lECTURE-14 5 Ahmed Mumtaz Mustehsan, CIIT, Islamabad Inverted Page Tables-the Picture lECTURE-14 6 Ahmed Mumtaz Mustehsan, CIIT, Islamabad When Page fault occurs! If new page is brought in, need to chose a page to evict Don’t want to evict heavily used pages If page has been written to, need to copy it to disk. Otherwise, a good copy is on the disk=>can write over it Page Replacement Algorithms lECTURE-14 Ahmed Mumtaz Mustehsan, CIIT, Islamabad 7 Similar problem in other parts of Computer Science! One or more cache (32 or 64 memory Blocks) of recently .