2024. 2. 5. 16:08ㆍ프로그래밍 공부/OS
Non-coutinuous allocation
사용자 프로그램을 여러 개의 block으로 분할
☆실행 시, 필요한 block들만 메모리에 적재
- 나머지 block들은 swap device에 존재
Disk
continous allocation
ㅁ ㅁ
Pi → Mem
Noncontinous allocation
1 1
2
3 2
3
Pi → Mem
기법들
- Paging system
+
- Segmentation system
↓
- Hybrid paging/segmentation system
Address Mapping
Continuous allocation
- Relative address (상대 주소)
* 프로그램의 시작 주소를 0으로 가정한 주소
- Relocation (재배치)
* 메모리 할당 후, 할당된 주소(allocation address)에 따라 상대 주소들을 조정하는 작업
Continuous allocation
Relative address
0 ... 400 ... 400 ...
240 Branch 360 640 Branch 360+400→ 640 Branch 760
... ... ...
800 Load 1204 1200 Load 1204+400→ 1200 Load 1604
... ... ...
1204 x 1604 x 1604 x
... ... ...
Memory Memory
(a) Program code (b) After loading (c) After relocation
Non-continous allocation
↓|___| |===|
|----| →|===|
Memory
- Virtual address (가상주소) = relative address
* Logical address (논리주소)
*☆ 연속된 메모리 할당을 가정한 주소
- Real address (가상주소) = absolute (physical)
* 실제 메모리에 적재된 주소
- Address Mapping
* Virtual address → real address
virtual Addr. real Memory
→ address → Mapping → address - | Kernel |
| | | |
User → | |
process----------------------------------→ | |
| |
☆ 사용자/프로세스는 실행 프로그램 전체가 메모리에 연속적으로
적재되었다고 가정하고 실행할 수 있음
Block Mapping
사용자 프로그램을 block 단위로 분할/관리
- 각 block에 대한 address mapping 정보 유지
Virtual address : v = (b, d)
- b = block number
- d = displacement(offset) in a block
0
block 1
1
virtual address block 1
v = (b, d)
| ...........
| b ↑ block b
| ↓d
-------------->
...........
m-1
block m-1
Block Mapping
Kernel
| | BMT
| |
Block map table (BMT)
- Address Mapping 정보 관리
* Kernel 공간에 프로세스마다 하나의 BMT를 가짐
| block number | residence bit | ... | real address |
| 0 1 2 ... |
. . . |
||
| b | 1 | ...... | a |
| ... m-1 |
. . |
* Residence bit: 해당 블록이 메모리에 적재되었는지 여부 (0/1)
(virtual address) v=(b,d)
block number displacement
------- b | d
| ↓
| real address
| ----→ a+d computation
| residence real | | ____________
| bit ... address | | a ↓ d
| 0 | |-→r
| 1 |
| ... ... |
→b 1 a --
... ...
m-1 main memory
block mapping table
BMT
Block Mapping
v = (b, d)
1. 프로세스의 BMT에 접근
2. BMT에서 block b에 대한 항목(entry)를 찾음
3. Residence bit 검사
memory에 안 올라갔다
① Residence bit = 0 경우,
swap device에서 해당 블록을 메모리로 가져 옴
BTM 업데이트 후 3-② 단계 수행
② Residence bit = 1 경우,
BTM에서 b에 대한 real address 값 a 확인
4. 실제 주소 r 계산 (r = a + d)
5. r을 이용하여 메모리에 접근
In the Next Video
Paging System
가상 메모리
페이징
Virtual Storage Methods
Paging system
Segmentation system
Hybrid paging/segmentation system
Paging System
프로그램을 같은 크기의 블록으로 분할 (Pages)
|=====| ← |=====| page
Memory
Terminologies
- Page
* 프로그램의 분할된 block
- Page frame 틀
* 메모리의 분할 영역
* Page와 같은 크기로 분할
(페이지를 넣는 틀)
Paging System
pf-0 Process i
pf-1 page-(n-1)
pf-2
pf-3 page-k
pf-4
... page-2
pf-k page-1
... page-0
pf-(m-1)
Main memory Secondary storage
(Swap device) → 가상 memory
특징
|=====| page function 분할
- 논리적 분할이 아님 (크기에 따른 분할)
* Page 공유(sharing) 및 보호(protection)과정이 복잡함
★Segmentation 대비
- Simple and Efficient
* Segmentation 대비 단편화
- No external fragmentation
* Internal fragmentation 발생 가능
내부
_____ |____|
|____| →|____|
|____| |____|
|____| |____|
| ↓ |
내부 단편화
Paging System (in Windows)
제어판 - 시스템 - 고급 시스템 설정 - 고급 탭 - 성능 부분 설정 버튼
- 성능옵션 - 고급 탭 - 가상메모리 - 페이징 파일 - 변경버튼
Windows page size = 4KB ←linux
(System에 따라 다를 수 있음)
Address Mapping
b, d
Virtual address : v = (p, d) block Mapping과 유사
- p: page number
- d: displacement(offset)
Address mapping BMT
- PMT(Page Map Table) 사용
Address mapping mechanism
- Direct mapping (직접 사상) block mapping과 유사
- Associative mapping (연관 사상)
* TLB(Translation Look-aside Buffer)
- Hybrid direct/associative mapping
Page Map Table (PMT)
swap device
Pi
| page number | residence bit | secondary storage address | other fields | page frame number |
| 0 | 1 | S0 | ... | 2 |
| 1 | 1 | S1 | ... | 4 |
| 2 | 0 | S2 | ... | - |
| ... | ... | ... | ... | ... |
| k | 1 | Sk | ... | h |
| ... | ... | ... | ... | ... |
| n-1 | 0 | Sn-1 | ... | - |
Direct mapping
- Block mapping 방법과 유사
- 가정
* PMT를 커널 안에 저장
* PMT entry size = entrySize
* Page size = pageSize
Direct Mapping
(p, d)
b PMT base address (virtual address)
↓ page number displacement
b + p * entrySize ←------- b | d
| ↓
| real address
| --→ p' * pageSize + d computation
| residence page frame | |
|es bit ... number | | page frame p' ↕ d
① | 0 | |----------------→r
| 1 | ②
| ... ... |
→b 1 p' --
... ...
n-1 main memory
page map table
in main memory (kernel)
PMT
Direct Mapping
1. 해당 프로세스의 PMT가 저장되어 있는 주소 b에 접근
2. 해당 PMT에서 page p에 대한 entry를 찾음
p의 entry 위치 = b + p * entrySize
3. 찾아진 entry의 존재 bit 검사
running
↗ ↘ context switching
ready ← asleep
/block ↙ Context switch 발생(I/O) → Overhead
① Residence bit = 0 경우 (page fault), 피해
swap device에서 해당 page를 메모리로 적재
PMT를 갱신한 후 3-② 단계 수행
② Residence bit = 1 경우,
해당 entry에서 page frame 번호 p'를 확인
4. p'와 가상 주소의 변위 d를 사용하여 실제 주소 r 형성
r = p' * pageSize + d
5. 실제 주소 r로 주기억장치에 접근
작업 관리자 - 성능 탭 - 리소스 모니터 열기 - 메모리 탭 - 페이지 폴트
Direct Mapping
문제점
- 메모리 접근 횟수가 2배
* 성능 저하 (performance degradation)
-★ PMT를 위한 메모리 공간 필요
해결방안
- Associative mapping (TLB)
- PMT를 위한 전용 기억장치(공간) 사용
* Dedicated register or cache memory
- Hierachical paging
- Hashed page table
- Inverted page table
Associative Mapping
TLB(Translation Look-aside Buffer)에 PMT 적재
address mapping할때 옆에 두고 사용하는 특별한 장치
- Associative high-speed memory 전용 H/W
PMT를 병렬 탐색
Low overhead, high speed
(virtual address)
p page number displacement
-------------------------- p | d
| ↓
| "b + p * ( )" real address
| ----→ p' * pageSize + d computation
| page residence page frame | |
| number bit ... number | | page frame p' ↕ d
|--→. 0 | |----------------→r
parallel|--→ 1 | ②
search | ... ... ... ... |
|--→ p 1 p' --
| ... ... ...
|--→ n-1 main memory
PMT in TLB
Associative Mapping
TLB(Translation Look-aside Buffer)에 PMT 적재
- Associative high-speed memory 전용 HW
PMT를 병렬 탐색
Low overhead, high speed
Expensive hardware → 작다
- 큰 PMT를 다루기가 어려움
Typical TLB
size: 12bits - 4096 entries
A + B
Hybrid Direct/Associative Mapping
두 기법을 혼합하여 사용
- HW 비용은 줄이고, Associative mapping의 장점 활용
TLB ← PMT
작은 크기의 TLB 사용
- PMT: 메모리(커널 공간)에 저장 "어떤 entry?"
- TLB: PMT 중 일부 entry들을 적재
* 최근에 사용된 page들에 대한 entry 저장
↓
- Locality (지역성) 활용
* 프로그램의 수행과정에서 한번 접근한 영역을 다시 접근
(temporal locality) 또는 인접 영역을 다시 접근(spatial locality)
할 가능성이 높음
프로세스의 PMT가 TLB에 적재되어 있는지 확인
PMT
① TLB에 적재되어 있는 경우, Associative Mapping
* residence bit를 검사하고 page frame 번호 확인
② TLB에 적재되어 있지 않은 경우,
* Direct mapping으로 page frame 번호 확인
* 해당 PMT entry를 TLB에 적재함
PMT base address
b (virtual address)
↓ page number displacement
b + p * entrySize ←------- p | d
| | ↓x ↑locality ↓
| first trial |
| | real address
| | ---→ p' * pageSize + d computation
| | page residence page frame | |
| | number bit ... number | | page frame p' ↕ d
| |--→ ... ... ... | |----------------→r
| |--→ p 1 p' ---|
| |--→ ... ... ... |
| | main memory
| partial PMT in TLB |
| second trial |
| residence page frame |
| bit ... number |
| 0 |
| 1 |
| ... ... |
→p 1 p' |
... ... ---------------|
n-1
PMT
in main memory
In the Next Video
Paging System
- Memory Management
Memory Management
Page와 같은 크기로 미리 분할하여 관리/사용
- Page frame
- FPM 기법과 유사
_____
|____|
|____| ] page
|____|
|____|
Frame table
- Page frame당 하나의 entry
- 구성
* Allocated/available field
* PID field
* Link field : For free list (사용가능한 fp들을 연결)
* AV: Free list header (free list의 시작점)
(available의 약자)
Frame table
pageframe 누구 빈공간
↓
AV pointer→
| page frame number | allocated | PID | link |
| 0 | 0 빈공간 | (0 → k+1) | |
| 1 | 1 | P2 | |
| 2 | 1 | P1 | |
| ... | |||
| k-1 | 0 | - | (k-1 → m-1) |
| k | 1 | P1 | |
| k+1 | 0 | - | (k+1 → k-1) |
| ... | |||
| m-1 | 0 | - | (m-1 → |
빈 entry
=> linked list
Page Sharing
여러 프로세스가 특정 page를 공유 가능
- Non-continuous allocation!
funcX A A - x
□ B B - x
C C - x
A ↘
B → x
C ↗
공유 가능 page
-1. Procedure pages
* Pure code (reenter code)
-2. Data page
* Read-only data
* Read-write data
"병행성(concurrency) 제어" 기법 관리하에서만 가능
Page Sharing (Example)
한글
Editor 프로그램을 3명이 사용하는 경우
P1을 위한
프로세스 P1 페이지 테이블
ed 1 3
ed 2 4
ed 3 6
data 1 1
P2를 위한
프로세스 P2 페이지 테이블
ed 1 3
ed 2 4
ed 3 6
data 2 7
P3를 위한
프로세스 P3 페이지 테이블
ed 1 3
ed 2 4
ed 3 6
data 3 2
0
1 data 1
2 data 3
3 ed 1
4 ed 2
5
6 ed 3
7 data 2
8
9
10
Page Sharing
Data page sharing
residence page frame
bit ... number
0
1
... ...
k1 1 p' ↘
... ... ↘
n1-1 ↗ page frame p'
PMT for P1 /
residence page frame /
bit ... number /
0 /
1 /
... ... /
k2 1 p'
... ... main memory
n2-1
PMT for P2
Procedure Page Sharing (Problem)
page residence page frame
num bit ... number
0
1
... ...
k1 1 p' ↘
... ... ↘
n1-1 ↗ ↕ d ↑ page frame p'
PMT for P1 / ↗ |
page residence page frame / | ↓ w
num bit ... number / \ Branch(?, d) Branch(k1, d)
0 / VA ↘ or
1 / Branch(k2, d)
... ... /
k2 1 p'
... ... main memory
n2-1
PMT for P2
Procedure Page Sharing (Solution)
- 프로세스들이 shared page에 대한 정보를 PMT의 같은 entry에 저장하도록 함
page residence page frame 이름 같게
num bit ... number
0
1
... ...
k 1 p' ↘
... ... ↘
n-1 ↗ ↕ d ↑ page frame p'
PMT for P1 / ↗ |
page residence page frame / | ↓ w
num bit ... number / \ Branch(k, d)
0 /
1 /
... ... /
k 1 p'
... ... main memory
n-1
PMT for P2
Page Protection
보안
여러 프로세스가 page를 공유할 때,
- Protection bit 사용
물리적 주소
논리적 주소 VRWE
페이지 0 → 0 1 1100 → 페이지0
페이지 1 → 1 4 1110 → 페이지1
2 3 0000
페이지 3 → 3 7 1111 → 페이지3
페이지 테이블
타당 비타당(V)비트: 메인 메모리의 적재 여부
읽기(R) 비트: 읽기 여부
쓰기(W) 비트: 수정 여부
실행(E) 비트: 실행 여부
그림7-43 페이지 보호 비트
Paging System - Summary
프로그램을 고정된 크기의 block으로 분할 (page)
/ 메모리를 block size로 미리 분할 (page frame)
- 외부 단편화 문제 없음
X ↙
- 메모리 통합/압축 불필요 f1 ←
-★ 프로그램의 논리적 구조 고려하지 않음 f2
* Page sharing/protection이 복잡
필요한 page만 page frame에 적재하여 사용
-★ 메모리의 효율적 활용
Page mapping overhead
- 메모리 공간 및 추가적인 메모리 접근이 필요
- 전용 HW (TLB) 활용으로 해결 가능 Hybrid
* 하드웨어 비용 증가
In the Next Video
Segmentation System
segment-0
segment-1
segment-2
segment-3
segment-4
P4
Swap device
Virtual Storage Methods
____ |___|
|___| |___|
|___| |___|
|___| | |
Paging system
Segmentation system
Hybrid paging/segmentation system
Segmentation system
process
프로그램을 논리적 block으로 분할 (segment)
- Block의 크기가 "★서로 다를 수 있음"
- 예) stack, heap, main procedure, shared lib, Etc.
block 크기 다를 수 있다 → 미리 자를 수 없다
특징
- 메모리를 미리 분할하지 않음
* VPM과 유사
- Segment sharing/protection이 용이함
- Address mapping 및 메모리 관리의 overhead가 큼
내부 단편화
- No internal fragmentation
* "External fragmentation" 발생 가능
외부
Segmentation System
segment-3 of P4 Pi 논리적 분할
empty ↙ segment-0 func A
..... segment-1 B
↖ segment-2 dataset A
segment-1 of P4 segment-3
..... segment-4
empty Pa
main memory Swap device
Virtual Memory
Segmentation System
Address mapping p
- Virtual address: v = (s, d)
* s: segment number 번호
* d: displacement in a segment
offset
- Segment Map Table (SMT)
- Address mapping mechanism
* "Paging system과 유사"
Segment Map Table (SMT) VPM
| segment number |
residence bit |
secondary storage address |
크기 segment length |
func data protection bits(R/W/X/A) |
other fields | segment address in memory |
| 0 | 1 | S0 | l0 | RW | ... | a0 |
| 1 | 1 | S1 | l1 | RW | ... | a1 |
| 2 | 0 | S2 | l1 | RX | ... | - |
| ... | ... | ... | ... | ... | ... | ... |
| k | 1 | Sk | lk | RX | ... | ak |
| ... | ... | ... | ... | .... | ... | ... |
| n-1 | 0 | Sn-1 | ln-1 | RWA | ... | - |
Segmentation System
Address mapping ("direct mapping")
SMT base address
b (virtual address)
↓ segment number displacement
b + s * entrySize ←------- s | d
↓
| real address
| ---→ as + d computation
| residence segment segment | |
| bit length ... address | | as ↕ d |
| 0 | |---------→ r | ls
| 1 | |
| ... ... ... |
→s 1 ls as --|
main memory
segment map table
in main memory
Segmentation System
Address Mapping (direct mapping)
v = (s, d)
1. 프로세스의 SMT가 저장되어 있는 주소 b에 접근
2. SMT에서 segment s의 entry 찾음
- s의 entry 위치 = b + s * entrySize
3. 찾아진 Entry에 대해 다음 단계들을 순차적으로 실행
① 존재 비트가 0 경우, Memory 없다
// missing segment fault
swap device에서 해당 segment를 메모리로 적재
SMT를 갱신
↓ ② 변위(d)가 segment 길이보다 큰 경우 (d > ls),
segment overflow exception 처리 모듈을 호출
v(s, d > ls)
w ---------
Pi → | | | ) ls
--↓-----
③ 허가되지 않은 연산일 경우 (protection bit field 검사),
segment protection exception 처리 모듈을 호출 ↓
4. 실제 주소 r 계산 (r = as + d)
5. r로 메모리에 접근
Memory management
- VPM과 유사
* Segment 적재 시, 크기에 맞추어 분할 후 적재
<Partition table or State table>
| partition | 시작 주소 start address |
크기 size |
current process ID | segment number | storage protection key | other fields |
| 0 | ... | ... | Px | x1 | ... | ... |
| 1 | ... | ... | none | ... | ... | ... |
| 2 | ... | ... | Py | y1 | ... | ... |
| 4 | ... | ... | Px | x2 | ... | ... |
| 5 | ... | ... | none | ... | ... | ... |
| 6 | ... | ... | ... | ... | ... | ... |
Segment sharing/protection
- 논리적으로 분할되어 있어, 공유 및 보호가 용이함
P1 WP
편집기 데이터1 ls Start Addr. 물리적 주소
세그멘트0 세그멘트1 0 25286 43062 43062 ----------
1 4425 68348 편집기
사용자 1 68348 ----------
세그먼트 테이블 데이터1
P2 72773 ----------
편집기 데이터2 ls Start Addr.
세그멘트0 세그멘트1 0 25286 43062 90003 ----------
1 8500 90063 데이터 2
사용자 2 98553 ---------
세그먼트 테이블
세그멘테이션에서 세그멘트 공유
Segmentation System - Summary
프로그램을 논리 단위로 분할 (segment)
/ 메모리를 동적으로 분할
- 내부 단편화 문제 없음
공유 보호
- Segment sharing/protection이 용이함
- Paging system 대비 관리 overhead가 큼
필요한 segment만 메모리에 적재하여 사용
- 메모리의 효율적 활용
Segment mapping overhead
SMT
- 메모리 공간 및 추가적인 메모리 접근이 필요
- 전용 HW 활용으로 해결 가능
TLB←SMT "Hybrid"
Paging vs Segmentation
| Paging system | Segmentation System |
| 장 Simple, Low overhead | 단 High management overhead |
| 단 No logical concept for partitioning | 장 Logical concept for partitioning |
| 단 Complex page sharing mechanism | 장 Simple and easy sharing mechanism |
Virtual Storage Methods
Paging system
Segmentation system
Hybrid paging/segmentation system
Hybrid Paging/Segmentation
Paging과 Segmentation의 장점 결합
프로그램 분할
1. 논리 단위의 segment로 분할
2. 각 segment를 고정된 크기의 page들로 분할
Page단위로 메모리에 적재
Hybrid Paging/Segmentation
Process/Program
| S0-P0
| S0-P1 ← Segment-0 logical
| S0-P2
|
| S1-P0
| S1-P1
| S1-P2 ← Segment-1
Memory ←| S1-P3
|
| S2-P0
| S2-P1 ← Segment-2
|
| S3-P0
| S3-P1 ← Segment-3
| S3-P2
|
| S4-P0
| S4-P1
| S4-P2 ← Segment-4
| S4-P3
| S4-P4
user program
Hybrid Paging/Segmentation
Address mapping
- Virtual address : v = (s, p, d)
* s : segment number
* p : page number
* d : offset in a page
- "SMT"와 "PMT" 모두 사용
* 각 프로세스 마다 하나의 SMT
* 각 segment마다 하나의 PMT → page → Memory
page!
- Address mapping
* Direct, associated 등
- 메모리 관리
* FPM과 유사
Hybrid Paging/Segmentation
SMT in hybrid mechanism
| segment number | secondary storage address | segment length | protection bits(R/W/X/A) | other fields | "PMT address" |
| 0 | S0 | l0 | RW | ... | b0 |
| 1 | S1 | l1 | RW | ... | b1 |
| 2 | S2 | l2 | RX | ... | b2 |
| ... | ... | ... | ... | ... | ... |
| k | Sk | lk | RX | ... | bk |
| ... | ... | ... | ... | ... | ... |
| n-1 | Sn-1 | ln-1 | RWA | ... | bn-1 |
* No residence bit
메모리에 올라가는 것은 페이지이고 세그먼트는 메모리에 직접 올라가지 않음
대신에 각 segment에 PMT가 어디 있는지에 대한 정보 추가
Hybrid Paging/Segmentation
PMT for a segment k in hybrid mechanism
| page number | residence bit | secondary storage address | other fields | page frame number |
| 0 | 1 | Sk0 | ... | Pk0 |
| 1 | 1 | Sk1 | ... | Pk1 |
| 2 | 0 | Sk2 | ... | - |
| ... | ... | ... | ... | ... |
| k | 1 | Ski | ... | Pki |
| ... | ... | ... | ... | ... |
| h-1 | 0 | Sk,h-1 | ... | - |
Address mapping tables
S0 → PMT
residence ... page frame
-------→ bit number
| 0
| ... ... PMT of segment-0
| h0 - 1
Pi ★ | ---→ residence ... page frame
segment protection PMT | | bit number
length bits ... address | | 0
0 l0 ... b0 -- | ... ... PMT of segment-1
1 l1 ... b1 ---- h1 - 1
... ... ... | ---→ residence ... page frame
s ls ... bs ---- | bit number
... ... ... 0
n-1 ln-1 ... bn-1 -- ... ... PMT of segment-s
SMT | hs - 1
| -----→ residence ... page frame
bit number
0
... ... PMT of segment-(n-1)
hn-1 - 1
Direct (address) mapping HW → TLB
b SMT base address (virtual address)
↓ segment number page number displacement
b + s * SMTentrySize ←------- s | p | d
| ↓
| → bs + p * PMTentrySize ←----- real address
| | | → p' * pageSize + d computation
| PMT | | residence page frame | ____|
① | ... address | | bit ... number | | page frame p' ↕ d
| 0 | | 0 | -------------→ r
| 1 | ②| 1 | ③
| ... | | ... ... |
→s bs - →P 1 p' -
...
n-1 h-1 main memory
SMT PMT of segment-s
Hybrid Paging/Segmentation
Summary App 작은 OS
- 논리적 분할(segment)와 고정 크기 분할(page)을 결합
* Page sharing/protection이 쉬움
* 메모리 할당/관리 overhead가 작음 ↓ pf
* No external fragmentation pf
내부 단편화 O
단점
- 전체 테이블의 수 증가 ↑
* 메모리 소모가 큼
* Address mapping 과정이 복잡
- Direct mapping의 경우, 메모리 접근이 3배
* 성능이 저하될 수 있음
요약
Non-continuous allocation
Address mapping
- Block mapping
Paging system
Segmentation system
Hybrid paging/segmentation system
In the Next Video
Virtual Memory Management
: 가상 메모리 시스템 성능 최적화
'프로그래밍 공부 > OS' 카테고리의 다른 글
| 11 파일 시스템 (0) | 2024.02.11 |
|---|---|
| 10 가상 메모리 관리 (0) | 2024.02.07 |
| 8 메모리(주기억장치) 관리 (0) | 2024.02.02 |
| 7 Deadlock (0) | 2024.01.31 |
| 6 프로세스 동기화 & 상호배제 (0) | 2024.01.24 |