혼자 공부하는 컴퓨터구조 + 운영체제 - 운영체제

08 운영체제 시작하기

---

운영체제란

실행할 프로그램에 필요한 자원을 할당하고, 프로그램이 올바르게 실행되도록 돕는 특별한 프로그램이 바로 운영체제(operating system)이다. 매우 특별한 프로그램이기 떄문에 항상 컴퓨터가 부팅될 때 메모리 내 커널 영역(kernel space)이라는 공간에 따로 적재되어 실행된다. 커널 영역을 제외한 나머지 영역, 사용자가 이용하는 응용 프로그램이 적재되는 영역을 사용자 영역(user space)라고 한다. 즉, 운영 체제는 커널 영역에 적재되어 사용자 영역에 적재된 프로그램들에 자원을 할당하고 이들이 올바르게 실행되도록 돕는다.

운영체제를 알아야 하는 이유

운영체제는 현재 하드웨어의 상태는 어떠한지, 코드가 어떻게 실행되는지, 하드웨어 상에 어떤 문제가 있었는지 등을 상세히 알려줄 수 있고, 이를 통해 문제 해결의 실마리를 찾을 수 있다.

운영체제의 심장, 커널

자원에 접근하고 조작하는 기능, 프로그램이 올바르고 안전하게 실행되게 하는 기능이 운영체제의 핵심 서비스이고 이를 커널(kernel)이 담당한다. 운영체제가 제공하는 서비스 중 커널에 포함되지 않는 서비스도 있는데, 대표적으로 사용자 인터페이스(UI: User Interface)가 있다. 사용자 인터페이스에는 그래픽 유저 인터페이스(GUI: Graphical User Interface)와 커맨드 라인 인터페이스(CLI: Command Line Interface)가 있다. 전자는 윈도우나 스마트폰 화면처럼 그래픽을 기반으로 컴퓨터와 상호작용하는 것을 뜻하고, 후자는 유닉스나 리눅스처럼 명령어 기반으로 상호작용한다.

이중 모드와 시스템 호출

이중 모드(dual mode)란 CPU가 명령어를 실행하는 모드를 크게 사용자 모드와 커널 모드로 구분하는 방식이다. CPU는 명령어를 사용자 모드로써 실행할 수 있고, 커널 모드로써 실행할 수 있다. 사용자 모드(user mode)는 운영체제 서비스를 제공받을 수 없는 실행 모드이므로 커널 영역의 코드를 실행할 수 없다. 일반적인 응용 프로그램은 기본적으로 사용자 모드로 실행되어 자원에 접근할 수 없다. 반면 커널 모드(kernel mode)는 운영체제 서비스를 제공받을 수 있는 실행모드로 커널 영역의 코드를 실행할 수 있어 자원에 접근할 수 있다.

사용자 모드로 실행되는 프로그램이 자원에 접근하는 운영체제 서비스를 제공 받으려면 운영체제에 요청을 보내 커널 모드로 전환되어야 한다. 이때 운영체제 서비스를 제공받기 위한 요청을 시스템 호출(system call)이라고 한다. 시스템 호출은 일종의 인터럽트이다. 예를 들면 다음과 같다. 한 응용 프로그램이 하드 디스크에 데이터를 저장하려 한다. 이를 위해 응용 프로그램은 하드 디스크에 접근해야하는데 사용자 모드로 실행되는 동안에는 자원(하드 디스크)에 접근할 수 없으므로 커널 모드로 전환해야 한다. 이를 위해 응용 프로그램은 시스템 호출을 발생시켜 커널 모드로 전환하고, 운영체제 내의 '하드 디스크에 데이터를 저장하는 코드'를 실행함으로써 하드 디스크에 접근한다. 그리고 작업이 끝나면 다시 사용자 모드로 복귀하여 실행을 계속해 나간다. 일반적으로 응용 프로그램은 실행 과정에서 운영체제 서비스들을 매우 빈번하게 이용한다. 그 과정에서 빈번하게 시스템 호출을 발생시키고 사용자 모드와 커널 모드를 오가며 실행된다.

운영체제의 핵심 서비스

• 프로세스 관리 : 실행 중인 프로그램을 프로세스(process)라고 한다. 일반적으로 하나의 CPU는 한 번에 하나의 프로세스만 실행할 수 있기에 CPU는 이 프로세스들을 조금씩 번갈아 실행한다. 이때 각 프로세스는 상태도, 사용하고자 하는 자원도 다양하므로 운영체제는 다양한 프로세스를 일목요연하게 관리하고 실행할 수 있어야 한다.
• 자원 접근 및 할당 : 모든 프로세스는 실행을 위해 자원을 필요로 하고, 운영체제는 프로세스들에 자원을 할당해준다.
• 파일 시스템 관리

 

10 프로세스와 스레드

---

프로세스 직접 확인하기

포그라운드 프로세스(foreground process)는 사용자가 볼 수 있는 공간에서 실행되는 프로세스이고, 백그라운드 프로세스(background process)는 보이지 않는 공간에서 실행된다. 백그라운드 프로세스 중에는 사용자와 직접 상호작용할 수 있는 백그라운드 프로세스도 있지만, 사용자와 상호작용하지 않고 그저 묵묵히 정해진 일만 수행하는 백그라운드 프로세스도 있다. 이러한 프로세스를 유닉스 체계의 운영체제에서는 데몬(daemon)이라 부르고, 윈도우에서는 서비스(service)라 부른다.

프로세스 제어 블록

모든 프로세스는 실행을 위해 CPU를 필요로 하지만, CPU 자원은 한정되어 있다. 즉 모든 프로세스가 CPU를 동시에 사용할 수 없어 프로세스들은 차례대로 돌아가며 한정된 시간만큼만 CPU를 이용한다. 자신의 차례가 되면 정해진 시간만큼 CPU를 이용하고, 시간이 끝났음을 알리는 인터럽트(타이머 인터럽트)가 발생하면 자신의 차례를 양보하고 다음 차례가 올 때까지 기다린다.

운영체제는 빠르게 번갈아 수행되는 프로세스의 실행 순서를 관리하고, 프로세스에 CPU를 비롯한 자원을 배분한다. 이를 위해 운영체제는 프로세스 제어 블록(PCB: Process Control Block)을 이용한다. PCB는 프로세스와 관련된 정보를 저장하는 자료 구조이고, 프로세스를 식별하기 위해 꼭 필요한 정보들이 저장된다. 커널영역에 생성되는 이 PCB에 담기는 정보는 아래와 같다.

• 프로세스 ID(PID: Process ID)는 특정 프로세스를 식별하기 위해 부여하는 고유한 번호이다. 같은 일을 수행하는 프로그램이라 할지라도 두 번 실행하면 PID가 다른 두 개의 프로세스가 생성된다.
• 레지스터 값 : 프로세스는 자신의 실행 차례가 돌아오면 이전까지 사용했던 레지스터의 중간값들을 모두 복원한다. 그래야만 이전까지 진행했던 작업들을 그대로 이어 실행할 수 있다. 그래서 해당 프로세스가 실행하며 사용했던 프로그램 카운터를 비롯한 레지스터 값들이 담긴다.
• 프로세스 상태 : 현재 프로세스가 어떤 상태인지도 기록된다. 현재 프로세스가 입출력장치를 사용하기 위해 기다리고 있는 상태인지, CPU를 사용하기 위해 기다리고 있는 상태인지, 아니면 CPU를 이용하고 있는 상태인지 등의 프로세스 상태 정보가 저장된다.
• CPU 스케줄링 정보 : 프로세스가 언제, 어떤 순서로 CPU를 할당받을지에 대한 정보도 저장된다.
• 메모리 관리 정보 : 프로세스마다 메모리에 저장된 위치가 다르다. 그래서 프로세스가 어느 주소에 저장되어 있는지에 대한 정보가 있어야 하고, 베이스 레지스터, 한계 레지스터 값과 같은 정보가 담긴다. 또한 프로세스의 주소를 알기 위한 또 다른 중요 정보 중 하나인 페이지 테이블 정보도 담긴다.
• 사용한 파일과 입출력장치 목록 : 프로세스가 실행 과정에서 특정 입출력장치나 파일을 사용하면 PCB에 해당 내용이 명시된다. 즉, 어떤 입출력장치가 이 프로세스에 할당되었는지, 어떤 파일들을 열었는지에 대한 정보들이 기록된다.

문맥 교환

프로세스 A가 운영체제로부터 CPU를 할당받아 실행되다가 시간이 다 되어 프로세스 B에 CPU 사용을 양보한다고 가정해보자. 이런 상황에서 바로 직전까지 실행되던 프로세스 A는 프로그램 카운터를 비롯한 각종 레지스터 값, 메모리 정보, 실행을 위해 열었던 파일이나 사용한 입출력장치 등 지금까지의 중간 정보를 백업해야 한다. 그래야만 다음 차례가 왔을 때 이전까지 실행했던 내용에 이어 다시 실행을 재개할 수 있으니까 말이다. 이러한 중간 정보, 즉 하나의 프로세스 수행을 재개하기 위해 기억해야 할 정보를 문맥(context)이라고 한다. 하나의 프로세스 문맥은 해당 프로세스의 PCB에 표현되어 있다. PCB에 기록되는 정보들을 문맥이라고 봐도 무방하다. 실행 문맥을 잘 기억해 두면 언제든 해당 프로세스의 실행을 재개할 수 있기 때문에 프로세스가 CPU를 사용할 수 있는 시간이 다 되거나 예기치 못한 상황이 발생하여 인터럽트가 발생하면 운영체제는 해당 프로세스의 PCB에 문맥을 백업한다. 그리고 뒤이어 실행할 프로세스 B의 문맥을 복구한다. 이처럼 기존 프로세스의 문맥을 PCB에 백업하고, 새로운 프로세스를 실행하기 위해 문맥을 PCB로부터 복구하여 새로운 프로세스를 실행하는 것을 문맥 교환(context switching)이라고 한다.

문맥 교환은 여러 프로세스가 끊임없이 빠르게 번갈아 가며 실행되는 원리이다. 문맥 교환이 자주 일어나면 프로세스는 그만큼 빨리 번갈아 가며 수행되기 때문에 우리 눈에는 프로세스들이 동시에 실행되는 것처럼 보인다.

