운영체제 정리(4)-Process Scheduling과 Race Condition

 

IPC(Inter Process Communication)

프로세스는 각각 개별 메모리를 가지고 있기 때문에, 다른 프로세스와 통신하거나 데이터를 공유하고 싶을 때는 커널에서 제공하 는통신 설비가 필요하다. 프로세스간 통신 방법은 크게 두 가지 모델이 있다.

 

Message passing

커널의 중계를 통해 프로세스 간 메세지를 전달하는 방식의 총칭이다. message passing 이란 개념 안에서도 pipe, message queue 등의 통신 방법으로 분류할 수 있다. message passing 방식은 데이터를 전송할 때마다 시스템 콜을 호출(커널의 중계를 거침)하기 때문에 그에 따른 오버헤드가 있지만, 그만큼 상대적으로 안전하고(명시적 통신) 오류 발생 가능성이 낮다.

 

공유메모리

스레드는 프로세스 내에서 메모리 공간을 공유하지만, 프로세스는 개별의 보호되는 메모리 공간을 가진다. 그렇기에 메모리 공간을 공유하려면 커널에게 공유 메모리를 할당해 줄 것을 요청하는데, 이렇게 할당받은 메모리 공간은 모든 프로세스가 접근할 수 있다. 
공유 메모리 방식은 중개자 없이 메모리에 곧바로 접근할 수 있어서 IPC 중에 가장 빠르게 작동한다. 그렇지만 여러 프로세스가 동일한 메모리에 접근할 수 있는 만큼, 프로세스 간 동기화 문제가 발생한다. 이는 세마포어, 뮤텍스 등으로 반드시 처리해 줘야 한다.

 

 

CPU 스케줄링

운영체제가 CPU를 잘 사용하기 위해 프로세스에게 CPU를 효율적으로 할당하는 방식이다.
스케줄링 알고리즘을 분류하는 여러 기준이 있지만, 크게 선점형과 비선점형 스케줄링으로 볼 수 있다.
선점형 스케줄링은 '선점이 가능한' 즉 '빼앗을 수 있음'을 뜻하고, 비선점형 스케줄링은 '빼앗을 수 없음' 을 뜻한다.

선점형 스케줄링

선점형 스케줄링에는 인터럽트와 같이 현재 CPU가 할당된 프로세스로부터 점유를 빼앗아 다른 프로세스에 할당시키는 방식이 포함된다. 이러한 스케줄링 알고리즘에는 RoundRobin, SRTF, Priority 스케줄링, 다단계 큐, 다단계 피드백 큐 등이 포함된다.

• Round Robin (RR): 정해진 시간(타임 퀀텀) 동안 프로세스를 실행하고, 시간이 다 되면 준비 큐의 다음 프로세스에게 CPU를 넘기는 방식 (시분할 시스템에 적합).
• SRTF (Shortest Remaining Time First): SJF의 선점형 버전으로, 현재 실행 중인 프로세스와 새로 도착한 프로세스 중 남은 시간이 더 짧은 프로세스에게 CPU 할당.
• Priority Scheduling (선점형): 우선순위가 더 높은 프로세스가 실행 중인 프로세스의 CPU를 빼앗아오는 방식.
• MLQ (Multi-Level Queue): 프로세스를 여러 개의 큐(예: 시스템, 대화형, 배치)로 나누고, 각 큐에 다른 스케줄링 알고리즘을 적용하는 방식.
• MLFQ (Multi-Level Feedback Queue): 여러 개의 큐와 우선순위를 사용하며, 프로세스의 실행 패턴에 따라 큐를 이동시켜 기아 현상을 완화하는 방식

비선점형 스케줄링

비선점형 스케줄링은 CPU 를 할당받은 프로세스가 종료, 또는 자발적으로 대기 상태에 들어가기 전까지 는 계속 CPU 를 점유하는 방식이다. 이러한 스케줄링 알고리즘에는 FCFS, SJF, HRN 등이 있다.

• FCFS (First Come, First Served): 먼저 도착한 프로세스가 먼저 CPU를 할당받는 가장 간단한 방식 (FIFO).
• SJF (Shortest Job First): 준비 큐에서 실행 시간이 가장 짧은 프로세스에게 CPU를 먼저 할당 (최단 작업 우선).
• HRN(Highest Response Ratio Next): 우선순위를 추가하여 SJF 에서 발생하는 점유 불평등을 보완한 방식
  (우선순위 = [대기시간+실행시간/실행시간])

