혼자 공부하는 컴퓨터 구조 + 운영체제 | 12장 ~ 끝

프로세스 동기화

동시다발적으로 실행되는 많은 프로세스는 서로 데이터를 주고받으며 협력하며 실행될 수 있습니다. 예를 들어 워드 프로세스서에는 사용자로부터 입력을 받는 프로세스와 입력한 내용의 맞춤법을 검사하는 프로세스, 입력한 내용을 화면에 출력해 주는 프로세스 등이 있습니다. 이 프로세스들은 각기 다른 독립적인 프로세스이지만 공동의 목표를 위해 협력하는 존재입니다. 

 

이렇게 협력적으로 실행되는 프로세스들은 아무렇게나 마구 동시에 실행해서는 안됩니다. 올바른 실행을 위해서는 동기화가 필요합니다. 

프로세스 동기화란 프로세스들 사이의 수행 시기를 맞추는 것을 의미합니다. 

 

- 실행 순서 제어: 프로세스를 올바른 순서대로 실행하기

- 상호 배제: 동시에 접근해서는 안되는 자원에 하나의 프로세스만 접근하게 하기

 

상호 배제(mutual exclusion)은 공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘입니다. 

 

상호 배제를 위한 동기화에 대해 조금 더 알아봅시다. 이와 관련된 고전적이고 유명한 문제로 생산자와 소비자 문제가 있습니다. 생산자와 소비자 문제는 물건을 계속해서 생산하는 프로세스인 생산자와 물건을 계속해서 소비하는 프로세스인 소비자로 이루어져 있습니다. 

 

code -> https://github.com/kangtegong/self-learning-cs/tree/main/producer_consumer 

GitHub - kangtegong/self-learning-cs: 집필서적- 『혼자 공부하는 컴퓨터구조 & 운영체제』 (한빛미디어)

 

동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역을 임계 구역(critical section)이라고 합니다. 두 개 이상의 프로세스가 임계구역에 진압하고자 하면 둘 중 하나는 대기해야 합니다. 임계 구역에 먼저 진입한 프로세스의 작업이 마무리되면 그제서야 비로서 기다렸던 프로세스가 임계 구역에 진입합니다. 

 

임계 구역은 두 개 이상의 프로세스가 동시에 실행하면 안되는 영역이지만, 잘못된 실행으로 인해 여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행하여 문제가 발생하는 경우가 있습니다. 이를 레이스 컨디션(race condition)이라고 합니다. 

 

레이스 컨디션이 발생하면 계좌 잔액 문제나 생산자와 소비자 문제처럼 데이터의 일관성이 깨지는 문제가 발생합니다. 레이스 컨디션이 발생하는 근본적인 이유를 따져봅시다. 고급언어는 실행과정에서 저급언어로 변환되어 실행됩니다. 

 

가령 생산자와 소비자 문제에서 총합을 1 증가 시킨다 혹은 총합을 1 감소시킨다라는 코드는 고급언어 한줄로 작성할 수 있지만, 이는 컴퓨터 내부에서 대략 다음과 같이 여러 줄의 저급 언어로 변환되어 실행됩니다. 

 

컴퓨터는 고급언어가 아닌 저급 언어를 실행하기 때문에 여러 줄의 저급 언어로 변환된 고급 언어 한 줄을 실행하는 과정에서 문맥 교환이 일어날 수 있습니다. 

 

상호 배제를 위한 동기화는 이와 같은 일이 발생하지 않도록 두개 이상의 프로세스가 임계 구역에 동시에 접근하지 못하도록 관리하는 것을 의미합니다. 운영체제는 이러한 임계 구역 문제를 아래 세가지 원칙하에 해결합니다. 다시 말해 상호 배제를 위한 동기화를 위해서는 아래 세 가지 원칙이 반드시 지켜져야만 합니다. 

 

- 상호 배제: 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 접근할 수 없다.

- 진행: 임계 구역에 어떤 프로세스도 접근하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.

- 유한 대기(bounded waiting): 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 언젠가는 임계 구역에 들어올 수 있어야 한다.

 

뮤텍스 락(Mutex lock; MUTual EXclusion lock)은 동시에 접근해서는 안되는 자원에 동시에 접근하지 않도록 만드는 도구, 다시 말해 상호 배제를 위한 동기화 도구입니다. 임계 구역에 진입하는 프로세스는 '내가 지금 임계 구역에 있음'을 알리기 위해 뮤텍스 락을 이용해 임계 구역에 자물쇠를 걸어둘 수 있고, 다른 프로세스는 임계 구역이 잠겨 있다면 기다리고, 잠겨 있지 않다면 임계 구역에 진입할 수 있습니다. 뮤텍스 락의 매우 단순한 형태는 하나의 전역 변수와 두개의 함수로 구현할 수 있습니다. 

- 자물쇠 역할: 프로세스들이 공유하는 전역 변수 lock

- 임계 구역을 잠그는 역할: acquire 함수

- 임계 구역의 잠금을 해제하는 역할: release 함수

 

acquire 함수는 프로세스가 임계 구역에 진입하기 전에 호출하는 함수입니다. 만일 임계 구역이 잠겨 있다면 임계 구역이 열릴 때까지(lock이 false가 될 때까지) 임계 구역을 반복적으로 확인하고, 임계 구역이 열려 있다면 구역을 잠그는(lock을 true로 바꾸는) 함수입니다. release함수는 임계 구역에서 작업이 끝나고 호출하는 함수입니다. 현재 잠긴 임계 구역을 열어주는(lock을 false로 바꾸는) 함수라고 보면됩니다. 

 

세마포어(semaphore)는 뮤텍스 락과 미슷하지만, 조금 더 일반화된 방식의 동기화 도구입니다. 뮤텍스 락은 하나의 공유 자원에 접근하는 프로세스를 상정한 방식입니다. 공유 자원이 여러개 있는 경우 여러개의 프로세스가 각각 공유 자원에 접근이 가능해야합니다. 세마포어는 뮤텍스 락과 비슷하게 하나의 변수와 두 개의 함수로 단순하게 구현할 수 있습니다. 

- 임계 구역에 진입할 수 있는 프로세스의 개수(사용 가능한 공유 자원의 개수)를 나타내는 전역 변수 S

- 임계 구역에 들어가도 좋은지, 기다려야 할지를 알려주는 wait 함수

- 임계 구역 앞에서 기다리는 프로세스에 '이제 가도 좋다'고 신호를 주는 signal 함수

 