프로세스의 메모리 영역

하나의 프로세스는 사용자 영역에 크게 코드 영역, 데이터 영역, 힙 영역, 스택 영역으로 나뉘어 저장된다.

• 코드 영역(code segment)은 텍스트 영역(text segment)이라고도 부른다. 이곳에는 말 그대로 실행할 수 있는 코드, 즉 기계어로 이루어진 명령어가 저장된다. 코드 영역에는 데이터가 아닌 CPU가 실행할 명령어가 담겨 있기 때문에 쓰기가 금지되어 있다. 다시 말해 코드 영역은 읽기 전용(read-only) 공간이다.
• 데이터 영역(data segment)은 잠깐 썼다가 없앨 데이터가 아닌 프로그램이 실행되는 동안 유지할 데이터가 저장되는 공간이다. 이런 데이터로는 전역 변수(global variable)가 대표적이다. 코드 영역과 데이터 영역은 그 크기가 변하지 않는다. 프로그램을 구성하는 명령어들이 갑자기 바뀔 일이 없으니 코드 영역의 크기가 변할 리 없고, 데이터 영역에 저장될 내용은 프로그램이 실행되는 동안에만 유지할 데이터이기 때문이다. 그래서 코드 영역과 데이터 영역은 '크기가 고정된 영역'이라는 점에서 정적 할당 영역이라고도 부른다. 반면 힙 영역과 스택 영역은 프로세스 실행 과정에서 그 크기가 변할 수 있는 영역이라 동적 할당 영역이라 부른다.
• 힙 영역(heap segment)은 프로그램을 만드는 사용자, 즉 프로그래머가 직접 할당할 수 있는 저장공간이다. 프로그래밍 과정에서 힙 영역에 메모리 공간을 할당했다면 언젠가는 해당 공간을 반환해야 한다. 메모리 공간을 반환한다는 의미는 '더 이상 해당 메모리 공간을 사용하지 않겠다'라고 운영체제에 말해주는 것과 같다. 메모리 공간을 반환하지 않는다면 할당한 공간은 메모리 내에 계속 남아 메모리 낭비를 초래한다. 이런 문제를 메모리 누수(memory leak)이라고 한다.
• 스택 영역(stack segment)은 데이터를 일시적으로 저장하는 공간이다. 데이터 영역에 담기는 값과는 달리 잠깐 쓰다가 말 값들이 저장되는 공간이다. 이런 데이터로는 함수의 실행이 끝나면 사라지는 매개 변수, 지역 변수가 대표적이다. 일시적으로 저장할 데이터는 스택 영역에 PUSH되고, 더 이상 필요하지 않은 데이터는 POP됨으로써 스택 영역에서 사라진다. 힙 영역과 스택 영역은 실시간으로 그 크기가 변할 수 있기 때문에 동적 할당 영역이라고 부른다. 그래서 일반적으로 힙 영역은 메모리의 낮은 주소에서 높은 주소로 할당하고, 스택 영역은 높은 주소에서 낮은 주소로 할당된다. 그래야만 힙 영역과 스택 영역에 데이터가 쌓여도 새롭게 할당되는 주소가 겹칠일이 없기 때문이다.

프로세스 상태

여러 프로세스들이 빠르게 번갈아 가며 실행 될 때 하나의 프로세스는 여러 상태를 거치며 실행된다. 그리고 운영체제는 프로세스의 상태를 PCB를 통해 인식하고 관리한다. 프로세스의 상태를 표현하는 방식은 운영체제마다 조금씩 차이가 있지만, 프로세스가 가질 수 있는 대표적인 상태는 아래와 같다.

• 생성 상태 : 프로세스를 생성 중인 상태를 생성 상태(new)라고 한다. 이제 막 메모리에 적재되어 PCB를 할당 받은 상태를 말한다. 생성 상태를 거쳐 실행할 준비가 완료된 프로세스는 곧바로 실행되지 않고 준비 상태가 되어 CPU의 할당을 기다린다.
• 준비 상태(ready) : 당장이라도 CPU를 할당받아 실행할 수 있지만, 아직 자신의 차례가 아니기에 기다리고 있는 상태이다. 준비 상태 프로세스는 차례가 되면 CPU를 할당받아 실행 상태가 된다.
• 실행 상태(running) : CPU를 할당받아 실행 중인 상태를 의미한다. 실행 상태인 프로세스는 할당된 일정 시간 동안만 CPU를 사용할 수 있다. 이때 프로세스가 할당된 시간을 모두 사용한다면(타이머 인터럽트가 발생하면) 다시 준비 상태가 되고, 실행 도중 입출력장치를 사용하여 입출력 장치의 작업이 끝날 때까지 기다려야 한다면 대기 상태가 된다.
• 대기 상태 : 프로세스는 실행 도중 입출력장치를 사용하는 경우가 있다. 입출력 작업은 CPU에 비해 처리 속도가 느리기에, 입출력 작업을 요청한 프로세스는 입출력장치가 입출력을 끝낼 떄까지(입출력 완료 인터럽트를 받을 때까지) 기다려야 한다. 이렇게 입출력장치의 작업을 기다리는 상태를 대기 상태(block)라고 한다. 입출력 작업이 완료되면 해당 프로세스는 다시 준비 상태로 CPU 할당을 기다린다.
• 종료 상태(terminated) : 프로세스가 종료된 상태이다. 프로세스가 종료되면 운영체제는 PCB와 프로세스가 사용한 메모리를 정리한다.

프로세스 계층 구조

프로세스는 실행 도중 시스템 호출을 통해 다른 프로세스를 생성할 수 있다. 이때 새 프로세스를 생성한 프로세스를 부모 프로세스(parent process), 부모 프로세스에 의해 생성된 프로세스를 자식 프로세스(child process)라고 한다. 부모 프로세스와 자식 프로세스는 엄연히 다른 프로세스이기에 각기 다른 PID를 가진다. 일부 운영체제에서는 자식 프로세스의 PCB에 부모 프로세스의 PID인 PPID(Parent PID)가 기록되기도 한다. 부모 프로세스로부터 생성된 자식 프로세스는 실행 과정에서 또 다른 자식 프로세스를 생성할 수 있고, 그 자식 프로세스는 실행 과정에서 또 다른 자식 프로세스를 생성할 수 있다. 많은 운영체제는 이처럼 프로세스가 프로세스를 낳는 계층적은 구조로써 프로세스들을 관리한다.

예를 들어 사용자가 컴퓨터를 켜고 로그인 창을 통해 성공적으로 로그인해서 bash 셸(사용자 인터페이스)로 Vim이라는 문서 편집기 프로그램을 실행했다고 가정해 봅시다. 이 경우 사용자가 컴퓨터를 켠 순간에 생성된 최초 프로세스는 로그인을 담당하는 프로세스를 자식 프로세스로 생성한 것이고, 로그인 프로세스는 사용자 인터페이스(bash 셸) 프로세스를 자식 프로세스로 생성한 것이고, 사용자 인터페이스 프로세스는 Vim 프로세스를 생성한 셈이다.

프로세스 생성 기법

부모 프로세스를 통해 생성된 자식 프로세스들은 복제와 옷 갈아입기를 통해 실행된다. 조금 더 정확하게, 부모 프로세스는 fork를 통해 자신의 복사본을 자식 프로세스로 생성해내고, 만들어진 복사본(자식 프로세스)은 exec를 통해 자신의 메모리 공간을 다른 프로그램으로 교체한다. fork와 exec는 시스템 호출이다. 부모 프로세스는 fork 시스템 호출을 통해 자신의 복사본을 자식 프로세스로 생성한다. 즉, fork는 자기 자신 프로세스의 복사본을 만드는 시스템 호출이다. 자식 프로세스는 부모 프로세스의 복사본이기 때문에 부모 프로세스의 자원들, 이를테면 메모리 내의 내용, 열린 파일의 목록 등이 자식 프로세스에 상속된다(복사된 자식 프로세스라 할지라도 PID값이나 저장된 메모리 위치는 다르다). fork를 통해 복사본이 만들어진 뒤에 자식 프로세스는 exec 시스템 호출을 통해 새로운 프로그램으로 전환된다. exec는 자신의 메모리 공간을 새로운 프로그램으로 덮어쓰는 시스템 호출이다. 다시 말해 새로운 프로그램 내용으로 전환하여 실행하는 시스템 호출이다. 메모리 공간에 새로운 프로그램 내용이 덮어 써진다는 점에서 이는 자식 프로세스가 새로운 옷으로 갈아입었다고 불 수 있다. exec를 호출하면 코드 영역과 데이터 영역의 내용이 실행할 프로그램의 내용으로 바뀌고, 나머지 영역은 초기화된다.

정리하면, 부모가 자식 프로세스를 실행하여 프로세스 계층 구조를 이루는 과정은 fork과 exec가 반복되는 과정이라 볼 수 있다. 부모 프로세스가 자식 프로세스를 fork한 뒤에 부모 프로세스, 자식 프로세스 누구도 exec를 호출하지 않는 경우도 있다. 이 경우 부모 프로세스와 자식 프로세스는 같은 코드를 병행하여 실행하는 프로세스가 된다.

프로세스와 스레드

스레드(thread)는 실행의 단위이다. 조금 더 정확하게 표현하자면, 스레드란 프로세스를 구성하는 실행의 흐름 단위이다. 그리고 하나의 프로세스는 여러 개의 스레드를 가질 수 있다. 스레드를 이용하면 하나의 프로세스에서 여러 부분을 동시에 실행할 수 있다.

스레드는 프로세스 내에서 각기 다른 스레드 ID, 프로그램 카운터 값을 비롯한 레지스터 값, 스택으로 구성된다. 각자 프로그램 카운터 값을 비롯한 레지스터 값, 스택을 가지고 있기에 스레드마다 각기 다른 코드를 실행할 수 있다. 여기서 중요한 점은 프로세스의 스레드들은 실행에 필요한 최소한의 정보(프로그램 카운터를 포함한 레지스터, 스택)만을 유지한 채 프로세스 자원을 공유하며 실행된다는 점이다. 프로세스의 자원을 공유한다는 것이 스레드의 핵심이다. 최근 많은 운영체제는 CPU에 처리할 작업을 전달할 때 프로세스가 아닌 스레드 단위로 전달한다. 그리고 스레드는 프로세스 자원을 공유한 채 실행에 필요한 최소한의 정보만으로 실행된다.

