[OS] Virtual Memory

seunghyunยท2023๋…„ 5์›” 12์ผ
0

๐Ÿ’ป

๋ชฉ๋ก ๋ณด๊ธฐ
7/16

Introduction

๐Ÿ’ก Virtual Memory

  • Programmer's view of memory
  • Each process has its own virtual memory
  • A linear array of bytes addressed by the virtual address

โœ”๏ธ ๊ฐ€์ƒ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์™œ ์‚ฌ์šฉํ•˜๋Š”๊ฐ€?

  • ํŒŒํ‹ฐ์…˜ ํฌ๊ธฐ์— ๋”ฐ๋ผ overlay ์ˆ˜์ •์„ ํ•  ํ•„์š”์—†์ด OS๊ฐ€ ์ฑ…์ž„์ ธ์ค˜์„œ ํ”„๋กœ๊ทธ๋ž˜๋ฐ์„ ํ•˜๊ธฐ ์‰ฝ๋‹ค.
  • ๋‹ค ์˜ฌ๋ผ์˜ฌ ํ•„์š”์—†์ด ํ”„๋กœ์„ธ์Šค ์ด๋ฏธ์ง€์˜ ์ผ๋ถ€๋งŒ ์˜ฌ๋ผ์™€์„œ ์‹คํ–‰ํ•œ๋‹ค.
  • ๊ฐ€์ƒ ๋ฉ”๋ชจ๋ฆฌ๋Š” ์ถฉ๋ถ„ํžˆ ํฌ๊ฒŒ ์žกํ˜€์ ธ์žˆ์–ด์„œ ํ”„๋กœ๊ทธ๋ž˜๋จธ๋Š” ๋ฉ”๋ชจ๋ฆฌ๊ฐ€ (๊ฑฐ์˜) ๋ฌดํ•œํ•˜๋‹ค๊ณ  ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ๋‹ค.

๐Ÿ’ก Physical Memory

  • Machine's physical memory (DRAM)
    • Caches are parts of physical memory
  • Also called main memory

โœ”๏ธ Virtual address : The address of a program ๋ช…๋ น์–ด๋‚˜ ๋ฐ์ดํ„ฐ์˜ ์ฃผ์†Œ

โœ”๏ธ Physical address : The address of a DRAM

โœ”๏ธ Page table : OS ๊ฐ€ ๊ด€๋ฆฌํ•˜๋Š” ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ

โœ”๏ธ TLB (MMU) : Virtual page number ๋ฅผ Physical Page Number ๋กœ ๋ฐ”๊พธ๋Š” ๊ฒƒ์ด Translate ์ด๋ผ๊ณ  ํ•œ๋‹ค. Page table ์˜ entry ๋“ค์„ Caching ํ•œ ํ•˜๋“œ์›จ์–ด. ํŠน์ˆ˜ํ•œ entry ๋ฅผ ์ œ์™ธํ•˜๊ณ ๋Š” ๋Œ€๊ฐœ ์ปจํ…์ŠคํŠธ ์Šค์œ„์นญ๋  ๋•Œ๋งˆ๋‹ค flush ๋˜์–ด์•ผ ํ•œ๋‹ค. ์ด๊ฒƒ์ด ์—†๋‹ค๋ฉด ๋งค๋ฒˆ CPU ๊ฐ€ exception ์ด ๊ฑธ๋ ค์„œ OS ๊ฐ€ ์ฐพ์•„์™€์•ผํ•œ๋‹ค.. ๋„ˆ๋ฌด ๋А๋ ค์ง„๋‹ค!


Virtual Memory

Functions

  • Large address space
    • Easy to program
    • Provide the illusion of infinite amount of memory
    • Program (including both code and data) can exceed the main memory capacity
    • Processes partially resident in memory
  • Protection
    • Access rights: read modify/ execute permission
      • Each segment/page has its own access rights
    • Privilege level
  • Sharing
  • Portability
  • Increased CPU utilization
    • More programs can run at the same time

Require the following functions

  • Memory allocation (Placement)
    • Any virtual page can be placed in any page frame
  • Memory deallocation (Replacement)
    • LRU, Clock algorithm
  • Memory mapping (Translation)
    • Virtual address must be translated to physical address to access main memory and caches

memory management

  • Automatic movement of data between main memory and secondary storage
    • Done by OS with the help of processor HW (TLB)
    • Main memory contains only the most frequently used portions of a process's address space
  • Illusion of infinite memory(size of secondary storage) but access time is equal to main memory
  • Usually use demand paging (cache ๋Š” ๋ˆˆ์น˜๋น ๋ฅด๊ฒŒ PreFetching)
    • Bring a page on demand

