운영체제(9장~15장) 개념 정리

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

운영체제(9장~15장) 개념 정리

hsb_02 2024. 6. 22. 20:17

9장 운영체제 시작하기

9-1. 운영체제를 알아야 하는 이유

운영체제란

모든 프로그램은 하드웨어를 필요로 함. 계산하는 프로그램은 CPU를, 이미지를 디스크에 저장하는 프로그램은 하드 디스크를 필요로 하는 것 처럼
이때 프로그램 실행에 필요한 요소들을 가리켜 시스템 자원, 혹은 자원이라고 함
1장에서 8장까지 배웠던 CPU, 메모리, 보조기억장치, 입출력장치 등과 같은 컴퓨터 부품들은 모두 자원!
여기서 실행할 프로그램에 필요한 자원을 할당하고, 프로그램이 올바르게 실행되도록 돕는 특별한 프로그램이 바로 운영체제(Operating System)

운영체제는 인터넷 브라우저, 게임과 같은 프로그램임
그렇기 때문에 여느 프로그램과 마찬가지로 메모리에 적재되어야 함
다만, 운영체제는 매우 특별한 프로그램이기 대문에 항상 컴퓨터가 부팅될 대 메모리 내 커널 영역(kernel space)이라는 공간에 따로 적재되어 실행됨
우리가 일반적으로 이용하는 응용 프로그램이 적재되는 영역을 사용자 영역(user space)라고 함
즉, 운영체제는 커널 영역에 적재되어 응용 프로그램과 하드웨어(시스템 자원) 사이에서 사용자 영역에 적재된 응용 프로그램에 필요한 자원을 할당하고, 이들이 올바르게 실행되도록 관리함

9-2. 운영체제의 큰 그림

커널

운영체제는 현존하는 프로그램 중 규모가 가장 큰 프로그램(메모리에 적재) 중 하나
운영체제의 핵심 서비스에는 자원에 접근하고 조작하는 기능, 프로그램이 올바르고 안전하게 실행되게 하는 기능이 있음
이러한 운영체제의 핵심 서비스를 담당하는 부분을 커널(kernel)이라고 함

다만, 운영체제가 제공하는 서비스 중 커널에 포함되지 않는 서비스가 존재하는데 이는 바로 사용자 인터페이스(UI, User Interface)

이중 모드와 시스템 호출

운영체제는 사용자가 실행하는 응용 프로그램이 하드웨어 자원에 직접 접근하는 것을 방지함
운영체제는 응용 프로그램들이 자원에 접근하려고 할 때 오직 자신을 통해서만 접근하도록 하여 자원을 보호, 비유하자면 일종의 문지기 역할
운영체제의 문지기 역할은 이중 모드로써 구현됨.
이는 CPU가 명령어를 실행하는 모드를 크게 사용자 모드와 커널 모드로 구분하는 방식
- 사용자 모드는 운영체제 서비스를 제공받을 수 없는 실행 모드
- 응용 프로그램들은 기본적으로 사용자 모드로 실행됨
- 사용자 모드로 실행 중인 CPU는 입출력 명령어와 같이 하드웨어 자원에 접근하는 명령어 실행 불가
- 반면, 커널 모드는 운영체제 서비스를 제공받을 수 있는 실행 모드
- 즉, 커널 영역의 코드를 실행할 수 있는 모드이며, 운영체제는 커널 모드로 실행됨
요컨대 사용자 모드로 실행되는 프로그램이 자원에 접근하는 운영체제 서비스를 제공받으려면 운영체제에 요청을 보내 커널모드로 전환되어야 함
이때 운영체제 서비스를 제공받기 위한 요청을 시스템 호출(System Call)이라고 함
- 시스템 호출은 소프트웨어 인터럽트임
- 일반적으로 응용 프로그램은 실행 과정에서 운영체제 서비스를 빈번하게 이용함.
- 그 과정에서 빈번하게 시스템 호출을 발생시키고 사용자 모드와 커널 모드를 오가며 실행됨

운영체제의 핵심 서비스

1. 프로세스 관리

