[CS Study] 3. 운영체제 (2)

# 본 글은 인하대학교 단풍나무숲 CS 스터디에 작성한 내용을 그대로 가져온 글입니다.

3. 운영체제

목차

3. 프로세스와 스레드

컴퓨터에 설치된 '프로그램' 이 실행되면, 코드가 스토리지에서 메모리로 옮겨지고, CPU 등의 자원이 할당됩니다. 이렇게 실행 중인 상태의 프로그램을 '프로세스'라고 부릅니다. Task라고도 합니다.
프로세스 내에 존재하는 1개 이상의 작업 흐름을 스레드 (thread)라고 부릅니다. 한 프로세스 내의 여러 스레드는 메모리 공간을 공유하며, 각 프로세스는 고유의 메모리 공간을 가집니다.

1. 프로세스와 컴파일 과정

2. 프로세스의 상태

프로세스는 아래와 같은 상태를 가집니다.

• 생성 (create): fork() 또는 exec() 함수를 통해 프로세스가 신규로 생성된 상태를 가리킵니다. 이 때 PCB가 할당됩니다.
  • fork(): 부모 프로세스(의 주소 공간)를 그대로 복사하여, 새로운 자식 프로세스를 생성하는 함수입니다. 메모리 공간은 공유하지 않으며, 두 프로세스는 같은 프로세스 그룹에 속합니다.
  • exec(): 신규 프로세스를 생성하는 함수입니다.
• 대기 (ready): 메모리 공간이 충분하면 메모리 공간을 할당 받고, 그렇지 않다면 CPU scheduler로부터 CPU 제어권이 넘어오기를 기다리는 상태입니다.
• 대기 중단 (ready suspended): 메모리 부족으로 프로세스가 일시 중단된 상태입니다..
• 실행 (running): 프로세스가 CPU, 메모리 등의 자원을 할당받고 명령어를 수행 중인 상태를 가리킵니다.
• 중단 (blocked): 어떤 이벤트를 통해 프로세스가 차단된 상태입니다. 대표적인 예로 I/O 디바이스에 의한 인터럽트로 인해, 프로세스가 block될 수 있습니다.
• 일시 중단 (blocked suspended): 중단된 프로세스가 실행되려고 했지만, 메모리 부족으로 일시 중단된 상태입니다.
• 종료 (terminated): 프로세스가 메모리와 CPU 등의 자원을 반환하고 사라지는 상태입니다.

3. 프로세스의 메모리 구조

OS가 프로세스에게 할당하는 메모리는 다음과 같은 구조를 가집니다.
낮은 메모리 주소부터 높은 메모리 주소 쪽으로,

• 코드
• 데이터
• 힙 (heap)
• 스택 (stack)

이라는 네 개의 영역을 가집니다. 이 영역은 프로세스별로 독립적이며, 같은 프로세스 내 스레드는 공유합니다.

• 코드 (Code)
  • 프로그램에 내장되어 있는 소스 코드가 들어갑니다. 수정 불가능한 기계어로 들어가며, 따라서 정적인 영역입니다.
• 데이터 (data)
  • 전역변수, 정적변수가 저장되고, 정적인 특징을 갖는 프로그램이 종료되면 사라지는 변수가 들어 있습니다.
• 힙 (heap)
  • 동적 할당 시 사용되며, 런타임 시 크기가 결정됩니다. vector와 같은 동적 배열이 이 영역에 저장되며, 따라서 동적인 영역입니다.
• 스택 (stack)
  • 지역변수, 매개변수, 함수 등이 저장되며, 컴파일 시에 크기가 정해집니다. 마찬가지로 동적인 영역입니다.
  • 함수가 재귀호출 되면 동적으로 크기가 늘어날 수 있으며, 힙과 영역이 충돌하지 않도록 둘 사이의 공간을 비워 둡니다.

4. PCB (Process Control Block)

