Process Scheduling

스케줄링 목적

• 왜 프로세스 스케줄링을 해야 하는가?
• 여러 개의 프로세스가 시스템 내 존재하는 환경 속에 자원을 할당할 프로세스를 선택해야 함.
• 이걸 스케줄링, 자원 관리라 함.
• 자원 관리에는 2가지가 있음.
• 시간 분할 관리
• 하나의 자원을 여러 스레드들이 번갈아 가며 사용.
• 프로세스 스케줄링, 프로세서 사용 시간을 프로세스들에게 분배.
• 공간 분할 관리
• 하나의 자원을 분할하여 동시에 사용.
• ex) 메모리.
• 시스템 성능 향상.
• 성능에 대한 객관적인 지표가 있음.
• 응답 시간
• 얼마나 빨리 걸리는지.
• ex) interactive systems
• 작업 처리량
• 얼마나 많이 처리하는지.
• ex) batch systems
• 자원 활용도
• 얼마나 놀지 않고 일할 수 있는지.
• 특히 가격이 중요할 때 사용.
• 공평성
• 실행 대기 방지
• 예측 가능성
• 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택해야 함.

스케줄링 기준

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

• 프로세스의 특성
• I/O-bounded (I/O burst): I/O 대기 시간이 더 많아 I/O가 성능을 결정함.
• compute-bounded(cpu burst) : CPU 사용 시간이 더 많아 CPU가 성능을 결정함.
• 어디에 시간을 더 많이 쓰게할지에 따라 성능이 결정됨. 프로세스 수행은 cpu 사용 + I/O 대기 (사용)임.
• burst time은 스케줄링의 중요한 기준 중 하나임.

• 시스템 특성
• batch system : 일괄 처리 시스템
• interactive system : 대화형 시스템
• 이 둘은 목적이 다르기 때문에 어떤 걸 선택할지는 목적에 따라 달라짐.

• 프로세스의 긴급성
• 누가 더 급한지에 따라 올릴지 결정.

• 프로세스 우선순위

• 프로세스 총 실행 시간

스케줄링 단계 (Level)

• 발생하는 빈도 및 할당 자원에 따라 구분함.

• Long-term scheduling



• 장기 스케줄링, 긴 시간동안 가끔 일어남.
• ex) job scheduling - 시스템에 제출할 (kernel에 등록할) 작업(job) 결정.
• 다중 프로그래밍 정도(degree) 조절, 시스템 내 프로세스 수 조절.
• 그렇다면 누구를 올려줄까 했을 때 I/O bounded와 compute-bounded 프로세스들을 잘 섞어서 선택해야 함. 효율적이려면 두 개가 모두 일하는 상태로 만들어야 하기 때문.
• 테스크를 잘게 쪼개는 시분할 시스템은 모든 작업을 시스템에 등록하므로 오래동안 대기해야 하는 것들을 관리하는 long term scheduling이 덜 필요함.

• Mid-term scheduling



• 중기 스케줄링, 종종 일어남.
• ex) memory allocation : 누구한테 메모리를 줄지 결정.

• Short-term scheduling



• 단기 스케줄링, 자주 일어남.
• 자주 일어나기 때문에 효율적으로 동작해야 함 (매우 빨라야 함).
• ex) process scheduling

스케줄링 정책

• 선점(Preemptive scheduling) vs 비선점 (None-Preemptive scheduling)
• 비선점
• 빼앗을 수 없다.
• 할당 받을 자원을 스스로 반납할 때까지 사용.
• Context switch overhead가 적다는 장점이 있지만 급한 일(우선순위가 높은 일)을 먼저 처리하지 못함 (우선 순위 역전 현상). 평균 응답 시간 증가.
• 선점
• 빼앗을 수 있다.
• 타인에 의해 자원을 빼앗길 수 있음. ex) 할당 시간 종료, 우선순위가 높은 프로세스 등장.
• Context switch overhead가 크다는 단점이 있지만 응답성이 높아진다는 장점이 있음. time-sharing system, real-time system 등에 적합함.