일반적으로 하나의 CPU는 한 번에 하나의 프로세스만 실행시킬 수 있기에 CPU는 프로세스들은 조금씩 번갈아 가며 실행
여러 프로세스가 동시에 실행되는 환경에서는 프로세스 동기화가 필수적
프로세스가 꼼짝도 못하고 실행되지 못하는 상황인 교착 상태를 해결해야 함

2. 자원 접근 및 할당

지금까지 배운 자원은 CPU, 메모리, 입출력장치 등이 존재함
이 모든 자원들을 운영체제가 접근하고 조작함으로써 프로세스에 필요한 자원을 할당해 줌

3. 파일 시스템 관리

우리는 컴퓨터를 사용하며 여러 파일을 열고, 생성하고, 삭제함. 그리고 이 파일들을 묶어 디렉터리로 관리함
이러한 파일 시스템도 운영체제가 지원하는 핵심 서비스임

10장 프로세스와 스레드

10-1. 프로세스 개요

프로그램은 실행되기 전까지 그저 보조기억장치에 있는 데이터 덩어리, 보조기억장치에 저장된 프로그램을 메모리에 적재하고 실행하는 순간 그 프로그램은 프로세스가 됨

이 과정을 프로세스를 생성한다라고 표현함

사용자가 볼 수 있는 공간에서 실행되는 프로세스를 포그라운드 프로세스

사용자가 보지 못하는 뒤편에서 실행되는 프로세스를 백그라운드 프로세스라고 함(유닉스에서는 데몬, 윈도우에서는 서비스라고 부름)

프로세스 제어 블록

운영체제는 빠르게 번갈아 수행되는 프로세스의 실행 순서를 관리하고, 프로세스에 CPU를 비롯한 자원을 배분함
이를 위해 운영체제는 프로세스 제어 블록(PCB)를 이용함
PCB는 프로세스를 식별하기 위해 꼭 필요한 정보를 저장하는 자료 구조.(마치 상품에 달린 태그와 같음)
PCB는 메모리의 커널 영역에 생성됨
PCB에는 다음과 같은 정보들이 담김
- 프로세스 ID(PID): 특정 프로세스를 식별하기 위해 부여하는 고유한 번호
- 레지스터 값: 해당 프로세스가 실행하며 사용했던 프로그램 카운터를 비롯한 레지스터 값들이 담김
- 프로세스 상태: 현재 프로세스가 어떤 상태인지에 대한 정보
- CPU 스케줄링 정보: 프로세스가 언제, 어떤 순서로 CPU를 할당받을지에 대한 정보
- 메모리 관리 정보: 프로세스가 메모리의 어느 주소에 저장되어 있는지에 대한 정보
- 사용한 파일과 입출력장치 목록: 어떤 입출력장치가 이 프로세스에 할당되었는지, 어떤 파일들을 열었는지에 대한 정보

문맥 교환

하나의 프로세스 수행을 재개하기 위해 기억해야 할 정보를 문맥(context)이라고 함
하나의 프로세스 문맥은 해당 프로세스의 PCB에 표현되어 있음
프로세스가 CPU를 사용할 수 있는 시간이 다 되거나 예기치 못한 상황이 발생하여 인터럽트가 발생하면 운영체제는 해당 프로세스의 PCB에 문맥을 백업
그리고 뒤이어 실행할 프로세스의 문맥을 복구하며 자연스럽게 실행되는 프로세스가 바뀜
즉, 기존 프로세스의 문맥을 자신의 PCB에 백업하고, 새로운 프로세스를 실행하기 위해 문맥을 새로운 프로세스의 PCB로부터 복구하여 새로운 프로세스를 실행하는 것을 문맥 교환(context switch)이라고 함

프로세스의 메모리 영역

