_운영체제_ 11. CPU 스케줄링

11-1. CPU 스케줄링 개요

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

• 프로세스 우선순위
  프로세스마다 우선순위의 차이가 존재(입출력 작업 양에 비례)

- 프로세스의 실행 과정
 CPU 사용 -> 입출력장치 사용 -> CPU 사용 -> 입출력 장치 사용 -> ...

프로세스 종류별로 입출력 장치와 CPU를 이용하는 시간의 차이 존재
 -> 이에 따라 "입출력 집중 프로세스"와 "CPU 집중 프로세스"로 나뉘어짐

- 입출력 집중 프로세스 : 실행 상태 < 대기 상태(입출력 버스트 높음)
- CPU 집중 프로세스 : 실행 상태 > 대기 상태(CPU 버스트 높음)

입출력 집중 프로세스는 작업 완료 후 대기 상태(CPU 할당X)가 되므로 먼저 처리한 후에
다른 작업을 재개하는 것이 "효율적"
 -> 우선순위 부여

• 스케줄링 큐
  프로세스를 ==“줄 세워 기다리게 하는 것”==을 구현한 것
  우선순위가 높은 프로세스들은 새치기 가능

- 큐 종류
 준비 큐 : CPU를 이용하는 프로세스들의 줄
 대기 큐 : 입출력 장치 이용을 위해 대기 상태에 접어든 프로세스들의 줄
  -> 입출력장치 이용 후 다시 준비 상태 변경, 준비 큐로 이동

• 선점형, 비선점형 스케줄링
  스케줄링은 운영체제가 프로세스에게서 자원을 빼앗아 다른 자원에게 할당하느냐 하지 않느냐로
  선점, 비선점형으로 나뉘어짐

- 선점형 스케줄링
 특정 프로세스의 자원 독점 불가 -> 프로세스에 골고루 자원 배분 가능
 문맥 교환 과정에서 오버헤드 발생 확률 증가
- 비선점형 스케줄링
 특정 프로세스의 자원 독점 가능 -> 오버헤드 발생 확률 감소
 특정 상황에서 자원을 할당받아야 함에도 무조건 기다려야함

11-2. CPU 스케줄링 알고리즘

• 스케줄링 알고리즘의 종류

- 선입 선처리 스케줄링
 FCFS 스케줄링으로도 지칭(비선점형 스케줄링)
 준비 큐에 삽입된 순서대로 프로세스 처리
 사용시간이 적은 프로세스가 앞의 프로세스들 때문에 사용시간보다 많은 시간을 기다려야함.
  -> 호위 효과

- 최단 작업 우선 스케줄링
 SJF 스케줄링으로도 지칭(비선점형 스케줄링)
 준비 큐에 삽입된 프로세스 중 사용시간이 짧은 순서대로 처리
 호위 효과 방지

- 라운드 로빈 스케줄링
 FCFS 스케줄링 + 타임 슬라이스(각 프로세스의 CPU 사용 시간 지정)
 정해진 시간 만큼 돌아가며 이용하는 선점형 스케줄링
 시간 안에 완료하지 못할 시 큐 맨 뒤로 삽입 후 문맥교환
 타임 슬라이스의 크기를 효율적으로 지정하는 것이 중요!

- 최소 잔여 시간 우선 스케줄링
 SRT 스케줄링으로도 지칭(최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링)
 정해진 타임 슬라이스만큼 CPU 사용, 다음 프로세스를 남은 작업 시간이 적은 순서대로 처리

- 우선순위 스케줄링
 우선순위 부여 후, 순서대로 프로세스 처리
 단점 : 우선순위가 낮은 프로세스가 높은 프로세스들에게 계속 순위가 밀려날 수 있음(기아 현상)
  -> 에이징 기법 : 오랫동안 대기한 프로세스의 우선순위를 점차 높임(기아 현상 방지)

- 다단계 큐 스케줄링
 우선순위 스케줄링의 발전 형태, 우선순위 별로 준비 큐를 여러 개 사용
 프로세스 유형 별로 우선순위 구분 실행에 용이, 큐마다 타임 슬라이스, 스케줄링 방식 등 다양
 하게 지정 가능(유도리 증가)

- 다단계 피드백 큐 스케줄링
다단계 큐 스케줄링의 발전된 형태(프로세스들이 큐 사이를 이동 불가능한 문제 해결)
프로세스들이 큐 사이를 이동 가능하게 만들어 지정 시간동안 완료되지않은 프로세스를 다음 큐로
이동 -> CPU를 오래 사용하는 프로세스의 우선순위를 점차 낮춤(반대인 프로세스의 우선순위 높임)
 -> 가장 일반적인 CPU 스케줄링 알고리즘