세마포어와 뮤텍스 락에는 한가지 문제가 있는데, 사용할 수 있는 공유 자원이 없는 경우 프로세스는 무작정 무한히 반복하며 S를 확인해야 합니다. 이렇게 바쁜 대기를 반복하며 확인할 시간에 CPU는 더 생산성 있는 작업을 할 수 있을 텐데, CPU 주기를 낭비한다는 점에서 손해입니다. 그레서 실제로 세마포어는 더 좋은 방법을 사용합니다. wait 함수는 만일 사용할 수 있는 자원이 없을 경우 해당 프로세스 상태를 대기 상태로 만들고, 그 프로세스의 PCB를 세마포어를 위한 대기 큐에 집어넣습니다. 그리고 다른 프로세스가 임계 구역에서의 작업이 끝나고 signal 함수를 호출하면 signal 함수는 대기 중인 프로세스를 대기 큐에서 제거하고, 프로세스 상태를 준비 상태로 변경한 뒤 준비 큐로 옮겨줍니다. 

 

세마포어는 그 자체로 매우 훌륭한 프로세스 동기화 도구이지만, 사용하기가 조금 불편한 면이 있습니다. 매번 임계 구역에 앞뒤로 일일이 wait와 signal 함수를 명시하는 것은 번거로운 일이기 때문입니다. 이에 최근에 등장한 동기화 도구가 모니터입니다. 모니터는 세마포어에 비하면 사용자가 사용하기에 훨씬 편리한 도구입니다. 모니터는 공유 자원과 공유 자원에 접근하기 위한 인터페이스를 묶어 관리합니다. 그리고 프로세스는 반드시 인터페이스를 통해 공유 자원에 접근하도록 합니다. 이를 위해 모니터를 통해 공유 자원에 접근하고자 하는 프로세스를 큐에 삽입하고, 큐에 삽입된 순서대로 하나씩 공유 자원을 이용하도록 합니다. 즉, 모니터는 공유 자원을 다루는 인터페이스에 접근하기 위한 큐(모니터에  진입하기 위한 큐)를 만들고, 모니터 안에 항상 하나의 프로세스만 들어오도록 하여 상호 배제를 위한 동기화를 제공합니다. 이 밖에도 모니터는 세마포어와 마찬가지로 실행 순서 제어를 위한 동기화도 제공합니다. 특정 조건을 바탕으로 프로세스를 실행하고 일시 중단하기 위해 모니터는 조건 변수를 사용하는데, 조건 변수는 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수입니다. 

 

프로세스를 실행하기 위해서는 자원이 필요한데, 두 개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다린다면 그 어떤 프로세스도 더 이상 진행할 수 없는 교착 상태가 됩니다. 교착 상태는 자원 할당 그래프 (resource-allocation graph)를 통해 단순하게 표현할 수 있습니다. 자원 할당 그래프는 어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 간단한 그래프입니다. 자원 할당 그래프는 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 간단한 그래프입니다. 

 

교착 상태가 발생할 조건에는 네가지가 있습니다. 바로 상호 배제, 점유와 대기, 비선점, 원형 대기입니다. 즉, 아래 조건 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않습니다. 

 

우선 교착 상태가 발생하는 근본적인 원인은 해당 자원을 한 번에 하나의 프로세스만 이용 가능했기 때문입니다. 프로세스도 마찬가지로 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때, 즉 상호 배제 상황에서 교착 상태가 발생할 수 있습니다. 

 

프로세스는 어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다린다면 교착 상태가 발생할 수 있습니다. 이렇게 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태를 점유와 대기(hold and wait)라고 합니다. 

 

교착 상태가 발생하게 된 또 하나의 근본적인 문제는 프로세스가 자원을 비선점(nonpreemptive)하고 있기 때문입니다. 비선점 자원은 그 자원을 이용하는 그 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 이용할 수 있습니다. 즉, 어떤 프로세스도 다른 프로세스의 자원을강제로 빼앗지 못했기 때문에 교착 상태가 발생했다고 볼 수 있습니다. 교착 상태가 발생한 마지막 이유는 프로세스들과 프로세스가 요청 및 할당받은 자원이 원의 형태를 이루었기 때문입니다. 다시말해 자원 할당 그래프가 원의 형태로 그려지면 교착 상태가 발생할 수 있습니다. 이렇게 프로세스들이 원의 형태로 자원을 대기하는 것을 원형 대기(circular wait)라고 합니다. 자원 할당 그래프가 원의 형태가로 그려지면 교착 상태가 발생할 수 있습니다. 원의 형태가 반드시 교착 상태를 의미하는 것은 아닙니다. 

 

운영체제는 애초에 교착 상태가 일어나지 않도록 교착 상태 발생 조건에 부합하지 않게 자원을 분배하여 교착 상태를 예방할 수 있고, 교착 상태가 발생하지 않을 정도로 조금씩 자원을 할당하다가 교착 상태의 위험이 있다면 자원을 할당하지 않는 방식으로 교착 상태를 회피할 수도 있습니다. 그리고 자원을 제약 없이 할당하다가 교착 상태가 검출되면 교착 상태를 회복하는 방법을 취할 수도 있습니다. 

 

교착 상태를 예방하는 방법은 교착 상태 발생 필요 조건 네가지 중 하나를 충족하지 못하게 하는 방법과 같습니다. 즉, 프로세스들에 자원을 할당할 때 상호배제, 점유와 대기, 비선점, 원형 대기 중 하나의 조건이라도 만족시키지 않게 할당하면 교착상태는 발생하지 않습니다. 자원의 상호배제를 없앤다는 말의 의미는 모든 자원을 공유 가능하게 만든다는 말과 같습니다. 다만 이 방식대로면 이론적으로는 교착 상태를 없앨 수 있지만, 현실적으로는 모든 자원의 상호 배제를 없애기는 어렵기에 이 방식을 현실에서 사용하기에는 다소 무리가 있습니다. 

 

점유와 대기를 없애면 운영체제는 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분합니다. 이 방식도 이론적으로 교착상태를 해결할 수 있지만, 단점도 있습니다. 우선 자원 활용률이 낮아질 우려가 있습니다. 점유와 대기를 금지하면 한 프로세스에 필요한 자원을 몰아주고, 그 다음에 다른 프로세스에 필요한 자원들을 몰아줘야 합니다. 이는 당장 자원이 필요해도 기다릴 수 밖에 없는 프로세스와 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산하기 때문에 자원의 활용률이 낮아집니다. 

 

