2. 스케줄링
1. CPU 스케줄링
어떤 스레드가 어떠한 우선순위로 CPU를 얼마나 사용할 것인지를 결정하고 수행하는 것을 CPU 스케줄링이라고 한다. CPU 스케줄링의 목표는 시간 당 처리되는 프로세스의 수를 높이고 CPU의 효율을 높여주기 위한 것이다. CPU 스케줄링을 통해 작업 시간과 응답 시간을 줄여 자원들의 유휴상태로 놓이지 않게 해 활용을 최대화하고 특정 프로세스 실행이 무한정으로 기다리지 않게 한다.
2. CPU 스케줄링의 단계
1. 장기: 어느 작업(Job)을 등록하여 시스템 자원을 이용할 수 있게 할 것 인지를 결정한다. 선택된 작업은 프로세스로 수행
2. 중기: 어느 프로세스에게 메모리를 할당할 것인지를 결정한다. 시스템의 상태에 따라서 조정하게 된다.
3. 단기: 준비 상태의 프로세스들 중 어떤 것에 CPU를 할당할 것인지를 결정한다. (dispatcher가 수행)
장기 스케쥴러에서 준비큐에 대기하고 있는 태스크들이 우선순위에 따라서 준비큐에 들어가고 준비 큐에 있는 것들이 단기적으로 우선 순위에 맞춰서 수행이 된다. 그리고 수행 중에 우선순위가 더 높은 것이 들어오거나 퀀텀타임이 끝나게 되면 대기 모드로 들어가며 그 내에서 스케쥴이 결정되어서 다시 준비큐에 들어와서 수행을 준비한다.
3. 선점형 스케줄링
실행중인 프로세스가 강제적으로 실행권을 빼앗기는 방식을 의미하며, 높은 우선순위 프로세스들이 들어오는 경우 오버헤드를 초래할 수 있다. 선점 알고리즘을 사용하는 경우에는 CPU의 사용을 중단하고 다른 프로세스에게 인터럽트에 의해 사용권을 넘겨주기 때문에 지금까지 수행한 모든 내용을 보관해 둔 후, 새로 시작하는 프로세스에 대한 내용을 새로 적재해 주어야 하는데 이를 문맥교환(Context Switching)이라 한다.
라운드 로빈(Round Robin) : 들어오는 순서대로 CPU 시간을 할당 받는다. 각 프로세스는 같은 크기의 CPU 시간을 할당 받게 된다. 시분할 방식에 효과적, 할당시간의 크기가 중요하다. 할당시간이 크면 FCFS와 같게 되고 작으면 문맥교환이 자주 발생하게 된다.
SRT(Short Remaining Time): 남은 수행 시간이 가장 짧은 것을 먼저 수행하는 방식이다. 남은 처리 시간이 더 짧다고 판단되면+프로세스가 준비큐에 생기면 언제라도 실행중인 프로세스가 선정된다. 긴 작업은 SJF보다 대기 시간이 길다.
다단계 큐(Multilevel Queue): 작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 기법이다. 준비상태의 큐를 작업단위 별로 여러 종류로 분할하는데, 다른 큐로의 작업이동이 불가하다. 각 큐는 자신만의 독자적인 스케쥴링을 가진다.(각 큐마다 시간 할당량이 달라진다) 상위단계 작업에 의해 하위 단계작업이 선점된다. 하위 단계 큐일수록 할당시간은 커지게 되며, 처음 발생하는 프로세스는 최상위단계에 위치한다. 만일 할당시간 내에 작업을 끝내지 못하면 그 다음 레벨의 큐에서 대기한다.
4. 비선점형 스케줄링
CPU를 선점한 프로세스가 자발적으로 실행권을 내려놓는 방식을 의미
우선 순위(Priority) 스케쥴링: 프로세스에게 우선순위를 부여하여 우선순위가 높은 순서대로 처리한다. 각 프로세스에게 우선순위가 주어지며, CPU는 가장 우선순위가 높은 프로세스에게 CPU를 할당하며 우선순위가 동일할 경우 선입 선처리(FCFS)로 처리 된다.
- 정적(static) 우선순위: 주변 환경 변화에 적응하지 못하여 실행중 우선순위를 바꾸지 않음, 구현이 쉽고 오버헤드가 적다.
- 동적(dynamic) 우선순위: 상황 변화에 적응하여 우선순위를 변경되며 구현이 복잡하고 오버헤드 많다. 2) 시스템의 응답속도를 증가시켜 효율적이다.
우선순위의 등급은 내부적 요인과 외부적 요인으로 구분되며, 내부적 우선순위는 기계내부의 성능에 영향을 미치는 작업처리의 제한 시간, 주기억 장소에 대한 요구량, 사용되는 파일의 수, 평균 CPU 버스트에 대한 평균 I/O 버스트의 비율을 고려하여 결정 된다. 외부적 우선순위는 기계외적 요인으로 결정된다. 우선순위가 높은 작업이 계속적으로 들어오게 될 때는 우선순위가 낮은 작업은 무한정 기다리게 될 수 있다.
FIFO/FCFS 스케쥴링 : FIFO(First Input First Out) 프로세스가 대기큐에 도착하는 순서에 따라 CPU를 할당하며, 프로세스가 CPU를 차지하고 난 후에는 그 프로세스가 CPU를 반환할 때까지 다른 프로세스가 선점할 수 없게 된다. 일괄처리 시스템에서 주로 사용, 작업 완료 시간을 예측하기 용이하며, 짧은 작업이 긴 작업을 기다리게 된다. 중요하지 않은 작업이 중요한 작업을 기다리게 하여 불합리하다. 빠른 응답을 요구하는 대화식 시스템에서는 부적절하며, 단독으로 사용되는 경우가 없으며 실제의 적용은 다른 스케쥴링 알고리즘에 보조적으로 사용된다.
HRRN(Highest Response Ratio Next) 스케쥴링: 대기중인 프로세스 중 현재 응답률이 가장 높은 것을 선택한다. 긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법이다. 짧은 작업이나 대기시간이 긴 작업은 우선순위가 높아진다.
SJF(Shortest Job First) 스케쥴링 : 준비 큐 내의 작업 중 수행시간이 가장 짧은 것을 먼저 수행한다. FCFS보다 평균 대기 시간(average waiting time)을 감소하고 긴 작업은 무한연기 가능성이 있다. 짧은 작업에 유리하다. 각 프로세스에서 CPU 버스트 길이를 비교하여 CPU가 이용 가능해지면 가장 작은 CPU 버스트를 가진 프로세스를 할당한다.
기한부(Deadline) 스케쥴링: 작업을 명시된 시간이나 기한내에 완료되도록 계획되며 작업시간이나 상황 등 정보를 미리 예측하기가 곤란하다.
문맥교환: CPU의 사용을 중단하고 다른 프로세스에게 인터럽트에 의해 사용권을 넘겨주기 때문에 지금까지 수행한 모든 내용을 보관해 둔 후, 새로 시작하는 프로세스에 대한 내용을 새로 적재해주는 것. 한 프로세스에서 다른 프로세스로 CPU가 새롭게 배당되는 교환과정을 말한다. 추후 프로세스 재실행을 위해 손상되지 않게 저장하여야 한다.
문맥교환(Context Switching)의 과정 1) 현재 실행 중인 프로세스 P0가 문맥교환이 요구된다. 2) 사용자 모드에서 운영체제 모드로 제거가 넘어가서 나중에 재개할 수 있도록 P0의 현재 상태를 PCB0에 저장한다. 3) 프로세스 P1이 실행될 수 있도록 PCB1에서 상태값을 reload를 하고 P1을 수행한다. 4) 다시 프로세스 P0이 실행될 수 있도록 PCB1의 하드웨어 상태와 특징들을 CPU에 재 저장하고 난 후 프로세스 P0를 실행시킨다.
문맥교환시 오버헤드가 생성되는데, 이는 적은 자료들을 주기억 장소로 옮기거나, 스레드의 이용으로 막을 수 있다.
Reference
IT 기술 노트
정보보안기사 > 필기 > 시스템 보안 > 운영체제 구조
운영체제 이론중에서 CPU스케줄링 기법
[운영체제]FIFO/FCFS (피포/first come first served)정의와 문제 & Convey Effect
https://jhnyang.tistory.com/34