[혼공스터디 9기] 혼.공.컴.운. - 11. CPU 스케줄링(선택 미션 포함)

11-1 CPU 스케줄링 개요

운영체제는 CPU를 어떻게 프로세스에 배분할까?
CPU 스케줄링: 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것. 이는 컴퓨터 성능과도 직결되는 중요한 문제다.

프로세스 우선순위

입출력 집중 프로세스: 비디오 재생 등 입출력 작업이 많은 프로세스. 실행 상태보다는 대기 상태에 많이 머무른다.

CPU 집중 프로세스: 복잡한 수학 연산, 컴파일 등 CPU 작업이 많은 프로세스. 대기 상태보다는 실행 상태에 더 많이 머무른다.

 

CPU 버스트: CPU를 이용하는 작업

입출력 버스트: 입출력장치를 기다리는 작업

 

운영체제는 각 프로세스의 PCB에 우선순위를 명시하고, PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정한다. 그렇게 자연스레 우선순위가 높은 프로세스는 더 빨리, 더 자주 실행된다.

 

*유닉스 체계 운영체제에서는 ps -el 명령을 통해 프로세스의 우선순위를 확인할 수 있다. 윈도우에서는 Process Explorer라는 소프트웨어를 통해 확인/변경할 수 있다.

 

스케줄링 큐

운영체제가 모든 프로세스의 PCB를 찾아 보는 것은 비효율적이므로, 프로세스들을 줄 세운다.

 

즉, 메모리로 적재되고 싶은(새로 생성되는) 프로세스들을 큐에 삽입하여 줄을 세우고, CPU를 이용하고 싶은 프로세스들 또한 큐에 삽입하여 줄을 세우고, 특정 입출력장치를 이용하고 싶은 프로세스들 역시 큐에 삽입하여 줄을 세운다.

 

준비 큐: CPU를 이용하고 싶은 프로세스들이 서는 줄

대기 큐: 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄

 

1. 준비 상태에 있는 프로세스들의 PCB는 준비 큐의 마지막에 삽입 되어 CPU 사용 차례를 기다림
2. 운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내 실행하되 그 중 우선순위가 높은 프로세스를 먼저 실행
3. 대기 상태에 있는 프로세스들은 같은 장치를 요구한 프로세스들끼리 같은 대기 큐에서 기다림
4. 입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾아 이를 준비 상태로 변경한 뒤 준비 큐로 이동시킨다.

 

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

선점형 스케줄링: 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식

 

급한 프로세스가 언제든 끼어들 수 있어 자원이 골고루 배분되지만, 그만큼 문맥 교환 과정에서 오버헤드가 발생할 수 있다.

 

비선점형 스케줄링: 하나의 프로세스가 자원 사용을 독점할 수 있는 스케줄링 방식. 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식

 

 

 

대부분의 운영체제에서는 선점형 스케줄링 방식을 차용하고 있다.

 

 

 

11-2. CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘의 종류는 매우 다양하고 운영체제 저마다 서로 다른 스케줄링 알고리즘을 사용한다.

스케줄링 알고리즘의 종류

선입 선처리 스케줄링

FCFS 스케줄링(First Come First Served Scheduling)이라고도 한다.

 

단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식이다.

언뜻 보기에는 가장 공정해 보이지만, 때때로 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용*이 있다.

 

*호위 효과(Convoy effect)

 

최단 작업 우선 스케줄링

SJF 스케줄링(Shortest Job First Scheduling)이라고도 한다.

 

준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식

 

라운드 로빈 스케줄링

선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식. 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링. 정해진 시간만큼만 CPU를 이용하고, 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입된다. 이 때 문맥 교환이 발생한다.

 

타임 슬라이스: 프로세스가 CPU를 사용할 수 있는 정해진 시간. 너무 짧거나 길면 문맥 교환에 너무 많은 비용이 소요되거나 선입 선처리 스케줄링과 다를 바 없게 된다.

 

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

SRT(Shortest Remaining Time) 스케줄링

최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 것.

정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.

 

우선순위 스케줄링

프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘.(우선순위가 같은 프로세스들은 선입 선처리로 스케줄링 된다.)

 

기아 현상: 우선순위가 높은 프로세스만 계속 먼저 실행되니 우선순위가 낮은 프로세스의 실행은 계속 뒤로 밀리는 것

에이징: 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

 

다단계 큐 스케줄링

우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식. 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리한다. 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해진다. 또, 큐마다 다른 스케줄링 방식을 사용할 수도 있다.

 

다단계 피드백 큐 스케줄링

어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘이다.

 

다단계 큐 스케줄링에서 발전한 형태로, 프로세스들이 큐 사이를 이동할 수 있다는 점이 다르다. CPU를 비교적 오래 사용해야 하는 CPU 집중 프로세스들은 자연스레 우선순위가 낮아지고, CPU를 비교적 적게 사용하는 입출력 집중 프로세스들은 자연스레 우선순위가 높은 큐에서 실행이 끝난다.

 

낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방할 수 있다.

 

구현이 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘이다.