멀티프로세스와 멀티스레드

컴퓨터는 실행 과정에서 여러 프로세스가 동시에 실행될 수 있고, 그 프로세스를 이루는 스레드는 여러 개 있을 수 있다고 하였다. 이떄 여러 프로세스를 동시에 실행하는 것을 멀티프로세스(multiprocess), 그리고 여러 스레드로 프로세스를 동시에 실행하는 것을 멀티스레드(multithread)라고 한다.

동일한 작업을 수행하는 단일 스레드 프로세스 여러 개를 실행하는 것과 하나의 프로세스를 여러 스레드로 실행하는 것은 무엇이 다를까? 프로세스끼리는 기본적으로 자원을 공유하지 않지만, 스레드끼리는 같은 프로세스 내의 자원을 공유한다.

프로세스를 fork하여 같은 작업을 하는 동일한 프로세스 두 개를 동시에 실행하면 코드 영역, 데이터 영역, 힙 영역 등을 비롯한 모든 자원이 복제되어 메모리에 적재된다. 한 마디로 PID, 저장된 메모리 주소를 제외하면 모든 것이 동일한 프로세스 두 개가 통쨰로 메모리에 적재되는 것이다. fork를 세 번, 네 번 하면 마찬가지로 메모리에는 같은 프로세스가 통째로 세 개, 네 개 적재된다. 이는 같은 프로그램을 실행하기 위해 메모리에 동일한 내용들이 중복해서 존재하는 것이므로 낭비이다.

이에 반해 스레드들은 각기 다른 스레드 ID, 프로그램 카운터 값을 포함한 레지스터 값, 스택을 가질 뿐 프로세스가 가지고 있는 자원을 공유한다. 즉, 같은 프로세스 내의 모든 스레드는 동일한 주소 공간의 코드, 데이터, 힙 영역을 공유하고, 열린 파이과 같은 프로세스 자원을 공유한다. 여러 프로세스를 병행 실행하는 것보다 메모리를 더 효율적으로 사용할 수 있다. 또한 서로 다른 프로세스들은 기본적으로 자원을 공유하지 않기 때문에 서로가 남남처럼 독립적으로 실행되는 반면, 스레드는 프로세스의 자원을 공유하기 때문에 서로 협력과 통신에 유리하다.

프로세스의 자원을 공유한다는 특성은 떄론 단점이 될 수도 있는데, 멀티프로세스 환경에서는 하나의 프로세스에 문제가 생겨도 다른 프로세스에는 지장이 적거나 없지만, 멀티스레드 환경에서는 하나의 스레드에 문제가 생기면 프로세스 전체에 문제가 생길 수 있다. 모든 스레드는 프로세스의 자원을 공유하고, 하나의 스레드에 문제가 생기면 다른 스레드도 영향을 받기 때문이다.

프로세스끼리는 '기본적으로' 자원을 공유하지 않지만, 프로세스끼리도 충분히 자원을 공유하고 데이터를 주고 받을 수 있다. 프로세스 간의 자원을 공유하고 주고받는 것을 프로세스 간 통신(IPC: Inter-Process Communication)이라고 부른다.

 

11 CPU 스케줄링

---

운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 CPU 스케줄링(CPU scheduling)이라고 한다. CPU 스케줄링은 컴퓨터 성능과도 직결되는 대단히 중요한 문제다. 프로세스들에게 현명하게 CPU를 배분하지 못하면 반드시 실행되어야 할 프로세스들이 실행되지 못하거나, 당장 급하지 않은 프로세스들만 주로 실행되는 등 무질서한 상태가 발생할 수도 있기 때문이다.

프로세스 우선순위

프로세스는 종류마다 입출력장치를 이용하는 시간과 CPU를 이용하는 시간의 양에는 차이가 있다. 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스도 있고, 복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스와 같이 CPU 작업이 많은 프로세스도 있다. 전자를 입출력 집중 프로세스(I/O bound process)라고 하고, 후자를 CPU 집중 프로세스(CPU bound process)라고 한다. 입출력 집중 프로세스는 실행 상태보다는 입출력을 위한 대기 상태에 더 많이 머무르게 된다. 반대로 CPU 집중 프로세스는 대기 상태보다는 실행 상태에 더 많이 머무르게 된다. CPU 집중 프로세스는 CPU를 많이 사용해야 하는 프로세스이고, 입출력 집중 프로세스는 그렇지 않은 프로세스인데, CPU 집중 프로세스와 입출력 집중 프로세스가 모두 동일한 빈도로 CPU를 사용하는 것은 비합리적이다.

CPU 집중 프로세스와 입출력 집중 프로세스가 동시에 CPU 자원을 요구했다고 가정해보자. 이러한 경우 입출력 집중 프로세스를 가능한 빨리 실행시켜 입출력 장치를 끊임없이 작동시키고, 그 다음 CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적이다. 입출력장치가 입출력 작업을 완료하기 전까지는 입출력 집중 프로세스는 어차피 대기 상태가 될 예정이기 때문에 입출력 집중  프로세스를 얼른 먼저 처리해 버리면 다른 프로세스가 CPU를 사용할 수 있기 때문이다. 이렇듯 모든 프로세스가 CPU를 차례대로 돌아가며 사용하는 것보다 각각의 상황에 맞게 CPU를 배분하는 것이 더 효율적이다.

상황에 맞게, 그리고 프로세스의 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 하기 위해 운영체제는 프로세스마다 우선순위(proiority)를 부여한다. 운영체제는 각 프로세스의 PCB에 우선순위를 명시하고, PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정한다. 그렇게 자연스레 우선순위가 높은 프로세스는 더 빨리, 더 자주 실행된다.

스케줄링 큐

PCB에 우선순위가 적혀 있다고는 하지만, CPU를 사용할 다음 프로세스를 찾기 위해 운영체제가 일일이 모든 프로세스의 PCB를 뒤적거리는 것은 비효율적이다. CPU를 원하는 프로세스들은 한 두개가 아니고, CPU를 요구하는 새로운 프로세스는 언제든지 생길 수 있으니 말이다. 운영체제가 매번 일일이 모든 PCB를 검사하여 먼저 자원을 이용할 프로세스를 결정하는 일은 매우 번거로울뿐더러 오랜 시간이 걸리는 일이다. 그래서 운영체제는 프로세스들에 '줄을 서서 기다릴 것'을 요구한다. CPU를 사용하고 싶은 프로세스들, 메모리에 적재되고 싶은 프로세스들, 특정 입출력장치를 사용하고 싶은 프로세스들은 모두 줄 세우는 것이다. 그리고 운영체제는 이 줄을 스케줄링 큐(scheduling queue)로 구현하고 관리한다. 대표적인 큐로 준비 큐와 대기 큐가 있다. 준비 큐(ready queue)는 CPU를 이용하고 싶은 프로세스들이 서는 줄을 의미하고, 대기 큐(wating queue)는 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄을 의미한다.

준비 상태에 있는 프로세스들의 PCB는 준비 큐의 마지막에 삽입되어 CPU를 사용할 차례를 기다린다. 운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행하되, 그중 우선순위가 높은 프로세스를 먼저 실행한다. 우선순위가 낮은 프로세스들이 먼저 큐에 삽입되어 줄을 섰다고 할지라도 우선순위가 높은 프로세스는 그들보다 먼저 처리될 수 있다. 대기 상태에 있는 프로세스도 마찬가지다. 같은 장치를요구한 프로세스들은 같은 대기 큐에서 기다린다. 입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고, 이 PCB를 준비 상태로 변경한 뒤 대기큐에서 제거한다. 당연히 해당 PCB는 준비 큐로 이동한다.

선점형과 비선점형 스케줄링

선점형 스케줄링(preemptive scheduling)은 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식을 의미한다. 다시 말해 어느 하나의 프로세스가 자원 사용을 독점할 수 없는 스케줄링 방식이다. 프로세스마다 정해진 시간만큼 CPU를 사용하고, 정해진 시간을 모두 소비하여 타이머 인터럽트가 발생하면 운영체제가 해당 프로세스로부터 CPU 자원을 빼앗아 다음 프로세스에 할당하는 방식은 선점형 스케줄링의 일종으로 볼 수 있다.

비선점형 스케줄링(non-preemptive scheduling)이란 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식을 의미한다. 다시 말해 비선점형 스케줄링은 하나의 프로세스가 자원 사용을 독점할 수 있는 스케줄링 방식이다. 만약 비선점형 스케줄링 방식으로 자원을 이용하는 프로세스가 있다면 다른 프로세스들은 그 프로세스의 사용이 모두 끝날 때까지 기다려야 한다.

현재 대부분의 운영체제는 선점형 스케줄링 방식을 차용하고 있지만, 선점형 스케줄링과 비선점형 스케줄링은 각기 장단점을 가지고 있다. 선점형 스케줄링은 더 급한 프로세스가 언제든 끼어들어 사용할 수 있는 스케줄링 방식이므로 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있다는 장점이 있지만, 그만큼 문맥 교환 과정에서 오버헤드가 발생한다.

반면 비선점형 스케줄링은 문맥 교환 횟수가 선점형 스케줄링보다 적기 때문에 문맥 교환에서 발생하는 오버헤드는 선점형 스케줄링보다 적지만, 하나의 프로세스가 자원을 사용 중이라면 당장 자원을 사용해야 하는 상황에서도 무작정 기다리는 수밖에 없다. 모든 프로세스가 골고루 자원을 사용할 수 없다는 단점이 있다.

스케줄링 알고리즘의 종류

선입 선처리 스케줄링

