[운영체제 3기] 3주차 스터디 정리

🔹기아 상태(Starvation)

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

 

기아상태 해결 방안

• 프로세스 우선순위를 수시로 변경하여 각 프로세스가 높은 우선순위를 가지도록 기회를 부여한다.
• 오래 기다린 프로세스의 우선순위를 높인다.
• 우선순위가 아닌 요청 순서대로 처리하는 요청 큐 사용한다.

🔹CPU 스케줄링

CPU 스케줄링이란 어떤 작업에 CPU를 배정할지 결정하는 것이다.

스케줄링 규모에 따른 구분
발생하는 빈도 및 할당 자원에 따라 다음 3가지 스케줄링으로 구분된다.
- 장기 스케줄링(Long-term scheduling)

• 가장 큰 틀에서 이루어지는 CPU 스케줄링
• 고수준 스케줄링(high level scheduling), 작업 스케줄링(job scheduling) 또는 승인 스케줄링(admission scheduling)이라고도 한다.
• 시스템 내의 전체 작업 수 조절
• 전체 시스템 부하를 고려하여 작업 시작 여부 결정 (프로세스 수 결정)
  • 멀티 프로그래밍 정도(degree of multiprogramming)라고 한다.
• 최근 운영체제(OS)에서는 보통 장기 스케줄러가 없으며, 프로그램 실행 시 바로 준비(ready) 상태로 돌입한다.

- 중기 스케줄링(Mid-term scheduling)

• 장기와 단기 스케줄링 사이에서 발생하는 스케줄링
• 중간수준 스케줄링(middle level scheduling)이라고도 한다.
• 장기 스케줄링에서 활성화된 프로세스가 활성화된 이후에도 여러 예외 상황으로 인한 시스템 과부하 발생 시 프로세스의 활성 상태를 제어하는 스케줄링
• 메모리 할당 결정(Memory allocation)
  • Intermediate-level scheduling
  • Swapping(Swap-in / Swap-out)
• 프로세스의 중지(suspend)와 활성화(active) 상태를 제어하여 전체 시스템에 활성화된 프로세스 수 조절

- 단기 스케줄링(Short-term scheduling)

• 가장 작은 단위의 스케줄링
• 저수준 스케줄링(low level scheduling)이라고도 한다.
• 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 일
• 단기 스케줄러가 어떤 기준에 따라 프로세스를 선택(스케줄링 알고리즘)하고 어느 정도 자원을 배분(Time slice)할지에 따라 시스템에 큰 영향을 주기 때문에 가장 핵심 스케줄링이라고 할 수 있다.

스케줄링 목적

• 공평성: 프로세스 자원 분배 과정이 공평해야 함
• 효율성: 시스템 자원이 쉬는 시간이 없어야 함
• 안정성: 중요 프로세스들에게 우선권을 주어야함, 또한 프로세스 증가해도 시스템이 안정적으로 돌아가야 함
• 확장성: 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되어야 함
• 반응 시간 보장: 프로세스 요구가 있을 경우 적절한 시간 내에 반응해주어야 함
• 무한 연기 방지: 특정 프로세스 작업이 무한 연기되면 안됨
• 시스템 성능 향상
  • 대표적 시스템 성능 지표(index)
    1. 응답시간(response time): 작업 요청으로부터 응답 받을 때까지의 시간
    2. 작업 처리량(throughput): 단위 시간동안 완료된 작업 수
    3. 자원 활용도(resource utilization): 주어진 시간(Tc) 동안 자원이 활용된 시간(Tr)

스케줄링 기준(Criteria)

스케줄링 기법이 고려하는 항목들은 다음과 같다.

• 프로세스 특성: I/O-bounded or Compute-bounded
• 시스템 특성: Batch-system or Interactive system
• 프로세스 긴급성: Hard- or Soft- or Non- real time systems
• 프로세스 우선순위(Priority)
• 프로세스 총 실행시간
• 프로세스 위치: 전면 프로세스 or 후면 프로세스

🔹선점형 스케줄링 vs 비선점형 스케줄링

선점형 스케줄링(Preemptive scheduling)

다른 프로세스에 의해 자원을 빼앗길 수 있음

(e.g, Timeout(할당 시간 종료), 우선순위가 높은 프로세스 등장)

장점: Time-sharing system, real-time system 등에 적합 → 응답성 ↑

단점: Context switch overhead ↑

 

비선점형 스케줄링(Non-preemptive scheduling)

할당 받은 자원을 스스로 반납할 때까지 사용

(e.g, System call, I/O, etc.)

장점: Context switch overhead ↓

단점: 잦은 우선순위 역전, 평균 응답시간 ↑