게다가 점유와 대기를 금지하면 많은 자원을 사용하는 프로세스가 불리해집니다. 자원을 많이 사용하는 프로세스는 자원을 적게 사용하는 프로세스에 비해 동시에 자원을 사용할 타이밍을 확보하기가 어렵기 때문입니다. 이는 결국 많은 자원을 필요로 하는 프로세스가 무한정 기다리게 되는 기아 현상을 야기할 우려가 있습니다. 

 

비선점 조건을 없애면 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있습니다. 한 프로세스가 작업이 끝날 때까지 다른 프로세스가 기다려야 하는 자원도 많습니다. 예를 들어 한 번에 하나의 프로세스만 이용 가능한 프린터 자원이 있다고 생각해보세요. 한 프로세스가 이 프린터를 이용하는 도중에 다른 프로세스가 프린터 자원을 빼앗아 사용하기란 어렵습니다. 그렇기에 비선점 조건을 없애 모든 자원을 빼앗을 수 있도록 하여 교착 상태를 예방하는 방법은 다소 범용성이 떨어지는 방안입니다. 

 

원형대기를 없애는 방법은 간단합니다. 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 원형대기는 발생하지 않습니다.

 

교착 상태 회피는 교착 상태가 발생하지 않을 정도로만 조심조심 자원을 할당하는 방식입니다. 교착 상태 회피 방식에서는 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주합니다. 프로세스들에 할당할 수 있는 자원이 충분한 상황에서 프로세스들이 한두 개의 적은 자원만을 요구한다면 교착 상태는 발생하지 않습니다. 프로세스들에 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분하는 방법이 교착 상태 회피입니다.

 

교착 상태가 발생하지 않고 모든 프로세스가 정삭적으로 자원을 할당받고 종료될 수 있는 상태를 안전 상태(safe state)라 부르고, 교착 상태가 발생할 수도 있는 상태를 불안전 상태(unsafe state)라고 부릅니다. 

 

안전 순서열(safe sequence)은 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미합니다. 예를 들어 웹 브라우저, 메모장, 게임 프로세스가 동시에 운영체제 자원을 요청한 상황에서 웹 브라우저, 메모장, 게임 프로세스 순서대로 자원을 할당하면 교착 상태가 발생하지 않는다고 가정해보겠습니다. 이 경우 웹 브라우저 -> 메모장 -> 게임이 안전 순서열이 됩니다. 안전순서열이 있는 상태를 안전 상태라고 볼 수 있습니다. 

 

교착 상태 예방과 회피는 교착 상태 발생을 막기 위한 노력이었다면, 교착 상태 검출 후 회복은 교착 상태 발생을 인정하고 사후에 조치하는 방식입니다. 검출 후 회복 방식에서 운영체제는 프로세스들이 자원을 요구할 때마다 그때그때 모두 할당하며, 교착 상태 발생 여부를 주기적으로 검사합니다. 

 

선점을 통한 회복은 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식입니다. 교착상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당하는 방식입니다. 프로세스 강제 종료를 통한 회복은 가장 단순하면서 확실한 방식입니다. 운영체제는 교착 상태에 놓인 프로세스를 모두 강제 종료할 수 있고, 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료할 수도 있습니다. 전자는 한방에 교착 상태를 해결할 수 있는 가장 확실한 방법이지만 그만큼 프로세스들이 작업내역을 잃게될 가능성이 있고, 후자는 작업 내역을 잃는 프로세스는 최대한 줄일 수 있지만 교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드를 야기합니다. 

 

지금까지 교착 상태와 해결 방법에 대해 알아봤습니다. 교착 상태를 아예 무시하는방법도 존재합니다. 드물게 발생하는 잠재적 문제를 무시로 대처하는 방식으로 타조 알고리즘이라는 방식입니다. 

 

가상 메모리

메모리에 적재된 프로세스들 중에서는 현재 실행되지 않는 프로세스가 있을 수 있습니다. 입출력 작업의 요구로 대기 상태가 된 프로세스라던지, 오랫동안 사용되지 않은 프로세스가 이런 프로세스들에 속합니다. 이러한 프로세스들을 임시로 보조기억장치 일부 영역으로 쫓아내고, 그렇게 해서 생긴 메모리상의 빈 공간에 또 다른 프로세스를 적재하여 실행하는 방식을 스와핑(swaping)이라고 합니다. 

 

이때 프로세스들이 쫓겨나는 보조기억장치의 일부 영역을 스왑 영역(swap space)이라고 합니다. 그리고 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것을 스왑 아웃(swap-out), 반대로 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것을 스왑 인(swap-in)이라고 합니다. 스왑 아웃 되었던 프로세스가 다시 스왑 인될 때는 스왑 아웃되기 전의 물리 주소와는 다른 주소에 적재될 수 있습니다. 

 

프로세스는 메모리 내의 빈 공간에 적재되어야 합니다. 메모리 내의 빈 공간이 여러개 있다면 프로세스를 어디에 배치해야 할까요? 비어 있는 메모리 공간에 프로세스를 연속적으로 할당하는 방식을 알아봅시다. 여기에는 대표적으로 최초 적합, 최적 적합, 최악 적합의 세 가지 방식이 있습니다. 최초 적합은 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식입니다. 즉 운영체제가 빈 공간 A -> 빈공간 B -> 빈 공간 C 순으로 빈 공간을 검색했다면 프로세스는 빈 공간 A에 적재됩니다. 검색을 최소화하고 빠른 할당이 가능합니다. 최적 적합은 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식입니다. 최악 적합은 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식입니다. 

 

프로세스를 메모리에 연속적으로 배치하는 연속 메모리 할당은 언뜻 들으면 당연하게 느껴질 수 있습니다. 사실 이는 효율적인 메모리 사용 방법이 아닙니다. 왜냐하면 연속 메모리 할당은 외부 단편화(external fragmentation)라는 문제를 내포하고 있기 때문입니다.

 

프로세스들이 메모리에 연속적으로 할당되는 환경에서 프로세스들이 실행되고 종료되기를 반복하며 메모리 사이 사이에 빈 공간들이 생깁니다. 프로세스 바깥에 생기는 이러한 빈 공간들은 분명 빈 공간이지만 그 공간보다 큰 프로세스를 적재하기 어려운 상황을 초래하고, 결국 메모리 낭비로 이어집니다. 이러한 현상을 외부 단편화라고 합니다 .

 

