이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

아래는 모두 프로세스를 예로 들었지만 스레드에서도 똑같이 적용된다.

교착 상태가 발생할 조건에는 아래와 같이 네 가지가 있다.

아래의 조건 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않지만, 아래 조건이 모두 만족될 때 교착 상태가 발생할 가능성이 생긴다.

• 상호 배제(mutual exclusion) : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
• 점유와 대기(hold and wait) : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
• 비선점(nonpreemptive) : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
• 원형 대기(circular wait) : 자원 할당 그래프를 그렸을 때, 프로세스들이 원의 형태로 자원을 대기하는 상태

운영체제는 아래의 방법으로 교착 상태를 해결한다.

• 예방 : 애초에 교착 상태가 일어나지 않도록 교착 상태 발생 조건에 부합하지 않게 자원을 분배
• 회피 : 교착 상태가 발생하지 않을 정도로 조금씩 자원을 할당하다가 교착 상태의 위험이 있으면 자원을 할당을 멈춤
• 검출 후 회복 : 자원을 제약 없이 할당하다가 교착 상태가 검출되면, 교착 상태를 회복

교착 상태 예방

애초에 교착 상태가 발생하지 않도록, 교착 상태 발생조건(상호배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 없애는 것이다.

상호 배제를 없애기

• 모든 자원을 공유 가능하게 만든다
• 상호 배제를 없애면 동기화를 할 때 큰 문제가 될 수 있다.
• 현실적으로 불가능

점유와 대기를 없애기

• 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분
• 당장 자원이 필요해도 기다릴 수밖에 없는 프로세스와 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산하기 때문에 자원의 활용률이 낮아진다.
• 자원을 많이 필요로 하는 프로세스가 무한정 기다리게 되므로 기아 현상을 야기할 우려가 있다.

비선점 조건을 없애기(선점형으로 변환)

• 선점이 가능한 자원(CPU 등)에 한에 효과적
• 선점이 불가능한 자원(프린터 등)은 불가능
• 범용성이 떨어지는 방법

원형 대기 조건을 없애기

모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 원형 대기는 발생하지 않는다.

• 앞선 세 방식에 비해서 비교적 현실적이다.
• 컴퓨터 시스템 내에 존재하는 수많은 자원에 번호를 붙이는 것이 쉽지 않다.
• 각 자원에 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 달라진다.

위 그림은 교착 상태의 대표적인 예시인 식사하는 철학자 문제이다.

식사하는 철학자 문제에서 모든 포크에 1번부터 5번까지 번호를 붙이고, 철학자들로 하여금 번호가 낮은 포크에서 높은 포크 순으로 집어 들게 한다면 원형 대기는 발생하지 않는다.

왜냐하면 5번 포크를 집어들고 1번 포크를 집어들 수 없기 때문이다.

이는 마치 철학자들이 원형 식탁이 아닌 사각형 식탁에서 일렬로 앉아 식사를 하는 상황과 유사하다.

교착 상태 회피

• 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주
• 교착 상태가 발생하지 않을 만큼만 자원을 할당

교착 상태 회피에 대해 깊이 알려면 아래의 용어를 알아야 한다.

• 안전 순서열(safe seqnence) : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
• 안전 상태(safe state) : 교착 상태 없이 프로세스가 자원을 할당받고 종료될 수 있는 상태, 안전 순서열이 있는 상태
• 불안전 상태(unsafe state) : 교착 상태가 발생할 수도 있는 상태, 안전 순서열이 없는 상태

예를 들어 A, B, C 프로세스가 동시에 운영체제에 자원을 요청한 상황에서 B -> A -> C 순서로 자원을 할당하면 교착 상태가 발생하지 않는다고 가정하면 B -> A -> C가 안전 순서열이 된다.

안전 순서열이 있는 상태를 안전 상태이고, 없는 상태가 불완전 상태이다.

운영체제는 교착 상태를 회피하기 위해 시스템 상태가 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당한다.

즉, 교착 상태 회피 방식은 항시 안전 상태를 유지하도록 자원을 할당하는 방식이다.

교착 상태 회피 예제

• 컴퓨터 시스템에 총 12개의 자원이 있다고 가정
• 프로세스 P1, P2, P3가 각각 5개, 2개, 2개의 자원을 할당받아 실행 중이라 가정
• 프로세스 P1, P2, P3는 각각 최대 10개, 4개, 9개 자원을 요구할 수 있다고 가정

프로세스와 스레드는 우선 자원을 운영체제에게 요청하고, 운영체제로부터 자원을 할당받아 사용하고, 자원 사용이 끝나면 자원을 반환한다.

안전 상태

이 상태는 안전 상태이다. P2 -> P1 -> P3이라는 안전 순서열이 있기 때문이다.

왜냐하면 각 프로세스들이 최대로 자원을 요구한 최악의 상황이라면 시나리오는 아래와 같다.

1. 이미 자원 2개를 점유하고 있던 P2는 남은 자원에서 2개를 추가적으로 할당 받아 작업을 끝내고 쓰던 모든 자원을 반환한다.
2. 이미 자원을 5개 점유하고 있던 P1은 남은 자원에서 5개를 추가적으로 할당 받아 작업을 끝내고 쓰던 모든 자원을 반환한다.
3. 이미 자원을 2개 점유하고 있던 P3는 남은 자원에서 7개를 추가적으로 할당 받아 작업을 끝내고 쓰던 모든 자원을 반환한다.

불안전 상태

이번에는 P3가 2개의 자원을 쓰고있는 상태가 아니라 3개의 자원을 쓰고 있는 상태라 가정

이는 불안전 상태이다. 즉, 안전 순서열이 없으므로 교착 상태가 일어날 수 있다.

예를 들어, 최악의 상황인 각 프로세스가 최대로 자원을 요구하면 시나리오는 아래와 같다.

1. 이미 자원 2개를 점유하고 있던 P2는 남은 자원에서 2개를 추가적으로 할당받아 작업을 끝내고 쓰던 모든 자원을 반환한다.
2. 이미 자원을 5개 점유하고 있던 P1은 남은 자원에서 5개를 추가적으로 할당받고 싶지만, 남은 자원이 4개이므로 작업을 완료할 수 없게 된다.
3. 이미 자원을 3개 점유하고 있던 P3은 남은 자원에서 6개를 추가적으로 할당받고 싶지만, 남은 자원이 4개이므로 작업을 완료할 수 없게 된다.
4. 교착 상태에 빠진다.

교착 상태 검출 후 회복

• 교착 상태의 발생을 인정하고 사후에 조치하는 방식
• 프로세스가 자원을 요구하면 일단 할당, 교착 상태가 검출되면 회복
• 회복에는 선점을 통한 회복과 프로세스 강제 종료를 통한 회복이 있다.

선점을 통한 회복

• 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
• 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당

프로세스 강제 종료를 통한 회복

프로세스 강제 종료를 통한 회복에는 아래의 두 가지 방법이 있다.

• 교착 상태에 놓인 프로세스를 모두 강제 종료하는 방법(작업 내역을 잃을 위험)
• 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료(교착 상태가 해결되었는지 확인하는 과정에서 오버헤드 발생)

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

교착 상태(Deadlock)

교착 상태의 정의 : 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상

아래는 모두 프로세스를 예로 들었지만 스레드에서도 똑같이 적용된다.

예를 들어, 아래와 같은 상황을 교착 상태라고 말할 수 있다.

• 게임 프로세스는 자원 A를 점유한 채 웹 브라우저 프로세스가 점유하고 있는 자원 B의 사용을 기다림
• 웹 브라우저 프로세스는 자원 B를 점유한 채 게임 프로세스의 자원 A 사용이 끝나길 기다림

또 다른 교착상태의 예를 들면 식사하는 철학자 문제가 있다.

식사하는 철학자 문제에서 한두 명의 철학자가 식사를 할 때는 문제가 되지 않지만, 모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없다.(교착 상태)

자원 할당 그래프(resource-allocation graph)

교착 상태는 자원 할당 그래프를 통해 단순하게 표현할 수 있다.

자원 할당 그래프는 어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는 지를 표현하는 간단한 그래프이다.

자원 할당 그래프는 아래와 같은 규칙으로 그려진다.

1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현
2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
3. 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원 프로세스를 향해 화살표를 표시
4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시

자원할당 그래프 예제

• SSD자원은 세 개, CPU 자원은 두 개, 프린터는 하나
• 프로세스 A는 SSD를 할당받아 사용 중, 프로세스 B와 C는 CPU를 할당받아 사용 중, 프로세스 D는 프린터를 사용 중
• 프로세스 E는 프린터 자원을, 프로세스 F는 CPU 자원의 할당을 기다리는 중

교착 상태 발생 조건

교착 상태가 발생할 조건에는 아래와 같이 네 가지가 있다.

아래의 조건 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않지만, 아래 조건이 모두 만족될 때 교착 상태가 발생할 가능성이 생긴다.

• 상호 배제(mutual exclusion) : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
• 점유와 대기(hold and wait) : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
• 비선점(nonpreemptive) : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
• 원형 대기(circular wait) : 자원 할당 그래프를 그렸을 때, 프로세스들이 원의 형태로 자원을 대기하는 상태

위에서 교착 상태 예제로 들었던 상태들을 자원 할당 그래프로 나타내면 아래와 같다.

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

동시다발적으로 실행되는 프로세스와 스레드들은 공동의 목적을 수행하기 위해 서로 협력하며 영향을 주고받기도 한다.

이렇게 협력하여 실행되는 프로세스와 스레드들은 실행 순서와 자원의 일관성을 보장해야 하기에 반드시 동기화가 되어야 한다.

프로세스 동기화란 프로세스 사이에 동기화를 하는 것을 말한다. 현재는 대부분 스레드 기준으로 문맥 교환이 일어나기 때문에 스레드 동기화라고도 불린다.

이 글에선 동기화 기법의 전체적 개념을 다루므로 프로세스 동기화와 스레드 동기화의 개념을 구분 짓지 않았으면 좋겠다.

프로세스뿐만 아니라 스레드도 동기화 대상이다.
정확히 말하면 실행의 흐름을 갖는 모든 것은 동기화의 대상이다.
이 글에서는 대부분의 전공서 표현에 따라 프로세스 동기화라고 칭하겠다.

2023.07.02 - [컴퓨터 구조 & 운영체제] - [운영체제] 프로세스와 스레드의 동기화 개념

뮤텍스 락(Mutex lock:MUTual EXclusion lock)

임계 구역 문제와 이를 해결하기 위한 동기화를 옷 가게에서 탈의실을 이용하는 것에 비유해 보자.

탈의실에는 한 명만 들어갈 수 있다. 손님들은 탈의실이라는 자원을 이용하고 탈의실 안에는 손님 한 명 씩만 들어올 수 있으니, 손님은 프로세스, 탈의실은 임계 구역이라고 할 수 있다.

만약 밖에서 탈의실에 사람이 있는지 없는지 알 수 없는 상황이라면, 일단 탈의실을 열어 보고 자물쇠가 걸려있다면 탈의실에 사람이 있다고 판단한다.

이 자물쇠 기능을 코드로 구현한 것이 뮤텍스 락이다.

• 동시에 접근해서 안 되는 자원에 동시에 접근하지 않도록 만드는 도구
• 즉, 상호 배제를 위한 동기화 도구

임계 구역에 진입하는 프로세스는 자신이 지금 임계 구역에 있음을 알리기 위해 뮤텍스 락을 이용해 임계 구역에 자물쇠를 걸어둘 수 있고, 다른 프로세스는 임계 구역이 잠겨 있다면 기다리고, 잠겨 있지 않다면 임계 구역에 진입할 수 있다.

뮤텍스 락은 전역 변수와 두 개의 함수로 구현할 수 있다.

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

acquire 함수

• 프로세스가 임계 구역에 진입하기 전에 호출하는 함수
• 임계 구역이 잠겨 있다면 임계 구역이 열릴 때까지(lock이 false가 될 때까지) 임계 구역을 반복적으로 확인
• 임계 구역이 열려 있다면 임계 구역을 잠그는(lock을 true로 바꾸는) 함수

release 함수

• 임계 구역에서의 작업이 끝나고 호출하는 함수
• 현재 잠긴 임계 구역을 열어주는(lock을 false로 바꾸는) 함수

acquire와 release 함수를 아래와 같이 임계 구역 전후로 호출함으로써 하나의 프로세스만 임계 구역에 진입할 수 있다.

이렇게 되면 프로세스는 

• 임계 구역에 진입할 수 없다면, 무작정 기다리고,
• 임계 구역에 진입할 수 있다면, 임계 구역을 잠근 뒤 임계 구역에서 작업을 진행하고,
• 임계 구역에서 빠져나올 때엔 다시 임계 구역의 잠금을 해제함으로써

임계 구역을 보호할 수 있다.

프로그래밍 언어에서의 뮤텍스 락
C/C++, python 등의 일부 프로그래밍 언어에서는 사용자가 직접 acquire, release 함수를 구현하지 않도록 뮤텍스 락 기능을 제공한다.
실제 프로그래밍 언어가 제공하는 뮤텍스 락은 더욱 정교하게 설계되어 있다.

바쁜 대기(busy wait)
acquire 함수를 보면

임계 구역이 잠겨 있을 경우 프로세스는 반복적으로 lock를 확인하는 것을 볼 수 있다.
이런 대기 방식을 바쁜 대기라고 한다.

세마포(semaphore)

• 뮤텍스 락보다 좀 더 일반화된 방식의 동기화 기법
• 공유 자원이 여러 개 있는 경우에도 적용 가능

세마포의 종류
이진 세마포와 카운팅 세마포 등이 있다.
이진 세마포는 뮤텍스 락과 비슷한 개념.
이 글에서는 여러 공유 자원을 다룰 수 있는 카운팅 세마포를 다룬다.

세마포는 철도 신호기에서 유래한 단어이다.

기차는 신호기가 내려가 있을 때는 '멈춤' 신호로 간주하고 잠시 멈춘다.

반대로 신호기가 올라와 있을 때는 '가도 좋다'는 신호로 간주하여 다시 움직인다.

세마포는 이와 같이 임계 구역을 관리한다.

세마포는 하나의 변수와 두 개의 함수로 단순하게 구현할 수 있다.

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

세마포 변수와 함수 이름
일부 전공서에는 wait와 signal 함수를 P, V로 명명하기도 하고 down, up으로 명명하기도  한다.

뮤텍스 락과 마찬가지로 세마포도 임계 구역 진입 전후로 wait()와 signal()을 호출한다.

wait 함수

signal 함수

busy wait를 극복하지 못한 세마포 예시

예를 들어 P1, P2, P3 세 개의 프로세스가 두 개의 공유자원에 순서대로 접근한다고 가정하면, 공유 자원이 두 개 있으니 변수 S는 2가 된다.

바쁜 대기(busy wait)의 단점 극복(상호 배제를 위한 동기화 기법)

wait 함수는 사용할 수 있는 공유 자원이 없는 경우 프로세스는 무작정 무한히 반복하며 S를 확인해야 한다.

이는 CPU 사이클을 낭비한다는 점에서 손해이다.

그래서 세마포는 아래와 같은 방법으로 이를 해결한다.

• 사용할 수 있는 자원이 없을 경우 대기 상태로 만듦(해당 프로세스의 PCB를 대기 큐에 삽입)
• 사용할 수 있는 자원이 생겼을 경우 대기 큐의 프로세스를 준비 상태로 만듦(해당 프로세스의 PCB를 대기 큐에서 꺼내 준비 큐에 삽입)

이를 간단한 코드로 나타내면 아래와 같다.

busy wait을 극복한 세마포 예시 (상호 배제를 위한 동기화 기법)

예를 들어 P1, P2, P3 세 개의 프로세스가 두 개의 공유자원에 순서대로 접근한다고 가정하면, 공유 자원이 두 개 있으니 변수 S는 2가 된다.

세마포를 활용한 실행 순서 동기화

1. 세마포의 변수 S를 0으로 초기화
2. 먼저 실행할 프로세스 뒤에 signal 함수 호출
3. 다음에 실행할 프로세스 앞에 wait함수 호출

P1이 먼저 실행되면 P1이 임계 구역에 먼저 진입한다, P2가 먼저 실행되더라도 P2는 wait 함수를 만나므로 P1이 먼저 임계 구역에 진입한다.

그리고 P1이 임계 구역의 실행을 끝내고 signal을 호출하면 이후에 P2가 임계구역에 진입한다.

즉, P1이 먼저 실행되는 P2가 먼저 실행되는 반드시 P1, P2 순서대로 실행된다.

세마포도 뮤텍스 락과 마찬가지로 많은 프로그래밍 언어에서 제공한다.

모니터(mornitor)

세마포는 아래와 같은 단점을 가지고 있다.

• 매번 임계 구역 앞뒤로 일일이 wait와 signal 함수를 호출해야 한다.
• 세마포를 누락하거나, wait와 signal함수 호출 순서를 헷갈린 경우, 중복해서 사용한 경우 예기치 못한 결과를 얻을 수 있다.

이에 최근에 등장한 동기화 기법이 모니터이다.

모니터는 세마포에 비하면 개발자가 사용하기에 훨씬 편리한 도구이다.

상호 배제를 위한 동기화

• 객체지향 프로그래밍에서 사용되는 방법
• 인터페이스를 위한 큐
• 공유 자원에 접근하고자 하는 프로세스를 (인터페이스를 위한) 큐에 삽입
• 큐에 삽입된 순서대로 (한 번에 하나의 프로세스만) 공유 자원 이용
• 프로세스는 반드시 인터페이스를 통해서만 공유 자원에 접근

모니터는 위의 그림처럼 공유 자원과 공유 자원에 접근하기 위한 인터페이스(통로)를 묶어서 관리한다.

모니터를 통해 공유 자원에 접근하고자 하는 프로세스를 큐에 삽입하고, 큐에 삽입된 순서대로 하나씩 공유자원을 이용하도록 한다.

즉, 모니터에 진입하기 위한 큐를 만들고,  모니터 안에 항상 하나의 프로세스만 들어오도록 하여 상호 배제를 위한 동기화를 제공한다.

실행 순서 제어를 위한 동기화

• 조건 변수(condition variable) 이용하여 실행 순서 제어
• 조건 변수와 모니터는 별개의 개념

조건 변수
프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수
wait()와 signal()을 호출할 수 있는 특별한 변수

• 조건변수.wait() : 호출한 프로세스의 상태를 대기 상태로 전환하고 일시적으로 조건 변수에 대한 대기 큐에 삽입하는 연산
• 조건변수.signal() : wait()를 호출하여 대기큐에 삽입된 프로세스를 실행 상태로 변경하는 연산
• 상호 배제를 위한 큐 : 모니터에 진입하기 위해 삽입되는 큐(모니터에 한 번에 하나의 프로세스만 진입하도록 하기 위해 만들어진 큐)
• 조건 변수에 대한 큐 : wait가 호출되어 실행 중단된 프로세스들이 삽입되는 큐(이미 진입한 프로세스의 실행 조건이 만족될 때까지 잠시 실행이 중단되어 기다리기 위해 만들어진 큐)

즉, 조건 변수에 대한 큐는 상호 배제를 위한 큐와는 별개의 큐이다.

프로세스 B가 모니터를 떠난 뒤 프로세스 A가 실행하도록 하는 방법(방법 1)

예를 들어 프로세스 A와 B가 있는데 A가 먼저 큐에 있지만 A보다 B가 먼저 실행되어야 한다고 가정하자.

A가 x.wait()를 통해 조건 변수 x에 대한 wait를 호출했다고 하면

그 프로세스는 아래의 그림처럼 조건 변수 x에 대한 큐에 삽입되므로 모니터는 다시 비게 된다.

A는 대기상태이므로 다음 차례인 B가 실행이 된다.

wait() 으로 인해 일시 중지된 프로세스는 다른 프로세스의 signal()를 통해 실행이 재개될 수 있기에

실행을 마친 프로세스 B가 x.signal()을 통해 조건 변수 x에 대한 signal을 호출했다고 하면 이를 통해 조건 변수 x에 대해 대기 상태에 있던 프로세스가 깨어나 모니터 안으로 다시 들어올 수 있다.

프로세스 B를 일시정지 시 뒤 프로세스 A가 실행하도록 하는 방법

아래의 부분은 이해가 잘되지 않아서 맞는 건지 잘 모르겠다.

예를 들어 프로세스 A와 B가 있는데 A가 먼저 큐에 있지만 A보다 B가 먼저 실행되어야 한다고 가정하자.

1. A가 먼저 인터페이스에 들어간다.
2. A는 signal을 통해 B의 실행시킨 뒤 자신을 일시 중지(wait)한다.
3. B가 실행이 끝난다.
4. 다시 A의 실행이 재개된다. 

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

동시다발적으로 실행되는 프로세스와 스레드들은 공동의 목적을 수행하기 위해 서로 협력하며 영향을 주고받기도 한다.

이렇게 협력하여 실행되는 프로세스와 스레드들은 실행 순서와 자원의 일관성을 보장해야 하기에 반드시 동기화가 되어야 한다.

프로세스 동기화란 프로세스 사이에 동기화를 하는 것을 말한다. 현재는 대부분 쓰레드 기준으로 문맥 교환이 일어나기 때문에 스레드 동기화라고도 불린다.

이 글에선 동기화의 전체적 개념을 다루므로 프로세스 동기화와 스레드 동기화의 개념을 구분 짓지 않았으면 좋겠다.

프로세스뿐만 아니라 스레드도 동기화 대상이다.
정확히 말하면 실행의 흐름을 갖는 모든 것은 동기화의 대상이다.
이 글에서는 대부분의 전공서 표현에 따라 프로세스 동기화라고 칭하겠다.

동기화(Synchronization)의 의미

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

프로세스들 사이의 수행 시기를 맞추는 것은 크게 아래 두 가지를 일컫는다.

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

즉, 동기화에서는 실행 순서 제어를 위한 동기화가 있고, 상호 배제를 위한 동기화가 있다.

실행 순서 제어를 위한 동기화 : reader writer problem

예를 들어, 아래와 같은 프로세스가 있다고 가정하자

• Writer : Book.txt 파일에 값을 쓰고 저장하는 프로세스
• Reader : Book.txt 파일에 저장된 값을 읽어들이는

이 두 프로세스는 무작정 아무 순서대로 실행되어서는 안 된다.

Reader 프로세스는 Writer 프로세스 실행이 끝나야 비로소 실행할 수 있기 때문이다.

Writer 프로세스가 Book.txt에 값을 저장하기도 전에 Reader 프로세스가 Book.txt를 읽는 것은 올바른 실행 순서가 아니다.

->Reader 프로세스는 Book.txt 안에 값이 존재한다는 특정 조건이 만족되어야만 실행 가능

상호 배제(mutual exclusion)를 위한 동기화 : Bank account problem

상호 배제는 공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘이다.

즉, 한 번에 하나의 프로세스만 접근해야 하는 자원에 동시 접근을 피하기 위한 동기화이다.

예를 들어, 현재 계좌의 잔액은 10만 원이 있고, 아래의 프로세스가 있다고 가정하자

• 프로세스 A : 현재 잔액에 2만 원을 추가하는 프로세스
• 프로세스 B :  현재 잔액에 5만 원을 추가하는 프로세스

프로세스 A와 B가 실행되는 과정은 아래와 같다.

이제 프로세스 A와 B가 동시에 실행되었다고 가정한 상태에서 동기화가 제대로 이루어지지 않은 경우에는 17만 원이 계좌에 남지 않을 수 있다.

이유는 아래와 같다.

문맥 교환 과정에서 A프로세스의 실행 과정에서 더한 값을 저장하기 전에 문맥 교환이 일어나서 12+5가 아니라 10+2라는 연산이 이뤄졌다.

즉, A프로세스의 실행 과정이 완전히 끝나기 전에 B프로세스가 시작되었기 때문이다.

동기화가 이루어진 상태에서 A프로세스와 B프로세스가 실행되었다고 가정하면 실행 과정은 아래와 같다.

이렇게 동시에 접근해서는 안 되는 자원에 동시에 접근하지 못하게 하는 것이 상호 배제를 위한 동기화이다.

공유 자원과 임계 구역

위의 상호 배제를 위한 동기화에서 '잔액'이라는 공동의 자원을 두고 작업을 했다 이러한 자원을 공유 자원이라고 한다.

또한, 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역을 임계 구역이라고 한다.

• 공유 자원(shared resource) : 여러 프로세스 혹은 스레드가 공유하는 자원(전역 변수, 파일, 입출력장치, 보조기억장치 등)
• 임계 구역(critical section) : 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역

임계 구역에 동시에 접근하면 자원의 일관성이 깨질 수 있다. 이를 레이스 컨디션(race condition)이라고 한다.

운영체제는 임계 구역 문제를 아래 세 가지 원칙 하에 해결한다.

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

레이스 컨디션이 발생하는 근본적인 이유

우리가 프로그래밍하는 고급 언어는 실행 과정에서 저급 언어로 변환되어서 실행된다.

변수를 증가 또는 감소시키는 코드는 고급 언어에서는 한 줄로 작성할 수 있지만, 컴퓨터 내부에서는 여러 줄의 저급 언어로 변환되어 실행된다.

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

저급 언어를 실행하는 과정에서 문맥 교환이 일어난다면 아래와 같은 문제가 발생한다.

이때, 상호 배제를 위한 동기화는 이와 같은 일이 발생하지 않도록 두 개 이상의 프로세스가 임계구역에 동시에 접근하지 못하도록 관리하는 것을 의미한다.

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

선입선출(FCFS:First Come First Served) 스케줄링

• 비선점형방식
• 단순히 준비 큐에 삽입된 순서대로 처리하는 스케줄링
• 먼저 CPU를 요청한 프로세스부터 CPU할당
• 프로세스들이 기다리는 시간이 매우 길어질 수 있다. (=호위효과)

최단 작업 우선 스케줄링(SJF:Shortest Job First)

• 선점형이나 비선점형 둘다 구현될 수 있지만 보통 비선점형으로 구현
• 호위 효과를 줄이기위해 고안된 스케줄링
• 실행 시간이 가장 짧은 프로세스에 우선순위를 매긴다.
• CPU 사용이 긴 프로세스는 나중이 실행, CPU 사용 시간이 짧은 프로세스를 먼저 실행

라운드 로빈(RR:Round Robin) 스케줄링

• 선점형 방식
• 선입선출 스케줄링 + 타임 슬라이스(time slice)
• 정해진 타임 슬라이스 만큼의 시간 동안 돌아가며 CPU를 이용하는 스케줄링

타임 슬라이스
각 프로세스가 CPU를 사용할 수 있는 정해진 시간.
타임 슬라이스의 크기가 너무 짧으면 오버헤드가 자주 발생하고, 너무 길면 선입선출 스케줄링과 다를게 없다.

최소 잔여 시간 우선 스케줄링(SRT:Shortest Remaining Time)

• 선점형 방식
• 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
• 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택
• 진행 중인 프로세스가 있어도, 최단 잔여시간인 프로세스를 위해 sleep 시키고 짧은 프로세스를 먼저 할당

우선순위 스케줄링(Priority Scheduling)

• 선점형 방식과 비선점형 방식이 둘다 존재
• 프로세스들에 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행
• 우선순위가 같은 프로세스들은 선입 선출로 스케줄링
• 최단 작업 우선 스케줄링과, 최소 잔여 시간 스케줄링은 넓은 범위에서 우선순위 스케줄링이라고 볼 수 있다.

우선순위 스케줄링은 기아(starvation)현상이라는 근본적인 문제점을 가지고 있다.

기아(starvation)현상
우선순위가 높은 프로세스만 계속 실행되는 것이다. 즉, 우선순위가 낮은 프로세스는 준비 큐에 먼저 삽입되었음에도 불구하고 계속 실행이 연기된다.

기아 현상을 해결하기위한 기법으로는 에이징(aging)이 있다.

에이징 기법은 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식이다.

대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시킨다고 해서 에이징이라고 한다.

다단계 큐 스케줄링(MLQ:MultiLevel Queue)

• 우선선위 스케줄링의 단점을 보완한 형태
• 우선순위별로 준비큐를 여러 개 사용하는 스케줄링 방식
• 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
• 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리
• 각 큐는 자신만의 독자적인 스케줄링 알고리즘과 타임 슬라이스를 가질 수 있다.
• 프로세스는 큐에서 다른 큐로 이동이 불가능 하기에, 기아(starvation)현상이 발생할 수 있다.

다단계 피드백 큐 스케줄링(MLFQ:MultiLevel Feedback Queue)

• 다단계 큐 스케줄링의 기아현상을 보완하기 위한 형태
• 큐 간의 이동이 가능한 다단계 큐 스케줄링
• 우선순위가 높은 프로세스가 타임 슬라이스 동안 처리가 되지 않으면 한 단계씩 우선순위가 낮아진다.
• 우선순위가 낮은 프로세스가 오래 기다릴수록 우선순위가 높아진다.(에이징)
• 가장 일반적인 CPU 스케줄링 알고리즘으로 알려짐

즉, 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘이다.

구현이 복잡하지만, 가장 일반적인 CPU 스케줄링으로 알려져 있다.

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

모든 프로세스들은 CPU를 필요로 하고, 모든 프로세스들은 먼저 CPU를 사용하고 싶어 한다.

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

CPU 스케줄링은 컴퓨터 성능과도 직결되는 중요한 문제이다.

프로세스 우선순위

단순히 생각하면 CPU를 사용하고 싶어 하는 프로세스들을 줄 세워서 차례대로 쓰게 하면 된다.

하지만 프로세스마다 우선순위(priority)가 다르기 때문에 적절하지 못한 방법이다.

우선순위가 높은 프로세스는 대표적으로 입출력 작업이 많은 프로세스이다.

입출력 작업이 많은 프로세스(=입출력 집중 프로세스(I/O bound process))의 우선순위는 CPU 작업이 많은 프로세스(=CPU 집중 프로세스(CPU bound process)) 의 우선순위보다 높다.

왜냐하면 입출력 집중 프로세스는 입출력 장치를 많이 사용하다 보니 자연스럽게 "실행 상태"보다 "대기 상태"에 더 많이 머물기 때문에 입출력 집중 프로세스를 먼저 처리하면 CPU 집중 프로세스에 집중적으로 CPU를 할당시킬 수 있기 때문이다.

이렇게 운영체제는 각각의 상황에 맞게 CPU를 배분하는 것이 더 효율적이다.

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

CPU 버스트와 입출력 버스트
CPU를 이용하는 작업을 CPU 버스트(CPU burst)라고 하고, 입출력장치를 기다리는 작업을 입출력 버스트(I/O burst)라고 한다.
프로세스는 일반적으로 CPU 버스트와 입출력 버스트를 반복하며 실행된다.
그래서 입출력 집중 프로세스는 입출력 버스트가 많은 프로세스, CPU 집중 프로세스는 CPU 버스트가 많은 프로세스라고 정의할 수 있다.

스케줄링 큐

PCB에 우선순위가 적혀있지만 CPU를 사용할 다음 프로세스를 찾기 위해 운영체제가 모든 프로세스의 PCB를 탐색하는 것은 비효율적이다.

그래서 운영체제는 줄을 서서 기다릴 것을 요구한다.

CPU를 사용하고 싶은 프로세스, 메모리에 적재되고 싶은 프로세스, 입출력 장치를 사용하고 싶은 프로세스들 모두 줄을 세우는 것이다.

운영체제는 이 줄을 스케줄링 큐(scheduling queue)로 구현하고 관리한다.

큐(queue)
자료구조 관점에서 큐는 선입선출(FIFO) 구조이지만, 스케줄링에서 말하는 큐는 반드시 선입선출은 아니다.

스케줄링 큐에는 아래와 같은 종류가 있다.

• 준비 큐(ready queue) : CPU를 이용하기 위해 프로세스들이 서는 줄
• 대기 큐(waiting queue) : 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄

준비 상태

• 운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행한다.
• 우선순위가 높은 프로세스가 있다면 높은 프로세스부터 실행한다.
• 위 방식은 선점형 스케줄링이라고 한다.

대기 상태

• 대기 상태에 있는 프로세스도 마찬가지로 준비 상태와 마찬가지인 규칙을 따른다.
• 같은 장치를 요구한 프로세스들은 같은 대기 큐에서 작업을 기다린다.
• 입출력이 완료되면 해당 PCB를 찾고 이 PCB를 준비 상태로 변경한 뒤 대기 큐에서 제거 후, 해당 PCB를 준비 큐로 이동시킨다.

위 과정들을 상태 다이어그램으로 나타내면 아래와 같다.

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

선점형 스케줄링(preempitve schduling)

프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식을 의미

• 우선순위가 높은 프로세스가 언제든 끼어들어 사용할 수 있는 방식
• 어느 하나의 프로세스가 자원 사용을 독점할 수 없는 스케줄링 방식
• 프로세스마다 정해진 시간만큼 CPU를 사용
• 정해진 시간을 모두 써서 타이머 인터럽트가 발생하면 운영체제가 CPU를 빼앗고, 다른 프로세스에게 CPU를 할당한다.

장점과 단점은 아래와 같다.

• 장점 : 어느 한 프로세스의 자원 독점을 막고 프로세스들에게 골고루 자원 배분 가능
• 단점 : 문맥 교환 횟수가 많아서 오버헤드 발생 횟수가 높다.

비선점형 스케줄링(non-preempitve schduling)

하나의 프로세스가 CPU를 비롯한 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링

• 우선순위가 높은 프로세스가 끼어들어 사용할 수 없는 방식
• 어느 하나의 프로세스가 자원 사용을 독점할 수 있는 스케줄링 방식
• 어떤 프로세스가 CPU를 사용 중이라면 해당 프로세스가 CPU를 원하는 만큼 다 쓸 때까지 다른 프로세스들은 기다려야 한다.

장점과 단점은 아래와 같다.

• 장점 : 문맥 교환 횟수가 적어서 오버헤드 발생 횟수가 적다.
• 단점 : 하나의 프로세스가 자원을 사용 중이라면 당장 자원을 사용해야 하는 프로세스라도 무작정 기다릴 수밖에 없다.

오버헤드(overhead)
오버헤드는 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등을 말한다.
여기서 오버헤드는 문맥 교환을 할 때 지금까지 작업해야 하는 내용을 백업하거나 다시 불러올 때 생기는 비용을 뜻한다.

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

스레드

이 글에서 다루는 내용은 소프트웨어적 스레드이며, 스레드는 실행의 단위이다.

• 스레드란 프로세스를 구성하는 실행의 흐름 단위
• 하나의 프로세스는 여러 개의 스레드를 가질 수 있다.

스레드를 이용하면 하나의 프로세스에서 여러 부분을 동시에 실행할 수 있다.

프로세스와 스레드

단일 스레드 프로세스

• 하나의 프로세스는 한 번에 하나의 일만 처리
• 실행의 흐름 단위가 하나라는 점에서 이렇게 실행되는 프로세스를 단일 스레드 프로세스라고 부른다.

멀티 스레드 프로세스

• 실행 흐름이 여러 개인 프로세스
• 프로세스를 이루는 여러 명령어 동시 실행 가능

스레드의 구성요소

스레드는 프로세스 내에서 각기 다른 아래의 값을 가지고 있다.

• 스레드 ID
• 프로그램 카운터 값을 비롯한 레지스터 값
• 스택

각자 프로그램 카운터 값을 비롯한 레지스터 값, 스택을 가지고 있기에 스레드마다 각기 다른 코드를 실행할 수 있다.
 
여기서 중요한 점은 프로세스의 스레드들은 실행에 필요한 최소한의 정보(프로그램 카운터를 포함한 레지스터, 스택)만을 유지한 채 프로세스 자원을 공유하며 실행된다는 점이다.
프로세스의 자원을 공유한다는 것이 스레드의 핵심이다.

위 그림을 보면 스레드 1만의 코드/데이터/힙 영역이 있는 게 아니고 스레드 1,2,3은 모두 같은 코드/데이터/힙 영역을 공유한다는 것이다.
 
정리하면 아래와 같다.

• 스레드는 프로세스를 구성하는 실행의 흐름단위
• 최근 많은 운영체제는 CPU에 처리할 작업을 전달할 때 프로세스가 아닌 스레드 단위로 전달
• 스레드는 프로세스 자원을 공유한 채 실행에 필요한 최소한의 정보만으로 실행

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

• 멀티 프로세스 : 여러 프로세스를 동시에 실행
• 멀티 스레드 : 한 프로세스에서 여러 스레드를 실행하는 것

동일한 작업을 수행하는 단일 스레드 프로세스 여러 개 실행 VS 하나의 프로세스를 여러 스레드로 실행

예를 들어, "hello, os"를 화면에 출력하는 프로그램이 있다고 가정

• 이 프로그램을 3번 fork(복제)하여 실행하면 화면에는 "hello, os"가 3번 출력
• 이 프로그램 내에 스레드를 세 개 만들어 실행하면 화면에는 "hello, os"가 3번 출력
• 결과는 같다.

하지만 여기에는 큰 차이점이 있다.
프로세스끼리는 기본적으로 자원을 공유하지 않지만, 스레드끼리는 같은 프로세스 내의 자원을 공유한다는 점이다.
 
멀티 프로세스

• 프로세스를 fork(복제)하면 코드 /데이터 / 힙 영역 등 모든 자원이 복제되어 저장됨
• 저장된 메모리 주소를 제외하면 모든 것이 동일한 프로세스 두 개가 통째로 메모리에 적재
• fork(복제)를 세 번, 네 번하면 메모리에는 같은 프로세스가 통째로 세 개, 네 개 적재
• 프로세스끼리는 자원을 공유하지 않는다 -> 남남처럼 독립적으로 실행된다.

쓰기 시 복사(copy on write)
fork를 한 직후 같은 프로세스를 통째로 메모리에 중복 저장하지 않으면서 동시에 프로세스끼리 자원을 공유하는 방법을 쓰기 시 복사 기법이라고 한다.
하지만 여기서는 이 기법을 쓰지 않는다고 가정

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

 
멀티 스레드

• 스레드들은 프로세스 자원(코드/ 데이터/ 파일/ 힙 영역)을 공유
• 실행에 필요한 각기 다른 최소한의 정보(프로그램 카운터 값을 포함한 레지스터 값, 스택)만으로 실행
• 스레드는 프로세스의 자원을 공유한다 -> 협력과 통신에 유리하다.

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

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

프로세스 상태(process state)

우리가 컴퓨터를 사용할 때 여러 프로세스들이 빠르게 번갈아 가면서 실행된다.
그 과정에서 하나의 프로세스는 여러 상태를 거치며 실행된다.
운영체제는 프로세스의 상태를 PCB를 통해 인식하고 관리한다.
프로세스의 상태를 표현하는 방식은 운영체제마다 다르지만 대표적인 상태는 아래와 같다.
 

생성 상태

• 이제 막 메모리에 적재되어 PCB를 할당받은 상태
• 준비가 완료되었다면 준비상태가 된다.

준비 상태

• 당장이라도 CPU를 할당받아 실행할 수 있지만 자신의 차례가 아니기에 기다리는 상태
• 자신의 차례가 된다면 실행상태가 된다.
• 준비 상태인 프로세스가 실행 상태로 전환되는 것을 디스패치(dispatch)라고 한다.

실행 상태

• CPU를 할당 받아 실행 중인 상태
• 할당된 시간 모두 사용 시(타이머 인터럽트 발생 시) 준비 상태가 된다.
• 실행 도중 입출력장치를 사용하면 입출력 작업이 끝날 때까지 대기 상태가 된다.

대기 상태

• 프로세스가 실행 도중 입출력장치를 사용하는 경우
• 입출력 작업은 CPU에 비해 느리기에 이 경우 대기 상태가 된다.
• 입출력 작업이 끝나면(입출력 완료 인터럽트를 받으면) 준비 상태가 된다.

대기 상태의 일반적인 정의
프로세스가 대기 상태가 되는 이유에 입출력 작업만 있는 것은 아니다.
프로세스가 대기 상태가 되는 대부분의 원인이 입출력 작업인 것은 맞지만
더 일반적으로 표현하자면 특정 이벤트가 일어나길 기다릴 때 프로세스는 대기 상태가 된다.

종료 상태

• 프로세스가 종료된 상태
• PCB, 프로세스의 메모리 영역에서 정리된다.

프로세스 상태 다이어그램(process state diagram)

운영체제는 이러한 상태를 PCB에 기록하며 프로세스들을 관리한다.
 

프로세스 계층 구조

프로세스는 실행 도중 시스템 호출을 통해 다른 프로세스를 생성할 수 있다.

• 부모 프로세스(parent process) : 새 프로세스를 생성한 프로세스
• 자식 프로세스(child process) : 부모 프로세스에 의해 생성된 프로세스

부모 프로세스와 자식 프로세스는 엄연히 다른 프로세스이기에 각기 다른 PID를 가진다.
일부 운영체제에서는 자식 프로세스의 PCB에 부모 프로세스의 PID인 PPID(Parent PID)가 기록되기도 한다.
 
또한 자식 프로세스는 또 다른 자식 프로세스를 생성할 수 있다.
많은 운영체제는 이처럼 프로세스가 프로세스를 낳는 계층적인 구조로써 프로세스들을 관리한다.
컴퓨터가 부팅될 때 실행되는 최초의 프로세스가 자식 프로세스들을 생성하고, 생성된 자식 프로세스들이 새로운 프로세스들을 낳는 형식으로 여러 프로세스가 동시에 실행되는 것이다.
 
이 과정을 도표로 그리면 트리 구조를 띄는데, 이를 프로세스 계층 구조라고 한다.

위 그림은 사용자가 컴퓨터를 켜고 로그인 창을 통해 성공적으로 로그인해서 bash 셸(UI)로 Vim이라는 문서 편집기 프로그램을 실행했다고 가정한 것이다.

데몬이나 서비스 또한 최초 프로세스의 자식 프로세스이다.

프로세스 생성 기법

이하 내용은 윈도우 OS와 관련이 없으나 수많은 OS의 핵심개념이다.

부모 프로세스를 통해 생성된 자식 프로세스들은 복제와 옷 갈아입기를 통해 실행된다.

• fork(복제) 시스템 호출 : 부모 프로세스는 자신의 복사본을 자식 프로세스로 생성
• exec(옷 갈아입기)시스템 호출 : 자식 프로세스는 자신의 메모리 공간을 다른 프로그램으로 교체

fork 시스템 호출

• 복사본(=자식 프로세스) 생성
• 부모 프로세스의 자원 상속

fork(복제)를 그림으로 나타내면 아래와 같다.

exec 시스템 호출

• 메모리 공간을 새로운 프로그램으로 덮어쓰기
• 코드/데이터 영역은 실행할 프로그램 내용으로 바뀌고 나머지 영역은 초기화

fork(복제)와 exec(옷 갈아입기) 시스템 호출을 그림을 나타내면 아래와 같다.

 
부모가 자식 프로세스를 실행하며 프로세스 계층 구조를 이루는 과정은 fork와 exec가 반복되는 과정이라 볼 수 있다.

부모 프로세스로부터 자식 프로세스가 복사되고, 자식 프로세스는 새로운 프로그램으로 옷을 갈아입고, 또 그 자식 프로세스로부터 자식 프로세스가 복사되고, 옷을 갈아입는 방식으로 여러 프로세스가 계층적으로 실행된다.