프로세스 스케줄링

📝 스케줄링의 목적

다중 프로그래밍(multi-programming)

여러개의 프로세스가 시스템 내 존재
자원을 할당 할 프로세스를 선택해야 함 ⇒ 스케줄링(scheduling)
자원 관리
- 시간 분할(time sharing) 관리
  - 하나의 자원을 여러 스레드들이 번가아 가며 사용 : 프로세서(processor)
  - 프로세스 스케줄링(process scheduling) : 프로세서 사용 시간을 프로세스들에게 분배
공간 분할(space sharing)관리
- 하나의 자원을 분할하여 동시에 사용 : 메모리(memory)

스케줄링(scheduling)의 목적

시스템 성능(performance) 향상
대표적 시스템 성능 지표(index)
- 응답시간(response time) : 작업 요청(submission)으로부터 응답을 받을때까지의 시간
- 작업 처리량(throughput) : 단위 시간 동안 완료된 작업의 수
- 자원 활용도(resource utilization) : 주어진 시간(Tc)동안 활용된 시간(Tr) : U= Tr/Tc
목적에 맞는 지표를 고려하여 스케줄링 기법을 선택

시스템 성능 지표들

평균 응답시간(mean response time) : 사용자 지향적
처리량(throughput) : 시스템 지향적
자원 활용도(resource utilization)
공평성(fairness)
실행 대기 방지 : 무기한 대기 방지
예측 가능성(predictablity) : 적절한 시간 안에 응답을 보장하는 가
등

대기시간, 응답시간, 반환시간

대기시간 (wating time) : 프로세스가 도착해서 실행 시작전까지 기다리는 시간
응답시간 (response time) : 프로세스가 도착해서 첫번째 응답을 받을때까지 시간
실행시간 (burst time) : 실제로 프로세스가 실행된 시간
반환 시간 (turn-around time) : 도착을해서 종료까지의 시간

🎢 스케줄링 기준 및 단계

스케줄링 기준(criteria)

스케줄링 기법이 고려하는 항목들

프로세스(process)의 특성
시스템 특성
프로세스의 긴급성 (urgency)
프로세스 우선순위 (priority)
프로세스 총 실행 시간 (total service time)

CPU burst vs I/O burst

프로세스 수행 = CPU 상용 + I/O 대기
CPU burst : CPU 사용 시간
I/O burst : I/O 대기 시간
Burst time은 스케줄링의 중요한 기준 중 하나

compute-bonded process : CPU burst > I/O busrst
I/O-bonded process : I/O busrst > CPU burst

스케줄링의 단계 (Level)

발생하는 빈도 및 할당 자원에 따른 구분 Long-term scheduling

job scheduling : 시스템에 제출 할(kernel에 등록 할) 작업 결정
- Admission scheduling, High-levle scheduling
다중 프로그래밍 정도(degree) 조절 : 시스템 내에 프로세스 수 조절
I/O-bounded와 compute-bouded 프로세스들을 잘 섞어서 선택해야 함
- 왜? 시스템의 효율을 높이기 위해
시분할 시스템에서는 모든 작업을 시스템에 등록
- Long-term scheduling이 불필요

Mid-term scheduling

메모리 할당(memory allocation)
- Intermediate-level scheduling
- Swapping(swap-in/swap-out)

Short-term scheduling

✴️ Process scheduling : CPU 할당
- low-level scheduling
- 프로세서(processor)를 할당할 프로세스(process)를 결정 : Processor scheduler, dispatcher
가장 빈번하게 발생
- interrupt, block(I/O), time-out, etc.
- 매우 빨라야 함

👨‍⚖️ 스케줄링 정책

선점 / 비선점 (Preemptive/Non-Preemptive scheduling)

Non-Preemptive scheduling

할당 받은 자원을 스스로 반납할 때까지 사용
장점 context switch overhead가 적음
단점 잦은 우선순위 역전, 평균 응답 시간 증가

