OS를 공부하면서 정리를 한 내용들 입니다.

Paging System에서 LRU, LFU 가능한가?

그림 출처 : 반효경 교수님 강의 중..

그림을 하나씩 따라갑니다.

Process A가 CPU를 가지고 있는데(running 중)

이 프로그램이 메모리를 참조하고자 주소변환을 합니다.

상황 1. 찾고자하는 주소의 페이지가 이미 물리적인 메모리에 올라와있다.

해당 페이지가 이미 물리적인 메모리에 올라와있다면 바로 CPU가 그 페이지를 가져갑니다.

이 상황에선 운영체제가 개입하는 것이 없습니다.

그렇기에 메모리에 올라와있는 페이지는 그대로 가져갈 수 있기에 페이지를 언제 사용했는지 운영체제는 모릅니다.

이와 같이 운영체제가 LRU 알고리즘을 운영하려면 페이지들이 사용되는 시점을 그때마다 알아야합니다.

상황 2. 찾고자하는 주소의 페이지가 물리적 페이지에 없고, 백킹 스토리지에 있다.

이런 경우 page fault가 발생하고, 이때 CPU 제어권이 Process A로부터 운영체제로 넘어가게 됩니다.

그러면 운영체체가 백킹 스토리지에서 메모리로 올려놓고, 그 과정에서 페이지를 올리는 시점을 알게 됩니다.

따라서 결과적으로는 아래와 같습니다.

OS가 LRU 알고리즘을 사용한다면, OS가 가장 오래 전에 참조된 페이지를 알 수 있는가? NO

OS가 LFU 알고리즘을 사용한다면, OS가 가장 참조 횟수가 적은 페이지를 알 수 있는가? NO

Clock Algorithm

그림 출처 : 반효경 교수님 강의 중..

• LRU를 근사(approximation)시킨 알고리즘

LRU 알고리즘의 경우, 모든 페이지들의 사용 시점을 한 줄로 줄 세운 후 가장 오래전에 사용된 페이지를 쫓아냅니다.

그러나 Clock 알고리즘의 경우, 모든 페이지들의 사용 시점을 운영체제가 알수 없기 때문에 비트 하나로 판단합니다.

각 페이지마다 0 또는 1로 bit가 적혀있습니다.

이 bit를 reference bit(또는 access bit)이라고 부릅니다.

bit가 1이라는 것은 이 페이지가 최근에 사용된 페이지를 나타내고,

bit가 0이라는 것은 이 페이지가 최근에 사용되지 않은 페이지를 나타냅니다. (가장 오래된 페이지는 아님)

그렇기에 정확한 LRU는 아니지만 근사시킨 알고리즘이라고 볼 수 있습니다.

Circular list를 이용해 시계바늘처럼 돌면서 Reference bit를 이용해 교체 대상 페이지를 선정합니다.

reference bit가 0인것을 찾을 때까지 포인터를 하나씩 앞으로 이동하고, 이동 중 bit가 1인 것은 0으로 바꿉니다.

0인 것은 그 페이지를 교체합니다.

한 바퀴를 되돌아와서도(=second chance) 0이면 그때는 replace 당합니다.

자주 사용되는 페이지라면 second chance가 올 때 1로 설정합니다.

조금 더 개선된 Clock Algorithm

reference bit(access bit)와 modified bit(dirty bit)를 함께 사용하는 방법입니다.

reference bit가 1이라면 최근에 참조된 페이지인 것은 동일 합니다.

modified bit가 1이라면 최근에 변경된 페이지(I/O를 동반하는 페이지) 입니다.

Page Frame의 Allocation

Allocation시에 Problem은 “각 process에 얼마만큼의 page frame을 할당할 것인가?” 입니다.

Allocation의 필요성

1. 메모리 참조 명령어 수행 시 명령어, 데이터 등 여러 페이지 동시 참조
	* 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있습니다.
2. Loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리함
	* 최소한의 allocation이 없으면 매 loop 마다 page fault가 발생합니다.

Allocation Scheme

• Equal allocation : 모든 프로세스에 똑같은 갯수를 할당합니다. 프로그램이 큰 프로그램이 있고, 작은 프로그램이 있을 수 있 듯이 그런면에서는 적절하지 않은 방식입니다.
• Proportional allocation : 프로세스 크기에 비례하여 할당합니다.
• Priority allocation : 프로세스의 priority에 따라 다르게 할당합니다.

Global vs Local Replacement

Global replacement

• Replace 시 다른 process에 할당된 frame을 빼앗아 올 수 있습니다.
• Process 별 할당량을 조절하는 또 다른 방법입니다.
• FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당합니다.
• Working set, PFF 알고리즘을 사용합니다.

Global한 replace Algorithm을 쓰면 각 프로세스에게 할당되는 메모리량이 자동으로 조절이됩니다.

어떤 프로그램이 메모리를 많이 쓰면 많이 할당되고, 적게 사용하면 적게 할당되는 식입니다.

Local replacement

• 자신에게 할당된 frame 내에서만 replacement합니다.
• FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영시

프로세스마다 할당은 일단 해놓고, 어떤 프로그램이 페이지를 쫓아내야할 필요성이 있다면

자기에게 할당된 페이지 중 어떤 것을 쫓아낼 때 알고리즘들 적용이 됩니다.

-참고 KOCW 이화여자 대학교 반효경 교수님 : 운영체제 강의