๐Ÿฆ• ๊ณต๋ฃก์ฑ…์œผ๋กœ ์ •๋ฆฌํ•˜๋Š” ์šด์˜์ฒด์ œ Ch.8

Memory-Management Strategies

๋ฉ”๋ชจ๋ฆฌ์— ๋กœ๋“œ๋œ ํ”„๋กœ์„ธ์Šค๋ฅผ ํšจ์œจ์ ์œผ๋กœ ๊ด€๋ฆฌํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ๋‹ค๋ฃจ๋Š” ์ฑ•ํ„ฐ๋กœ, ๋ณต์žกํ•œ ๋งค์ปค๋‹ˆ์ฆ˜๊ณผ ๊ณ„์‚ฐ์ด ๋‚˜์˜ค๊ธฐ ์‹œ์ž‘ํ•ด ์กฐ๊ธˆ ์–ด๋ ค์›Œ์ง€๋Š” ๋‹จ๊ณ„๋‹ค.

Background

Ch.1 Overview์—์„œ ์–ธ๊ธ‰ํ–ˆ๋“ฏ ๋ฉ”๋ชจ๋ฆฌ๋Š” ํ˜„๋Œ€ ์ปดํ“จํ„ฐ ์‹œ์Šคํ…œ์˜ ํ•ต์‹ฌ์ด๋‹ค. ํ”„๋กœ์„ธ์Šค๋Š” ๋…๋ฆฝ์ ์ธ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ์ฐจ์ง€ํ•˜๋ฉฐ, ์‹œ์Šคํ…œ์€ ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ž์‹ ์˜ ์˜์—ญ ์™ธ์—๋Š” ์ ‘๊ทผํ•  ์ˆ˜ ์—†๋„๋ก ๋ง‰์•„์•ผ ํ•œ๋‹ค.

Basic Hardware

CPU๋Š” ๋ ˆ์ง€์Šคํ„ฐ๋ฅผ ์ฐธ์กฐํ•˜๋ฉฐ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ๋ณดํ˜ธํ•˜๋ฉฐ, ๋ ˆ์ง€์Šคํ„ฐ ์ •๋ณด๋Š” PCB์— ๋‹ด๊ฒจ์žˆ๋‹ค. ์ด๋•Œ ๋ ˆ์ง€์Šคํ„ฐ๋Š” base์™€ limit์œผ๋กœ ๋‚˜๋‰œ๋‹ค. base๋Š” ๋ฉ”๋ชจ๋ฆฌ์˜ ๊ฐ€์žฅ ์ž‘์€ physical address๋ฅผ ์˜๋ฏธํ•˜๋ฉฐ, limit์€ ๊ฐ€์žฅ ํฐ physical address๋ฅผ ์˜๋ฏธํ•œ๋‹ค. ๋”ฐ๋ผ์„œ ์–ด๋–ค ํ”„๋กœ์„ธ์Šค์˜ base๊ฐ€ 300040์ด๊ณ , limit์ด 120900์ด๋ผ๋ฉด ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ๋Š” ๋ฉ”๋ชจ๋ฆฌ ์ฃผ์†Œ์˜ ๋ฒ”์œ„๋Š” 300040๋ถ€ํ„ฐ 120900๊นŒ์ง€์ธ ๊ฒƒ์ด๋‹ค.

Address Binding

์ผ๋ฐ˜์ ์œผ๋กœ ํ”„๋กœ๊ทธ๋žจ์€ ๋””์Šคํฌ์— binary executable ํŒŒ์ผ๋กœ ์ €์žฅ๋˜์–ด ์žˆ๋‹ค. ํ”„๋กœ๊ทธ๋žจ์„ ์‹คํ–‰ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋ฉ”๋ชจ๋ฆฌ์— ๋กœ๋“œํ•ด ํ”„๋กœ์„ธ์Šค๋กœ ๋งŒ๋“ค์–ด์•ผ ํ•œ๋‹ค. ์ด๋•Œ ๋””์Šคํฌ์—์„œ ๋ฉ”์ธ ๋ฉ”๋ชจ๋ฆฌ๋กœ ๋กœ๋“œ๋˜๊ธฐ๋ฅผ ๋Œ€๊ธฐํ•˜๋Š” ๊ณณ์ด input queue๋‹ค. ์šด์˜์ฒด์ œ๋Š” input queue์—์„œ ํ”„๋กœ์„ธ์Šค๋ฅผ ์„ ํƒํ•ด ๋ฉ”๋ชจ๋ฆฌ์— ๋กœ๋“œํ•œ๋‹ค.