Preemptive scheduling

타의에 의해 자원을 빼앗길 수 있음

장점 응답성이 높음

Time-sharing system, real-time system 등에 적합

단점 context switch overhead가 큼

Priority

프로세스의 중요도

static priority(정적 우선순위)
- 프로세스 생성시 결정된 priority가 유지 됨
- 구현이 쉽고, overhead가 적음
- 시스템 환경 변화에 대한 대응이 어려움
Dynamic priority(동적 우선순위)
- 프로세스의 상태 변화에 따라 priority 변경
- 구현이 복잡, priority 재계산 overhead가 큼
- 시스템 환경 변화에 유연한 대응 가능

📅 기본 스케줄링 알고리즘들

FCFS(First-Come-First-Service)

Non-preemptive scheduling
스케줄링 기준(criteria)
- 도착시간(ready queue 기준)
- 먼저 도착한 프로세스를 먼저 처리
자원을 효율적으로 사용 가능
- High resource utilization / 왜? 스케줄링 오버해드가 적다
Batch system에 적합, interactive system에 부적합
단점
- convoy effect : 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상(대기시간>>실행시간)
- 긴 평균 응답시간(response time)

RR(Round-Robin)

Preemptive scheduling
스케줄링 기준(criteria)
- 도착시간(ready queue 기준)
- 먼저 도착한 프로세스를 먼저 처리
자원 사용 제한 시간(time quantum)이 있음
- system parameter(δ)
- 프로세스는 할당된 시간이 지나면 자원 반납 : timer-runout
- 장점 특정 프로세스의 자원 독점(monopoly) 방지
- 단점 context siwtch overhead가 큼
대화형, 시분할 시스템에 적합
Time quantum (제한시간)(δ) 이 시스템 성능을 결정하는 핵심 요소
- Very large (infinite) δ → FCFS
- Very small time quantum → processor sharing
  - 사용자는 모든 프로세스가 각각의 프로세서 위에서 실행되는 것 처럼 느낌 : 체감 프로세서 속도 = 실제 프로세서 성능의 1/n
  - High context switch overhead

SPN(Shrtest-Process-Next)

Non-preemptive scheduling
스케줄링 기준 (Criteria)
- 실행시간 (burst time 기준)
- Burst time 가장 작은 프로세스를 먼저 처리 : SJF(Shortest Job First) scheduling
장점
평균 대기시간(WT) 최소화
시스템 내 프로세스 수 최소화
- 스케줄링 부하 감소 , 메모리 절약 → 시스템 효율 향상
많은 프로세스들에게 빠른 응답 시간 제공

단점

Starvation (무한대기) 현상 발생
- BT가 긴 프로세스는 자원을 할당받지 못할 수 있음 : Aging 등으로 해결 (e.g., HRRN)
정확한 실행 시간을 알 수 없음 : 실행 시간 예측 기법이 필요

SRTN(Shortest Remaining Time Next)

SPN의 변형
Preemptive scheduling
- 잔여 실행 시간이 더 적은 프로세스가 ready상태가 되면 선점됨

장점

SPN의 장점 극대화

단점

프로세스 생성시, 총 실행 시간 예측이 필요함
잔여 실행을 계속 추적해야 함 = overhead
Context switching overhead

⇒ 구현 및 사용이 비현실적

HRRN(High-Response-Ratio-Next)

SPN의 변형
- SPN + Aging concepts, Non-preemptive scheduling
Aging concepts
- 프로세스의 대기 시간(WT)을 고려하여 기회를 제공
스케줄링 기준 (Criteria)
- Response ratio가 높은 프로세스 우선
𝑹𝒆𝒔𝒑𝒐𝒏𝒔𝒆 𝒓𝒂𝒕𝒊𝒐 = (𝑾𝑻+𝑩𝑻)/𝑩𝑻 (응답률)
- SPN의 장점 + Starvation 방지
- 실행 시간 예측 기법 필요 (overhead)

