[운영체제] 프로세스 스케쥴링 알고리즘

🎧 프로세스 스케쥴링 평가 기준

1. CPU 이용률, CPU utilization

• 시간당 CPU를 사용한 시간의 비율
• 프로세서를 실행상태로 항상 유지하려고 해야 함

2. 처리율, Throughput

• 시간당 처리한 작업의 비율
• 단위 시간당 완료되는 작업 수가 많도록 해야 함

3. 반환시간, Turnaround time

• 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간
• 작업이 준비큐에서 기다린 시간부터 CPU에서 실행된 시간, I/O 작업 시간의 합

4. 대기시간, Waiting time

• 대기열에 들어와 CPU를 할당받기까지 기다린 시간
• 준비큐에서 기다린 시간의 총합

5. 반응시간, Response time

• 대기열에서 처음으로 CPU를 얻을 때까지 시간
• 대기시간과 비슷하지만 다른 점은, 대기시간은 준비큐에서 기다린 모든 시간을 합친 것이지만 반응 시간은 CPU를 할당받은 최초의 순간까지 기다린 시간 한번만을 측정한다

CPU 이용률과 처리율은 극대화
반환시간, 대기시간, 반응시간은 줄이자

🎧 프로세스 스케쥴링 알고리즘

1. First-Come, First-Served (FCFS)

• 비선점형
• CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받음
• First-In, First-Out 큐로 구현
• 구현은 매우 쉬움
• 단점:
  • 대기시간이 한없이 길어질 수 있음
  • 응답시간/평균 대기시간이 길어질 수 있음

2. Shortest-Job-First (SJF)

• 비선점형/선점형 가능
• Priority 스케쥴링의 종류
• 각 프로세스에 CPU burst길이를 남기도록 함 > 이용 가능해지면 Burst 시간이 가장 짧은 프로세스 할당
• 최소의 평균 대기 상태
• 단점:
  • CPU burst 시간은 어떻게 파악해야 하는가?
    • Burst time: total time that a process requires for its overall execution
    • 이전 CPU burst 시간을 기록 후 이후 시간 추측
    • 단기 스케쥴링에서는 사용하기 어려움. 장기 스케쥴링에 적합
  • 선점형일 경우에 현재 실행되고 있는 프로세스를 빼앗을 수도 있음: 새로운 프로세스가 들어올때 현재 실행되고 있는 프로세스보다 burst 시간이 짧으면
  • 무한봉쇄 가능성: 작업시간이 작은 프로세스가 계속 큐에 들어와 작업시간이 긴 프로세스가 무한히 연기되는 경우

3. Priority Scheduling

• 선점형/비선점형 가능
• 우선 순위 높은대로 배치
• 우선 순위 요건: 시간제한, 메모리 요구, 파일 수, 평균 I/O burst, 평균 CPU burst 등
• 단점:
  • 무한 봉쇄, indefinite blocking: 높은 우선순위의 프로세스가 꾸준히 들어옴 > 낮은 우선순위의 프로세스가 계속 순서가 밀리는 현상
  • 기아 상태, starvation: 특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태
• 해결방법: 노화, aging: 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킴

4. Round-Robin(RR) Scheduling

• 선점형
• 시분할 시스템을 위해 설계된 알고리즘:
  • 각각의 프로세스에 동일한 CPU할당 시간을 부여해서 해당 시간 동안만 CPU를 이용하게 한다
  • 할당 시간 내에 처리를 완료하지 못하면 다음 프로세스로 넘어가므로 선점형 방식
• FCFS + 시스템이 프로세스들 사이로 옮겨 다닐 수 있도록 선점성 추가
• 과정:
  • 시간 할당량/조각 정의하여 Ready queue를 circular queue로 만들어서 작동
    • 시간할당량, time quantum/시간 조각, time slice: 작은 단위의 시간
  • 스케쥴러는 하나의 프로세스를 선택해 일정 시간 이후에 인터럽트를 걸도록 타이밍 설정하고 dispatch
  • 프로세스는 작동하다가 시간 할당량 초과 시 현재 프로세스가 끝나지 않아도 다음 프로세스로 넘어감
    • 선점형
• 시간할당량이 매우 크면 FCFS와 같아짐
• 시간할당량이 매우 적으면 과도한 context switching > 오버헤드
  • 시간할당량은 context switching에 걸리는 시간보다 길어야 함
• 장점: 응답시간이 빠름

5. Multilevel queue scheduling

• 프로세스들을 몇몇 그룹으로 분리/활용하기 위한 스케쥴링 알고리즘
• 준비큐가 여러개의 큐로 나뉨: 각각의 스케쥴링 알고리즘
  • 프로세스를 메모리 크기/우선순위/메모리 등으로 분류 > 준비큐에 영구적 배정 (이동 불가)