외부 단편화를 해결할 수 있는 대표적인 방안으로 메모리를 압축(compaction)하는 방법이 있습니다. 메모리 조각 모음이라고도 부릅니다. 압축은 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식으로 메모리 내에 저장된 프로세스를 적당히 재배치시켜 여기저기 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법입니다. 

 

다만 압축 방식은 여러 단점이 있습니다. 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야 하고, 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기하며, 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하여 압축할 수 있는지에 대한 명확한 방법을 결정하기 어렵습니다. 이에 외부 단편화를 없앨 수 있는 또 다른 해결 방안이 등장했는데, 이것이 오늘날까지도 사용되는 가상 메모리 기법, 그 중에서도 페이징 기법입니다. 

 

가상 메모리는 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술입니다. 이를 가능케 하는 가상 메모리 관리 기법에는 크게 페이징과 세그멘테이션이 있습니다. 페이징 기법을 사용하면 물리메모리보다 큰 프로세스를 실행할 수 있을 뿐만아니라 외부 단편화 문제도 해결할 수 있습니다. 

 

연속 메모리 할당 방식에서 외부 단편화가 생긴 근본적인 이유는 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문입니다. 만일 메모리와 프로세스를 일정한 단위로 자르고, 이를 메모리에 불연속적으로 할당할 수만 있다면 외부 단편화는 발생하지 않습니다. 예를 들어 위 그림에서 메모리 공간과 프로세스들을 10MB 단위의 일정한 크기로 자르고, 잘린 메모리 조각들에 프로세스 조각들을 불연속적으로 적재할 수 있다면 오른쪽 그림과 같이 외부 단편화는 발생하지 않습니다. 이것이 페이징(paging)입니다. 페이징은 프로세스의 논리 주소 공간을 페이지라는 일정한 단위로 자르고, 메모리 물리 주소 공간을 프레임(frame) 이라는 페이지와 동일한 크기의 일정한 단위로 자른뒤 페이지를 프레임에 할당하는 가상메모리 관리 기법입니다. 

 

페이징: 메모리의 물리 주소 공간을 프레임 단위로 자르고, 프로세스의 논리 주소 공간을 페이지 단위로 자른 뒤 각 페이지를 프레임에 할당하는 가상 메모리 관리 기법입니다. 

 

페이징에서도 스와핑을 사용할 수 있습니다. 페이징을 사용하면 시스템에서는 프로세스 전체가 스왑 아웃/ 스왑 인되는 것이 아닌 페이지 단위로 스왑 아웃/스왑 인 됩니다. 즉 메모리에 적재될 필요가 없는 페이지들은 보조 기억장치로 스왑 아웃되고, 실행에 필요한 페이지들은 메모리로 스왑 인되는 것이지요. 페이징 시스템에서의 스왑 아웃은 페이지 아웃, 스왑 인은 페이지인이라고 부르기도 합니다. 

이는 다르게 말하면 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없다는 말과 같습니다. 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하고, 당장 실행에 필요하지 않은 페이지들은 보조 기억 장치에 남겨둘 수 있습니다. 이와 같은 방식을 통해 물리 메모리보다 더 큰 프로세스를 실행할 수 있습니다. 

 

 

프로세스가 메모리에 불연속적으로 배치되어 있다면 CPU 입장에서 이를 순차적으로 실행할 수가 없습니다. 프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 CPU가 모두 알고 있기란 어렵기 때문입니다. 즉, 프로세스가 메모리에 불연속적으로 배치되면 CPU 입장에서 '다음에 실행할 명령어 위치'를 찾기가 어려워집니다. 이를 해결하기 위해 페이징 시스템은 프로세스가 비록 (실제 메모리 내의 주소인) 물리 주소에 불연속적으로 배치되더라도(CPU가 바라보는 주소인) 논리 주소에는 연속적으로 배치될 수 있도록 페이지 테이블(page table)을 사용합니다.

 

페이지 테이블은 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표입니다. CPU로 하여금 페이지 번호만 보고 해당 페이지가 적재된 프레임을 찾을 수 있게 해줍니다. 다시 말해 페이지 테이블은 현재 어떤 페이지가 어떤 프레임에 할당되었는지를 알려줍니다. 위와 같은 방식으로 비록 물리 주소상에서는 프로세스들이 분산되어 저장되어 있더라도 CPU 입장에서 바라본 논리 주소는 연속적으로 보일 수 있습니다. 즉 프로세스들이 메모리에 분산되어 저장되어 있더라도 CPU는 논리 주소를 그저 순차적으로 실행하기만 하면 됩니다. 

 

페이징은 외부 단편화 문제를 해결할 수 있지만, 내부 단편화(internal fragmentation)라는 문제를 야기할 수 있습니다. 페이징은 프로세스의 논리 주소 공간을 페이지라는 일정한 크기 단위로 자른다고 했습니다. 그런데 모든 프로세스가 페이지 크기에 딱 맞게 잘리는 것은 아닙니다. 다시 말해 모든 프로세스 크기가 페이지의 배수는 아닙니다. 가령 페이지 크기가 10KB인데, 프로세스 크기가 108KB라고 해볼까요? 이 경우에 마지막 페이지는 2KB만큼의 크기가 남습니다. 이러한 메모리 낭비를 내부 단편화라고 합니다. 내부 단편화는 하나의 페이지 크기보다 작은 크기로 발생합니다. 그렇기에 하나의 페이지 크기가 작다면 발생하는 내부 단편환의 크기는 작아질 것으로 기대할 수 있습니다. 하지만 하나의 페이지 크기를 너무 작게 설정하면 그만큼 페이지 테이블의 크기도 커지기 때문에 페이지 테이블이 차지하는 공간이 낭비됩니다. 그렇기에 내부 단편화를 적당히 방지하면서 너무 크지 않은 페이지 테이블이 만들어지도록 페이지의 크기를 조정하는 것이 중요합니다. 리눅스를 포함한 일부 운영체제에서는 위와 같이 기본적으로 설정된 페이지 크기보다 더 큰 크기의 페이지도 일부 허용하며 메모리에 유지하는 경우도 있습니다. 기본적으로 설정된 페이지보다 큰 페이지를 대형 페이지(huge page)라고 합니다. 

 

