Every CS - 운영체제(OS) 03 - CPU 스케줄링

CPU 스케줄링

개념 정리

1. CPU 스케줄링 : 다양한 프로세스와 스레드에 CPU의 사용을 배분하는 방법
2. CPU 스케줄링 알고리즘 : CPU 스케줄링의 절차
3. CPU 스케줄러 : CPU 스케줄링 알고리즘을 결정하고 수행하는 운영체제의 일부분

1. CPU 스케줄링

우선순위

모든 프로세스는 CPU의 자원을 필요로 하기 때문에 운영체제는 공정하고 합리적인 방법으로 CPU의 자원을 프로세스에 할당해야 한다.
따라서 운영체제는 프로세스별 우선순위를 판단하여 PCB에 명시하고, 우선순위가 높은 프로세스에 CPU의 자원을 더 빨리, 더 많이 할당한다.

윈도우의 Process Explorer에서 소프트웨어의 Prioriy 항목을 확인할 수 있다.

우선순위 할당 방법

1. CPU 활용률 : 전체 CPU의 가동 시간 중 작업을 처리하는 시간의 비율.
    운영체제는 가급적 CPU활용률을 높게 유지할 수 있도록 우선순위를 할당한다.
    기본적으로 입출력작업이 많은 프로세스의 우선순위를 높게 유지한다.
2. CPU 버스트 : 프로세스가 CPU를 이용하는 작업
3. 입출력 버스트 : 프로세스가 입출력장치를 기다리는 작업
4. 예시) 프로세스에 따른 CPU 할당
    입출력 집중 프로세스 : 비디오 재생, 디스크 백업 등 입출력작업이 많은 프로세스
    CPU 집중 프로세스 : 복잡한 수학 연산, 그래픽 처리 작업 등 CPU 작업이 많은 프로세스
    입출력 집중 프로세스는 대기 상태에 많이 머무르고, CPU 집중 프로세스는 실행 상태에 많이 머무른다. 
    따라서, 이 두 프로세스가 동시에 자원을 요구했다면, 입출력 집중 프로세스를 가능한 빨리 실행시켜 끊임없이 입출력장치를 작동시킨 다음 CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 합리적이다.

스케줄링 큐

""자원을 사용하고 싶다면 기다릴 것""

자원을 할당받고 싶은 프로세스들을 큐의 형태인 스케줄링 큐를 통해 구현한다.

1. 준비 큐 : CPU를 이용하고 싶은 프로세스의 PCB가 서는 줄
2. 대기 큐 : 대기 상태에 접어든 프로세스의 PCB가 서는 줄

스케줄링 큐의 운용 과정

입출력 작업의 경우 대기 큐에서 CPU 차례를 기다린다.
운영체제는 큐에 삽입된 순서대로, 우선순위가 높은 프로세스부터 실행한다.
실행되는 프로세스가 할당받은 시간을 모두 소모할 셩우 준비 큐로 이동한다.
실행 도중 입출력 작업 등 대기 상태로 접어들어야 하는 경우 대기 큐로 이동한다.
같은 입출력 장치를 요구한 프로세스는 같은 대기 큐에서 기다린다.
완료인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾아 준비 상태로 변경한 뒤 큐에서 제거 한다.
해당 PCB는 준비 큐로 이동한다.

선점형 스케줄링과 비선점형 스케줄링

선점형 스케줄링 : 현재 어떤 프로세스가 CPU를 할당받아 사용하고 있더라도 운영체제가 프로세스로부터 CPU 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식
비선점형 스케줄링 : 어떤 프로세스가 CPU를 사용하고 있을 때 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지는 다른 프로세스가 끼어들 수 없는 스케줄링 방식

2. CPU 스케줄링 알고리즘

1. 선입 선처리 스케줄링

준비 큐에 삽입된 순서대로 CPU를 할당하는 스케줄링 방식
프로세스들이 기다리는 시간이 매우 길어질 수 있는 부작용이 발생할 수 있다.
호위효과(convoy effect) : 나중에 삽입된 프로세스의 실행이 지연되는 문제가 발생할 수 있다.

2. 최단 작업 우선 스케줄링

준비 큐에 삽입된 프로세스 중 CPU를 이용하는 시간의 길이가 가장 짧은 프로세스부터 먼저 실행하는 스케줄링 방식

3. 라운드 로빈 스케줄링

선입 선처리 스케줄링 + 타임 슬라이스
타임 슬라이스 : 프로세스가 CPU를 사용하도록 정해진 시간
프로세스가 정해진 시간을 모두 사용하고도 완료되지 않으면 다시 큐의 맨 뒤에 삽입된다.

4. 최소 잔여 시간 우선 스케줄링

최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
프로세스로 하여금 정해진 타임 슬라이스만큼 CPU를 이용하되, 남아 있는 작업시간이 가장 적은 프로세스를 다음으로 CPU를 이용할 프로세스로 선택한다.

5. 우선순위 스케줄링

프로세스에 우선순위를 부여하고, 가장 높은 우선순위의 프로세스부터 실행하는 스케줄링 방식
우선순위가 낮은 프로세스는 일찍 준비 큐에 삽입되었더라도 실행이 계속 연기되는 아사현상(starvation)이 발생할 수 있다.
이를 대기한 프로세스의 시간이 길어질 수록 우선순위를 높이는 방식의 에이징(aging)기법으로 해결한다.

6. 다단계 큐 스케줄링

우선순위별로 여러 개의 준비 큐를 사용하는 스케줄링 방식
우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고, 우선순위가 가장 높은 큐가 비어있게 되면, 그 다음으로 우선순위가 높은 큐에 있는 프로세스를 처리한다.
단점 : 프로세스들이 큐 사이를 이동할 수 없기 때문에 우선순위가 낮은 프로세스의 작업이 꼐속 연기되는 아사 현상이 또한 발생할 수 있다.

7. 다단계 피드백 큐 스케줄링

다단계 큐 스케줄링 + 프로세스의 큐 이동
우선 모든 프로세스는 타임 슬라이스 동안 실행된다.
우선순위가 높은 큐의 프로세스가 실행된 후, 실행이 끝나지 않으면, 그 프로세스는 그 다음 우선순위 큐에 삽입되어 실행된다.
따라서, CPU를 오래 사용하는 CPU 집중 프로세스의 우선순위는 점점 낮아지고, 입출력 집중 프로세스는 우선순위가 높은 큐에서 실행이 끝나게 된다.
여기에 아사현상을 막기 위한 에이징 기법까지 적용할 수 있다.