CPU 스케줄링 알고리즘

1. 선입 선처리 스케줄링
   1. FCFS(First Come First Served) 스케줄링
   2. 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
   3. 먼저 CPU를 요청한 프로세스부터 CPU 할당
   4. 단점 : 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용 (=호위 효과)
2. 최단 작업 우선 스케줄링
   1. SJF(Shortest Job First) 스케줄링
   2. 호위 효과를 방지하려면?
   3. CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스는 먼저 실행
   4. CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식
3. 라운드 로빈 스케줄링
   1. RR(Round Robin) 스케줄링
   2. 선입 선처리 스케줄링 + 타임 슬라이스
   3. 타임슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
   4. 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
   5. 정해진 시간을 모두 사용했음에도 프로세스가 완료되지 않아도 큐의 맨 뒤로 보냄
4. 최소 잔여 시간 우선 스케줄링
   1. SRT (Shortest Remaining Time) 스케줄링
   2. 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
   3. 최단 작업 우선 스케줄링 : 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘
   4. 라운드 로빈 스케줄링 : 정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 알고리즘
   5. 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업시간이 가장 적은 프로세스 선택
5. 우선순위 스케줄링
   1. 프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
   2. 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
   3. 최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링 은 우선순위 스케줄링 안에 포함
   4. 우선순위 스케줄링의 근본적인 문제점, 기아(starvation) 현상
      1. 우선순위 높은 프로세스만 주구장창 실행
      2. 우선순위 낮은 프로세스는 준비 큐에 먼저 삽입되었음에도 불구하고 실행 연기
   5. 이를 방지하기 위한 기법 : 에이징
      1. 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
      2. 우선순위가 낮아도 언젠가는 우선순위가 높아진다
6. 다단계 큐 스케줄링
   1. Multilevel Queue 스케줄링
   2. 우선순위 스케줄링의 발전된 형태
   3. 우선순위 별로 준비 큐를 여러 개 사용하는 스케줄링 방식
      1. 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
      2. 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리
7. 다단계 피드백 큐 스케줄링
   1. Multilevel feedback queue 스케줄링
   2. 다단계 큐 스케줄링의 발전된 형태
   3. 큐 간의 이동이 가능한 다단계 큐 스케줄링
   4. 다단계 큐 스케줄링에서는 기본적으로 큐 간의 이동 불가
      1. 우선순위 낮은 프로세스는 계속해서 실행 연기 우려
      2. 기아 현상 발생 가능
   5. CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고 입출력 집중 프로세스의 우선순위는 상대적으로 높아짐
   6. 에이징 기법도 적용 될 수 있음