프로세스마다 각자의 프로세스 테이블을 가지고 있고 각 프로세스의 페이지 테이블들은 메모리에 적재되어 있습니다. 그리고 CPU 내의 페이지 테이블 베이스 레지스터(PTBR: Page Table Base Register)는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있습니다. 예를 들어 프로세스 A가 실행될 때 PTBR은 프로세스 A의 페이지 테이블을 가리키고, CPU는 프로세스 A의 페이지 테이블을 통해 프로세스 A의 페이지가 적재된 프레임을 알 수 있습니다. 마찬가지로 프로세스 B가 실행될 때는 PTBR이 프로세스 B의 페이지 테이블을 가리키고 CPU는 프로세스 B의 페이지 테이블을 통해 프로세스 B의 페이지가 적재된 프레임을 알 수 있습니다. 

 

이러한 각 프로세스들의 페이지 테이블 정보는 각 프로세스의 PCB에 기록됩니다. 그리고 프로세스의 문맥 교환이 일어날 때 다른 레지스터와 마찬가지로 함께 변경됩니다. 

 

그런데 이렇게 페이지 테이블을 메모리에 두면 문제가 있습니다. 메모리에 접근 시간이 두 배로 늘어난다는 점입니다. 메모리에 있는 페이지 테이블을 보기 위해 한 번, 그렇게 알게 된 프레임에 접근하기 위해 한 번, 이렇게 총 두 번의 메모리 접근이 필요하기 때문입니다. 이와 같은 문제를 해결하기 위해 CPU 곁에 (일반적으로 MMU내에) TLB(Translation Lookaside Buffer)라는 페이지 테이블의 캐시 메모리를 둡니다. 여러분이 사용하는 컴퓨터의 CPU 곁에는 TLB가 있습니다. TLB는 페이지 테이블의 캐시이기 때문에 페이지 테이블의 내용 일부를 저장합니다. 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와 저장합니다. 

 

CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 이를 TLB HIT라고 합니다. 이 경우에는 페이지가 적재된 프레임을 알기 위해 메모리에 접근할 필요가 없습니다. 그렇기에 메모리 접근을 한 번만 하면 됩니다. 하지만 만일 페이지 번호가 TLB에 없을 경우 어쩔 수 없이 페이지가 적재된 프레임을 알기 위해 메모리 내의 페이지 테이블에 접근할 수 밖에 없습니다. 이를 TLB 미스라고 합니다. 

 

하나의 페이지 혹은 프레임은 여러 주소를 포괄하고 있습니다. 그렇기에 특정 주소에 접근하려면 아래와 같은 두가지 정보가 필요합니다. 

- 어떤 페이지 혹은 프레임에 접근하고 싶은지

- 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나떨어져 있는지

 

그렇기에 페이징 시스템은 모든 논리 주소가 기본적으로 페이지 번호와 변위로 이루어져 있습니다. 페이지 번호는 말 그대로 접근하고자 하는 페이지 번호입니다. 페이지 테이블에서 해당 페이지 번호를 찾으면 페이지가 어떤 프레임에 할당되었는지를 알 수 있습니다. 변위는 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는지를 알기 위한 정보입니다. 즉, 논리 주소 <페이지 번호, 변위>는 페이지 테이블을 통해 물리주소 <프레임 번호, 변위>로 변환됩니다. 

 

페이지 테이블의 각 엔트리, 다시 말해 페이지 테이블의 각각의 행들을 페이지 테이블 엔트리(PTE: Page TAble Entry)라고 합니다. 지금까지는 페이지 테이블 엔트리에 담기는 정보로 페이지 번호, 프레임 번호만을 설명했지만, 실은 페이지 테이블 엔트리에는 이외에도 다른 중요한 정보들이 있습니다. 대표적인 것이 유효 비트, 보호 비트, 참조 비트, 수정 비트입니다. 

 

유효 비트는 해당 페이지에 접근 가능한지 여부를 알려줍니다. 페이지 테이블 엔트리에서 프레임 번호 다음으로 중요한 정보라고도 볼 수 있습니다. 페이징에서 스와핑을 사용할 수 있다고 했었습니다. 일반적으로 프로세스를 이루는 모든 페이지가 메모리에 있지 않습니다. 일부 페이지는 보조 기억장치(스왑 영역)에 있는 경우가 많습니다. 유효 비트는 현재 페이지가 메모리에 적재되어 있는지 아니면 보조기억장치에 있는지를 알려주는 비트입니다. 즉, 페이지가 메모리에 적재되어 있다면 유효 비트가 1, 페이지가 메모리에 적재되어 있지 않다면 유효비트가 0이됩니다. 만약 CPU가 유효 비트가 0인 메모리에 적재되어 있지 않은 페이지로 접근하려고 하면 어떻게 될까요? 이 경우 페이지 폴트(page fault)라는 예외가 발생합니다. 

 

보호 비트는 페이지 보호 기능을 위해 존재하는 비트입니다. 보호 비트를 통해 페이지가 읽고 쓰기가 모두 가능한 페이지인지, 혹은 읽기만 가능한 페이지인지를 나타낼 수 있습니다. 가령 비트가 0일 경우 이 페이지는 읽기만 가능한 페이지임을 나타내고, 1일 경우 읽고 쓰기가 모두 가능한 페이지임을 나타내는 것입니다. 프로세스의 코드 영역은 읽기 전용입니다. 이러한 읽기 전용 페이지에 쓰기를 시도하면 운영체제가 이를 보호합니다. 

 

참조 비트(reference bit)는 CPU가 이 페이지에 접근한 적이 있는지 여부를 나타냅니다. 적재 이후 CPU가 읽거나 쓴 페이지는 참조 비트가 1로 세팅되고, 적재 이후 한 번도 읽거나 쓴 적이 없는 페이지는 0으로 유지됩니다. 수정 비트는 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려줍니다. 더티 비트라고도 부릅니다. 이 비트가 1이면 변경된 적이 있는 페이지, 0이면 변경된 적이 없는 페이지(한 번도 접근한 적 없거나 읽기만 했던 페이지)임을 나타냅니다. 

 