Paging

  • Divide address space into fixed size pages

    • VA consists of VPN, offset
    • PA consists of PPN, offset
  • Map a virtual page to a physical page frame at runtime

  • Each process has its own page table

    • The page table contains mapping between VPN and PPN
    • VPN is used as an index into the page table
  • Page Table Entry(PTN) contains

    • PPN (Physical Page Number or Frame Number)
    • Presence bit : 1 if this page is in main memory
    • Modified bit : 1 if this page has been modified
    • Reference bits : reference statistics into used for page replacement
    • Access control : read/write/execute permissions
    • Privilege level : user-level page versus system-level page
    • Disk Address

Page table organization

  • Linear : one PTE per virtual page

  • Hierarchical : tree structured page table

    • Page Directory ๐Ÿ‘‰ Page Table ๐Ÿ‘‰ Virtual Memory
  • Inverted : PTEs for only pages in main memory ํ”„๋กœ์„ธ์Šค ์ˆ˜์— ์ƒ๊ด€์—†์ด ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ผ์™€์žˆ๋Š” ํŽ˜์ด์ง€์— ๋Œ€ํ•ด์„œ๋งŒ ๊ด€๋ฆฌํ•˜๊ฒ ๋‹ค. frame ์— ๋”ฐ๋ผ ๊ด€๋ฆฌํ•˜๊ฒ ๋‹ค.

    • Hashing ์œผ๋กœ ํŽ˜์ด์ง€์™€ ํ”„๋ ˆ์ž„์„ ์ง์ง€์–ด์ค€๋‹ค. Hash collision ์ด ๋‚˜๋ฉด chain ์œผ๋กœ ๊ทธ ๋‹ค์Œ ๊ฒƒ์„ ์—ฐ๊ฒฐํ•œ๋‹ค
  • Page table entries are dynamically allocated as needed

TLB (MMU; Memory Management Unit)

TLB ๋„ ์บ์‹œ์ด๋ฏ€๋กœ TLB miss, hit ์ด ์žˆ๋‹ค
์ด๊ฒƒ์ด CPU ๋‚ด์— ์žˆ์–ด์•ผ๋งŒ ๊ฐ€์ƒ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์ง€์›ํ•  ์ˆ˜ ์žˆ๋‹ค

โœ”๏ธ Translation Lookaside Buffer

  • Cache of page table entries (PTEs)
  • On TLB hit, can do virtual to physical translation without accessing the page table
  • On TLB miss (Exception), must search the page table for the missing entry

Page fault

๐Ÿ’ก But what happens if the process tries to access a page that was not brought into memory? Access to a page marked invalid causes a page fault.

The paging hardware, in translating the address through the page table, will notice that the invalid bit is set, causing a trap to the operating system. This trap is the result of the operating systemโ€™s failure to bring the desired page into memory. The procedure for handling this page fault is straightforward (Figure 10.5):

  1. We check an internal table (usually kept with the process control block) for this process to determine whether the reference was a valid or an invalid memory access.
  2. If the reference was invalid, we terminate the process. If it was valid but we have not yet brought in that page, we now page it in.
  3. We find a free frame (by taking one from the free-frame list, for example)
  4. We schedule a secondary storage operation to read the desired page into
    the newly allocated frame.
  5. When the storage read is complete, we modify the internal table kept with the process and the page table to indicate that the page is now in memory.
  6. We restart the instruction that was interrupted by the trap. The process can now access the page as though it had always been in memory.

Page Size

์ปค์ง€๋Š” ์ถ”์„ธ๋‹ค. ๊ฐ€์ ธ์˜ค๋Š” ์˜ค๋ฒ„ํ—ค๋“œ๋ฅผ ์ค„์ด๊ธฐ ์œ„ํ•ด์„œ.

  • The smaller the page size, the lesser the amount of internal fragmnentation
    • However, more pages are required per process
    • More pages per process means larger page tables
      • For large programs, portion of the page tables of active processes must be in secondary storage instead of main memory

Segmentation

โœ”๏ธ Segmentation allows a programmer to view a virtual memory as a collection of sgments

โœ”๏ธ Advantages

  • Simplify the handling of growing data structures
  • Facilitate sharing among processes

โœ”๏ธ Segment Table Entry Contains

  • Base address of the corresponding segment in main memory (DRAM ์—์„œ ์‹œ์ž‘ํ•˜๋Š” ์ฃผ์†Œ)
  • Length of the segment (๋ฒ”์œ„)
  • Presence bit - 1 if this segment is in main memory
  • Modified bit - 1 if this segment has been modified

Virtual Memory Policies

๐Ÿ’ก Key issues: Performance

  • Minimize page faults

Fetch Policy

โœ”๏ธ Demand paging

  • Bring a page into main memory only on a page miss
  • Generate 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 fault should drop to a very low level

โœ”๏ธ Prepaging

  • Pages other than the one demanded by a page fault are brought in
  • If pages of a process are stored contiquously in secondary memory it is more efficient to bring in a number of pages at one time
  • Ineffective if extra pages are not referenced

Frame Locking

