[16] 운영체제 - Virtual Memory-1

안녕하세요! 저번 포스팅까지는 메모리에 관한 포스팅이었다면,

오늘부터는 운영체제에서 중요한 부분인 가상 메모리 (Virtual Memory)에 관한 포스팅을 해보도록 하겠습니다.

전체적인 흐름은 가상 메모리를 관리하는 기법 중 하나인 Demand Paging을 공부하고

이 기법에 사용되는 알고리즘인 Page Replacement Schemes에 관해 공부를 합니다.

마지막으로 이러한 가상 메모리를 사용함으로써 발생할 문제점 중 하나인 Thrashing에 관해 알아보도록 하겠습니다.

그럼 바로 시작해보겠습니다.

가상 메모리 (Virtual Memory)

지금까지 배운 메모리 관리에서는 하나의 프로그램 전체를 실제 메모리에 올리는 방식을 사용했으나,

가상 메모리를 사용한다면 당장 실행에 필요한 부분만 실제 메모리에 올려서 실행하게 됩니다.

예를 들어 Error Handling에 관한 코드가 있으나 너무나 완벽한 소스 코드라면 Error Handling 코드는 실제 메모리에 올라갈 필요가 없게 됩니다. 

또한 배열이나 리스트를 크게 잡아놓고선 사용하지 않는 부분이 크다면 이 역시 사용하는 크기만큼만

실제 메모리에 올라가게 됩니다.

즉 가상 메모리 기법은 프로그램 전체가 아닌 필용한 일부분만 실제 메모리에 올리는 기법입니다.

이렇게 전체가 아닌 부분만을 메모리에 올려 사용하게 되면 어떤 장점이 있을까요?

첫째, 프로그램은 더 이상 Physical Memory의 여유 공간이 얼마나 되는지에 대해서 시작도 하기 전에 고민할 필요가 없습니다.

둘째, 프로그램이 전체 다 올라가지 않기 때문에 더 많은 프로그램들을 동시에 메모리에 올려 작업을 수행할 수 있습니다.

셋째, 한 번에 올리는 소스의 양이 적기 때문에 Disk와 Memory 간 I/O 작업 속도가 빨라집니다.

가상 메모리는 Demand Paging 기법과 Demand Segmentation 기법으로 구현될 수 있는데.

이 포스팅에서는 Demand Paging에 관해서만 알아보도록 하겠습니다.

Demand Paging

Demand Paging의 기본 컨셉은 가상 메모리가 추구하는 방식을 구현하는 기법으로  사용하는 부분만 메모리에 올리는 방법 중 하나입니다.

이러한 Demand Paging을 구현하기 위해서는 하드웨어적인 지원을 필요로 합니다.

그 이유는 바로 Valid-Invalid Bit를 사용하기 때문인데요!

Demand Paging을 사용할 때는 메모리에 올리려는 것이 현재 메모리에 존재하는지 아니면 Disk에 존재하는지를 알아야 합니다. (이전에 Valid-Invalid Bit의 사용법에 약간의 정보가 더 추가된 것입니다.)

case 1) Bit = Valid

    Bit가 Valid라는 뜻은 두 가지 의미를 내포합니다. 해당 Page Table의 인덱스는 접근이 가능하며(이전에 다루었던 내용),

    또한 해당 부분은 실제 메모리에 올라와 있다는 뜻입니다.

case 2) Bit = Invalid

    Bit가 Invalid라는 뜻 역시 두 가지 의미를 내포합니다. 해당 Page Table의 인덱스는 접근 불가능하거나 혹은

    해당 부분은 현재 Disk에 존재한다는 뜻입니다.

Page fault

Page fault란 지금 실행시켜야 할 Page가 실제 메모리에 올라와 있지 않는 것을 말합니다.

이렇게 Page fault가 일어난다면  CPU는 운영체제에게 알리고 운영체제는 잠시 동안 CPU 작업을 멈춥니다.

그리고 Disk에서 해당 부분을 찾아 실제 메모리의 비어있는 Frame에 올리고 Page Table의 해당 부분의 Bit를 Valid로 갱신합니다.

그 후 Page fault를 일으켰던 명령어를 다시 실행하여 작업을 재개합니다.

다음 그림은 Page fault의 전체적인 흐름을 보여줍니다.

page fault

하지만 여기서 이런 의문이 생길 수 있습니다.

"실제 메모리에 비어있는 Frame이 존재하지 않으면 어떡하지?"

이때 사용하는 것이 바로 Page Replacement 알고리즘입니다.

이 알고리즘의 핵심은 현재 자신이 차지하고 있는 Frame을 지금 당장 실행해야 할 Page에게 넘겨줄 Victim Frame을 찾는 과정입니다.

여기서 Victim Frame은 "자주 사용되지 않는" Frame입니다.

이러한 Page Replacement 알고리즘에서도 Page fault를 적게 발생할수록 좋은 알고리즘이라고 볼 수 있습니다.

Page Replacement 알고리즘이 Victim Frame을 찾는 것을 도와줄 수 있는 것이 바로 Modify Bit입니다.

Modify Bit는 현재 메모리에 올라가 있는 Page들 중에서 내부 데이터가 바뀌었는지를 알려주는 Bit이며

내부 데이터가 바뀌었다면 Disk와의 동기화를 위해 Swap-out 될 필요가 있습니다. 