프로세스가 생성되면 커널 영역에는 PCB가 생성되며, 사용자 영역에는 코드 영역, 데이터 영역, 힙 영역, 스택 영역으로 나뉘어 저장됨
- 코드 영역: 실행할 수 있는 코드, 즉 기계어로 이루어진 명령어가 저장되는 공간(정적 할당 영역)
- 데이터 영역: 프로그램이 실행되는 동안 유지할 데이터가 저장되는 공간(전역 변수) (정적 할당 영역)
- 힙 영역: 프로그래머가 직접 할당할 수 있는 저장 공간, 할당한 이후에는 언젠가는 해당 공간을 반환해야 함 (동적 할당 영역, 메모리의 낮은 주소에서 높은 주소로 할당)
- 스택 영역: 데이터를 일시적으로 저장하는 공간(매개 변수, 지역변수 등) (동적 할당 영역, 메모리의 높은 주소에서 낮은 주소로 할당)

10-2. 프로세스 상태와 계층 구조

프로세스 상태

생성(new) 상태: 프로세스가 생성 중인 상태
준비(ready) 상태: CPU를 할당받아 실행 중인 상태
대기(wait) 상태: 실행 도중 입출력 장치의 인터럽트를 받아, 입출력장치의 작업을 기다리는 상태
종료(terminated) 상태: 프로세스가 종료된 상태

위와 같은 도표를 프로세스 상태 다이어그램이라고 하며, 운영체제는 이 상태를 PCB에 기록하며 프로세스들을 관리함

프로세스 계층 구조

프로세스는 실행 도중 시스템 호출을 통해 다른 프로세스를 생성할 수 있음
이때 새 프로세스를 생성한 프로세스를 부모 프로세스, 부모 프로세스에 의해 생성된 프로세스를 자식 프로세스라고 함
이 과정은 트리 구조를 띄며, 이를 프로세스 계층 구조라고 함

프로세스 생성 기법

부모 프로세스를 통해 생성된 자식 프로세스들은 복제(fork)와 옷 갈아입기(exec)를 통해 실행됨
부모 프로세스는 시스템 호출 중 하나인 fork()를 통해 자신의 복사본을 자식 프로세스로 생성
자식 프로세스는 exec()를 통해 자신의 메모리 공간을 다른 프로그램으로 교체(옷 갈아입기)
fork()는 자신과 똑같은 프로세스를 생성하나, exec()를 호출하면 코드 영역과 데이터 영역의 내용이 실행할 프로그램의 내용으로 바뀌고, 나머지 영역은 초기화됨

10-3. 스레드

스레드란 실행의 단위임, 조금 더 정확하게 표현하면 스레드란 프로세스를 구성하는 실행의 단위임

이는 소프트웨어적 스레드로도 불림

프로세스와 스레드

실행의 흐름 단위가 하나라는 점에서 실행되는 프로세스들은 단일 스레드 프로세스
스레드라는 개념이 등장하며 하나의 프로세스가 한 번에 여러 일을 동시에 처리할 수 있게된 것이 멀티스레드 프로세스
스레드는 프로세스를 구성하는 실행 단위라고 볼 수 있음
스레드는 프로세스 내에서 각기 다른 스레드 ID, 프로그램 카운터 값을 비롯한 레지스터 값, 스택으로 구성됨
여기서 중요한 점은 프로세스의 스레드들은 실행에 필요한 최소한의 정보(프로그램 카운터를 포함한 레지스터, 스택)만을 유지한 채 나머지 프로세스 자원들을 공유하며 실행

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

여러 프로세스를 동시에 실행하는 것을 멀티프로세스
여러 스레드로 프로세스를 동시에 실행하는 것을 멀티스레드라고 함
프로세스끼리는 기본적으로 자원을 공유하지 않으나, 스레드들끼리는 같은 프로세스 내의 자원을 공유함
프로세스는 fork()를 통해 멀티프로세스 구조를 형성하나 이는 같은 프로그램을 실행하기 위해 메모리에 동일한 내용들이 중복해서 존재한다는 낭비가 있음
다만, 프로세스는 하나의 프로세스에 문제가 생겨도 다른 프로세스에는 지장이 적거나 없음
스레드는 프로세스의 자원을 공유하기 때문에 서로 협력과 통신에 유리
다만, 하나의 스레드에 문제가 생기면 프로세스 전체에 문제가 생길 수 있음

11장 CPU 스케줄링

11-1. CPU 스케줄링 개요

