---

CPU 스케줄링

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

• 각각의 프로세스마다 우선순위가 다르기 때문에, 프로세스 우선순위대로 스케줄링되어야한다.
• 스케줄링 큐 - CPU를 이용하고 싶은 프로세스들이 서는 줄
  • 준비 큐 - CPU를 이용하기 위해서 기다리는 줄. 준비 상태의 프로세스들이 대기하다가 실행상태로 전환되면 실행되다가, 타임아웃에 의해서 준비상태가 되면 다시 준비 큐로 들어온다.
  • 대기 큐 - 입출력장치를 이용하기 위해서 기다리는 줄
    
    
• 선점형 스케줄링 - 현대 운영체제가 사용하고 있는 방식. 어떤 프로세스가 CPU를 할당받아 실행 중이더라도, 운영체제가 이를 강제로 뺏을 수 있다. 처리 시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능하지만, 그만큼 문맥 교환과정(context switching)에서의 오버헤드가 발생할 수 있다.
  
  
• 비선점형 스케줄링 - 어떤 프로세스가 CPU를 사용하고 있다면 이를 뺏을 수 없는 방식. 선점형 스케줄링에 비해 문맥교환에서 발생하는 오버헤드가 적다. 하지만, 모든 프로세스가 골고루 자원을 이용하기 어렵다.
  
  

CPU 스케줄링 알고리즘

선입선출 스케줄링(FCFS, First Come First Served)

• 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
• 만약 먼저 삽입된 프로세스들이 CPU를 오랫동안 점유한다면, 나머지 프로세스들이 기다리는 시간이 매우 길어질 수 있다

최단 작업 우선 스케줄링(SJF, Shortest Job First)

• CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스는 먼저 실행

라운드 로빈 스케줄링(RR, Round Robin)

• 선입선출 + 타임 슬라이스. 정해진 시간만큼 돌아가며 CPU를 이용하는 선점형 스케줄링
• 타임 슬라이스의 크기가 중요하다. 너무 크면 선입선출과 동일하고, 너무 작으면 잦은 문맥교환으로 인한 오버헤드가 발생한다

최소 잔여 시간 우선 스케줄링(SRT, Shortest Remaining Time)

• 최단 작업우선 + 라운드 로빈
• 정해진 시간만큼 CPU를 사용하되, 다음으로 CPU를 사용할 프로세스는 남은 작업시간이 가장 적은 프로세스가 사용하는 것

우선순위 스케줄링

• 프로세스들에게 우선순위를 부여하고, 가장 우선순위가 높은 프로세스부터 실행
• 우선순위가 같다면, 선입선출로 진행
• 기아현상(Starvation)의 문제가 있음 → 우선순위가 높은 프로세스들만 주구장창 실행됨. 우선순위가 낮은 프로세스는 먼저 큐에 들어왔는데도 실행이 연기됨
  • 에이징(aging) - 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식, 나이를 먹듯이. 우선순위가 낮아도 실행을 보장

다단계 큐 스케줄링(Multilevel queue)

• 우선순위 스케줄링의 발전된 형태
• 우선순위별로 준비큐를 여러개 사용하는 스케줄링방식
• 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
• 우선순위가 가장 높은 큐가 비어있다면 그 다음 우선순위 큐에 있는 프로세스 처리
• 하지만, 큐 간의 이동이 안됨으로, 우선순위가 낮은 프로세스는 계속 순위가 낮은 큐에 머물러 있을 것 → 기아현상 발생 가능있음

다단계 피드백 큐 스케줄링(Multilevel Feedback queue)

• 다단계 큐 스케줄링이 발전된 형태
• 큐 간의 이동이 가능한 다단계 큐 스케줄링 → 다단계 큐 스케줄링의 기아문제 해결
• 기본적으로 CPU를 적게 사용하는 프로세스의 우선순위는 상대적으로 낮아지고, CPU를 많이 사용하는 프로세스는 상대적으로 높아짐
• 에이징 방법 적용가능
• CPU 스케줄링의 가장 일반적인 형태