๋ช…๋ น๊ณผ ๋ฐ์ดํ„ฐ๋ฅผ ๋ฉ”๋ชจ๋ฆฌ ์ฃผ์†Œ๋กœ bindingํ•˜๋Š” ์‹œ์ ์— binding์ด ๊ตฌ๋ถ„๋œ๋‹ค.

  • Compile time: ๋งŒ์•ฝ compile time์— ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋ฉ”๋ชจ๋ฆฌ์˜ ์–ด๋Š ์œ„์น˜์— ๋“ค์–ด๊ฐˆ์ง€ ๋ฏธ๋ฆฌ ์•Œ๊ณ  ์žˆ๋‹ค๋ฉด absolute codel๋ฅผ ์ƒ์„ฑํ•  ์ˆ˜ ์žˆ๋‹ค. ์œ„์น˜๊ฐ€ ๋ณ€๊ฒฝ๋œ๋‹ค๋ฉด ์ฝ”๋“œ๋ฅผ ๋‹ค์‹œ ์ปดํŒŒ์ผํ•ด์•ผ ํ•œ๋‹ค. MS-DOS .COM ํ˜•์‹ ํ”„๋กœ๊ทธ๋žจ์ด ์˜ˆ์‹œ๋‹ค.
  • Load time: ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋ฉ”๋ชจ๋ฆฌ์˜ ์–ด๋Š ์œ„์น˜์— ๋“ค์–ด๊ฐˆ์ง€ ๋ฏธ๋ฆฌ ์•Œ ์ˆ˜ ์—†๋‹ค๋ฉด ์ปดํŒŒ์ผ๋Ÿฌ๋Š” relocatable code๋ฅผ ๋งŒ๋“ค์–ด์•ผ ํ•œ๋‹ค. ์ด ๊ฒฝ์šฐ ์ตœ์ข… ๋ฐ”์ธ๋”ฉ์€ ๋กœ๋“œ์˜ ์†Œ์š” ์‹œ๊ฐ„๋งŒํผ ์ง€์—ฐ๋  ์ˆ˜ ์žˆ๋‹ค.
  • Execution time: ํ”„๋กœ์„ธ์Šค๊ฐ€ ์‹คํ–‰ ์ค‘ ๋ฉ”๋ชจ๋ฆฌ์˜ ํ•œ ์„ธ๊ทธ๋จผํŠธ์—์„œ ๋‹ค๋ฅธ ์„ธ๊ทธ๋จผํŠธ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋‹ค๋ฉด ๋ฐ”์ธ๋”ฉ์€ runtime๊นŒ์ง€ ์ง€์—ฐ๋˜์–ด์•ผ ํ•œ๋‹ค.

Logical Versus Physical Address Space

CPU๊ฐ€ ์ƒ์„ฑํ•˜๋Š” logical address์ด๊ณ , ๋ฉ”๋ชจ๋ฆฌ์— ์˜ํ•ด ์ทจ๊ธ‰๋˜๋Š” ์ฃผ์†Œ๋Š” physical address์ด๋‹ค. compile-time๊ณผ load-time์—์„œ ์ฃผ์†Œ๋ฅผ bindingํ•  ๋•Œ๋Š” logical address์™€ physical address๊ฐ€ ๊ฐ™๊ฒŒ ์ƒ์„ฑ๋˜๋Š” ๋ฐ˜๋ฉด execution-time์—์„œ๋Š” ๋‹ค๋ฅด๊ฒŒ ์ƒ์„ฑ๋œ๋‹ค. ์ด ๊ฒฝ์šฐ logical address๋ฅผ virtual address๋ผ๊ณ  ํ•œ๋‹ค. virtual address๋ฅผ physical address๋กœ ๋Œ€์‘์‹œํ‚ค๋Š” ๊ฒƒ์€ ํ•˜๋“œ์›จ์–ด ๋””๋ฐ”์ด์Šค์ธ MMU(Memory-Management Unit)๊ฐ€ ํ•œ๋‹ค.

Swapping

