Linux Scheduling

Choooose·2023년 2월 7일
0

운영체제

목록 보기
5/8

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 이면 존재하지 않는다.

이러한 bitmapqueue는 각 CPU마다 두 개의 배열로 구성되어 있는데
각각 Active arrayExpired array라 한다.

Active array는 말 그대로 현재 CPU가 스케줄하기 위해 대기하고 있는 작업들의 배열이다.
Expired array완료되거나 timeslice가 0인 작업들을 보관하게 되는 배열이다

따라서 Active array에서 작업이 배정되는 과정은

  1. bitmap 에서 우선순위에 따라 queue가 있는지를 확인한다.
  2. queue가 있다면 queue에서 우선순위가 가장 높은 작업을 수행한다.
  3. queue가 없다면 다음 bitmap의 요소로 넘어간다.
  4. 완료되거나 timeslice가 0이된 작업은 Expired array로 이동한다.

만약 Active array의 작업이 모두 완료되어 비워지게 된다면

Expired arrayActive array를 교체하여 Expired arraytimeslice를 부여하여 다시 Active array로 만들어 사용한다.

위 알고리즘의 시간 복잡도는 O(1) 이다.

참고 및 이미지 자료


운영체제 - YES24

고건 교수님 강의
https://olc.kr/course/course_online_view.jsp?id=35&cid=51

0개의 댓글