[OS] CPU 스케줄링

< CPU 스케줄링 알고리즘 > 

1. FCFS - 비선점 
   1. CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받음
   2. convoy effect 발생할 수 있음
      1. 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기 기다리는 것
2. SJF (Shortest Job First) - 비선점
   1. 가장 작은 CPU burst 시간을 가진 프로세스에게 우선적으로 CPU를 할당함
   2. 비선점이므로 가장 먼저 도착한 p1이 일단 실행하고, 그 다음 burst time이 작은 p3 순으로 실행함
3. SRTF (Shortest Remaining Time First) - 선점형
   1. 먼저 온 프로세스가 CPU를 할당받고 있더라고 남은 처리 시간이 뒤에 온 프로세스의 처리 시간보다 길면 CPU를 빼앗김
4. RR (Round Robin) - 선점형 
   1. 프로세스에게 각각 동일한 CPU 시간 할당량 (time quantum)을 부여해서 이 시간 동안만 CPU를 이용하게 하여 선점형으로 동작함
   2. 만약 할당 시간동안 처리를 다 하지 못하면 CPU를 빼앗고 다른 프로세스에게 넘김
   3. 규정 시간량이 작으면 문맥 교환을 많이 하므로 평균 반환시간이 더 좋지 않음.
   4. 빼앗긴 프로세스는 준비 큐의 맨 뒤로 감
5. 우선순위 스케줄링  
   
   1. 선점형 : 새로 도착한 프로세스의 우선순위 > 현재 실행되는 프로세스의 우선순위 -> CPU 선점 
   2. 비선점형 : 준비완료 큐의 머리 부분에 새로운 프로세스를 넣음
   3. 운영체제 혹은 사용자에 의해 프로세스에 우선순위를 부여하고, CPU는 가장 높은 우선순위를 가진 프로세스에 할당됨 
      1. 문제점
         1. 높은 우선순위의 프로세스가 계속 들어올 경우, 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생함 (무한 봉쇄, 기아 상태)
         2. starvation 문제 해결 방안 - 노화 (againg)
            1. 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시켜주는 방법

1. 다단계 큐 스케줄링
   1. 여러 개의 준비 큐를 가지는 스케줄링 방법
   2. 각 큐는 절대적인 우선순위를 가짐
      1. 우선순위가 높은 큐에 존재하는 프로세스부터 실행, 해당 큐가 비어있어야 그 아래 큐 실행할 수 있음
      2. 작업이 한 큐에서 다른 큐로 옮겨지지 않음
      3. 큐 간의 절대적인 우선순위 때문에 starvation이 발생할 수 있음
2. 다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링
   1. 프로세스가 큐들 사이에 이동하는 것을 허용함
   2. 프로세스들을 CPU burst 성격에 따라 구분함
   3. 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동됨
   4.  I/O 중심의 프로세스와 대화형 프로세스들을 높은 우선순위의 큐에 넣음. (이들은 통상적으로 짧은 CPU 버스트가 특징이다.)
   5. 마찬가지로 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위 큐로 이동할 수 있다.
      1. 이 방법으로 startvation 을 예방한다.
3. HRN(Highest Response-ratio Next) 스케줄링
   1. 짧은 작업에 유리한 SJF의 단점을 개선한 기법- 비선점 
   2. 최소작업 우선 스케줄링의 약점인 긴 작업과 짧은 작업 간의 지나친 불평 등을 보완
   3. 우선순위 = (대기 시간 + 서비스 시간) / 서비스 시간
   4. 시스템 응답 시간 = 대기 시간 + 서비스 시간
   5. 장점
      1. 자원을 효율적으로 사용함
      2. 기아가 발생하지 않음
   6. 오버헤드 발생할 수 있음 (메모리, 프로세서 낭비)