๋ฉ”๋ชจ๋ฆฌ๋Š” ํฌ๊ธฐ๊ฐ€ ํฌ์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ํ”„๋กœ์„ธ์Šค๋ฅผ ์ž„์‹œ๋กœ ๋””์Šคํฌ์— ๋ณด๋ƒˆ๋‹ค๊ฐ€ ๋‹ค์‹œ ๋ฉ”๋ชจ๋ฆฌ์— ๋กœ๋“œํ•ด์•ผ ํ•˜๋Š” ์ƒํ™ฉ์ด ์ƒ๊ธด๋‹ค. ์ด๋•Œ ๋””์Šคํฌ๋กœ ๋‚ด๋ณด๋‚ด๋Š” ๊ฒƒ์„ swap out, ๋ฉ”๋ชจ๋ฆฌ๋กœ ๋“ค์—ฌ๋ณด๋‚ด๋Š” ๊ฒƒ์„ swap in์ด๋ผ๊ณ  ํ•˜๋ฉฐ, ์šฐ์„  ์ˆœ์œ„์— ๋”ฐ๋ผ ์–ด๋–ค ํ”„๋กœ์„ธ์Šค๋ฅผ swap in/outํ• ์ง€ ๊ฒฐ์ •ํ•œ๋‹ค. swapํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์˜ ๋Œ€๋ถ€๋ถ„์€ ๋””์Šคํฌ ์ „์†ก ์‹œ๊ฐ„์ด๋‹ค.

Contiguous Memory Allocation

๋ณดํ†ต ๋ฉ”๋ชจ๋ฆฌ๋Š” ๋‘ ๊ฐœ์˜ ์˜์—ญ์œผ๋กœ ๋‚˜๋ˆ  ๊ด€๋ฆฌ๋˜๋Š”๋ฐ, low memory์—๋Š” ์ปค๋„์„, high memory์—๋Š” ์‚ฌ์šฉ์ž ํ”„๋กœ์„ธ์Šค๋ฅผ ๋‹ด๋Š”๋‹ค. ์ด๋•Œ contiguous memory allocation ์‹œ์Šคํ…œ์—์„œ๋Š” ๊ฐ ํ”„๋กœ์„ธ์Šค๋“ค์ด ์—ฐ์†์ ์ธ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ์ฐจ์ง€ํ•˜๊ฒŒ ๋œ๋‹ค. ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ž์‹ ์˜ ๋ฒ”์œ„๋ฅผ ๋„˜์ง€ ๋ชปํ•˜๋„๋ก ํ•˜๋Š” ๊ฒƒ์€ base register์™€ limit register์˜ ์—ญํ• ์ด๋‹ค.

Memory Allocation

ํ”„๋กœ์„ธ์Šค๋ฅผ ๋ฉ”๋ชจ๋ฆฌ์— ๋กœ๋“œํ•  ๋•Œ๋Š” ๋จผ์ € ๋ฉ”๋ชจ๋ฆฌ ์ƒ์— ํ”„๋กœ์„ธ์Šค๋ฅผ ๋„ฃ์„ ์ˆ˜ ์žˆ๋Š” ๊ณต๊ฐ„์„ ์ฐพ๋Š”๋‹ค. ๋ฉ”๋ชจ๋ฆฌ์„ ๋ถ„ํ• ํ•˜๋Š” ๊ฐ ๋‹จ์œ„๋Š” block์ด๊ณ , ์ด ์ค‘ ์‚ฌ์šฉ ๊ฐ€๋Šฅํ•œ block์„ hole์ด๋ผ๊ณ  ํ•œ๋‹ค. ์ด๋•Œ ํ• ๋‹นํ•˜๋Š”๋ฐ ์—ฌ๋Ÿฌ ๋ฐฉ๋ฒ•์ด ์žˆ๋‹ค.

  • First fit: ์ฒซ ๋ฒˆ์งธ hole์„ ํ• ๋‹น
  • Best fit: hole ์ค‘์—์„œ ๊ฐ€์žฅ ์ž‘์€ ๊ณณ์„ ํ• ๋‹น
  • Worst fit: ๊ฐ€์žฅ ํฐ ๊ณณ์„ ํ• ๋‹น

