CPU 스케줄링

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

• 프로세스마다 우선순위가 다르다.
• 우선순위가 높은 프로세스란 빨리 처리해야하는 프로세스들을 의미한다.
• 입출력 작업이 많은 프로세스를 먼저 실행하는것이 효율적이다.
  • 입출력 작업을 담당하는 입출력 집중 프로세스는 실행 상태보다 입출력을 위한 대기 상태에 더 많이 머물기 때문이다.
  • 반대로 CPU 작업을 답당하는 CPU 집중 프로세스는 대기 상태보다는 실행 상태에 더 많이 머문다.
  • 그렇기 때문에 CPU 집중 프로세스와 입출력 집중 프로세스가 모두 동일한 빈도로 CPU를 사용하는 것은 비합리적이다.
  • 즉, 입출력장치가 입출력 작업을 완료하기 전까지는 입출력 집중 프로세스는 어차피 대기 상태가 될 예정이기 때문에 입출력 집중 프로세스를 얼른 먼저 처리해 버리면 다른 프로세스가 CPU를 사용할 수 있기 때문이다.
• PCB에 우선순위를 명시하고, 해당 우선순위를 기준으로 먼저 처리할 프로세스를 결정한다.

스케줄링 큐 : 운영체제는 프로세스들에게 줄을 서서 기다릴 것을 요구한다. 즉, 운영체제는 메모리에 적재되고 싶은 프로세스들을 큐에 삽입하고 줄을 세운다.

• 준비큐와 대기큐가 있다.
  • 준비큐 : CPU를 이용하고 싶은 프로세스들이 서는 줄
  • 대기큐 : 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄
• 운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행하되, 그 중 우선순위가 높은 프로세스를 먼저 실행한다.

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

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

CPU 스케줄링 알고리즘

• 선입 선처리 스케줄링 : FCFS 스케줄링으로 단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식
  • 가장 공정해 보이지만, 프로세스들이 기다리는 시간이 매우 길어질 수 있다.
  • 가장 첫 번째 프로세스가 17ms시간이라면, 두 번째, 세 번째 프로세스는 대기시간이 훨씬 길어질 수 밖에 없다 이런 현상을 호위 효과라고한다.
• 최단 작업 우선 스케줄링 : CPU이용시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식
• 라운드 로빈 스케줄링 : 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식.
  • 타임 슬라이스란 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미한다.
  • 즉, 라운드 로빈 스케줄링은 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링이다.
• 최소 잔여 시간 우선 스케줄링 : 최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 스케줄링 방식
  • 즉, 최소 잔여 시간 우선 스케줄링에서 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.
• 우선순위 스케줄링 : 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스로부터 실행하는 스케줄링 알고리즘
  • 최단 작업 우선 스케줄링은 작업시간이 짧은 프로세스에 높은 우선순위를 부여하는 방식
  • 최소 잔여 시간 우선스케줄링은 남은시간이 짧은 프로세스에 높은 우선순위를 부여하는 방식
  • 다만, 우선순위 스케줄링의 근본적인 문제는 우선순위가 높은 프로세스를 우선하여 처리하는 방식이기에 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있다. 이를 기아현상이라고 한다.
  • 이를 방지하기 위해 에이징을 이용한다. 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식.
• 다단계 큐 스케줄링 : 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식. 
  • 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐에 비어 있으면 그다음 우선순위 큐에 있는 프로세스들을 처리하는 방식.
  • 큐를 여러 개 두면 프로세스 유형별로 우선순위로 구분하여 실행하는 것이 편리해진다.
• 다단계 피드백 큐 스케줄링 : 다단계 큐 스케줄링의 발전된 형태. 다단계 큐 스케줄링에서는 프로세스들이 큐 사이를 이동할 수 없기 때문에 기아 현상이 발생할 수 있다. 차이점은 큐 사이를 이동할 수 있다는 점이다.
  • 새로 준비 상태가 된 프로세스가 있다면 우선 순위가 가장 높은 우선순위 큐에 삽입되고 일정시간동안 실행한다.
  • 만약 프로세스가 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행되고 이런식으로 진행된다.
  • 너무 오래기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방할 수 있다.