교착상태

개념

프로세스들이 서로가 가진 자원을 요청하며 기다리는 상태

---

교착상태 발생 조건

1. 상호 배제

: 주어진 시간 안에 하나의 프로세스만 자원 사용이 가능하지만 그렇지 못한 경우

2. 점유대기

: 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있는 경우

3. 비선점

: 프로세스는 자원을 강제로 빼앗기지 않고 스스로 내놓는 특성때문에 발생 가능.
즉, 자원을 내놓지 않기 때문에 교착상태 발생
👉 자원을 빼앗기는 특성이 있었다면, 교착상태는 발생하지 X

4. 환형대기

: 자원을 기다리는 프로세스간에 사이클이 형성되는 경우
ex.
📍프로세스 $P_0, P_1, ..., P_n$이 있을 때
$P_0$은 $P_1$이 가진 자원을 기다림
🔻
$P_1$은 $P_2$가 가진 자원을 기다림
🔻
$P$n-1은 $P_n$이 가진 자원을 기다림
🔻
$P_n$은 $P_0$가 가진 자원을 기다림

---

해결방법

1. 자원 할당 시 위 조건이 성립되지 않도록 설계
   ⚠️ 어려움

2. 은행원 알고리즘 사용

3. 교착상태 발생 시 사이클이 있는지 확인 후 이와 관련된 프로세스를 한 개씩 지움

4. 교착상태 무시
   👉 교착상태 처리 비용이 크고 발생 가능성이 적기 때문에 프로세스 내에서 해결하지 않고 무시
   👉 사용자가 프로세스 종료 또는 대기를 선택할 수 있게 함

은행원 알고리즘

개념

교착상태를 회피하는 알고리즘으로 자원의 양에 따라 교착상태를 일으키지 않는 상태로 가도록 자원을 할당하는 알고리즘

구조

• available: 운영체제가 프로세스에게 줄 수 있는 자원 양
• max: 요청가능한 최대 자원 양
• need: 자원을 추가로 요구하는 양
• finish: 프로세스가 요청하는 양을 운영체제가 줄 수 있는지를 파악하는 불리언 배열

알고리즘 순서

1. 프로세스가 자원을 요청할 때, 시스템은 해당 자원이 요청 가능한지 확인

2. 요청이 가능하다면, 시스템은 요청한 자원을 일시적으로 할당한 뒤, 안전 상태를 유지하도록 확인

3. 안전 상태를 확인하기 위해 시뮬레이션을 수행하며, 자원을 반납하거나 할당할 수 있는지 판단

4. 안전 상태가 유지되면, 요청한 자원을 실제로 할당하고 프로세스를 실행. 만약 안전 상태가 유지되지 않으면 프로세스는 대기

예상 기술 질문!

🤔 Q. 은행원 알고리즘(Banker's Algorithm)은 무엇이며, 어떻게 교착상태를 방지하나요?
🙋‍♀️ A. 은행원 알고리즘은 교착상태를 방지하기 위한 알고리즘 중 하나로, 프로세스가 자원을 요청할 때마다 시스템이 안정 상태를 유지하면서 자원을 할당하는 방식입니다. 이는 시스템은 자원을 요청한 후의 상태를 가정하여 자원을 할당해보는 자원 할당 시뮬레이션을 통해 교착상태를 방지합니다.

---

CPU 스케줄링 알고리즘

개념

• CPU가 프로세스를 선택하는데 기준이 되는 알고리즘
• 가장 효율적인 프로세스 선택!

⭐ 효율적인 프로세스를 선택하기 위해 충족해야하는 조건

• CPU 사용률이 높은지
• 처리량이 높은지
• 프로세스 시작 전 대기 시간이 짧은지

1. 비선점형 알고리즘

개념

• 프로세스가 스스로 CPU를 포기하는 방식 👉 강제로 프로세스를 중지하지 않음!

종류

1) FCFS(First Come, First Service)

• 개념 : 먼저 온 것을 먼저 처리하는 순차적인 알고리즘
• 단점 : 먼저 온 프로세스 길이가 길면 다음 프로세스가 실행되는데 시간이 오래 기다리는 현상(convoy effect)이 발생

2) SJF(Shortest Job First)

• 개념 : 실행 시간이 가장 짧은 프로세스를 먼저 실행하는 알고리즘
• 단점 : 마지막에 실행되는(긴 시간을 가진) 프로세스가 실행되지 않는 현상(starvation) 발생 가능

3) 우선순위

• SJF의 starvation 현상을 보완하기 위해 오래된 작업일수록 우선순위를 높이는 aging 기법을 사용한 알고리즘

2. 선점형 알고리즘

개념

현대 운영체제가 쓰는 방식으로 알고리즘에 의해 강제로 다른 프로세스에 CPU를 할당하는 방식

종류

1) 라운드 로빈

• 개념 : 각 프로세스에 동일한 할당 시간을 주고 그 시간안에 끝나지 않으면 준비 큐 뒤로 가는 알고리즘
• 단점 : 할당 시간이 너무 짧으면 오버헤드가, 길면 FCFS로 동작하게된다는 단점이 있음

2) SRF(Shortest Remaining time First)

• 개념 : 프로세스 실행 시, 중간에 짧은 작업이 들어오면 수행하던 것을 중지하고 짧은 프로세스를 실행시킴
  👉 SJF의 선점형 버전이라고 생각하면 됨!

3) 다단계 큐

• 개념 : 우선순위에 따라 각 프로세스에 다른 알고리즘이 적용되는 방식
• 단점 : 우선순위가 낮은 프로세스 처리가 안되는 starvation 발생 가능

예상 기술 질문!

🤔 Q. CPU 스케줄링 알고리즘이란 무엇인가요? 어떤 목적으로 사용되나요?
🙋‍♀️ A. 다중 프로세스 환경에서 CPU의 할당 방식을 결정하는 방법을 말합니다. 어떤 프로세스에게 CPU를 할당할지, 언제 할당할지, 얼마나 오랫동안 할당할지 등을 결정하여 시스템 성능을 최적화하고, 응답 시간을 최소화하며, 자원 활용을 극대화하는 것이 목적입니다.