ํ•˜์ง€๋งŒ Best fit๋„ ๊ทธ๋‹ฅ ํšจ์œจ์ด ์ข‹์ง€ ์•Š์•„ ์ด๋Ÿฐ ์‹์œผ๋กœ๋Š” ์“ธ ์ˆ˜ ์—†๋‹ค.

Fragmentation

fragmentation์€ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ์‚ฌ์šฉํ•˜์ง€ ๋ชปํ•˜๊ฒŒ ๋˜๋Š” ๊ฒƒ์„ ๋งํ•œ๋‹ค. (Java์˜ garbage collection์—๋„ ๊ฐ™์€ ๋ฌธ์ œ๊ฐ€ ์ƒ๊ธด๋‹ค.) ์—ฌ๋Ÿฌ ํ”„๋กœ์„ธ์Šค์— ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ํ• ๋‹นํ•˜๋Š” ๊ณผ์ •์„ ๊ฑฐ์น˜๋ฉด ๋ฉ”๋ชจ๋ฆฌ์˜ ๋ชจ์Šต์€ ๋Œ€๋žต ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๋น„์Šทํ•  ๊ฒƒ์ด๋‹ค.

memory alloc

๊ฐ block์˜ ํฌ๊ธฐ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ 30k, 60k, 20k, 40k, 60k๋ผ๊ณ  ํ•ด๋ณด์ž. hole์€ 60k ๋‘ ๊ณณ๋ฟ์ด๋‹ค. ๊ทธ๋Ÿฐ๋ฐ ๋งŒ์•ฝ 70k ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋“ค์–ด์™€์•ผ ํ•œ๋‹ค๋ฉด? ์‹ค์ œ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์€ 120k๊ฐ€ ๋น„์–ด์žˆ์ง€๋งŒ ์–ด๋””์—๋„ 70k๊ฐ€ ๋“ค์–ด๊ฐˆ ์ˆ˜๋Š” ์—†๋‹ค. ์ด๊ฒƒ์„ external fragmentation์ด๋ผ๊ณ  ํ•œ๋‹ค.

internal fragmentation์€ ์‹ค์ œ ํ”„๋กœ์„ธ์Šค ๊ณต๊ฐ„๋ณด๋‹ค ํฐ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ํ• ๋‹นํ•˜๊ฒŒ ๋˜๋Š” ๊ฒฝ์šฐ๋ฅผ ๋งํ•œ๋‹ค. ์ผ๋ฐ˜์ ์œผ๋กœ ๋ฉ”๋ชจ๋ฆฌ๊ฐ€ ์‹œ์Šคํ…œ ํšจ์œจ์„ ์œ„ํ•ด ๊ณ ์ • ํฌ๊ธฐ์˜ ์ •์ˆ˜ ๋ฐฐ๋กœ ํ• ๋‹น๋˜๊ธฐ ๋•Œ๋ฌธ์— ์ƒ๊ธฐ๋Š” ํ˜„์ƒ์ด๋‹ค.

์ด๋Ÿฐ ๋ฌธ์ œ๋Š” ํ• ๋‹น๋œ block์„ ํ•œ์ชฝ์œผ๋กœ ๋ชฐ์•„ ํฐ block์„ ์ƒ์„ฑํ•˜๋Š” compaction์œผ๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค.

compaction

์ด๋ ‡๊ฒŒ ํ•˜๋ฉด 70k ํ”„๋กœ์„ธ์Šค๋„ ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ ํ”„๋กœ์„ธ์Šค ํ• ๋‹น์€ ์ •๋ง ์ž์ฃผ ์ผ์–ด๋‚˜๋Š” ์ผ์ด๊ธฐ ๋•Œ๋ฌธ์— compaction์ฒ˜๋Ÿผ ์˜ค๋ฒ„ํ—ค๋“œ๊ฐ€ ํฐ ์ž‘์—…์„ ๋งค๋ฒˆ ํ•  ์ˆ˜๋Š” ์—†๋‹ค. ๊ณผ๊ฑฐ์—๋Š” ์ด ๋ฐฉ๋ฒ•์„ ์ผ์ง€๋งŒ ์ด์   ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์„ ์“ด๋‹ค.

Segmentation

