Memory Management - hochan222/Everything-in-JavaScript GitHub Wiki

๋ฐ”๋กœ๊ฐ€๊ธฐ
๋ฐ”๋กœ๊ฐ€๊ธฐ
๋ฐ”๋กœ๊ฐ€๊ธฐ
๋ฐ”๋กœ๊ฐ€๊ธฐ

Logical vs Physical Address

  • Logical address (=virtual address)
    • ํ”„๋กœ์„ธ์Šค๋งˆ๋‹ค ๋…๋ฆฝ์ ์œผ๋กœ ๊ฐ€์ง€๋Š” ์ฃผ์†Œ ๊ณต๊ฐ„
    • ๊ฐ ํ”„๋กœ์„ธ์Šค๋งˆ๋‹ค 0๋ฒˆ์ง€๋ถ€ํ„ฐ ์‹œ์ž‘
    • CPU๊ฐ€ ๋ณด๋Š” ์ฃผ์†Œ๋Š” logical address์ž„
  • Physical address
    • ๋ฉ”๋ชจ๋ฆฌ์— ์‹ค์ œ ์˜ฌ๋ผ๊ฐ€๋Š” ์œ„์น˜

์ฃผ์†Œ ๋ฐ”์ธ๋”ฉ: ์ฃผ์†Œ๋ฅผ ๊ฒฐ์ •ํ•˜๋Š” ๊ฒƒ
Symbolic Address -> Logical Address -> Physical Address

์ฃผ์†Œ ๋ฐ”์ธ๋”ฉ

  • Complie time binding
    • ๋ฌผ๋ฆฌ์  ๋ฉ”๋ชจ๋ฆฌ ์ฃผ์†Œ๊ฐ€ ์ปดํŒŒ์ผ ์‹œ ์•Œ๋ ค์ง
    • ์‹œ์ž‘ ์œ„์น˜ ๋ณ€๊ฒฝ์‹œ ์žฌ์ปดํŒŒ์ผ
    • ์ปดํŒŒ์ผ๋Ÿฌ๋Š” ์ ˆ๋Œ€์ฝ”๋“œ ์ƒ์„ฑ
  • Load time binding
    • Loader์˜ ์ฑ…์ž„ํ•˜์— ๋ฌผ๋ฆฌ์  ๋ฉ”๋ชจ๋ฆฌ ์ฃผ์†Œ ๋ถ€์—ฌ
    • ์ปดํŒŒ์ผ๋Ÿฌ๊ฐ€ ์žฌ๋ฐฐ์น˜๊ฐ€๋Šฅ ์ฝ”๋“œ๋ฅผ ์ƒ์„ฑํ•œ ๊ฒฝ์šฐ ๊ฐ€๋Šฅ
  • Execution time binding (=Run time binding)
    • ์ˆ˜ํ–‰์ด ์‹œ์ž‘๋œ ์ดํ›„์—๋„ ํ”„๋กœ์„ธ์Šค์˜ ๋ฉ”๋ชจ๋ฆฌ ์ƒ ์œ„์น˜๋ฅผ ์˜ฎ๊ธธ ์ˆ˜ ์žˆ์Œ
    • CPU๊ฐ€ ์ฃผ์†Œ๋ฅผ ์ฐธ์กฐํ•  ๋•Œ๋งˆ๋‹ค binding์„ ์ ๊ฒ€

Memory-Management Unit (MMU)

  • MMU (Memory-Management Unit)
    • logical address๋ฅผ physical address๋กœ ๋งคํ•‘ํ•ด ์ฃผ๋Š” Hardware device
  • MMU scheme
    • ์‚ฌ์šฉ์ž ํ”„๋กœ์„ธ์Šค๊ฐ€ CPU์—์„œ ์ˆ˜ํ–‰๋˜๋ฉฐ ์ƒ์„ฑํ•ด๋‚ด๋Š” ๋ชจ๋“  ์ฃผ์†Œ๊ฐ’์— ๋Œ€ํ•ด base register์˜ ๊ฐ’์„ ๋”ํ•œ๋‹ค.
  • user program
    • logical address๋งŒ์„ ๋‹ค๋ฃฌ๋‹ค
    • ์‹ค์ œ physical address๋ฅผ ๋ณผ ์ˆ˜ ์—†์œผ๋ฉฐ ์•Œ ํ•„์š”๊ฐ€ ์—†๋‹ค.

