[CS 스터디-OS] Deadlock/Starvation/CPU Scheduling

똘맹·2023년 3월 25일

CS 스터디

목록 보기
3/20
post-thumbnail

이 글은 반효경 교수님의 운영체제 강의 및 교재를 참고합니다.



1. Deadlock

Deadlock

Deadlock은 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상을 가리킨다. 서로가 가진 자원을 기다리며 block된 상태이기 때문이다.

Resource

Resource(자원)는 하드웨어, 소프트웨어를 포함하는 개념이다.

ex) I/O device, CPU cycle, memory space, semaphore

프로세스가 자원을 사용하는 절차

Request->Allocate->Use->Release

(1) Deadlock 발생 조건

Deadlock은 다음의 4가지 조건을 만족할 때 발생한다.

  • Mutual exclusion: 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.

  • No preemption: 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다.

  • Hold and wait: 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있다.

  • Circular wait: 자원을 기다리는 프로세스간에 사이클이 형성되어야 한다.

(2) Deadlock 상태 처리 방법

Deadlock에는 다음의 처리 방법을 적용할 수 있다. (순서: 적극적---->소극적)

  • Deadlock Prevention, Deadlock Avoidance, Deadlock Detection and recovery, Deadlock Ignorance

각각에 대해 알아보자.

Deadlock Prevention

자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

Deadlock 발생 조건에 따라, 다음과 같은 각각의 방식이 있을 수 있다.

  • Mutual Exclusion
    • 공유해서는 안되는 자원의 경우에는 만족할 수밖에 없다.
  • Hold and Wait
    • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않도록 한다.
      • 방법 1. 프로세스 시작 시, 모든 필요한 자원을 할당받게 한다.
      • 방법 2. 자원이 필요할 경우, 보유 자원을 모두 놓고 다시 요청하게 한다.
  • No Preemption
    • process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점되도록 하고, 모든 필요한 자원을 얻을 수 있을 때 해당 프로세스를 다시 시작한다.
    • State를 쉽게 save하고 restore 할 수 있는 자원에서 주로 사용한다.(CPU, Memory)
  • Circular Wait
    • 모든 자원 유형에 할당 순서를 정하여, 정해진 순서대로만 자원을 할당 할 수 있게 한다.
      • ex) 순서가 3인 자원을 보유 중인 프로세스가 순서가 1인 자원을 할당 받으려면, 기존의 순서 3 자원을 release 해야 한다.
  • 그런데 위의 Circular Wait 방식은 다음과 같은 상황의 Deadlock을 해결하지 못하지 않나?
프로세스 A: 자원 1, 3이 필요
프로세스 B: 자원 3이 필요
Allocation: 프로세스 A - 자원 3

이와 같은 상황에서 프로세스 A가 자원 1을 추가로 요청 + 프로세스 B가 자원 3을 요청한다면?

A가 자원 3을 놓고 자원 1을 잡는 사이 B가 자원 3을 홀랑 할당해버린다면?

(해결!) deadlock이 아니다!! 프로세스 B가 작업을 끝내면 프로세스 A가 작업을 할 수 있기 때문이다. 😭

나열한 모든 방법에 대해 Utilization 저하, throughput 감소, starvation 문제가 발생할 수 있다. 왜냐하면 Deadlock은 매우 드물게 발생하기 때문이다.

Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원 할당
시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

자원 요청에 대한 부가 정보를 이용해서 자원 할당이 deadlock으로부터 안전한지 동적으로 조사하고, 안전한 경우에만 할당한다.

프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방식이 가장 단순하고 일반적이다.

다음의 두 가지 avoidance 알고리즘이 존재한다.

  • Single instance per resource types: Resource Allocation Graph algorithm
  • Multiple instances per resource types: Banker's Algorithm

Deadlock Detection and recoverty

Deadlock 발생은 허용하되, 그에 대한 detection routine을 두어 deadlock 발견 시 recover

Resource Allocation Graph algorithm, Banker's Algorithm 을 사용하여 Deadlock 발생 여부를 판단하고, 만약 Deadlock이 발생한다면 Recovery 한다.

두 가지 방법이 있다.

  • Process termination: deadlock cycle 상의 모든 프로세스를 kill
  • Resource Preemption: 비용을 최소화할 victim을 선정하고 kill, safe state로 rollback 할 때까지 반복한 후 process를 재개

다만 Resource Preemption 방식에서는 동일한 프로세스가 계속해서 victim으로 선정되는 경우 Starvation 문제가 발생할 수 있다. cost factor에 rollback 횟수도 고려하는 편이 좋다.


Deadlock Ignorance

Deadlock을 시스템이 책임지지 않음

Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는다!

사실 Deadlock은 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead를 불러올 수 있다.

시스템에 deadlock이 발생한 경우, 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후에, 직접 process를 kill하는 방식으로 대처하면 된다.

