혼공 컴+운 chapter11. CPU 스케줄링

11-1. CPU 스케줄링 개요

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

프로세스 우선순위

• 프로세스마다 우선순위가 다르다. 우선순위가 높은 프로세스란 빨리 처리해야 하는 프로세스들을 의미한다. 우선순위가 높은 프로세스에는 대표적으로 입출력 작업이 맣은 프로세스가 있다.
• 대부분의 프로세스들은 CPU와 입출력장치를 모두 사용하며 실행
• 입출력 집중 프로세스 : 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스.(실행 상태보다는 입출력을 위한 대기 상태에 더 많이 머무르게 된다.)
• CPU 집중 프로세스 : 복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스와 같이 CPU 작업이 많은 프로세스. ( 대기 상태보다는 실행 상태에 더 많이 머무르게 된다.)
• 입출력 집중 프로세스와 CPU 집중 프로세스가 동시에 CPU 자원 요구 => 입출력  집중 프로세스를 가능한 한 빨리 실행시켜 입출력 장치를 끊임없이 작동시키고, 그다음 CPU 집중 프로세스에 집중적으로 CPU 할당.

스케줄링 큐

• CPU를 사용할 다음 프로세스를 찾기 위해 운영체제가 일일이 모든 프로세스의 PCB를 뒤적거리는 것은 비효율적.
• 스케줄링 큐 : 운영체제는 메모리로 적재되고 싶은 프로세스들을 큐에 삽입하여 줄을 세우고, CPU를 이용하고 싶은 프로세스들 또한 큐에 삽입하여 줄을 세우고, 특정 입출력장치를 이용하고 싶은 프로세스들 역시 큐에 삽입하여 줄을 세운다 
• 큐 종류 : 준비큐, 대기큐
  • 준비큐 : CPU를 이요하고 싶은 프로세스들이 서는 줄
  • 대기큐: 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄
  •  

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

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

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

스케줄링 알고리즘의 종류

• 선입 선처리 스케줄링(FCFS 스케줄링)
  
  • 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식. CPU를 먼저 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식. 
  • 호위효과 : CPU 스케줄링에서 실행 시간이 긴 프로세스가 CPU를 사용하는 동안, 짧은 실행 시간을 가진 프로세스가 대기하는 현상
  • EX) 17ms 동한 CPU를 이용한느 프로세스 A, 5ms 동안 CPU를 이용하는 프로세스 B, 2ms 동안 CPU를 이용하는 프로세스 C가 차례로 준비 큐에 삽입된다면 평균 대기 시간은 (22 + 17 + 0) / 3 = 13(ms)
• 최단 작업 우선 스케줄링(SJF 스케줄링)
  • 준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식.
  • EX) CPU 사용 시간이 짧은 C와 B부터 실행한다면 C->B->A 평균 대기 시간 : (0+2+7)/3 = 3(ms)
• 라운드 로빈 스케줄링
  • 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식.
    • 타임 슬라이스: 프로세스가 CPU를 사요할 수 있는 정해진 시간.
  • 큐에 삽입된 프로세스들은 삽입된 순서대로 CPU를 이용하되 정해진 시간만큼만 CPU를 이요하고, 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입된다. (문맥교환 발생)
• 최소 잔여 시간 우선 스케줄링(SRT)
  • 최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 스케줄링 방식.
  • 최소 잔여 시간 우선 스케줄링 하에서 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다. 
• 우선순위 스케줄링
  • 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘
  • 최단 작업 우선 스케줄링, 최소 잔여 시간 우선 스케줄링 알고리즘은 넓은 의미에서 우선순위 스케줄링의 일종.
  • 기아현상 발생 : 우선순위 스케줄링은 우선순위가 높은 프로세스를 우선하여 처리하는 방식이기에 우선순위가 낮은 프로세스는(준비 큐에 먼저 삽입 되었음에도 불구하고) 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있다.
  • 기아현상 발생 해결 => 에이징 : 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
• 다단계 큐 스케줄링
  • 우선순위 스케줄링의 발전된 형태. 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식. 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있으면 그다음 우선순위 큐에 있는 프로세스들을 처리. 
• 다단계 피드백 큐 스케줄링
  • 다단계 큐 스케줄링의 발전된 형태. 다단계 큐 스케줄링에서는 프로세스들이 큐 사이를 이동할 수 없다. 우선순위가 낮은 프로세스는 계속 연기될 여지가 있다. 이를 보완한 스케줄링 알고리즘이 다단계 피드백 큐 스케줄링이다.
  • 프로세스들이 큐 사이를 이동할 수 있다. 새로 준비 상태가 된 프로세스가 있다면 우선 우선순위가 가장 높은 우선순위 큐에 삽입되고 일정시간동안 실행.
  • 프로세스가 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행. CPU를 비교적 오래 사용해야 하는 CPU 집중 프로세스들은 자연스레 우선순위가 낮아지고 CPU를 비교적 적게 사용하는 입출력 집중 프로세스들은 자연스레 우선순위가 높은 큐에서 실행이 끝난다. 
  • 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선수위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘.

---

추가문제

1. 준비 큐에 프로세스 A, B, C, D 순으로 삽입되었다고 가정했을 때, 선입 선처리 스케줄링 알고리즘을 적용한다면 어떤 프로세스 순서대로 CPU를 할당받게 되나?

-> 선입 선처리 스케줄링을 적용하면 큐에 삽입되어 있는 순서 A, B, C, D 순서대로 CPU를 할당받게 된다.