[CS] CPU 스케줄링 알고리즘

목차

• CPU 스케줄링
• 우선순위
• 대기큐와 준비큐
• 선점형과 비선점형 스케줄링
• CPU 스케줄링 알고리즘

 

 

CPU 스케줄링

운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것

 

 

프로세스 우선순위

가장 공정한 CPU 스케줄링?

CPU를 사용하고 싶어하는 프로세스들이 차례로 돌아가며?

빨리 처리해야 하는 프로세스가 있기 때문 (= 프로세스마다 우선순위가 다르기 때문)

 

입출력 작업이 많은 프로세스 (= 입출력 집중 프로세스) 의 우선순위는

CPU 작업이 많은 프로세스 (= CPU 집중 프로세스) 의 우선순위보다 높다.

 

 

프로세스 우선순위(priority)

 

이런식으로 모든 프로세스가 CPU를 그저 차례대로 돌아가면서 사용하는 것보다

각각의 상황에 맞게 요구하는 자원에 맞게 CPU를 배분하는 것이 조금 더 효율적이다.

우선순위는 이 프로세스의 PCB에 저장이 된다.

 

 

 

스케줄링 큐

PCB마다 우선순위가 적혀있다고는 하지만 운영체제 입장에서는 다음에 CPU를 사용할

프로세스를 선정하기 위해서 일일이 모든 프로세스의 PCB를 뒤적거리는 것은 비효율적이다.

 

스케줄링 큐는 어떤 자원을 이용하고 싶어하는 프로세스들이 서는 줄이다.

스케줄링에서의 큐는 반드시 선입선출이 필요는 없다

 

 

 

스케줄링 큐의 종류

프로세스마다 요구하는 자원들은 여러개가 있을 것이고 그렇기 때문에 스케줄링 큐 또한 여러가지 큐들이 있다.

• 준비 큐: CPU를 이용하기 위해 기다리는 줄
• 대기 큐: 입출력장치를 이용하기 위해 기다리는 줄

이런 스케줄링 큐들은 반드시 선입선출은 아니기 때문에 우선순위가 높은 프로세스가 먼저 자원을 이용한다.

 

 

대기 큐: 같은 장치를 요구한 프로세스들은 같은 큐에서 대기

※ 물론 같은 큐에서도 우선순위가 높은 프로세스부터 처리된다.

 

 

운영체제는 이런식으로 스케줄링 큐를 이용해 프로세스 상태를 관리하고 프로세스에게 자원을 할당한다.

프로세스 상태 다이어그램을 스케줄링 큐를 넣어서 자세하게 표현해보자.

 

 

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

가령 어떤 프로세스가 지금 자기 차례가 되어서 CPU를 할당받아서 CPU를 이용하고 있었다 가정해보자(실행 상태)

그런데 너무너무너무 급한 프로세스가 나타난 상황이 있을 수 있다. 이럴 때는 어떻게 처리를 할까?

• 현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 뺴앗아 다른 프로세스에 할당(선점형 스케줄링)
• 현재 CPU를 사용 중인 프로세스의 작업이 끝날 때까지 프로세스 기다리기(비선점형 스케줄링)

 

선점형 스케줄링(preemptive scheduling)

어떤 프로세스가 CPU를 할당받아 쓰고 있다 할지라도 다른 더 우선순위가 높은 프로세스가 얼마든지 

CPU의 자원을 뺴앗아 쓸 수 있는 스케줄링을 의미한다.

 

장점: 어느 한 프로세스의 자원독점을 막고 프로세스들에게 골고루 자원을 배분할 수 있다.

단점: 그 만큼 문맥 교환 과정이 많이 발생하기 때문에 과정에서 오버헤드가 발생할 수 있다.

 

 

 

비선점형 스케줄링(non - preemptive scheduling)

어떤 프로세스가 한 자원을 점거하고 있다면 이 프로세스가 종료되거나 대기상태에 접어들기 전까지는

그 자원을 쓸 수 없는 스케줄링을 의미하다.

 

장점: 선점형 스케줄링에 비해 문맥 교환에서 발생하는 오버헤드가 적다.

단점: 모든 프로세스가 골고루 자원을 이용하기 어렵다.

 

 

