[3주차] CPU 스케줄링

CPU 스케줄링

CPU 스케줄링에 대해 설명해주세요.

• 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
  • 여러 프로세스의 상황을 고려하여 CPU와 시스템 자원을 어떻게 배분할지 결정한다.

어떤 프로세스에게 CPU를 할당할것인가?
CPU 스케줄러 = 프로세서 스케줄러

 

스케줄러의 종류는 무엇이 있나요?

• 고수준 스케줄링 (장기 스케줄링, 작업 스케줄링) : 시스템 내의 전체 작업 수를 조절하는 것
  • 작업은 여러개의 프로세스로 이루어질 수 있다.
  • 어떤 작업을 시스템이 받아들일지 결정한다.
  • 실행 가능한 프로세스의 총 개수가 정해진다.
• 중수준 스케줄링 : 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막는다.
  • 시스템에 과부하가 걸려서 전체 프로세스 수를 조절해야한다면, 이미 활성화된 프로세스 중 일부를 보류 상태로 보낸다.
    • 보류된 프로세스는 처리 능력에 여유가 생기면 다시 활성화된다.
  • 저수준 스케줄링이 원만하게 이루어지도록 완충하는 역할을 한다.
• 저수준 스케줄링(단기 스케줄링): 어떤 프로세스에 cpu를 할당할지 결정한다.
  • 준비 상태의 프로세스를 실행 상태로 보내고, 실행 상태의 프로세스를 대기 상태로 보낸다.
    • 프로세스 상태를 변경한다.
  • 실제로 작업이 이루어진다.
  • 오늘 날의 CPU 스케줄러는 대부분은 중간 수준 스케줄링과 저수준 스케줄링으로 구성되어있다.

CPU 스케줄러는 특별한 명시가 없는 한 저수준 스케줄러를 의미한다.

 

프로세스 우선순위

• 프로세스마다 우선순위가 다르다.
• 우선순위가 높은 프로세스는 더 빨리, 자주 실행된다.
  • 입출력 작업이 많은 프로세스는 우선순위가 높다.
• 우선순위는 PCB에 기록된다.

일반적으로 운영체제 프로세스는 일반 프로세스(입출력, cpu 프로세스)보다 우선적으로 cpu를 배정받는다.
시스템이 안정적으로 수행되기 위해서이다.

 

입출력 집중 프로세스가 CPU 집중 프로세스보다 우선순위가 높은 이유

• 입출력 집중 프로세스: 입출력 작업(입출력 버스트)이 많은 프로세스
  • ex) 비디오 재생
• CPU 집중 프로세스: CPU 작업(CPU 버스트)이 많은 프로세스
  • ex) 복잡한 수학연산, 그래픽 처리 작업
• 입출력 집중 프로세스는 대부분의 시간을 입출력을 대기하는데 사용한다.
  • 입출력이 진행되는 동안 CPU를 다른 프로세스에 할당할 수 있어 CPU 유휴 시간을 줄일 수 있다.
  • 입출력 작업과 CPU 작업이 병렬 처리된다.
• 입출력 집중 프로세스가 먼저 실행되도록 하고, 대기하는 동안 CPU 집중 프로세스가 cpu를 사용하도록 한다.
  • 시스템의 전체적인 성능이 향상된다.

사이클 훔치기: 입출력 집중 프로세스가 cpu 집중 프로세스보다 실행 상태에 먼저 들어가는 것

 

전면 프로세스가 후면 프로세스보다 우선순위가 높다.

• 전면 프로세스: 사용자와 상호작용하는 프로세스
• 후면 프로세스: 사용자와 상호작용이 없는 프로세스
• 사용자의 요구에 즉각 반응하기 위해 전면 프로세스가 후면 프로세스보다 우선순위가 높다.

 

스케줄링 큐

• 운영체제는 프로세스들에 줄을 서서 기다릴 것을 요구한다.
  • 운영체제가 매번 모든 pcb를 검사하여 cpu를 할당할 프로세스를 결정하는 일이 번거롭기 때문이다.
  • 스케줄링 큐로 구현하고 관리한다.
• 준비 큐: CPU를 이용하고 싶은 프로세스들이 서는 줄
  • 한번에 한 프로세스를 선택하여 cpu를 할당한다.
• 대기 큐: 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄
  • 장치 별로 입출력 큐를 분류한다.
  • 여러 프로세스가 하나의 입출력을 기다릴 경우 동시에 여러 프로세스가 준비 큐로 이동할 수 있다.
    
    

 

선점형 스케줄링과 비선점형 스케줄링의 차이가 무엇인가요?

 

선점형 스케줄링

• 프로세스가 cpu를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식
  • ex) 인터럽트 - 프로세스가 정해진 시간을 다 사용하면 타이머 인터럽트가 발생하여 cpu 자원을 빼앗는다.
• 장점: 하나의 프로세스가 자원을 독점하는 것을 막을 수 있다.
• 단점: 문맥 교환 과정에서 오버헤드가 발생할 수 있다.
• 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합하다.

대부분의 저수준 스케줄러는 선점형 스케줄링 방식을 사용한다.

 

비선점형 스케줄링

• 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 스케줄링 방식
  • 하나의 프로세스가 자원 사용을 독점할 수 있다.
• 장점: 문맥 교환에서 발생하는 오버헤드가 적다.
• 단점: 모든 프로세스가 골고루 자원을 사용할 수 없다.
• 과거의 일괄 작업 시스템에서 사용하던 방식이다. (현재는 효율이 떨어져서 사용X)

 

