Operating Systems: Memory - University of Guelph - PDF

Operating Systems: Memory CIS*3110: Operating Systems Dr. A. Hamilton-Wright School of Computer Science University of Guelph 2024-12-01 1 / 41 Unix-Style Process Image 0xFFFFFFFF Stack...

Operating Systems: Memory CIS*3110: Operating Systems Dr. A. Hamilton-Wright School of Computer Science University of Guelph 2024-12-01 1 / 41 Unix-Style Process Image 0xFFFFFFFF Stack text – contains executable code other processes data – contains static data shared with Data Segment Dynamic Data Shared BSS Data symbol table – symbol (literal) definitions Symbols Static – strings, constants Data Segment Text Text (machine code) 0x00000000 2 / 41  0xFFFFFFFF Stack Process Image: Unique pro- Data Segment Dynamic cess image “contains” all data Data Shared Data Symbols Static Data Segment Text Text (machine code) 0x00000000 3 / 41  0xFFFFFFFF 0xFFFFFFFF Stack Stack Program may clone itself using fork(): most data copied Data Segment Data Segment Dynamic Dynamic Data Data shared (pointer) to shared Shared Shared libs, shared mem, readonly Data Data Symbols Symbols portions (text, symbols) Static Static Data Data Segment Segment Text Text Text Text (machine (machine code) code) 0x00000000 0x00000000 4 / 41  0xFFFFFFFF 0xFFFFFFFF Stack Stack If a new POSIX thread is cre- ated: most data is shared only the stack is copied → only local variables may be used without potential race conditions Data Segment Data Segment Dynamic Dynamic Data Data different thread Shared Shared implementation give Data Data Symbols Symbols different things Static Static fibres are threads that use Data Data co-operative Segment Segment multitasking instead of Text Text Text Text preemptive multitasking (machine (machine code) code) 0x00000000 0x00000000 5 / 41 Protected Virtual Addressing program sees only virtual addresses kernel sees/manages all address 0xFFFFFFFF spaces k ac ss 0 St one program cannot ‘see’ or Proce a ac Tex Dat 0xFFFFFFFF affect any other programs in k k t ac 0x00000000 0xFFFFFFFF s1 St St memory s Proce ap a at D G xt large space requirements to store Te 0x00000000 many programs a 0xFFFFFFFF k sN ac at St D s Proce a program may largely consist of at D xt xt Te 0x00000000 Te l rne Ke ory ts ‘empty space’ between stack and 0x00000000 m n me reme req ui data each program is divided into pages; only the pages currently needed are represented in (or loaded into) in real memory 6 / 41 Process image and logical pages 0xFFFFFFFF ck a St process image is “sliced” into pages independent of data ap unneeded pages arrangement on G pages “page + offset” → logical position of... 39 a... at byte D 4 10... 0 1 2 3...... 9 3 physical storage ↔ page 3, byte 2 2 @ 40 bytes/page logical? = absolute 3x40+2 xt 1 = 120 + 2 = 122 Te 0 0x00000000 7 / 41 MMU (Memory Management Unit) Translates virtual ⇒ physical addresses A virtual address: Page # Offset Translation Table (Page Table) 5 9 + Physical Address 7 Page Frame Main Memory OR I/O device registers 8 / 41 MMU - Address Translation Processes are divided into pages (analogies: book, also slice of a loaf of bread) VirtualAddress/PageSize = VirtualPageNumber VirtualAddress%PageSize = PageOffset Use virtual page number to look up the frame number for the page number in the page table. (FrameNumber × PageSize) + Offset = PhysicalAddress 9 / 41 Relationship between CPU and Memory CPU MMU Memory (ALU) (RAM chips) Virtual Physical Addresses Addresses 10 / 41 Valid and Invalid regions of Memory the hardware page table contains the following information for each page within a process whether the page is “valid”, meaning “in memory” (called the V bit) writeability: usually called RO or W dirty and used bits – more on this shortly page frame number additionally, the in-memory page table contains an associated disk address if paged out the valid bit indicates whether page is currently in memory; the bottom of the stack and top of the heap indicate whether the page is legally part of the process 11 / 41  Page Table Main Memory V RO D U Page Frame Disk Addr Example #1: F 0 0 C 0x16 P0−2 (RO) Given a page size of E D 1 0 0 11 6 0x14 0x12 P0−6 P2−0 P4−2 51210 bytes = ???16 C B 0 0 0x10 P1−4 0x0E PA−0 P1−E Read virtual address A 0 0x0C P0−A P1−3 (RO) 9 0 0x0A P5−1 PA−A 0x072E (for process 1) 8 0 0x08 P0−C P2−1 7 0 0 11 0x06 P0−4 P5−F 0x200 = 29 ⇒ 9 bits of 6 1 0 1 0x04 P1−2 (RO) P1−5 5 1 0 5 0x02 P5−4 P5−0 offset 4 1 0 10 0x00 P0−1 (RO) P1−6 3 1 1 D 4 0x072E / 0x200 = 0x3 2 1 1 4 (0x12E remainder) 1 0 0 0 1 1 B 5 page 0x3 ⇒ frame 0xD Paging Disk 0 0xD × 0x200 = 0x1A00 4 P0−D P0−1(RO) P0−8 P0−E P1−3 (RO) P0−B + 0x12E 8 P1−0 (RO) P1−E P1−1 (RO) = physical address C P1−F P0−5 P0−3(RO) P0−F 10 0x1B2E P1−7 P2−0 (RO) 12 / 41  Page Table Main Memory V RO D U Page Frame Disk Addr F 0 0 C 0x16 P0−2 (RO) Example #2: E 1 0 11 6 0x14 P0−6 P2−0 D 0 0x12 P4−2 Given a page offset of C 0 0x10 P1−4 P1−E 11 bits B A 0 0 0x0E PA−0 0x0C P0−A P1−3 (RO) 11 wires of bus used 9 0 0x0A P5−1 PA−A 8 0 0x08 P0−C P2−1 for offset; 7 0 0 11 0x06 P0−4 P5−F 211 =0x800 6 5 1 0 1 0 1 5 0x04 0x02 P1−2 (RO) P5−4 P1−5 P5−0 Read virtual address 4 1 0 10 0x00 P0−1 (RO) P1−6 3 1 1 D 4 0x77FF (for process 1) 2 1 1 4 1 0 1 B 0x77FF / 0x800 = 0xE 0 0 1 5 (0x7FF remainder) Paging Disk 0 P0−D page 0xE ⇒ frame 0x11 4 P1−3 (RO) P0−1(RO) P0−8 P0−E P0−B = physical address 8 P1−0 (RO) P1−E P1−1 (RO) C P0−5 P0−3(RO) 0x8FFF P1−F P0−F 10 P1−7 P2−0 (RO) 13 / 41  Page Table Main Memory Example #3: V RO D U Page Frame Disk Addr F 0 0 C 0x16 P0−2 (RO) Given a page offset of E 1 0 11 6 0x14 P0−6 P2−0 D 0 0x12 P4−2 11 bits (11 wires of bus C 0 0x10 P1−4 P1−E B 0 0x0E PA−0 used for off-set) A 0 0x0C P0−A P1−3 (RO) 211 = 0x800 9 8 0 0 0x0A P5−1 0x08 P0−C PA−A P2−1 7 0 0 11 0x06 P0−4 P5−F Read virtual address 6 5 1 0 1 0 1 5 0x04 0x02 P1−2 (RO) P5−4 P1−5 P5−0 0x77FF (for process 1) 4 1 0 10 0x00 P0−1 (RO) P1−6 3 1 1 D 4 2 1 1 4 1 0 1 B 0x77FF / 0x800 = 0x0E 0 0 1 5 (0x7FF remainder) page 0xE ⇒ frame 0x11 Paging Disk 0 P0−D 0x11 × 0x800 = 4 P1−3 (RO) P0−1(RO) P0−8 P0−E P0−B 0x8800 + 0x7FF 8 P1−0 (RO) P1−E P1−1 (RO) C P0−5 P0−3(RO) = physical address P1−F P0−F 10 0x8FFF P1−7 P2−0 (RO) 14 / 41 Example #4: Given a page offset of 11 bits Page Table Main Memory V RO D U Page Frame Disk Addr Read virtual address F E 0 0 1 0 11 C 6 0x16 0x14 P0−6 P0−2 (RO) P2−0 0x072E (for process 1) D C 0 0 0x12 0x10 P1−4 P4−2 P1−E 0x072E / 0x800 = 0 B A 0 0 0x0E PA−0 0x0C P0−A P1−3 (RO) (72E remainder) 9 0 0x0A P5−1 PA−A 8 0 0x08 P0−C P2−1 page 0x0 ⇒ page not 7 0 0 11 0x06 P0−4 P5−F 6 1 0 1 0x04 P1−2 (RO) P1−5 in memory 5 1 0 5 0x02 P5−4 P5−0 4 1 0 10 0x00 P0−1 (RO) P1−6 3 1 1 D 4 page fault 2 1 1 0 1 1 4 B page is on the paging 0 0 1 5 disk Paging Disk we schedule a read to 0 P0−D P0−E place the page in an 4 P1−3 (RO) P0−1(RO) P0−8 P0−B 8 P1−0 (RO) P1−E empty frame (let’s say C P0−5 P0−3(RO) P1−1 (RO) P1−F 0x16) 10 P0−F when I/O completes, we P1−7 P2−0 (RO) restart MMU access... 15 / 41  Page Table Main Memory V RO D U Page Frame Disk Addr Example #4b: F 0 0 C 0x16 P1−0 (RO) P0−2 (RO) Given a page offset of E D 1 0 0 11 6 0x14 P0−6 0x12 P2−0 P4−2 11 bits C B 0 0 0x10 P1−4 0x0E PA−0 P1−E Read virtual address A 0 0x0C P0−A P1−3 (RO) 9 0 0x0A P5−1 PA−A 0x072E (for process 1) 8 0 0x08 P0−C P2−1 7 0 0 11 0x06 P0−4 P5−F 0x072E / 0x800 = 0 6 1 0 1 0x04 P1−2 (RO) P1−5 5 1 0 5 0x02 P5−4 P5−0 (72E remainder) 4 1 0 10 0x00 P0−1 (RO) P1−6 3 1 1 D 4 page 0x0 (now in 2 1 1 4 memory) 1 0 0 1 1 1 16 B 5 page 0x0 ⇒ frame 0x16 Paging Disk 0 0x16 × 0x800 = 4 P0−D P0−1(RO) P0−8 P0−E P1−3 (RO) P0−B 0xB800 + 0x72E 8 P1−0 (RO) P1−E P1−1 (RO) = physical address C P1−F P0−5 P0−3(RO) P0−F 10 0xB72E P1−7 P2−0 (RO) 16 / 41 Page Fault Handling 1 IF address invalid ⇒ terminate process 2 ELSE IF page frame in process allocation is empty ⇒ use this frame 3 ELSE choose page to be replaced IF page is modified ⇒ save page on disk 4 IF required page is saved on paging area ⇒ read in from disk paging area 5 ELSE IF required page is a text page or an initialized data page ⇒ read in from executable program file 6 ELSE initialize page to zeros (for security) 7 set up page table to point to the new page 8 mark process RUNNABLE 17 / 41 Page Fault Timeline If address mapping in process X causes page fault: process X cannot be run – BLOCKED on I/O waiting for needed page to be loaded into page frame + possibly other steps other processes (Y, Z... ) may be run if RUNNABLE if no RUNNABLE process, system is idle all processes are waiting on I/O (no matter what), fault causes major interruption in runtime of process X equivalent to thousands of instructions.˙. worthwhile to spend some processor effort trying to manage and decrease the number of page faults 18 / 41 Paged Virtual Memory Paged Virtual Memory depends on the locality principle: a large program only uses a small portion of its virtual address space at a given time. The set of pages that make up this portion is called the working set The pages that are allocated page frames in physical memory is called the resident set. 19 / 41  ∗ ∗ Silberschatz et al, Operating System Concepts, 8th ed. John Wiley & Sons. Fig 9.19, pp. 388. 20 / 41 Page Replacement Policy A page replacement policy decides which page frames to replace The ideal page replacement policy would achieve: resident set ≡ working set To evaluate a page replacement policy, you must calculate its page fault rate for the page reference strings of real programs. 21 / 41 Page Replacement Policies Belady’s Optimal Replacement replaces the page that occurs furthest ahead in the reference string FIFO replace the page resident the longest LFU (Least Frequently Used) replace the page that has been referenced the fewest times LRU (Least Recently Used) replace the page that whose last reference is the furthest in the past 22 / 41 Use Bit A use bit is a hardware bit that is set when a page is referenced, which is reset by a software process. If the bit is clear, this means that the (page) has not been referenced since the software cleared it. The bit will be set to 1 when the hardware accesses the (page). The page replacement algorithm becomes: at regular time intervals, clear all reference bits replace a page that has a clear (i.e.; unset, 0) reference bit. This is a crude approximation of LRU. Similar to the dirty bit, which is set whenever a page is modified. 23 / 41 Page Replacement Example #1: FIFO If 64-bit machine with 64 kilobytes of RAM has a page size of 512 bytes, and the following page reference string is observed for a running program where ▽ indicates the use bit has been cleared: ▽ ABCD ABE▽ABCD EBCFBB▽BCDE F Q: How many page faults would occur using FIFO with 3 page frames? Frame 0 Frame 1 Frame 2 A B  C  D A B FIFO(3) = 15    E C  D  B F  C  D E F 24 / 41 Page Replacement Example #2: Belady’s If 64-bit machine with 64 kilobytes of RAM has a page size of 512 bytes, and the following page reference string is observed for a running program where ▽ indicates the use bit has been cleared: ▽ ABCD ABE▽ABCD EBCFBB▽BCDE F Q: How many page faults would occur using Belady’s Optimal Algorithm with 3 page frames and falling back to FIFO to break any ties? Frame 0 Frame 1 Frame 2 A  B  C  C D D Belady’s(3) = 11   D  E  F C  E 25 / 41 Page Replacement Example #3: bigger Belady’s If 64-bit machine with 64 kilobytes of RAM has a page size of 512 bytes, and the following page reference string is observed for a running program where ▽ indicates the use bit has been cleared: ▽ ABCD ABE▽ABCD EBCFBB▽BCDE F Q: How many page faults would occur using Belady’s Optimal Algorithm with 4 page frames and falling back to FIFO to break any ties? F0 F1 F2 F3 A B C D Belady’s(4) = 8    D E E F 26 / 41 Page Replacement Example #4: LFU ▽ ▽ ABCD ABE ABCD EBCFBB▽BCDE F Q: How many page faults would occur using LFU with 4 page frames and falling back to FIFO to break any ties? F0 F1 F2 F3 counts:............. A B C  D  E C  LFU(4) = 13 D  E  C F  D  E  F 27 / 41 Page Replacement Example #5: LRU ▽ ▽ ABCD ABE ABCD EBCFBB▽BCDE F Q: How many page faults would occur using LRU with 3 page frames and falling back to FIFO to break any ties? F0 F1 F2 F3 A  B  C  D  E F E C LRU(4) = 12   D D  F  E 28 / 41 Clock Algorithm Simple: Frame 0 read+clear use bits 9 1 use first clear page found 8 2 Enhanced: 7 3 (use, dirty) (0,0) – best 6 4 (0,1) – write to store (1,0) – probably needed 5 (1,1) – worst use first page found in lowest non-empty class may require several sweeps 29 / 41 Global versus Local Paging Policies Selection for replacement: a global page replacement policy (a.k.a. a paging policy) is applied to all pages versus a local page replacement policy is applied to pages for that process only Allocation: a fixed size partition policy uses a fixed frame allocation for each process a variable partition policy varies the frame allocation for each process. 30 / 41 Variable Partition Policies An algorithm may adjust the page frame allocation based on the observed page fault rate. IF fault rate is High for a process, increase frame allocation by quite a bit *** ELSE IF fault rate is Low, decrease frame allocation a little *** possibly even multiplicative or exponential instead of linear 31 / 41  Frames -vs- Faults : Memory -vs- Time 16 14 12 Number of Page Faults 10 8 6 4 2 0 0 1 2 3 4 5 6 Number of Page Frames † † Silberschatz et al, Operating System Concepts, 8th ed. John Wiley & Sons. Fig 9.11, pp. 373. 32 / 41  Memory -vs- Time 30000 Time taken for task (kernel build) HDD light on continuously 25000 20000 Time (s) 15000 10000 5000 0 4 8 Memory (MB) 33 / 41  Memory -vs- Time 90000 Time taken for task (kernel build) HDD light on continuously 80000 70000 60000 Time (s) 50000 40000 30000 20000 10000 0 0 8 16 32 64 128 256 Memory (MB) 34 / 41 Swapping: transferring page_size blocks of memory data between memory ⇔ disk transferring entire segments of processes between memory ⇔ Performance Degratation High disk No Swapping swapping is a (1/Time) desperation effort Swapping which attempts to provide a graceful (i.e.; linear) degradation of 0 0 High performance Total Memory Requirements 35 / 41 Unix-Style Process Virtual Address Space 0xFFFFFFFF Stack for a read-write page, a separate copy of each page must be kept for each other processes process, however the duplication can be shared with delayed until a process modifies each Data Segment Dynamic Data page (this is known as copy on write), Shared BSS Data unless it is a shared segment Symbols Static Data for a read-only segment, only 1 copy of each page must be in physical memory Segment for all processes Text Text (machine code) 0x00000000 36 / 41 Adjusting the Address Space There are two segments that may change size: Stack : adjusted through (function) call Data : adjusted when malloc(), new + co. are called kernel routines to do this: brk(void *endp) sets end of data segment to absolute (virtual) address endp sbrk(int incr) increments data segment size by incr bytes (decrements if incr negative) (Version 7 AT&T Unix – not POSIX, nor ANSI) 37 / 41 Dynamic Allocation (Segmentation) There are several algorithms popular for (re-)allocation: First Fit use first space found which is large enough 111111 000000 000000 111111 000000 111111 space − size ≥ 0 111111 000000 000000 111111 000000 111111 Best Fit use space found whose leftover 000000 111111 space is smallest 000000 111111 000000 111111 min space − size ≥ 0 111111 000000 000000 111111 000000 111111 Worst Fit use space found whose leftover space is largest 111111 000000 000000 111111 000000 111111 max space − size ≥ 0 Knuth Buddy System complicated and unpopular, but used in Linux 38 / 41 Memory Caches similar to a paging system implemented entirely in hardware Cache Memory memory 111111 000000 000000 111111 tag line 0 access to lines 3, 111111 000000 000000 111111 111111 000000 000000 111111 3 7, 2, 8, 1, 9, 4 ⇒ 000000 111111 1 000000 111111 000000 111111 000000 111111 7 cache hits 000000 111111 2 000000 111111 000000 111111 1111 0000 2 000000 111111 000000 111111 3 111111 000000 000000 111111 access to lines 5, 000000 111111 000000 111111 00000 11111 8 000000 111111 000000 111111 4 00000000000 11111111111 6, 10 ⇒ cache 00000000000 11111111111 00000 11111 111 000 111111 000000 1 5 00000000000 11111111111 miss 1111 0000 000 111 000000 111111 9 6 the tags are the 000000 111111 4 7 000000 111111 000000 111111 page table 000 111 000000 111111 8 entries and the 9 A 000 111 00000000000 11111111111 00000000000 11111111111 lines are the pages 39 / 41 Memory Hierarchy Level 2 (L2) cache tags lines (usually associative) L1 cache MMU CPU (TLB) usually within the CPU, the direct mapped Level-1 (L1) cache records a small number of recent cache lines, supplied RAM from the L2 cache Main Paging Disk Memory in general, the (direct mapped further from the via block #) (always CPU storage is, the direct larger, slower and mapped) cheaper it is. 40 / 41 Hierarchical Page Table Virtual Address l bits m bits n bits p q o page directory table page table itself is large p t + page table ’t’ each 2nd order q page table is 1 f page in size f o allows us to page physical address out parts of the page table we are not using 41 / 41