CPU 스케줄링 알고리즘

대표적인 7가지 CPU 스케줄링 알고리즘

• 선입 선처리 스케줄링
• 최단 작업 우선 스케줄링
• 라운드 로빈 스케줄링
• 최소 잔여 시간 우선 스케줄링
• 우선순위 스케줄링
• 다단계 큐 스케줄링
• 다단계 피드백 큐 스케줄링

 

선입 선출 스케줄링

 

FCFS(First Come First Serced) 스케줄링

• 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
• 먼저 CPU를 요청한 프로세스로부터 CPU할당
• 단점: 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용(=호위 효과)

 

최단 작업 우선 스케줄링

SJF(Shortest Job First) 스케줄링

• 호위 효과를 방지하려면
• CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스는 먼저 실행
• CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식
• 비선점형, 선점형으로 구현가능하나 일반적으로 비선점형 스케줄링으로 분류됨

 

 

라운드 로빈 스케줄링

RR(Round Robin) 스케줄링

• 선입 선처리 스케줄링 + 타임 슬라이스(time slice)
• 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가면 CPU를 이용하는 선점형 스케줄링
  • 큐에 삽입된 프로세들은 순서대로 CPU를 이용하되 정해진 시간만큼만 이용
  • 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입(문맥교환)

 

 

최소 잔여 시간 우선 스케줄링

SRT(Shortest Remaining Time) 스케줄링

• 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
• 최단 작업 우선 스케줄링: 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘
• 라운드 로빈 스케줄링: 정해진 타임 슬라이스만큼 돌아가며 사용하는 알고리즘
• 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택

 

 

우선 순위 스케줄링

• 프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
• 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
• 최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링 ⊂ 우선순위 스케줄링
• 우선순위 스케줄링의 근본적인 문제점, 기아(starvation) 현상
  • 우선순위 높은 프로세스만 주구장창 실행
  • 우선순위 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 실행 연기
  • 개인적으로 롯데월드의 매직 패스같다..

 

• 이를 방지하기 위한 기법: 에이징(aging)
• 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
• 대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법
  • 우선순위가 낮아도 언제가는 우선순위가 높아진다.

 

 

다단계 큐 스케줄링

Multilevel queue 스케줄링

• 우선순위 스케줄링의 발전된 형태
• 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
• 큐 별로 스케줄링을 달리 적용해서 프로세스를 유형별로 처리하는게 쉬워진다. 
  • 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
  • 우선 순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리
  • 하지만 우선순위 스케줄링과 같이 우선순위가 고정되어 있기 때문에 기아 현상 발생가능

 

 

 

다단계 피드백 큐 스케줄링

Multilevel feedback queue 스케줄링

• 다단계 큐 스케줄링의 발전된 형태
• 큐 간의 이동이 가능한 다단계 큐 스케줄링
• 다단계 큐 스케줄링에서는 기본적으로 큐 간의 이동 불가
  • 우선순위 낮은 프로세스는 계속해서 실행 연기 우려
  • 기아 현상 발생 가능

 

• 새롭게 준비 상태가 된 프로세스가 있으면 가장 우선순위가 높은 큐에 삽입
• 일정시간 타임 슬라이스만큼 CPU를 할당받아서 사용을 하게 함
  • 실행이 끝났다면 볼게 없음
  • CPU가 더 필요하다면 우선순위가 내려감

타임슬라이스 만큼 실행을 하고 끝내지 못했다면 우선순위 하락

다단계 피드백 큐에서의 에이징 기법 적용

 

어떤 프로세스의 CPU 시간이 길면 우선순위가 낮아지고 

어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는 방식

구현이 복잡하지만 CPU 스케줄링 방식의 가장 일반적인 형태로 알려져 있음

 

 

 

 

해당 포스팅에 나온 글과 이미지들은 강민철 저자님의 혼자 공부하는 컴퓨터 구조+운영체제의 책과 강의를 참고하여 만들어졌습니다.

책에서 보다 깊게 나오는 내용이 있으므로 한번 구매하고 보셔도 좋을 것 같습니다. (저도 오늘 도착했습니다! ㅎㅎ)

[한빛미디어] 혼자 공부하는 컴퓨터 구조+운영체제