수정 비트(modified bit)는 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려줍니다. 더티비트(dirty bit)라고도 부릅니다. 이 비트가 1이면 변경된 적이 있는 페이지, 0이변 변경된적이 없는 페이지(한 번도 접근한 적이 없거나 읽기만 했던 페이지)임을 나타냅니다. 수정 비트는 왜 존재하는 것일까요? 수정 비트는 페이지가 메모리에서 사라질 떄 보조 기억장치에 쓰기 작업을 해야하는지, 할 필요가 없는지를 판단하기 위해 존재합니다. CPU는 메모리를 읽기도 하지만 메모리에 값을 쓰기도 합니다. CPU가 한 번도 접근하지 않았거나 읽기만 한 페이지의 경우 보조 기억장치에 저장된 해당 페이지의 내용과 메모리에 저장된 페이지 내용은 아래 그림과 같이 서로 같은 값을 가지고 있습니다. 이렇게 한 번도 수정된 적이 없는 페이지가 스왑 아웃될 경우 아무런 추가 작업 없이 새로 적재된 페이지로 덮어쓰기만 하면 됩니다. 어짜피 똑같은 페이지가 보조기억장치에 저장되어 있으니까요. 하지만 CPU가 쓰기 작업을 수행한 페이지의 경우 보조 기억장치에 저장된 페이지의 내용과 메모리에 저장된 페이지의 내용은 서로 다른 값을 가지게 됩니다. 이렇게 수정된 적이 있는 페이지가 스왑 아웃될 경우 변경된 값을 보조 기억장치에 기록하는 작업이 추가되어야 합니다. 이 작업이 필요한 페이지인지 아닌지를 판단하기 위해 페이지 테이블 엔트리에 수정 비트를 두는 것입니다. 

 

외부 단편화 문제를 해결한다는 점 이외에도 페이징이 제공하는 이점은 다양합니다. 대표적인 것이 프로세스 간에 페이지를 공유할 수 있다는 점입니다. 프로세스 간 페이지를 공유하는 사례로는 공유 라이브러리 등 다양하지만, 대표적인 예시로 쓰기 시 복사(copy on write)가 있습니다. 

 

유닉스나 리눅스 운영체제에서 fork 시스템 호출을 하면 부모 프로세스의 복사본이 자식 프로세스로서 만들어집니다. 프로세스 간에는 기본적으로 자원을 공유하지 않는다는 프로세스의 전통적인 개념에 입각하면 새롭게 생성된 자식 프로세스의 코드 및 데이터 영역은 부모 프로세스가 적재된 메모리 공간과는 다른 메모리 공간에 생성됩니다. 한 마디로 부모 프로세스의 메모리 영역이다른 영역에 자식 프로세스로서 복제되고, 각 프로세스의 페이지 테이블은 자신의 고유한 페이지가 할당된 프레임을 가리킵니다.하지만 복사 작업은 프로세스 프로세스 생성 시간을 늦출뿐만 아니라 불필요한 메모리 낭비를 야기합니다. 

 

반면 쓰기 시 복사에서는 부모 프로세스와 동일한 자식 프로세스가 생성되면 자식 프로세스로 하여금 부모 프로세스와 동일한 프레임을 가리킵니다. 이로써 굳이 부모 프로세스와 자식 프로세스가 메모리에 어떠한 데이터도 쓰지 않고 그저 읽기 작업만 이어 나간다면 이 상태가 지속됩니다. 부모 프로세스 혹은 자식프로세스 둘 중 하나가 페이지에 쓰기 작업을 하면 그 순간 해당 페이지가 별도의 공간으로 복제됩니다. 각 프로세스는 자신의 고유한 페이지가 할당된 프레임을 가리킵니다. 이것이 쓰기 시 복사입니다. 쓰기 시 복사를 통해 프로세스 생성 시간을 줄이는 것은 물론 메모리 공간도 절약가능합니다. 

 

페이지 테이블의 크기는 생각보다 작지 않습니다. 프로세스의 크기가 커지면 자연히 프로세스 테이블의 크기도 커지기 때문에 프로세스를 이루는 모든 페이지 테이블 엔트리를 메모리에 두는 것은 큰 메모리 낭비입니다. 이를 위해 모든 페이지 테이블 엔트리를 항상 메모리에 유지하지 않을 수 있는 방법이 등장했는데, 이것이 계층적 페이징(hierarchical paging)입니다. 계층적 페이징은 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식입니다. 여러 단계의 페이지를 둔다는 점에서 다단계 페이지 페이블(multilevel page table)기법이라고도 부릅니다. 프로세스의 페이지 테이블을 여러 개의 페이지로 자르고, 바깥쪽에 페이지 테이블을 하나 더 두어 잘린 페이지 테이블의 페이지들을 가리키게하는 방식입니다. 계층적 페이징 기법을 사용하지 않으면 이 프로세스 테이블은 전체가 메모리에 있어야합니다. 

 

이 페이지 테이블을 여러개의 페이지로 쪼개고, 이 페이지들을 가리키는 페이지 테이블을 두는 방식이 계층적 페이징입니다. 페이지 테이블을 이렇게 계층적으로 구성하면 모든 페이지 테이블을 항상 메모리에 유지할 필요가 없습니다. 페이지 테이블들 중 몇개는 보조 기억장치에 있어도 무방하며, 추후 해당 페이지 테이블을 참조해야 할 때가 있으면 그 떄 메모리에 적재하면 그만입니다. 

 

프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법을 요구 페이징(demand paging)이라고 합니다. 

 

요구 페이징의 기본적인 양상은 다음과 같습니다. 

 

1. CPU가 특정 페이지에 접근하는 명령어를 실행한다. 

