CPU 스케줄링

• 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
  프로세스마다 우선순위가 다르기 때문에 우선순위에 맞게 CPU 자원을 배분해야 함
• 입출력 작업이 많은 프로세스의 우선순위는 CPU작업이 많은 프로세스보다 높음
  입출력 작업이 많은 프로세스는 대기상태에 많이 머무름으로 먼저 작업을 처리해주면 CPU 집중 프로세스에 많은 자원을 할당할 수 있기 때문

스케줄링 큐

• 운영체제는 컴퓨터의 자원을 사용하고자 하는 프로세스들을 큐에 삽입해 자원을 이용하도록 만듬
• 스케줄링에서의 큐는 선입선출방식이 아니며 우선순위에 따라 작업을 처리하게 됨
• 스케줄링 큐에는 대표적으로 준비 큐와 대기 큐가 있음
  준비 큐: CPU를 이용하기 위해 준비 상태에 있는 프로세스들이 있는 큐
  대기 큐: 입출력 장치를 이용하기 위해 대기 상태에 있는 프로세스들이 있는 큐
• 대기 큐에서 같은 장치를 요구한 프로세스들은 같은 큐에서 대기하게 됨

선점형, 비선점형 스케줄링

선점형 스케줄링

• 우선 순위가 높은 프로세스가 CPU 사용을 요청하면 우선순위가 낮은 프로세스의 자원을 빼앗아 사용가능한 방식
• 선점형 스케줄링을 사용하면 어느 한 프로세스의 자원독점을 막고 프로세스들에 골고루 자원을 배분할 수 있음
• 문맥 교환 과정에서 오버헤드가 발생할 수 있음

비선점형 스케줄링

• 우선순위가 높은 프로세스가 CPU 사용을 요청해도 다른 프로세스가 종료되거나 대기 상태에 접어들 때 까지 CPU 자원을 사용할 수 없는 방식
• 문맥 교환에서 발생하는 오버헤드가 적지만, 프로세스간 골고루 자원 배분을 하는 것이 어려워짐

스케줄링 알고리즘

1. 선입 선처리(First Come First Served) 스케줄링

• 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
• CPU를 요청한 프로세스 순으로 CPU를 할당함
• 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용이 생김
  이를 호위 효과라 부름

2. 최단 작업 우선(Shortest Job First) 스케줄링

• 호위 효과를 방지하기 위해 CPU 사용 시간이 짧은 프로세스부터 우선 실행하는 방법
• 선점형, 비선점형 스케줄링 양쪽으로 구현 가능하지만, 보통 비선점형 스케줄링으로 구분함

3. 라운드 로빈(Round Robin) 스케줄링

• FCFS 스케줄링 기반이지만, 타임 슬라이스를 활용하는 스케줄링
  타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
• 타임 슬라이스가 크면 FCFS 스케줄링과 큰 차이가 없어지고, 타임 슬라이스가 작으면 context overhead문제 발생 -> 타임 슬라이스 크기가 중요

4. 최소 잔여 시간 우선(Shortesr Remaining Time) 스케줄링

• SJF 스케줄링과 RB 스케줄링을 합친 방식
• 정해진 시간만큼 CPU를 이용하지만, 다음으로 CPU를 사용할 프로세스는 남은 작업 시간이 가장 적은 프로세스를 선택하는 스케줄링 방식

5. 우선순위(Priority) 스케줄링

• 프로세스들에 우선순위를 부여하고 우선순위가 높은 프로세스부터 실행하는 방식
• 우선순위가 같은 프로세스들은 선입선출로 스케줄링하게 됨
• SJF 스케줄링, SRT스케줄링은 넓은 의미에서 우선순위 스케줄링으로 볼 수 있음
• 우선순위가 높은 프로세스만 계속 실행되고 우선순위가 낮은 프로세스는 실행이 지연되는 기아(starvation) 현상이 발생함
• starvation을 방지하기 위해 대기 중인 프로세스의 우선순위를 점차 증가시키는 에이징(aging) 기법을 사용함

6. 다단계 큐(Multilevel queue) 스케줄링

• Priority 스케줄링의 발전된 형태로 우선순위별로 준비 큐를 여러개 사용하는 스케줄링 방식
• 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스를 처리하게 됨
• 큐별로 프로세스를 유형별로 처리할 수 있게 됨
• 큐간의 이동이 불가능하기 때문에 여전히 starvation 발생 가능

7. 다단계 피드백 큐 스케줄링

• Multilevel queue 스케줄링의 발전된 형태로 큐 간의 이동이 가능한 Multilevel queue 스케쥴링
• CPU를 많이 사용할수록 우선순위가 낮아지게 됨 => 자연스럽게 입출력 집중 프로세스의 우선순위가 높아지고, CPU 집중 프로세스의 우선순위는 낮아짐
• 다단계 피드백 큐에서도 aging 기법 적용 가능 => 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높일 수 있음

출처:
https://www.youtube.com/watch?v=Jjfah3t_xWk&list=PLVsNizTWUw7FCS83JhC1vflK8OcLRG0Hl&index=33
혼자 공부하는 컴퓨터 구조+운영체제, 강민철, 한빛미디어