선입 선처리 스케줄링은 FCFS 스케줄링(First Come First Served Scheduling)이라고도 부른다. 이는 단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식이다. 즉, 선입 선처리 스케줄링은 CPU를 먼저 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식이다. 선입 선처리 스케줄링은 어뜻 보기에는 가장 공정해 보이지만, 때때로 ㅂ프로세스들이 기다리는 시간이 매우 길어질 수 있다는 단점이 있다. 가령 CPU를 오래 사용하는 프로세스가 먼저 도착하면 다른 프로세스는 그 프로세스가 CPU를 사용하는 동안 무작정 기다리는 수밖에 없다. 에를 들어 17ms 동안 CPU를 이용하는 프로세스 A, 5ms동안 CPU를 이용하는 프로세스 B, 2ms 동안 CPU를 이용하는 프로세스 C가 차례로 준비 큐에 삽입된다면 프로세스 C는 고작 2ms를 실행하기 위해 22ms(17ms+5ms)라는 긴 시간을 기다려야만 한다. 이런 현상을 호위 효과(convoy effect)라고 한다.

최단 작업 우선 스케줄링

호위 효과를 방지하려면 어떻게 해야할까? 단순하게 생각해 보면 CPU 사용 시간이 긴 프로세스는 나중에 실행하고, CPU 사용 시간이 짧은 간단한 프로세스를 먼저 실행하면 된다. 앞서 보여준 예시에서는 프로세스 A의 CPU 사용 시간이 매우 길기 때문에 B와 C는 무작정 오래 기다릴 수밖에 없었다. 만약 CPU 사용 시간이 짧은 C와 B부터 실행한다면 C는 더 이상 기다릴 필요가 없고, B는 2ms, A는 7ms만 기다리면 된다. 이렇게 준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방ㅎ식을 최단 작업 우선 스케줄링 혹은 SJF 스케줄링(Shortest Job First Scheduling)이라고 한다. 최단 작업 우선 스케줄링은 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될 수도 있다. 선점형 최단 작업 우선 스케줄링이 뒤에 언급할 최소 잔여 시간 우선 스케줄링이다.

라운드 로빈 스케줄링

라운드 로빈 스케줄링(round robin scheduling)은 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식이다. 타임 슬라이스란 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미한다. 즉, 라운드 로빈 스케줄링은 정해진 타임 슬라이스만큼의 시간 동안 돌아가면 CPU를 이용하는 선점형 스케줄링이다. 큐에 삽입된 프로세스들은 삽입된 순서대로 CPU를 이용하되 정해진 시간만큼만 CPU를 이용하고, 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입되어 문맥 교환이 발생한다. 라운드 로빈 스케줄링에서는 타임 슬라이스 크기가 매우 중요하다. 타임 슬라잏스가 지나치게 크면 사실상 선입 선처리 스케줄링과 다를 바 없어 호위 효과가 생길 여지가 있고, 타임 슬라이스가 지나치게 작으면 문맥 교환에 발생하는 비용이 커 CPU는 프로세스를  처리하는 일보다 프로세스를 전환하는 데에 온 힘을 다 쓸 여지가 있기 때문이다.

최소 잔요 시간 우선 스케줄링

최소 잔여 시간 우선 스케줄링 혹은 SRT(Shortest Remaining Time) 스케줄링은 최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 스케줄링 방식이다. 최소 잔여 시간 우선 스케줄링 하에서 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.

우선순위 스케줄링

우선순위 스케줄링(priority scheduling)은 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘이다. 우선순위가 같은 프로세스는 선입 선처리로 스케줄링한다. 앞서 설명한 최단 작업 우선 스케줄링, 최소 잔여 시간 우선 스케줄링 알고리즘은 넓은 의미에서 우선순위 스케줄링의 일종으로 볼 수 있다.

우선순위 스케줄링은 근본적인 문제를 내포하고 있다. 우선순위가 높은 프로세스를 우선하여 처리하는 방식이기에 우선수위가 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있다. 이를 기아(starvation) 현상이라고 한다. 우선순위가 높은 프로세스만 계속 먼저 실행되니 우선순위가 낮은 프로세스의 실행은 계속 뒤로 밀리는 것이다. 이를 방지하기 위한 대표적인 기법으로 에이징(aging)이 있다. 이는 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식이다. 말하자면 대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법이다. 에이징 기법을 적용하면 우선순위가 낮아 마냥 기다리기만 하는 프로세스가 없어진다. 우선순위가 낮더라도 언젠가는 높은 우선순위가 될테니까 말이다.

다단계 큐 스케줄링

다단계 큐 스케줄링은 앞서 설명한 우선순위 스케줄링의 발전된 형태이다. 다단계 큐 스케줄링(multilevel queue scheduling)은 우선수위별로 준비 큐를 여러 개 사용하는 스케줄링 방식이다. 다단계 큐 스케줄링 하에서는 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있으면 그다음 우선순위 큐에 있는 프로세스들을 처리한다.

이렇게 큐를 여러 개 두면 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해진다. 가령 어떤 큐에는 우선순위가 비교적 높아야 하는 CPU 집중 프로세스가 삽입될 수 있고, 어떤 큐에는 우선순위가 비교적 낮아도 상관없는 입출력 집중 프로세스가 삽입될 수 있다. 또 어떤 큐에는 (우선순위가 비교적 높아야 하는) 백그라운드 프로세스들을 삽입할 수 있고, 어떤 큐에는 (우선순위가 비교적 낮아도 무방한) 사용자와의 상호작용이 잦은 프로세스들을 삽입할 수 있다.

또한 큐별로 타임 슬라이스를 여러 개 지정할 수도 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수도 있다. 예를 들어 어떤 큐에서의 타임 슬라이스는 크게, 어떤 큐에서의 타임 슬라이스는 작게 사용하고, 어떤 큐에서는 선입 선처리 스케줄링을 사용하고, 어떤 큐에서는 라운드 로빈 스케줄링을 사용할 수 있다.

다단계 피드백 큐 스케줄링

다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링의 발전된 형태이다. 앞서 설명한 다단계 큐 스케줄링에서는 프로세스들이 큐 사이를 이동할 수 없다. 그러나 이런 방식대로라면 우선순위가 낮은 프로세스는 계속 연기될 여지가 있다. 즉, 다시 기아 현상이 발생할 수 있다. 언제 높은 우선순위의 프로세스가 들어올지 모르는데, 우선순위가 낮은 프로세스 입장에서는 매우 불리하다. 이를 보완한 스케줄링 알고리즘이 ㄷ다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)이다. 다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링과 비슷하게 작동하지만, 한 가지가 다르다. 바로 프로세스들이 큐 사이를 이동할 수 있다는 점이다. 다단계 피드백 큐 스케줄링에서 새로 준비 상태가 된 프로세스가 있다면 우선 우선순위가 가장 높은 우선순위 큐에 삽입되고 일정 시간(타임 슬라이스) 동안 실행된다. 그리고 만약 프로세스가 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행된다. 그리고 또 해당 큐에서 실행이 끝나지 않는다면 프로세스는 또 다음 우선순위 큐에 삽입되고, 결국 CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아진다. 즉, CPU를 비교적 오래 사용해야 하는 CPU 집중 프로세스들은 자연스레 우선순위가 낮아지고, CPU를 비교적 적게 사용하는 입출력 집중 프로세스들은 자연스레 우선순위가 높은 큐에서 실행이 끝난다. 다단계 피드백 큐 스케줄링은 플세스들이 큐 사이를 이동할 수 있는 방식이기 때문에 낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방할 수 있다. 즉, 다단계 피드백 큐 스케줄링 알고리즘은 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘이다. 다단계 피드백 큐 스케줄링은 구현이 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘으로 알려져 있다.

 

12 프로세스 동기화

---

동기화의 의미

프로세스 동기화란 프로세스들 사이의 수행 시기를 맞추는 것을 의미하는데, 대표적으로 아래 2가지이다.

• 실행 순서 제어: 프로세스를 올바른 순서대로 실행하기
• 상호 배제: 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하기

가령 Writer라는 프로세스와 Reader라는 프로세스가 동시에 실행 중이라고 가정해보자. Writer 프로세스는 Book.txt 파일에 값을 저장하는 프로세스이고, Reader 프로세스는 Book.txt 파일에 저장된 값을 읽어 들이는 프로세스라고 가정해보자. 이 두 프로세스는 무작정 아무 순서대로 실행되어서는 안된다. Reader 프로세스는 Writer 프로세스 실행이 끝나야 비로소 실행할 수 있기 때문이다. Writer 프로세스가 Book.txt에 값을 저장하기도 전에 Reader 프로세스가 Book.txt를 읽는 것은 올바른 실행 순서가 아니다. 다시 말해 Reader 프로세스는 'Book.txt 안에 값이 존재한다'는 특정 조건이 만족되어야만 실행을 이어나갈 수 있다. 이렇게 동시에 실행되는 프로세스를 올바른 순서대로 실행하는 것이 실행 순서제어이다.

상호 배제(mutual exclusion)는 공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘이다. 이 또한 간단한 예시를 들어보자. 가령 계좌에 10만 원이 저축되어 있다고 가정해 보자. 그리고 프로세스 A는 현재 저축된 금액에 2만 원을 넣는 프로세스, 프로세스 B는 현재 저축된 금액에 5만 원을 넣는 프로세스라고 가정해 보자.

프로세스 A가 실행되는 과정을 조금 더 자세히 아래와 같이 나타낼 수 있다.

1. 계좌의 잔액을 읽어 들인다.
2. 읽어 들인 잔액에 2만 원을 더한다.
3. 더한 값을 저장한다.

프로세스 B는 아래와 같은 순서대로 실행된다.

1. 계좌의 잔액을 읽어 들인다.
2. 읽어 들인 잔액에 5만 원을 더한다.
3. 더한 값을 저장한다.

이제 프로세스 A와 B가 동시에 실행되었다고 가정해보자. 당연히 실행 결과 17만 원이 계좌에 남을 것일 기대할 것이지만, 동기화가 제대로 이루어지지 않은 경우 아래와 같이 전혀 엉뚱한 결과가 나온다.

프로세스 A	프로세스 B	잔액
잔액을 읽어 들인다		10만 원
읽어 들인 값에서 2만원을 더한다		10만 원
문맥 교환		10만 원
	잔액을 읽어 들인다	10만 원
	읽어 들인 값에서 5만 원을 더한다	10만 원
	문맥 교환	10만 원
더한 값 저장		12만 원
	더한 값 저장	15만 원
		최종 잔액 = 15만원

