CPU 스케줄링이란?

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

가장 공정한 스케줄링

프로세스마다, 빨리 처리해야하는 프로세스와 그렇지 않은 프로세스가 있기 때문에 각각의 우선순위에 따라 배분해야한다.
예를 들어, 입출력 작업이 많은 프로세스의 우선순위는 CPU작업이 많은 프로세스의 우선순위보다 높다. 입출력 작업은 실행상태보다 대기상태에 더 많이 머무르기 때문에 빨리 끝내고 CPU 집중 프로세스에 CPU를 몰아서 쓸 수 있게 됨!

프로세스 우선순위

스케줄링 큐

프로세스의 우선순위가 PCB에 담겨있다. 매번 우선순위를 확인하기 위해 PCB를 확인하는 것은 비효율적이므로, 각종 자원 별로 줄을 세워놓는 스케줄링 큐를 이용한다.
준비 큐는 CPU를 이용하기 위해 기다리는 줄, 대기 큐는 입출력장치를 이용하기 위해 기다리는 줄이다.

예를 들어, 동시에 여러 프로세스가 돌아갈때 CPU자원은 한정적이므로 번갈아가며 사용해야한다. 이때 이 프로세스들은 준비 상태가 되어 준비 큐에 들어가서 CPU의 할당을 기다리게 된다. 자기 차례가 되면 디스패치되어 실행상태가 되고, 실행 시간이 완료되면 다시 준비 상태로 들어간다.

만약 어떤 프로세스에서 입출력장치를 요구하면, 이때부터는 CPU를 쓸 필요가 없기 때문에 대기 큐에 들어가서 대기상태에 진입하게 된다. 입출력이 완료되면 다시 준비상태로 넘어간다.

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

어떤 프로세스가 CPU를 사용중인데, 다른 프로세스가 급하게 CPU를 써야한다고 온다. 이때 두가지 방법을 사용할 수 있다.

1번, 현재 프로세스가 사용중인 CPU를 빼앗아 급한 프로세스에게 주기.

2번, 현재 작업중인 프로세스를 작업이 완료될때까지 기다리기.

1번을 선점형, 2번을 비선점형 스케줄링이라고 한다.
선점형 스케줄링은 어느 한 프로세스의 자원 독점을 막을 수 있지만, 문맥 교환 과정에서 오버헤드가 발생할 수 있다.
비선점형 스케줄링은 반대로 오버헤드가 적지만, 모든 프로세스가 골고루 자원을 이용하기 어렵다.

CPU 스케줄링 알고리즘

7가지 CPU스케줄링 알고리즘에 대해 알아보자.

FCFS 선입 선처리 스케줄링

• FCFS(First Come First Served) 방식

• 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링

• CPU를 요청한 프로세스 순으로 CPU를 할당함

• 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용(호위 효과)이 발생 할 수 있다.

SJF 최단 작업 우선스케줄링

• SJF(Shortest Job First) 방식

• 호위 효과를 방지하기 위해 CPU 사용 시간이 짧은 프로세스부터 처리

• 주로 비선점형 스케줄링으로 구분

RR 라운드 로빈 스케줄링

• RR(Round Robin) 스케줄링 (돌아가면서, 차례대로 처리)

• 선입 선처리 스케줄링 + 타임 슬라이스 (각 프로세스가 CPU를 사용할 수 있는 정해진 시간)

• 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링

  • 큐에 삽입된 프로세스들은 순서대로 이용하지만, 정해진 시간만큼만 사용한다.
  • 시간을 모두 사용했을 때도 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입한다. (문맥교환)

• 타임 슬라이스의 크기가 중요

  • 타임 슬라이스가 크면 FCFS 스케줄링과 큰 차이가 없어지고, 타임 슬라이스가 작으면 context overhead문제 발생

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

• SRT(Shortesr Remaining Time) 스케줄링

• SJF 스케줄링 + RB 스케줄링

  • 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스는 남은 작업 시간이 가장 적은 프로세스를 선택한다.

우선순위(Priority) 스케줄링

• 프로세스들에 우선순위를 부여하고 우선순위가 높은 프로세스부터 실행하는 방식. 우선순위가 같은 프로세스들은 선입선처리로 처리

• SJF 스케줄링, SRT스케줄링은 넓은 의미에서 우선순위 스케줄링으로 볼 수 있음

• 기아 현상(starvation)이 근본적인 문제점

  • 우선순위가 높은 프로세스만 주구장창 실행되어 우선순위가 낮은 프로세스는 (준비 큐에 먼저 삽입되었어도) 실행이 지연됨.

• 기아 현상을 방지하기 위해 대기 중인 프로세스의 우선순위를 점차 증가시키는 에이징(aging) 기법을 사용함.

<기아현상>

<에이징 기법>

다단계 큐 스케줄링

• Multilevel queue 스케줄링

• 우선순위 스케줄링의 발전된 형태

• 우선순위별로 준비 큐를 여러개 사용하는 스케줄링 방식

  • 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
  • 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리

• 큐별로 프로세스를 유형별로 처리할 수 있게 됨

• 큐간의 이동이 불가능하기 때문에 여전히 starvation 발생 가능

다단계 피드백 큐 스케줄링

• Multilevel feedback queue 스케줄링

• 다단계 큐 스케쥴링에서 큐 간의 이동이 가능하도록 발전된 형태

• 새롭게 준비상태가 된 프로세스를 가장 높은 우선순위 0에 삽입. 타임 슬라이스만큼 실행시킨다. 그때 만약 실행이 끝나지 않았다면, 우선순위가 다음으로 높은 우선순위1에 삽입하게 된다. 또 실행이 끝나지 않으면 우선순위2로 밀린다.

• CPU를 많이 사용할수록 우선순위가 낮아지게 됨

  • CPU 집중 프로세스의 우선순위는 낮아지면서 입출력 집중 프로세스의 우선순위가 높아지게 됨

• 다단계 피드백 큐에서도 aging 기법 적용 가능

  • 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높일 수 있음

  

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