Split View: [운영체제] 09. 메인 메모리 관리

CPU <-> Registers (~1ns) <-> Cache (~10ns) <-> Main Memory (~100ns)

[Address Binding Timing]

1. Compile-time Binding
   - Memory location determined at compile time
   - Recompilation needed if location changes
   - Example: MS-DOS .COM programs

2. Load-time Binding
   - Address determined when loading program into memory
   - Uses relocatable code
   - Address cannot change after loading

3. Execution-time Binding (Modern OS)
   - Addresses dynamically translated during execution
   - Requires MMU (Memory Management Unit) hardware
   - Processes can be moved within memory

[Address Translation via MMU]

CPU --[Logical addr: 346]--> MMU --[Physical addr: 14346]--> Memory
                              |
                        Relocation Register
                        (base value: 14000)

Physical address = Logical address + Relocation register value
346 + 14000 = 14346

[Static Linking vs Dynamic Linking]

Static Linking:
  Program A: [code + libc copy]   -- 50MB
  Program B: [code + libc copy]   -- 50MB
  Total memory: 100MB

Dynamic Linking (Shared Libraries):
  Program A: [code + libc ref]    -- 10MB
  Program B: [code + libc ref]    -- 10MB
  libc.so:   [shared library]     -- 40MB
  Total memory: 60MB

Linux: .so files (Shared Object)
Windows: .dll files (Dynamic-Link Library)

[Base Register and Limit Register]

     Base                   Limit
        |                       |
        v                       v
+-------+=======================+-------+
| OS    | Process P's region    | Other |
+-------+=======================+-------+
  0     300040                 420940

For address addr generated by CPU:
  if (addr >= base && addr < base + limit)
      Access allowed -> Physical memory access
  else
      Trap raised -> OS handles error

[Memory Allocation Example]

Initial state:
|---OS---|--P1--|-------free-------|--P3--|---free---|

Allocation strategies:
1. First Fit: Allocate in the first sufficiently large hole
   Pros: Fast

2. Best Fit: Allocate in the smallest sufficient hole
   Pros: Creates small remaining space
   Cons: Full search needed, creates very small fragments

3. Worst Fit: Allocate in the largest hole
   Pros: Remaining space is large enough to reuse
   Cons: Full search needed

[External vs Internal Fragmentation]

External Fragmentation:
|P1|  free  |P2| free |P3|  free  |P4|
    100KB     50KB     80KB

Total free space: 230KB, but cannot load a 200KB process!
(Not contiguous)

Solution: Compaction - Move processes to one end
|P1|P2|P3|P4|-----230KB free-----|

Internal Fragmentation:
When memory is allocated in fixed-size blocks
If process is smaller than block, space is wasted inside

Process size: 18,462 bytes
Block size: 20,000 bytes
Internal fragmentation: 1,538 bytes wasted

[Paging Address Translation]

Logical address = Page number(p) + Page offset(d)

Example: Page size 4KB (2^12), 32-bit logical address
  Upper 20 bits = Page number (max 2^20 = 1M pages)
  Lower 12 bits = Offset (0 ~ 4095)

+--------+--------+
| p (20) | d (12) |       Logical address
+--------+--------+
     |
     v
[Page Table]
 p -> f (frame number)
     |
     v
+--------+--------+
| f (20) | d (12) |       Physical address
+--------+--------+

[Paging Example]

Logical Memory (4 pages):        Physical Memory (8 frames):
+------+                     +------+
|Page 0| ----+              |      | Frame 0
+------+     |              +------+
|Page 1| --+ |              |Page 2| Frame 1
+------+   | |              +------+
|Page 2| -+| |              |      | Frame 2
+------+  || |              +------+
|Page 3|  || +------------>|Page 0| Frame 3
+------+  ||                +------+
          |+--------------->|Page 1| Frame 4
          |                 +------+
          +---------------->|Page 2| Frame 5 (X)
                            +------+
                            |Page 3| Frame 6
                            +------+
                            |      | Frame 7
                            +------+

