[운영체제] CPU 스케줄링에 대하여...더보기

CPU 스케줄링

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

 

1. CPU 스케줄링이 필요한 이유 

모든 프로세스는 CPU를 필요로 하고 모든 프로세스는 먼저 CPU를 사용하고 싶어 한다.

프로세스 종류마다 입출력장치를 이용하는 시간과 CPU를 이용하는 시간의 양에는 차이가 있다.

 

1.1 시간에 따른 분류

• 입출력 집중 프로세스: 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스
• CPU 집중 프로세스: 복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스와 같이 CPU 작업이 많은 프로세스

 

1.2 우선순위

• 프로세스의 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 하기 위해 운영체제는 프로세스마다 우선순위를 부여한다.
• 우선순위가 높은 프로세스부터 빨리 처리해야하며 우선순위가 높은 프로세스에는 대표적으로 입출력 작업이 많은 프로세스가 있다.

 

2. CPU 스케줄링 큐

운영체제가 관리하는 대부분의 자원은 큐로 관리된다.

운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행하되 그중 우선순위가 높은 프로세스를 먼저 실행한다.

 

2.1 생성 배경

• CPU를 사용할 다음 프로세스를 찾기 위해 운영체제가 일일이 모든 프로세스의 PCB를 뒤적거리는 것은 비효율적이다.
• 그래서 운영체제는 프로세스들을 줄 서서 기다리게 하는데 이때 이 줄을 스케줄링 큐로 구현하고 관리한다.

 

2.2 큐의 종류

• 준비 큐: CPU를 이용하고 싶은 프로세스들이 서는 줄
• 대기 큐: 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄
• 작업이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고, 이 PCB를 준비 상태로 변경한 뒤 대기 큐에서 제거하며 해당 PCB는 준비 큐로 이동한다.

 

2.3 스케줄링 종류

• 선점형 스케줄링: 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 제로 빼앗아 다른 프로세스 할당할 수 있는 스케줄링 방식
  • 장점: 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있음
  • 단점: 문맥 교환 과정에서 오버헤드가 발생할 수 있음
• 비선점형 스케줄링: 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식
  • 장점: 문맥 교환의 횟수가 선점형 스케줄링보다 적기 때문에 문맥 교환에서 발생하는 오버헤드가 적음
  • 단점: 모든 프로세스가 골고루 자원을 사용할 수 없음

 

3. CPU 스케줄링 알고리즘

3.1 선입 선처리 스케줄링 (FCFS 스케줄링)

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

• 단점: 프로세스들이 기다리는 시간이 매우 길어질 수 있다. (호위 효과)

 

3.2.2 최단 작업 우선 스케줄링 (SJF 스케줄링)

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

 

3.2.3 라운드 로빈 스케줄링 

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

쉽게 말해, 선입 선처리 스케줄링 + 타임 슬라이스 방식이다.

• 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
  
  • 지나치게 크면 호위 효과가 생길 수 있다.
  • 지나치게 작으면 문맥 교환에 발생하는 비용이 커 CPU가 프로세스를 전환하는 데에 온 힘을 다 쓸 여지가 있다.

큐에 삽입된 프로세스들은 삽입된 순서대로 CPU를 이용하되 정해진 시간만큼만 CPU를 이용하고 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입된다. 이때 문맥 교환이 발생한다.

 

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

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

쉽게 말해, 최단 작업 우선 스케줄링 알고리즘 + 라운드로빈 알고리즘 방식이다.

 

3.2.5 우선순위 스케줄링

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

우선순위가 같은 프로세스들은 선입 선처리로 스케줄링한다.

• 단점: 준비 큐에 먼저 삽입되었음에도 불구하고 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기되는 기아 현상이 발생할 수 있다.
  • 해결방안: 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식인 에이징

 

3.2.6 다단계 큐 스케줄링

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

우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있으면 그다음 우선순위 큐에 있는 프로세스들을 처리한다.

큐별로 타임 슬라이스를 여러 개 지정할 수 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수 있다.

• 단점: 프로세스들이 큐 사이를 이동할 수 없어 우선순위가 낮은 프로세스는 계속 연기되어 기아 현상이 발생할 수 있다.
  • 해결방안: 다단계 피드백 큐 스케줄링

 

3.2.7 다단계 피드백 큐 스케줄링

새로 준비 상태가 된 프로세스가 있다면 우선 우선순위가 가장 높은 우선순위 큐에 삽입되고 타임 슬라이스동안 실행되며 프로세스들이 큐 사이를 이동할 수 있는 스케줄링 방식이다.

• 다단계 피드백 큐 스케줄링 알고리즘: 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘
• 장점: 낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방할 수 있다.