모든 프로세스는 CPU를 필요로 하고 모든 프로세스는 먼저 CPU를 사용하고 싶어함

운영체제는 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 기다리게 할지를 결정

이렇게 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 CPU 스케줄링이라고 함

프로세스 우선순위

대부분의 프로세스들은 CPU와 입출력장치를 모두 사용하며 실행
달리 말하면 프로세스는 실행 상태와 대기 상태를 반복하며 실행
CPU 작업이 많은 프로세스를 CPU 집중 프로세스, 입출력 작업이 많은 프로세스를 입출력 집중 프로세스라고 함
CPU를 이용하는 작업을 CPU 버스트, 입출력장치를 기다리는 작업을 입출력 버스트라고 함
CPU 집중 프로세스와 입출력 집중 프로세스가 동시에 CPU 자원을 요구했을 때, 입출력 집중 프로세스를 빨리 실행시키는 것이 더 효율적임 -> 입출력 작업을 완료하기 전까지 입출력 집중 프로세스는 어차피 대기 상태이기 때문
운영체제는 프로세스마다 우선순위를 부여하며, 프로세스의 중요도에 맞게 프로세스가 CPU를 이용하도록 함
운영체제는 각 프로세스의 PCB에 우선순위를 명시

스케줄링 큐

CPU를 사용할 다음 프로세스를 찾기 위해 운영체제가 모든 프로세스의 PCB를 뒤적거리는 것은 비효율적
운영체제는 프로세스들에 줄을 서서 기다릴 것을 요구, 이 줄을 스케줄링 큐로 구현하고 관리함
운영체제가 관리하는 대부분의 자원은 큐로 관리되며, 대표적인 큐로 준비 큐와 대기 큐가 있음
준비 큐는 CPU를 이용하고 싶은 프로세스들이 서는 줄을 의미, 대기 큐는 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄을 의미

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

선점형 스케줄링은 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식
비선점형 스케줄링은 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식
선점형 스케줄링은 어느 한 프로세스의 자원 독점을 막고 프로세스에 골고루 자원을 배분할 수 있다는 장점이 있지만, 그만큼 문맥 교환 과정에서 오버헤드가 발생할 수 있음
비선점형 스케줄링은 문맥 교환에서 발생하는 오버헤드는 적으나, 하나의 프로세스가 자원을 사용 중이라면 무작정 기다리는 수 밖에 없음

11-2. CPU 스케줄링 알고리즘

스케줄링 알고리즘의 종류

선입 선처리 스케줄링

FCFS(First Come First Served) 스케줄링이라고도 불림
준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식
프로세스들이 기다리는 시간이 매우 길어질 수 있음
실행시간이 매우 짧은 프로세스가 먼저 도착한 긴 시간의 프로세스들을 기다리는 현상을 호위 효과(convoy effect)라고 함

최단 작업 우선 스케줄링

SJF(Shortest Job First) 스케줄링이라고도 불림
준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식
기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될수도 있음

라운드 로빈 스케줄링

라운드 로빈(Round Robin) 스케줄링은 선입 선처리(FCFS) 스케줄링에 타임 슬라이스 개념이 더해진 스케줄링 방식
타임 슬라이스란 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
라운드 로빈 스케줄링은 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링

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

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

우선순위 스케줄링

프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘
SJF(작업 시간이 짧은 프로세스 우선)와 SRT(남은 시간이 짧은 프로세스 우선)는 넓은 의미에서 우선순위 스케줄링의 일종으로 볼 수 있음
다만 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있음.
이를 기아(starvation) 현상이라고 함, 우선순위가 높은 프로세스만 먼저 실행되니 우선순위가 낮은 프로세스의 실행은 계속 뒤로 밀리는 것
기아 현상을 방지하기 위한 기법으로는 에이징(aging)이 있으며, 이는 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

다단계 큐 스케줄링

우선순위 스케줄링의 발전된 형태이며, 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 비었다면 그 다음 우선순위 큐에 있는 프로세스들을 처리
다만 이런 방식대로라면 우선순위가 낮은 프로세스는 계속 연기될 여지가 있음, 즉 기아 현상 발생