MLQ(Multi-levelQueue)

작업 (or 우선순위)별 별도의 ready queue를 가짐
- 최초 배정 된 queue를 벗어나지 못함
- 각각의 queue는 자신만의 스케줄링 기법 사용
Queue 사이에는 우선순위 기반의 스케줄링 사용
- E.g., fixed-priority preemptive scheduling

장점

빠른 응답시간 (?) : 중요도가 높은 일은 응답시간이 빠르다

단점

여러 개의 Queue 관리 등 스케줄링 overhead
우선순위가 낮은 queue는 starvation 현상 발생 가능

MFQ(Multi-level Feedback Queue)

프로세스의 Queue간 이동이 허용된 MLQ
Feedback을 통해 우선 순위 조정
- 현재까지의 프로세서 사용 정보(패턴) 활용
특성
- Dynamic priority
- Preemptivescheduling
- Favor short burst-time processes
- Favor I/O bounded processes
- Improveadaptability
프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN 기법의효과를볼수있음

단점

설계 및 구현이 복잡, 스케줄링 overhead가 큼
Starvation문제등

변형

각 준비 큐마다 시간 할당량을 다르게 배정
- 프로세스의 특성에 맞는 형태로 시스템 운영 가능
입출력 위주 프로세스들을 상위 단계의 큐로 이동,우선 순위 높임
- 프로세스가 block될 때 상위의 준비 큐로 진입하게 함
- 시스템 전체의 평균 응답 시간 줄임,입출력 작업 분산 시킴
대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동
- 에이징 (aging) 기법
Parameters for MFQ scheduling
- Queue의 수
- Queue별 스케줄링 알고리즘
- 우선순위조정기준
- 최초 Queue 배정 방법
- ...

📖 Case Study : scheduling in OS

🐧 Scheduling in Unix Systems

Interactive system
- Priority-based scheduling, preemptive scheduling
Priority
- Kernel priority
  - 커널모드에있는프로세스
  - interruptible/uninterruptible priority
- User priority
  - 사용자모드에있는프로세스
Clock handler
- 주기적으로 인터럽트 발생
- 모든 프로세스들의 우선순위 조정
스게줄링 기법
- 높은 우선순위 우선
  - 프로세서 사용량에 따라 우선순위가 주기적으로 변함
- MFQ 스케줄링 기법
우선순위 조정
- 프로세서 사용 반영 (decay computation)
  - 𝑪𝑷𝑼𝑪𝒐𝒖𝒏𝒕 = 𝑪𝑷𝑼𝑪𝒐𝒖𝒏𝒕/ 𝟐
- 우선순위 조정
  - 𝑷𝒓𝒊𝒐𝒓𝒊𝒕𝒚 = 𝑪𝑷𝑼𝑪𝒐𝒖𝒏𝒕 / 𝟐+ 𝒃𝒂𝒔𝒆𝑷𝒓𝒊𝒐𝒓𝒊𝒕𝒚 + 𝒏𝒊𝒄𝒆𝑽𝒂𝒍𝒖𝒆

🪟 Scheduling in windows

Thread scheduling
Priority-based, Preemptive scheduling
32-level priority scheme
- Variable class: 1-15
- Real-time class: 16-32
MLQ scheduling
- 각각의 우선순위 마다 큐(queue)를 가짐
- 스케줄러(scheduler)는 높은 우선순위 큐부터 순차적 으로 방문하며, 실행할 준비가 된 스레드를 찾음
스케줄링 기법
- 스레드가 자신의 time quantum을 다 소비하고 나올때 →우선순위 하향 조정 (variable class의 경우)
- Wake-up 시→우선순위 상향 조정 (variable class의 경우)
  - 상향 정도는 스레드가 대기중이었던 작업에 종속적
    - 예) 키보드/마우스 I/O→크게 상향 디스크 I/O → 약간 상향