메모리 관리 측면에서, OS가 어떤 역할을 하고, 어떤 설계를 가지고 있는지.
Memory Access
메모리 접근은 어떻게 일어나는가?
컴구 복습 : 하드웨어 관점에서는 이러한 메모리 액세스가 일어난다.
일반적인 인스트럭션 수행 과정:
1.
Fetch : 메모리(Text 부분)에서 CPU 내부의 PC 레지스터로 인스트럭션을 가져옴.
2.
Decode : 단순히 바이너리일 뿐인 인스트럭션을 해석.
3.
Fetch Operands : Argument에 메모리값이 필요할 경우 메모리에서 또 가져옴. 일어날 수도 있고 아닐 수도 있음.
4.
Execute : 실행!
5.
Store : 레지스터에 결과값을 저장.
그러면 메모리 액세스는 언제 발생하는가? → 총 2회 발생할 수 있다.
•
Fetch : 반드시 발생. 메모리에서 PC로 인스트럭션을 가져와야 한다.
•
Fetch Operands : Argument에 따라 메모리 접근이 또 필요할 수 있음.
근데 매 인스트럭션 수행마다 메모리 액세스를 해야 하는가?
→ 캐시를 쓰자!
메모리 액세스의 특징:
•
프로그램은 실행되려면 메모리에 로드되어야 한다.
◦
CPU가 접근할 수 있는 저장 공간은 메모리, 레지스터 두 개밖에 없다. 디스크에 직접 접근할 수 없다!
◦
레지스터 접근 : CPU 사이클 1회
◦
메모리 접근 : CPU 사이클 여러 번.
▪
CPU 밖으로 나가서 메모리 버스 타고 읽어서 다시 오는 경우인데, CPU가 잠깐 멈출 수밖에 없다. (stall)
•
메모리는 Context oblivious하다.
◦
메모리 유닛(메모리 + 컨트롤러)에는 접근해야 할 메모리의 주소들이 계속 stream으로 들어온다.
◦
메모리 유닛 입장에서는, 어떻게 발생한 요청인지, 그 주소에 있는 데이터가 어떤 내용인지 신경쓰지 않는다. Context를 고려하지 않는다.
Memory Protection:
•
한 프로세스가 다른 프로세스의 메모리 영역에 접근할 수 없도록 해야 한다. → 메모리 보호.
•
메모리 유닛은 이런 걸 신경쓰지 않는다. OS가 해 준다.
•
한 예시 : base register, limit register 사용.
◦
두 레지스터로, 프로세스가 사용하는 메모리 주소 범위를 제한한다. 두 레지스터값은 OS가 관리한다.
◦
base register : 이 프로세스가 사용하는 메모리 최초 주소.
◦
limit register : 주소 범위 길이.
◦
CPU에서 생성된 주소가 base ≤ Address < base+limit 인지 체크. 이 프로세스가 생성하는 주소는 항상 이 범위 내에서만 있어야 한다.
Address Binding
주소 연결 : 프로그램이 메모리에 로딩될 때, 어느 주소에 로딩되는가?
•
Program Lifecycle:
◦
프로그램은 디스크에 바이너리 파일로 존재한다.
◦
프로그램이 input queue에서 선택되고, 메모리에 로드된다.
◦
끝나면 메모리 해제된다.
•
OS는 프로그램이 메모리의 특정 물리적 주소에 로드될 수 있도록 할 수 있다.
◦
컴파일러는 symbolic address(프로그래밍할 때 선언했던 변수들)을 모두 relocatable address로 바꾼다.
▪
변수 → (이 프로그램의 시작으로부터 14바이트 떨어진 곳)
▪
고정된 주소값이 아닌, relocatable. 상대 주소.
◦
링커, 로더는 relocatable address를 absolute address로 바꾼다.
▪
(이 프로그램의 시작으로부터 14바이트 떨어진 곳) → 74014
▪
relocatable address에 프로그램의 시작 주소를 넣어서 절대 주소로 결정.
Address Binding Time
프로그램의 변수들의 주소가 결정되는 시간이 세 종류가 있다.
•
Compile time binding (컴파일러) : 컴파일할 때 이 프로그램이 메모리의 어느 주소에 로드될 지 이미 결정됨. 프로그램은 특정 메모리의 물리적 위치로만 로딩되게 된다.
◦
실행될 때 비어있는 메모리 주소로 로드되는 게 바람직한데, 그 위치에 다른 프로그램이 있다면 실행을 못 한다. 새로운 주소로 새로 컴파일해야 한다.
•
Load time binding (링커, 로더) : 컴파일 타임에서는 Relocatable address(상대 주소)로만 채우고, 로드 과정에서 프로그램이 어디에 로드될 지 결정되면, Relocatable 주소에 프로그램 주소값 넣어서 싹 다 절대주소로 만드는 것.
•
Execution time binding (메모리에서 실행 중) : 실제로 실행될 때가 되어서야 프로그램의 주소값이 결정된다.
◦
하드웨어 지원이 필요. (base, limit 레지스터 등)
Logical vs. Physical Address Space
•
Physical Address : 메모리 유닛 하드웨어에서 보는 주소. 물리적인 주소.
•
Logical Address (Virtual Address) : 실제 메모리 하드웨어만큼의 공간이 아님. CPU 내부에서만 사용되는 주소. 실제 주소가 아님. CPU 내부에서는 이만큼이 존재한다고 가정하고 쓰는 것. 논리적인 주소.
Remind: Address binding time
•
Compile time binding, Load time binding
◦
결과물은 실제 주소이다. Logical, Physical 주소 구분이 없다.
•
Execution time binding
◦
실행되기 전에는 Logical address, 실행되고 나서야 Physical address로 바뀐다.
•
Logical-address space : 프로그램에서 쓰는 Logical address들의 집합
•
Physical-address space : 각 Logical address들에 해당하는 Physical address들을 모두 모은 집합
MMU (Memory Management Unit)
•
MMU : Virtual address(Logical address) → Physical address 변환.
◦
CPU에서 나오는 주소는 모두 Logical address이다.
◦
이 주소가 MMU로 넘어가서, Physical address로 변환되어서, 메모리로 가서 내용 가져오는 것.
•
MMU의 간단한 예시:
◦
MMU에는 Relocation register가 있다. → 프로그램 실행될 때 Relocation register 값이 정해진다. Context switch 등 프로세스가 바뀌면 값이 바뀐다.
◦
MMU에서는 단순히 Logical address에 Relocation register값 더하면 그냥 Physical address 된다.
•
CPU 내부에서, CPU에서 돌고 있는 사용자 프로그램은 Physical address를 알 수 없다. 프로그램이 다루는 주소값은 모두 논리 주소이다.
•
MMU를 거쳐야만 물리 주소가 만들어진다.
Dynamic Linking
•
Static Linking : 프로그램 빌드할 때, 라이브러리 바이너리들을 다 copy해서 하나의 바이너리 프로그램으로 만드는 것.
•
Dynamic Linking : 빌드할 당시에는 라이브러리 바이너리들이 붙지 않는다. 프로그램 내에는 해당 라이브러리 코드가 없다. 프로그램에서 외부 라이브러리 함수를 호출할 때, 그제서야 바이너리를 찾아서 그걸 호출하는 것. → Execution time 전까지 Linking을 미룬다.
◦
stub : 라이브러리 함수가 필요한 메모리 주소에 stub이 존재하다가, 라이브러리 함수가 호출되면, 자기 자신을 라이브러리 루틴 주소로 Replace한다.
•
장점
◦
전체 프로그램을 새로 빌드할 필요가 없다. 라이브러리를 새로 업데이트했다면? Dynamic Library 자체만 새로 빌드해서 갖다 쓰면 된다.
•
단점
◦
새 버전이 불안정하므로 버전업을 원하지 않을 때도 있다. 특정 버전의 라이브러리만 호출하고 싶을 때가 있다. → 여러 버전을 메모리에 올려두고, 사용자가 버전을 선택할 수 있도록 하는 식으로.
•
Dynamic Linking은 OS의 도움이 필요.
◦
라이브러리 코드가 다른 Address space에 존재할 경우, 프로세스 간 메모리 경계를 뛰어넘어야 할 필요가 있다. OS가 액세스를 허용해줘야 한다.
Swapping
프로세스마다 자신의 Virtual memory space가 있다. 프로세스는 4GB의 메모리 공간으로 인식하지만, 실제 물리 메모리에 할당되는 공간은 매우 작다. 그래서 프로세스가 100개 넘게 돌아갈 수 있는 것. 그런데 가상 메모리를 사용함에도 물리 메모리의 한계에 다다른다면?
→ Swapping : 메모리에 로드된 프로세스 중 하나를 골라서, 그 프로세스의 메모리 내용을 모두 디스크에 옮기고, 다른 프로세스를 올린다.
•
Swap out, Swap in : 프로세스를 디스크로 내리고, 디스크의 메모리 내용을 다시 메모리로 올리고.
•
Roll out, Roll in : Priority scheduler에서, lower priority 프로세스를 내리고, higher priority 프로세스를 올리고.
어디에 Swap in될 지는 Binding time에 따라 또 다르다.
•
Compile time binding, Load time binding : 프로세스의 메모리 위치는 고정. Swap in이 일어나도 고정된 그 자리에 들어간다.
•
Execution time binding : Swap in할 때, 메모리 비어 있는 어디든 프로세스를 올릴 수 있다. 더 flexible하다.
Ready Queue에는 PCB들이 있는데, 하나씩 꺼내와서 Context Switch할 때 그 PCB 프로세스가 이미 Swap out된 애일 수 있다. → 디스크 가서 걔 메모리 내용 읽어와서 올린다.
Context Switch Time Including Swapping
스와핑은 Disk를 왔다갔다 하는 작업이다. Context Switch Time이 굉장히 높은 작업이다.
그 중에서도 Transfer time이 major이다. Swap in, Swap out 할 때 디스크 갔다오니까.
프로세스 100MB, HDD 전송률 50MB/s → Transfer time 2s.
swap out time + swap in time = 4s.
Context Switch Time : 프로세스 전환하는 타임이니까 Swapping에만 4초다.
함부로 스와핑할 수 없는 경우도 있다.
•
I/O를 기다리는 프로세스들은 Swap out을 함부로 할 수 없다.
◦
I/O 완료됐는데, 그 메모리에 다른 프로세스가 올라와있다면? 잘못된 메모리에 I/O 값을 쓰게 되는 것.
◦
→ Pending I/O 프로세스가 Swap out되었다면? I/O가 완료되면 값을 Kernel buffer에 임시로 담았다가, 그 프로세스가 Swap in되면 복사해주자.
▪
→ Double buffering! I/O값을 Kernel buffer에 한번 복사하고, 프로세스 올라오면 그 프로세스 메모리에 한번 더 복사하고.
Contiguous Memory Allocation
연속적 메모리 할당 (요즘엔 안 쓴다)
•
Memory Partition
◦
OS는 낮은 메모리 주소에, User process는 높은 메모리 주소에 할당한다.
◦
OS 포함, 각 프로세스 하나는 연속적인 메모리 주소를 차지한다.
◦
Contiguous memory allocation에는 두 가지 방법이 있다.
▪
Fixed-sized partitions : 각 파티션 크기가 고정되어 있다. 프로세스 하나가 파티션 하나에 할당되면, 그 프로세스는 해당 파티션 전체를 사용한다. (프로세스 자체가 파티션의 얼마를 사용하든 상관없다. 효율적이지 않다.)
▪
Variable partition size : 메모리의 어느 부분이 할당되었는지를 기록하는 표가 있다.
•
hole : 메모리의 빈 공간.
•
새 프로세스가 들어오면, 이 프로세스가 할당될 빈 공간을 어떻게 찾아야 하는가? 할당할 수 있을만큼 충분히 큰 hole이어야 한다.
◦
First fit : 처음 나오는 충분히 큰 hole에 할당한다.
◦
Best fit : 충분히 크면서 가장 작은 hole에 할당한다.
◦
Worst fit : 가장 큰 hole에 할당한다.
세 방법 모두 장단점이 있다.
보통 First fit, Best fit이 Worst fit보다는 좋다.
•
Memory Protection
◦
Remind: base register(=relocation register), limit register.
◦
CPU에서 논리 주소가 나오면, limit register값보다 작은지 보고, 맞다면 거기다 relocation register 값 더한 게 물리 주소가 되므로 메모리에 접근하면 된다.
◦
프로세스가 다른 프로세스의 메모리 영역에 접근하려 하면, MMU에서 에러를 뱉는다.
Fragmentation
•
External fragmentation
◦
아까 봤던, 너무 작아서 못 쓰는 작은 hole들이 생기는 것. 할당되지 않은 작은 조각 부분들.
◦
50-percent rule : First fit의 경우, N개의 블록이 할당되었을 때, 0.5N개의 블록(할당된 부분 중 절반)이 External fragmentation 때문에 손실된다. → 전체 메모리의 1/3이 못 쓰게 된다.
◦
→ Compaction : 작은 hole들을 하나의 큰 hole로 모으자. 단, Execution time binding일 때만 가능하고, 메모리를 이동시키기 위해 메모리 계산 등 Overhead 존재.
•
Internal fragmentation
◦
한 프로세스에게 할당된 메모리 영역 내에서도, 프로세스가 사용하지 않는 부분이 있다. 주어진 모든 부분을 사용하지는 않는다.
Segmentation
모던 컴퓨터들은 Contiguous memory allocation 안 쓴다. Segmentation과 Paging을 쓴다.
•
Segment
◦
길이 다양
◦
프로그래머 입장에서, 모든 오브젝트는 다양한 크기의 순서 없는 세그먼트들이다. 프로그래머 관점에서, 하나의 프로세스를 여러 Segment로 나누자.
◦
한 Segment 내의 element들은 세그먼트 시작으로부터의 offset으로 구분.
•
Segmentation : Segment의 개념을 사용한, 메모리 관리 Scheme.
◦
논리 주소는 segment의 모음
◦
각 세그먼트에는 번호가 붙어서, 주소를 S:D로 나타낼 수 있다. S번 segment의 D번 offset.
Segmentation HW
CPU에서 나오는 논리주소를 S:D로 보자.
주소는 32비트이므로, 앞의 몇 비트를 segment 번호로, 나머지 몇 비트를 segment 내의 offset으로.
1.
S는 segment table로 가서 S번째 행을 본다. 해당 segment의 limit register, base register값이 저장되어 있다.
2.
D를 이 segment의 limit register 값과 비교한다. limit은 범위니까 D가 얘보다 작아야 한다.
3.
조건에 맞으면, D에 base register 더한 값이 실제 주소이므로, 더해서 실제 메모리로 접근.
Paging
•
Page : 메모리의 고정된 크기 (4KB) 블록.
•
Paging : 프로세스를 페이지 단위로 자른다. 프로세스의 물리 주소가 연속되지 않아도 되게 함 → External fragmentation 방지
•
Page table : 페이지 번호 당 프레임 번호 매핑.
Paging에서는 논리 메모리의 블록을 Page라 하고, 물리 메모리의 블록을 Frame이라고 한다.
Segmentation과 비슷하게, 논리 주소를 page number (p), page offset(d)로 나누자.
Segment : 길이 가변. 다양한 길이.
Page : 4KB 고정.
논리주소 전체 비트가 m이고, page offset (d) 비트가 n이면, page number(p) 비트가 m - n.
1.
논리 주소를 p:d로 나누자.
2.
p로는 page table에 가서 p비트에 해당하는 위치의 frame값을 찾아온다. → f.
3.
d는 그대로 가져와서 f:d 주소를 구성하고, 이 주소로 실제 물리 메모리의 frame에 접근한다.
Paging Example
1페이지는 4바이트, 메모리는 32바이트라 하자. → 메모리가 총 8 Frame으로 등분된다.
m = 4, n = 2 → m - n = 2. 전체 비트 4비트 중 p 2비트, d 2비트.
•
논리 주소 13 (1101)을 물리 주소로 바꿔라!
◦
1101 중 앞 11은 page number, 뒤 01은 page offset.
◦
page table에서 3 (11)은 2번 프레임이므로 f는 2 (10)
◦
f랑 d 붙이면 1001, 물리 주소 9.
Fragmentation in Paging
External fragmentation 문제는 거의 사라졌지만, Internal fragmentation 문제가 생겼다.
•
OS는 프로세스에게 4KB 페이지를 주지만, 프로세스는 2000바이트만 사용한다면? 2096바이트는 낭비된다. 프로세스에게 할당된 마지막 페이지의 일부가 남는다.
•
→ 페이지 사이즈를 줄여서 Internal fragmentation을 줄일 수 있다.
◦
페이지 사이즈가 4KB가 아니라 1KB라면, 프로세스가 2000바이트 사용해도 두 페이지 주고 96바이트만 낭비된다.
◦
하지만, 페이지 수가 늘어나므로 page table 사이즈가 커진다.
HW Support for Paging
예전에는 페이지 테이블 저장하는 레지스터가 CPU 내에 있었지만, 요즘은 페이지 테이블 자체는 메모리에 저장하고, CPU에 페이지 테이블을 가리키는 4바이트 레지스터 PTBR(Page Table Base Register)을 추가함
TLB
TLB : Translation Look-aside Buffer
•
Page table translation을 위한 캐시 메모리.
•
Page table entry (key: page number, value: frame number) 캐싱.
•
사이즈 작음. 32~1024개 엔트리 저장.
How it works?
•
p를 보고 page table로 가면서, 동시에 TLB도 본다.
•
TLB에 (p, f) 쌍이 있다면, TLB에 있는 값을 쓰고, 아니면 page table 가서 frame number를 가져온다.
•
TLB 보러 가는 작업과 page table 보러 가는 작업은 병렬로 일어난다.
•
TLB 접근은 1사이클, page table 접근은 100사이클
TLB도 결국 캐시다!
Terminology, Concepts
•
TLB miss : TLB에서 page number p를 못 찾은 경우. → 메모리로 가서 가져와서 TLB에 넣는다.
◦
Evict (Kick out) : TLB가 꽉 찼으면, 하나 빼야 한다. 알고리즘에 따라서 하면 됨.
◦
Wired down (Pinned) : Kick out되지 않는 엔트리.
•
TLB는 Context switch가 일어날 때 flush된다.
◦
새 프로세스가 들어오면, 새 Page table이 사용되므로, 이전의 캐시 결과는 쓸모없다.
◦
Context switch 직후, TLB를 다시 채우는 데 시간이 걸린다.
◦
근데 매번 flush하고 다시 채우지 않고, 프로세스끼리 공유하고 싶다면?
▪
ASIDs (Address-Space IDs) = pid
▪
각 TLB entry에 ASIDs를 저장해서 flush되지 않도록 한다.
Effective memory access time
•
Hit ratio : 모든 메모리 주소 Translation에 대해, Page number가 TLB에 있을 확률
Page Protection
Page table의 추가 Property. 각 entry에 bit 하나를 더하자.
•
Valid/Invalid bit : valid면 유효한 캐시값. invalid면 못 쓰는 값. 쓰면 안 된다.
◦
페이지를 부분적으로 쓰더라도, 그 페이지 넘버에 대해 valid라면 써도 된다.
•
RW/RO bit : 그 entry가 업데이트될 수 있음 / 읽기만 가능.
PTLR : Page Table Length Register
•
페이지 테이블 길이
Shared Pages
•
Reentrant code (실행 중에 변경되지 않는 코드)는 여러 프로세스끼리 공유될 수 있다.
•
각 프로세스마다 Page table이 있는데, 서로 다른 page table의 entry가 같은 frame을 가리킬 수 있다.
Page Table Structure
페이지 테이블은 메모리에 저장된다. 그런데, 얼마나 큰가?
•
페이지 테이블 사이즈는?
◦
32비트 시스템에서, 1페이지 4KB(=4096=) 일 때, 페이지 테이블 사이즈는?
◦
→ 12비트를 page offset(d)로 써야 하니까, 20비트를 page number에 사용 가능하다.
◦
→ 총 개 페이지 사용 가능.
•
페이지 테이블 엔트리 하나는?
◦
결국 주소값이므로 32비트 = 4바이트.
메모리에 다 때려박기에는 너무 크다.
Hierarchical Paging
페이지 테이블을 두 단계로 나누자.
•
outer page table (p1) : 1024개의 엔트리가 있고, 각 엔트리는 다음 페이지 테이블을 가리킨다.
•
page of page table (p2) : 여기도 1024개 엔트리가 있고, 각 엔트리는 물리 메모리의 프레임을 가리킨다.
•
비트가 20 | 12 나뉘었던 게 10 | 10 | 12 나뉜다.
•
각 트리 레벨에 대해 1 메모리 액세스이므로 300사이클.
64비트 주소에 대해서는?
7 | 9 | 9 | 9 | 9 | 9 | 12
트리 따라가보면 메모리 액세스 6번 나오는데, 600사이클. 비효율적이다.
Hashed Page Table
방금 봤던 Hierarchical page table (트리 형태의 페이지 테이블 구성)이 아니라, 해시를 사용해서 해당 페이지 번호의 프레임 번호를 바로 찾는 방식.
•
보통 32비트 이상의 주소 체계에서 사용. (Remind: 주소 비트 수가 커지면 Hierarchical paging은 비효율적)
•
p:d에서 page number를 해싱해서, hashed page table에서 해당 해시값의 linked list를 쭉 보면서 page number를 비교, 일치하면 그에 해당하는 frame number 가지고 옴.
•
그냥 page number를 해싱해서 접근하는 것.
Inverted Page Table
32비트에서 프로세스마다 논리 주소는 4GB인데, 모든 프로세스가 자신만의 페이지 테이블을 가지려면 너무 크다.
→ 프로세스마다 페이지 테이블을 만드는 게 아니라, 물리 메모리를 기준으로 페이지 테이블을 만들자.
→ 시스템에 페이지 테이블이 딱 하나 존재한다.
•
slow search : 주소를 pid | p | d 나눠서, pid로 linear search해야 한다.
◦
→ pid를 hashing해서 한번에 찾으면? hash function collision 일어나면 또 그대로 O(N)이다.
•
shared page 구현이 어렵다.