다단계 피드백 큐 스케줄링

다단계 큐 스케줄링의 발전된 형태
프로세스들이 큐 사이를 이동할 수 있게 된 형태
우선순위가 높은 큐에 삽입된 프로세스는 타임 슬라이스 동안 실행되며, 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행
낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법이 적용되며 기아 현상을 예방
구현이 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘

12장 프로세스 동기화

12-1. 동기화란

동기화의 의미

협력하여 실행되는 프로세스들은 실행 순서와 자원의 일관성을 보장해야 하기에 반드시 동기화(synchronization)되어야 함
프로세스 동기화란 프로세스들 사이의 수행 시기를 맞추는 것을 의미하며 크게 두 가지를 일컫음
- 실행 순서 제어: 프로세스를 올바른 순서대로 실행
- 상호 배제: 동시에 접근해서는 안되는 자원에 하나의 프로세스만 접근하게 하기

생산자와 소비자 문제

상호 배제를 위한 동기화에 대해서 고전적이고 유명한 문제
물건을 계속해서 생산하는 프로세스인 생산자와 물건을 계속해서 소비하는 프로세스인 소비자로 이루어져 있음
생산자와 소비자는 총합이라는 데이터를 공유함
생산자는 버퍼에 물건을 넣은 후, 물건의 총합을 1 증가시키고, 소비자는 버퍼에 물건을 빼낸 후 물건의 총합을 1 감소시킴

위와 같은 상태에서 생산자를 100000번, 소비자를 100000번 실행했을 때의 결과는 10이 아닌 다른 수들이 결과로 나옴
이러한 이유는 동시에 접근해서는 안되는 자원(총합)에 동시에 접근했기에 발생한 문제임

공유 자원과 임계 구역

생산자 소비자 문제에서 총합이라는 공동이 자원이 존재했었음
이러한 자원을 공유 자원(shared resource)라고 하며, 전역 변수가 될 수도, 파일이 될 수도, 입출력장치, 보조기억장치가 될 수도 있음
공유 자원 중에는 두 개 이상의 프로세스를 동시에 실행하면 문제가 발생하는 자원이 있으며, 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역을 임계 구역(critical section)이라고 함
임계 구역은 두 개 이상의 프로세스가 동시에 실행되서는 안되나, 잘못된 실행으로 인해 여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행하여 발생하는 문제를 레이스 컨디션(race condition)이라고 함

상호배제를 위한 동기화를 위해 지켜져야 할 세 가지 원칙

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

12-2. 동기화 기법

뮤텍스 락 (상호 배제를 위한 동기화)

임계 구역 문제와 이를 해결하기 위한 동기화를 옷 가게에서 탈의실을 이용하는 것에 비유
탈의실엔 손님 한명만 들어갈 수 있음. 탈의실에 들어간 손님은 자물쇠를 걸 수 있음
이 때 손님은 프로세스, 탈의실은 임계 구역이라고 할 수 있음
자물쇠 기능을 코드로 구현한 것이 바로 뮤텍스 락(Mutex lock, MUTual EXclusion lock)
뮤텍스 락은 동시에 접근해서는 안되는 자원에 동시에 접근하지 않도록 만드는 도구, 다시 말해 상호 배제를 위한 동기화 도구임
뮤텍스 락은 자물쇠 역할을 하는 하나의 전역 변수(lock)와 두 개의 함수(acquire, release)로 구현

acquire는 프로세스가 임계 구역에 진입하기 전에 호출하는 함수이며, 임계 구역이 잠겨 있다면 열릴 때까지(lock이 false가 될 때까지) 임계 구역을 반복적으로 확인하고, 임계 구역이 열려 있다면 임계 구역을 잠그는 함수
release 함수는 임계 구역에서의 작업이 끝나고 호출하는 함수. 현재 잠긴 임계 구역을 열어주는 함수임
acquire 함수의 while 부분 같이 쉴 새 없이 반복(while)하며 확인해 보는 대기 방식을 바쁜 대기(busy wait)이라 함

세마포(상호 배제를 위한 동기화)

