3. cpu 스케쥴링

1. 스케줄링의 단계

고수준 스케줄링(승인 스케줄링)

• 시스템 내의 전체 작업수를 조정한다.
• 프로세스를 승인할지 거부할지를 결정

중간수준 스케줄링

• 활성화된 프로세스를 보류상태(또는 중지)로 만들거나 다시 활성화 한다.
• 저수준 스케줄링이 잘 일어나도록 완충하는 역할을 한다.
• 시스템의 과부하를 막는 방식

저수준 스케줄링

• 어떤 프로세스를 CPU에 할당하고 대기, 실행상태로 보낼지 결정하는 스케줄링이다.

순서

작업대기 ==⇒ 보류상태 ==⇒ 활성상태 ==⇒ 실행상태 ==⇒ 종료

고수준 중간수준 저수준

2. 스케줄링의 목적

• 모든 프로세스가 공평하고 효율적으로 작업하도록 하는 것이다.
• 먼저 처리해야 하는게 있으므로 일정부분 공평함을 희생한다.

3. 선점과 비선점

• 선점형 스케줄링: CPU를 할당받은 프로세스를 다른 프로세스가 강제로 뺏음
  • 인터럽트가 발생
  • 문맥교환 발생 ⇒ 오버헤드
  • 저수준 스케줄링은 선점형을 이용한다.
• 비선점 스케줄링: 프로세스가 한번 CPU를 점유하면 끝날때 까지 뺏을수 없다.
  • 필요한 문맥교환만 일어나지만 오래기다리게 되어 시스템 효율이 떨어진다.
  • 일괄 작업 방식에 사용한다.
• CPU 집중 프로세스: CPU를 많이 사용하여 CPU burst가 많은 프로세스 - 입출력이외의 거의 모든 프로세스
• 입출력 집중프로세스: 입출력을 많이 사용해 I/O burst가 많은 프로세스 - 예를 들어 accept(), connect(), send(), recv(), open(), close(), fgets(), printf()

두 프로세스가 같이 대기상태에 있다면 입출력 집중 프로세스에 먼저 CPU를 할당시키는 것이 더 효율적이다.

왜냐하면 입출력 집중 프로세스는 CPU를 빠르게 쓰고 입출력 버스트를 하러 나가기 때문에 다른 프로세스가 오래 기다리지 않아도 된다.

• 전면 프로세스 : GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓여 현재 입출력이 사용되고, 사용자와 상호작용이 가능해 상호작용 프로세스라고도 불림 (워드 프로세스)
• 후면 프로세스 : 사용자의 입력 없이 작동하여 일괄 작업 프로세스라고 불림 (압축 프로세스)

전면 프로세스는 사용자의 요구에 즉각 즉각 반응해야 하지만 후면 프로세스는 그럴 필요가 없다. 따라서 전면 프로세스를 먼저 처리해 줘야 한다.

CPU 스케줄러 대부분은 프로세스에 우선순위를 매겨 우선순위가 높은(우선순위 숫자가 작은) 프로세스부터 처리되도록 한다.

• 커널 프로세스 > 일반 프로세스
• 전면 프로세스 > 후면 프로세스
• 대화형 프로세스 > 일괄 처리 프로세스
• 입출력 집중 프로세스 > CPU 집중 프로세스

4. 스케줄링 알고리즘

스케줄링 알고리즘은 주로 프로세스의 평균 대기시간을 측정한다.

1. FCFS
   • 선입 선출, 프로세스마다 우선순위가 동일
   • 비선점형 스케줄링
   • 처리시간이 긴 프로세스가 CPU를 차지하면 뒤의 프로세스들이 하염없이 기다린다.
   • 입출력 작업등을 요청하는 경우 CPU의 쉬는 시간이 많아진다.
2. SJF
   • 실행시간이 짧은 작업부터 할당한다
   • 비선점형 스케줄링
   • 실행시간이 긴 프로세스는 아사현상이 발생한다 ← 에이징으로 해결가능하지만 기준이 모호하다.
3. HRN
   • Highest Response Ratio Next → 우선순위 = (대기시간+CPU 사용시간) / CPU 사용시간
   • 선점형 스케줄링
   • SJF의 아사현상을 해결하기 위해 에이징을 구현한 것이다.
4. Round Robin
   • CPU를 사용할 수 있는 최대시간인 타임 슬라이스가 있다.
   • 선점형 프로세스
   • FCFS와 대기시간이 같다면 문맥교환시간이 추가되어 더 비효율 적이다. 따라서 타임슬라이스를 적장하게 정해야한다.
     • 너무 크다면 - FCFS와 다를게 없다
     • 너무 작다면 - 문맥교환 시간이 많이 추가되어 오래 걸린다.
5. SRT
   • SJF와 Round Robin의 혼합형
   • 선점형 스케줄링
   • RR 이지만 시간이 적은 프로세스부터 실행한다.
     • 프로세스의 남은 시간을 주기적으로 계산해야하고 문맥교환이 발생한다.
     • 프로세스의 종료시간을 모두 계산할 수 없기 때문에 힘들고 아사현상이 발생한다.
6. 우선순위
   • 프로세스에 우선순위를 부여한다. 위에서 나온것들이 있음
     • 비선점형
       • SJF: 남은 시간이 적은 프로세스에게 우선순위
       • HRN: 대기시간긴 프로세스를 고려한 우선순위
     • 선점형
       • SRT: 남은 시간이 적은 프로세스에 우선순위
   • 우선순위를 따지기 때문에 아사현상이 일어난다.
   • 큐가 계속 변경된다.
   • 시스템의 효율보다 프로세스의 우선순위를 따지는게 중요하다.
7. 다중큐
   • 선점형 스케줄링
   • 우선순위에 따라 여러개의 큐를 사용하는 방식이다.
   • 우선순위가 낮은건 연기되므로 다중 피드백 큐를 이용한다.
8. 다중피드백큐
   • 선점형 스케줄링
   • 라운드 로빈을 사용하고 CPU를 할당받은 후 우선순위가 낮아져서 큐에 삽입된다.
   • 우선순위에 따라 타임슬라이스를 다르게 주는데 우선순위가 낮아질수록 높게 준다.
   • 낮은 프로세스에게 좀더 긴 시간을 줘서 아사현상을 막는다.
   • 요즘 대부분의 운영체제에서 사용하는 방식이다.