2024. 2. 2. 16:22ㆍ프로그래밍 공부/OS
메모리(기억장치)의 종류
CPU 속도 I/O bottleneck
저 ↑ 레지스터 } HW가 관리
용량 |↑속도 캐시 CPU
↓|가격 메인 메모리. } SW가 관리
고 보조 기억 장치 OS
메모리(기억장치) 계층 구조
processor cache main auxiliary
registers memory memory storage Disk(1 + DD.SSD)
←--------------------
reg ↔ ↔ 1~4KB ↔ 1~4KB
64bit word □□□□ block ■□□□
←---------------
1bit
larger capacity, low cost/bit
----------------------------------------------------→
←----------------------------------------------------
faster access time
Block
- 보조기억장치와 주기억장치 사이의 데이터 전송 단위
- Size: 1~4KB
Word
- 주기억장치와 레지스터 사이의 데이터 전송 단위
- Size: 16~64bits
8
↓
32bit
CPU 64bit
(word단위)
Backgrounds
Address Binding
int a
100 4
|=|=|=|
a => 100
프로그램의 논리 주소를 실제 메모리의 물리 주소로 매핑(mapping)하는 작업
Binding 시점에 따른 구분
- Compile time binding
- Load time binding
- Run time binding
논리적 관점 물리적 관점
_____시작
LC PA
_____끝
_____시작
LB PB 끝
______시작
LA PC
_______끝
(a) 논리적 주소 (b) 물리적 주소
Address Binding
User Program Processing Steps
Compile time Load time Run time
Pi
exe <Memory>
Source → Compiler → Object → Linker → Load → Loader → In-memory
code module module binary Image
+ ↗ ↗ ↗
Other System Dynamic loaded
object lib library system library
module
Address Binding
int a; → 100V Compiler
int b; → 200V ==ㅁ====
↑↑↑
ㅁㅁ
Compile time binding
- 프로세스가 메모리에 적재될 위치를 컴파일러가 알 수 있는 경우
* 위치가 변하지 않음
- 프로그램 전체가 메모리에 올라가야 함
Load time binding
- 메모리 적재 위치를 컴파일 시점에서 모르면, 대체 가능한 상대 주소를 생성
u
u + 100
v + 200
- 적재 시점(load time)에 시작 주소를 반영하여 사용자 코드 상의 주소를 재설정
- 프로그램 전체가 메모리에 올라가야 함
Address Binding
Load time binding
가정
0 ... 400
240 Branch 360 640
...
800 Load 1204 1200
...
1204 X 1604
...
Memory Memory
(a) Program code
(Allocation address = 400)
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
Address Binding
running
↗ ↘
ready ← block
Run-time binding
- Address binding을 수행시간까지 연기
* 프로세스가 수행 도중 다른 메모리 위치로 이동할 수 있음
- HW의 도움이 필요
* MMU: Memory Management Unit
- 대부분의 OS가 사용
relocation
register
logical 14000 physical
address address
CPU → + → memory
346 14346
MMU
Dynamic Loading
모든 루틴을 교체 가능한 형태로 디스크에 저장
실제 호출 전까지는 루틴을 적재하지 않음
- 메인 프로그램만 메모리에 적재하여 수행
- 루틴의 호출 시점에만 address binding 수행
Pi
func A → ===|A|===
func B
func C
장점
- 메모리 공간의 효율적 사용
Swapping
프로세서 할당이 끝나고 수행 완료된 프로세스
는 swap-device로 보내고 (Swap-out)
새롭게 시작하는 프로세스는 메모리에 적재
(Swap-in)
Memory ready
Image \ |↑↑ swap-in
\ | | | (resume)
swap-out \ | | |
(suspend)↓↓| |
suspended
ready
운영체제
① 스왑 아웃 프로세스
사용자 영역 → P1
② 스왑 인 프로세스
← P2
메인 메모리 보조예비기억장치
Memory Allocation
Continuous Memory Allocation (연속할당)
- Uni-Programming
- Multi-Programming
* Fixed partition (FPM)
* Variable partition (VPM)
Non-continuous Memory Allocation (비연속할당)
- Next chapter
Continuous Memory Allocation
프로세스(context)를 하나의 연속된 메모리 공간에 할당하는 정책
- 프로그램, 데이터, 스택 등
□
□→□
□
메모리 구성 정책
- 메모리에 동시에 올라갈 수 있는 프로세스 수
* Multiprogramming degree
* 각 프로세스에게 할당되는 메모리 공간 크기
* 메모리 분할 방법
Continuous Memory Allocation
하나
Uni-Programming
- Multiprogramming degree = 1 process 1
Multi-Programming
- Fixed(static) partition multi-programming (FPM)
* 고정 분할
- Variable(dynamic) partition multi-programming (VPM)
* 가변 분할
Uni-Programming
하나의 프포세스만 메모리 상에 존재
가장 간단한 메모리 관리 비법
Kernel ] Kernel Space
Pi → Pi |
User Program | User Space
Wasted Space |
Uni-Programming
문제점 1
_
|_| ↘ _
|_| > |_|
→
- 프로그램의 크기 > 메모리 크기
해결법 사용자
- Overlay structure programmer
* 메모리에 현재 필요한 영역만 적재
* 사용자가 프로그램의 흐름 및 자료구조를 모두 알고 있어야 함
공통
S1
S2
패스 1: 70KB
패스 2: 80KB
심벌 테이블: 20KB
공통 루틴: 30KB
중첩 구동비(오버레이 드라이버): 10KB
(a) 2단계 어셈블리 예
심벌 테이벌 20KB
공통 루틴 30KB
중첩 구동기 10KB
70KB 패스 1→ ← 패스2 80KB
중첩 A: 심벌 테이블, 공통 루틴, 패스 1
중첩 B: 심벌 테이블, 공통 루틴, 패스 2
(b) 2단계 어셈블리 중첩
문제점 2
- 커널(kernel) 보호
해결법
- 경계 레지스터 (boundary register) 사용
Kernel
Boundary address →
Boundary register
User program
낭비
Wasted space
문제점 3
- Low system resource utilization
- Low system performance
해결법
- Multi-Programming
Memory Allocation
Continuous Memory Allocation (연속할당)
- Uni-Programming
- Multi-Programming
* Fixed partition (FPM)
* Variable partition (VPM)
Non-continuous Memory Allocation (비연속할당)
- Next chapter!
Fixed partition Multiprogramming
고정
메모리 공간을 고정된 크기로 분할
- 미리 분할되어 있음
각 프로세스는 하나의 partition(분할)에 적재
- Process : Partiton = 1 : 1
Partition의 수 = K
- Multiprogramming degree = K
Pi→
| 0 | Kernel |
| a1 | partition-A (10MB) |
| a2 | partition-B (10MB) |
| a3 | partition-C (20MB) |
| a4 | partition-D (30MB) |
| a5 | partition-E (50MB) |
자료 구조의 예
| 0 | Kernel |
| a1 | partition-A (10MB) |
| a2 | partition-B (10MB) |
| a3 | partition-C (20MB) |
| a4 | partition-D (30MB) |
| a5 | partition-E (50MB) |
| 이름 partition |
start address |
크기 size |
current process ID |
other fields |
| A | a1 | 10MB | - | ... |
| B | a2 | 10MB | - | ... |
| C | a3 | 20MB | - | ... |
| D | a4 | 30MB | - | ... |
| E | a5 | 50MB | - | ... |
<Partition table or State table>
Fixed partition Multiprogramming
커널 및 사용자 영역 보호
| Kernel | |
| Boundary register-1 Boudary address |
partition-A |
| Boundary register-2 Boudary address |
partition-B |
| Boundary register-3 Boudary address |
partition-C |
| Boundary register-4 Boudary address |
partition-D |
| Boundary register-5 Boudary address |
partition-E |
Fragmentation (단편화)
Internal fragmentation
- 내부 단편화
- Partition 크기 > Process 크기
* 메모리가 낭비 됨
External fragmentation
- 외부 단편화
- (남은 메모리 크기 > Process 크기)
지만, 연속된 공간이 아님
* 메모리가 낭비 됨
Process 4
(30MB)
44MB
| Kernel | |
| 10MB | |
| 10MB | |
| Process 3 (15 MB) 5MB |
20MB |
| Process 2 (21 MB) 9MB |
30MB |
| Process 1 (40 MB) 10MB |
50MB |
Fixed Partition Multiprogramming
요약
- 고정된 크기로 메모리 미리 분할
- 메모리 관리가 간편함
* Low overhead
- 시스템 자원이 낭비될 수 있음
- ☆Internal/external fragmentation
Variable Partition Multiprogramming
초기에는 전체가 하나의 영역
프로세스를 처리하는 과정에서 메모리 공간을 동적으로 분할
☆ No internal fragmentation
internal fragmentation
Variable Partition Multiprogramming
VPM Example
- Memory space: 120MB
1. 초기 상태
2. 프로세스 A(20MB)가 적재 된 후
3. 프로세스 B(10MB)가 적재 된 후
4. 프로세스 C(25MB)가 적재 된 후
5. 프로세스 D(20MB)가 적재 된 후
6. 프로세스 B가 주기억장치를 반납한 후
7. 프로세스 E(20MB)가 적재 된 후
8. 프로세스 D가 주기억장치를 반납한 후
Variable Partition Multiprogramming
VPM Example
| Kernel |
| 120MB |
(a)
A enters (20MB)
-------------------->
| Kernel |
| A(20MB) |
| 100MB |
(b)
<State table>
| partition | start address | size | current process ID | other field |
| 1 | u | 120 | none | ... |
(a)
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 100 | none | ... |
(b)
Variable Partition Multiprogramming
VPM Example
| Kernel |
| A(20MB) |
| 100MB |
(b)
B enters (10MB)
-------------------->
| Kernel |
| A(20MB) |
| B(10MB) |
| 90MB |
(c)
<State table>
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 100 | none | ... |
(b)
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 10 | B | ... |
| 3 | u+30 | 90 | none | ... |
(c)
Variable Partition Multiprogramming
VPM Example
| Kernel |
| A(20MB) |
| B(10MB) |
| 90MB |
(c)
C enters (25MB)
-------------------->
| Kernel |
| A(20MB) |
| B(10MB) |
| C(25MB) |
| 65MB |
(d)
internal fragmentation X
<State table>
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 10 | B | ... |
| 3 | u+30 | 90 | none | ... |
(c)
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 10 | B | ... |
| 3 | u+30 | 25 | C | ... |
| 4 | u+55 | 65 | none | ... |
(d)
Variable Partition Multiprogramming
VPM Example
| Kernel |
| A(20MB) |
| B(10MB) |
| C(25MB) |
| 65MB |
(d)
D enters (20MB)
-------------------->
| Kernel |
| A(20MB) |
| B(10MB) |
| C(25MB) |
| D(20MB) |
| 45MB |
(e)
<State table>
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 10 | B | ... |
| 3 | u+30 | 25 | C | ... |
| 4 | u+55 | 65 | none | ... |
(d)
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 10 | B | ... |
| 3 | u+30 | 25 | C | ... |
| 4 | u+55 | 20 | D | ... |
| 5 | u+75 | 45 | none | ... |
(e)
Variable Partition Multiprogramming
VPM Example
| Kernel |
| A(20MB) |
| B(10MB) |
| C(25MB) |
| D(20MB) |
| 45MB |
(e)
B exits (10MB)
-------------------->
| Kernel |
| A(20MB) |
| 10MB |
| C(25MB) |
| D(20MB) |
| 45MB |
(f)
<State table>
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 10 | B | ... |
| 3 | u+30 | 25 | C | ... |
| 4 | u+55 | 20 | D | ... |
| 5 | u+75 | 45 | none | ... |
(e)
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 10 | none | ... |
| 3 | u+30 | 25 | C | ... |
| 4 | u+55 | 20 | D | ... |
| 5 | u+75 | 45 | none | ... |
(f)
Variable Partition Multiprogramming
VPM Example
| Kernel |
| A(20MB) |
| 10MB |
| C(25MB) |
| D(20MB) |
| 45MB |
(f)
D enters (15MB)
-------------------->
| Kernel |
| A(20MB) |
| 10MB |
| C(25MB) |
| D(20MB) |
| E(15MB) |
| 30MB |
(g)
<State table>
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 10 | none | ... |
| 3 | u+30 | 25 | C | ... |
| 4 | u+55 | 20 | D | ... |
| 5 | u+75 | 45 | none | ... |
(f)
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 10 | none | ... |
| 3 | u+30 | 25 | C | ... |
| 4 | u+55 | 20 | D | ... |
| 5 | u+75 | 15 | E | ... |
| 6 | u+90 | 30 | none | ... |
(g)
Variable Partition Multiprogramming
VPM Example
| Kernel |
| A(20MB) |
| 10MB |
| C(25MB) |
| D(20MB) |
| E(15MB) |
| 30MB |
(g)
D exits (20MB)
-------------------->
| Kernel |
| A(20MB) |
| 10MB |
| C(25MB) |
| 20MB |
| E(15MB) |
| 30MB |
(h)
<State table>
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 10 | none | ... |
| 3 | u+30 | 25 | C | ... |
| 4 | u+55 | 20 | D | ... |
| 5 | u+75 | 15 | E | ... |
| 6 | u+90 | 30 | none | ... |
(g)
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 10 | none | ... |
| 3 | u+30 | 25 | C | ... |
| 4 | u+55 | 20 | none | ... |
| 5 | u+75 | 15 | E | ... |
| 6 | u+90 | 30 | none | ... |
(h)
Variable Partition Multiprogramming
어디에 배치할 것인가?
| Kernel |
| A(20MB) |
| ① 10MB |
| C(25MB) |
| ② 20MB |
| E(15MB) |
| ③ 30MB |
(h)
P enters (5MB)
-------------------->
?
배치 전략 (Placement strategies)
First-fit(최초 적합)
- 충분한 크기를 가진 첫 번째 partition을 선택
- Simple and low overhead
- ☆공간 활용률이 떨어질 수 있음
first
0
운영체제 ↓
시작 주소 길이 1000
1000 16KB ---> 13KB를 요구 --------> 16KB 공백
5000 14KB
8000 5KB 사용 중
11000 30KB 5000
사용 가능 공간 리스트 14KB 공백
사용 중
8000
5KB 공백
사용 중
11000
30KB 공백
배치 전략 (Placement strategies)
first-fit vs
Best-fit(최적 적합)
- Process가 들어갈 수 있는 partition 중 가장 작은 곳 선택
- 탐색시간이 오래 걸림 → overhead!
* 모든 partition을 살펴봐야 함
- 장: 크기가 큰 partition을 유지 할 수 있음
- 단: 작은 크기의 partition이 많이 발생 x →
* 활용하기 너무 작은 ↓
0
운영체제
1000
16KB 공백
사용 중
시작 주소 길이 5000
8000 5KB ---> 13KB를 요구 --------> 14KB 공백
5000 14KB 1KB
1000 16KB 사용 중
11000 30KB 8000
사용 가능 공간 리스트 5KB 공백
(공백 크기 오름 차순)
사용 중
11000
30KB 공백
배치 전략 (Placement strategies)
Worst-fit(최악 적합)
- Process가 들어갈 수 있는 partition 중 가장 큰 곳 선택
- 탐색시간이 오래 걸림
* 모든 partition을 살펴봐야 함
- ☆장: 작은 크기의 partition 발생을 줄일 수 있음
- 단: 큰 크기의 partition 확보가 어려움 단점!
* 큰 프로세스에게 필요한
25KB
0
운영체제
1000
16KB 공백
사용 중
시작 주소 길이 5000
8000 5KB ---> 13KB를 요구\ 14KB 공백
5000 14KB \
1000 16KB \ 사용 중
11000 30KB \ 8000
사용 가능 공간 리스트 \ 5KB 공백
(공백 크기 오름 차순) \
\ 사용 중
\ 11000
\ ------> 30KB 공백
배치 전략 (Placement strategies)
Next-fit(순차 최초 적합)
- 최초 적합 전력과 유사
- State table에서 마지막으로 탐색한 위치부터 탐색
- ☆ 메모리 영역의 사용 빈도 균등화
- Low overhead
--↓
| ①
| ↓
| ②
| ↓
Variable Partition Multiprogramming
어디에 배치할 것인가?
| Kernel |
| A(20MB) |
| 10MB |
| C(25MB) |
| 20MB |
| E(15MB) |
| 30MB |
(h)
60MB 연속 X → External fragmentation issue
P enters (50MB)
-------------------->
?
External fragmentation issue
Coalescing holes (공간 통합)
인접한 빈 영역을 하나의 partition으로 통합
- Process가 memory를 release하고 나가면 수행
- Low overhead
| Kernel |
| A(20MB) |
| 10MB |
| C(25MB) |
| 20MB |
| E(15MB) |
| 30MB |
(a)
-------------------->
Process A releases memory
state table
| Kernel |
| 20MB |
| 10MB |
| C(25MB) |
| 20MB |
| E(15MB) |
| 30MB |
(b)
-------------------->
Coalescing holes
50MB P
| Kernel |
| 30MB 55MB |
| C(25MB) |
| 20MB |
| E(15MB) |
| 30MB |
(c)
Example 2
| Kernel |
| A(20MB) |
| 10MB |
| C(25MB) |
| 20MB |
| E(15MB) |
| 30MB |
(a)
-------------------->
Process C releases memory
| Kernel |
| A(20MB) |
| 10MB |
| 25MB |
| 20MB |
| E(15MB) |
| 30MB |
(b)
-------------------->
Coalescing holes
| Kernel |
| 30MB |
| 55MB |
| E(15MB) |
| 30MB |
(c)
State table
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 10 | none | ... |
| 3 | u+30 | 25 | C | ... |
| 4 | u+55 | 20 | none | ... |
| 5 | u+75 | 15 | E | ... |
| 6 | u+90 | 30 | none | ... |
(a)
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 10 | none | ... |
| 3 | u+30 | 25 | none | ... |
| 4 | u+55 | 20 | none | ... |
| 5 | u+75 | 15 | E | ... |
| 6 | u+90 | 30 | none | ... |
(b)
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 55 | none | ... |
| 3 | u+75 | 15 | E | ... |
| 4 | u+90 | 30 | none | ... |
(c)
Storage Compaction (메모리 압축)
모든 빈 공간을 하나로 통합
프로세스 처리에 필요한 적재 공간 확보가 필요할 때 수행
High overhead
→ 자주 X
→ 일정시간, 요청이 있을 때
- 모든 Process 재배치 (Process 중지)
- 많은 시스템 자원을 소비
Example
| Kernel |
| A(20MB) |
| 10MB |
| 멈춘다! C(25MB) |
| 20MB |
| 멈춘다! E(15MB) |
| 30MB |
(a)
-------------------->
Storage compaction
Example
| Kernel |
| A(20MB) |
| C(25MB) |
| E(15MB) |
| 60MB |
(b)
<State table>
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 10 | none | ... |
| 3 | u+30 | 25 | C | ... |
| 4 | u+55 | 20 | none | ... |
| 5 | u+75 | 15 | E | ... |
| 6 | u+90 | 30 | none | ... |
(a)
| partition | start address | size | current process ID | other field |
| 1 | u | 20 | A | ... |
| 2 | u+20 | 25 | C | ... |
| 3 | u+45 | 15 | E | ... |
| 4 | u+60 | 60 | none | ... |
(b)
요약: Continuous Memory Allocation
Uni-programming
- Simple
- Fragmentation problem
a 1GB + -
new
z → malloc 동적 → expensive
new a 할당
"Memory pool"
copy DA
P 1GB ↓
| 1GB
↓ ←OS
|a(10MB)
FPM | P
state | b
table | ↑요금
VPM | z | 반납
fragmentation
Fixed partition multi-programming (FPM)
Variable partition multi-programming (VPM)
- Placement strategies
* First-fit, Best-fit, Worst-fit, Next-fit
- External fragmentation issue
* Coalescing holes
* Storage compaction
'프로그래밍 공부 > OS' 카테고리의 다른 글
| 10 가상 메모리 관리 (0) | 2024.02.07 |
|---|---|
| 9 Virtual Storage (Memory) (0) | 2024.02.05 |
| 7 Deadlock (0) | 2024.01.31 |
| 6 프로세스 동기화 & 상호배제 (0) | 2024.01.24 |
| 5 프로세스 스케줄링 (0) | 2024.01.22 |