🔹선입선출 스케줄링(FCFS, First-Come-First-Service)

Non-preemptive scheduling Time quantum(Time slice) 기준

FCFS는 먼저 도착한 프로세스(Ready Queue 기준)를 먼저 처리하는 스케줄링 방식이다.

일괄처리 시스템(Batch system)에 적합, 대화형 시스템(Interactive system)에 부적합

 

장점: 자원을 효율적으로 사용 가능(High resource utilization)

단점: Convoy effect ↑(Starvation 발생 O), 평균 응답 시간이 긺(Response time average ↑)

*. Convoy effect: CPU 사용시간이 긴 프로세스에 의해 CPU 사용시간이 짧은 프로세스들이 오래 기다리는 현상(대기 시간 >> 실행 시간)

🔹라운드 로빈 스케줄링(RR, Round-Robin)

Preemptive scheduling Time quantum(Time slice) 기준

FCFS와 유사하지만, 자원 사용 제한 시간(Time quantum or Time slice)이 존재한다.

RR은 한 프로세스가 할당 받은 시간 동안 작업하다가 시간이 끝나면 Ready Queue의 맨 뒤로 가서 자기 차례를 기다리는 방식이다.

대화형 시스템(Interactive system)과 시분할 시스템(Time-sharing system)에 적합

 

RR은 Time quantum이 시스템 성능을 결정하는 핵심 요소

- Time quantum ↑ : FCFS와 동일한 스케줄링이 된다. (Convoy effect↑, Starvation 발생 O)

- Time quantum ↓ : Processor Sharing(체감 프로세서 속도 = 실제 프로세서 성능의 1/n), Context Switching Overhead ↑

 

장점: Convoy effect ↓(CPU 일정 시간 사용 후 다른 프로세스에게 넘겨주어야 하므로, 자원 독점(monopoly) 방지 == Starvation X)

단점: RR과 FCFS의 평균 대기 시간이 동일하다면 RR이 더 비효율적 (RR은 Context switching overhead↑)

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

Non-preemptive scheduling 실행시간(Burst Time) 기준

SJF는 실행시간(Burst Time) 기준으로 가장 작은 프로세스를 먼저 처리하는 스케줄링 방식이다.

SJF는 SPN(Shortest-Process-Next)라고도 한다.

장점

- 평균 대기 시간(WT, Wating Time) 최소화 ↓

- 시스템 내 프로세스 수 최소화 ↓

- 많은 프로세스들에게 빠른 응답 시간(Response Time ↓)제공

단점

- Starvation(무한대기) 현상 발생 가능 (실행시간이 긴 프로세스는 자원 할당 받지 못할 수 있음)

- 정확한 실행시간(Burst Time)을 알 수 없음 (실행시간 예측 기법 필요)

🔹최소 잔류 시간 우선 스케줄링(SRTF, Shortest Remaining Time First)

Preemptive scheduling 실행시간(Burst Time) 기준

SRTF는 SJF의 변형, SJF + 선점(Preemption)을 의미한다.

즉, 잔여 실행 시간이 더 적은 프로세스가 준비(ready) 상태가 되면 선점(Preemption)이 된다.

장점: SJF의 장점 극대화

단점

- Starvation(무한대기) 현상 발생 가능

- 프로세스 생성 시, 총 실행 시간 예측 필요

- 잔여 실행 시간(BT)을 계속 추적해야 함 (Overhead ↑)

- Context Switching Overhead ↑

► 구현 및 사용이 비현실적

🔹최상 응답 비율 순서 스케줄링(HRRN, High-Response-Ratio-Next)

Non-preemptive scheduling 응답률(Response ratio) 기준

HRRN은 SJF의 변형, SJF + Aging을 의미한다.

Aging: 프로세스의 대기 시간(WT)를 고려하여 기회를 제공하는 것을 말한다.

장점: SJF의 장점 + Starvation 방지

단점: 실행시간(BT) 예측 기법 필요 (Overhead ↑)

🔹우선순위 스케줄링(Priority scheduling)

우선순위 스케줄링은 Ready Queue에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스에게 먼저 CPU를 할당하는 방식이다.

 

- 우선순위 동일 시 FCFS 스케줄링 사용

- Aging 기법 사용(대기 시간(WT)에 비례하여 우선순위를 부여해 무한대기(Starvation) 방지)

 

Non-preemptive scheduling

SJF 스케줄링: 실행 시간(BT)가 짧은 프로세스에게 높은 우선순위 부여

HRRN 스케줄링: 실행 시간(BT)이 짧거나 대기 시간(WT)이 긴 프로세스에게 높은 우선순위 부여

 

Preemptive scheduling