• 큐와 큐 사이의 스케쥴링 필요 > 고정적 우선순위의 선점형 알고리즘 활용
• 프로세스가 영구적으로 오버헤드가 적으나 융퉁성 적음: 프로세스가 큐를 바꾸지 않음
• 기아문제 가능

6. Multilevel Feedback Queue Scheduling

• 선점형
• 큐를 여러개 둬서 우선순위 높은 프로세스에 먼저 RR(Round-Robin) 방식으로 CPU 할당
• time quantum만에 빨리 끝나면 I/O 사용자랑 interaction이 많은 프로세스는 우선순위 높은 상태 유지
• time quantum 내에 끝나지 않은 프로세스는 독식 가능성이 있으므로 낮은 큐로 단계적으로 내림
• 장점:
  • 설계중인 특성 시스템에 부합하도록 각각 큐의 조건 정의할 수 있음
  • 대응하기 쉬움
• 단점:
  • 좋은 스케쥴러로 동작하기 위해선 모든 매개변수들의 값을 선정해야 함
    • 매개변수: 큐의 수, 각각의 큐의 스케쥴링 알고리즘, 한 프로세스를 높은/낮은 우선순위를 갖고 있는 큐로 이동시키는 조건, 처음에 프로세스가 들어갈 큐를 결정할 조건
• Multilevel queue와 비슷하지만 각 큐 간에 프로세스들이 이동 가능

🎧 RR 사용 시 Time Slice에 따른 trade-off

RR의 성능은 시간 할당량의 크기에 매우 많은 영향을 받음

• 시간 할당량이 매우 크면 FCFS와 같아짐
• 시간 할당량이 매우 적으면 매우 많은 문맥 교환 야기

🎧 싱글 스레드 CPU에서 상시로 돌아가야 하는 프로세스 상황에 적합한 스케쥴링 알고리즘

싱글 스레드 CPU:

• 프로세스가 단일 스레드로 동작하는 방식
• 하나의 레지스터, 스택으로 표현
• 장점:
  • 멀티스레드와 같이 자원을 공유할 필요 X > 자원의 동기화 상관 없음
  • 문맥 교환 없음
• 단점:
  • CPU 코어를 모두 활용하지 못함: 하나의 물리적 코어밖에 사용하지 못해 멀티코어머신에서 CPU 사용을 최적화할 수 없음

싱글 스레드 CPU에서 상시로 돌아가는 프로세스에 적합한 스케쥴링 알고리즘:
멀티레벨 피드백 큐/RR을 사용하면 우선순위가 가장 높은 알고리즘부터 순차적으로 실행할 수 있음

🎧 동시성 vs. 병렬성

동시성, Concurrency:

• 목표: 유휴 시간의 최소화
  • 유휴 시간: 컴퓨터가 작동가능한데도 작업을 하지 않는 시간
• 동시에 실행되는 것 같이 보이는 것
• 싱글 코어에서 멀티스레드를 동작시키는 방식
• 한번에 많은 것을 처리
• 논리적인 개념
• 여러 task를 계속 번갈아가면서 실행
  • 벌아가면서 실행 > 자원 값이 계속 변경 > 서로의 실행 결과에 영향 될수도
• Race condition, deadlock, starvation 등의 문제 가능
  • Race condition: 두 개 이상의 프로세스/스레드가 공유 자원을 서로 사용하려고 경합하는 현상
    • 동시에 공유 자원에 접근할 수 있으면 자원의 일관성을 해치는 결과
    • 이를 방지하기 위해 상호 배제 조건을 만들어 놓음
  • Deadlock, 교착 상태: 공유 자원에 대한 요구가 엉켜서 자원관리를 잘못하여 프로세스나 스레드가 자원의 락을 획득하기 위해 무한대기
  • Starvation: 특정 프로세스가 우선순위가 낮아 원하는 자원을 계속 할당받지 못하는 현상

병렬성, Parallelism:

• 실제로 동시에 여러 작업이 처리되는 것
• 멀티 코어에서 멀티스레드를 동작시키는 방식
• 한번에 많은 일 처리
• 물리적인 개념

🎧 Multi-level Feedback Queue의 장점

1. 무한봉쇄: 작업시간이 작은 프로세스가 계속 큐에 들어와서 작업시간이 긴 프로세스가 무한히 연기
2. 기아 상태

우선순위가 낮은 프로세스의 우선순위를 주기적으로 boost하여 실행될 수 있도록 함

---

참고:

• [운영체제/OS] CPU Scheduling_ Multilevel Queue, Multilevel Feedback Queue 스케줄링
• [Operating System - Chapter 5] CPU 스케줄링
• 동시성 (Concurrency) vs 병렬성 (Parallelism)