2. 해당 페이지가 현재 메모리에 있을 경우 (유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다. 

3. 해당 페이지가 현재 메모리에 없을 경우 (유효 비트가 0일 경우) 페이지 폴트가 발생한다. 

4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.

 

아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행부터 할 수도 있습니다. 이경우 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트가 계속 발생하게 되고, 실행에 필요한 페이지가 어느 정도 적재된 이후부터는 페이지 폴트 빈도가 떨어집니다.

 

이를 순수 요구 페이징(pure demand paging) 기법이라고 합니다. 다시 요구 페이징 이야기로 돌아와서, 위와 같은 요구 페이징 시스템이 안정적으로 작동하려면 필연적으로 다음 두 가지를 해결해야 합니다. 하나는 페이지 교체이고, 다른 하나는 프레임 할당입니다. 요구 페이징 기법으로 페이지들을 적재하다보면 언젠가 메모리가 가득차게 됩니다. 이때는 당장 실행에 필요한 페이지를 적재하기 위해 메모리에 적대된 페이지를 보조 기억장치로 내보내야 합니다. 메모리에 적재된 많고 많은 페이지 중 어떤 페이지를 내보내는 것이 최선일까요? 이를 결정하는 방법이 페이지 교체 알고리즘입니다. 좋은 페이지 교체알고리즘은 페이지 폴트를 가장 적게 일으키는 알고리즘입니다. 페이지 폴트가 일어나면 보조 기억장치로부터 필요한 페이지를 가져와야 하기 때문에 메모리에 적재된 페이지를 가져오는 것보다 느려지기 때문입니다. 가령 한 알고리즘을 통해 고른 페이지를 스왑아웃시켰을 때 페이지 폴트가 자주 발생하면 이는 좋은 알고리즘이 아닙니다. 한 페이지 교체 알고리즘을 선택했더니 페이지 폴트가 자주 발생했다는 말은 보조 기억장치로 내쫓을 페이지를 잘못 골랐다는 뜻으로 내보내면 안되는 페이지를 보조 기억장치로 내보냈다는 의미와 같기 때문입니다. 이는 당연히 컴퓨터의 성능을 저해하는 나쁜 알고리즘입니다. 반면 어떤 알고리즘을 통해 고른 페이지를 스왑 아웃시켜도 페이지 폴트가 자주 발생하지 않는다면 이는 컴퓨터의 성능 저하를 방지하는 좋은 알고리즘으로 평가할 수 있습니다. 그렇기에 페이지 교체 알고리즘을 제대로 이해하려면 페이지 폴트 횟수를 알 수 있어야 합니다. 그리고 페이지 폴트 횟수는 페이지 참조열 (page reference string)을 통해 알 수 있습니다. 페이지 참조열의 개념은 간단합니다. CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미합니다. 

 

중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않습니다. CPU가 특정 페이지에 열 번 연속으로 접근한다고 해서 한 번 접근하는 것보다 페이지 폴트가 많이 발생하지 않습니다. 페이지 교체 알고리즘을 평가할 때 관심있게 고려해야할 것은 오직 페이지 폴트의 발생 횟수이기 때문에 어차피 페이지 폴트가 일어나지 않을 연속된 페이지에 대한 참조는 고려하지 않습니다. 

 

FIFO 페이지 교체 알고리즘(First-In First-Out Page Replacement Algorithm)은 가장 단순한 방법입니다. 이름 그대로 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식으로 쉽게 말해 "오래 머물렀다면 나가라"는 알고리즘입니다. 최적 페이지 교체 알고리즘은 CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘입니다. (optional page replacement algorithm) 최적 페이지 교체 알고리즘은 구현이 어렵습니다. 앞으로 오랫동안 사용되지 않ㅇ르 페이지를 예측하기란 어렵습니다. 프로세스가 앞으로 메모리 어느 부분을 어떻게 참조할지 미리 알아야 하는데, 이는 현실적으로 불가능에 가깝기 때문입니다. 따라서 최적 페이지 교체 알고리즘은 그 자체를 운영체제에서 사용하기보다는, 주로 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용됩니다. 즉, 최적 페이지 교체 알고리즘을 실행했을 때 발생하는 페이지 폴트 횟수를 페이지 폴트의 하한선으로 간주하고, 최적 페이지 교체 알고리즘에 비해 얼만큼 페이지 폴트 횟수가 발생하느냐를 통해 페이지 교체 알고리즘을 평가하기 위해 사용합니다. 

 

가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘은 LRU 페이지 교체 알고리즘입니다. (Least Recently Used Page Replacement Algorithm) LRU 페이지 교체 알고리즘은 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이라는 아이디어를 토대로 만들어진 알고리즘입니다. 

 

프로세스가 사용할 수 있는 프레임 수가 적어도 페이지 폴트는 자주 발생합니다. 반대로 프로세스가 사용할 수 있는 프레임 수가 많으면 일반적으로 페이지 폴트 빈도는 감소합니다. 극단저긍로 프레임이 무한히 많은 컴퓨터와 프레임이 한 개 있는 컴퓨터를 비교해보면 전자는 페이지를 수용할 공간이 넉넉하여 모든 프로세스의 페이지가 메미뢰에 적재될 수 있기 때문에 페이지 폴트 발생 빈도가 적지만, 후자는 새로운 페이지를 참조할 때마다 페이지 폴트가 발생합니다. 

 

프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저하되는 문제를 스레싱(thrashing)이라고  합니다. 

동시에 실행되는 프로세스의 수를 늘린다고해서 CPU 이용률이 그에 비례해서 증가하는 것은 아닙니다. 동시에 실행되는 프로세스 수가 어느 정도 증가하면 CPU 이용률이 높아지지만, 필요 이상으로 늘리면 각 프로세스들이 사용할 수 있는 프레임 수가 적어지기 때문에 페이지 폴트가 지나치게 빈번히 발생하고, 이에 따라 CPU 이용률이 떨어져 전체적인 성능이 저해되는 것입니다. 아무리 CPU의 성능이 뛰어나도 동시에 실행되는 프로세스를 수용할 물리 메모리가 너무 작다면 전체 컴퓨터의 성능이 않좋아지는 이유는 이러한 이유 때문입니다. 

 

스레싱이 발생하는 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문입니다. 가령 프로세스 A를 무리없이 실행하기 위해서는 최소 열 개의 프레임이 필요한데도 불구하고 프로세스 A가 다섯 개의 프레임만 이용할 수 있다면 이 프로세스는 페이지 폴트가 자주 발생합니다. 스레싱 발생 위험이 높아집니다. 

 

프로세스를 실행하는 과정에서 배분할 프레임을 결정하는 방식에는 크게 작업 집합 모델(working set model)을 사용하는 방식과 페이지 폴트 빈도(PFF; Page-Fault Frequency)를 사용하는 방식이 있습니다. 이 두개의 방식은 프로세스의 실행을 보고 할당할 프레임 수를 결정한다는 점에서 동적 할당 방식이라고도 합니다. 스렐싱이 발생하는 이유는 빈번한 페이지 교체 때문입니다. 그렇기에 작업 집합 모델 기반 프레임 할당 방식은 프로세스가 일정 기간 동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체를 방지합니다. CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당하면 페이지 교체는 빈번하게 발생하지 않습니다. 만약 CPU가 어떤 프로세스를 실행하는 동안 3초에 일곱개의 페이지를 집중적으로 참조했다면 운영체제는 그 프로세스를 위해 그 순간만큼은 최소 일곱 개의 프레임을 할당하면도비니다. 또 만약 CPU가 어떤 프로세스를 실행하는 동안 3초에 20개의 페이지를 집중적으로 참조했다면 운영체제는 그 프로세스를 위해 그 순간만큼은 최소 20개의 프레임을 할당하면 됩니다. 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합을 작업 집합(working set)이라고 합니다. CPU가 과거에 주로 참조한 페이지를 작업 집합에 포함한다면 운영체제는 작업 집합의 크기만큼만 프레임을 할당해주면 됩니다. 

 

다음으로 페이지 폴트를 기반으로 한 프레임 할당입니다. 이는 아래의 두 개의 가정에서 생겨난 아이디어입니다. 

1. 페이지 폴트율이 높으면 그 프로세스는 너무 적은 프레임을 갖는다. 

2. 페이지 폴트율이 너무 낮으면 그 프로세스는 너무 많은 프레임을 갖고 있다. 

 

파일 시스템

파일이란 하드 디스크나 SSD와 같은 보조 기억장치에 저장된 관련 정보의 집합을 의미합니다. 달리 표현하면 파일은 의미 있고 관련 있는 정보를 모은 논리적 단위를 의미합니다. 모든 파일에는 이름과 파일을 실행하기 위한 정보, 그리고 파일 관련 부가정보가 있습니다. 이 부가 정보를 속성(attribute) 또는 메타 데이터(metadata)라고 부릅니다. 

 

파일을 다루는 모든 작업은 운영체제에 의해 이뤄집니다. 어떤 응용 프로그램도 임의로 파일을 조작할 수 없으며 파일을 다루려면 운영체제에게 부탁해야합니다. 이를 위해 운영체제는 다음과 같은 파일 연산을 위한 시스템 호출을 제공합니다. 

 

1. 파일 생성 2. 파일 삭제 3. 파일 열기 4. 파일 닫기 5. 파일 읽기 6. 파일 쓰기

 

파일들을 일목요연하게 관리하기 위해 디렉터리를 사용할 수 있습니다. 

 

파티셔닝(partitioning)은 저장 장치의 논리적인 영역을 구획하는 작업을 의미합니다. 파티셔닝을 통해 나눠진 영역 하나하나를 파티션(partition)이라고 합니다. 

 

포매팅이란 파일 시스템을 설정하여 어떤 방식으로 파일을 저장하고 관리할 것인지를 결정하고 새로운 데이터를 쓸 준비를 하는 작업을 의미합니다. 즉, 어떤 종류의 파일 시스템을 사용할지는 바로 이때 결정납니다. 운영체제는 파일과 디렉터리를 블록 단위로 읽고 씁니다. 즉 하나의 파일이 보조기억장치에 저장도딜 때는 하나 이상의 블록에 걸쳐 저장됩니다. 하드 디스크의 가장 작은 단위는 섹터이지만 운영체제는 하나 이상의 섹터를 블록이라는 단위로 묶은 뒤 블록 단위로 파일과 디렉터리를 관리합니다. 파일 시스템이 모든 섹터를 관리하기에는 개수가 너무 많고 크기도 작기 때문입니다. 

 

연속할당은 보조 기억장치 내 연속적인 블록에 파일을 할당하는 방식입니다. 연속적으로 할당된 파일에 접근하기 위해서는 파일의 첫번째 블록 주소와 블록 단위의 길이만 알면 됩니다. 그렇기에 연속 할당을 사용하는 파일 시스템에서는 다음과 같이 디렉터리 엔트리에 파일 이름과 더불어 첫 번째 블록 주소와 블록 단위의 길이를 명시합니다. 연속할당은 파일을 그저 연속적으로 저장하는 방식이기에 구현이 단순하다는 장점이 있지만 외부 단편화를 야기한다는 치명적인 문제가 있습니다. 연속 할당의 문제를 해결할 수 있는 방법이 연결할당(linked allocation)입니다. 연결 할당은 각 블록 일부에 다음 블록의 주소를 저장하여 각 블록이 다음 블록을 가리키는 형태로 할당하는 방법입니다. 즉, 파일을 이루는 데이터를 연결리스트로 관리합니다. 연결할당은 불연속 할당의 일종이기에 파일이 여러 블록에 흩어져 저장되어도 무방합니다. 연결할당은 외부 단편화문제를 해결하지만 또한 단점이 있습니다. 첫번째 단점은 파일의 중간 부분부터 접근하고 싶어도 반드시 첫번째 블록부터 접근하여 하나씩 읽어야 한다는 것입니다. 다시 말해 파일 내 임의의 위치에 접근하는 속도, 즉 임의 접근(random access)속도가 매우 느립니다. 두번째 단점은 하나의 블록 안에 파일 데이터와 다음 블록 주소가 모두 포함되어 있다 보니, 하드웨어 고장이나 오류로 인해 파일을 이루는 블록에 하나라도 문제가 생긴다면 그 블록 이후의 블록에 접근할 수 없다는 것입니다. 하드 디스크는 굉장히 정교하고 고장에 예민한 장치입니다. 하드 디스크 헤드는 플래터 위에 대단히 미세한 간격으로 떨어져 있는 만큼 충격을 받으면 자칫 헤드가 플래터에 충돌하여 데이터 손상을 일으킬 수 있습니다 .

 

연결 할당의 단점을 보완한 파일 시스템이 FAT 파일시스템입니다. 각 블록에 포함된 다음 블록의 주소들을 한데 모아 테이블 형태로 관리하면 앞서 언급한 단점들을 상당 부분 해소할 수 있습니다. 이러한 테이블을 파일 할당 테이블(File Allocation Table)이라고 부릅니다. 

 

이렇게 FAT를 이용하는 파일 시스템이 바로 FAT 파일 시스템입니다. 옛날 마이크로 소프트의 운영체제인 MS-DOS에서 사용되었고 최근까지 USB 메모리, SD 카드와 같은 저용량 저장 장치용 파일 시스템으로 많이 이용되고 있습니다. FAT 파일 시스템은 버전에 따라 FAT12, FAT16, FAT32가 있으며 FAT 뒤에 오는 숫자는 블록을 표현하는 비트수를 의미합니다. 

 

색인 할당은 색인 블록을 기반으로 파일의 데이터 블록들을 찾는 방식입니다. 유닉스 파일 시스템에서는 이 색인 블록을 i-node(index-node)라고 부릅니다.