세마포(semaphore)는 뮤텍스 락과 비슷하지만, 조금 더 일반화된 방식의 동기화 도구
위의 그림처럼 세마포는 공유 자원이 여러 개 있는 상황에서도 적용이 가능한 동기화 도구임
세마포는 임계 구역에 진입할 수 있는 프로세스의 개수를 나타내는 전역 변수(S)와 두 함수(wait, signal)를 통해 구현
뮤텍스 락을 사용할 때 임계 구역 진입 전후로 acquire()와 release()를 호출했듯이 세마포도 임계 구역 진입 전후로 wait()과 signal()을 호출함

가령 세 개의 프로세스 P1, P2, P3가 두 개의 공유 자원에 P1, P2, P3 순서로 접근한다고 가정했을 때 다음의 순서로 실행됨

프로세스 P1 wait 호출, S는 현재 2이므로 1 감소시키고 임계 구역 진입
프로세스 P2 wait 호출, S는 현재 1이므로 1 감소시키고 임계 구역 진입
프로세스 P3 wait 호출, S는 현재 0이므로 무한히 반복하며 S 확인
프로세스 P1 임계 구역 작업 종료, signal() 호출하며 S를 1 증가
프로세스 P3에서 S가 1이 됨을 확인, S는 현재 1이므로 1 감소시키고 임계 구역 진입

하지만 여기서도 뮤텍스 락에서도 해당되는 문제인 바쁜 대기가 존재함

P3은 P1이 끝나기 전까지 한없이 무한정 기다리는 바쁜 대기 모드에 돌입했음

그래서 실제로 세마포는 위의 wait과 signal 함수를 업그레이드 한 새로운 방법을 사용함

wait 함수는 사용할 수 있는 자원이 없을 경우 해당 프로세스를 대기 상태로 만들고, 그 프로세스의 PCB를 세마포를 위한 대기 큐에 집어넣음

다른 프로세스가 signal을 호출할 경우 signal 함수는 대기 중인 프로세스를 대기 큐에서 제거하고, 프로세스 상태를 준비 상태로 변경한 뒤 준비 큐로 옮김

이번에도 똑같이 세 개의 프로세스 P1, P2, P3가 두 개의 공유 자원에 P1, P2, P3 순서로 접근한다고 가정

프로세스 P1 wait 호출, S를1 감소시키면 1이므로 임계 구역 진입
프로세스 P2 wait 호출, S를1 감소시키면 0이므로 임계 구역 진입
프로세스 P3 wait 호출, S를1 감소시키면 S는 -1이므로 본인의 PCB를 대기 큐에 넣고 대기 상태로 전환
프로세스 P1 임계 구역 작업 종료, signal() 호출하며 S를 1 증가하면 0이므로 대기 상태였던 P3을 대기 큐에서 꺼내 준비 큐로 옮김
깨어난 프로세스 P3 임계 구역 진입
프로세스 P2 임계 구역 작업 종료, signal() 호출, S를 1 증가시켜 1
프로세스 P3 임계 구역 작업 종료, signal() 호출, S를 1 증가시켜 2

세마포(실행 순서 제어를 위한 동기화)

세마포를 이용해 프로세스의 순서를 제어하는 방법은 간단함
세마포의 변수 S를 0으로 두고 먼저 실행할 프로세스(A) 뒤에 signal 함수, 다음에 실행할 프로세스(B) 앞에 wait 함수를 붙이면 됨
이렇게 설정할 경우 아무리 B가 먼저 실행된다 하더라도 실행 즉시 wait 함수를 만나며 대기 상태에 돌입하고 A가 임계 구역에 진입 후 signal을 통해 신호를 줘야만 그 후에 B가 임계 구역에 진입할 수 있게 됨
즉, A이 먼저 실행되든 B가 먼저 실행되든 반드시 A, B 순서대로 실행

모니터

뮤텍스 락과 세마포의 단점 중 하나로는 매번 임계 구역에 앞뒤로 일일이 함수를 명시해야 하는 것임.
이는 아래와 같은 잘못된 코드로 인해 예기치 못한 결과를 얻게 하기도 함