선입선출 스케줄링(FCFS)에 대해 설명해주세요.

• FCFS : First Come First Served
• 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 스케줄링 방식
  • 준비 큐가 하나이므로 모든 프로세스는 우선순위가 동일하다.
• 호위 효과(convoy effect): CPU를 오래 사용하는 프로세스가 먼저 도착하면 프로세스들이 기다리는 시간이 매우 길어질 수 있다.

 

최단 작업 우선 스케줄링(SJF)에 대해 설명해주세요.

• SJF : Shortest Job First
• 준비 큐에 삽입된 프로세스들 중 실행시간이 가장 짧은 작업부터 CPU를 할당하는 스케줄링 방식
• 기본적으로 비선점형 스케줄링으로 분류되지만, 선점형 방식(최소 잔류 시간 우선 스케줄링)도 있다.
• 한계
  • 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.
    • 사용자의 상호작용이 빈번하게 발생하기 때문이다.
  • 공평하지 못하다.
    • 실행시간이 긴 프로세스가 기아 현상이 발생할 수 있다.

 

HRN 스케줄링

• Highest Response Ratio Next : SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘
• 최고 응답률 우선 스케줄링
• 우선순위 = (대기시간 + CPU 사용 시간) / CPU 사용 시간
• 대기시간과 CPU 사용 시간을 고려하여 스케줄링을 한다.
  • 대기 시간을 고려함으로써 아사 현상을 완화한다.
• 여전히 공평성을 위배하기 때문에 많이 사용되지 않는다.
  • 오랜 대기 시간의 작업보다 짧은 작업이 먼저 실행될 수 있다.

 

최소 잔류 시간 우선 스케줄링(SRTF, SRT) 방식에 대해 설명해주세요.

• SRTF : Shortest Remaining Time First
• 최단 작업 우선 스케줄링(SJF)과 라운드 로빈(선점형)을 합친 스케줄링 방식이다.
  • 남아있는 작업 시간이 가장 적은 프로세스부터 정해진 타임 슬라이스만큼 cpu를 사용한다.
• SJF 스케줄링과 마찬가지로 운영체제가 프로세스의 종료 시간을 예측하기 어렵고, 아사 현상이 일어난다.

 

라운드 로빈 스케줄링에 대해 설명해주세요.

• 선입선출 스케줄링에 타임 슬라이스 개념이 더해진 스케줄링 방식이다.
  • 타임 슬라이스: 각 프로세스가 cpu를 사용할 수 있는 정해진 시간
  • 스케줄링 큐에 삽입된 순서대로 cpu를 이용하되, 정해진 타임 슬라이스 시간 동안 돌아가며 이용한다.
• 선점형 스케줄링 방식이다.
  • 타임 슬라이스를 모두 이용하면 문맥교환이 일어나며 다시 준비 큐의 맨 뒤에 삽입된다.
• 타임 슬라이스 크기에 따라 시스템 성능에 영향을 준다.
  • 타임 슬라이스가 큰 경우: FCFS 스케줄링과 비슷해진다.
  • 타임 슬라이스가 작은 경우: 문맥 교환으로 많은 시간을 낭비한다.

 

우선순위 스케줄링에 대해 설명해주세요.

• 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 방식이다.
  • 우선순위가 같은 프로세스들은 선입 선처리(FCFS)로 스케줄링된다.
• 우선순위 스케줄링은 기아 현상를 발생시키는 문제를 가진다.

 

기아 상태(기아 현상)가 무엇인가요?

• 우선순위가 낮은 프로세스가 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기되는 현상

 

기아 상태를 어떻게 해결할 수 있나요?

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

 

멀티 레벨 큐 스케줄링(다단계 큐 스케줄링)에 대해 설명해주세요.

• 우선순위 별로 준비 큐를 여러개 사용하는 스케줄링 방식
  • 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있으면, 그 다음 우선순위 큐에 있는 프로세스들을 처리한다.
  • 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리하다.
• 큐 별로 타임 슬라이스를 여러개 지정하거나, 큐마다 다른 스케줄링 알고리즘을 사용할 수 있다.
• 기아 현상이 발생할 수 있다.

 

멀티 레벨 피드백 큐 스케줄링(다단계 피드백 큐 스케줄링)에 대해 설명해주세요.

• 멀티 레벨 큐 스케줄링에서 기아 현상이 발생하지 않도록 보완한 스케줄링 방식
  • 프로세스들이 다른 레벨의 준비 큐 사이를 이동한다.
• CPU를 오래 사용해야하는 프로세스는 점차 우선순위가 낮아진다.
  • 새로 준비 상태가 된 프로세스는 우선순위가 가장 높은 우선순위 큐에 삽입되고 일정 시간(타임 슬라이스)동안 실행된다.
  • 프로세스가 해당 큐에서 실행이 끝나지 않는다면 그 다음 레벨의 우선순위 큐에 삽입되어 실행된다.
  • CPU 집중 프로세스는 우선순위가 점차 낮아지고, 입출력 집중 프로세스는 우선순위가 높은 상태에서 종료된다.
• 에이징 기법 사용 : 낮은 우선순위의 프로세스를 점차 높은 우선순위 큐로 이동시켜 기아 현상을 예방할 수 있다.
• 우선순위가 낮아질 수록 해당 큐의 타임 슬라이스가 커진다.
  • 어렵게 얻은 CPU를 좀 더 오랫동안 사용할 수 있도록 하기 위해서이다.
  • 마지막 큐는 FCFS 스케줄링 방식으로 동작한다.

가장 일반적인 CPU 스케줄링 알고리즘이다.