[운영체제] CPU 스케줄링

 

 

CPU 스케줄링

---

CPU 스케줄링은 운영체제가 프로세스들에게 CPU 자원을 배분하는 것이다.

운영체제는 준비 큐에 있는 프로세스들 중에서 어떤 프로세스에게 CPU를 할당할지 결정한다.

시분할 시스템에서 각 프로세스들의 CPU 수행시간이 다르기 때문에 CPU 스케줄링을 통헤 적절히 CPU를 할당하여 빠른 사용자 응답을 제공하고, CPU와 입출력장치의 효율을 높일 수 있다.

 

 

 

 

스케줄링의 종류

---

 

단기 스케줄링

• 준비 큐에 있는 대기 상태 프로세스 중 어떤 프로세스를 다음으로 실행할지 스케줄링 알고리즘으로 결정한다.
• CPU 스케줄링이라고도 한다.

 

중기 스케줄링

• 너무 많은 프로세스에게 메모리를 할당해 성능이 저하되는 경우를 막기 위해, 메모리에 로드 된 프로세스 수를 동적으로 조절한다.
• 메모리에 프로세스가 많이 로드되면 스왑 아웃해서 일부 프로세스를 통째로 디스크에 저장한다.

 

장기 스케줄링

• 준비 큐에 어떤 프로세스를 넣을지 결정해 메모리에 올라가는 프로세스 수를 조절한다.
• 현대 운영체제에서는 시분할 시스템을 사용하기 때문에 대부분 사용하지 않는다.

 

 

 

 

 

스케줄링 알고리즘

---

스케줄링 알고리즘은 CPU 스케줄러(단기 스케줄러)가 준비 큐에 있는 프로세스 중 어떤 프로세스를 실행시킬지 결정하는데 사용된다.

CPU 사용률, 처리량, 응답시간, 반환시간, 대기시간 등의 기준으로 평가한다.

 

 

비선점형 스케줄링

---

비선점형 스케줄링은 실행 중인 프로세스가 종료될 때까지 다른 프로세스를 실행할 수 없음을 의미한다.

CPU 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 스케줄링 방법이다.

 

 

FCFS 스케줄링

• 선입선출(First Come First Served) 스케줄링
• 준비 큐에 먼저 들어온 프로세스가 우선순위를 갖는 알고리즘이다.
• 구현이 간단하지만 CPU 사용시간이 매우 긴 프로세스가 먼저 도착한다면 다수의 프로세스들이 긴 시간 기다리는 현상(convoy effect)이 발생한다는 단점이 있다.

 

SJF 스케줄링

• 최단 작업 우선(Shortest Job First) 스케줄링
• 실행시간이 짧은 프로세스가 우선순위를 갖는 알고리즘으로, 준비 큐에 있는 프로세스 중 CPU를 점유하는 시간이 가장 짧은 프로세스부터 실행한다.
• 평균 대기 시간이 가장 짧지만, 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에 밀려 기아 상태가 될 수 있다.

 

우선순위 스케줄링

• 프로세스들에 우선순위를 부여하고 가장 높은 우선순위를 가진 프로세스부터 실행하는 알고리즘이다.
• 우선순위를 정하는 기준은 다양한 방법이 있다.
• 단점은 프로세스가 기아 상태가 될 수 있다는 것이다.

 

💡 기아상태(Starvation)
     : 우선순위가 높은 프로세스만 수행되어 우선순위가 낮은 특정 프로세스가 계속 자원을 할당받지 못하는 상태

해결 방법
- 오래 기다린 프로세스의 우선순위 높이기 (에이징)
- 우선 순위가 아닌 요청 순서대로 처리하는 요청 큐 사용
- 프로세스 우선순위 수시 변경으로 각 프로세스에게 동등한 기회 부여

 

 

 

 

선점형 스케줄링

---

선점형 스케줄링은 스케줄러가 실행 중인 프로세스를 중단시키고 다른 프로세스를 실행할 수 있음을 의미한다.

프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법이다.

 

 

라운드 로빈(RR) 스케줄링

• 프로세스간 우선 순위가 없다.
• 각 프로세스들이 CPU를 연속적으로 사용할 수 있는 시간을 타임 퀀텀(타임 슬라이스)으로 제한된다. (일반적으로 시간 단위는 0~100ms)
  • 모든 프로세스를 순서대로 일정 시간 동안 실행하며, 일정 시간을 초과하면 다른 프로세스를 실행한다.
  • 한 프로세스가 타임 퀀텀만큼 CPU를 사용했다면, 타이머 인터럽트가 발생하고 준비 큐에 있는 다른 프로세스에게 CPU를 할당한다.
• 타임 퀀텀의 크기가 매우 중요하다.
  • 타임 슬라이스가 지나치게 크면 FCFS 스케줄링과 마찬가지로 convoy effect가 생길 여지가 있다.
  • 타임 슬라이스가 지나치게 작으면 콘텍스트 스위칭이 빈번하게 일어나서 오버헤드가 크다는 단점이 있다.
• 모든 프로세스가 반복 수행되어 응답 속도가 빠르다는 장점이 있다.

 

SRTF 스케줄링

• 최소 잔류 시간 우선(Shortest Remaining Time First) 스케줄링 - SJF의 선점 버전
• 준비 큐에서 실행 시간이 가장 짧게 남은 프로세스를 우선 수행하는 알고리즘이다.
• 현재 실행 중인 프로세스의 남은 CPU 실행 시간보다 실행시간이 더 짧은 프로세스가 준비 큐에 들어오면 CPU를 빼앗아 할당한다.
• 평균 대기 시간이 가장 짧지만, 실행 시간이 긴 프로세스는 영원히 CPU를 할당받지 못하는 기아 상태가 될 수 있다.

 

멀티 레벨 큐 스케줄링

• 준비 큐를 목적에 따라 여러 개로 분리해 사용하는 알고리즘이다.
• 분리한 큐는 각각 우선순위가 있고 각자 다른 스케줄링 알고리즘을 적용할 수 있다.
• 일반적으로 전위(foreground) 큐와 후위(background) 큐로 구분된다.
  • 전위 큐 : CPU 실행시간이 짧은 대화형 프로세스를 담기 위함 - 라운드 로빈 방식 적용 (응답 속도 중요)
  • 후위 큐 : CPU 실행시간이 긴 계산위주의 프로세스를 담기 위함 - FCFS 방식 적용 (성능 중요)
• 프로세스 뿐만 아니라 큐에 대한 스케줄링을 적용해야한다
  • 큐마다 다른 스케줄링 알고리즘 사용
  • 큐에 우선순위 부여
  • 큐별로 타임 슬라이스 여러개 지정

 

멀티 레벨 피드백 큐 스케줄링

• 멀티 레벨 큐 스케줄링의 발전된 형태로, 기아 현상을 방지 하기 위해 프로세스들을 여러 개의 준비 큐에 줄 세우는 방식이다.
• 프로세스들이 큐 사이를 이동할 수 있다.
• 각 큐들은 우선순위를 갖고 있고. 타임 슬라이스 동안 실행을 마치지 못한 프로세스는 점점 우선순위가 낮은 큐로 이동한다.
• 우선순위가 낮은 큐에서 너무 오래 기다린 프로세스들을 다시 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방할 수 있다.
• 구현이 복잡하지만 가장 일반적인 CPU 스케줄링 알고리즘이다.