Logical address space: 프로세스가 자신의 메모리를 바라보는 관점에서의 주소 공간 프로세스는메모리를 가상 메모리 공간으로, 즉 본인의 실제 물리 메모리 공간보다 더 크다고 생각한다!
Address Generation
코드는 컴파일되어 어셈블리어로 번역된다. 이때 적재될 메모리 주소는 어디가 될지 모르므로 보통 0번지의 값을 가진다.
실제 메모리는 1000번지부터 적재되므로 jmp 175 코드는 실제 메모리의 175로 가면 안되고 1175로 가야 하므로 1175로 바꿔줘야 한다.
Multiple Programs Without Memory Abstraction
단일 프로그램은 하나씩 할당하여 충돌이 발생하지 않을 수 있지만, 여러 개 돌리면 메모리 공간 어디에 적재될지 모르므로 문제가 발생한다.
-> relocation이 필요하다!
Partioning
미리 메모리를 여러 개의 partition으로 쪼개 놓아 relocation이 필요 없도록 하는 방법이다.
Equal-size partitions(모든 파티션이 동일한 크기를 가짐)
Unequal-size partitions : 파티션 별로 Queue가 존재한다.
: 처음부터 어느 파티션에 들어갈지 시작 주소를 다 알고 있다면 relocation은 필요하지 않다.
Placement with Partioning
물리 메모리는 고정된 크기의 파티션으로 나누어져 있다.
Internal fragmentation(내부 단편화 - 낭비되는 공간 O), Inefficient와 같은 문제점이 존재한다.
- 컴파일 시에는 항상 시작 주소를 0번지로 하고, 실행 시에 실행마다 주소를 바꾸어줄 필요가 있다. -> Dynamic Program Relocation!
Dynamic Program Relocation
CPU는 실시간으로 코드의 주소와 Limit register값을 비교하고 값보다 작다면 Base register의 값을 더해서Relocate 한다! (Logical Addresses -> Physical Addresses)
Dynamic Partitioning
파티션이 나누어져있을 때는 파티션마다 Q가 존재하였지만(a), 0번지를 기준으로 실행파일을 생성한다면 비어있는곳마다 실행하므로 노는 공간이 줄어들게 되고, 하나의 Q로 실행한다.(b)
-> 미리 쪼개지 말고동적으로 파티셔닝 한다!
파티션은 가변크기의 길이와 숫자를 가진다.
프로세스는 메모리가 요구하는만큼 할당되어야 한다.
한 블록에서 모든 메모리를 순서대로 변환할 수 있도록 compaction을 사용해야 한다.??
동적 파티셔닝의 예시.
- 멀티프로세싱: 메모리에 여러 개의 프로세스를 넣고 실행하는 것
- a~d: 메모리 공간에 프로세스 1부터 3까지 적재된다.
- e: 프로세스 2가 입출력 요구 등을 이유로 잠깐 멈추면 메모리 공간에서 쫓아낸다.
- f: 빈 공간에 프로세스 4가 들어와 적재된다.
-> 다음과 같은 과정을 거치며 동적 파티셔닝이 일어나는데, 이때 중간중간 빈 공간(h)이 생기게 되어 메모리 효율이 떨어지게 된다. 이를메모리 단편화, 즉fragmentation이 일어난다고 한다.
Dynamic Partitioning Placment Algorithm
Best-fit Algorithm
First-fit Algorithm
Next-fit Algorithm
Worst-fit Algorithm
각 상황에 따라 좋은 알고리즘이 달라지므로, 각 알고리즘 중 어떤 알고리즘이 좋을지는 모른다. 케바케.
First-Fit: 항상 처음부터 살펴보다가 적재 가능한 곳이 있으면 발견한 처음 공간에 넣는다.
Best-Fit: 전체를 다 살펴보고, 가장 딱 들어맞는 크기의 공간에 넣는다.
Next-Fit: First-Fit과 유사. 한번 검색하면 마지막 검색위치를 기억하여 다음 검색 시에는 이 지점부터 찾기 시작한 후 발견한 공간에 넣는다.
Worst-Fit: 전체를 다 살펴보고, 가장 큰 공간에 넣는다.
-> 전체를 다 살펴보면 오래 걸리게 되고, 처음부터 찾아 바로 넣으면 윗부분의 메모리 사용도가 높아지며 빈 공간이 생길 수 있다는 단점이 존재한다.
모든 알고리즘은 장단점이 모두 존재하기 때문에 상황에 따라 달라진다!
Solutions for Fragmentation
Coalescing
Program A가 작업이 종료되면 빈공간이 생기는데, 이를 다른 빈 공간과 통합(Coalescing)하는 방법이다.
CPU는 2K와 5K를 통합하지 않는다면 각각 따로 생각하기 때문에 통합이 필요하다.
Compaction
메모리에서 사용되지 않는 공간(unused) 모두를 하나로 크게 통합하는 방법이다.
Compaction의 문제점
- optimal compaction 알고리즘을 찾기 어렵다.
- compaction 하는 동안 시스템은 정지한다.
Compaction을 수행하는 경우
- 메모리 utilization(효율)이 낮은 수치(75% 정도)로 떨어질 때
- memory allocation(할당) 실패 시
- 주기적으로
생각할때는 쉽게 동작하는 것처럼 보이지만 실제로 구현 시 어려움이 있다.
Swapping
기술이 발전하며 HDD의 속도가 빨라지게 되면서 메모리 사이즈보다 더 많은 프로세스를 넣고 실행하기 위해서 Swap In/Out개념을 도입하였다.
- 메모리에프로세스를 많이 넣으면 넣을수록 CPU의 활용도. 즉 Utilization이 높아진다.
- c: 프로세스 A.B.C 모두 I/O요구 등의 이유로 중단된다면 이 중 하나인 A를 골라서 Swap out 한다; 프로세스의 메모리 데이터 그대로 - HDD의 swap영역에 넣고 프로세스를 쫓아낸다.
- 이렇게 Swap in/out을 하면 더 많은 프로세스를 사용할 수 있고 Utilization이 높아진다.
- 현재도 Swap을 사용하는데, CPU Utiilization을 높이려기보다는 threashing 현상으로 시스템이 다운되는 것을 방지하기 위해 사용한다.
+) 프로그램 수행 이미지의 크기가 변하는 경우. 사용 가능한 메모리 공간보다 더 커지게 되면 swapping으로 잠시 디스크로 옮기고 큰 공간이 나오게 된다면 그때 수행된다.
Overlay
램보다 프로그램 크기가 클 때 수행하는 방법. Overlay기능을 켜고 작업을 수행할 수 있다.
Program 실행 시 함수 별로 모듈을 생성한다.
프로그램에 작성되어 있는 오버레이 매니저 코드가 실행된다.
A를 수행하다 B함수가 호출(call)되면
매니저가 확인 후에 A를 쫓아내고 B를 실행한다.(overlay)
Memory Management with Bitmaps
a: 메모리 공간. A~E까지 5개의 프로세스가 적재되어있고, 3개의 비어있는 공간이 존재한다.
b: bitmap. 1이면 사용 중이고 0이면 비어있음을 나타낸다.
c: b를 linked-list로 표현한 방식. P면 사용 중, H면 비어있음을 나타내고 H 5 3이면 5번부터 3개의 상태가 비어있음을 나타낸다.
Virtual Memory
- CPU는 메모리를 공간이 무한한 Logical Memory로 인식한다; 가상 주소와 실제 주소를 분리하여 생각한다.
- 가상 주소 공간에서 프로그램을 실행하고 이는 실제 DRAM에 적재되며, 실제 주소로 변환하여 실행하도록 한다.
Virtual Address Space
: 모든 프로세스는 위 가상공간 모두를 혼자 다 쓴다는 환상을 가지고 실행한다.
- 이 개념을 통해 작은 DRAM보다 size가 더 큰 프로세스를 넣고 실행할 수도 있다. 이는 필요 부분만 DRAM에 적재하고 나머지는 DISK에서 Swap 하여 실행한다.
Paging(Virtual memory) 기법
- Virtual Address Space을 동일한 크기인Page단위로 쪼갠다.
- Virtual Address(VA): 20bit는 페이지 번호로, 12bit는 페이지 안의 offset으로 쪼개어 할당한다.(p, o)
- Physical Memory는 동일한 크기인Frame단위로 쪼갠다.
- Physical Address도 마찬가지로 프레임 번호와 offset으로 쪼개어 할당한다.(f, o)
- (f, o) = (3, 6)이면 3번째 frame의 6번째 offset을 나타낸다.
Page는 frame으로 매핑된다. page의 일부는 DRAM으로, 일부는 Disk의 Swap영역에 적재된다.
가상공간을 페이지 단위로 쪼개어 특정 프레임에 넣고 실행하겠다는 것이페이징 처리이다.
Virtual Address Translation
(p, o) 페이지가 (f, o) 프레임에 적재될 때 가상 주소는 물리 주소로 실시간으로 변환되어 access 하도록 구현되어야 한다.
이는 CPU 내부의 Page Table을 통해 수행되는데, 과정은 다음과 같다.
(p, o) 가상 주소가 나오면
Page Table의 p번째 엔트리를 찾는다.
찾아보니 f가 적혀있기 때문에
(f, o)을 Access 한다.
Page TableStructure
Page Table의 contents
- Flags : valid/invalid(resident) bit, dirty bit, reference(clock or used) bit
- page frame number
- PTBR(Page Table Base Register)이 Page Table을 가리키게 한다.
- Flag 중 valid bit가 1이면 frame을 access 하고, 0이면 CPU가 스스로 해결하지 못하므로 page interrupt를 걸어 jump 한다. (OS가 swap영역에서 PT에 세팅하여 1로 변환해준다)
- valid bit: 메인 메모리에 해당 페이지가 존재하는가?
- Page Table은 2^20개의 페이지(1MB)가 존재하며 한 entry의 크기는 4kb이므로 프로세스마다 4MB의 Page Table이 필요하다.
Translation Lookaside Buffer(TLB - 명칭 외우기!!)
가상 메모리는 PT entry 접근 1번, 물리 주소 접근 1번 총 2번의 접근이 필요하기 때문에(물리 메모리 : 1번만 접근) 메모리 효율이 2배로 떨어진다는 문제점이 있다.
이를 해결하기 위해 CPU의 Cache와 같은 기능을 가지는 Translation Lookaside Buffer(TLB)를 도입하였다.
- 최근에 Access 한 PT entry만 caching 하고 있자!
동작 과정- CPU 내부 회로에서 실시간으로 동작한다.
가상 주소 변환 시 우선 TLB에서 엔트리를 찾는다.
TLB에 없다면 PT에 접근(Access)하여 찾는다.
PT에서 찾았다면(접근했다면) TLB에 넣는다.
문맥 교환 시 Valid bit의 초기 상태는 모두 0이다.(Invalid)
TLB에서 못 찾으면 PT를 거쳐서 변환한다
한번 Access 하면 TLB에 적고, valid bit를 1로 바꾼다.
Page Table의 valid bit: 1일 때는 존재한다는 것이고, 0일 때는 Disk의 swap영역에 존재한다는 뜻이다.
문맥 교환 시 TLB의 Valid bit는 0으로 CLEAR 된다. 이는 TLB히트율이 잠시 떨어진다 할 수 있다. (물론 TLB가 다시 채워지면 높아진다)
Protection and Sharing
Process A, B의 데이터 Page Table은 서로 다르지만 내부 코드 부분의 f=4는 동일하다. f=4에 해당하는 프레임은 메모리에 따로 적재하지 않고 똑같은 프레임을 가리키게 하는데, 이를 Sharing 한다고 한다.
하지만 이는 Read-only모드일 때는 가능하지만, Write 명령이라면 OS에 부탁하여 물리 메모리를 copy 하여 두 개의 영역에서 write 하도록 한다.
++ OS는 각 프로세스마다 Page Table 을 유지하도록 한다.
Page Table
Assignment of Process Pages to Free Frames
- A process의 0번 페이지, 1번페이지, ... , B process의 0번 페이지, ...를 메모리에 적재한다.
- 각 프로세스는 적재될 때 빈 프레임이면 어디든 적재될 수 있다. (process D-꼭 연속적으로 적재될 필요는 없다!)
- Process B가 수행 종료되었으므로 PT의 valid bit는 모두 0(N)으로 된다.
- 프로세스를 페이지 별로 나누어 메모리에 적재하므로메모리 단편화(Fragmentation)가 일어나지 않는다!(페이지 내에서 사용되지 않는 공간은 존재할 수는 있다.)
Logical-to-Physical Address Translation of Paging. CPU 내부의 하드웨어 회로에 의해 빠르게 진행된다.
Virtual Memory - Paging
CPU에서 가상주소는 MMU chip(변환회로)을 통해 가상주소를 물리주소로 바꾸어 Bus를 통해 메모리에 할당한다.
만약 페이지번호: 0010 -> 2이라면 PT에서 2번째 엔트리를 찾아 110으로 주소를 변환한다.(valid: 1) 12-bit offset은 직접적으로 copy된다.
Structure of Page Table Entry
Caching disabled: 0이면 caching, 해당 bit를 보고 CPU에 캐시할지말지를 결정한다.
Referenced: 주소 변환할때마다 1로세팅한다. - CPU 교체정책에서 사용된다. 후술.
Modified(dirty): 해당 페이지가 메인 메모리 프레임에 적재된 이후 변경되었다는것을 표시해준다.
Protection: read/write/execution의 보호기능을 한다. 운영체제가 이를 점검하여 보안관련 기능이 수행될수있다.
Present/absent(valid): 메인 메모리에 해당 패이지가 존재하는지 여부를 보여준다.
Page frame number
Speeding Up Paging
가상주소에서 물리주소로 매핑되는 과정은 빨라야 한다.
가상주소공간이 크면 클수록 Page Table의 크기도 커져야한다.
-> TLB를 사용하더라도 Page Table이 너무 크다면 PT는 메모리의 상당부분을 차지한다.
Translation Lookaside Buffers
- Page Table에서 주소를 변환하면 TLB에 적재된 후 Valid bit는 1로 바뀐다.
- TLB는 최근에 주소변환한 내용만 기억한다!
- TLB에 64, 128개 정도의 페이지만 존재하더라도(적은 페이지수) 히트율은 크게 증가한다.
Problem: Too Large Page Tablesolution
- Multilevel paging
- Inverted page table
Multilevel paging
singlelevel page는 2^20개의 entry가 모두 존재해야한다.
PT를 Multilevel로 구현하면 Top-level Page Table에만 entry가 존재하면 되므로 2nd PT부터는 entry가 존재하지 않아도 된다.
페이지번호에는 p1, p2의 여러 단계의 페이지 테이블 번호가 적혀있다.
이 방법을 사용하면 3번 Access하므로 TLB Miss가 발생하면 많은 메모리를 사용해야하므로 접근율이 떨어질 수 있다는 단점이 존재한다.
Inverted page table(역페이지 테이블)
- Page Table에 페이지 번호(몇번 프로세스에 몇번 페이지가 있는지)가 기록되어있고, 전체 시스템에 하나만 존재한다. (프로세스마다 존재 x)
Process Id(Pid)를 통해 PT의 entry를 찾는다.
i번째 프레임에 프로세스가 존재한다는 사실을 안다
이 i가 물리주소가 되어 변환해준다.
또한 TLB도 존재하며, 발상의 전환이라 할 수 있다!
- PT의 메모리 공간이 줄어든다는 장점이 있지만, TLB Miss가 나게되면 하드웨어 회로 말고 소프트웨어가 검색(해쉬 탐색등)하여 TLB를 세팅한 후 동작해야한다는 문제점이 존재한다. 이에 현재는 잘 사용하지 않는 방식이다.
Address Space and OS
- 모든 Process는 각각의 OS 코드 데이터가 Mapping되어있다.
- 각 Process가 main, I/O등을 실행하는 코드 실행시 Interrupt service routine을 이 OS 코드 데이터로 자기가 직접 실행한다!
- Shared Library: paging 기법을 이용해서 Library를 공유할 수 있다.
코드를 미리 적재하지 않고 필요한 페이지가 참조될 때 page fault형태로 핸들링하면서 적재하겠다는 demand paging방법을 요즘 대부분 사용한다!
Page Faults
- mapping되지 않은 페이지가 참조되면 page fault가 발생한다.
- 만약 hwp실행파일을 실행했다고 하자. 우선 disk의 swap영역에 수행 이미지를 만들고, 메인 함수를 CPU에서 실행한다. 이때PT를 보면 valid 비트는 모두 0이다. 메모리의 프레임이 할당되어있지 않은것이다. 따라서 주소변환하지 못하므로 CPU는 할 작업이 없으므로스스로 interrupt를 건다. OS의 fault handler는 이를 보고 정해진 서비스루틴으로 jump한다.OS의 fault handler는 적재가 안되서 나오는 page fault인지 확인한 후 맞다면 해당 페이지를 swap영역이나 실행파일에서 찾아서 읽고 메인 메모리의 빈 frame에 넣은 후 Page Table의 valid bit를 1로 변환한 후 적재한다.
- 빈 프레임이 없다면(메모리가 꽉 찼다면) 기존 적재된 프레임 중 하나를 쫓아내야한다. ->Replacement 정책!
!! page fault가 발생할 확률은 매우 작아야한다!
만약 또 참조될 프로세스를 쫓아내면 또다시 가져와야한다. 이러한 page fault가 나오면 어마어마한 시간을 손해보기 떄문에 쫓아낼 때 잘 쫓아내는 것이 중요하다!
Page Replacement Algorithms
프레임에 새로운 페이지를 넣으려면 기존 메모리에 적재된 페이지를 쫓아내야한다.
-> 기존 프레임에 적재된 페이지 중 어느것을 쫓아내고 새로운 페이지를 넣을까?
Optimal page replacement algorithm - 미래를 알고있다는 전제하에 사용하므로 실제 사용할 수 없지만 다른 방법과 성능을 비교할 때 쓰인다.
Not recently used(NRU) page replacement
First-In, First-Out page replacement
Second chance page replacement
Clock page replacement
Least recently used(LRU) page replacement
Working set page replacement
WSClock page replacement
NRU(Not Recently Used), FIFO
NRU: 최근에 참조되지 않은 페이지를 쫓아내겠다!
Class 0: Not Referenced, Not Modified
Class 1: Not Referenced, Modified
Class 2: Referenced, Not Modified
Class 3: Referenced, Modified
-> Class 0의 페이지를 우선해서 쫓아내고, 만약 없다면 그 다음 Class 1, 2, 3순서로 쫓아낸다.
- reference bit를 확인하여 1로 세팅되어있다면 최근에 참조(주소변환)되었으므로 우선순위가 낮다.
- modified: 변경(write 등)안되어있다면 바로 쫓아내고, 변경되었다면 해당페이지를 쫓아내기 전에 swap영역에 다시 적어야한다.
- NRU 기법은 실제로 많이 변형해서 사용하는 기법이다.
FIFO: 선입선출, 가장 먼저 적재되었다고해서 참조가 덜 되는것은 아니기 떄문에 참조가 많이 되는 페이지(hot page)를 쫓아낼 수 있다는 단점이 있다. (성능에 손해를 볼 수 있다)
Second Chance Algorithm
FIFO를 보완한 알고리즘. 가장 먼저 들어온 페이지의 참조비트가 1이라면 0으로 변경하고 가장 마지막으로 보낸다.(한번 더 기회를 더 줌)
The Clock Page Replacement Algorithm
메모리에 적재된 페이지들 사이에서 Clock hand가
돌아가며 가리키는 페이지부터 확인한다. 만약 검사하는 페이지의 reference bit가 1이면 넘어가고 0이면 쫓아낸다.
LRU Page Replacement Algorithm
Top: Most Recently Used (MRU) Page
Bottom: Least Recently Used (LRU) page
항상 LRU page를 교체한다.(쫓아낸다)
참조될때마다 페이지 순서가 LRU page stack에 linked-list로 만든다. 이는 소프트웨어적으로 구현이 쉽지만 하드웨어인 CPU 캐시에 구현하기는 어렵다.
-> 현재 가장 연구가 많이되어있고 성능이 좋은 알고리즘이며 모든 프로그램이 가장 많이 사용하는 방식이다.
- 페이지 참조 bit를 행렬로 만들어서 관리하는 방법이 있다. 0번 페이지 참조시 행은 모두 1로, 열은 모두 0으로 만들고 확인시 행으로 가서 가장 큰값을 가지는 페이지가 최근에 참조된것이고, 가장 작은값을 가지는 페이지는 예전에 참조된 것이다. 최근에몇번 참조되었는지 확인할 수 없다.
이 방법도 페이지수가 많아지게 되면 CPU가 해주기에는 큰 일이다.
또다른 LRU 관리 방법)
- CPU는 참조(주소변환)될때마다 R bit를 1로 세팅한다.
- CPU Clock이 한번 tick할때마다 6개 페이지의 R bit를 가장 왼쪽에 각각 기록한다.
- 최근 참조된 bit는 가장 클것이고, 가장 옛날에 참조된 bit는 가장 작을것이다. 또한 최근에 참조된 횟수도 표현이 가능하다!
-> 하지만 페이지 개수가 많아지면 카운트를 유지하기 어려워지기 때문에 실제 시스템 구현시엔 어렵다.
Comparison of OPT, LRU, FIFO, CLOCK
OPT에서 3번의 Fault가 나오므로 3번보다 더 줄일 수 있는 알고리즘은 존재하지 않는다.
Working Set Page Replacement
- Working Set: 작업 집합. 프로그램이 실행하는데 필요한 페이지들
- Working Set이 메모리에 올라오면 잘 작동하고, 없다면 가져와야한다.
- R(Referenced bit)==1이면 놔두고 R==0이면 working set에 속하는지 확인한다.
- R==0이면서 age(현재 시간 - 마지막 사용시간) >τ이면페이지를 제거한다.
WSClock Page Replacemnet Algorithm
Working Set에 속한 Page들은 꼭 필요하므로 그것들은 메모리에 가지고 있겠다는 것. 특히 멀티프로그래밍에서 기본이 되는 이론이다.
Clock Page 알고리즘에 Working Set 개념을 추가한 방식이다.
ex. R bit가 1이면 0으로 바꾸고 clock hand를 움직인다. 만약 R bit가 0이면 페이지를 교체한다.
Summary of Page Replacement Algorithms
LRU Algorithm은 다른 기법의 기본이 되는 알고리즘이다. 하지만 하드웨어적으로 구현이 어려워 Working set..등으로 보완했지만 실질적으로 많은 CPU는 NRU를 응용한 Two handed Clock기법을 사용한다!
Thrashing
: 메모리에 너무 많은 process가 적재되어있어서 각 프로세스의 working set이 적재될 수 없는 현상. swapping으로 이를 해결할 수 있다.
OS - 03. Memory Management
Address Space(주소 공간)
Address Generation
코드는 컴파일되어 어셈블리어로 번역된다. 이때 적재될 메모리 주소는 어디가 될지 모르므로 보통 0번지의 값을 가진다.
실제 메모리는 1000번지부터 적재되므로 jmp 175 코드는 실제 메모리의 175로 가면 안되고 1175로 가야 하므로 1175로 바꿔줘야 한다.
Multiple Programs Without Memory Abstraction
단일 프로그램은 하나씩 할당하여 충돌이 발생하지 않을 수 있지만, 여러 개 돌리면 메모리 공간 어디에 적재될지 모르므로 문제가 발생한다.
-> relocation이 필요하다!
Partioning
미리 메모리를 여러 개의 partition으로 쪼개 놓아 relocation이 필요 없도록 하는 방법이다.
: 파티션 별로 Queue가 존재한다.
: 처음부터 어느 파티션에 들어갈지 시작 주소를 다 알고 있다면 relocation은 필요하지 않다.
Placement with Partioning
물리 메모리는 고정된 크기의 파티션으로 나누어져 있다.
Internal fragmentation(내부 단편화 - 낭비되는 공간 O), Inefficient와 같은 문제점이 존재한다.
- 컴파일 시에는 항상 시작 주소를 0번지로 하고, 실행 시에 실행마다 주소를 바꾸어줄 필요가 있다. -> Dynamic Program Relocation!
Dynamic Program Relocation
CPU는 실시간으로 코드의 주소와 Limit register값을 비교하고 값보다 작다면 Base register의 값을 더해서 Relocate 한다!
(Logical Addresses -> Physical Addresses)
Dynamic Partitioning
-> 미리 쪼개지 말고 동적으로 파티셔닝 한다!
- 멀티프로세싱: 메모리에 여러 개의 프로세스를 넣고 실행하는 것
- a~d: 메모리 공간에 프로세스 1부터 3까지 적재된다.
- e: 프로세스 2가 입출력 요구 등을 이유로 잠깐 멈추면 메모리 공간에서 쫓아낸다.
- f: 빈 공간에 프로세스 4가 들어와 적재된다.
-> 다음과 같은 과정을 거치며 동적 파티셔닝이 일어나는데, 이때 중간중간 빈 공간(h)이 생기게 되어 메모리 효율이 떨어지게 된다.
이를 메모리 단편화, 즉 fragmentation이 일어난다고 한다.
Dynamic Partitioning Placment Algorithm
각 상황에 따라 좋은 알고리즘이 달라지므로, 각 알고리즘 중 어떤 알고리즘이 좋을지는 모른다. 케바케.
First-Fit: 항상 처음부터 살펴보다가 적재 가능한 곳이 있으면 발견한 처음 공간에 넣는다.
Best-Fit: 전체를 다 살펴보고, 가장 딱 들어맞는 크기의 공간에 넣는다.
Next-Fit: First-Fit과 유사. 한번 검색하면 마지막 검색위치를 기억하여 다음 검색 시에는 이 지점부터 찾기 시작한 후 발견한 공간에 넣는다.
Worst-Fit: 전체를 다 살펴보고, 가장 큰 공간에 넣는다.
-> 전체를 다 살펴보면 오래 걸리게 되고, 처음부터 찾아 바로 넣으면 윗부분의 메모리 사용도가 높아지며 빈 공간이 생길 수 있다는 단점이 존재한다.
Solutions for Fragmentation
Coalescing
Program A가 작업이 종료되면 빈공간이 생기는데, 이를 다른 빈 공간과 통합(Coalescing)하는 방법이다.
CPU는 2K와 5K를 통합하지 않는다면 각각 따로 생각하기 때문에 통합이 필요하다.
Compaction
메모리에서 사용되지 않는 공간(unused) 모두를 하나로 크게 통합하는 방법이다.
Compaction의 문제점
- optimal compaction 알고리즘을 찾기 어렵다.
- compaction 하는 동안 시스템은 정지한다.
Compaction을 수행하는 경우
- 메모리 utilization(효율)이 낮은 수치(75% 정도)로 떨어질 때
- memory allocation(할당) 실패 시
- 주기적으로
생각할때는 쉽게 동작하는 것처럼 보이지만 실제로 구현 시 어려움이 있다.
Swapping
기술이 발전하며 HDD의 속도가 빨라지게 되면서 메모리 사이즈보다 더 많은 프로세스를 넣고 실행하기 위해서 Swap In/Out개념을 도입하였다.
- 메모리에 프로세스를 많이 넣으면 넣을수록 CPU의 활용도. 즉 Utilization이 높아진다.
- c: 프로세스 A.B.C 모두 I/O요구 등의 이유로 중단된다면 이 중 하나인 A를 골라서 Swap out 한다; 프로세스의 메모리 데이터 그대로 - HDD의 swap영역에 넣고 프로세스를 쫓아낸다.
- 이렇게 Swap in/out을 하면 더 많은 프로세스를 사용할 수 있고 Utilization이 높아진다.
- 현재도 Swap을 사용하는데, CPU Utiilization을 높이려기보다는 threashing 현상으로 시스템이 다운되는 것을 방지하기 위해 사용한다.
+) 프로그램 수행 이미지의 크기가 변하는 경우. 사용 가능한 메모리 공간보다 더 커지게 되면 swapping으로 잠시 디스크로 옮기고 큰 공간이 나오게 된다면 그때 수행된다.
Overlay
램보다 프로그램 크기가 클 때 수행하는 방법. Overlay기능을 켜고 작업을 수행할 수 있다.
Memory Management with Bitmaps
a: 메모리 공간. A~E까지 5개의 프로세스가 적재되어있고, 3개의 비어있는 공간이 존재한다.
b: bitmap. 1이면 사용 중이고 0이면 비어있음을 나타낸다.
c: b를 linked-list로 표현한 방식. P면 사용 중, H면 비어있음을 나타내고 H 5 3이면 5번부터 3개의 상태가 비어있음을 나타낸다.
Virtual Memory
- CPU는 메모리를 공간이 무한한 Logical Memory로 인식한다; 가상 주소와 실제 주소를 분리하여 생각한다.
- 가상 주소 공간에서 프로그램을 실행하고 이는 실제 DRAM에 적재되며, 실제 주소로 변환하여 실행하도록 한다.
: 모든 프로세스는 위 가상공간 모두를 혼자 다 쓴다는 환상을 가지고 실행한다.
- 이 개념을 통해 작은 DRAM보다 size가 더 큰 프로세스를 넣고 실행할 수도 있다. 이는 필요 부분만 DRAM에 적재하고 나머지는 DISK에서 Swap 하여 실행한다.
Paging(Virtual memory) 기법
- Virtual Address Space을 동일한 크기인 Page단위로 쪼갠다.
- Virtual Address(VA): 20bit는 페이지 번호로, 12bit는 페이지 안의 offset으로 쪼개어 할당한다. (p, o)
- Physical Memory는 동일한 크기인 Frame단위로 쪼갠다.
- Physical Address도 마찬가지로 프레임 번호와 offset으로 쪼개어 할당한다. (f, o)
- (f, o) = (3, 6)이면 3번째 frame의 6번째 offset을 나타낸다.
Page는 frame으로 매핑된다. page의 일부는 DRAM으로, 일부는 Disk의 Swap영역에 적재된다.
Virtual Address Translation
(p, o) 페이지가 (f, o) 프레임에 적재될 때 가상 주소는 물리 주소로 실시간으로 변환되어 access 하도록 구현되어야 한다.
이는 CPU 내부의 Page Table을 통해 수행되는데, 과정은 다음과 같다.
Page Table Structure
Page Table의 contents
- Flags : valid/invalid(resident) bit, dirty bit, reference(clock or used) bit
- page frame number
- PTBR(Page Table Base Register)이 Page Table을 가리키게 한다.
- Flag 중 valid bit가 1이면 frame을 access 하고, 0이면 CPU가 스스로 해결하지 못하므로 page interrupt를 걸어 jump 한다. (OS가 swap영역에서 PT에 세팅하여 1로 변환해준다)
- valid bit: 메인 메모리에 해당 페이지가 존재하는가?
- Page Table은 2^20개의 페이지(1MB)가 존재하며 한 entry의 크기는 4kb이므로 프로세스마다 4MB의 Page Table이 필요하다.
Translation Lookaside Buffer(TLB - 명칭 외우기!!)
가상 메모리는 PT entry 접근 1번, 물리 주소 접근 1번 총 2번의 접근이 필요하기 때문에(물리 메모리 : 1번만 접근) 메모리 효율이 2배로 떨어진다는 문제점이 있다.
이를 해결하기 위해 CPU의 Cache와 같은 기능을 가지는 Translation Lookaside Buffer(TLB)를 도입하였다.
- 최근에 Access 한 PT entry만 caching 하고 있자!
동작 과정 - CPU 내부 회로에서 실시간으로 동작한다.
문맥 교환 시 TLB의 Valid bit는 0으로 CLEAR 된다. 이는 TLB히트율이 잠시 떨어진다 할 수 있다. (물론 TLB가 다시 채워지면 높아진다)
Protection and Sharing
Process A, B의 데이터 Page Table은 서로 다르지만 내부 코드 부분의 f=4는 동일하다. f=4에 해당하는 프레임은 메모리에 따로 적재하지 않고 똑같은 프레임을 가리키게 하는데, 이를 Sharing 한다고 한다.
하지만 이는 Read-only모드일 때는 가능하지만, Write 명령이라면 OS에 부탁하여 물리 메모리를 copy 하여 두 개의 영역에서 write 하도록 한다.
++ OS는 각 프로세스마다 Page Table 을 유지하도록 한다.
Page Table
Assignment of Process Pages to Free Frames
- A process의 0번 페이지, 1번페이지, ... , B process의 0번 페이지, ...를 메모리에 적재한다.
- 각 프로세스는 적재될 때 빈 프레임이면 어디든 적재될 수 있다. (process D-꼭 연속적으로 적재될 필요는 없다!)
- Process B가 수행 종료되었으므로 PT의 valid bit는 모두 0(N)으로 된다.
- 프로세스를 페이지 별로 나누어 메모리에 적재하므로 메모리 단편화(Fragmentation)가 일어나지 않는다! (페이지 내에서 사용되지 않는 공간은 존재할 수는 있다.)
Virtual Memory - Paging
CPU에서 가상주소는 MMU chip(변환회로)을 통해 가상주소를 물리주소로 바꾸어 Bus를 통해 메모리에 할당한다.
만약 페이지번호: 0010 -> 2이라면 PT에서 2번째 엔트리를 찾아 110으로 주소를 변환한다.(valid: 1) 12-bit offset은 직접적으로 copy된다.
Structure of Page Table Entry
Speeding Up Paging
-> TLB를 사용하더라도 Page Table이 너무 크다면 PT는 메모리의 상당부분을 차지한다.
Translation Lookaside Buffers
- Page Table에서 주소를 변환하면 TLB에 적재된 후 Valid bit는 1로 바뀐다.
- TLB는 최근에 주소변환한 내용만 기억한다!
- TLB에 64, 128개 정도의 페이지만 존재하더라도(적은 페이지수) 히트율은 크게 증가한다.
Problem: Too Large Page Table solution
- Multilevel paging
- Inverted page table
Multilevel paging
singlelevel page는 2^20개의 entry가 모두 존재해야한다.
PT를 Multilevel로 구현하면 Top-level Page Table에만 entry가 존재하면 되므로 2nd PT부터는 entry가 존재하지 않아도 된다.
페이지번호에는 p1, p2의 여러 단계의 페이지 테이블 번호가 적혀있다.
이 방법을 사용하면 3번 Access하므로 TLB Miss가 발생하면 많은 메모리를 사용해야하므로 접근율이 떨어질 수 있다는 단점이 존재한다.
Inverted page table(역페이지 테이블)
- Page Table에 페이지 번호(몇번 프로세스에 몇번 페이지가 있는지)가 기록되어있고, 전체 시스템에 하나만 존재한다. (프로세스마다 존재 x)
또한 TLB도 존재하며, 발상의 전환이라 할 수 있다!
- PT의 메모리 공간이 줄어든다는 장점이 있지만, TLB Miss가 나게되면 하드웨어 회로 말고 소프트웨어가 검색(해쉬 탐색등)하여 TLB를 세팅한 후 동작해야한다는 문제점이 존재한다. 이에 현재는 잘 사용하지 않는 방식이다.
Address Space and OS
- 모든 Process는 각각의 OS 코드 데이터가 Mapping되어있다.
- 각 Process가 main, I/O등을 실행하는 코드 실행시 Interrupt service routine을 이 OS 코드 데이터로 자기가 직접 실행한다!
- Shared Library: paging 기법을 이용해서 Library를 공유할 수 있다.
Page Faults
- mapping되지 않은 페이지가 참조되면 page fault가 발생한다.
- 만약 hwp실행파일을 실행했다고 하자. 우선 disk의 swap영역에 수행 이미지를 만들고, 메인 함수를 CPU에서 실행한다. 이때 PT를 보면 valid 비트는 모두 0이다. 메모리의 프레임이 할당되어있지 않은것이다. 따라서 주소변환하지 못하므로 CPU는 할 작업이 없으므로 스스로 interrupt를 건다. OS의 fault handler는 이를 보고 정해진 서비스루틴으로 jump한다. OS의 fault handler는 적재가 안되서 나오는 page fault인지 확인한 후 맞다면 해당 페이지를 swap영역이나 실행파일에서 찾아서 읽고 메인 메모리의 빈 frame에 넣은 후 Page Table의 valid bit를 1로 변환한 후 적재한다.
- 빈 프레임이 없다면(메모리가 꽉 찼다면) 기존 적재된 프레임 중 하나를 쫓아내야한다. -> Replacement 정책!
!! page fault가 발생할 확률은 매우 작아야한다!
Page Replacement Algorithms
프레임에 새로운 페이지를 넣으려면 기존 메모리에 적재된 페이지를 쫓아내야한다.
-> 기존 프레임에 적재된 페이지 중 어느것을 쫓아내고 새로운 페이지를 넣을까?
- 미래를 알고있다는 전제하에 사용하므로 실제 사용할 수 없지만 다른 방법과 성능을 비교할 때 쓰인다.
NRU(Not Recently Used), FIFO
NRU: 최근에 참조되지 않은 페이지를 쫓아내겠다!
-> Class 0의 페이지를 우선해서 쫓아내고, 만약 없다면 그 다음 Class 1, 2, 3순서로 쫓아낸다.
- reference bit를 확인하여 1로 세팅되어있다면 최근에 참조(주소변환)되었으므로 우선순위가 낮다.
- modified: 변경(write 등)안되어있다면 바로 쫓아내고, 변경되었다면 해당페이지를 쫓아내기 전에 swap영역에 다시 적어야한다.
- NRU 기법은 실제로 많이 변형해서 사용하는 기법이다.
FIFO: 선입선출, 가장 먼저 적재되었다고해서 참조가 덜 되는것은 아니기 떄문에 참조가 많이 되는 페이지(hot page)를 쫓아낼 수 있다는 단점이 있다. (성능에 손해를 볼 수 있다)
Second Chance Algorithm
FIFO를 보완한 알고리즘. 가장 먼저 들어온 페이지의 참조비트가 1이라면 0으로 변경하고 가장 마지막으로 보낸다.(한번 더 기회를 더 줌)
The Clock Page Replacement Algorithm
메모리에 적재된 페이지들 사이에서 Clock hand가
돌아가며 가리키는 페이지부터 확인한다.
만약 검사하는 페이지의 reference bit가 1이면 넘어가고 0이면 쫓아낸다.
LRU Page Replacement Algorithm
Top: Most Recently Used (MRU) Page
Bottom: Least Recently Used (LRU) page
항상 LRU page를 교체한다.(쫓아낸다)
참조될때마다 페이지 순서가 LRU page stack에 linked-list로 만든다. 이는 소프트웨어적으로 구현이 쉽지만 하드웨어인 CPU 캐시에 구현하기는 어렵다.
-> 현재 가장 연구가 많이되어있고 성능이 좋은 알고리즘이며 모든 프로그램이 가장 많이 사용하는 방식이다.
- 페이지 참조 bit를 행렬로 만들어서 관리하는 방법이 있다. 0번 페이지 참조시 행은 모두 1로, 열은 모두 0으로 만들고 확인시 행으로 가서 가장 큰값을 가지는 페이지가 최근에 참조된것이고, 가장 작은값을 가지는 페이지는 예전에 참조된 것이다. 최근에 몇번 참조되었는지 확인할 수 없다.
이 방법도 페이지수가 많아지게 되면 CPU가 해주기에는 큰 일이다.
또다른 LRU 관리 방법)
- CPU는 참조(주소변환)될때마다 R bit를 1로 세팅한다.
- CPU Clock이 한번 tick할때마다 6개 페이지의 R bit를 가장 왼쪽에 각각 기록한다.
- 최근 참조된 bit는 가장 클것이고, 가장 옛날에 참조된 bit는 가장 작을것이다. 또한 최근에 참조된 횟수도 표현이 가능하다!
-> 하지만 페이지 개수가 많아지면 카운트를 유지하기 어려워지기 때문에 실제 시스템 구현시엔 어렵다.
Comparison of OPT, LRU, FIFO, CLOCK
Working Set Page Replacement
- Working Set: 작업 집합. 프로그램이 실행하는데 필요한 페이지들
- Working Set이 메모리에 올라오면 잘 작동하고, 없다면 가져와야한다.
- R(Referenced bit)==1이면 놔두고 R==0이면 working set에 속하는지 확인한다.
- R==0이면서 age(현재 시간 - 마지막 사용시간) > τ이면 페이지를 제거한다.
WSClock Page Replacemnet Algorithm
Working Set에 속한 Page들은 꼭 필요하므로 그것들은 메모리에 가지고 있겠다는 것. 특히 멀티프로그래밍에서 기본이 되는 이론이다.
Clock Page 알고리즘에 Working Set 개념을 추가한 방식이다.
ex. R bit가 1이면 0으로 바꾸고 clock hand를 움직인다. 만약 R bit가 0이면 페이지를 교체한다.
Summary of Page Replacement Algorithms
LRU Algorithm은 다른 기법의 기본이 되는 알고리즘이다. 하지만 하드웨어적으로 구현이 어려워 Working set..등으로 보완했지만 실질적으로 많은 CPU는 NRU를 응용한 Two handed Clock기법을 사용한다!
Thrashing
: 메모리에 너무 많은 process가 적재되어있어서 각 프로세스의 working set이 적재될 수 없는 현상. swapping으로 이를 해결할 수 있다.
'cs지식 > 운영체제' 카테고리의 다른 글