4. CPU 스케줄링

스케줄링의 목적 : 모든 프로세스가 공평하고 안정적으로 작업하도록 하는 것

• 공평성 : 모든 프로세스가 자원을 공평하게 받음
• 효율성 : 자원이 유휴시간없이 스케줄링되고, 유휴 자원을 사용하려는 프로세스에게 우선권을 줌
• 안정성 : 우선순위를 통해 중요 프로세스가 먼저 작동하도록 배정(ex. 운영체제 프로세스) → 자원을 점유, 파괴하려는 프로세스로부터 보호
• 확장성 : 프로세스 / 자원이 증가해도 안정적으로 작동
• 반응시간보장 : 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 함
• 무한연기방지 : 특정 프로세스의 작업이 무기한 연기되면 안됨(starvation)

 

스케줄링의 단계 : 현대의 CPU 스케줄러는 대부분 저 수준 ~ 중간 수준 스케줄링으로 구성됨

• 고수준 스케줄링 : 전체 시스템의 부하를 고려하여 작업의 실행여부를 결정함. 전체 프로세스의 수 == 멀티프로그래밍 정도 결정
• 중간 수준 스케줄링 : 전체 시스템의 활성화된 프로세스로 인해 과부화가 걸린 경우 일부를 보류 상태로 보냄.
• 저수준 스케줄링 : 어떤 프로세스를 CPU에 할당할 지 결정함. 준비 → 실행 → 대기 → 준비 등과 같은 작업을 함. 

 

비선점형 스케줄링 : CPU를 할당받아 프로세스가 실행중이면 다른 프로세스가 빼앗을 수 없는 방식. 컨텍스트스위칭이 적게 일어나지만 CPU 사용 시간이 짧은 프로세스들이 오래 기다리게되어 전체 성능이 저하됨.

• FCFS(First Come First Served) : 들어온 순서대로 실행. 공평하지만 긴 프로세스가 들어오면 다른 프로세스들이 기다려 전체 성능 저하를 일으키는 콘보이 효과(컨베이어 벨트)가 발생하고 작업중인 프로세스가 입출력 작업을 요청하면 CPU가 놀게 됨.
• SJF(Shortest Job First) - 우선순위 스케줄링(작업시간 빠른 순) : 빠르게 끝나는 작업이 먼저 실행. 프로세스의 종료시간 혹은 입출력이 발생해도 응답시간을 알 수 없고, starvation이 발생함
• HRN(Highest Response Ratio Next) - 우선순위 스케줄링(계산식에 따른)  : SJF에서 starvation을 개선함(우선순위 = (CPU 사용시간 + 대기 시간) / CPU 사용시간) 그럼에도 짧은 프로세스가 우선순위가 높아 공평성이 위배 됨

 

선점형 스케줄링 : CPU를 할당받아 프로세스가 실행중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 방식. 빠른 응답을 요구하는 시분할 시스템에 적합하고, 컨텍스트스위칭이 자주 일어나지만 대부분의 저수준 스케줄러에 사용됨. 

• RR(Round Robin) : 할당받은 타임슬라이스만큼 작업을 하다가 완료하지 못하면 준비 큐의 맨 뒤로 들어감. 문맥교환이 더 일어나기 때문에 타임슬라이스 크기를 적절히 선택해야 함.
• SRT(Shortest Remaining Time) - 우선순위 스케줄링(남은 작업시간 적은 순)  : SJF + RR 방식. 기본적으로 RR로 사용하지만 CPU를 할당받을 프로세스를 선택할 때 남은 작업시간이 가장 적은 프로세스를 선택. 프로세스들의 남은 시간을 주기적으로 확인해야하고, SJF에 비해 컨텍스트스위칭도 발생되며, 프로세스 종료시간 확인도 어렵고, starvation이 발생됨
• 다단계 큐 : 우선순위마다 준비 큐 형성. 항상 가장 높은 우선순위 큐의 프로세스에 CPU를 할당 (우선순위가 낮은 큐에서 작업 실행 중이더라도 상위 단계의 큐에 프로세스가 도착하면 CPU를 빼앗음. 각 큐는 라운드 로빈이나 FCFS 등 독자적 스케줄링 사용 가능. starvation 발생
• 다단계 피드백 큐 : 다단계 큐와 동일 하지만, CPU를 사용한 프로세스는 원래의 큐가 아닌 우선순위가 하나 낮은 큐의 맨뒤로 들어감. 또한 우선순위가 낮은 큐 일수록 타임 슬라이스가 커져서 어렵게 CPU를 얻은만큼 좀 더 오래 사용할 수 있게 함. 가장 우선순위가 낮은 큐의 경우 무한대의 타임 슬라이스를 얻게 됨. 이러한 이유가 유닉스 운영체제에서 타임슬라이스를 유동적으로 사용할 수 있게한 이유임

 

준비 상태의 다중 큐 : 매번 우선순위가 높은 PCB를 찾아야 하는 문제 개선 → 스케줄링 알고리즘에 따라 여러개의 우선순위 준비 큐를 만듦

대기 상태의 다중 큐 : 인터럽트가 발생했을 때, 어떤 프로세스였는 지 찾아야 하는 문제 개선 → 같은 입출력끼리 묶음(HDD, CD-ROM, LAN 등) 준비에서 찾아서 실행상태로 옮기는건 1개씩 해야하지만 대기 → 준비로 옮기는건 동시에 처리된 것들을 한번에 보내도 되기 때문에 인터럽트 벡터라는 자료구조를 이용하여 모두 준비로 옮김 

 

 

스케줄링 알고리즘의 선택기준 : 높은 CPU 사용률, 높은 처리량, 적은 대기시간, 적은 응답시간, 적은 반환시간 (앞 2개는 계산이 어려움)을 통해 평균 대기 시간을 계산 (모든 프로세스의 대기 시간의 합 / 프로세스의 수) 

• 대기 시간 : 생성되고 대기 → 실행 전까지 시간 
• 응답 시간 : 생성되고 첫 번째 출력까지의 시간
• 실행 시간 : 실행 → 종료까지의 시간
• 반환 시간 : 대기 시간 + 실행 시간