Dynamic Loading

  • ํ”„๋กœ์„ธ์Šค ์ „์ฒด๋ฅผ ๋ฉ”๋ชจ๋ฆฌ์— ๋ฏธ๋ฆฌ ๋‹ค ์˜ฌ๋ฆฌ๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ ํ•ด๋‹น ๋ฃจํ‹ด์ด ๋ถˆ๋ ค์งˆ ๋•Œ ๋ฉ”๋ชจ๋ฆฌ์— loadํ•˜๋Š” ๊ฒƒ
  • memory utilization์˜ ํ–ฅ์ƒ
  • ๊ฐ€๋”์”ฉ ์‚ฌ์šฉ๋˜๋Š” ๋งŽ์€ ์–‘์˜ ์ฝ”๋“œ์˜ ๊ฒฝ์šฐ ์œ ์šฉ
  • ์šด์˜์ฒด์ œ์˜ ํŠน๋ณ„ํ•œ ์ง€์›์—†์ด ํ”„๋กœ๊ทธ๋žจ ์ž์ฒด์—์„œ ๊ตฌํ˜„ ๊ฐ€๋Šฅ (OS๋Š” ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ํ†ตํ•ด ์ง€์› ๊ฐ€๋Šฅ)

Loading: ๋ฉ”๋ชจ๋ฆฌ๋กœ ์˜ฌ๋ฆฌ๋Š” ๊ฒƒ

Overlays

  • ๋ฉ”๋ชจ๋ฆฌ์— ํ”„๋กœ์„ธ์Šค์˜ ๋ถ€๋ถ„ ์ค‘ ์‹ค์ œ ํ•„์š”ํ•œ ์ •๋ณด๋งŒ์„ ์˜ฌ๋ฆผ
  • ํ”„๋กœ์„ธ์Šค์˜ ํฌ๊ธฐ๊ฐ€ ๋ฉ”๋ชจ๋ฆฌ๋ณด๋‹ค ํด ๋•Œ ์œ ์šฉ
  • ์šด์˜์ฒด์ œ์˜ ์ง€์›์—†์ด ์‚ฌ์šฉ์ž์— ์˜ํ•ด ๊ตฌํ˜„
  • ์ž‘์€ ๊ณต๊ฐ„์˜ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•˜๋˜ ์ดˆ์ฐฝ๊ธฐ ์‹œ์Šคํ…œ์—์„œ ์ˆ˜์ž‘์—…์œผ๋กœ ํ”„๋กœ๊ทธ๋ž˜๋จธ๊ฐ€ ๊ตฌํ˜„
    • "Manual Overlay"
    • ์šด์˜์ฒด์ œ ์ง€์›์—†์Œ
    • ํ”„๋กœ๊ทธ๋ž˜๋ฐ์ด ๋งค์šฐ ๋ณต์žก

Swapping

  • Swapping
    • ํ”„๋กœ์„ธ์Šค๋ฅผ ์ผ์‹œ์ ์œผ๋กœ ๋ฉ”๋ชจ๋ฆฌ์—์„œ backing store๋กœ ์ซ“์•„๋‚ด๋Š” ๊ฒƒ
  • Backing store (=swap area)
    • ๋””์Šคํฌ
      • ๋งŽ์€ ์‚ฌ์šฉ์ž์˜ ํ”„๋กœ์„ธ์Šค ์ด๋ฏธ์ง€๋ฅผ ๋‹ด์„ ๋งŒํผ ์ถฉ๋ถ„ํžˆ ๋น ๋ฅด๊ณ  ํฐ ์ €์žฅ ๊ณต๊ฐ„
  • Swap in / Swap out
    • ์ผ๋ฐ˜์ ์œผ๋กœ ์ค‘๊ธฐ ์Šค์ผ€์ค„๋Ÿฌ(swapper)์— ์˜ํ•ด swap out์‹œํ‚ฌ ํ”„๋กœ์„ธ์Šค ์„ ์ •
    • priority-based CPU scheduling algorithm
      • priority๊ฐ€ ๋‚ฎ์€ ํ”„๋กœ์„ธ์Šค๋ฅผ swapped out ์‹œํ‚ด
      • priority๊ฐ€ ๋†’์€ ํ”„๋กœ์„ธ์Šค๋ฅผ ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ ค ๋†“์Œ
    • Compile time ํ˜น์€ load time binding์—์„œ๋Š” ์›๋ž˜ ๋ฉ”๋ชจ๋ฆฌ ์œ„์น˜๋กœ swap in ํ•ด์•ผํ•จ
    • Execution time binding์—์„œ๋Š” ์ถ”ํ›„ ๋นˆ ๋ฉ”๋ชจ๋ฆฌ ์˜์—ญ ์•„๋ฌด ๊ณณ์—๋‚˜ ์˜ฌ๋ฆด ์ˆ˜ ์žˆ์Œ
    • swap time์€ ๋Œ€๋ถ€๋ถ„ transfer time(swap๋˜๋Š” ์–‘์— ๋น„๋ก€ํ•˜๋Š” ์‹œ๊ฐ„)์ž„