이러한 Swap-In / Swap-out은 많은 비용을 발생시키는데요. 그리하여 Victim Frame을 찾을 때는 Modify Bit가 0인 즉 Swap-out 될 필요 없는 Frame을 우선적으로 찾게 됩니다. Swap-out 될 필요가 없으니 그 자리에 덮어 씌어버리면 되기 때문입니다.

그리하여 정리해본 기본적인 Page Replacement의 과정은 다음과 같습니다.

1. 원하는 Page를 Disk에서 찾는다.

2. 비어있는 Frame을 찾는다.

    a ) 비어있는 Frame을 찾았다면 사용하면 된다!

    b ) 비어 있는 Frame이 존재하지 않는다면 Page Replacement 알고리즘을 통해 Victim Frame을 찾는다.

3. Disk에서 가져온 Page를 2번 과정에서 찾은 Frame에 넣고 Frame Table과 Page Table을 갱신합니다.

4. 프로세스를 재실행합니다.

그림으로 정리해본다면 다음과 같습니다.

Page Replacement Algorithm

Page Replacement 알고리즘에도 여러 가지가 있습니다. 그럼 알고리즘들을 하나씩 살펴보도록 하겠습니다.

1. FIFO algorithm

    말 그대로 실제 메모리에 올라온 지 (Frame을 차지한지) 가장 오래된 Frame을 선택하는 알고리즘입니다.

    밑의 그림을 보면 2번 Page에 대한 Frame 요청이 들어왔을 때 가장 오래된 7번 Page의 Frame이 선택되는 걸 보실 수 있습니다.

FIFO algorithm

하지만 FIFO 알고리즘은 Frame 수가 많아도 Page fault가 많이 발생하는 모순을 일으키게 됩니다.

(Frame이 많다면 Page fault가 적어야 한다.)

2. Optimal algorithm

   이 알고리즘은 가장 오랫동안 사용되지 않을 Frame을 Victim Frame으로 선택하는 알고리즘입니다.

(말 그대로 "사용되지 않을", 예측이 필요한 알고리즘이기 때문에 이론상으로만 존재하며 다른 알고리즘들의 성능 비교를 위해 사용됩니다.)

Optimal algorithm

네 번째 순서에서 2번 Page가 실행되어야 하는데 메모리에 존재하지 않는다면 Page fault가 일어나고 Disk에서 찾아 메모리에 올리기 위해 비어있는 Frame을 찾게 됩니다. 하지만 그림과 같이 비어있는 Frame이 존재하지 않는다면 Optimal 알고리즘은 가장 오랫동안 사용되지 않을 Page의 Frame을 선택하게 되는데 위의 그림에서는 7번 Page의 Frame이 선택되게 됩니다. 

위의 실행 순서를 보시면 7번 Page의 다음 실행 순서는 0, 1, 2 ,3 , 4에 비해 가장 나중에 실행되기 때문입니다.

3. LRU(Least Recently Used) algorithm

    이름 그대로 가장 오랫동안 사용되지 않은 Page의 Frame을 선택하는 알고리즘입니다. (FIFO와는 미묘한 차이를 보입니다.)

FIFO의 차이점은 그림에서 찾아보실 수 있으실 텐데요! 

FIFO의 그림에서는 6 번째 실행 순서인 3번 Page가 Victim Frame을 찾을 때 메모리에 올라온 지 가장 오래된 0번째 Page의 Frame을 선택합니다. 하지만 LRU에서는 0번째 Page는 바로 직전에 실행되었기 때문에 실행된 지 가장 오래된 1번 Page의 Frame을 선택하게 됩니다.

LRU 알고리즘은 최근에 실행되었으면 조만간 다시 한번 사용될 것이라고 가정하기 때문입니다.

이러한 LRU 알고리즘을 구현하기 위해서는 두 가지 방법이 있습니다.

첫 번째로는 해당 Page가 실행될 때 실행된 시간을 Page Table의 해당 부분에 저장하는 방법입니다.

두 번째로는 실행되는 순서를 Stack으로 쌓아서 관리하는 것입니다. 그렇다면 Stack의 순서는 위에서 아래로 최근에서 과거 순이 됩니다.

Stack

하지만 이러한 방법들은 하드웨어적인 지원을 필요로 합니다.

이러한 하드웨어적인 지원을 필요로 하지 않는 개선된 LRU algorithm이 존재합니다.

하지만 글이 길어지는 것을 막고자 위의 알고리즘과 다른 Page Replacement 알고리즘들은 다음 포스팅에서 알아보도록 하겠습니다.

애매하게 글을 끊게 되어서 정말 죄송합니다..!!

사실 수업을 여기까지 진행하여서 뒤의 내용을 더욱 정확하게 포스팅하기 위해서는 수업을 듣고 글을 쓰는 것이 맞다고 생각하여

여기서 끊고 다음 시간에 마저 이어서 공부를 해보도록 하겠습니다.

사실 이번 포스팅을 작성하면서 제 글에 대한 자신감이 많이 떨어졌습니다. 수업도 열심히 듣고 구글링도 많이 해봤지만

이해가 확실히 안됐다고 생각하기 때문입니다. 그래서 오점이 많을 수 있는데 이 점은 계속 공부를 하면서 수정해가도록 하겠습니다.

많은 피드백 부탁드리겠습니다! 감사합니다.