Real-Time CPU Scheduling
- 실시간 시스템에서는 event-driven 방식으로 동작
- 마감 시간 안에 응답해서 적절한 동작을 수행
- Event latency : 이벤트가 발생해서 실시간 시스템에서 그에 맞는 적절한 서비스가 수행될 때까지의 시간
- Interrupt latency : CPU에 이벤트에 해당하는 interrupt가 도착한 시점으로부터 해당 interrupt의 처리 루틴이 시작하기까지의 시간
- Dispatch latency : 스케줄러 dispatcher가 한 프로세스를 중지시키고 다른 프로세스를 시작시키는데 걸리는 시간
- Conflict 해결
- 기존에 동작하고 있는 (특히 kernel mode) 프로세스들을 선점
- 높은 우선순위의 프로세스가 필요로 하는 자원을 낮은 우선순위의 프로세스가 release하게 하는 것
Priority-based Scheduling
- 실시간 시스템에서 주로 사용되는 우선순위 기반 스케줄링
- 실시간 OS에서 가장 중요한 기능은 실시간 프로세스가 CPU를 필요로 할 때 (이벤트가 발생한 시점), 이에 즉각 응답을 해주는 것
- 선점형 우선순위 기반 스케줄링은 단순히 soft real-time 기능을 제공하는 것에 불과함
→ deadline을 만족시켜주지 못할 수 있음 - hard real-time 시스템에서는 deadline이 꼭 지켜져야 하므로 부가적인 스케줄링 기법이 필요함
- 실시간 시스템에서 task들은 주기적 성질을 가짐 = CPU를 일정 시간마다 요구
- 각 주기적인 task마다 고정된 수행시간(t)과 deadline(d), 주기(p)가 있음
- 실행 빈도 = 1/p
Rate Monotonic Scheduling
- 선점형 고정 우선순위 스케줄링
- 우선순위 = task 주기의 역
- 주기가 짧을수록 우선순위가 높아짐
Example
- 두 개의 프로세스 P1, P2가 있다고 가정
- P1의 주기는 50, P2의 주기는 100
→ P1은 P2에 비해 높은 우선순위를 가짐 - P1의 수행 시간은 20, P2의 수행 시간은 35
- 각 프로세스의 마감 시간은 다음 주기가 시작하기 전까지
- 50에서 P2는 5만큼 더 실행해야 하지만 우선순위가 더 높은 P1에 의해 선점 됨
- 75 ~ 100까지는 idle time (유휴 시간)
Example - Missed Deadline
- P1은 주기가 50, P2는 주기가 80
- P1의 수행 시간은 25, P2의 수행 시간은 35
- P2는 85에 실행을 마치게 되어 마감 시간을 지키지 못함
- 주어진 두 프로세스는 주기와 수행 시간을 고려했을 때 둘 다 만족시키는 스케줄링을 할 수 없음
→ Rate Monotonic 스케줄링 기법이 스케줄 할 수 없는 task 집합은 정적인 우선순위를 사용하는 다른 어떤 스케줄링 알고리즘도 스케줄 할 수 없음 - Rate Monotonic은 최적의 스케줄링 기법이지만 CPU 이용률에 한계가 있으므로 CPU 자원을 극대화 해서 사용하는 것이 불가능함
Earliest Deadline First Scheduling (EDF)
- deadline에 따라서 우선순위를 동적으로 부여하는 기법
- 마감 시간이 빠를수록 우선순위가 높아짐
- 프로세스가 실행이 가능하게 되면 자신의 deadline을 시스템에 알리고, 우선순위는 그때 새로 실행 가능하게 된 프로세스의 deadline에 맞춰서 다시 조정하게 됨
Example
- 처음에는 P1의 deadline이 50으로 더 빠르기 때문에 P1의 우선순위가 더 높음
- P1이 첫 실행을 마친 후 다음 deadline은 100이므로 P2의 우선순위가 더 높아지게 됨
- P1과 P2는 deadline을 만족하며 실행을 마친 뒤 150까지 시스템 전체가 유휴 시간을 가지고 다시 P1이 스케줄을 시작하게 됨
Proportional Share Scheduling
- 모든 응용들에게 T개의 time share을 할당하여 동작
- 1개의 응용이 N개의 share를 할당받으면 이 응용은 전체 CPU 시간 중 N/T 시간을 할당받는 것
- time share를 할당받는 것을 보장하는 admission control 정책과 함께 동작해야 함
- admission control 정책에서는 사용이 가능한 충분한 몫이 존재할 때 그 범위 내의 몫을 요구하는 프로세스들에게만 실행을 허락함
Operating System Examples
Linux Scheduling Through Version 2.5
- 버전 2.5까지는 기존의 Unix 스케줄링 알고리즘을 변형해서 사용
→ CPU가 여러 개인 시스템에서 성능이 떨어지는 경향 - 버전 2.5에서는 task 개수와 무관하게 항상 상수 시간 내에 스케줄링이 이루어질 수 있는 order O(1) 스케줄링 알고리즘을 사용
- 우선순위 기반 선점형 알고리즘
- 높은 우선순위의 task가 time quantum을 더 많이 받게 됨
- 우선순위 class
- time sharing
- real-time
- 우선순위는 0~99까지, nice value는 100~140
- nice value : 프로세스에게 할당된 우선순위 값에 대해서 사용자가 그 값을 조정할 수 있는 여지
- nice value가 음수이면 더해서 우선순위가 높아질 수 있음
- ready 상태의 프로세스들도 상태를 더 세분화해서 나눠짐
- active : 자신에게 주어진 time quantum에서 남은 여분이 있는 상태
- expired : time quantum을 다 실행해서 소진한 상태
- 이 상태의 task는 나머지 active한 task들이 각각 자신의 time quantum을 소진할 때까지는 더 이상 실행되지 않음
- CPU마다 run queue를 가지며, run queue 안에서 각각 active한 task의 time quantum과 그 time quantum에서 남은 시간들이 유지되는 자료구조를 가짐
- 단점 : interactive 시스템에서 응답 시간이 좋지 않음
Linux Scheduling in Version 2.6.23+
- Completely Fair Scheduler (CFS)
- 스케줄링 class에 기반을 둠
- 각 class마다 우선순위 부여
- 스케줄러는 매번 가장 높은 우선순위 class 내의 가장 높은 우선순위의 프로세스를 선택
- 기본적으로 제공되는 class는 default와 real-time
- real-time의 우선순위가 더 높음
- 시스템 admin 같은 사람이 새로운 class 추가 가능
- 각 task에 고정된 time quantum이 아닌 CPU time의 비율을 할당
- quantum은 nice value로부터 계산되며 값이 낮을수록 높은 우선순위를 의미 (-20~19)
- target latency 사용
- target latency : 다른 모든 수행 가능한 task가 적어도 한 번씩은 실행할 수 있는 시간 간격
- CPU 시간 비율은 target latency로부터 할당
- 각 task별로 vruntime이라는 변수에 해당 task가 실행된 시간을 기록해서 virtual run time을 유지
- CFS는 다음 실행할 task로 가장 작은 virtual run time을 가지는 task를 선택하게 됨
Linux Scheduling
- POSIX.1b에 따른 real-time 스케줄링이 가능
- static한 우선순위를 갖고 동작
- 각각 class에 속하는 프로세스들의 우선순위 값은 global priority scheme에 따라서 결정
- 우선순위 값이 0부터 139까지 부여되는데, 이 중 real-time에 해당하는 프로세스들은 0~99의 값을 가지고 나머지는 normal priority를 가지는 프로세스에게 할당
- real-time 프로세스들은 nice value가 -20까지 부여될 수 있고, 나머지는 19의 nice value를 가짐
Windows Scheduling
- 우선순위 기반 선점형 스케줄링
- 매번 가장 높은 우선순위를 갖는 thread가 다음에 실행됨
- Dispatcher가 Scheduler
- thread는 한 번 실행을 시작하면 block 되거나 time slice를 다 소진하거나, 혹은 더 높은 우선순위의 thread에 선점될 때까지 실행
- real-time thread는 non-real-time thread를 선점 가능
- 우선순위 체계는 32단계가 있으며, 각 단계마다 queue가 존재
- variable class는 1~15단계, real-time clas는 16~31단계의 우선순위 level을 가짐
- 32단계 중 0 level class는 memory-management thread가 속함
- 스케줄링 도중 실행 가능한 thread가 없는 경우 idle thread가 동작
Windows Priority Classes
- 한 프로세스가 속할 수 있는 여러 개의 priority class를 identify 할 수 있음
- REALTIME_PRIORITY_CLASS, HIGH_PRIORITY_CLASS, ABOVE_NORMAL_PRIORITY_CLASS 등
- priority class 안에 속한 thread는 상대적인 7가지의 priority를 가지게 됨
- thread에 주어진 time quantum이 다 소진되고 나면 priority가 낮춰지게 되며, base 이하로 내려가지는 않음
참고 자료 : Operating System Concepts Essentials
*이미지 자료는 교재 자료를 직접 다시 만든 것으로 무단 불펌 금지입니다
요즘 오버쿡드가 재밌따
끗!!