Dynamic Linking

  • Linking์„ ์‹คํ–‰ ์‹œ๊ฐ„ (execution time)๊นŒ์ง€ ๋ฏธ๋ฃจ๋Š” ๊ธฐ๋ฒ•
  • Static linking
    • ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๊ฐ€ ํ”„๋กœ๊ทธ๋žจ์˜ ์‹คํ–‰ ํŒŒ์ผ ์ฝ”๋“œ์— ํฌํ•จ๋จ
    • ์‹คํ–‰ ํŒŒ์ผ์˜ ํฌ๊ธฐ๊ฐ€ ์ปค์ง
    • ๋™์ผํ•œ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ๊ฐ๊ฐ์˜ ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ฆฌ๋ฏ€๋กœ ๋ฉ”๋ชจ๋ฆฌ ๋‚ญ๋น„ (eg. printfํ•จ์ˆ˜์˜ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ ์ฝ”๋“œ)
  • Dynamic linking
    • ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๊ฐ€ ์‹คํ–‰์‹œ ์—ฐ๊ฒฐ๋จ
    • ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ ํ˜ธ์ถœ ๋ถ€๋ถ„์— ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ ๋ฃจํ‹ด์˜ ์œ„์น˜๋ฅผ ์ฐพ๊ธฐ์œ„ํ•œ stub์ด๋ผ๋Š” ์ž‘์€ ์ฝ”๋“œ๋ฅผ ๋‘ 
    • ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๊ฐ€ ์ด๋ฏธ ๋ฉ”๋ชจ๋ฆฌ์— ์žˆ์œผ๋ฉด ๊ทธ ๋ฃจํ‹ด์˜ ์ฃผ์†Œ๋กœ ๊ฐ€๊ณ  ์—†์œผ๋ฉด ๋””์Šคํฌ์—์„œ ์ฝ์–ด์˜ด
    • ์šด์˜์ฒด์ œ์˜ ๋„์›€์ด ํ•„์š”

Allocation of Physical Memory

  • ๋ฉ”๋ชจ๋ฆฌ๋Š” ์ผ๋ฐ˜์ ์œผ๋กœ ๋‘ ์˜์—ญ์œผ๋กœ ๋‚˜๋‰˜์–ด ์‚ฌ์šฉ
    • OS ์ƒ์ฃผ ์˜์—ญ
      • interrupt vector์™€ ํ•จ๊ป˜ ๋‚ฎ์€ ์ฃผ์†Œ ์˜์—ญ ์‚ฌ์šฉ
    • ์‚ฌ์šฉ์ž ํ”„๋กœ์„ธ์Šค ์˜์—ญ
      • ๋†’์€ ์ฃผ์†Œ ์˜์—ญ ์‚ฌ์šฉ
  • ์‚ฌ์šฉ์ž ํ”„๋กœ์„ธ์Šค ์˜์—ญ์˜ ํ• ๋‹น ๋ฐฉ๋ฒ•
    • Contiguous allocation
      • ๊ฐ๊ฐ์˜ ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋ฉ”๋ชจ๋ฆฌ์˜ ์—ฐ์†์ ์ธ ๊ณต๊ฐ„์— ์ ์žฌ๋˜๋„๋ก ํ•˜๋Š”๊ฒƒ
      • ๊ณ ์ • ๋ถ„ํ•  ๋ฐฉ์‹, ๊ฐ€๋ณ€ ๋ถ„ํ•  ๋ฐฉ์‹
    • Noncontiguous allocation
      • ํ•˜๋‚˜์˜ ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋ฉ”๋ชจ๋ฆฌ์˜ ์—ฌ๋Ÿฌ ์˜์—ญ์— ๋ถ„์‚ฐ๋˜์–ด ์˜ฌ๋ผ๊ฐˆ ์ˆ˜ ์žˆ์Œ
      • Paging
      • Segmentation
      • Paged Segmentation