A가 끝나기도 전에 B가 잔액을 읽어 버렸기 때문에 엉뚱한 결과가 나온 것이다. A와 B가 올바르게 실행하기 위해서는 한 프로세스가 잔액에 접근했을 때 다른 프로세스는 기다려야 한다. 이렇게 동시에 접근해서는 안 되는 자원에 동시에 접근하지 못하게 하는 것이 상호 배제를 위한 동기화이다.

공유 자원과 임계 구역

계좌 잔액 문제 예시에서 동시에 실행되는 프로세스들은 전역 변수 '잔액'이라는 공동의 자원을 두고 작업했다. 이러한 자원을 공유 자원(shared resource)이라고 한다. 공유 자원은 전역 변수가 될 수도 있고, 파일이 될 수도 있고, 입출력장치, 보조기억장치가 될 수도 있다. 그리고 이 공유 자원 중에는 두 개 이상의 프로세스를 동시에 실행하면 문제가 발생하는 자원이 있다. '잔액' 변수이다. 이렇게 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역을 임계 구역(critical section)이라고 한다. 두 개 이상의 프로세스가 임계 구역에 진입하고자 하면 둘 중 하나는 대기해야 한다. 임계 구역에 먼저 진입한 프로세스의 작업이 마무리되면 그제서야 비로소 기다렸던 프로세스가 임계구역에 진입한다.

임계 구역은 두 개 이상의 프로세스가 동시에 실행되면 안 되는 영역이지만, 잘못된 실행으로 인해 여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행하여 문제가 발생하는 경우가 있는데, 이를 레이스 컨디션(race condition)이라고 한다. 레이스 컨디션이 발생하면 계좌 잔액 문제처럼 데이터의 일관성이 깨지는 문제가 발생한다. 레이스 컨디션이 발생하는 근본적인 이유는 고급 언어는 실행 과정에서 저급 언어로 변환되어 실행되기 때문이다. 잔액 문제에서 총합을 더하는 코드는 고급 언어에서 한 줄로 작성하지만, 이는 컴퓨터 내부에서 다음과 같이 여러 줄의 저급 언어로 변환되어 실행된다.

고급 언어

총합++;

저급 언어

r1 = 총합;
r1 = r1 + 1;
총합 = r1

컴퓨터는 고급 언어가 아닌 저급 언어를 실행하기 때문에 여러 줄의 저급 언어로 변환된 고급 언어 한 줄을 실행하는 과정에서 문맥 교환이 일어날 수 있다. 저급 언어를 실행하는 과정에서 문맥 교환이 일어난다면 아래와 같은 문제가 발생한다.

프로세스 A	프로세스 B	현재 총합	현재 r1	현재 r2
r1 = 총합		10	10
r1 = r1 + 1		10	11
문맥교환		10	11
	r2 = 총합	10	11	10
	r2 = r2 - 1	10	11	9
	문맥교환	10	11	9
총합 = r1		11	11	9
문맥교환		11	11	9
	총합 = r2	9	11	9
		최종 총합 = 9

운영체제는 이러한 임계 구역 문제를 알 ㅐ세 가지 원칙 하에 해결한다. 달리 말해 상호 배제를 위한 동기화를 위해서는 아래 세 가지 원칙이 반드시 지켜져야만 한다.

• 상호 배제(mutual exclusion) : 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없다.
• 진행(progress) : 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
• 유한 대기(bounded wating) : 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 언젠가는 임계 구역에 들어올 수 있어야 한다(임계 구역에 들어오기 위해 무한정 대기해서는 안 된다).

뮤텍스 락

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

• 자물쇠 역할 : 프로세스들이 공유하는 전역 변수 lock
• 임계 구역을 잠그는 역할: acquire 함수
• 임계 구역의 잠금을 해제하는 역할 : release 함수

참고로 qcquire 함수는 반복적으로 lock을 확인하는데, 이르 바쁜 대기(busy wait)라고 한다.

세마포

세마포(semaphore)는 철도 신호기에서 유래한 단어이다. 기차는 신호기가 내려가 있을 때는 '멈춤' 신호로 간주하고 잠시 멈춘다. 반대로 신호기가 올라와 있을 때는 '가도 좋다'는 신호로 간주하고 다시 움직이기 시작한다. 세마포는 이와 같이 '멈춤' 신호와 '가도 좋다'라는 신호로서 임계 구역을 관리한다. 즉, 프로세스는 임계 구역 앞에서 멈춤 신호를 받으면 잠시 기다리고, 가도 좋다는 신호를 받으면 그제서야 임계 구역에 들어가게 된다. 세마포는 뮤텍스 락과 비슷하게 하나의 변수와 두 개의 함수로 단순하게 구현한다.

• 임계 구역에 진입할 수 있는 프로세스의 개수(사용 가능한 공유 자원의 개수)를 나타내는 전역변수 S
• 임계 구역에 들어가도 좋은지, 기다려야 할지를 알려주는 wait 함수
• 임계 구역 앞에서 기다리는 프로세스에 '이제 가도 좋다'고 신호를 주는 signal 함수

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

모니터

세마포에서 매번 임계 구역에 앞뒤로 일일이 wait와 signal 함수를 명시하는 것은 매우 번거롭고 실수를 유발한다. 이에 최근에 등장한 동기화 도구가 모니터(monitor)이다. 모니터는 공유 자원과 공유 자원에 접근하기 위한 인터페이스(통로)를 묶어 관리하고, 모든 프로세스는 반드시 인터페이스를 통해서만 공유 자원에 접근하도록 한다.

 

13 교착 상태

---

일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 교착 상태(deadlock)라고 한다.

교착 상태 발생 조건

상호 배제, 점유와 대기, 비선점, 원형 대기로 총 4가지인데, 이 조건들 중 하나라도 만족하지 않는다면 교착상태는 발생하지 않고, 4가지 조건이 모두 만족되면 발생할 가능성이 있다.

• 상호 배제(mutual exclusion) : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때
• 점유와 대기(hold and wait) : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
• 비선점(nonpreemptive) : 비선점 자원은 그 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 이용할 수 있다. 즉, 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못할 때 교착 상태가 발생할 수 있다.
• 원형 대기(circular wait) : 자원 할당 그래프가 원의 형태로 그려질 때

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

교착 상태 예방

교착 상태 발생 필요 조건 4가지 중 하나를 충족하지 못하게 하는 방법이다.

• 상호배제 없애기 : 자원의 상호 배제를 없앤다는 말의 의미는 모든 자원을 공유 가능하게 만든다는 말과 같다. 다만 이 방식대로면 이론적으로는 교착상태를 없앨 수 있지만, 현실적으로 모든 자원의 상호 배제를 없애기는 어렵기에 이 방식을 현실에서 사용하기에는 다소 무리가 있다.
• 점유와 대기 없애기 : 점유와 대기를 없애면 운영체제는 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다. 이 방식은 단점이 있다. 우선 자원의 활용률이 낮아질 우려가 있다. 점유와 대기를 금지하면 한 프로세스에 필요한 자원들을 몰아주고, 그 다음에 다른 프로세스에 필요한 자원들을 몰아줘야 한다. 이는 당장 자원이 필요해도 기다릴 수밖에 없는 프로세스와 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산하기 때문에 자원의 활용률이 낮아진다. 게다가 점유와 대기를 금지하면 많은 자원을 사용하는 프로세스가 불리해진다. 자원을 많이 사용하는 프로세스는 자원을 적게 사용하는 프로세스에 비해 동시에 자원을 사용할 타이밍을 확보하기가 어렵기 때문이다. 이는 결국 많은 자원을 필요로 하는 프로세스가 무한정 기다리게 되는 기아 현상을 야기할 우려가 있다.
• 비선점 조건 없애기 : 비선점 조건을 없애면 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있다. 이 방식은 선점하여 사용할 수 없는 일부 자원에 대해서는 효과적이다. 가령 CPU는 프로세스들이 선점할 수 있는 대표적인 자원이다. 한 프로세스가 CPU를 이용하다가 일정 시간이 지나면 아직 작업이 모두 끝나지 않았다고 할지라도 다른 프로세스가 CPU를 할당받아 사용할 수 있기 때문이다. 하지만 프린터나 스캐너와 같이 모든 자원이 이렇게 선점 가능한 것은 아니기 때문에 범용성이 떨어지는 방안이다.
• 원형 대기 조건 없애기 : 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 간단하게 원형 대기가 발생하지 않는다. 이 방식은 위 3가지 방식보다 현실적이지만 역시 단점은 있다. 모든 컴퓨터 시스템 내에 존재하는 수많은 자원에 번호를 붙이는 일은 그리 간단한 작업이 아니거니와 각 자원에 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어질 수 있다.

이렇듯 교착 상태의 발생 조건을 원천적으로 제거하는 예방 방식은 여러 부작용이 따른다.

교착 상태 회피

• 안전 상태(safe state) : 교착 상태가 발생하지 않고 무든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태 
• 불안전 상태(unsafe state) : 교착 상태가 발생할 수도 있는 상황
• 안전 순서열(safe sequence) : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미한다. 예를 들어 웹 브라우저, 메모장, 게임 프로세스가 동시에 운영체제에 자원을 요청한 상황에서 웹 브라우저-메모장-게임 프로세스 순서대로 자원을 할당하면 교착 상태가 발생하지 않는다고 가정해보자. 이 경우 웹 브라우저->메무장->게임이 안전 순서열이 된다. 안전 순서열이 있는 상태를 안전 상태라고 볼 수 있다.

교착 상태 검출 후 회복

운영체제는 프로세스들이 자원을 요구할 때마다 그떄그때 모두 할당하며, 교착 상태 발생 여부를 주기적으로 검사한다. 그리고 교착 상태가 검출되면 비로소 다음과 같은 방식으로 회복한다.

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

 

14 가상 메모리

---

스와핑

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

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

스와핑을 이용하면 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시에 실행할 수 있다.

메모리 할당

비어 있는 메모리 공간에 프로세스를 연속적으로 할당하는 방식에는 3가지가 있다.

