스케줄링(Scheduling) 개념 및 이해

스케줄링(Scheduling)

스케줄링은 여러 프로세스가 번갈아가며 사용하는 자원을 어떤 시점에 어떤 프로세스에게 자원을 할당할 지 결정하는 것이다.

스케줄링 방법에 따라 프로세서(CPU)를 할당받을 프로세스를 결저하므로 스케줄링은 시스템의 성능에 직/간접적인 영향을 미친다.

좋은 스케줄링은 프로세서의 효율성을 높이고, 프로세스의 응답시간을 최소화하여 시스템의 작업 처리 능력을 향상시킨다.

즉, cpu가 쉬지않고 계속해서 돌 수 있도록 해준다.

스케줄링 알고리즘 종류

선점 스케줄링 :: 프로세스 하나가 장시간 동안 프로세서를 독점하는 것을 방지하기 위한 것이다.

장점 : 우선순위가 높은 프로세스가 긴급 처리되야할 때 유용하고 모든 프로세스에 프로세서를 할당해줄 수 있는 기회가 생긴다.

단점 : 잦은 프로세스 교환으로 인해(컨텍스트 스위칭) 오버헤드가 높다.

비선점 스케줄링 : 한 프로세스가 프로세서(CPU, 자원)을 선택했을 때 다른 프로세스가 해당 프로세서를 빼앗을 수 없도록 한 것이다.

장점 : 실행시간이 짧은 프로세스가 먼저 자원을 가질 수 있어 가장 짧은 평균 대기 시간을 기대 할 수 있다.

단점 : 실행시간이 긴 프로세스는 실행시간이 짧은 프로세스에 밀려 Starvation 상황이 올 수 있다.

스케줄링 목적

스케줄링을 하는 이유를 아래에서 찾아보자.

1. 자원 할당의 공정성 :: 모든 프로세스는 공평하게 다뤄져야 하고 어떤 프로세스도 실행이 무제한 연기(Starvation)가 되면 안된다.

2. 단위시간당 처리량 최대화 :: 프로세서(cpu)가 최대한 쉬지않고(유효시간 없이) 일을 하도록 하는게 스케줄러의 목적이다.

3. 적절한 반환시간 보장 :: 어떤 input이 일어나면 적절한 시간내에는 프로세스가 output을 낼 수 있도록 스케줄링 해야한다.

4. 예측 가능성 보장 :: 언제 어떻게 실행해도 프로세스는 거의 비슷한 시간에 비슷한 비용으로 처리 되어야 한다.

5. 오버헤드 최소화 :: 오버헤드가 발생(ex :: while(1){})하면 CPU 자원의 낭비가 심하므로 오버헤드를 줄여야 한다.

6. 자원 사용의 균형 유지 :: 최대한 프로세서 및 자원을 쉬지 않고 동작시키는게 목표이니 유휴 상태의 자원을 사용하려는 프로세스에 우선순위를 줄 수 있다.(ex : 프린터)

7. 실행 대기 방지 :: 실행을 무한하게 연기하지 않도록 해야한다. 즉, 우선순위를 적절히 주어 프로세스가 starvation 상태가 일어나지 않도록 해야한다.

이는 aging 방법으로 해결 할 수 있다.(대기중인 프로세스가 우선순위가 차츰차츰 높아지는 방식)

8. 우선순위 :: 모든 프로세스에 우선순위를 부여하여 스케줄링 알고리즘을 통해 우선순위가 높은 프로세스부터 먼저 실행하도록 한다.

스케줄링 단계

1단계 :: 작업 스케줄링

이 단계는 실제로 시스템 자원을 사용할 작업을 선택하는 단계이다.

디스크에 프로그램으로 있는 작업 중 프로세스화할 작업과 시스템으로 들어갈 작업을 결정하므로 승인 스케줄링이라고 한다.

이는 작업 스케줄링에 따라 작업을 프로세스들로 나누어 생성한다.

이는 수행 빈도가 적기 때문에 장기 스케줄링이라고도 부른다.

디스크에서 메모리로 작업(프로그램)을 가져와 PCB를 부착시켜 메모리를 적재하여 프로세스로 만든 후 Ready Queue에 넣는다.

2단계 :: 작업 승인과 프로세서 결정 스케줄링

이 단계는 프로세서(CPU)를 사용할 프로세스를 결정하는 작업 승인을 해주는 역할을 한다.

혹은 시스템의 오버헤드가 심하면 연기(보류)할 프로세스를 결정한다.

따라서 이 2단계는 1, 3단계의 완충 역할을 한다.

이는 수행빈도가 1단계, 3단계의 사이라 중기 스케줄링이라고도 부른다.

3단계 :: 프로세서 할당 스케줄링

3단계는 dispatcher가 Ready Queue에 있는 프로세스 중에서 우선순위에 따라 프로세스를 프로세서에 할당해주는 스케줄링이다.

이는 다음 프로세스 결정을 자주 해야하므로 단기 스케줄링이라고도 부른다.

장기 스케줄러에서 메모리에 적재시킨 프로세스 중 프로세서(CPU)를 할당하여 실행 상태가 되도록 결정하는 스케줄링을 한다. 이때 프로세스가 요청하는 자원의 할당을 만족해야 한다.

** Ready Queue**

스케줄링에는 Ready Queue라는 것을 이용하여 대기중인 프로세스를 프로세서에 할당하는데 이용한다.

Ready Queue에는 프로세스가 담긴다고 하는데 정확하게는 PCB가 큐에 담기는 것이다.

큐는 아래와 같이 연결 리스트로 구성되어있고 스케줄러에 필요한 큐 및 프린터, 디스크, 터미널 등등에 해당하는 큐들도 존재한다.

단기, 중기, 장기 스케줄러가 프로세스 상태 천이과정에서 어떻게 동작하는지 보자.

장기 스케줄러

장기 스케줄러는 프로세스의 생성 과정에서 프로세스의 준비 상태에 무엇을 추가할지 결정하고 메모리의 사용 가능 공간 및 자원을 확인한다.

중기 스케줄러

중기 스케줄러는 스왑 기능의 일부로 메모리에 부분적으로 프로세스를 적재하고 일시중지된 프로세서의 원인을 해결하면 다시 준비 상태로 만든다.

단기 스케줄러

단기 스케줄러는 미리 정한 스케줄링 알고리즘에 따라 실행할 프로세스를 선택한다.

프로세스 실행상태에서 대기 혹은 준비 상태로 변화시키는 역할을 한다.

마지막으로 작업이 성공적으로 종료되거나 운영체제가 트랩(S/W 인터럽트, ex : kill, 강제 종료)을 당하면 모든 자원은 해제된다.

큐잉 도표

큐잉 도표는 프로세스 스케줄링을 표현하는 방법중 하나이다.

디스크에서 프로그램이 프로세스가 되어 Ready Queue에 들어오면서 PCB가 생성되는데 이는 종료가 될 때까지(CPU에서 오른쪽화살표로 가는 방향이 종료이다.) PCB는 계속 갱신된다.

프로세스가 프로세서(CPU)에 할당되면 위의 그림중 하나가 일어나게 된다.

1. I/O 요청을 보내고 입출력 큐에 들어간다.

2. 프로세스가 새로운 프로세스를 fork하고 생성한 프로세스의 종료를 기다린다.

3. 프로세스의 CPU 점유 시간이 초과가 되면 Ready Queue에 들어간다. 

4. 인터럽트로 프로세서에서 빠진 프로세스는 다시 Ready Queue에 들어간다.