• 우선순위
• static priority
• 장점 ) 구현이 쉽고, overhead가 적음.
• 단점 ) 시스템 환경 변화에 대한 대응이 어려움.
• 도장같은 존재.
• dynamic priority
• 단점 ) 구현이 복잡, priority 재계산, overhead가 큼.
• 장점 ) 시스템 환경 변화에 유연한 대응 가능.
• 연필로 쓰고 지울 수 있는 존재.

스케줄링 기본 알고리즘

• FCFS (first-come-first-service)
• ready queue 기준 먼저 오는 프로세스 처리 (선착순).
• None-Preemptive scheduling.
• 퍼포먼스를 높이는 게 목적인 batch system에 적합.
• 장점 ) overhead가 줄어듦. 자원을 효율적으로 사용 가능.
• 단점 ) convoy effect (대기 시간 > 실행 시간), 긴 평균 응답 시간.

• RR (Round-Robin)
• Preemptive scheduling.
• 제한 시간을 가진 상태에서 먼저 도착한 프로세스를 처리.
• 제한 시간이 시스템 성능을 결정하는 핵심 요소. 제한 시간이 무한대라면 FCFS가 되고, 0에 수렴한다면 프로세스를 동시에 쓰는 processor sharing이 됨.
• interactive system, 시분할 시스템에 적합.
• 장점 ) 특정 프로세스의 자원 독점 방지.
• 단점 ) context switch overhead가 큼.

• SPN (Shortest-Process-Next)
• None-Preemptive scheduling.
• 짧은 애(Burst time이 낮은 프로세스) 먼저 처리하자.
• 스케줄링 기준이 실행시간임 (SJF Shortest Job First scheduling).
• ex) 마트에 있는 소량 계산대
• 장점
• 평균 대기시간 (WT) 최소화.
• 들고 있어야 하는 게 적으니 스케줄링 부하 감소, 메모리 절약을 통한 시스템 효율 향상.
• 많은 프로세스들에게 빠른 응답 시간 제공.
• 단점
• 무한 대기 현상 발생. BT가 긴 프로세는 자원을 할당 받지 못할 수 있음.
• 정확한 실행 시간을 알 수 없음. 실행 시간 예측 기법이 필요.

• SRTN (Shortest Remaining Test Next)
• SPN 변형 기법 1
• Preemptive scheduling.
• 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선전됨.
• 장점 ) SPN 장점 극대화.
• 단점 ) BT 예측 필요, 잔여 실행을 계속 추적해야 하므로 overhead가 발생.
• 현실적으로 구현 및 사용이 어려움.

• HRRN (High-Response-Ratio-Next)
• SPN 변형 기법 2
• None-Preemptive scheduling.
• SPN + Aging concepts
• 나이가 많은 걸 배려 즉, WT(대기시간)을 고려해 기회를 제공.
• Response Ratio (응답률)가 높은 프로세스 우선.



• 필요한 BT 대비 얼마나 기다렸는가.
• 장점 ) SPN의 장점 + 무한 대기 현상 방지.
• 단점 ) 실행 시간 예측 기법 필요. overhead 발생.

• MLQ (Multi-level Queue)
• 작업 (or 우선순위)별 별도의 ready queue를 가짐.
• 최초 배정된 queue를 벗어나지 못함 → 시스템 변화에 적응하지 못함.
• 각각의 queue는 자신만의 스케줄링 기법 사용.
• Queue 사이에는 우선순위 기반의 스케줄링 사용.
• 우선순위가 높으면 응답이 빠르긴 하나 우선 순위가 낮은 queue는 starvation 현상 발생이 가능. 그리고 여러 개의 queue 관리를 하면 스케줄링 overhead가 발생함.
• Queue의 구성은 정책에 따라 결정.

• MFQ (Multi-level Feedback Queue)
• 프로세스의 Queue 간 이동이 허용됨.
• feedback을 통해 우선 순위 조정. 현재까지의 프로세서 사용 정보 활용.
• 동적 우선순위
• Preemptive scheduling.
• 장점 ) 프로세스에 대한 사전정보 (BT) 없이 SPN, SRTN, HRRN 기법의 효과를 볼 수 있음.
• 단점 ) 설계 및 구현이 복잡함. 스케줄링 overhead가 큼. starvation 문제.