스케줄링의 개념
단일 처리 시스템을 사용하지 않는 이유중 한 가지는 바로 이 스케줄링과 관련이 있다.
단일 처리 시스템에서 실행 중인 프로세스가 입출력을 요청하면, 이 프로세스가 실행을 마칠 때 까지는 사용하던 자원을 대기해야 하므로 효율이 많이 떨어진다.
하지만 다중 처리 시스템에서는 여러 프로세스를 동시에 메모리에 올려놓고 실행 중인 프로세스가 입출력을 요청하면, 운영체제가 실행중인 프로세서를 회수하여 다른 프로세스에게 할당한다. 이처럼 다중 처리 시스템에서는 다음과 같은 장점을 얻을 수 있다.
- 프로세서 이용율을 높일 수 있다.
- 프로세서 처리율(주어진 시간에만 처리하는 작업량)이 증가한다.
다중 프로그래밍에서 프로세서를 할당할 프로세스를 선택할 때 어떤 전략이 필요한데 이때 필요한 개념이 스케줄링 이다.
스케줄링(scheduling) 은 여러 프로세스가 번갈아 사용하는 자원을 어떤 시점에 어떤 프로세스에 할당할지 결정하는 것이다.
※ 참고
위 스케줄링 정의에서 해당하는 자원이 프로세서인 경우를 프로세서 스케줄링이라고 하는데, 대부분 스케줄링이 프로세서 스케줄링을 의미한다.
좋은 스케줄링은 프로세스들에게 프로세서를 효율적으로 할당, 시스템의 작업 처리 능력을 향상시며 응답 시간을 최소화하는 것이 목적이다.
스케줄링이 불필요한 프로세스
- 인터럽트 처리, 오류 처리, 사용자의 시스템 호출 등의 사전 처리 프로세스 등
스케줄링이 필요한 프로세스
- 사용자 프로세스, 시스템 호출로 발생하는 시스템 프로세스 등
그리고 스케줄링 방법에 따라 프로세서를 할당받을 프로세스를 결정하므로 스케줄링이 시스템의 성능에 영향을 미친다.
스케줄링의 목적
앞서 스케줄링은 시스템의 성능에 영향을 미친다고 했는데, 구체적으로 다음 목적에서 스케줄링을 한다.
- 자원 할당의 공정성 : 모든 프로세스는 공평하게 다뤄져야 하고 어떤 프로세스도 실행이 무제한 연기(Starvation)가 되면 안된다.
- 단위시간당 처리량 최대화 : 단위시간당 유효 시간을 줄이가ㅗ 프로세서의 처리량을 최대화하여 가능한 많은 프로세스에 서비스를 제공해야 한다.
- 적절한 반환시간 보장 : 적절한 시간 안에 응답(프로세스 완료)을 해야 한다. 대화식 시스템에서는 사용자에게 늦어도 2~3초 이내에 응답해 주어야 한다.
- 예측 가능성 보장 : 작업(프로세스)을 시스템 부하와 상관없이 거의 같은 시간에 거의 같은 비용으로 실행할 수 있어야 한다.
- 오버헤드 최소화 : 일반적으로 오버헤드가 발생하면 자원이 낭비되므로 오버헤드를 줄여야 한다. 하지만 오버헤드가 시스템의 전반적인 성능을 크세 높일 수도 있다.
- 자원 사용의 균형 유지 : 시스템의 자원을 가능한 쉬지 않고 사용할 수 있도록 스케줄링을 해야 한다. 따라서 유휴 상태의 자원을 사용하려는 프로세스에 특별한 혜택을 줄 수 있다.
- 반환시간과 자원의 활용 간에 균형 유지 : 반환시간(turn around time) 을 빠르게 하는 방법은 중분한 자원을 확보하는 것이지만 한 프로세스가 너무 많은 자원을 차지하면 시스템의 자원 활용도가 떨어진다. 실시간 시스템은 빠른 응답이 필요하므로 자원 활용이 상대적으로 덜 중요하지만 다른 형태의 시스템에서는 효과적인 자원 활용이 더 중요하다.
- 실행 대기 방지 : 실행을 무한 연기하지 않도록 해야 한다. 실행의 무한 연기는 교착 상태만큼 나쁜 영향을 줄 때가 많다. 이런 무한 연기 문제는 자원을 오래 기다릴수록 높은 우선순위를 부여하여 언젠가는 자원을 확보할 수 있도록 하는 에이징(aging) 방법으로 해결할 수 있다.
- 우선 순위 : 우선순위를 부여한 후 스케줄링 방법을 이용하여 우선순위가 높은 프로세스를 먼저 실행하도록 한다. 비선점 자원이라면, 스케줄링 방법은 프로세스에 주요 자원을 넘겨주기보다는 우선순위에 따라 처리해야 한다.
- 서비스 사용 기회 확대 : 프로세스에 더 자주 서비스 사용 기회를 주어야 한다. 특히 페이지 부재율이 적은 프로세스에는 더 자주 서비스 사용 기회를 제공해야 한다.
- 서비스 수 감소 방지 : 서비스 수가 갑자기 감소해서는 안 된다. 시스템에 부하가 많이 걸릴 대 갑자기 서비스 수가 감소하면 안된다. 과부하를 방지하든지 프로세스들의 서비스를 줄여 과부하에 대처해야 한다. 이런 목적들은 서로 모순되는 면이 많은데, 이는 스케줄링 문제를 어렵게 만드는 원인 중 하나이다.
스케줄링의 기준 요소
스케줄링의 목적을 실현하려면 프로세스의 동작을 고려해야 한다. 그리고 특히 프로세스의 실행 시간이 중요한 요소이다.
프로세스는 시작 ~ 종료까지 실행과 입출력 대기를 순환 반복한다.
두 종류의 버스트(burst)
- 프로세서 버스트 : 프로세스가 프로세서를 차지하고 명령어를 실행하는 단계
- 입출력 버스트 : 프로세스가 CPU를 반환하고 입출력을 대기하는 단계
프로세스는 입출력 버스트 후 다음 프로세서 버스트를 위해 준비 큐(Ready Queue)로 이동한다.
그러므로 프로세스 실행은 위 그림과 같이 프로세서 버스트와 입출력 버스트의 순환 형태로 구성된다.
스케줄링 버스트 분포
스케줄링 버스트 분포는 적절한 프로세서 스케줄링 알고리즘을 선택하는 데 중요한 기준이 된다.
위의 버스트 분포 그래프를 보면, 짧은 프로세서 버스트 작업이 초반에 다수 이루어진다.
짧은 프로세서 버스트 작업이 끝난 이후부터는 긴 프로세서 버스트 작업이 매우 낮은 빈도수로 이루어진다.
이를 바탕으로 추측해보면, 입출력 중심 프로세서를 먼저 처리한 뒤, 그 이후에 프로세서 중심 프로세스들이 처리된다는 것을 알 수 있다.
그리고 프로세서 버스트 차이에 따라 프로세서 중심 프로세스와 입출력 중심 프로세스로 나눠진다.
프로세서 중심 프로세스(Processor-Bound Process)
프로세서 중심 프로세스(Processor-Bound Process)는 프로세서 버스트가 매우 길다.
이는 대부분의 계산 작업에 해당하고, 완료 시간은 보통 할당받은 프로세서 시간으로 결정한다.
즉, 프로세서를 1번 차지하면, 점유 시간이 매우 길다.
입출력 중심 프로세스(I/O Bound Process)
입출력 중심 프로세스(I/O Bound Process)는 프로세서 버스트가 짧다.
이런 짧은 프로세서 버스트는 입출력을 처리하고 다음 입출력을 요청하므로 입출력을 완료하려고 기다리느라 대부분의 시간을 보낸다.
즉, 프로세서를 1번 차지하면, 점유 시간이 짧다.
주로 입출력 요청 시간으로 프로세스 완료 시간을 결정하므로, 2가지 유형의 적절한 혼합은 스케줄링 알고리즘을 선택할 때 매우 중요한 기준 요소가 된다.
프로세서 속도 기술이 입출력 속도 기술보다 훨씬 더 빨리 발전하여 프로세서 버스트는 짧아지고 입출력 대기 는 비교적 일정해서 프로세스는 더 입출력 중심으로 바뀌고 있다.
프로세스는 실행 단계에 따라 프로세서 중심에서 입출력 중심 (또는 그 반대) 으로 진행할 수 있다. 이때 입출력 중심 프로세스를 실행한 후 프로세서 중심 프로세스를 선택하면 아주 짧은 지연이 발생하는데, 프로세서 중심 프로세스를 실행한 후 입출력 중심 프로세스를 선택하면 지연은 훨씬 길어진다.
그러므로 입출력 프로세서를 바쁘게 하여 성능을 높이려면 프로세서 중심 프로세스와 입출력 중심 프로세스를 적절히 혼합해서 사용해야 한다.
스케줄링의 단계
1 단계 작업 스케줄링 : 작업 선택
- 실제로 시스템 자원을 사용할 작업을 결정하는 작업 스케줄링이다. 수행 빈도가 적어 장기 스케줄링에 해당함.
- 디스크에 있는 작업 중 프로세스화할 작업과 시스템에 들어갈 작업을 결정하므로 승인 스케줄이라고도 함.
- 작업 스케줄링에 따라 작업을 프로세스들로 나눠 생성한다.
2 단계 작업 승인과 프로세서 결정 스케줄링 : 사용 권한 부여
- 프로세서를 사용할 권한을 부여할 프로세스를 결정하는 작업 승인과 프로세서 할당 스케줄링
- 시스템의 오버헤드에 따라 연기할 프로세스를 잠정적으로 결정한다.
- 2 단계는 1단계 작업 스케줄링과 3단계 프로세서 할당 스케줄링의 완충 역할
- 수행 빈도를 기준으로 하면 중기 스케줄링에 해당하며, 메모리 사용성도 높이고 작업의 효율성도 향상시키는 스와핑(swapping, 교체) 기능의 일부로 이해할 수 있음
3 단계 프로세서 할당 스케줄링 : 준비 상태의 프로세스에 프로세서 할당(디스패칭)
- 디스패처가 준비 상태에 있는 프로세스 중에서 프로세서를 할당할 프로세스를 결정
- 다음에 실행할 프로세스 결정은 자주 발생하므로 수행 빈도가 많아 단기 스케줄링에 해당
스케줄링 큐
스케줄링에는 다양한 큐가 존재한다.
준비 큐(Ready Queue)
- 프로세서를 할당받아 실행하려고 기다리는 프로세스들이 대기
- 좁은 의미에서 스케줄링은 준비 큐에서 프로세스를 하나 선택하는 것
입출력 장치 큐
- 입출력 장치를 사용하려는 프로세스들이 대기
- 각각의 큐들은 프로세스 제어 블록(PCB)을 연결 리스트로 연결하고 있는 형태이다.
- 큐에는 머리(head) 와 꼬리(tail) 가 있고, 각각 연결된 첫 번째 PCB와 마지막 PCB의 포인터 필드를 가리킨다.
- 입출력 장치 큐는 다양하게 추가할 수 있다.
- 테이프 드라이브나 시분할 단말기 같은 전용장치일 때 입출력 장치 큐는 프로세스를 하나만 가질 수 있음.
- 디스크와 같은 공유 장치는 입출력 장치 큐에 여러 프로세스가 대기할 수 있음.
스케줄링과 스케줄러
OS는 다양한 스케줄러를 이용하여 지원한다. 이때 스케줄러가 스케줄링을 표현하는 대표적인 방법으로 큐잉 도표가 있다.
큐잉 도표(queueing diagram)
큐잉 도표는 프로세스 스케줄링을 표현하는 방법이다.
- 작업이 시스템에 들어오면 작업의 프로세스 제어 블록(PCB)을 생성하는데, 이는 작업을 종료할 때까지 갱신된다.
- 따라서 실행 준비가 된 프로세스가 준비 큐에 들어가고 프로세서를 할당받을 때까지 대기한다.
프로세스에 프로세서가 할당되면 다음 사항 중 하나가 일어난다.
- 프로세스가 입출력 요청을 보내고 입출력 큐로 이동
- 프로세스가 새로운 프로세스를 생성(fork) 하고 생성한 프로세스의 종료를 기다림.
- 프로세스가 시간 할당량을 초과(시간 종료)하면 준비 큐로 이동
- 인터럽트로 프로세서에서 제거된 프로세스는 다시 준비 큐로 이동
1, 2 번 같은 경우 프로세스는 대기 상태에서 준비 상태로 전환되고 다시 준비 큐에 들어간다. 프로세스는 종료할 때까지, 즉 시스템을 떠날 때까지 이 순환을 반복한다.
스케줄러의 종류와 역할
스케줄링으로 프로세스를 선택할 때는 스케줄러를 이용한다. OS는 다양한 스케줄러를 지원하는데, 주로 장기 스케줄러와 단기 스케줄러를 이용한다.
장기 스케줄러
- 장기 스케줄러는 작업 스케줄러하고도 하며, 스케줄링에 따라 디스크에서 메모리로 작업을 가져와 처리할 순서를 결정한다.
- 작업 스케줄링에 필요한 정보로 제출 시간, 작업 이름, 작업 길이(용량) 등이 있다.
- 선택한 작업에 PCB를 부착시켜 메모리에 적재한 것이 프로세스이다.
단기 스케줄러
- 메모리에 적재된 프로세스 중 프로세서를 할당하여 실행 상태가 되도록 결정하는 프로세스 스케줄링
- 이때는 프로세스가 실행하는데 필요한 자원의 요청을 만족해야 함.
장기 스케줄러와 단기 스케줄러의 차이
- 장기 스케줄러와 단기 스케줄러의 가장 큰 차이는 실행 빈도이다
- 단기 스케줄러는 실행할 프로세스를 수시로 선택하며 매우 빨라야 함.
- ex. 프로세서에서 실행 시간은 100만 분의 수초 정도이므로 최소한 100만 분의 10 초 단위로 단기 스케줄러를 실행한다고 가정.
- 단기 스케줄러가 프로세스를 선택하는데 100만 분의 1초가 걸린다면, 전체 실행 시간의 9%[ ≒ 1/(10+1)] 정도는 프로세서 스케줄링에 소비하므로 단기 스케줄러는 매우 빨라야 함.
- 장기 스케줄러는 시스템에 새로운 작업이 분 단위로 들어오므로 단기 스케줄러에 비해 상대적으로 드물게 수행
- 장기 스케줄러는 다중 프로그래밍의 정도(메모리에 있는 프로세스 수, degree of multiprogramming) 를 결정
- 작업이 시스템에 들어오는 정도가 일정하다면 작업의 도착률과 작업을 마치고 나가는 정도가 같다.
- 그러면 장기 스케줄러는 작업이 시스템을 나갈 때만 실행하여 실행 간격이 상대적으로 길어지므로 실행 시간이 좀 더 길어도 영향을 많이 받지 않는다.
디스패처
- 단기 스케줄러는 디스패처를 포함할 수 있음.
- 디스패터는 단기 스케줄러가 선택한 프로세스에 실질적으로 프로세서를 할당하는 역할을 하는 모듈
- 프로세스의 레지스터를 적재하고(문맥 교환), 사용자 모드로 전환하고, 다시 시작할 때 사용자 프로세스가 올바른 위치를 찾을 수 있도록 해줌.
- 따라서 디스패처 처리 속도는 빠를 수록 좋다.
중기 스케줄러
어떤 시스템에서는 장기 스케줄러가 없거나 그 역할이 매우 작다. 예를 들어 시분할 시스템은 장기 스케줄러가 없고 새로운 프로세스를 메모리에 넣기만 한다. 특히 가상 메모리 체제나 시분할 방법을 사용하는 시스템은 중기 스케줄러를 추가 사용한다.
- 중기 스케줄러는 프로세스들이 프로세서를 서로 차지하려고 할 때 프로세스를 별도의 기억 장소로 빼낼 수 있어 다중 프로그래밍의 정도(메모리에 있는 프로세스 수) 를 줄일 수 있다.
- 스왑(스왑 인, 스왑 아웃)
- 시간이 흐른 후 빼낸 프로세스는 다시 메모리에 들어가 실행을 중단했던 곳부터 다시 실행시키는 방법
- 스왑은 작업의 혼합을 개선하거나 프로세스가 가지고 있던 메모리를 사용할 수 있게 하는데 필요
프로세스 상태 변화와 스케줄러의 역할
- 장기 스케줄러
- 프로세스의 생성 과정에서 프로세스의 준비 상태에 무엇을 추가할지 결정하며, 메모리의 사용 가능 공간과 자원을 확인
- 중기 스케줄러
- 스왑 기능의 일부로 메모리에 부분적으로 프로세스를 적재하고, 일시중지된 프로세스의 원인을 해결하면 다시 준비 상태로 만듦.
- 단기 스케줄러
- 미리 정한 스케줄링 알고리즘에 따라 실행할 프로세스를 선택
- 프로세스의 실행 상태에서는 대기 또는 대기 상태에서 준비 상태로 변화하는 것은 각각 단기 스케줄러가 처리
- 단-장기 스케줄러
- 실행에서 종료 상태로 변화하는 것은 장기, 단기 스케줄러가 처리
선점 스케줄링과 비선점 스케줄링
스케줄링 알고리즘을 이해하기 위한 개념이며 이는 "실행 중인 작업이나 프로세스를 실행 중 중단할 것인가?" 하는 관점을 바탕으로 스케줄링을 구분한 것이다.
선점 스케줄링
- 현재 실행 중인 프로세스를 인터럽트할 수 있거나 준비 상태로 이동할 수 있다
- 프로세스 하나가 장시간 동안 프로세서를 독점하는 것을 방지하기 때문에 모든 프로세스에 프로세서를 서비스할 기회를 늘릴 수 있다. 따라서 우선 순위가 높은 프로세스들이 긴급 처리를 요청할 때 유용하다.
- 예를 들어, 실시간 시스템에서 인터럽트를 받아들이지 않으면 결과를 예측할 수 없다.
- 대화식 시분할 시스템이나 실시간 시스템에서 빠른 응답시간을 유지하는데 선점 스케줄링은 필수이다.
- 하지만 선점 스케줄링은 오버헤드가 커질 수 있어 이를 효과적으로 이용하려면 메모리에 프로세스가 많이 적재되어 있어야 한다.
- 즉, 프로세서를 사용 가능할 때마다 실행할 수 있는 프로세스들이 준비 상태에 있어야 효과적이다.
- 따라서 우선 순위라는 개념을 반드시 고려해야 하면, 우선 순위는 의미 있게 부여하지 않으면 효과가 없다.
비선점 스케줄링
- 한 프로세스가 자원(예: 프로세서) 을 선택했을 때 다른 프로세스가 해당 자원을 빼앗을 수 없다
- 실행 시간이 짧은 프로세스(작업) 가 실행 시간이 긴 프로세스(작업) 를 기다리는 대신 모든 프로세서를 공정하게 관리한다.
- 우선 순위가 높은 프로세스를 중간에 입력해도 대기 중인 프로세스는 영향을 받지 않으므로 응답시간을 예측하기도 쉽다.
스케줄링 알고리즘 선택 기준
스케줄링 알고리즘을 비교할 때 참조할 수 있는 기준들이며 스케줄링 알고리즘을 선택할 때는 프로세서 사용률과 처리율을 최대화하고, 반환 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직하다.
- 프로세서 사용률 : 프로세서를 항상 실행 상태로 유지하여 유휴 상태가 되지 않도록 한다. 따라서 입출력 중심 작업보다는 프로세서 중심 작업을 실행한다.
- 처리율 : 단위 시간당 완료하는 작업 수가 많도록 짧은 작업을 우선 처리하거나 인터럽트 없이 작업을 실행한다.
- 반환 시간 : 작업이 메모리에 들어가기까기 걸린 시간, 준비 큐에 머무는 시간, 실행 시간, 입출력 시간 등 작업을 완료하는 데 소요되는 시간을 최소화하도록 일괄 처리 작업을 우선 처리 한다.
- 대기 시간 : 작업의 실행 시간이나 입출력 시간은 영향을 줄 수 없으므로 준비 큐에서 기다리는 시간을 최소화하도록 사용자 수를 제한한다.
- 반응 시간 : 작업을 요청한 시간부터 반응을 시작하는 시간(첫 번째 응답)까지 간격으로, 대화형 시스템에 중요한 사항이다. 따라서 대화식 작업을 우선 처리하고 일괄 처리 작업은 대화식 작업을 요청하지 않을 때 처리한다.
반환시간, 대기 시간, 응답 시간의 관계
예를 들어, 프로세스 3개가 동시에 도착하여 프로세스 P1, P2, P3 순으로 실행했다고 가정하면 각 프로세스의 반환시간과 대기 시간은 아래와 같다.
참고
- 운영체제:그림으로 배우는 구조와 원리 - 한빛 아카데미
- https://wonit.tistory.com/97
- https://arainablog.tistory.com/289
- https://velog.io/@sawol/%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81