-
[OS] - Paging AlgorithmCS/면접준비 2022. 9. 30. 12:49
Paging Change Algorithm
요청하는 Page가 Main Memory에 없다면(Page Fault) -> 새로운 Page 할당 -> 할당된 Page 중에서 어떤 것을 Main Memory에서 내려서 사용할 것인가?
- Virtual Memory는 필요한 Page만 Memory에 적재한다.
- 그럼에도 Main Memory가 가득 찰 수 있다.
- 가득차게 된다면 안쓰는 Page는 Out 하고 요청한 Page를 In해야 한다.
- 이 때 Page Out되는 Page를 Victim Page라고 하며, 수정이 되지 않은 Page를 우선으로 하여 Page Out한다. ( 수정되면 Disk 작업이 필요하다 )
Page Reference String
- Cpu는 Logical Address를 통해 특정 Address를 요구한다.
- Main Memory의 Address들은 Page 단위로 가져오기 때문에 번호가 연속되어도 결함이 없다.
- Processor(CPU) Address request에 따라 Page이 결함이 일어나지 않는 부분이 생략되는 것을 의미한다.
# Example CPU 주소 = {100, 101, 102, 432, 612, 103, 104, 611, 612} Page 번호 = {1, 1, 1, 4, 6, 1, 1, 6, 6} Page reference string = {1, 4, 6, 1, 6}
Page Change Algorithm
1. FIFO ( First In First Out )
- Victim = 먼저 들어온 Page를 Out
- 간단하면서 초기화 코드에서 적절하다.
- 초기화 코드란 Process가 처음 실행될 때, 초기화 시키는 역할만 진행하고 다른 역할이 없는 Process임으로 Main Memory에 없어도 괜찮은 코드
2. OPT ( Optimal Page Replacement )
- 앞으로 가장 사용하지 않은 Page를 우선적으로 내보낸다.
- FIFO에 비해 Page Fault를 많이 낮추어 준다.
- 앞으로 사용하지 않을 Page를 예측은 어떻게 할 것이며, 예측하더라도 실제와 다를 가능성이 높다.
3. LRU ( Least Recently Used )
- 최근에 사용되지 않은 Page를 내보낸다.
- 가정 : 최근에 사용하지 않으면 이후에도 사용하지 않는다.
- OPT보다 Page Fault가 발생하지만, 현실적이고 실제로 사용 가능한 Algorithm
교체 방식
1. Global
- Memory 상의 모든 Process의 Page를 Out 가능
- Trashing = Memory 상에 올라온 Process가 늘어날 수록 CPU의 이용량이 증가하지만, 특정 구간을 넘어서면 많은 Page Fault를 발생시켜 CPU 이용률이 감소하고 빈버한 Swap in/Swap Out이 발생한다.
2. Local
- Memory 상의 자신의 Process에서만 Page Out 가능
'CS > 면접준비' 카테고리의 다른 글
[OS] - File System (1) 2022.09.30 [OS] - Memory (1) 2022.09.30 [OS] - Paging / Segmentation (0) 2022.09.30 [OS] - Semaphore / Mutex (0) 2022.09.30 [OS] - DeadLock (0) 2022.09.29