“운영체제 : 아주 쉬운 세가지 이야기”를 읽으면서 핵심 내용을 정리하였습니다.
이화여대 반효경 교수님의 운영체제 강의를 듣고 복습 차원에서 책 한권을 완독해보고자 합니다.
잘못된 정보가 있다면 댓글 남겨주시면 감사하겠습니다!
스케줄링 정책
지금까지는 CPU 가상화를 구현하는 저수준의 기법인 “제한적 직접 실행”에 대해 알아 보았다. 제한적 직접실행을 통해 프로세스간 전환이 되는 과정(문맥 교환)을 이해하고 어떻게 운영체제의 주도하에 시스템(물리 장치들)을 관리 할 수 있는지 알 수 있었다.
그렇다면 운영체제는 어떤 원칙을 통해 프로세스를 전환할까?
•
A 프로세스 실행중 타이머 인터럽트가 발생 했다. 수많은 프로세스중 어떤 프로세스로 전환할까?
운영체제는 특정한 원칙을 가지고 있고 이를 “스케쥴링 정책” 이라고 한다. 아래의 질문을 통해 어떻게 정책들이 발전해 왔는지 알아보고자 한다.
•
핵심 가정은 무엇일까?
•
어떤 평가 기준으로 정책을 평가할 수 있을까?
핵심 가정
아래의 가정들은 비현실적이긴 하지만 차차 가정을 줄여 나가면서 최종적으로 제대로 동작하는 스케쥴링 정책을 만들 수 있다.
1.
모든 작업은 같은 시간동안 실행된다.
2.
모든 작업은 동시에 도착한다.
3.
각 작업은 시작되면 완료될 때 까지 실행된다.
4.
모든 작업은 CPU만 사용한다.(입출력 등등 안함)
5.
각 작업의 실행 시간은 사전에 알려져있다.
평가 항목
•
성능 측면
◦
반환 시간 (turnaround time)
▪
작업이 완료된 시간 - 작업이 도착한 시간
▪
작업은 동시에 도착한다고 가정하였으므로 반환 시간은 작업이 완료된 시간임.
◦
응답시간
▪
작업이 도착할 때부터 처음 스케줄 될 때까지의 시간
▪
시분할 컴퓨터의 등장으로 사용자가 터미널을 통해 시스템과 상호작용을 하기 시작하면서 요구됨
▪
상호작용이 중요한 프로그램일 경우 짧을 수록 좋다
•
공정성 측면
◦
기아 현상이 발생되지 않는지?
◦
프로세스들이 공정하게 CPU를 차지할 수 있는지?
→ 성능과 공정성은 trade-off 관계에 있음
여러 스케쥴링 정책들
선입 선출 (FIFO)
•
특징
◦
도착한 순서대로 처리함
◦
도착시간이 같다고 가정하기 때문에 반환 시간은 프로세스들의 완료 시간을 모두 더해 평균 낼 수 있음
•
장점
◦
구현이 매우 단순하다.
•
단점
◦
실행 시간이 모두 같다는 가정을 완화 하면 convoy effect가 발생할 수 있음
◦
반환시간이 길어질 수 있음
▪
안좋은 케이스 반환 시간 : 110초
convoy effect
짧은 시간동안 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상
최단 작업 우선 (Shortest Job First, SJF)
•
특징
◦
가장 짧은 실행 시간을 가진 작업을 먼저 실행 시킴
•
장점
◦
FIFO 대비 반환 시간에서 더 나은 성능을 보임
▪
반환 시간 : 50초 → 2배이상의 성능 향상
•
단점
◦
모든 작업은 동시에 도착한다는 가정을 완화하면 긴 실행시간을 가진 작업이 먼저 도착 했을 때 성능 감소
▪
반환 시간 : 103.33 초
최소 잔여 시간 우선(Shortest Time-to-Completion First, STCF)
•
특징
◦
작업은 끝날 때까지 계속 실행되어야 한다는 가정을 완화 (선점형 스케줄러)
▪
선점형 : 문맥 교환을 수행 할 수 있음
▪
비선점형 : 작업이 끝날 때까지 계속 실행해야함
◦
언제든 새로운 작업이 들어오면 현재 실행 중인 작업과 비교해서 적은 잔여 실행 시간을 가진 작업을 스케줄함
•
장점
◦
SJF대비 평균 반환 시간이 줄어듬
▪
반환 시간 : 50초
•
단점
◦
기아현상 발생 : 잔여 실행 시간이 긴 작업에 계속 밀릴 수 있음
◦
각 작업의 실행 시간이 사전에 알려져 있다는 가정이 비현실적임.
◦
응답시간이 느림
라운드 로빈(Round-Robin, RR)
•
특징
◦
작업이 끝날 때까지 기다리지 않고 일정 시간동안 실행한 후 실행 큐의 다음 작업을 실행함
▪
타임 슬라이스, 스케줄링 퀀텀 : 작업이 실행되는 일정 시간
•
장점
◦
응답시간이 빠르다
◦
공정성 측면에서 우수함
•
단점
◦
타임 슬라이스가 너무 짧으면 문맥교환에 들어가는 비용으로 인해 전체 성능에 큰 영향을 줄 수 있음
◦
반환 시간이 상대적으로 느리다
문맥 교환 시 갱신 해야 되는 정보들
- 레지스터
- CPU 캐시
- TLB, 분기 예측
- 기타 타 하드웨어에 저장된 프로그램과 관련된 정보
입출력 연산을 고려한 스케줄러
•
스케줄러가 고려해야 할 사항
◦
특정 작업이 입출력 요청을 한경우 다음에 어떤 작업을 스케줄 할 것인가?
◦
입출력이 완료되었을 때 어떤 행동을 할 것인가?
▪
입출력을 요청한 프로세스를 대기 상태에서 준비 상태로 이동시키기
▪
입출력을 요청한 프로레스를 바로 실행 시키기
•
중첩을 통한 CPU 사용 효율성 증대
아직 스케줄러가 각 작업의 실행 시간을 알고 있다는 비현실적인 가정을 완화하지 못했다.
이는 멀티 레벨 피드백 큐 라는 과거의 정보를 이용해서 미래를 예측하는 스케줄러를 통해 완화 해보자!