OS에서 프로세스에 대한 메타데이터를 저장한 것을 PCB라고 부릅니다. 프로세스가 생성되면, OS는 해당 프로세스에 대한 PCB를 생성합니다.

• 프로세스 스케줄링 상태
• 프로세스 ID
• 프로세스 권한
• 프로그램 카운터: 프로세스가 다음으로 실행해야 할 명령어의 주소를 가리키는 포인터
• CPU 레지스터: 프로세스를 실행하기 위해 저장해야 할 레지스터에 대한 정보
• CPU 스케줄링 정보
• 계정 정보
• I/O 상태 정보

5. 컨텍스트 스위칭 (Context Switching)

OS가 실행 중인 한 프로세스에서 다른 프로세스로 넘어가는 과정을 컨텍스트 스위칭이라고 부릅니다.
책을 하나 읽다가 다른 책을 펼 때, 기존 책을 어디까지 읽었는지 책갈피를 끼워 두듯, 프로세스 간에 넘어갈 때 기존 프로세스의 상태에 대한 정보를 기록해 두어야 합니다.

• 배용: 캐시미스
  • 컨텍스트 스위칭이 발생할 때, 프로세스가 가지고 있는 메모리 주소가 그대로 있으면, 잘못된 주소 변환이 생깁니다.
  • 이로 인해 캐시클리어 과정을 겪게 되고, 따라서 캐시 미스가 발생합니다.
• 스레드에서의 컨텍스트 스위칭이
  • 스레드는 스택 영역을 제외한 모든 메모리 영역을 공유합니다. 따라서 프로세스의 컨텍스트 스위칭에 비해 비용도 적고 시간도 더 적게 걸립니다.

6. 멀티프로세싱과 IPC (Inter-Process Communication)

컴퓨터는 한 번에 두 개 이상의 프로세스가 실행됩니다. 이 때 프로세스 간의 커뮤니케이션을 위해 다양한 방법이 고안되었는데, 이 중 대표적인 두 개를 소개합니다.

공유 메모리

여러 프로세스가 동일한 메모리 블럭에 대한 접근 권한을 가지는 것을 공유 메모리라고 합니다.
메모리 자체를 공유하므로 가장 효율적이고 오버헤드가 발생하지 않지만, 같은 메모리 영역을 공유하기 때문에 동기화 등의 과정이 필요합니다.
그만큼 구현 난이도가 있어서, 메세지 큐에 비해 덜 선호되는 방법입니다.

메세지 큐

프로세스 간 보내는 메세지를 queue 형태로 관리합니다. 이는 커널의 전역변수 형태 등으로 전역으로 관리되며 다른 IPC에 비해서 사용하기가 매우 쉽고 간단합니다.
현대에는 컴퓨터의 성능이 충분히 좋아졌기 때문에, 공유 메모리가 주는 이점의 메리트가 그다지 크지 않은 상황입니다.

7. 스레드와 멀티스레딩

앞서 언급한 바와 같이, 스레드 (thread)는 프로세스의 실행 단위입니다. 프로세스는 하나 이상의 스레드를 가질 수 있고, 각 스레드는 병렬적으로 동작할 수 있습니다.

메모리 구조

한 프로세스 내의 스레드는 코드, 데이터, 힙 영역을 공유합니다. 즉, 스택은 별도로 가지게 됩니다.

멀티스레딩 (multithreading)

프로세스 내 작업을 여러 개의 스레드를 통해 처리하는 기법입니다.
서로 자원을 공유하기 때문에, 멀티프로세싱에 비해 효율성이 높습니다. 또한, 한 프로세스가 block되어도 다른 프로세스가 여전히 실행 중이기 때문에, 빠른 처리가 가능합니다.
단점으로는, 한 스레드에 문제가 생기면, 메모리를 공유하기 때문에 다른 스레드에도 필연적으로 영향을 주게 됩니다.

8. 공유 자원과 임계 영역 (critical section)

