Virtual Memory System 구현 방법
- Paging
- Segmentation
- Combined
Combined Paging and Segmentation
- Process 를 Segment 단위로 나눈다.
- PCB
- CODE
- DATA
- STACK
- 다시 각각의 Segment 를 Page 단위로 나눈다.
페이지 번호는 Segement 안에서 몇번째 페이지인지를 나타낸다.
→ 프로그램 전체에서 몇번째 페이지인지를 나타내는 것이 아니다.
최종적으로 페이지 단위로 메모리에 들어가게 된다.
→ 메모리는 페이지 프레임으로 나누어져 있어서 External Fragmentation 이 없다.
- Paging eliminates external fragmentation
- Segmentation allows for modularity and support for
sharing and protection - Each segment is broken into fixed-size pages
Combined Paging and Segmentation 의 장점
최종적으로 페이지 단위로 자르기 때문에 External Fragmentation 이 존재하지 않는다.
⇒ Segmentation 의 문제점 해결
한 페이지 안에 코드나 데이터가 겹치지 않기 때문에 Protection 과 Sharing 이 잘된다.
Combined Paging and Segmentation 의 단점
단순 Paging System 은 마지막 한페이지에서만 Internal Fragmentation 이 발생하지만, Combined Paging and Segmentation 에서는 Segmentation 마다 Internal Fragmentation 이 발생한다.
code 를 access 해야할 때, Virtual Address는 1번 세그먼트의 4번 페이지의 12번째 offset 을 나타낸다.
이 페이지는 프레임 안에 들어 있기 때문에 메모리의 실제 프레임들이 쭉 있는데 이 페이지는 이 중에 어딘가에 들어 있다.
6번이라고 한다면, 우리에게 필요한 건 6번이라는 프레임 정보만 알면, 프레임 번호에 offset 을 붙여 Physical Address 를 만들어 낼 수 있다.
최종적으로 우리가 필요한건 6번이라는 프레임 번호이고 이 프레임 번호는 페이지 테이블에 들어 있다.
Combined Segmentation and Paging
Segment Table Entry
페이지 테이블의 엔트리를 보면, P bit, M bit, Frame# 가 있다.
→ 특정 페이지가 어떠한 프레임에 있는지에 대한 정보가 페이지 테이블에 저장되어 있다.
Length:
세그먼트에 속하는 마지막 페이지의 번호가 적혀 있다.
원래는 세그먼트의 길이가 들어가지만 우리는 여기서 페이지 단위로 잘랐다.
따라서 실제 길이가 아니라, 몇번 페이지까지 있는지 알려주는 정보이다.
→ 세그먼트마다 페이지의 개수가 다르다.
Length 와 찾으려는 Page# 를 비교한다.
→ Page# > Length ⇒ 프로그램 중단
Segment Base:
Base 값은 세그먼트에 속하는 페이지들에 대한 정보가 들어 있는 페이지 테이블의 시작 주소이다.
Base 값은 세그먼트 테이블의 베이스 값과 페이지 번호를 더해서 페이지 테이블 안에서 내가 원하는 엔트리가 들어 있는 위치를 찾아 나간다.
페이지 번호가 인덱스인데, 세그먼트 테이블 안에 들어 있는 베이스는 이 세그먼트에 속하는 페이지들에 대한 정보가 들어 있는 페이지 테이블의 시작 주소이다.
원래 동적할당을 할 때, Dynamic 할당을 할 때 Segment 를 그냥 메모리에 집어 넣으므로 Segment 시작 주소를 적어 놓는 곳이었다. 근데 우리는 세그먼트를 전체를 통으로 메모리에 집어 넣지 않는다.
즉, 베이스는 세그먼트의 시작 주소가 아니라 이 세그먼트에 속한 페이지들의 정보가 들어 있는 페이지 테이블이 메모리 몇번지에 있는지를 나타낸다.
Address Translation
실제 주소 변환 과정
- 레지스터에는 페이지 테이블이 아닌, 세그먼트 테이블의 시작 주소가 들어 있다.
- 세그먼트# 를 인덱스로 해서 세그먼트 테이블에서 내가 원하는 몇번 세그먼트에 대한 정보를 찾는다.
- 주소에 맞는 세그먼트 테이블에 가보면 Length, Base 가 엔트리의 요소로 들어 있다.
- 위의 예시에서 Length 는 6이다. 즉, 세그먼트 테이블의 Length 에는 세그먼트에 속하는 마지막 페이지의 번호가 적혀 있다.
→ 세그먼트 안애 내가 찾는 페이지가 있는지부터 확인해야 한다.
→ 1번 세그먼트의 4번 페이지라고 안하고 1번 세그먼트의 7번 페이지 라고 하면 Length 값과 비교했을 때 6 < 7 이므로 Page Fault 가 발생하고 프로그램이 중단되게 된다. - Base 값은 세그먼트 테이블의 베이스 값과 페이지 번호를 더해서 페이지 테이블 안에서 내가 원하는 엔트리가 들어 있는 위치를 찾아 나간다.
페이지 번호가 인덱스인데, 세그먼트 테이블 안에 들어 있는 베이스는 이 세그먼트에 속하는 페이지들에 대한 정보가 들어 있는 페이지 테이블의 시작 주소이다.
1번 세그먼트 / Length = 6 / Base
⇒ Segment Table: root page table 역할
⇒ Page Table: 2nd Page Table 역할
Fetch Policy
Determines when a page should be brought into memory
어떤 Page 가 필요 → HardDisk 에서 그것만 가져올지? 아님 그 다음 페이지도 가져올지?
몇 페이지를 가져오든 속도는 차이가 없다.
다만, HardDisk 에서 페이지를 가져올 때 가져오는 양이 아니라 access 하는 횟수에 따라 소요시간이 결정된다.
Demand Paging 👍
내가 필요한 페이지만 가져온다.
⇒ 결론적으로 Demand Paging 이 좋다.
Demand paging only brings pages into main memory when a reference is made to a location on the page
- Many page faults when process first started
Pre-paging
내가 필요한 것 이상의 페이지를 가져온다.
→ 전체 메모리의 반이 현재 사용하지 않는 상태가 된다. 반 정도가 현재 사용하는 페이지가 아닌 다음을 대비한 페이지들이다.
⇒ 메모리가 낭비된다.
Pre-paging brings in more pages than needed
- More efficient to bring in pages that reside contiguously on the disk
Replacement Policy
할당해줄 수 있는 페이지 프레임의 수에 제한이 존재한다.
→ 새로 페이지를 가져올 때 메모리에 올라와 있는 기존의 페이지를 버려야 한다.
↳ 최악의 경우, 페이지를 잘못 선택해서 버리면, Thrashing 이 발생할 수 있다.
↔ 페이지를 잘 선택해서 버리면, PageFault 가 줄어든다. → HardDisk Access 횟수 = 10 : 20
PageFault 가 발생하면 Process block 이 발생하고 하드디스크에 가서 필요한 페이지를 가져와야 하고, 결론적으로 프로그램 실행 속도가 느려지게 된다. ← OS 의 잘못
⇒ 어떤 페이지를 버려야할지 고민해야 한다. → Page Fault 과 직결이 된다.
↳ 사용하지 않는 Page 는 버리면 된다.
→ 어떻게?
- 최근에 사용된 Page 를 가져오기
- 과거에 사용되지 않은 Page 를 버리기
지금까지 어떤 페이지를 사용했는지는 알 수 있지만, 앞으로 어떤 페이지를 사용할지는 알 수 없다.
따라서 최근에 사용됐던 페이지는 냅두고, 오랫동안 사용하지 않는 페이지는 버리게 된다.
Examples
An example of the implementation of these policies will use a page address stream formed by executing the program is
↳ PageFrame = 3개, Page = 5개
Basic Replacement Algorithms (4가지 존재)
Optimal Policy
- Selects for replacement that page for which the time
to the next reference is the longest - Impossible to have perfect knowledge of future events
앞으로 가장 오랫동안 사용하지 않을 페이지를 버리는 방식
- Page Fault 의 수가 최소인 방식이다.
- 하지만, 실제 구현은 불가능한 기법이다.
내가 무슨 페이지를 사용할지 미리 다 알고 있어야 하기 때문이다.
↳ 그런데 왜 존재하는걸까? → Optimal Policy 가 다른 Policy 들의 기준 이 된다.
Optimal Policy 의 Page Fault 수와 비교해서 Page Fault 가 적게 일어 났는지 많이 일어났는지를 확인한다.
Optimal Policy Example
⇒ 3번 페이지 Fault 가 발생한다. (최소의 횟수)
처음엔 그냥 비어있는 프레임에 페이지를 가져온다.
메모리가 다 차기 전까지(프레임이 비어 있는 경우) 발생하는 Page Fault는 수를 세는데 포함하지 않는다.
→ 우리는 지금 Replacement 에서 발생하는 Page Fault 수를 세는 것이기 때문에 기존에 있는 페이지를 버리는 경우만 Page Fault 수를 세는데 포함된다.
⇒ Page Fault 가 아닌 것은 아니다.
다시는 사용하지 않을 페이지를 버리거나 앞으로 제일 사용 횟수가 적을 페이지를 버린다.
둘 다 버릴 수 있는 상황에서는 앞선 번호의 프레임의 페이지를 버린다.
Basic Replacement Algorithm
best fit 과 worst fit 은 메모리 전체를 확인했어야 했다.
LRU (Least Recently User)
최근에 가장 사용하지 않은 페이지를 버린다.
⇒ 가장 오랫동안 사용되지 않은 페이지를 버린다.
- 과거를 보고 최근에 사용한 적이 있는 경우 → 버리지 않는다.
- 과거를 보고 최근에 사용한 적이 없는 경우 → 버린다.
근거: Reference의 locality
Reference의 locality ⇒ 당분간은 최근에 사용한 적 있는 페이지에 있는 Code 와 Data 를 계속 사용할 것이다.
- Replaces the page that has not been referenced for
the longest time - By the principle of locality, this should be the page least likely to be referenced in the near future
- Each page could be tagged with the time of last reference. This would require a great deal of overhead.
LRU 의 문제점
공간적 시간적 문제를 해결해야 한다. → Overhead 가 많다.
공간적 문제
각 페이지마다 마지막으로 access 된 시간 기록이 필요하다.
TIME_STAMP 가 필요 ⇒ 테이블 엔트리 요소가 추가되며 공간적인 문제가 존재하게 된다.
시간적 문제
시간적 문제도 존재한다. 최근에 가장 적게 → 가장 오랫동안 사용되지 않은 페이지를 찾기 위해 Best-fit, Worst-fit 처럼 존재하는 페이지를 다 비교해야 한다.
⇒ 시간이 어마어마하게 많이 걸리게 된다.
LRU Example
제일 오랫동안 사용되지 않은 페이지를 버린다.
⇒ 4번 페이지 Fault 가 발생한다. → Optimal Policy 와 거의 성능이 비슷하다.
- The LRU policy does nearly as well as the optimal policy.
- In this example, there are four page faults
Basic Replacement Algorithm
First-in, First-out (FIFO)
→ 사용 X
메모리에 들어온 가장 오래된 페이지를 버린다.
오랫동안 사용되지 않은 페이지를 버리는게 아니라 메모리에 들어온지 가장 오래된 메모리를 버린다.
Page Fualt 수는 많지만, 공간적, 시간적 Overhead 가 거의 없다.
- Treats page frames allocated to a process as a circular
buffer - Pages are removed in round-robin style
- Simplest replacement policy to implement
- FIFO Anomaly
FIFO Anomaly
할당한 프레임 수가 많아질 수록 Page Fault 수가 줄어든다. 하지만, FIFO 는 그렇지 않은 경우가 있을 수 있다.
즉, 할당한 프레임 수가 증가해도 Page Fault 수가 줄어들지 않고 증가할 수도 있다.
더 많은 공간을 줬다고 해서 Page Fault 가 발생하는 것이 아니다.
시간적 공간적 문제를 해결하는 대신 하드디스크에 조금 더 다녀오겠다는 생각으로 FIFO 를 사용할 수도 있지만, 이 이상한 현상이 발생하기 때문에 FIFO 를 사용하는 시스템은 거의 없다.
FIFO Example
⇒ 6번 페이지 Fault 가 발생한다.
FIFO 가 Page Fault 가 제일 많다. ⇒ 프로세스가 Block 되는 횟수가 많아지고, 하드디스크에 접근해야 하므로 실행 시간이 제일 길어진다.
대신, LRU 에서 존재하던 시간적, 공간적 overhead 가 없다.
→ 시간 기록이 필요할 것 같지만, 필요하지 않다.
메모리에 들어온지 가장 오래된 페이지 이므로 메모리에 들어온 시간이 필요할 것 같지만, 페이지 교체한 순서를 보면, 0 → 1 → 2 → 0 → 1 → 2 → 0 → 1 → 2 순서로 페이지를 교체하는 것을 확인할 수 있다.
페이지 프레임 0번 부터 페이지를 집어 넣기 때문에 이 페이지 프레임 번호 순서가 메모리에 들어온 순서이다. 프레임이 n개 존재할 때 0번 부터 n-1 번까지 가면, 다시 0번 프레임부터 시작되는 것이다.
Circular Buffer 로 Round Robin 방식으로 돌아가면서 페이지 교체를 한다.
공간적 overhead 는 마지막에 교체된 페이지가 어딘지를 가르키는 포인터 하나만 있으면 해결이 된다.
시간적, 문제는 비교할게 없으므로 시간적 overhead 도 존재하지 않는다.
Basic Replacement Algorithm
Clock Policy
딱 한 비트만 사용할 것이다. ⇒ 페이지 테이블이 커지지 않는다.
LRU → 4 byte 필요 ↔ Use Bit → 1bit 필요 (LRU에 비해 1/32 bit로 문제해결가능)
페이지가 메모리로 올라오면 use bit 가 0 이었다가 페이지가 사용되면 use bit 가 1로 바뀌게 된다.
내가 페이지를 가져오는 건, page fault 가 발생했을 때 이다.
⇒ Blocked 된 Process 의 Use bit 는 Ready 일 때 까지만 0이고 Running 하자마자 1이된다.
⇒ 금방 1이 된다.
Use bit 가 0 인 페이지를 찾아서 교체한다. → 1인 애를 만나면 버리진 않지만, 0으로 바꾸고 지나간다.
- 공간적인 면에서 overhead 가 감소한다.
- 시간적인 면에서 바늘이 적당한 속도로 움직인다. → 바늘이 돌아다니는 속도는 Page Fault 의 개수에 따라 달라진다.
시간적인 면에서 Clock 기법은 바늘이 엄청 빠른 속도로 움직이면 use bit 가 전부 0이 될 것이다.
반면 바늘이 엄청 느린 속도로 움직이면 use bit 는 항상 1이 될 것이다.
바늘이 적당한 속도로 움직이면, 바늘이 지나가며 use bit 를 1에서 0으로 바꾸는데,
바늘이 나한테 다시 돌아왔을 때 use bit 가 여전히 0이라면 한시간 동안 사용하지 않은 것이고, 1이라면 한시간 동안 사용한 적이 있는 페이지라는 뜻이다.
⇒ 내가 자주 사용하는 페이지는 금방 다시 1이 된다.
가장 오랫동안 사용하지 않은 페이지를 골라내는 것은 아니지만, 적어도 바늘이 한바퀴 돌 동안 사용하지 않은 페이지를 버리게 되는 것이다.
- Page Fault 가 자주 발생하면, 바늘이 빠르게 돌게 된다.
- Page Fault 가 자주 발생하지 않으면, 바늘이 천천히 돌게 된다.
- Page Fault 가 적절히 발생하면, 적절한 시간 간격으로 바늘이 돌게 된다.
바늘이 한바퀴 도는 시간동안 사용되지 않은 페이지를 버린다.
제일 오랫동안 사용안한 페이지가 아니라 최근에 사용하지 않은 페이지를 버린다.
⇒ Overhead 가 LRU 보다 적다.
Clock Policy Example
화살표(바늘)는 마지막으로 교체한 페이지 프레임 바로 다음 프레임을 가리킨다.
*O → use bit = 1*X → use bit = 0
항상 바늘이 있는 지점부터 use bit 를 검사한다.
⇒ 한바퀴를 다 도는 것이 최악의 상황이다.
페이지를 교체하지 않으면 바늘은 움직이지 않는다. 페이지 교체를 할 때만 바늘은 움직이고,
페이지 교체를 할 때만 Page Fault 의 수에 포함한다.
내가 필요한 페이지가 메모리에 있으면 바늘은 움직이기 않는다.
원래 있던 페이지에 바늘이 있고 그 페이지가 사용되어 use bit 가 1로 바뀌고 이후에 메모리에 없는 페이지가 요청되면 바늘이 움직이며 다시 0으로 바꾸고 지나간다.
Clock Policy
4번 프레임에 있던 페이지 556의 use bit 가 0이었으므로 페이지 727 로 교체되고, 사용되어 use bit 가 1로 바뀌고 바늘은 다음 프레임인 5번 프레임을 가르키게 된다.
Clock Policy(2)
- Page Frame 수 ↓ Page Fault ↑ ← Locality 때문
- Page Frame 수 ↑ Page Fault ↓ ← Locality 때문
(필요한 페이지가 메모리게 있을 수 있기 때문)
- Clock Policy 는 LRU Policy 쪽에 가깝다.
- LRU 는 Optimal Policy 쪽에 가깝다.
Resident Set Size
프로세스의 페이지 중 메모리에 들어 있는 페이지들의 집합
↳ 즉, 내가 페이지 프레임 몇개를 할당 받았는지를 나타낸다.
Resident Set Size 를 어떻게 결정하느냐에 따라서 LRU, Clock, FIFO 중에 어느것을 사용하는 것이 좋을지 달라질 수 있다.
시스템마다 한 프로세스에게 나누어 주는 페이지 프레임의 수를 결정해야 한다.
- Fixed-allocation 방법
- Variable-allocation 방법
Fixed-allocation
한 프로세스 당 무조건 5개라고 정해두면, 이 프로세스는 4개의 페이지를 가지고 작업을 진행해야 한다.
page fault 가 발생하면 5개 중 한 페이지를 교체한다.
↳ Overhead 계산
LRU 기법이 페이지 기법은 Page Fault 가 제일 적지만, 오랫동안 사용되지 않던 페이지를 버려야 하기 때문에 모든 페이지를 확인해야해 시간이 오래 걸리는 문제가 있다.
↳ Fixed-allocation 같은 경우, 5개 중 오랫동안 사용되지 않은 페이지를 확인하는 것은 시간이 오래걸리지 않다.
공간적 overhead 가 문제 X, 시간만 중요하다. Fixed-allocation 은 시간은 적게 걸리므로
→ fixed allication 을 할 때는 LRU 가 좋다.
오히려 CLock 기법을 사용하면 맞지 않다.
Variable-allocation
프로세스마다 할당하는 Page Frame 차이가 있다. → 프로세스가 실행해서 끝낼때 까지 할당하는 Page Frame이 계속 변한다.
어떤 프로세스가 Page Fault 가 일어났다고 했을 때, 프로세스에 할당된 페이지들 중에 페이지 교체를 하는 것이 아니라, 시스템 전체를 훑어보고 페이지 교체를 진행한다.
→ Clock 기법이 더 적합하다.