여러 스케줄링 알고리즘 중 효과적인 알고리즘을 선택해야 한다. 이러한 선택 기준에는 대기시간(waiting time), 응답 시간(response time), 반환 시간(turnaround time), 처리량(throughput) 등의 지표가 있으며, 컴퓨터 또는 시스템의 목적에 맞는 스케줄링 알고리즘을 선택하여야 한다.

• 처리량 (Throughput): 단위 시간당 완료되는 프로세스의 수 (작업 처리량).
• 반환 시간 (Turnaround Time): 프로세스 도착부터 완료까지 걸리는 총 시간 (대기 시간 + 실행 시간).
• 대기 시간 (Waiting Time): 프로세스가 준비 큐에서 기다리는 시간.
• 응답 시간 (Response Time): 요청 후 첫 응답이 나올 때까지 걸리는 시간 (대화형 시스템에 중요).

 

 

데드락(교착 상태)

운영체제에서 말하는 교착 상태의 정의는 두 개 이상의 프로세스나 스레드가 상대방이 점유하고 있는 자원을 무한정 기다리면서 대기 상태에서 빠져나오지 못하고 있는 상태를 말한다. 데드락은 다음과 같은 상태에서 발생한다.

t1: 프로세스 a가 자원1을 얻음/ 프로세스 b가 자원2를 얻음
t2: 프로세스 a 가 자원2를 기다림/ 프로세스 b가 자원1을 기다림

-> 데드락 발생

 

데드락 발생 조건

교착 상태는 다음과 같이 4 가지 조건이 모두 성립해야 발생한다. 하나라도 성립하지 않으면 교착 상태에 빠지지 않는다.

1. 상호 배제 (Mutual Exclusion): 자원은 한 번에 하나의 프로세스만 사용할 수 있음.
   (자원이 공유 가능하면 교착 상태에 빠질 일이 없음)
2. 점유와 대기 (Hold and Wait): 자원을 점유한 프로세스가 다른 자원을 요구하며 대기함.
   (Hold 하지 않고 대기한다면 언젠가 자기 차례가 옴)
3. 비선점 (No Preemption): 프로세스가 점유한 자원은 강제로 빼앗을 수 없음.
   (선점(강제로 빼앗음)이 가능하다면 교착 상태에 빠질 일이 없음)
4. 순환 대기 (Circular Wait): 프로세스들이 자원을 요청하는 순환 고리가 형성됨
   (점유하고 있는 자원을 기다리는 쪽이 점유하고 있는 또다른 자원을 누군가가 기다리는 순환의 고리가 만들어 질 때 교착상태가 발생함)
   

데드락 해결 방법

교착 상태를 해결하는 주요 접근 방식은 다음과 같다.