segmentation์€ ํ•˜๋‚˜์˜ ํ”„๋กœ์„ธ์Šค๋ฅผ ์—ฌ๋Ÿฌ ๊ฐœ๋กœ ๋‚˜๋ˆ„๋Š” ๊ฒƒ์„ ๋งํ•œ๋‹ค. segment๋Š” main, function, method, object ๋“ฑ์˜ ๋…ผ๋ฆฌ์  ๋‹จ์œ„๋กœ, ์ธ๊ฐ„์˜ ๊ด€์ ์œผ๋กœ ํ”„๋กœ์„ธ์Šค๋ฅผ ๋‚˜๋ˆˆ ๊ฒƒ์ด๋‹ค. ๊ฐ segment์˜ base์™€ limit์€ segment table์— ์ €์žฅ๋œ๋‹ค.

Paging

paging์€ segmentation๊ณผ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ํ”„๋กœ์„ธ์Šค๋ฅผ ์—ฌ๋Ÿฌ ์กฐ๊ฐ์œผ๋กœ ๋‚˜๋ˆ„๋Š” ๊ฒƒ์ด๋‹ค. ๊ทธ๋Ÿฐ๋ฐ ๋‹จ์ˆœํžˆ ํฌ๊ธฐ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋‚˜๋ˆ„๊ธฐ ๋•Œ๋ฌธ์— ๋น„์Šทํ•œ ์š”์†Œ๋ผ๋„ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์— ์—ฐ์†์ ์œผ๋กœ ํ• ๋‹น๋˜์ง€ ์•Š๋Š”๋‹ค. ์ปดํ“จํ„ฐ ์ž…์žฅ์—์„œ๋Š” ํ•ด์„ํ•˜๊ธฐ ์‰ฝ์ง€๋งŒ ์‚ฌ๋žŒ์ด ์ง์ ‘ ๊ด€๋ฆฌํ•˜๊ธฐ๋Š” ์–ด๋ ต๋‹ค.

paging์—์„œ๋Š” physical memory์˜ ๊ฐ block์„ frame์ด๋ผ๊ณ  ํ•˜๊ณ , logical memory์˜ ๊ฐ block์„ page๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค. frame์„ ์ž‘๊ฒŒ ๋‚˜๋ˆŒ์ˆ˜๋ก fragment๊ฐ€ ์ ๊ฒŒ ์ƒ๊ธฐ๋ฉฐ, ์‹ค์ œ๋กœ external fragmentation์€ ๊ฑฐ์˜ ์ƒ๊ธฐ์ง€ ์•Š๋Š”๋‹ค. logical address๋ฅผ physical address๋กœ ๋ณ€ํ™˜ํ•˜๋Š” page table์ด ํ•„์š”ํ•˜๋‹ค.

Basic Method

CPU์— ์˜ํ•ด ๋งŒ๋“ค์–ด์ง„ ์ฃผ์†Œ๋Š” page numberยง์™€ page offset(d) ๋‘ ๋ถ€๋ถ„์œผ๋กœ ๋‚˜๋‰œ๋‹ค. page number๋Š” page table์˜ index๋กœ์จ page table์— ์ ‘๊ทผํ•  ๋•Œ ์‚ฌ์šฉ๋œ๋‹ค. page offset์€ physical address๋ฅผ ์–ป์„ ๋•Œ ์“ฐ์ด๋ฉฐ, page table์˜ base address์— page offset์„ ๋”ํ•˜๋ฉด physical address๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

Hardware Support

page table์€ ๋ฉ”๋ชจ๋ฆฌ์— ์ €์žฅ๋˜์–ด ์žˆ๋‹ค. PTBR(Page-Table Base Register)๊ฐ€ page table์„ ๊ฐ€๋ฆฌํ‚ค๊ณ , PTLR(Page-Table Length Register)๊ฐ€ page table์˜ ํฌ๊ธฐ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ๋”ฐ๋ผ์„œ ๋งค๋ฒˆ ๋ฐ์ดํ„ฐ์— ์ ‘๊ทผํ•  ๋•Œ๋งˆ๋‹ค ํ•œ ๋ฒˆ์€ ๋ฐ์ดํ„ฐ์—, ํ•œ ๋ฒˆ์€ page table์— ์ ‘๊ทผํ•ด์•ผ ํ•œ๋‹ค. ๋ฌผ๋ก  ์ด๋Š” ๋น„ํšจ์œจ์ ์ธ ์ผ์ด๊ธฐ ๋•Œ๋ฌธ์— ์บ์‹œ๊ฐ™์€ ๊ฒƒ์„ ์‚ฌ์šฉํ•ด ํ•ด๊ฒฐํ–ˆ๋‹ค.