시스템 안에서 각 프로세스, 스레드 등이 함께 접근할 수 있는 자원을 공유 자원 (shared resource)라고 합니다. 메모리, 파일, 데이터, I/O 장비 등이 있습니다.
자연스레 두 개 이상의 프로세스가 해당 자원을 얻고자 하는 경우가 발생하며, 이를 경쟁 상태 (race condition)이라고 합니다. 두 개 이상의 프로세스가 특정 자원에 무분별하게 접근한다면, 접근 순서 등이 결과에 영향을 줄 가능성이 있습니다.

아래 예시를 봅시다.

int x = 3;

// process a
void processA() {
  print(x);
  x = x + 3;
  print(x);
}

// process b
void processB() {
  print(x);
  x = x * 2;
  print(x);
}

x는 공유 자원, 두 함수는 각각 프로세스라고 가정합니다.
프로세스 A만 실행했을 때는, 기대값이 어떻게 될까요? 먼저 3을 출력하고, 3에 3을 더한 후, 6을 출력하는 행동이 순수하게 A만 실행했을 때의 기댓값입니다.
만약 A와 B를 동시에 실행한다면, 이런 과정이 발생할 수도 있습니다.

• 프로세스 A가 x값을 출력
• 프로세스 A가 x에 3을 더한 값을 x에 할당함
• 프로세스 B가 x값을 출력
• 프로세스 B가 x에 2를 곱한 값을 x에 할당함
• 프로세스 A가 x값을 출력

위 상황에서, 사용자는 현재 프로세스 A만 보고 있다고 가정합니다.
그러면 이렇게 되겠지요.
|process A|expectation|reality|
|---|---|---|
|print(x);|3|3|
|x = x + 3;|-|-|
|print(x);|6|12|

이런 현상이 얼마든지 발생할 수 있습니다.

임계 영역

공유 자원에 접근할 때, 접근 순서 등의 이유로 결과가 달라질 수 있는 영역을 임계 영역 (critical seciton)이라고 합니다.
임계 영역의 문제를 해결하기 위하여 뮤텍스 (mutex), 세마포어 (semaphore), 모니터 (monitor) 등의 방법을 사용합니다. 이 세 방법 모두 상호 배제, 한정 대기, 융통성이라는 조건을 만족합니다.
핵심 개념은 lock입니다. 자주 사용하는 비유로 화장실 열쇠가 있는데, A라는 사람이 화장실 열쇠를 통해 화장실을 열고 들어가면, B라는 사람은 A가 화장실에서 나와서 열쇠를 제자리에 둘 때까지 화장실에 접근할 수 없는 것이죠.

• 뮤텍스
  • 공유 자원을 사용하기 전에 설정하고, 사용한 후에 해제하는 잠금입니다.
  • 잠금이 설정되면, 다른 스레드는 해당 코드 영역에 접근할 수 없습니다. 한 번에 하나의 잠금만 가집니다.
• 세마포어
  • 일반화된 뮤텍스입니다. 정수 값과 두 가지 함수 (wait, signal)를 통해 공유 자원에 대한 접근을 처리합니다.
  • wait(): 자신의 차례가 올 때까지 기다리는 함수입니다.
  • signal(): 다음 프로세스에게 순서를 넘겨 주는 함수입니다.
  • 바이너리 세마포어: 0과 1의 값만을 가질 수 있는 세마포어. 뮤텍스와 매우 유사합니다.
  • 카운팅 세마포어: 여러 개의 자원을 가질 수 있는 세마포어이며, 여러 개의 자원에 대한 접근을 제어할 때 사용됩니다.

9. 교착 상태 (deadlock)

두 개 이상의 프로세스들이 서로가 가진 자원을 기다리며 무기한 대기하는 상태를 교착 상태 (deladlock)라고 합니다.
교착 상태는 아래와 같은 조건을 모두 만족할 때 발생합니다.

