운영체제 07

본 포스트는 '신용현'교수님의 운영체제 강의를 듣고

이해, 정리한 내용들을 올린 포스트입니다.

- 강의자료는 올리지 않습니다.

---

Virtual Memeory

이전 포스팅에서 요약한 페이징의 경우 메모리보다 큰 프로그램을 사용하기 위해 사용하는 기법입니다. 대신 메모리가 한계가 있다보니 일부분씩만 올리게 되는데 전체를 써야 하는 경우 가상 메모리가 필요하게 됩니다.

 이 경우 프로그램의 일부 페이지만 메모리에 올라가게 하며 logical / physical memory 주소 공간을 분리하며 이 경우 logical이 주로 더 큽니다. (logical이 실제 프로그램이 필요한 메모리 양입니다) 물리적인 메모리의 주소가 더 작으니 Demand Paging을 통해 구현하게 됩니다.

 

Demand Paging

 필요한 경우에 페이지를 들고온다는 개념으로 필요한 경우 디스크에서 메모리로 불러오는 Swap In을 하고 필요 없는 경우 다시 디스크로 보내는 Swap out을 하게 됩니다. 그런데 이런 과정도 디스크를 이용한 I/O 작업이기 때문에 이걸 최대한 줄여야 합니다.

 

 또한 페이지 테이블에 valid / invalid를 위한 비트를 넣어 메모리에 있는지, 없는지를 판별할 수 있게 해줍니다. invalid의 경우 page fault handler가 처리를 해서 fault된 페이지를 가져오는 작업을 하게 됩니다.

 

 <Page Fault Handler가 하는 일>

1. invalid reference의 경우

- 잘못된 주소거나 protection으로 안된 경우 프로세스 중단

- 메모리에 없는 경우 2번으로

 

2. 빈 페이지 프레임 확보하기

- 빈 메모리가 없다면 사용하던걸 replace

 

3. 디스크에서 읽은 뒤 메모리에 올리기

- I/O동안 프로세스는 block

- 작업이 끝나면 페이지 테이블에 valid로 표시, 프로세스는 ready상태로

 

4. 다시 수행

 이런 식으로 fault난 페이지를 잘 처리해줘야 부족한 메모리를 보완할 수 있게  됩니다. 여기서 페이지가 fault날 확률은 0~1로 보고 있으며 가상 메모리를 사용할 때 Access Time의 기댓값은 다음과 같습니다.

(1-p) X 메모리 접근 시간 + p X fault service time

p : page fault 확률

 

Page Replacement

당연히 생각을 해 보면 fault가 있을때는 메모리에 페이지가 없다는 이야기로 다시 불러오기 위해서 시간이 들게 됩니다. 이 시간을 줄이기 위해서 여러가지 방안들을 고려했습니다.

 

1. FIFO Page Replacement

 - 페이지를 교체할때 교체되는 페이지는 가장 먼저 들어온 페이지를 대상으로 합니다.

 - 다만 가끔 메모리가 커졌음에도 불과하고 이 알고리즘을 사용하면 fault가 증가하는 경우가 있습니다. (Belady's Anomaly)

 

2. Optimal Page Replacement

 - 가장 오래동안 사용하지 않을 페이지를 내보내는 알고리즘 입니다.

 - 가장 이상적인 알고리즘으로 현실에서 적용하기에는 앞으로 올 페이지가 무엇인지 알 수 없어 구현할 수 없는 알고리즘입니다.

 - 그래도 시간이 가장 짧기 때문에 다른 알고리즘의 효율성 측정용으로 많이 사용됩니다.

 

3. LRU (Least Recently Used)

 - 실제로 가장 많이 사용하는 방법으로 가장 오랫동안 사용하지 않은 페이지를 내보내게 됩니다.

 - 대신 시간 기록을 위해 overhead가 생기게 되며 시간 기록 대신 count값을 넣거나 하드웨어적 구현으로 용량을 줄입니다.

 - Second change page replacement algorithm (= colck algorithm)이란 방법이 추가적으로 있습니다.

     - 페이지별로 reference bit가 있어 0이면 안한것, 1이면 한 것입니다.

     - 시계방향으로 체크를 하면서 1일 경우 한턴을 넘기고 0으로 바꾼뒤 0이라면 이 페이지를 교체하는 방식입니다.

 

4. LFU (Least Frequency Used)

 - 사용 횟수가 가장 적은걸 내보내는 알고리즘입니다.

 

 

 

Allocation

 위의 내용은 페이지 fault시 페이지 교체를 어떻게 하는가에 대한 이야기였고 이것들은 가변적인게 아닌 Fixed된 Allocation을 전제로 한 것입니다. 즉, 각 프로세스별 사용하는 프레임이 같다고 생각한 것입니다. 실제 프로세스마다 페이지의 크기가 다를 수 있어 이것에 대해 논의를 할 필요가 있습니다.

 

1. Fixed Allocation

각 프로세스별 사용하는 프레임이 동일하다고 합니다. 이걸 조금 더 개선해 프로세스 사이즈에 따라 프레임을 할당해 주는 방법입니다.

 

2. Pirority Allocation

사이즈보다 우선순위에 따라 할당을 해 줍니다. 우선순위가 높은 프로세스에게 더 많은 프레임을 할당해 줍니다.

 

3. Global vs Local Allocation

- Global : 다른 프로세스의 프레임을 사용할 수 있게 해줍니다. 

 - Local : 다른 프로세스의 프레임을 사용할 수 없습니다.

 

 전체적으로 프로세스에 따라 어떻게 메모리를 할당해줄까에 대한 이야기였습니다.

 

 

Trashing

 컴퓨터에 메모리가 적어 프로세스에게 충분한 프레임이 할당되지 않을 경우 page fault가 높아질 수 있습니다. 이로 인해서 CPU 사용량이 줄어들게 되고 OS는 CPU를 그냥 둘 수 없으니 프로세스를 추가하게 됩니다. 떄문에 이로 인해서 악순환이 만들어집니다.

 

* Trashing : 프로세스가 swap in/out를 빈번하게 하는 경우

 

 

Working-set Model

 실제 메모리에서 reference 패턴을 보면 2가지가 나오게 됩니다.

 - Temperal locality : 시간적으로 적은 duration, 시간 지엽성

 - Spatial locality : 상대적으로 인접한 메모리를 참조한 경우

 

쓰레싱이 일어나는가를 판단하기 위해서 Working-set Model을 아래 수식으로 나타내게 됩니다.

 - △ : Working set의 window

 - WSSi : 프로세스 i의 △

    - △가 작으면 locality를 충분히 담을 수 없습니다.

 - D =ΣWSSi

 

 여기서 만약 D가 메모리보다 크다고 하면 쓰레싱이 일어나게 됩니다. 따라서 OS가 프로세스를 하나씩 중단하면서 D <= 메모리 크기 가 될때까지 프로세스를 중단합니다. 이런 일이 일어나지 않게 특정 시간동안 working set window의 크기를 어떻게 할당해줄지 정해야 합니다.