[운영체제] CPU 스케줄링

CPU 스케줄링

프로세스 우선순위

• 입출력 작업이 많은 프로세스가 CPU 작업이 많은 프로세스보다 우선순위가 높다.

  • 어차피 잠깐 실행 후 대기 상태로 넘어가기 때문에 먼저 실행해준다.

스케줄링 큐

• 반드시 FIFO 구조인 것은 아니다.
• 준비 큐와 대기 큐 등이 있다.
• 준비 큐: CPU를 이용하려는 프로세스들이 서는 줄
• 대기 큐: 입출력 장치를 이용하려는 프로세스들이 서는 줄
  • 입출력 완료시 준비큐로 이동한다.
  • 같은 장치를 요구한 프로세스들은 같은 큐에서 대기한다.
• 실행 차례가 끝나 타임아웃 인터럽트가 발생하면 다시 준비 큐로 이동한다.

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

• 어떤 프로세스가 실행상태에 있는데 당장 실행이 급한 어떤 프로세스가 있을때 선점형 스케줄링은 현재 CPU를 사용중인 프로세스로부터 CPU자원을 빼앗아 사용하고, 비선점형 스케줄링은 현재 CPU를 사용중인 프로세스의 작업이 끝날 때까지 기다린다.
• 선점형 스케줄링(preemptive scheduling)
  • 한 프로세스의 자원 독점을 막고 자원을 고르게 배분할 수 있다.
  • 문맥 교환 과정에서 오버헤드(프로세스나 스레드를 교체할 때 발생하는 추가적인 시간 또는 리소스 소모)가 발생할 수 있다.
• 비선점형 스케줄링(non-preemptive scheduling)
  • 문맥 교환 과정에서 오버헤드 발생이 적다.
  • 모든 프로세스가 자원을 고르게 사용하기 어렵다.

CPU 스케줄링 알고리즘

1. 선입 선처리 스케줄링(FCFS, First Come First Served)
   • 준비 큐에 삽입된 순서대로 처리
   • 시간이 오래걸리는 프로세스가 앞에 있을 때 프로세스들이 기다리는 시간이 전체적으로 매우 길어지는 호위 효과가 발생할 수 있다.
   • 비선점 스케줄링
2. 최단 작업 우선 스케줄링(SJF, Shortest Job First)
   • CPU 사용 시간이 짧은 순서대로 처리
   • 기본적으로는 비선점형 스케줄링으로 분류
3. 라운드 로빈 스케줄링(RR, Round Robin)
   • 선입 선처리 스케줄링 + 타임 슬라이스
   • 정해진 타임 슬라이스 시간 만큼 돌아가며 CPU를 이용
   • 선점형 스케줄링
4. 최소 잔여 시간 우선 스케줄링(SRT, Shortest Remaining Time)
   • 최단 작업 우선 스케줄링 + 라운드로빈 스케줄링
   • 정해진 시간만큼 CPU를 이용하고 다음 프로세스로 남은 시간이 가장 적은 프로세스 선택
   • 선점형 스케줄링
5. 우선순위 스케줄링(Priority)
   • 프로세스별로 우선순위가 주어지고 이에 따라 CPU 할당
   • 우선순위가 낮은 프로세스는 실행이 계속 연기되는 기아(starvation) 현상 발생
   • 오래 대기한 프로세스의 우선순위를 점차 증가시키는 에이징(aging)으로 위 문제 해결
   • 비선점형 스케줄링
6. 다단계 큐 스케줄링(MLQ, Multi Level Queue)
   • 우선순위별로 준비 큐를 여러개 사용하여 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
   • 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐의 프로세스 처리
   • 큐 간의 이동이 불가능, 우선순위가 낮은 프로세스에 기아 현상 발생 우려가 있다.
7. 다단계 피드백 큐 스케줄링(MLFQ, Multi Level Feedback Queue)
   • 다단계 큐 스케줄링의 발전된 형태로 큐 간의 이동이 가능하다.
   • 새로 준비상태가 된 프로세스를 가장 우선순위가 높은 큐에 삽입하고 타임 슬라이스에 실행을 다 끝내지 못하면 다음 우선순위의 큐에 넣은 방식으로 CPU 집중 프로세스의 우선순위를 점차 낮추고 입출력 집중 프로세스의 우선순위를 높인다.