โœ”๏ธ Frame Locking

  • When a frame is locked, the page currently stored in that frame should not be replaced
    • OS kernel and key control structures are locked
    • I/O buffers and time-critical areas may be locked
    • Locking is achieved by associating a lock bit with each frame

Replacement Algorithms

โœ”๏ธ Optimal

  • Select the page for which the time to the next reference is the longest

โœ”๏ธ LRU

  • Select the page that has not been referenced for the longest time

โœ”๏ธ FIFO

  • Page that has been in memory the longest is replaced

โœ”๏ธ Clock

  • Associate a use bit with each frames
  • When a page is first loaded or referenced, the use bit is set to
  • Any frame with a use bit of 1 is passed over by the algorithm
  • Page frames visualized as laid out in a circle

Page Buffering

โœ”๏ธ When a page is replaced, the page is not physically moved

  • Instead, the PTE for this page is removed and placed in either the free or modified page list
  • Free page list is a list of page frames available for reading in pages
    • When a page is to be replaced, it remains in memory and its page frame is added to the tail of the free page list
    • Thus, if the process reference the page, it is returned to the resident set of that process at little cost
    • When a page is to be read in, the page frame at the head of the list is used. destroying the page that was there
  • Modified page list is a list of page frames that have been modified
    • When a modified is replaced, the page frame is added to the tail of the modified page list
    • Modified pages are written out in clusters rather than one at a timer significantly reducing the number of I/O operation

Page Fault Frequency (PFF)

PF ๊ฐ€ ๋„ˆ๋ฌด ์ž์ฃผ ๋ฐœ์ƒํ•˜๋ฉด working set ์„ ๋Š˜๋ ค์ฃผ๊ณ  PF ๊ฐ€ ๋„ˆ๋ฌด ๊ฐ€๋” ๋ฐœ์ƒํ•˜๋ฉด working set ์„ ์ค„์—ฌ์ค€๋‹ค.

โœ”๏ธ Requires a use bit to be associated with each page in memory

  • Bit is set to 1 when that page is accessed
  • When a page fault occurs, the OS notes the virtual time since the last page fault for that process
  • If the amount of time since the last page fault is less than a threshold (์ž„๊ณ„์ ), then a page is added to the working set of the process
  • Otherwise, discard all pages with a use bit of 0, and shrink the working set accordingly. At the same time reset the use bit on the remaining pages
  • The strategy can be refined by using 2 thresholds: An upper threshold is used to trigger a growth in the working size while a lower threshold is used to trigger a shrink in the working set size

โœ”๏ธ Does not perform well during the transient periods when there is a shift to a new locality


Multiprogramming

process ์ˆ˜๊ฐ€ ๋„ˆ๋ฌด ๋งŽ๊ฑฐ๋‚˜ ์ ์œผ๋ฉด ๋ฌธ์ œ๋‹ค!

ํ•˜๋‚˜์˜ process ์ˆ˜๊ฐ€ ๋„ˆ๋ฌด ๋งŽ์œผ๋ฉด working set ์ด ์ค„์–ด๋“ ๋‹ค. ๐Ÿ‘‰ ํ•œ process ์•ˆ์—์„œ page fault ๊ฐ€ ๋ฐ˜๋ณต๋œ๋‹ค ๐Ÿ‘‰ thrashing

โœ”๏ธ Load Control

  • Determine the number of processes that will be resident in main memory
  • This number is called multiprogramming level

โœ”๏ธ Too few processes lead to swapping

  • Since all the processes can be blocked

โœ”๏ธ Too many processes, lead to insufficient working set size, resulting in thrashing (frequent faults)


Process Suspension

โœ”๏ธ If the degree of multiprogramming is to be reduced,

  • One or more of the currently resident processes must be swapped out

โœ”๏ธ Six Possibilities

  • Lowest-priority process
  • Faulting process
  • Last process activated
  • Process with the smallest working set
  • Largest process
  • Process with the largest remaining execution window

๐Ÿ”— Reference

[KUOCW] ์ตœ๋ฆฐ ๊ต์ˆ˜๋‹˜์˜ ์šด์˜์ฒด์ œ ๊ฐ•์˜๋ฅผ ์ˆ˜๊ฐ•ํ•˜๊ณ  ์ •๋ฆฌํ•œ ๋‚ด์šฉ์ž…๋‹ˆ๋‹ค. ์ž˜๋ชป๋œ ๋‚ด์šฉ์ด ์žˆ๋‹ค๋ฉด ๋Œ“๊ธ€๋กœ ์•Œ๋ ค์ฃผ์‹œ๋ฉด ๊ฐ์‚ฌํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค ๐Ÿ˜Š

profile
๐Ÿ‘ฉ๐Ÿปโ€๐Ÿ’ป๐ŸŽฎ

0๊ฐœ์˜ ๋Œ“๊ธ€