마치 메모리가 더 있는 것처럼 indirection !
물리적으로는 RAM이 8GB이지만 전체 program을 동시에 돌리는건 극히 드물기에 가장 중요하다고 생각되는 프로그램을 실행하는데 16GB로 수행하는척 해주는 것. 굳이 메모리에 적재되어 있지 않아도 되는 것들을 굳이 적재하지 않음( Dynamic Loading ).
3번 메모리에 접근하고 싶은데 12번 메모리와 15번 메모리에 있는 것을 더해서 3번 메모리에 넣고 싶을 때, 3, 12 그리고 15번 메모리 공간만 알면 된다. 나머지는 필요 없음
physical 메모리는 page frames으로 구성되어 있기에 contiguous하지 않다.
virtual memory가 있으면 memory mapping으로 4GB 중 필요한 것만 1GB에 할당하고 나머지는 Disk(가상 메모리)에 넣어줬다가 필요하면 1GB에 넣게 해준다.
사실 이게 꼭 필요한가 싶을 것이다. 하지만 하드웨어 resource가 커질 수록 점점 더 많은 RAM을 요구하게 될 것이다. 그렇기에 virtual memory는 반창고와 같은 임시방편이 아니라 계속 필요로 하게 될 것이다.
sparse 주소 공간
Virtual-address Space
사용하지 않는 공간은 paging하지 않고 있다가 필요할 때 paging하는 방식이다. 사용하지 않을 때 이를 보관할 공간이 필요하다. Disk안에 저장되어 있다.
Demand Paging
Virtaul memory의 이론을 가능하게 해주는 방식
대부분 프로그램 실행 시작 시 프로그램의 전체가 물리 메모리에 있을 필요는 없다. 그렇기에 처음에 필요한 것들만 적재하는 Demand Paging이 사용된다. 이를 사용하는 가상 메모리는 page들이 실행과정에서 실제로 필요해 질 때 적재된다.
Disk안에 virtual address로 저장되어 있다. Demand Paging은 swapping + paging의 개념으로 볼 수 있으며, 프로세스 단위로 swap in out이 되는 swapping이 아닌 일부부만 swapping을 수행하기에 I/O 연산의 overhead를 줄일 수 있다. 사용자 입장에서도 일부만 오게되니 메모리를 더 사용할 수 있다.
swapping policy가 그만큼 중요해진다.
- Lazy swapper : 프로세스를 읽어 들일 때(swap in), 전체 프로세스가 아닌 필요한 page만 적재하도록 해준다.
- pager : sawpper는 전체 프로세스 관리인 반면 프로세스 내의 개별 page들을 관리하는 pager가 demand paging에 적합한 용어이다.
pager는 프로세스 전체가 아닌 실제 필요한 page들만 swap in을 하여 시간과 메모리 공간 낭비를 줄일 수 있다. 이는 프로세스가 다시 swap out 되기 전에 실제로 사용될 page들을 추측하기 때문에 가능하다.
어느 page가 disk에 있고 어떤 page가 메모리에 적재되어 있는지 구별할 수 있어야 하는데 이를 위해 valid-invalid bit가 사용된다.
기존의 address translation만 했던 MMU는 demand paging을 구현해야 할 역할이 추가된다. 내부적으로만 이런 것이 진행되어야 하고 프로그램 자체가 변경되거나 프로그래머가 코드를 변경하게 해서는 안된다.
Valid-Invalid Bit
page table에서 valid-invalid bit이 i (invalid)라면 해당 page가 가상 주소 공간에 정의되지 않았거나 메모리에 적재되지 않고 디스크에 존재한 상태이다.
valid-invalid bit이 v (valid)라면 해당 page가 메모리에 존재한다(memory resident).
이는 page fault를 발생한다.
page fault(중요) → 사용할 수는 있지만 아직 메모리에 적재되지 않은 상태를 말한다.
Page Fault
처음 접근했을 때 메모리 상에 존재하지 않으니, page fault가 발생하고 storage(Disk)에서 이를 메모리에 적재한다.
- 명령어나 프로그램을 load할 때 page table에서 page fault가 발생 (Interrupt or Trap)
- OS는 단지 메모리에 없는 것인지 잘못된 참조인지 판단한다. (valid-invalid bit)
- 잘못된 참조라면 abort (종료)
- 유효한 참조라면 disk에 있는 page를 memory로 적재해야 한다.
- free frame을 확보한다.
실제 메모리(물리 주소 공간)에 free frame이 없을 때는 page replacement를 수행한다. - backing store에서 virtual memory를 찾는다.
- page를 frame에 Swapping하고 page table의 i를 v(valid)로 바꾼다. → 이 page가 메모리에 있다는 뜻
- 명령어를 재시작하거나 프로그램을 다시 load한다.
물론 1번 단계를 수행할 때마다 page fault가 여러 번 일어나는 multiple page faults가 발생할 가능성이 있다. 하지만 이런 경우는 드물며 모든 프로그램은 locality of reference(특정 작은 부분만 한동안 집중적으로 참조)의 특징을 지니기에 성능 저하를 초래할 가능성이 적다.
pure demand paging :어떤 page가 필요해지기 전까지는 그 page를 메모리에 load하지 않는다.
demand paging을 위한 requirements
- valid or invalid page table
- Swap space(secondary memory) : main memory에 없는 모든 page들이 저장되어 있다.
- Instruction restart : page fault가 발생하면 중단된 프로세스 상태를 보관해두었다가 재시작이 가능해야 한다.
demand paging은 어떻게 하면 page fault를 줄일 수 있을지 생각해야 한다. (매우 중요)
Performance of Demand Paging
Page Fault Time
- interrupt 시간
- Disk에서 읽어오는 시간 (매우매우매우 길어서 overhead의 직접적인 요인)
- Process를 재시작하는 시간
실제 접근 시간(effective access time)은 page fault rate에 비례하기에 이를 줄이는 것이 필요하다.
Demand paging은 생각보다 cost가 많이 소모된다. 그렇기에 page fault이 발생하면 할수록 성능저하는 시간 문제이다.
Page fault가 발생하면 100 milliseconds(사람이 느림을 감지할 수 있는 시간)이상 걸리는게 대부분이다.
Copy on Write
fork()를 통해 프로세스를 생성 할 때에는 첫 demand paging을 copy on write로 생략하는 것이 가능하다.
이전에 배웠던 fork( )를 상기시켜 보자. fork( )를 수행하면 부모와 똑같은 프로세스가 복사가 된다. 만약 복사를 하고 모든 operation이 읽기라면 ? → 비효율적이다 !
즉 대부분의 자식들은 생성되자마자, exec( )를 호출하여 부모로부터 복사해온 page들이 쓸모없게 된다.
그래서 부모 page들을 다 복사해오는 대신 자식이 당분간 부모 page를 함께 사용할 수 있도록 copy on write(쓰기 시 복사) 방식이 사용된다.
기존의 프로세스를 fork( )한 것을 logical하게 만들고(실제 복사한 것이 아님) page link만 연결시켜주고(Physical memory 공유), write operation이 수행된다면 그제서야 copy를 수행한다. 이렇게되면 메모리를 아낄 수 있고 read 부분은 여전히 남아 있게 된다.
zero-fill-on-demand : 아무것도 없는 page를 우선으로 할당한다. process가 다른 process에 영향을 주지 않도록 security 차원에서 사용된다.
Page replacement
메모리가 가득 차 있을 때 어떤 page을 뺄 것인지 결정하는 것이다.
page는 실제 사용하지 않아야 하고 page fault를 최소화 시킬 수 있는(다음에도 잘 사용하지 않게될) page를 빼야한다.
process
- 실제 주소(물리 주소)에서 victim page를 swap out
→ overhead 발생 - page table의 해당 entry의 valid-invalid bit를 invalid로 바꾼다.
- victim page를 요구할 때 다시 swap in
→ overhead 발생
victim frame을 어떻게 고를 것인지가 중요한데 frame이 dirty하면 frame을 복사해야 하고 access time이 늘어난다.
- dirty frame : writing operation이 수행된 frame
Algorithms
Frame-allocation algorithm
프로세스가 여러 개 있을 때 메모리가 이 프로세스들을 어떻게 할당할지를 결정하는 알고리즘
Page-replacement algorithm
메모리에 할당되고 어떤 프레임을 victim으로 설정해서 운영할건지 결정하는 알고리즘
둘 다 수행되어야 한다.
page에 순서에 대한 reference string이 있다.
frame이 5개 할당 vs frame이 50개 할당
page fault는 어떤 상황에서 더 날까?
→ frame이 5개밖에 없을 때
이렇게 frame 수와 page fault rate는 반비례 관계를 보인다.
First in First out algorithm
reference string이 주어졌을 때 순서대로 frame에 할당된다. frame이 가득 찼다면 먼저 들어온게 먼저 빠진다.
reference string : 1 2 3 4 1 2 5 1 2 3 4 5
frame이 3개라면 총 9개의 page fault / frame이 4개라면 총 10개의 page fautl가 일어난다.
→ frame이 더 있는데 왜 ?!
이를 Belady's Anomaly의 영향을 받는다고 말한다.
Optimal algorithm
미래에 대한 모든 정보를 알고 있다면, page fault를 최소화시키는 page replacement를 찾는 알고리즘이다. 즉, 가장 오랫동안 사용되지 않을, 가장 나중에 사용될 page만을 빼는 작업을 수행한다.
가장 최소의 page fault가 일어난다. (Belady의 모순 또한 발생하지 않는다.)
LRU (Least Recently Used) algorithm
미래가 아닌 과거에 대한 정보를 토대로, 사용된지 가장 오래된 page를 골라 빼내는 작업을 수행한다.
성능은 FIFO와 OPT의 중간 정도이다. 일반적으로 좋고 빈번히 사용되는 알고리즘이다.
How to implement LRU?
구현이 까다롭기에 그대로 사용되지는 않고있다. LRU variant를 사용
- 모든 page entry는 counter를 가지고 있다.
- Stack을 사용
- Belady's Anomaly의 영향을 받지 않는다.
(좀 더 추가)
하지만 이를 통해 구현하면 overhead가 많이 발생해 cost가 많이 든다.
→ LRU approximation을 구현한다.
LRU Approximation algorithms
Reference bit algorithm
- 각 page는 0이라는 하나의 bit를 가진다.
- page가 referenced(참조되면) 1로 bit를 바꾼다.
- bit가 0인 page를 교체한다.
- timer를 두고 주기적으로 모든 page의 bit를 0으로 바꾼다.
타이밍이 좋지 않다면 문제가 발생할 수 있는데 이를 second-chance가 해결
타이밍이 좋지 않다 : 나는 bit가 1인데 timer 때문에 0으로 되고 그 즉시 대체될 때
Second-chance algorithm(Clock algorithm)
- 차례대로 FIFO를 수행하되, reference bit algorithm을 적용한다.
- page가 replace(교체)될 때, reference bit가 0이면 replace !
- 1이면 0으로 바꾼다.(다시 한 번 기회를 줌)
Enhanced Second-Chance algorithm
reference와 dirty?(modify?) bit를 통해 결정한다.
- (0, 0) : 최근에 사용되지도 변경되지도 않은 경우 - 교체되기 좋은 page
- (0, 1) : 최근에 사용되지 않고 변경만 된 경우
- (1, 0) : 최근에 사용은 되었으나 변경되지 않은 경우
- (1, 1) : 최근에 사용되었고 변경도 된 경우
clock scheme을 사용하지만 4가지의 우선순위를 고려한다. 교체의 우선순위는 1 > 2 > 3 > 4 이다.
Counting algorithm
몇 번 참조가 되었는지 카운팅한다. 하지만 keep track 어려움
LFU (Least Frequently Used) algorithm
가장 적게 참조된 page를 replace
MFU (Most Frequently Used) algorithm
가장 많이 참조된 page를 replace
Page-Buffering algorithms
thread pool과 비슷한 개념으로 free frame을 미리 생성하고 갖고 있다가 필요할 때 할당해준다. (Page-Buffering) - instruction이 들어와서 실행되기까지의 시간을 줄일 수 있다. page replacement는 언젠가는 발생하기에 줄이지는 못 함
page fault를 빨리 처리해야 프로세스가 실행되기에, 이런 바쁜 시간이 아닌 시간이 남을 때(CPU가 idle할 때) free frame을 미리 확보해놓는다.
몇 번 frame의 page를 요청한다면, 이전에 사용한 적이 있는지 확인하고 있으면 page를 복사하지 않고
Allocation of Frames
각 프로세스가 최소한의 frame 수를 확보하고 있어야 한다.
2가지 주요 할당 방식이 존재한다.
Fixed allocation
Equal allocation : OS에 할당되고 남은 공간에 102개의 frames과 5개의 프로세스가 존재한다고 가정하면, 각 프로세스에 20개의 프레임을 준다.
Proportional allocation : 각 프로세스가 요구사항에 맞게 비레하여 할당된다.
Priority allocation
우선순위가 낮은 프로세스로 부터 frame을 replace 가능
Local replacement : 나한테 할당된 공간에서 replacement
상대적으로 각 process별 성능을 예측 가능하지만 전체 memory에서는 여전히 메모리를 효율적으로 쓰고 있는게 아님
Global replacement : 나한테 할당된 공간을 넘어 외부에서 replacement
throughput 측면에서 좋지만
NUMA(Non-Uniform Memory Access)
각 process별로 CPU와 메모리에 접근하는데 걸리는 시간이 다른 시스템이기에 latency group을 만들어 더 빠른 접근이 가능한 그룹을 우선순위로 할당해준다. 멀티 프로세싱 프로그램에서 어떤 프로그램을 먼저 할지를 결정해주는 latency group
Trashing
page fault가 너무 발생하여 page fault 처리 시간이 프로세스 동작 시간(instruction 수행 시간)보다 더 걸렸을 때를 말한다.
너무 많은 프로세스들이 동시에 나뉘어 메모리에 있기에 일어난다.
프로세스들이 점점 더 늘어나면서 이 프로세스들을 할당하기 위해 더 작게 나누는 부분에서 발생한다. (너무 많이 적재되면 성능이 떨어짐)
왜 demand paging이 작동할까 ?
비슷한 메모리를 계속 접근하는 경향을 보이는걸 locality model이라고 한다.
Trashing이 발생했을 때 어떻게 해야 할지를 정해주는 기준표? 가 있다.
Working-Set Model
어떤 프로세스들이 얼마만큼의 page에 접근했는지 확인
Page-Fault Frequency
page fault가 얼마나 발생했는지를 확인
page fault가 upper bound를 넘어가면 page fault가 많이 발생하여 trashing
page fault가 lower bound 아래이면 page fault가 거의 일어나지 않기에, 프로세스가 좀 더 frame을 얻게 하여 upper bound와 lower bound 사이를 유지하도록 한다.
Memory-Mapped Files
file은 disk에 저장되어 있는데 I/O 접근은 overhead가 발생
→ file에 쓰고 싶은 내용을 메모리에 가져와서 쓰고 disk에 보내자.
주기적으로 한번에 처리하기에 접근시간이 줄어든다.
단, 메모리에 file을 저장할 수 있는 공간이 있다고 할 때 가능
mid-term scheduler - swapping 결정해주는
Kernel Memory 할당
kernel memory 할당은 다르게 취급된다. User application보다 예측 가능한 형태이기 때문이다.
다음은 OS가 할당되는 방법들이다.
Buddy System
A가 100K만큼의 공간 할당을 요청 그러면 1M를 512K, 256K, 128K, 128K로 나눈다. 나눈 조각 중에 128K에 할당 B가 240K가 요청 256K에 할당 C가 64K를 요청 128K를 64K 64K로 나누어 할당, C가 release되면 64K가 비어지고 다른 64K와 합쳐져서 128K가 된다.
hole 관리를 효율적으로 한다.
Slab Allocator
data structure에 대한 cache(사이즈 별로 모여진 것) 이 중 하나(그룹 중 한 개)를 slab(메모리 안에 있는 연속적인 물리 주소 공간)과 연결해서 할당
상대적으로 예측 가능한 형태이기에 각 사이즈 별로 나누고 이를 연속적으로 할당한다.
Buddy 보다 다양한 크기를 지원한다.
다른 고려사항
Prepaging
pure demand paging보다는 빠른 initialize
Page Size
demand paging에서는 I/O overhead(크기가 크면 속도 느림)가 추가된다. 이를 추가적으로 고려해야 한다. 하지만 I/O transmission이 점점 빨라지고 있는 추세
(page는 디스크와 메모리 사이의 I/O와 관련있기에)
Page 크기가 크면 I/O overhead가 늘어나지만 page fault가 발생할 확률이 줄어들고
page 크기가 줄어들면 I/O overhead는 줄어들지만 page fault가 발생할 확률이 늘어난다.
어떤 면을 중요하게 생각하느냐에 따라 page 크기를 달리 결정해야 한다.
작은 page - internal fragmentation, locality
큰 page - page table size, I/O overhead
I/O interlock
어떤 프로세스가 입출력 요구를 하면 이 요구는 입출력 장치의 Queue에 들어간다. 그동안 CPU는 다른 프로세스에게 할당된다.
그런데 이 프로세스가 page fault를 일으키고 global replacement을 사용하여 입출력 요청 후 대기 중인 프로세스의 page를 교체한다. (page out)
얼마 후 입출력 요청이 처리된다. 하지만 원래 버퍼가 있는 frame은 다른 프로세스에 의해 사용되고 있다.
이러한 문제를 해결하기 위해 I/O interlock이 존재한다.
demand paging의 victim이 된다는 것을 알지만 이 부분을 써야 하기에 I/O lock을 걸어준다. lock이 걸려있으면 이 page를 교체하지 않고 넘어가게 된다.
종합적인 문제임
스케쥴링이 독립적으로 이루어지고 스와핑, 메모리 관리, 동적 적재, 가상 메모리 등 이 모든 것이 유기적으로 수행되도록 고려해야 한다.
OS를 설계할 때 꼭 고려해야 할 사항이다.
