Scheduling
CPU를 사용하기 위한 작업들을 관리하는 것
스케줄러가 Dispatch 함으로써 프로세스가 CPU를 할당 받아 작업을 수행한다.
이때 스케줄링은 CPU를 할당하기 위해 결정하는 과정이라고 생각하면될 것 같다.
CPU를 사용하기 위한 조건
1. Time Slice
작업에 할당하는 CPU의 사용시간
Time Slice가 0이 된다면 CPU를 빼앗기게 된다.
2. 우선순위
작업마다 우선순위가 존재하는데 CPU를 사용하기 위해서는 대기 큐에서의 우선순위가 높은 순서부터 CPU를 할당받는다.
Scheduling Algorithm in Linux
Ready Queue
CPU를 받기위해 프로세스(작업) 들이 대기하는 큐
작업들이 대기하는 큐(queue)와 그러한 큐들을 모아놓은 이진 배열(bitmap) 으로 구성되어있다.
bitmap은 이진 비트로 구성되어 작업 큐의 유무를 보관한다.
bitmap 요소의 값이 1이라면 큐가 존재하는 것이고 0 이면 존재하지 않는다.
이러한 bitmap 과 queue는 각 CPU마다 두 개의 배열로 구성되어 있는데
각각 Active array와 Expired array라 한다.
Active array는 말 그대로 현재 CPU가 스케줄하기 위해 대기하고 있는 작업들의 배열이다.
Expired array는 완료되거나 timeslice가 0인 작업들을 보관하게 되는 배열이다
따라서 Active array에서 작업이 배정되는 과정은
bitmap에서 우선순위에 따라queue가 있는지를 확인한다.queue가 있다면queue에서 우선순위가 가장 높은 작업을 수행한다.queue가 없다면 다음bitmap의 요소로 넘어간다.- 완료되거나
timeslice가 0이된 작업은Expired array로 이동한다.
만약 Active array의 작업이 모두 완료되어 비워지게 된다면
Expired array와 Active array를 교체하여 Expired array에 timeslice를 부여하여 다시 Active array로 만들어 사용한다.
위 알고리즘의 시간 복잡도는 O(1) 이다.
참고 및 이미지 자료
고건 교수님 강의
https://olc.kr/course/course_online_view.jsp?id=35&cid=51