• 최초 적합(first fit) : 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 ㅅ후 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식이다. 프로세스가 적대될 수 있는 공간을 발견하는 즉시 메모리를 할당하는 방식이므로 검색을 최소화할 수 있고 결과적으로 빠른 할당이 가능하다.
• 최적 적합(best fit) : 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식이다.
• 최악 적합(worst fit) : 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식이다.

외부 단편화

프로세스를 메모리에 연속적으로 배치하는 연속 메모리 할당은 언뜻 들으면 당연하게 느껴질 수 있지만, 사실 이는 메모리를 효율적으로 사용하는 방법이 아니다. 왜냐하면 연속 메모리 할당은 외부 단편화(external fragmentation)라는 문제를 내포하고 있기 때문이다. 프로세스들이 메모리에 연속적으로 할당되는 환경에서는 프로세스들이 실행되고 종료되기를 반복하며 메모리 사이 사이에 빈 공간들이 생긴다. 프로세스 바깥에 생기는 이러한 빈 공간들은 분명 빈 공간이지만 그 공간보다 큰 프로세스를 적재하기 어려운 상황을 초래하고, 결국 메모리 낭비로 이어진다.

외부 단편화를 해결할 수 있는 대표적인 방안으로 메모리를 압축(compaction)하는 방법이 있다. 메모리 조각 모음이라고도 부른다. 압축은 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식으로 메모리 내에 저장된 프로세스를 적당히 재배치시켜 여기저기 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법이다. 다만 압축 방식은 여러 단점이 있다. 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야 하고, 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기하며, 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하며 압축할 수 있는지에 대한 명확한 방법을 결정하기 어렵다. 이에 외부 단편화를 없앨 수 있는 또 다른 해결 방안이 등장했는데, 이것이 오늘날까지도 사용되는 가상 메모리 기법, 그 중에서도 페이징 기법이다.

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

페이징이란

페이징(paging)은 프로세스의 논리 주소 공간을 페이지(page)라는 일정한 단위로 자르고, 메모리의 물리 주소 공간을 프레임(frame)이라는 페이지와 동일한 트기의 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법이다. 페이징에서도 스와핑을 사용할 수 있다. 페이징을 사용하는 시스템에서는 프로세스 전체가 스왑 아웃/스왑 인되는 것이 아닌 페이지 단위로 스왑 아웃/스왑 인된다. 즉, 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃되고, 실행에 필요한 페이지들은 메모리로 스왑 인되는 것이다. 페이징 시스템에서의 스왑 아웃은 페이지 아웃(page out), 스왑 인은 페이지 인(page in)이라고 부르기도 한다. 이는 다르게 말하면 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없나는 말과 같다. 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하고, 당장 실행에 필요하지 않은 페이지들은 보조기억장치에 남겨둘 수 있다. 이와 같은 방식을 통해 물리 메모리보다 더 큰 프로세스를 실행할 수 있다.

페이지 테이블

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

페이지 테이블은 페이지 번호와 프레임 번호를 찍지어 주는 일종의 이정표이다. CPU로 하여금 페이지 번호만 보고 해당 페이지가 적재된 프레임을 찾을 수 있게 한다. 다시 말해 페이지 테이블은 현재 어떤 페이지가 어떤 프레임에 할당되었는지를 알려준다. 프로세스마다 각자의 프로세스 테이블이 있다. 가령 프로세스 A의 페이지 테이블이 아래와 같다면 CPU는 이를 보고 '0번 페이지는 3번 프레임에, 1번 페이지는 5번 프레임에, 2번 페이지는 2번 프레임에 할당되어 있다'라는 사실을 알 수 있다.

페이지 번호	프레임 번호
0	3
1	4
2	2

위와 같은 방식을 ㅗ비록 물리 주소상에서는 프로세스들이 분산되어 저장되어 있더라고 CPU 입장에서 바라본 논리 주소는 연속적으로 보일 수 있어 CPU는 논리 주소를 그저 순차적으로 실행하면 된다.

페이징은 외부 단편화 문제를 해결할 수 있지만, 내부 단편화(internal fragmentation)라는 문제를 야기할 수 있다. 페이징은 프로세스의 논리 주소 공간을 페이지라는 일정한 크기 단위로 자른다고 했다. 그런데 모든 프로세스가 페이지 크기에 딱 맞게 잘리는 것은 아니다. 다시 말해 모든 프로세스 크기가 페이지의 배수는 아니다. 가령 페이지 크기가 10KB인데, 프로세스의 크기가 108KB라고 하면 이 경우 마지막 페이지는 2KB만큼의 크기가 남는다. 이러한 메모리 낭비를 내부 단편화라고 한다.

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

그런데 이렇게 페이지 테이블을 메모리에 두면 메모리 접근 시간이 2배로 늘어나는 문제가 있다. 메모리에 있는 페이지 테이블을 보기 위해 한 번, 그렇게 알게된 프레임에 접근하기 위해 한 번, 이렇게 총 2번의 메모리 접근이 필요하기 때문이다. 이와 같은 문제를 해결하기 위헤 CPU 곁에(일반적으로 MMU 내에) TLB(Translation Lookaside Buffer)라는 페이지 테이블의 캐시 메모리를 둔다. TLB는 페이지 테이블의 캐시이기 때문에 페이지 테이블의 일부 내용을 저장한다. 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와 저장한다. CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 이를 TLB 히트(TLB hit)라고 한다. 이 경우에는 페이지가 적재된 프레임을 알기 위해 메모리에 접근할 필요가 없다. 그렇기에 메모리 접근을 한 번만 하면 된다. 하지만 만일 페이지 번호가 TLB에 없을 경우 어쩔 수 없이 페이지가 적재된 프레임을 알기 위해 메모리 내의 페이지 테이블에 접근하는 수밖에 없는데 이를 TLB 미스(TLB miss)라고 한다.

페이지 테이블 엔트리

페이지 테이블의 각 엔트리, 다시 말해 페이지 테이블의 각각의 행들을 페이지 테이블 엔트리(PTE: Page Table Entry)라고 한다. 여기에는 유효 비트, 보호 비트, 참조 비트, 수정 비트라는 중요한 정보가 포함되어 있다.

• 유효 비트(valid bit) : 현재 해당 페이지에 접근 가능한지 여부를 알려준다. 페이지 테이블 엔트리에서 프레임 번호 다음을 ㅗ중요한 정보라고 볼 수 있다. 일반적으로 프로세스를 이루는 모든 페이지가 메모리에 있지 않다. 일부 페이지는 보조기억장치(스왑 영역)에 있는 경우가 많다. 유효 비트는 현재 페이지가 메모리에 적재되어 있는지 아니면 보조기억장치에 있는지를 알려주는 비트이다. 즉, 페이지가 메모리에 적재되어 있다면 유효 비트가 1, 페이지가 메모리에 적재되어 있지 않다면 유효 비트가 0이 된다.
• 만일 CPU가 유효 비트가 0인 메모리에 적재되어 있지 않은 페이지로 접근하려고 하면 어떻게 될까? 이 경우 페이지 폴트 page fault 라는 예외(Exception)가 발생한다.
  1. CPU는 기존의 작업 내역을 백업한다.
  2. 페이지 폴트 처리 루틴을 실행한다.
  3. 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경해 준다.
  4. 페이지 폴트를 처리했다면 이제 CPU는 해당 페이지에 접근할 수 있게 된다.
• 수정 비트 modified bit 는 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려준다. 더티 비트 dirty bit 라고도 부르는데, 이 비트가 1이면 변경된 적이 있는 페이지, 0이면 변경된 적이 없는 페이 지(한 번도 접근한 적 없거나 읽기만 했던 페이지)임을 나타낸다. 수정 비트는 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없는지를 판단하기 위해 존재한다. CPU는 메모리를 읽기도 하지만 메모리에 값을 쓰기도 한다. CPU가 한 번도 접근하지 않았거나 읽기만 한 페이지의 경우 보조기억장치에 저장된 해당 페이지의 내용과 메모리에 저장된 페이지 내용은 아래 서로 같은 값을 가지고 있다. 이렇게 한 번도 수정된 적이 없는 페이지가 스왑 아웃될 경우 아무런 추가 작업 없이 새로 적재된 페이지로 덮어쓰기만 하면 된다. 어차피 똑같은 페이지가 보조기억장치에 저장되어 있으니까 말이다. 하지만 CPU가 쓰기 작업을 수행한 페이지(수정 비트가 1인 페이지)의 경우 보조기억장치에 저장된 페이지의 내용과 메모리에 저장된 페이지의 내용은 서로 다른 값을 갖게 된다. 이렇게 수정된 적이 있는 페이지가 스왑 아웃될 경우 변경된 값을 보조기억장치에 기록하는 작업이 추가되어야 한다. 이 작업이 필요한 페이지인지 아닌지를 판단하기 위해 페이지 테이블 엔트리에 수정 비트를 두는 것이다.
• 참조 비트 reference bit 는 CPU가 이 페이지에 접근한 적이 있는지 여부를 나타낸다. 적재 이후 CPU가 읽거나 쓴 페이지는 참조 비트가 1로 세팅되고, 적재 이후 한 번도 읽거나 쓴 적이 없는 페이지는 0으로 유지된다.
• 보호 비트 protection bit 는 페이지 보호 기능을 위해 존재하는 비트이다. 보호 비트를 통해 해당 페이지가 읽고 쓰기가 모두 가능한 페이지인지, 혹은 읽기만 가능한 페이지인지를 나타낼 수 있다. 가령 비트가 0일 경우 이 페이지는 읽기만 가능한 페이지임을 나타내고, 1일 경우 읽고 쓰기가 모두 가능한 페이지임을 나타내는 것이다. 앞서 프로세스를 이루는 요소 중 코드 영역은 읽기 전용 영역이 라고 했는데, 이러한 읽기 전용 페이지에 쓰기를 시도하면 운영체제가 이를 막아준다.

요구 페이징

프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법을 요구 페이징(demand paging)이라고 한다. 이름 그대로 실행에 요구되는 페이지만 적재하는 기법이다. 요구 페이징의 기본적인 양상은 다음과 같다.

1. CPU가 특정 페이지에 접근하는 명령어를 실행한다.
2. 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다.
3. 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0일 경우) 페이지 폴트가 발생한다.
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
5. 다시 1번을 수행한다.

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

