- Published on
OS : 프로세스 스케줄링
- Authors
- Name
- Bora Choi
프로세스 스케줄링
📝 스케줄링의 목적
다중 프로그래밍(multi-programming)
- 여러개의 프로세스가 시스템 내 존재
- 자원을 할당 할 프로세스를 선택해야 함 ⇒ 스케줄링(scheduling)
- 자원 관리
- 시간 분할(time sharing) 관리
- 하나의 자원을 여러 스레드들이 번가아 가며 사용 : 프로세서(processor)
- 프로세스 스케줄링(process scheduling) : 프로세서 사용 시간을 프로세스들에게 분배
- 시간 분할(time sharing) 관리
- 공간 분할(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
- 사용자모드에있는프로세스
- Kernel priority
- Clock handler
- 주기적으로 인터럽트 발생
- 모든 프로세스들의 우선순위 조정
- 스게줄링 기법
- 높은 우선순위 우선
- 프로세서 사용량에 따라 우선순위가 주기적으로 변함
- MFQ 스케줄링 기법
- 높은 우선순위 우선
- 우선순위 조정
- 프로세서 사용 반영 (decay computation)
- 𝑪𝑷𝑼𝑪𝒐𝒖𝒏𝒕 = 𝑪𝑷𝑼𝑪𝒐𝒖𝒏𝒕/ 𝟐
- 우선순위 조정
- 𝑷𝒓𝒊𝒐𝒓𝒊𝒕𝒚 = 𝑪𝑷𝑼𝑪𝒐𝒖𝒏𝒕 / 𝟐+ 𝒃𝒂𝒔𝒆𝑷𝒓𝒊𝒐𝒓𝒊𝒕𝒚 + 𝒏𝒊𝒄𝒆𝑽𝒂𝒍𝒖𝒆
- 프로세서 사용 반영 (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 → 약간 상향
- 상향 정도는 스레드가 대기중이었던 작업에 종속적