UNIX, Windows 등 대부분의 범용 OS가 해당 방식을 채택하고 있다.



2. Starvation

(1) Starvation(기아 상태)란

특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태를 뜻한다.

deadlock과 연관지어 본다면, starvation이라고 해서 꼭 deadlock은 아니지만 deadlock은 반드시 starvation을 유발한다고 볼 수 있다.



3. CPU Scheduling

프로그램의 실행에서 CPU와 I/O bursts는 다음과 같이 발생한다.

그래서 프로세스는 특성에 따라 다음의 두 가지로 나누어진다.

  • l/O-bound process: CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job (many short CPU bursts)
  • CPU-bound process: 계산 위주의 job (few very long CPU bursts)

각각의 빈도는 다음과 같다.

이렇게 여러 종류의 process가 섞여 있기 때문에, CPU 스케줄링이 필요하다.

CPU Scheduler

Ready 상태의 프로세스 중 이번에 CPU를 줄 프로세스를 고른다.

Dispatcher

CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다. (context switch, 문맥 교환)

(1) CPU 스케줄링이란

CPU 스케줄링은 어떤 프로세스에 CPU를 배정할지 결정하고, 모든 프로세스가 공평하게 CPU를 점유할 수 있도록 하는 알고리즘을 의미한다. 쉽게 말해, CPU 스케줄링은 “시간”이라는 자원 아래에서 CPU 가 처리할 작업들의 일정과 계획을 세우는 것이라고 이해하면 된다.

CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다.

  1. Running -> Blocked（예: I/O 요청하는 시스템 콜）
  2. Running -> Ready（예: 할당시간만료로 timer interrupt）
  3. Blocked -> Ready（예: I/O 완료후 인터럽트）
  4. Terminate
  • 1, 4에서의 스케주링은 nonpreemptive (= 강제로 빼앗지 앉고 자진 반남)
  • All other scheduling is preemptive (= 강제로 빼앗음)

스케줄링은 Interactive job에게 적절한 response를 제공하고 CPU 및 I/O 장치 등의 시스템 자원을 효율적으로 사용할 수 있게 한다.

(2) 비선점형/선점형 스케줄링

CPU 스케줄링은 크게 선점형(Preemptive) 스케줄링과 비선점형(Non-Preemptive) 스케줄링으로 구분된다.

선점형 스케줄링은 필요한 경우 운영체제가 CPU의 자원 권한을 빼앗아 더 우선적인 프로세스의 작업으로 교체시킬 수 있는 방식이다. CPU가 어떤 프로세스에 의해 점유 중일지라도 우선 순위가 높은 프로세스가 들어오면 CPU를 차지할 수 있다. 우선 순위가 높은 프로세스를 빠르게 처리해야할 경우 유용하지만 오버헤드와 데이터 동기화 이슈를 해결해야 한다.

비선점형 스케줄링에서는 프로세스가 CPU를 점유하고 있는 경우 다른 프로세스가 CPU 자원을 빼앗을 수 없다. 작업 처리가 단순하고 일괄 처리 시스템에 적합하다. 모든 프로세스들에게 공정하며 응답 시간을 예측하기 쉽지만, 짧은 작업을 수행하는 프로세스라도 앞의 긴 작업이 종료될 때까지 기다려야 하는 경우가 발생한다.

(4) 스케줄링 알고리즘

FCFS(First-Come, First-Served)

  • 큐에 도착한 순서대로 CPU 할당
  • Starvation 현상 X
  • 호위 효과(Convoy Effect) 발생



SJF(Shortest-Job-First)

  • 수행 시간이 가장 짧은 작업 우선
  • 평균 대기 시간 🔻
  • Starvation 현상 O



HRN(Highest Response-ratio Next)

  • 우선순위를 계산하여 스케줄링
  • (우선순위) = (대기시간 + 실행 시간) / (실행 시간)



RR(Round Robin)

  • 할당 시간(Time Quantum)
  • 할당 시간이 끝나면 Ready Queue의 맨 뒤에 프로세스 삽입



SRTF(Shortest Remaining Time First)

  • SJF 개선
  • 현재 수행 중인 프로세스의 남은 시간 > 실행 시간을 만족하는 프로세스가 도착하면 CPU를 강제로 회수하여 할당



구분

📌 비선점형(Non-Preemptive) 스케줄링

  • FCFS (First-Come, First-Served)
  • SJF (Shortest-Job-First)
  • HRN (Highest Response-ratio Next)

📌 선점형(Preemptive) 스케줄링

  • RR (Round Robin)
  • SRTF (Shortest Remaining Time First)
profile
똘맹
척척학사가 되고 싶은 똘맹
이전 포스트

[CS 스터디-OS] 프로세스/쓰레드/동기화

다음 포스트

[CS 스터디-OS] Memory Management/Demand Paging

0개의 댓글