Contiguous Allocation

  • Dynamic Storage-Allocation Problem

    • ๊ฐ€๋ณ€ ๋ถ„ํ•  ๋ฐฉ์‹์—์„œ size n ์ธ ์š”์ฒญ์„ ๋งŒ์กฑํ•˜๋Š” ๊ฐ€์žฅ ์ ์ ˆํ•œ hole์„ ์ฐพ๋Š” ๋ฌธ์ œ
  • First-fit

    • Size๊ฐ€ n ์ด์ƒ์ธ ๊ฒƒ ์ค‘ ์ตœ์ดˆ๋กœ ์ฐพ์•„์ง€๋Š” hole์— ํ• ๋‹น
  • Best-fit

    • Size๊ฐ€ n ์ด์ƒ์ธ ๊ฐ€์žฅ ์ž‘์€ hole์„ ์ฐพ์•„์„œ ํ• ๋‹น
    • Hole๋“ค์˜ ๋ฆฌ์ŠคํŠธ๊ฐ€ ํฌ๊ธฐ์ˆœ์œผ๋กœ ์ •๋ ฌ๋˜์ง€ ์•Š์€ ๊ฒฝ์šฐ ๋ชจ๋“  hole์˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ํƒ์ƒ‰ ํ•ด์•ผํ•จ
    • ๋งŽ์€ ์ˆ˜์˜ ์•„์ฃผ ์ž‘์€ hole๋“ค์ด ์ƒ์„ฑ๋จ
  • Worst-fit

    • ๊ฐ€์žฅ ํฐ hole์— ํ• ๋‹น
    • ์—ญ์‹œ ๋ชจ๋“  ๋ฆฌ์ŠคํŠธ๋ฅผ ํƒ์ƒ‰ํ•ด์•ผ ํ•จ
    • ์ƒ๋Œ€์ ์œผ๋กœ ์•„์ฃผ ํฐ hole๋“ค์ด ์ƒ์„ฑ๋จ

First-fit๊ณผ best-fit์ด worst-fit๋ณด๋‹ค ์†๋„์™€ ๊ณต๊ฐ„ ์ด์šฉ๋ฅ  ์ธก๋ฉด์—์„œ ํšจ๊ณผ์ ์ธ ๊ฒƒ์œผ๋กœ ์•Œ๋ ค์ง. (์‹คํ—˜์ ์ธ ๊ฒฐ๊ณผ)

  • Compaction

    • external fragmentation ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ํ•œ๊ฐ€์ง€ ๋ฐฉ๋ฒ•
    • ์‚ฌ์šฉ ์ค‘์ธ ๋ฉ”๋ชจ๋ฆฌ ์˜์—ญ์„ ํ•œ๊ตฐ๋ฐ๋กœ ๋ชฐ๊ณ  hole๋“ค์„ ๋‹ค๋ฅธ ํ•œ ๊ณณ์œผ๋กœ ๋ชฐ์•„ ํฐ block์„ ๋งŒ๋“œ๋Š” ๊ฒƒ
    • ๋งค์šฐ ๋น„์šฉ์ด ๋งŽ์ด ๋“œ๋Š” ๋ฐฉ๋ฒ•์ž„
    • ์ตœ์†Œํ•œ์˜ ๋ฉ”๋ชจ๋ฆฌ ์ด๋™์œผ๋กœ compactionํ•˜๋Š” ๋ฐฉ๋ฒ•(๋งค์šฐ ๋ณต์žกํ•œ ๋ฌธ์ œ)
    • Compaction์€ ํ”„๋กœ์„ธ์Šค์˜ ์ฃผ์†Œ๊ฐ€ ์‹คํ–‰ ์‹œ๊ฐ„์— ๋™์ ์œผ๋กœ ์žฌ๋ฐฐ์น˜ ๊ฐ€๋Šฅํ•œ ๊ฒฝ์šฐ์—๋งŒ ์‹คํ–‰๋  ์ˆ˜ ์žˆ๋‹ค.
  • Paging

    • Process์˜ virtual memory๋ฅผ ๋™์ผํ•œ ์‚ฌ์ด์ฆˆ์˜ page ๋‹จ์œ„๋กœ ๋‚˜๋ˆ”
    • Virtual memory์˜ ๋‚ด์šฉ์ด page ๋‹จ์œ„๋กœ noncontiguousํ•˜๊ฒŒ ์ €์žฅ๋จ
    • ์ผ๋ถ€๋Š” backing storage์—, ์ผ๋ถ€๋Š” physical memory์— ์ €์žฅ
    • ํ”„๋กœ์„ธ์Šค๋งˆ๋‹ค TLB๋Š” ํ•˜๋‚˜์”ฉ ์žˆ์Œ ๋”ฐ๋ผ์„œ ๋‹ค๋ฅธ ํ”„๋กœ์„ธ์Šค ์‚ฌ์šฉํ•  ๋• flush ์‹œ์ผœ์•ผ๋Œ