요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체와 프레임 할당 과제를 해결해야 한다. 요구 페이징 기법으로 페이지들을 적재하다 보면 언젠가 메모리가 가득 차게 된다. 이떄는 당장 실행에 필요한 페이지를 적재하기 위해 메모리에 적재된 페이지를 보조기억장치로 내보내야 한다. 메모리에 적재된 페이지 중 어떤 페이지를 내보내는 것이 최선일지 결정하는 방법을 페이지 교체 알고리즘이라 한다.

페이지 교체 알고리즘

좋은 페이지 교체 알고리즘은 페이지 폴트를 가장 적게 일으키는 알고리즘이다. 페이지 폴트가 일어나면 보조기억장치로부터 필요한 페이지를 가져와야 하기 때문에 메모리에 적재된 페이지를 가져오는 것보다 느려지기 때문이다. 그렇기에 페이지 교체 알고리즘을 제대로 이해하려면 페이지 폴트 횟수를 알 수 있어야 한다. 그리고 페이지 폴트 횟수는 페이지 참조열(page reference string)을 통해 알 수 있다. 페이지 참조열의 개념은 간단하다. CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미한다. 가령 CPU가 아래와 같은 순서로 페이지에 접근했다고 가정하자.

2 2 2 3 5 5 5 3 3 7

여기서 연속된 페이지를 생략한 페이지열, 다시 말해 아래 숫자열이 페이지 참조열이다.

2 3 5 3 7

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

 

FIFO 페이지 교체 알고리즘(First-In First-Out page replacement Algorithm)

이름 그대로 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식이다. 가령 프로세스가 사용할 수 있는 프레임이 세 개 있다고 가정하고 페이지 참조열이 아래와 같다고 해보자.

2 3 1 3 5 2 3 4 2 3

그렇다면 FIFO 페이지 교체 알고리즘은 아래와 같은 순서대로 진행되어 총 4 번의 페이지 폴트가 발생한다. 페이지가 초기에 적재될 때 발생할 수 있는 페이지 폴트는 고려하지 않고, 적재된 페이지를 교체하기 위해 발생한 페이지 폴트만을 페이지 폴트고 간주했다.

					페이지 폴트	페이지 폴트	페이지 폴트	페이지 폴트
페이지 참조열	2	3	1	3	5	2	3	4	2	3
프레임	2	2	2	2	5	5	5	4	4	4
		3	3	3	3	2	2	2	2	2
			1	1	1	1	3	3	3	3
보조기억장치					2	3	1	5

FIFO 페이지 교체 알고리즘은 아이디어와 구현이 간단하지만, 마냥 좋은 것은 아니다. 프로그램 실행 초기에 적재된 페이지 속에는 프로그램 실행 초기에 잠깐 실행되다가 이후에 사용되지 않을 페이지도 있겠지만, 프로그램 실행 내내 사용될 내용을 포함하고 있을 수도 있다. 이런 페이지는 메모리에 먼저 적재되었다고 해서 내쫓아서는 안된다.

 

최적 페이지 교체 알고리즘(optimal page replacement algorithm)

CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘이다. 잘 생각해 보면 메모리에 오랫동안 남아야 할 페이지는 자주 사용될 페이지고, 반대로 메모리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지인데, 오랜 기간 메모리에 있었던 페이지라고 해서 보조기억장치로 내쫓는 건 비합리적이라고 볼 수 있다.

따라서 보조기억장치로 내보내야 할 페이지는 앞으로 사용 빈도가 가장 낮은 페이지이므로, 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘을 페이지 교체 알고리즘으로 삼는 것이 가장 합리적이다. 위에서 들었던 예시를 다시 가져와 보자. 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 아래와 같다고 하자.

2 3 1 3 5 2 3 4 2 3

최적 페이지 교체 알고리즘은 아래 그림과 같이 총 2번의 페이지 폴트가 발생한다. FIFO 알고리즘에 비하면 페이지 폴트 빈도가 훨씬 낮아진 것을 확인할 수 있다.

					페이지 폴트			페이지 폴트
페이지 참조열	2	3	1	3	5	2	3	4	2	3
프레임	2	2	2	2	2	2	2	2	2	2
		3	3	3	3	3	3	3	3	3
			1	1	5	5	5	4	4	4
보조기억장치					1			5

최적 페이지 교체 알고리즘은 이름 그대로 가장 낮은 페이지 폴트율을 보장하는 알고리즘이다. 그렇기에 최적 페이지 교체 알고리즘은 위 예시뿐 아니라 다른 페이지 참조열을 바탕으로 실험해 보아도 타 페이지 교체 알고리즘에 비해 페이지 폴트 발생 빈도가 가장 낮다. 다만, 최적 페이지 교체 알고리즘은 실제 구현이 어렵다. 최적 페이지 교체 알고리즘은 앞으로 오랫동안 사용되지 않을 페이지를 내보내는 알고리즘이다. 하지만 '앞으로 오랫동안 사용되지 않을 페이지'를 예측하기란 어렵다. 프로세스가 앞으로 메모리 어느 부분을 어떻게 참조할지 미리 알아야 하는데, 이는 현실적으로 불가능에 가깝기 때문이다. 따라서 최적 페이지 교체 알고리즘은 그 자체를 운영체제에서 사용하기보다는, 주로 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용된다. 즉, 최적 페이지 교체 알고리즘을 실행했을 때 발생하는 페이지 폴트 횟수를 페이지 폴트의 하한선으로 간주하고, 최적 페이지 교체 알고리즘에 비해 얼만큼 페이지 폴트 횟수가 발생하느냐를 통해 페이지 교체 알고리즘을 평가하기 위해 사용한다.

 

LRU 페이지 교체 알고리즘(LRU: Least Recently Used Page Replacement Algorithm)

'최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것'이라는 아이디어를 토대로 만들어진 알고리즘이다. 페이지마다 마지막으로 사용한 시간을 토대로 최근에 가장 사용이 적었던 페이지를 교체한다.

					페이지 폴트	페이지 폴트		페이지 폴트
페이지 참조열	2	3	1	3	5	2	3	4	2	3
프레임	2	2	2	2	5	5	5	4	4	4
		3	3	3	3	3	3	3	3	3
			1	1	1	2	2	2	2	2
보조기억장치					2	1		5

스래싱과 프레임 할당

페이지 폴트가 자주 발생하는 이유에 나쁜 페이지 교체 알고리즘만 있는 건 아니다. 프로세스가 사용할 수 있는 프레임 수가 적어도 페이지 폴트는 자주 발생한. (사실 이것이 더 근본적인 이유라고 볼 수 있다.) 반대로 프로세스가 사용할 수 있는 프레임 수가 많으면 일반적으로 페이지 폴트 빈도는 감소한다. 극단적으로 프레임이 무한히 많은 컴퓨터와 프레임이 한 개 있는 컴퓨터를 비교해 보자. 전자는 페이지를 수용할 공간이 넉넉하여 모든 프로세스의 페이지가 메모리에 적재될 수 있기 때문에 페이지 폴트 발생 빈도가 적지만, 후자는 새로운 페이지를 참조할 때마다 페이지 폴트가 발생한다.

이처럼 프레임이 부족하면 CPU는 페이지 폴트가 자주 발생할 수밖에 없다. 실행의 맥이 탁 탁 끊기고, 결과적으로 CPU의 이용률도 떨어진다. CPU가 쉴새 없이 프로세스를 실행해야 컴퓨터 전체의 생산성도 올라갈 텐데, 페이지 교체에 너무 많은 시간을 쏟으면 당연히 성능에도 큰 악영향이 초래된다. 이처럼 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제를 스래싱(thrashing)이라고 한다.

스래싱이 발생하는 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 떄문이다. 가령 프로세스 A를 무리 없이 실행하기 위해서는 최소 열 개의 프레임이 필요한데도 불구하고 프로세스 A가 다섯 개의 프레임만 이용할 수 있ㄷ가면 이 프로세스는 페이지 폴트가 자주 발생한다. 스래싱 발생 위험이 높아진다. 그렇기에 운영체제는 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에 적절한 수만큼 프레임을 할당해 줄 수 있어야 한다.

우선 가장 단순한 형태의 프레임 할당 방식부터 생각해보자. 모든 프로세스에 균등하게 프레임을 제공하는 방식인데, 가령 3개의 프로세스에 총 300개의 프레임을 할당할 수 있다면 각 프로세스에 100개의 프로세스를 할당한다. 이러한 프레임 할당 방식을 균등 할당(equal allocation)이라고 한다.

하지만 이는 그리 권장할 만한 방법이 아니다. 실해오디는 프로세스들의 크기는 각기 다른데, 모두 동일한 프레임 개수를 할당하는 것은 비합리적이다. 이와 반대로 프로세스의 크기가 크면 프레임을 많이 할당하고 프로세스의 크기가 작으면 작게 할당해주는 방식을 비례 할당(proportional allocation)이라고 한다.

하지만 비례 할당 또한 완벽한 방식은 아니다. 프로세스의 크기가 클지라도 막상 실행해 보니 많은 프레임을 필요로 하지 않는 경우도 있다. 반대로 프로세스의 크기가 작아도 실행해 보니 많은 프레임을 필요로 하는 경우도 있다. 즉, 하나의 프로세스가 실제로 얼마나 많은 프레임이 필요할지는 결국 실행해 봐야 아는 경우가 많다. 프로세스를 실행하는 과정에서 배분할 프레임을 결정하는 방식에는 크게 작업 집합 모델(working set moel)을 사용하는 방ㅎ식과 페이지 폴트 빈도(PFF: Page-Fault Frequency)를 사용하는 방식이 있다.

스래싱이 발생하는 이유는 빈번한 페이지 교체 때문이다. 그렇기에 작업 집합 모델 기반 프레임 할당 방식은 '프로세스가 일정 기간 동안 참조한 페이지 집합'을 기억하여 빈번한 페이지 교체를 방지한다. 참조 지역성의 원리에 따라 CPU가 메모리를 참조할 때에는 주로 비슷한 구역을 집중적으로 참조한다. 한 프로세스가 100개의 페이지로 이루어졌다고 해서 100개를 모두 고르게 참조하는 것이 아니라, 특정 시간 동안에는 몇몇 개의 페이지(정확히는 몇 개의 페이지 내 주소들)만을 집중적으로 참조하게 된다.

