[운영체제] 11-2 CPU 스케줄링 알고리즘

이 글을 혼자 공부하는 컴퓨터구조 + 운영체제 (한빛미디어) 책을 읽고 혼자 공부한 내용입니다.
잘못 이해한 부분이 있을 수 있고, 문제가 있는 부분 댓글로 알려주시면 수정하겠습니다.

 

스케줄링 알고리즘의 종류

스케줄링 알고리즘의 종류는 매우 다양, 이 중 '아이디어'가 중요한 것

 

선입 선처리 스케줄링 (FCFS 스케줄링, First Come First Served)

• 단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식
• CPU를 먼저 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식
• 공정해 보이지만, 때때로는 식간이 매우 길어지는 부작용이 있음
• CPU를 오래 사용하는 프로세스가 먼저 도착하면 다른 프로세스는 그 프로세스가 CPU를 사용하는 동안 무작정 기다리는 수 밖에 없음 -> 호위 효과

 

최단 작업 우선 스케줄링 or SJF 스케줄링 (Shortest Job First)

• 호위 효과 방지
• 준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행
• 비선점형 스케줄링 알고리즘으로 분류 but 선점형으로 구현 될 수도 있음

 

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

• 선입 선처리 스케줄링 + 타임 슬라이스
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
• 타임 슬라이스란 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미
• 큐에 삽입된 프로세스들은 삽입된 순서대로 CPU를 이용하되 정해진 시간만큼만 CPU를 이용하고, 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입 -> 문맥 교환 발생
• 타임 슬라이스 크기가 매우 중요
• 크다면 호위 효과 발생, 작으면 문맥 교환에 발생하는 비용이 커짐

최소 잔여 시간 우선 스케줄링 or SRT 스케줄링 (Shortest Remaining Time)

• 최단 작업 우선 스케줄링 + 라운드 로빈
• 프로세스들은 저해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택

 

우선순위 스케줄링 (Priority)

• 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘
• 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
• 문제점 > 기아현상 : 우선순위가 높은 프로세스만 계속 먼저 실행되니 우선순위가 낮은 프로세스의 실행은 계속 뒤로 밀림
• 해결법 > 에이징 : 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

 

다단계 큐 스케줄링

• 우선순위 스케줄링의 발전된 형태
• 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
• 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐에 있는 프로세스들을 처리
• 프로세스들이 큐 사이를 이동할 수 없음 -> 기아 현상 발생

 

다단계 피드백 큐 스케줄링

• 프로세스들이 큐 사이를 이동할 수 있음
• 우선순위가 가장 높은 우선순위 큐에 삽입되고 일정 시간(타임 슬라이스)동안 실행
• 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행 -> 반복 -> CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아짐 (에이징 기법을 적용하여 기아 현상 예방)
• 입출력 집중 프로세스들은 자연스레 우선순위가 높은 큐에서 실행이 끝남
• 구현이 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