CPU scheduling

모든 프로세스들은 먼저 cpu를 사용하고 싶어한다. 운영체제가 이 프로세스들에게 합리적으로 cpu 자원을 할당하는 것을 cpu 스케줄링이라고 한다.

프로세스 우선순위

• 입출력 집중 프로세스
  입출력장치를 기다리는 작업(I/O burst)와 같은 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스
  입출력 집중 프로세스는 실행 상태보다는 입출력을 위한 대기상태에 더 많이 머무르게 된다.
  
• cpu 집중 프로세스
  cpu를 이용하는 작업(CPU burst)와 같은 복잡한 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스
  cpu 집중 프로세스는 대기 상태보다는 실행 상태에 더 많이 머무르게 된다.
  만약 입출력 집중 프로세스와 cpu집중 프로세스가 동시에 cpu작업을 요구했다면, 입출력 집중 프로세스를 빨리 실행시켜 입출력 장치를 끊임없이 작동시키고, 그 다음 cpu집중 프로세스에 집중적으로 cpu를 할당하는 것이 효율적이다.

이렇게 cpu를 차례대로 돌아가며 사용하는 것보다, 각각의 상황에 맞게 cpu를 배분하는 것이 효율적이다.운영체제는 상황에 맞게, 중요도에 맞게 프로세스마다 우선순위를 부여하고, PCB에 명시한다.우선순위가 높은 프로세스는 더 빨리, 더 자주 실행된다.

Scheduling queue

PCB에 우선순위가 적혀있긴 하지만, cpu를 사용할 다음 프로세스를 찾기 위해 운영체제가 모든 프로세스의 PCB를 탐색하는 것은 비효율적이다. 때문에 운영체제는 cpu를 사용하거나, 메모리에 적재되고 싶거나, 입출력장치를 사용하고 싶은 프로세스들을 모두 줄 세운다. 이것을 스케줄링 큐라고 한다. 우선순위가 낮은 프로세스들이 먼저 큐에 줄을 섰다 하더라도, 우선순위가 높은 프로세스는 그들보다 먼저 처리된다.
준비 큐는 cpu를 이용하고 싶은 프로세스들이 서는 줄을 의미하고, 대기 큐는 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄을 의미한다.

스케줄링의 종류

프로세스가 cpu를 잘 사용하고 있는데, 다른 급한 프로세스가 cpu를 당장 사용하길 요청한다면 어떻게 할까?

• 선점형 스케줄링
  선점형 스케줄링은 다른 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에게 할당하는 방식이다. 선점형 스케줄링 방식은 중간에 급한 프로세스가 끼어들 수 있으므로, 한 프로세스의 자원 독점을 막고 프로세스들에게 골고루 자원을 분배할 수 있지만, context-swtiching 과정에서 오버헤드가 발생할 수 있다.
  

• 비선점형 스케줄링
  비선점형 스케줄링은 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 대기상태에 접어들기전까진 다른 프로세스가 끼어들 수 없는 방식이다. 비선점형 스케줄링 방식은 선점형 스케줄링 보다 오버헤드가 적지만 당장 자원을 사용해야하는 프로세스도 무작정 기다리는 수 밖에 없다.
  
  

스케줄링 알고리즘의 종류

• 선입 선처리 스케줄링(FCFS 스케줄링)
  준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식
  cpu를 먼저 요청한 프로세스 부터 cpu를 할당한다. 한 프로세스가 cpu를 길게 사용하면 나머지 프로세스들은 대기 시간이 길어질 수 밖에 없다. 10ms를 사용하는 A와 2ms를 이용하는 B가 있을때 A가 먼저 대기 큐에 들어갔다면, B는 2ms를 이용하기 위해 10ms를 기다려야한다. 이를 호위효과라 한다.
  
• 최단 작업 우선 스케줄링(SJF 스케줄링)
  호위효과를 방지하기 위해선 cpu사용시간이 짧은 프로세스를 먼저 실행하면 된다. 이렇게 cpu사용 시간이 짧은 프로세스 부터 실행하는 방식을 최단 작업 우선 스케줄링 이라고 한다.
  
• 라운드 로빈 스케줄링
  각 프로세스가 cpu를 사용할 수 있는 정해진 시간(타임 슬라이스)를 정해 정해진 타임 슬라이스 만큼의 시간동안 돌아가며 cpu를 이용하는 선점형 스케줄링 방식
  타임슬라이스가 너무 크면 선입 선처리 방식과 다를게 없어 호위효과가 생길여지가 있고, 타임슬라이스가 너무 작으면 cpu는 프로세스를 처리하는 일보다 context-switching비용이 더 들게 된다.
  
• 최소 잔여 시간 우선 스케줄링(SRT스케줄링)
  최단 작업 우선 스케줄링과 라운드 로빈 스케줄링을 합친 방식
  프로세스들은 정해진 타임 슬라이스만큼 cpu를 사용하되, cpu를 사용할 다음 프로세스는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.
  
• 우선순위 스케줄링
  우선순위 스케줄링은 프로세스들에게 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘
  우선순위가 높은 프로세스를 우선하여 처리하는 방식이기에 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있다. 이를 starvation이라고 한다.이를 해결하기 위해aging을 사용한다. 이는 오랫동안 대기한 프로세스의 우선순위를 점차 높여주는 방식이다.
  
• 다단계 큐 스케줄링
  다단계 큐 스케줄링은 우선순위별로 준비 큐를 여러개 사용하는 스케줄링 방식이다.
  우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐에 있는 프로세스들을 처리한다.이렇게 큐를 여러개 두면 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해진다. 또한 큐별로 타임 슬라이스를 여러개 지정할 수 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수 있다.
  
• 다단계 피드백 큐 스케줄링
  다단계 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 없다. 따라서 우선순위가 낮은 프로세스는 계속 연기
  될 수 있다. 이는 위에서 말한 것 처럼 starvation을 야기할 수 있다. 다단계 피드백 큐 스케줄링은 낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면, 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 이용하여 기아 현상을 예방할 수 있다.