TLB(Translation Look-aside Buffer)๋Š” ์ฐธ์กฐํ–ˆ๋˜ ํŽ˜์ด์ง€๋ฅผ ๋‹ด์•„์ฃผ๋Š” ์บ์‹œ ์—ญํ• ์„ ํ•œ๋‹ค. TLB๋Š” key-value pair๋กœ ๋ฐ์ดํ„ฐ๋ฅผ ๊ด€๋ฆฌํ•˜๋Š” acssociative memory์ด๋ฉฐ, CPU๋Š” page table๋ณด๋‹ค TLB์„ ์šฐ์„ ์ ์œผ๋กœ ์ฐธ์กฐํ•œ๋‹ค.

page number๊ฐ€ TLB์—์„œ ๋ฐœ๊ฒฌ๋˜๋Š” ๋น„์œจ์„ hit ratio๋ผ๊ณ  ํ•˜๋ฉฐ, effective memory-access time์„ ๊ตฌํ•˜๋Š”๋ฐ ์“ธ ์ˆ˜ ์žˆ๋‹ค.

effecftive memory-access = hit ratio * memory access time + (1 - hit ratio) * (2 * memory access time)

๋งŒ์•ฝ hit ratio๊ฐ€ 80%์ด๊ณ , ํ‰๊ท  ๋ฉ”๋ชจ๋ฆฌ ์ ‘๊ทผ ์‹œ๊ฐ„์ด 100 ๋‚˜๋…ธ์ดˆ๋ผ๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ณ„์‚ฐํ•œ๋‹ค.

effective memery-access time = 0.8 * 100 + 0.2 * 200 = 120

Protection

๋ฉ”๋ชจ๋ฆฌ ํ• ๋‹น์ด contiguousํ•œ ๊ฒฝ์šฐ limit๋งŒ ๋น„๊ตํ•ด๋„ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ๋ณดํ˜ธํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค. ํ•˜์ง€๋งŒ paging์€ contiguousํ•˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์„ ์“ด๋‹ค. page table์˜ ๊ฐ ํ•ญ๋ชฉ์—๋Š” valid-invalid bit๊ฐ€ ๋ถ™์–ด์žˆ์–ด ๊ทธ ๊ฐ’์ด valid๋ผ๋ฉด ํ•ด๋‹น ํŽ˜์ด์ง€์— ์ ‘๊ทผ์ด ๊ฐ€๋Šฅํ•˜๊ณ , invalid๋ผ๋ฉด ํ•ด๋‹น ํŽ˜์ด์ง€๊ฐ€ logical address space์— ์†ํ•˜์ง€ ์•Š์•„ ์ ‘๊ทผํ•  ์ˆ˜ ์—†๋‹ค๋Š” ๊ฒƒ์„ ์˜๋ฏธํ•œ๋‹ค.

Shared Pages

paging์˜ ๋˜ ๋‹ค๋ฅธ ์žฅ์ ์€ ์ฝ”๋“œ๋ฅผ ์‰ฝ๊ฒŒ ๊ณต์œ ํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. ๋งŒ์•ฝ ์ฝ”๋“œ๊ฐ€ reentrant code(๋˜๋Š” pure code)๋ผ๋ฉด ๊ณต์œ ๊ฐ€ ๊ฐ€๋Šฅํ•˜๋‹ค. reentrant code๋Š” runtime ๋™์•ˆ ์ ˆ๋Œ€๋กœ ๋ณ€ํ•˜์ง€ ์•Š๋Š” ์ฝ”๋“œ์ด๋ฉฐ, ๋”ฐ๋ผ์„œ ์—ฌ๋Ÿฌ ํ”„๋กœ์„ธ์Šค๋“ค์ด ๋™์‹œ์— ๊ฐ™์€ ์ฝ”๋“œ๋ฅผ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ๋‹ค. ์ด๋Ÿฐ ์‹์œผ๋กœ ๊ณตํ†ต page๋ฅผ ๊ณต์œ ํ•˜๋ฉด 12๊ฐœ ๋กœ๋“œํ•ด์•ผ ํ•  ๊ฒƒ์„ 6๊ฐœ๋งŒ ๋กœ๋“œํ•ด๋„ ๋œ๋‹ค.