• 상호 배재 (mutual exclusion): 한 프로세스가 자원을 독점하고 있으며, 다른 프로세스는 해당 자원에 접근이 불가능함
• 점유 대기 (hold and wait): 프로세스는 자원을 점유한 채로 다른 자원을 기다릴 수 있음
• 비선점 (no preemption): 다른 프로세스가 점유한 자원을 빼앗아 올 수 없음
• 환형 대기 (circular wait): 프로세스 A는 프로세스 B의 자원을, 프로세스 B는 프로세스 C의 자원을, 프로세스 C는 프로세스 A의 자원을 기다리는 등 서로가 서로의 자원을 요구함

위 조건 중 하나라도 불만족시키면 교착 상태를 해소할 수 있습니다.
현대 OS의 경우, 교착 상태가 발생하면, 처리하는 비용이 너무 크기 떄문에, 해당 프로세스를 종료시키는 방법을 사용합니다.

4. CPU 스케줄링 알고리즘

4. CPU 스케줄링 알고리즘

OS는 CPU, 메모리 등의 자원을 프로세스들에게 최대한 효율적으로 분배해야 합니다. 이를 위해 다양한 스케줄링 알고리즘이 고안되었습니다.
스케줄링 알고리즘은 크게 선점형 (preemptive), 비선점형 (non-preemptive) 알고리즘으로 나뉩니다.

1. 비선점형 (non-preemptive) 알고리즘

OS가 프로세스로부터 CPU를 뺏어올 수 없고, 프로세스가 스스로 CPU를 포기해야 하는 알고리즘입니다.

• FCFS (First Come First Served)
  • 가장 먼저 온 프로세스를 가장 먼저 처리합니다.
  • 구현이 단순하지만, 먼저 온 프로세스가 수행 시간이 길다면, 나중에 온 프로세스가 ready queue에서 오래 기다려야 하는 convoy effect가 발생합니다.
• SJF (Shortest Job First)
  • 실행 시간이 가장 짧은 프로세스를 먼저 처리합니다.
  • 수행 시간이 오래 걸리는 프로세스가 오랜 시간 동안 실행되지 않는 starvation 현상이 발생할 수 있습니다.
  • 평균 대기 시간이 가장 짧습니다.
  • 실제로는 정확한 실행 시간을 미리 알 수 없기 때문에, 과거의 데이터를 토대로 실행 시간을 예측하여 사용합니다.
• 우선 순위
  • 프로세스별 aging 개념을 도입하여, 오래 실행되지 않은 프로세스가 우선순위를 높게 가지도록 처리하는 알고리즘

2. 선점형 (preemptive) 알고리즘

OS가 프로세스로부터 CPU를 뺏어서, 다른 적당한 프로세스에게 할당해 줄 수 있는 알고리즘입니다.

• 라운드 로빈 (Round Robin)
  • 대기 중인 모든 프로세스를 일정 크기로 잘게 쪼개어, 각 프로세스별로 균등한 시간을 부여한 후 다음 프로세스로 CPU를 넘겨 주는 방식
  • 현대 컴퓨터 및 서버 로드 밸런서가 사용하는 알고리즘입니다.
  • 전체 작업 시간이 길어지지만, 평균 응답 시간이 짧아집니다.
• SRF (Shortest Round First)
  • SJF와 비슷하게, 실행 시간이 더 짧은 프로세스를 우선하여 CPU를 할당합니다.
  • 단, 현재 실행 중인 프로세스보다 실행 시간이 더 짧은 프로세스가 들어오면, SRF는 새 프로세스에게 CPU를 넘겨줍니다.
• 다단계 큐 (Multi-Level Queue)
  • 우선 순위에 따른 큐를 여러 개 사용하고, 큐마다 RR, FCFS 등의 스케줄링 알고리즘을 각자 적용하는 방법입니다.
  • 큐 사이의 프로세스 이동이 불가능하므로 유연성은 떨어지지만, 스케쥴링 부담이 적습니다.