이에 최근에 등장한 동기화 도구가 모니터(monitor)

모니터는 공유자원과 공유 자원에 접근하기 위한 인터페이스(통로)를 묶어 관리하며, 프로세스는 반드시 인터페이스를 통해서만 공유 자원에 접근하도록 함
이를 위해 모니터를 통해 공유 자원에 접근하고자 하는 프로세스를 큐에 삽입하고, 큐에 삽입된 순서대로 하나씩 공유 자원을 이용하도록 함
즉, 큐는 상호 배제를 위한 큐임

위의 그림은 조건 변수(wait, signal)를 사용한 모니터, 조건 변수는 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수
조건 변수에 대한 큐는 실행 순서를 위한 큐임

13장 교착 상태

13-1. 교착 상태란

운영체제의 핵심 서비스 중 하나인 프로세스 관리

일반적으로 하나의 CPU는 한 번에 하나의 프로세스만 실행시킬 수 있기에 CPU는 프로세스들은 조금씩 번갈아 가며 실행
여러 프로세스가 동시에 실행되는 환경에서는 프로세스 동기화가 필수적
프로세스가 꼼짝도 못하고 실행되지 못하는 상황인 교착 상태를 해결해야 함

교착 상태란 두 개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다리는 형태임

식사하는 철학자 문제

언뜻 보면 위 순서에는 아무런 문제가 없어 보이나 모든 철학자가 동시에 포크를 집어 식사를 시작하면, 어떤 철학자도 식사를 할 수 없고 영원히 생각만 하는 상황이 발생함
이렇게 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 교착 상태(deadlock)이라고 함
철학자는 프로세스 혹은 스레드, 포크는 자원, 생각하는 행위는 자원을 기다리는 것
또한 포크는 한 번에 하나의 프로세스 혹은 스레드만(철학자) 접근할 수 있으니 임계 구역이라고도 볼 수 있음
교착 상태를 해결하기 위해서는
첫째, 교착 상태가 발생했을 때의 상황을 정확히 표현해야 함
둘째, 교착 상태가 일어나는 근본적인 이유에 대해 알아야 함
교착 상태가 발생했을 때의 상황을 한 눈에 보기 쉽게 그래프로 표현하는 방법 또한 존재함(자원 할당 그래프)

자원 할당 그래프

자원 할당 그래프는 아래와 같은 규칙으로 그려짐
첫째, 프로세스는 원으로, 자원의 종류는 사각형으로 표현
둘째, 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
셋째, 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시
넷째, 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원을 향해 화살표를 표시
아래의 그림은 식사하는 철학자 문제를 자원 할당 그래프로 표현한 것

교착 상태가 발생하는 상황은 자원 할당 그래프가 원의 형태를 띄고 있음
이제 교착 상태가 일어나는 근본적인 이유를 알아볼 차례(교착 상태 발생 조건)

교착 상태 발생 조건

상호 배제(mutual exclusion)

교착 상태가 발생한 근본적인 원인은 해당 자원을 한 번에 하나의 프로세스만 이용 가능했기 때문임
식사하는 철학자 문제에서 하나의 포크를 여러 명이 동시에 사용할 수 있었다면 교착 상태는 발생하지 않았음
한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때, 즉 상호 배제 상황에서 교착 상태가 발생할 수 있음

점유와 대기(hold and wait)

식사하는 철학자 문제에서 큰 문제는 철학자들이 왼쪽 포크를 들고(점유) 다른 철학자의 포크를 기다렸었음
프로세스도 마찬가지로 어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다린다면 교착 상태가 발생할 수 있음

비선점(nonpreemptive)

만일 철학자들 중 누군가가 다른 철학자의 포크를 강제로 빼앗을 수 있었다면 교착 상태는 발생하지 않았음
프로세스가 자원을 비선점하고 있었기 때문에 교착 상태가 발생한 것

원형 대기(circular wait)

프로세스들과 프로세스 요청 및 할당받은 자원이 원의 형태를 이루면 교착 상태가 발생함

13-2. 교착 상태 해결 방법

교착 상태를 해결하는 방법에는 크게 예방, 회피, 검출 후 회복이 존재함