Structure of the Page Table

paging์„ ์ง์ ‘ ์ ์šฉํ•˜๋ฉด page table์˜ ํฌ๊ธฐ๊ฐ€ ์ปค์ง„๋‹ค. ํŽ˜์ด์ง€ ํ…Œ์ด๋ธ”์„ ํšจ์œจ์ ์œผ๋กœ ๊ตฌ์„ฑํ•˜๋Š” ๋ช‡ ๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด ์žˆ๋‹ค.

Hierachial Paging

hierachical paging์€ logical address space๋ฅผ ์—ฌ๋Ÿฌ ๋‹จ๊ณ„์˜ page table๋กœ ๋ถ„ํ• ํ•˜๋Š” ๊ธฐ๋ฒ•์ด๋‹ค. two-level paging scheme์ด ์˜ˆ์‹œ์ธ๋ฐ, page table๊ณผ ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์ด์— page table์„ ํ•˜๋‚˜ ๋” ๋‘ ์œผ๋กœ์จ ๋ชจ๋“  ํŽ˜์ด์ง€๋ฅผ ๋กœ๋“œํ•ด์•ผ ํ•˜๋Š” ๋ถ€๋‹ด์„ ์ค„์ผ ์ˆ˜ ์žˆ๋‹ค.

Hashed Page Tables

๋ง๊ทธ๋Œ€๋กœ hash table์„ ์ด์šฉํ•ด page table์„ ๊ด€๋ฆฌํ•˜๋Š” ๊ธฐ๋ฒ•. address space๊ฐ€ 32๋น„ํŠธ๋ณด๋‹ค ์ปค์ง€๋ฉด hierachial paging์ด ๋น„ํšจ์œจ์ ์ด๊ธฐ ๋•Œ๋ฌธ์— ์ฃผ๋กœ ์ด ๋ฐฉ๋ฒ•์„ ์“ด๋‹ค. virtual page number๋ฅผ hashingํ•ด page table์„ ์ฐธ์กฐํ•˜๋Š” ๋ฐ ์‚ฌ์šฉํ•œ๋‹ค. hashed page table์—์„œ๋Š” linked list๋ฅผ ๋”ฐ๋ผ๊ฐ€๋ฉฐ page number๋ฅผ ๋น„๊ตํ•˜๊ณ , ์ผ์น˜ํ•˜๋ฉด ๊ทธ์— ๋Œ€์‘ํ•˜๋Š” page frame number๋ฅผ ์–ป๋Š”๋‹ค. hash table์€ ๊ฒ€์ƒ‰์— O(1) ์‹œ๊ฐ„์ด ๊ฑธ๋ ค ๋งค์šฐ ๋น ๋ฅด์ง€๋งŒ ๊ตฌํ˜„์ด ์–ด๋ ต๋‹ค.

Inverted Page Tables

์ง€๊ธˆ๊นŒ์ง€ page table์€ ๊ฐ page๋งˆ๋‹ค ํ•˜๋‚˜์˜ ํ•ญ๋ชฉ์„ ๊ฐ€์กŒ๋‹ค. inverted page table์€ ๋ฉ”๋ชจ๋ฆฌ์˜ frame๋งˆ๋‹ค ํ•œ ํ•ญ๋ชฉ์”ฉ ํ• ๋‹นํ•˜๋Š”๋ฐ, ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด physical frame์— ๋Œ€์‘ํ•˜๋Š” ํ•ญ๋ชฉ๋งŒ ์ €์žฅํ•˜๋ฉด ๋˜๊ธฐ ๋•Œ๋ฌธ์— ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ํ›จ์”ฌ ์ ๊ฒŒ ์‚ฌ์šฉํ•˜๊ฒŒ ๋œ๋‹ค. ๋‹ค๋งŒ ํƒ์ƒ‰ ์‹œ๊ฐ„์ด ์˜ค๋ž˜ ๊ฑธ๋ฆฌ๊ธฐ ๋•Œ๋ฌธ์— ๋Œ€๋ถ€๋ถ„์˜ ๋ฉ”๋ชจ๋ฆฌ๋Š” inverted page table๊ณผ hased page table์„ ๊ฒฐํ•ฉํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๊ตฌํ˜„๋˜์–ด์žˆ๋‹ค.