10. 스케줄링 알고리즘: Chapter 5. CPU Scheduling (Part 2)

라운드 로빈 스케쥴링, RR(Round-Robin-Scheduling)

• FIFO 알고리즘과 유사하지만 선점이 추가됨
• 타임 퀀텀time quantum 또는 타임 슬라이스time slice라고 하는 작은 단위 시간을 정의
• 레디 큐는 선입 선출 원형 큐로 동작
• CPU 스케쥴러는 레디큐를 돌면서 한 번에 한 프로세스씩 한 번의 타임 슬라이스 동안 CPU를 할당함
• CPU 스케쥴러는 레디큐에서 첫번째 프로세스를 선택해 한 번의 타임 슬라이스 이후에 인터럽트를 걸도록 타이머를 선정한 후 프로세스르 디스패치 함
• 두 가지 경우가 발생 가능
  1. 프로세스의 CPU 버스트가 한 번의 타임 슬라이스보다 작을 수 있음
     • 이 경우 프로세스 자신이 CPU를 자발적으로 방출함
     • 스케쥴러는 그 이후 레디큐에 있는 다음 프로세스를 진행함
  2. 현재 실행중인 프로세스의 CPU 버스트가 한 번의 타임 슬라이스보다 긴 경우
     • 타이머가 끝나고 운영체제에 인터럽트가 발생함
     • context switch가 일어나고 실행하던 프로세스는 레디 큐의 꼬리에 넣어짐

• 위 그림은 시간 0에 도착한 프로세스의 집합임
• P1 -> P2 -> P3 순으로 도착함
• 타임 슬라이스는 4msec으로 설정

• 위 그림은 이 경우의 RR를 사용한 프로세스 처리 시간을 간트 차트를 나타냄
• P1은 처음의 4msec을 사용함
• P2는 4msec을 필요로 하지 않기 때문에 시간 할당량이 끝나기 전에 종료됨
• 대기시간
  • P1: 6msec
  • P2: 4msec
  • P3: 7msec
  • 평균 대기시간: (6+4+7)/3 = 5.66msec
• 총처리시간
  • P1: 30msec
  • P2: 7msec
  • P3: 10msec
  • 평균 총처리시간: (30+7+10)/3 = 15.67msec

• RR 알고리즘의 성능은 타임 슬라이스의 크기에 많은 영향을 받음
  • 시간 할당량이 매우 클 경우: FIFO 스케쥴링과 같음
  • 시간 할당량이 매우 작을 경우: context switch 오버헤드가 너무 커지므로 프로세스의 실행이 느려짐
• 그러므로 타임 슬라이스의 크기는 context switch 시간에 비교해 커야함

• RR 알고리즘의 총처리시간 또한 타임 슬라이스의 크기에 많은 영향을 받음
  • 한 프로세스 집합의 평균 총처리시간은 시간 할당량의 크기가 증가하더라도 반드시 개선되지는 않음 

 

 

우선순위 스케쥴링Priority Scheduling

• SJF 알고리즘은 CPU 버스트가 짧은 프로세스가 가장 높은 우선순위를 가진 우선순위 스케쥴링임
• FCFS 알고리즘은 우선순위가 같은 경우 선입 선처리로 스케쥴 되는 우선순위 케쥴링임

• 위 그림은 시간 0에 도착한 프로세스의 우선순위와 CPU 버스트 타임 집합과 이 경우의 Priority Scheduling을 사용한 프로세스 처리 시간을 간트 차트를 나타냄
• 평균 대기 시간: 8.2msec
• 우선 순위 스케쥴림은 선점형이거나 비선점형일 수 있음
• 우선순위 스케쥴링의 주요 문제
  • 무한봉쇄indefinite blocking: 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스의 상태
  • 기아starvation: 낮은 우선순위의 프로세스들이 무한 봉쇄되어 CPU를 무한히 기다리는 경우
• 우선순위 스케쥴링의 무한봉쇄 및 기아 문제의 해결방안
  • 에이징Aging: 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 것
  • RR과 우선순위 스케쥴링을 결합하는 방법
    • 시스템이 우선순위가 가장 높은 프로세스를 실행
    • 우선순위가 같은 프로세스들은 RR 스케쥴링을 사용하여 스케쥴하는 방식
    • 아래 그림과 같이 우선수위가 가장 높은 P4의 경우 완료될 때 까지 실행하고, 우선순위가 같은 P2, P3는 RR 방식으로 실행 후 종료되면 그 다음의 우선순위를 갖는 P1, P5를 RR 방식으로 실행함

 

 

다단계 큐 스케쥴링Multilevel Queue Scheduling

• 프로세스의 우선순위마다 별도의 큐를 두어 우선순위가 가장 높은 큐에서 프로세스를 스케쥴링 함
• 우선순위 스케쥴링이 RR과 결합한 경우에 효과적임

• 위 그림에서 각 큐는 다음과 같은 우선순위를 가짐
  1. 실시간 프로세스
  2. 시스템 프로세스
  3. 대화형 프로세스
  4. 배치 프로세스
• 각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가짐
• 상위 큐들이 모두 비어있지 않으면 하위 큐가 실행될 수 없음
• 하위 큐가 실행되고 있을 때 상위 큐에 프로세스가 레디 큐에 들어가면 상위 큐의 프로세스가 선점됨

 

다단계 피드백 큐 스케쥴링Multilevel Feedback Scheduling

• 다단계 큐 스케쥴링 알고리즘은 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당됨
• 대조적으로 다단계 피드백 큐 스케쥴링 알고리즘에서는 프로세스가 큐들의 사이를 이동하는 것을 허용함

• 어떤 프로세스가 CPU 시간을 너무 많이 사용하면 낮은 우선순위의 큐로 이동함
  • I/O 중심의 프로세스와 대화형 프로세스들이 높은 우선순위의 큐에 넣어짐
  • 예시
    • 새로 진입하는 프로세스는 큐0(quantum=8)에 넣어짐        
    • 만약 프로세스가 이 시간 안에 끝나지 않으면 큐1(quantum=16)의 꼬리에 넣어짐
    • 만약 프로세스가 이 시간 안에 끝나지 않으면 선점되어 큐2(FCFS)에 넣어짐
    • 큐0과 큐1이 비어있을 때만 큐2에 있는 프로세스가 FCFS의 방식으로 실행됨
• 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순의 큐로 이동할 수 있음
• 이를 통해 기아 현상을 예방할 수 있음
• 현대의 가장 일반적인 CPU 스케쥴링 알고리즘임

 

 

5.4 스레드 스케쥴링Thread Scheduling

• 프로세스 모델에 스레드를 도입하면서 유저 레벨과 커널 레벨 스레드로 구분하였음
• 대부분의 운영체제에서 스케쥴 되는 대상은 프로세스가 아니라 커널 레벨 스레드임
• 유저 레벨 스레드는 스레드 라이브러리에 의해 관리되고, 커널 레벨 스레드에 many-to-many 방식으로 매핑됨