SRTF 스케줄링: 잔여 실행 시간(BT)이 더 적은 프로세스에게 높은 우선순위 부여

 

장점: 중요한 작업 우선 처리 가능

단점

- 가장 낮은 우선순위의 프로세스는 Starvation 발생 가능

- 우선순위 역전(Priority Inversion) 발생 가능

🔹멀티 레벨 큐 스케줄링(MLQ, Multi-level Queue)

MLQ는 작업(or 우선순위)별 별도의 Ready Queue를 가짐으로써 각각의 Queue에 다른 스케줄링을 적용하는 방식이다.

Queue 사이에는 우선순위 기반 스케줄링(Priority scheduling) 사용

Queue 구성은 정책에 따라 결정됨

동작 원리

- 각 Queue에서 RR 방식 사용

- 각 Queue의 우선순위(Priority) 변화 없음

- 높은 우선순위의 Queue의 모든 프로세스 작업들이 끝나야 낮은 우선순위 Queue의 프로세스들이 작업 진행 가능

 

장점

- 응답 시간 향상 (Response Time ↓)

- 다양한 종류의 작업 처리 가능(자신만의 Ready Queue를 가지고 있기 때문에 특정 작업별로 다양한 방식의 스케줄링 기법을 사용할 수 있음)

 

단점

- 여러 개의 Queue 관리 등에 의한 스케줄링 Overhead ↑

- 우선순위가 낮은 Queue의 프로세스들은 Starvation 발생 가능

- 새로운 작업이 들어왔을 때, 어느 Queue로 분류해야 할지 애매함 → 개선: MFQ

🔹멀티 레벨 피드백 큐 스케줄링(MFQ, Multi-level Feedback Queue)

MFQ는 프로세스의 Queue 간 이동이 허용된 MLQ를 말한다.

Feedback을 통해 우선순위(Priority) 조정

동작 원리

• 프로세스가 Ready Queue에 도착 시 우선순위가 가장 높은 Queue로 들어감
• 해당 Queue의 주어진 Time quentum에 따라 CPU 사용 후 작업이 완료된 프로세스는 종료됨
• CPU 사용 후에도 아직 작업이 끝나지 않은 프로세스는 원래의 Queue로 되돌아가지 않고 우선순위가 한 단계 낮은 Queue로 들어감(작업이 끝나지 않는 프로세스는 계속 우선순위가 낮은 Queue로 들어감)
• Queue마다 Time quentum(Time slice)를 다르게 주어 사용 (우선순위가 낮을수록 Time quentum이 커짐)
• 우선순위가 낮은 Queue일수록 Time quentum이 점점 증가하는데, 가장 우선순위가 낮은 Queue의 경우에는 FCFS(Time quentum 무한) 스케줄링이 적용됨

장점

- 응답 시간 향상 (Response Time ↓)

- 다양한 종류의 작업 효율적으로 처리 가능(e.g, CPU bounded 작업과 I/O bounded 작업을 분리하여 처리 가능)

- 공정성(낮은 Queue의 프로세스들도 일정 기간동안 CPU 할당을 받을 수 있도록 설계되어 있어, 우선순위가 낮은 프로세스들에게도 공정한 기회 제공 가능)

 

단점

- 설계 및 구현 복잡

- Starvation 문제 (일부 프로세스가 항상 높은 우선순위 Queue에 남아 있어, 낮은 우선순위 Queue의 프로세스들이 실행 기회를 제대로 얻지 못함)

- 여러 개의 Queue 관리 등에 의한 스케줄링 Overhead ↑

- 우선순위 역전(Priority Inversion) 발생 가능

*. 우선순위 역전(Priority Inversion): 높은 우선순위의 프로세스가 낮은 우선순위의 프로세스로 인하여 수행이 "Block" 되어있는 상태, 즉 높은 우선순위의 프로세스가 가장 늦게 완료되는 상황을 의미

 

https://velog.io/@underlier12/OS-24-%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C%EC%99%80-%EA%B8%B0%EC%95%84%EC%83%81%ED%83%9C

https://hpckoreatech.notion.site/Operating-System-CSE132-2023-b8aa98fe69cc4a8cb950051a04bc35ca

https://kjhoon0330.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81#2.1.1.%201)%20%EC%9E%A5%EA%B8%B0%20%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81%20(Long-term%20scheduler)

https://velog.io/@sunnamgung8/CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81

https://imbf.github.io/computer-science(cs)/2020/10/18/CPU-Scheduling.html

https://ddongwon.tistory.com/31

https://codingrapper.tistory.com/124

https://j-i-y-u.tistory.com/21

https://sunny-jang.tistory.com/32