그렇다면 CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당하면 페이지 교체는 빈번하게 발생하지 않을 것이다. 만약 CPU가 어떤 프로세스를 실행하는 동안 3초에 7개의 페이지를 집중적으로 참조했다면 운영체제는 그 프로세스를 위해 그 순간만큼은 최소 7개의 프레임을 할당하면 된다. 또 만약 CPU가 어떤 프로세스를 실행하는 동안 3초에 20개의 페이지를 집중적으로 참조했다면 운영체제는 그 프로세스를 위해 그 순간만큼은 최소 20개의 프레임을 할당하면 된다.

실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합을 작업 집합(working set)이라고 한다. CPU가 과거에 주로 참조한 페이지를 작업 집합에 포함한다면 운영체제는 작업 집합의 크기만큼만 프레임을 할당해 주면 된다.

페이지 폴트 빈도를 기반으로 한 프레임 할당은 아래의 2개의 가정에서 생겨난 아이디어다.

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

이에 따라 페이지 폴트율에 상한선과 하한선을 정하고, 이 범위 안에서만 프레임을 할당하는 방식이다.

 

15 파일 시스템

---

파일

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

디렉터리

파일들을 일목요연하게 관리하기 위핸 디렉터리(directory)를 이요할 수 있다. 윈도우 운영체제에서는 디렉터리를 폴더(folder)라고 부른다. 옛날 운영체제에서는 하나의 디렉터리만 존재했다. 모든 파일이 하나의 디렉터리 아래에 있었는데 1단계 디렉터리(single-level drectory)라고 부른다. 컴퓨터 용량이 커지다 보니 저장할 수 있는 파일도 많아지고, 1단계 디렉터리로는 많은 파일을 관리하기가 어렵기 때문에 여러 계층을 가진 트리 구조 디렉터리(tree-structed directory)가 생겨났다. 트리 구조 디렉터리는 최상위 디렉터리가 있고 그 아래에 여러 서브 디렉터리(자식 디렉터리)가 있을 수 있다. 서브 디렉터리도 또 다른 서브 디렉터리를 가질 수 있다. 최상위 디렉터리는 흔히 루트 디렉터리(root directory)라고 부르고 슬래시(/)로 표현한다.

그러다 보니 자연스레 생긴 개념이 바로 경로(path)이다. 경로는 디렉터리를 이용해 파일 위치, 나아가 파일 이름을 특정 짓는 정보이다. 모든 파일은 루트 디렉터리에서 자기 자신까지 이르는 고유한 경로를 가지고 있고, 이러한 경로를 절대 경로(absolute path)라고 부른다. 또한 현재 디렉터리부터 시작하는 경로인 상대 경로(relative path)도 있다.

많은 운영체제에서는 디렉터리를 그저 '특별한 형태의 파일'로 간주한다. 즉, 디렉터리도 파일이고, 단지 포함된 정보가 조금 특별할 뿐이다. 파일이 내부에 해당 파일과 관련된 정보를 담고 있다면, 디렉터리는 내부에 해당 디렉터리에 담겨 있는 대상과 관련된 정보를 담고 있다. 그리고 이 정보는 보통 테이블(표) 형태로 구성된다. 

파티셔닝과 포매팅

용량이 큰 저장 장치를 하나 이상의 논리적인 단위로 구획하는 것을 파티셔닝(partitioning)이라고 하고, 파티셔닝 작업을 통해 나누어진 영역 하나하나를 파티션(partition)이라고 한다.

포맷하는 작업, 즉 포매팅(formatting)은 저장 장치를 완전히 삭제하는 것으로 알고 이쓴ㄴ 사람들이 많지만, 사실 이는 완벽하게 정확한 표현이라고 보기 어렵다. 포매팅이란 파일 시스템을 설정하여 어떤 방식으로 저장하고 관리할 것인지를 결정하고, 새로운 데이터를 쓸 준비를 하는 작업을 의미한다. 즉, 어떤 종류의 파일 시스템을 사용할지는 바로 이때 결정난다.

파일 할당 방법

운영체제는 파일과 디렉터리를 블록(block) 단위로 일고 쓴다. 크기가 작은 파일은 적은 수의 블록에 걸쳐 저장될 것이고, 크기가 큰 파일은 여러 블록에 걸쳐 저장된다. 이런 상황에서 파일을 보조기억장치에 할당하는 방법에는 크게 2가지가 있다. 연속 할당과 불연속 할당이다. 그리고 불연속 할당에는 크게 연결 할당, 색인 할당이 있다.

• 연속 할당(contigous allocation) : 가장 단순한 방식이다. 이름 그대로 보조기억장치 내 연속적인 블록에 파일을 할당한다. 연속으로 할당된 파일에 접근하기 위해서는 파일의 첫 번째 블록 주소와 블록 단위의 길이만 알면 된다. 구현은 단순하지만 외부 단편화를 야기해 저장 공간의 낭비를 초래한다.
• 연결 할당(linked allocation) : 각 블록 일부에 다음 블록의 주소를 저장하여 각 블록이 다음 블록을 가리키는 형태로 할당하는 방식이다. 즉, 파일을 이루는 데이터를 연결 리스트로 관리한다. 연결 할당은 불연속 할당의 일종이기에 파일이 여러 블록에 흩어져 저장되어도 무방하다. 연결 할당은 외부 단편화 문제를 해결하지만 이 또한 단점이 있다. 첫째, 반드시 첫 번째 블록부터 하나씩 차례대로 읽어야 하기 때문에 임의 접근(random access) 속도가 매우 느려 성능면에서 상당히 비효율적이다. 둘째, 하드웨어 고장이나 오류 발생 시 해당 블록 이후 블록은 접근할 수 없다.

그래서 오늘날에는 위 내용을 그대로 구현하기보다는 이를 조금 변형하여 사용한다. 대표적으로 FAT 파일 시스템이다.

색인 할당(indexed allocation)은 파일의 모든 블록 주소를 색인 블록(index block)이라는 하나의 블록에 모아 관리하는 방식이다. 임의의 파일에 순차적으로 접근하고 싶다면 색인 블록에 저장된 주소에 차례대로 접근하면 된다. 색인 할당은 연결 할당과는 달리 파일 내 임의의 위치에 접근하기 쉽다. 파일의 i번째 데이터 블록에 접근하고 싶다면 색인 블록의 i번째 항목이 가리키는 블록에 접근하면 되기 때문이다. 색인 블록 안에 파일을 구성하는 데이터 블록 주소가 있으므로 색인 블록만 알면 해당 파일 데이터에 접근할 수 있다. 그렇기에 색인 할당을 사용하는 파일 시스템에서는 디렉터리 엔트리에 파일 이름과 더불어 색인 블록 주소를 명시한다. 색인 할당으로 만든 파일 시스템이 유닉스 파일 시스템이다.

파일 시스템 살펴보기

FAT 파일 시스템

연결 할당의 단점을 보완한 시스템이다. 근본적으로 블록 안에 다음 블록의 주소를 저장하기 때문에 문제가 나타나는데, 각 블록에 포함된 다음 블록의 주소들을 한데 모아 테이블 형태로 관리하면 앞서 언급한 단점들을 상당 부분 해소할 수 있다. 이러한 테이블을 파일 할당 테이블(FAT: File Allocation Table)이라고 한다. FAT 파일 시스템은 버전에 따라 FAT12, FAT16, FAT32가 있으며, FAT 뒤에 오는 숫자는 블록을 표현하는 비트 수를 의미한다. FAT 파일 시스템에서 FAT는 파티션의 앞부분에 만들어진다.

예약 영역

FAT 영역

루트 디렉터리 영역

데이터 영역

유닉스 파일 시스템

색인 할당 기반이고, 유닉스 파일 시스템에서 색인 블록을 i-node(index-node)라고 부른다. i-node에는 파일 속성 정보와 15개의 블록 주소가 저장될 수 있다. 앞서 FAT 파일 시스템에서는 파일 속성 정보가 디렉터리 엔트리에 표현되었다면, 유닉스 파일 시스템에서는 i-node에 표현된다. 유닉스 파일 시스템에는 파일마다 이러한 i-node가 있고, i-node마다 번호가 부여되어 있다. 그리고 i-node들은 다음과 같이 파티션 내 특정 영역에 모여있다. i-node 영역에 i-node들이 있고, 데이터 영역에 디렉터리와 파일이 있다.

예약 영역

i-node 영역

데이터 영역

한 가지 문제는 i-node의 크기가 유한하다는 것이다. 15개의 블록 주소를 저장할 수 있기 때문에 i-node 하나는 15개의 블록을 차지하는 파일까지 가리킬 수 있다. 하지만 블록을 20개, 30개, 그 이상 차지하는 파일도 있을텐데 이 경우 i-node 하나만으로는 파일의 데이터 블록을 모두 가리킬 수 없다. 유닉스 파일 시스템은 이러한 문제를 아래와 같이 해결한다.

첫째, 블록 주소 중 12개는 직접 블록 주소(direct block)를 저장한다. 이것만으로 파일 데이터 블록을 모두 가리킬 수 있다면 여기서 추가적인 작업이 필요하지 않다. 둘째, '첫째' 내용으로 충분하지 않다면 12번째 주소에 단일 간접 블록 주소(single indirect block)를 저장한다. 단일 간접 블록이란 파일 데이터가 저장된 블록이 아닌 파일 데이터를 저장한 블록 주소가 저장된 블록을 의미한다. 셋째, '둘째' 내용으로 충분하지 않다면 14번째 주소에 이중 간접 블록 주소(double indirect block)를 저장한다. 이중 간접 블록이란 데이터 블록 주소를 저장하는 블록 주소가 저장된 블록을 의미한다. 즉, 단일 간접 블록들의 주소를 저장하는 블록이다. 넷째, '셋째' 내용으로 충분하지 않다면 15번째 주소에 삼중 간접 주소(triple indirect block)를 저장한다. 삼중 간접 주소란 이중 간접 블록 주소가 저장된 블록이다. 여기까지 이요하면 웬만한 크기의 파일은 모두 표현할 수 있다.