Page Table:
  Page 0 -> Frame 3
  Page 1 -> Frame 4
  Page 2 -> Frame 1
  Page 3 -> Frame 6

[Address Translation via TLB]

CPU --logical addr(p, d)--> TLB lookup
                              |
              +---------------+---------------+
              |                               |
          TLB Hit                         TLB Miss
          (fast, ~1ns)                    (slow)
              |                               |
          Get frame f                  Page table lookup
              |                        Get frame f
              |                        Add to TLB
              |                               |
              +---------------+---------------+
                              |
                   Access memory with
                   physical addr (f, d)

Effective Access Time (EAT) calculation:
  TLB hit rate = 99% (typical)
  Memory access time = 100ns
  TLB access time = 10ns

  EAT = 0.99 * (10 + 100) + 0.01 * (10 + 100 + 100)
      = 0.99 * 110 + 0.01 * 210
      = 108.9 + 2.1
      = 111ns

  Without TLB: 200ns (2 memory accesses)
  With TLB: 111ns (44.5% improvement)

[Two-level Page Table]

32-bit address, 4KB pages:
+--------+--------+--------+
| p1(10) | p2(10) | d(12)  |
+--------+--------+--------+

Outer Page Table (Level 1)
+---+
| 0 |---> Level 2 Table A
+---+      +---+
| 1 |--+   | 0 |--> Frame number
+---+  |   +---+
| 2 |  |   | 1 |--> Frame number
+---+  |   +---+
       |   | ...|
       |   +---+
       |
       +-> Level 2 Table B
           +---+
           | 0 |--> Frame number
           +---+
           | ...|
           +---+

Advantage: Level 2 tables for unused regions are not created
-> Memory savings

[Hashed Page Table]

Input logical page number p to hash function
-> Maps to hash table slot
-> Search chain (linked list) for p
-> Return corresponding frame number

Useful for very large address spaces like 64-bit

[Inverted Page Table]

Regular page table: One per process (logical -> physical)
Inverted page table: One for the system (physical frame -> process, page)

One entry for each physical memory frame:
Frame 0: (PID=5, Page=3)
Frame 1: (PID=2, Page=7)
Frame 2: (empty)
Frame 3: (PID=5, Page=0)
...

Advantage: Table size proportional to physical memory
Disadvantage: Full table search needed for translation (solved with hashing)

[Standard Swapping]

Main Memory                    Backing Store (Disk)
+---------+                   +---------+
|   OS    |                   |         |
+---------+                   |  P2's   |
|   P1    |  <-- swap in ---  |  image  |
+---------+                   |         |
|   P3    |  --- swap out --> |         |
+---------+                   +---------+
| free    |
+---------+

Modern systems swap at page granularity
rather than swapping entire processes

[Page-level Swapping]

Only specific pages of a process are moved to disk:
- Swap out pages not used for a long time
- Swap in again when needed
- Foundation technology for virtual memory

[Page Table Entry Structure]

+-------+-----+-----+-----+-------+
| Frame | Valid| Read| Write| Exec  |
| Number| Bit | OK  | OK   | OK    |
+-------+-----+-----+-----+-------+

Valid bit:
  1 = This page belongs to the process's logical address space
  0 = Invalid page (trap raised on access)

Protection bits:
  Write attempt on read-only page -> Hardware trap
  Code pages: Allow execute only, deny writes

// Memory protection example: mprotect system call
#include <sys/mman.h>
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>

void segfault_handler(int sig) {
    printf("Segmentation fault! Attempted access to protected memory\n");
    exit(1);
}

int main() {
    signal(SIGSEGV, segfault_handler);

    // Allocate memory in page-size units
    size_t page_size = getpagesize();  // Usually 4096
    void *ptr = aligned_alloc(page_size, page_size);

    // Write data
    *(int *)ptr = 42;
    printf("Value: %d\n", *(int *)ptr);

    // Protect memory as read-only
    mprotect(ptr, page_size, PROT_READ);

    // Write attempt -> Segmentation fault!
    *(int *)ptr = 100;

    free(ptr);
    return 0;
}