교착 상태 예방

자원의 상호 배제를 없앨 경우

모든 자원을 공유 가능하게 만든다는 말과 같음
다만 이론적으로는 교착 상태를 없앨수는 있지만, 현실적으로 모든 자원의 상호 배제를 없애기는 어려움

점유와 대기를 없앨 경우

이는 철학자들로 하여금 한 손에 포크를 들고 다른 포크를 기다리지 못하게 금지하는 것과 같음
점유와 대기를 없애면 운영체제는 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식(원자성?) 방식으로 배분
이 방식도 이론적으로는 교착 상태를 해결할 수 있음
단점으로는 자원의 활용률이 낮아질 수 있음
점유와 대기를 금지하면 한 프로세스에 필요한 자원들을 몰아주고, 그 다음에 다른 프로세스에 필요한 자원들을 몰아줌
이는 당장 자원이 필요해도 기다릴 수 밖에 없는 프로세스와 사요되지 않으면서 오랫동안 할당되는 자원을 다수 양산하기 때문에 자원의 활용률이 낮아짐

비선점 조건을 없앨 경우

이 방식은 선점하여 사용할 수 있는 일부 자원에 대해서는 효과적
가령 CPU는 프로세스들이 선점할 수 있는 대표적인 자원(작업이 모두 끝나지 않았어도 다른 프로세스가 할당받아 사용 가능)
하지만 모든 자원이 선점 가능한 것은 아님
예를 들어 한 프로세스가 프린터를 이용하는 도중 다른 프로세스가 프린터 자원을 빼앗아 사용하는 경우는 말이 되지 않음
즉, 비선점 조건을 없애는 경우는 범용성이 떨어지는 방법임

원형 대기 조건을 없앨 경우

이 방식은 매우 간단함. 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면됨

예를 들어, 식사하는 철학자 문제에서 모든 포크에 1번부터 5번까지 번호를 붙이고, 철학자들로 하여금 번호가 낮은 포크에서 높은 포크 순으로 집어들게 한다면 원형 대기는 발생하지 않음
하지만 역시 단점은 존재함. 모든 자원에 번호를 붙이는 일이란 간단한 작업이 아니기 때문

교착 상태를 사전에 방지하는 예방 방식은 교착 상태가 발생하지 않음을 보장할 수는 있지만 여러 부작용이 따름

교착 상태 회피

교착 상태가 발생하지 않을 정도로만 조심 조심 자원을 할당하는 방식
프로세스들에 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분하는 방법이 교착 상태 회피
모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태를 안정 상태, 교착 상태가 발생할 수도 있는 상황을 불완전 상태라고 부름
안전 순서열은 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미
안전 순서열대로 프로세스들에 자원을 배분하여 교착 상태가 발생하지 않는 상태를 안전 상태라고 함
반면 불안전 상태는 안전 순서열이 없는 상황이며, 시스템이 불안전 상태에 놓이면 교착 상태가 발생할 수 있는 위험이 존재함

교착 상태 검출 후 회복(선점을 통한 회복, 프로세스 강제 종료를 통한 회복)

교착 상태 예방과 회피는 교착 상태 발생을 막기 위한 노력임
교착 상태 검출 후 회복은 교착 상태 발생을 인정하고 사후에 조치하는 방식
선점을 통한 회복은 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식임. 다시말해 교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당하는 방식
프로세스 강제 종료를 통한 회복은 가장 간단한 방법
교착 상태에 놓인 프로세스를 모두 강종할 수도 있고, 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료할 수도 있음
전자는 한 방에 교착 상태를 해결하나 많은 프로세스들이 작업 내역을 잃게 될 가능성이 있고
후자는 작업 내역을 잃는 프로세스를 줄일 수 있으나 교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드를 야기함

타조 알고리즘

교착 상태를 아예 무시하는 방법
드물게 발생하는 잠재적 문제를 무시로 대처하는 방식

14장 가상 메모리

14-1. 연속 메모리 할당

15장 파일 시스템

15-1. 파일과 디렉터리

저작자표시 비영리 변경금지