• 예방 (Prevention): 교착 상태 발생 조건 4가지 중 하나 이상이 충족되지 않도록 시스템을 설계 단계에서 제약하는 방법. 예를 들어, 프로세스가 필요한 모든 자원을 한꺼번에 요청하도록 하거나(점유와 대기 방지), 자원에 순서를 부여하여 순환 대기를 방지할 수 있다.
• 회피 (Avoidance): 실행 중에 시스템의 상태를 지속적으로 검사하여 교착 상태가 발생할 가능성이 있는 자원 할당 요청을 거부하는 동적인 전략. 대표적인 알고리즘으로 은행원 알고리즘(Banker's Algorithm)이 있다.
• 탐지 및 복구 (Detection and Recovery): 교착 상태 발생을 허용하되, 주기적으로 시스템 내 교착 상태 발생 여부를 확인하고, 탐지되면 관련 프로세스를 강제 종료하거나 자원을 선점하여 복구하는 방법.
• 무시 (Ignorance): 교착 상태가 매우 드물게 발생한다고 가정하고 별다른 조치를 취하지 않는 방법으로, 대부분의 범용 운영체제(Windows, UNIX 등)는 이 접근 방식을 사용한다.

 

 

Race Condition(경합 상태)

운영체제에서의 경합 상태는, 둘 이상의 프로세스 또는 스레드가 공유 자원에 접근하면서 예상치 못한 실행 결과를 가져올 수 있는 상황을 말한다. 즉, 공유 자원에 대해 일관성(정합성)이 깨지는 상태이다.

운영체제에서 말하는 Race Condition 의 경우, 일반적으로 공유 자원은 커널 메모리의 데이터를 뜻한다. 커널 공간의 데이터는 일반적으로 모든 프로세스가 접근할 수 있는 공유 자원이다. 따라서 대부분의 경합 상태는 아래와 같은 상황에서 발생한다.

1. 특정 프로세스가 커널 모드에서 작업 중일 때, 인터럽트가 발생하여 다른 프로세스가 같은 데이터에 접근하는 경우
2. 프로세스가 커널 모드로 진입하여 작업 중일 때 Context Switch가 발생할 경우
3. 멀티프로세서 환경에서 2개 이상의 CPU가 동시에 공유 메모리 내의 커널 데이터에 접근할 경우

이처럼 일반적으로 운영체제에서 말하는 Race Condition 이란 공유 자원인 커널 데이터에 다수의 프로세스나 스레드가 접근하면서 발생한다.

따라서 커널 모드의 공유 데이터는 이러한 경합 상태를 예방하기 위해 인터럽트 비활성화, 상호 배제 등의 전략을 사용한다.

• 인터럽트 비활성화: 커널 코드가 수행되는 동안 인터럽트가 발생하지 않도록 하여 경쟁 상태를 방지하는 방법. 단, 너무 긴 시간 동안 사용하면 시스템 지연을 초래할 수 있다.
• 상호 배제: 한 번에 하나 또는 정해진 수의 프로세스(스레드)만 공유 자원에 접근하도록 보장하는 전략. 뮤텍스(Mutex), 세마포어(Semaphore) 등이 있다.

 

뮤텍스와 세마포어 

뮤텍스와 세마포어는 모두 운영체제의 Race Condition을 방지하기 위해 공유 자원의 접근을 제어하는 대표적인 동기화 도구이지만, 그 목적과 사용 방식에 명확한 차이가 존재한다.

1. 뮤텍스(Mutex)

뮤텍스는 Mutual Exclusion(상호 배제)의 약자로, 이름 그대로 단 하나의 스레드 또는 프로세스만이 공유 자원에 접근할 수 있도록 보장하는 데 사용된다.

• 자원 관리: 관리하는 공유 자원의 개수가 항상 1개로 제한된다. (이진 동기화)
• 소유권: 소유권 개념이 명확하다. 자물쇠(Lock)를 획득한 스레드만이 해당 자물쇠를 해제(Unlock)할 수 있다. 소유자가 아닌 다른 스레드가 해제를 시도하면 오류가 발생한다.
• 활용: 프린터 포트, 특정 데이터베이스 레코드 등과 같이 배타적인 단독 사용이 필수적인 자원을 보호할 때 주로 활용된다.

2. 세마포어(Semaphore)

세마포어는 뮤텍스와 달리 공유 자원에 대한 접근을 수량 기반으로 제어한다.

• 자원 관리: S라는 정수 변수를 사용하여 현재 접근 가능한 공유 자원의 **수량(카운터)**을 나타낸다. 이 카운터는 0 이상의 값을 가지며, 여러 스레드가 동시에 접근할 수 있다.
• 소유권: 소유권 개념이 없다. 자원을 사용하려는 스레드는 Wait(또는 P 연산)으로 카운터를 감소시키고, 사용 후에는 Signal(또는 V 연산)로 카운터를 증가시킨다. 락을 획득하지 않은 스레드도 Signal 연산을 수행할 수 있다.
• 활용: 생산자-소비자 문제에서 버퍼의 빈 공간 개수 관리, 동시에 접속 가능한 클라이언트 수 제한 등 여러 개의 동일한 자원을 관리할 때 유용하게 사용된다.
  

요컨대 뮤텍스는 단일 자원에 대한 배타적 접근을 보장하는 데 초점을 맞추고, 세마포어는 N개의 자원에 대한 가용 수량을 관리하는 데 초점을 맞춘다. 이런 면에서 뮤텍스를 자물쇠(하나의 자원 관리), 세마포어를 주차장 카운터(정해진 다수의 자원 관리)에 비유할 수 있다.이 두 가지 동기화 기법은 운영체제 커널의 데이터 무결성을 보장하고 경합 상태로 인한 시스템 오류를 방지하는 데 필수적인 역할을 한다. 뮤텍스를 다른 말로 이진 세마포어(0과 1, lock과 unlock의 두 가지 상태로 표현되므로)로 표현하기도 한다.