Two-Level Page Table

  • ํ˜„๋Œ€์˜ ์ปดํ“จํ„ฐ๋Š” address space๊ฐ€ ๋งค์šฐ ํฐ ํ”„๋กœ๊ทธ๋žจ ์ง€์›
    • 32 bit address ์‚ฌ์šฉ์‹œ 2^32B(4G)์˜ ์ฃผ์†Œ ๊ณต๊ฐ„
      • page size๊ฐ€ 4k์‹œ 1m๊ฐœ์˜ page table entry ํ•„์š”

Multilevel Paging and Perfomance

  • Address space๊ฐ€ ๋” ์ปค์ง€๋ฉด ๋‹ค๋‹จ๊ณ„ ํŽ˜์ด์ง€ ํ…Œ์ด๋ธ” ํ•„์š”.
  • ๊ฐ ๋‹จ๊ณ„์˜ ํŽ˜์ด์ง€ ํ…Œ์ด๋ธ”์ด ๋ฉ”๋ชจ๋ฆฌ์— ์กด์žฌํ•˜๋ฏ€๋กœ logical address์˜ physical address ๋ณ€ํ™˜์— ๋” ๋งŽ์€ ๋ฉ”๋ชจ๋ฆฌ ์ ‘๊ทผ ํ•„์š”
  • TLB๋ฅผ ํ†ตํ•ด ๋ฉ”๋ชจ๋ฆฌ ์ ‘๊ทผ ์‹œ๊ฐ„์„ ์ค„์ผ ์ˆ˜ ์žˆ์Œ
  • 4๋‹จ๊ณ„ ํŽ˜์ด์ง€ ํ…Œ์ด๋ธ”์„ ์‚ฌ์šฉํ•˜๋Š” ๊ฒฝ์šฐ
    • ๋ฉ”๋ชจ๋ฆฌ ์ ‘๊ทผ ์‹œ๊ฐ„์ด 100ns, TLB ์ ‘๊ทผ ์‹œ๊ฐ„์ด 20ns์ด๊ณ 
    • TLB hit ratio๊ฐ€ 98%์ธ ๊ฒฝ์šฐ
    • effective memory access time = 128 nanoseconds
    • ๊ฒฐ๊ณผ์ ์œผ๋กœ ์ฃผ์†Œ ๋ณ€ํ™˜์„ ์œ„ํ•ด 28ns๋งŒ ์†Œ์š”

Valid(v) / Invalid(i) Bit in a Page Table

Segmentation

  • ํ”„๋กœ๊ทธ๋žจ์€ ์˜๋ฏธ ๋‹จ์œ„์ธ ์—ฌ๋Ÿฌ๊ฐœ์˜ segment๋กœ ๊ตฌ์„ฑ
  • Protection
    • valid bit
    • Read / Write / Execution ๊ถŒํ•œ bit
  • Sharing

์‹ค์ œ ์จ๋ณด๋ฉด segment ๊ฐœ์ˆ˜๋Š” page ๊ฐœ์ˆ˜์—๋น„ํ•ด ๋ช‡๊ฐœ ์•ˆ๋œ๋‹ค. ๋”ฐ๋ผ์„œ ๋‚ญ๋น„๊ฐ€ ์ ๋‹ค.

Segmentation with Paging