[Chapter 5]
I. 프로세스 실행 형태와 분류
A. 프로세스 실행형태
1. CPU burst: I/O수행 없이 CPU작업만을 수행하는 시간.
2. I/O burst: 프로세스가 I/O 요청으로 인해 수행을 중단하고 기다리는 시간.
프로세스는 CPU burst와 I/O burst가 스위칭되어가면서 동작한다.
B. 프로세스 분류
1. CPU-bound process: 상대적으로 CPU burst 시간이 긴 프로세스. 예를 들면 머신러닝 코드를 돌 린다고 하면 IO는 거의 없고 CPU버스트타임이 훨씬 길다. CPU바운드 프로세스는 타임퀀텀을 거의 다 사용한다. IO가 발생하지 않고 타이머 인터럽트에 의해서 레디큐로 넘어간다. I/O 바운드 프로세스보다 CPU를 많이 사용한다.
2. I/O-bound process: 상대적으로 I/O burst 시간이 긴 프로세스. GUI나 로딩바가 차오르는 등의 입출력에 따른 reaction을 보여줘야 하는 경우. 사용자와 interactive하게 동작하는 프로세스일 확률이 높다. 타임퀀텀을 다 사용하는 경우가 적다.
프로세스들 통계를 내보면 CPU bound process보다 I/O bound process가 더 많다.
II. 프로세스 선정
A. Dispatcher
1. Dispatch: 현재 실행중인 프로세스를 중단하고 다음 실행할 프로세스를 선택하는 작업. 컨텍스 트 스위칭의 일부로 간주된다. Dispatch latency는 dispatcher가 한 프로세스를 멈추고 다른 프 로세스를 실행시킬때까지의 시간이다. 이 구간에서 일아나는 일들은 현재 프로세스 상태를 PCB에 저장하고 스케줄러를 통해서 프로세스를 선정하고 다음 실행할 프로세스의 PCB를 복구 하는과정으로 컨텍스트 스위칭에서 일어나는 작업과 동일하며 커널모드에서 이뤄진다.
Dispatch과정 안에 스케줄링이 존재한다. Dispatch Latency가 길어지면 효율이 나빠지기 때문에 최대한 시간을 줄여야 한다. PCB백업 및 restore과정은 상수시간이 걸리는 고정된 작업이지만 스케줄링은 정책에 따라서 시간이 변동될 수 있다. 따라서 Dispatch Latency를 줄이기 위해서 스케줄링 알고리즘을 최적화할 필요가 있다.
B. 선점형/비선점형 스케줄링
1. 비선점형 스케줄링: CPU를 할당받으면 자발적으로 CPU반환하기 전까지 다른 프로세스는 점유
가 불가한 스케줄링 방식. 프로세스가 종료되거나 IO때문에 waiting상태가 되는게 아니면 다 른 프로세스가 점유 불가. 대표적인 비선점형 스케줄링은 FIFO, SJF 등
2. 선점형 스케줄링: 우선순위가 높은 프로세스가 현재 실행중인 프로세스를 중단시키고 점유할 수 있는 방식. 대표적으로 Round Robin. 타임퀀텀이 설정되어 실행하다가 시간이 지나면 다음 프로세스로 전환.
C. 스케줄링 성능 기준
1. CPU Utilization: CPU를 최대한 바쁘게 유지
2. Throughput: 단위시간동안 몇개의 프로세스를 처리할 수 있나
3. Turnaround time: 프로세스가 처음 도착한 시간에서 완료될때까지의 시간(completion time – arrival time)
4. Waiting time: 레디큐에서 기다리고 있는 시간.
5. Response time: 프로세스가 도착한 시간에서부터 처음 실행될때까지의 시간(첫 실행 – arrival time)
6. CPU Utilization, Throughput은 최대로 하고 나머지 time들은 최소로 하면 이상적이다. D. 스케줄링 목표
1. 모든 시스템: 프로세스들이 공정하게 스케줄링 될 수 있도록 하는 fairness, 시스템 하드웨어 자원을 효율적으로 사용하는 balance.
2. Batch System: 하나의 프로세스가 독점해서 사용하므로 Throughput최대화, Turnaround time 최소화, CPU Utilization최대화 3가지를 고려.
3. Interactive System: 레디큐, waiting큐에서 보내는 시간을 최소화해서 response time 최소화, waiting time 최소화, 사용자의 기대를 충족할 수 있어야한다.
4. Real-time System: 주기적으로 동작하는 테스크의 데드라인 만족이 가장 중요. 5. 시스템마다 지향하는 목표가 다르므로 스케줄링 정책도 다를 수 있다.
E. 스케줄링 주의점
1. Starvation: 여러개의 프로세스중에서 특정 프로세스가 자원을 할당받지 못해서 진행되지 못하 는 상황. Fairness가 보장되지 않는 경우 발생한다. 스케줄링 정책에서 Starvation을 배제하도록 해야한다. 동기화 문제로 인해서도 발생할 수 있다.
F. 스케줄링 알고리즘
1. FCFS: First come, First Served. 먼저 들어온것을 먼저 수행시켜준다. 줄서는것과 비슷함. Starvation이 없지만 단점으로 작은 작업이 큰 작업 뒤에 위치하면 평균 waiting time이 길어 진다.
위의 예시에서 p1의 waiting time은 0, p2는 24 p3는 27이 된다. 하지만 burst time이 짧은 것 부터 실행시키면 p2, p3, p1의 순서대로 실행되고, 그럼 평균 waiting time은 3으로 줄어든다. 이처럼 실행시간이 긴 프로세스가 짧은 프로세스보다 앞에 있어서 waiting time이 길어지고 효율성이 하락하는 것을 convoy effect라고 한다.
이상적으로는 burst time이 가장 짧은 프로세스를 앞으로 보내주면 되지만 실행되지 않은 프 로세스가 얼마만큼의 실행시간을 가질지 예측하는것은 어렵기 때문에 현실성이 없다. 2. SJF(Shortest job first): FCFS를 개선해서 짧은 burst time을 가진 프로세스를 먼저 스케줄링하는 알고리즘이다. 하지만 burst time의 예측이 어렵기 때문에 구현할 수 없다. 또한 starvation이 발생할 가능성이 있다. 머신러닝처럼 burst time이 굉장히 긴 작업이 있을때 짧은 작업이 계속 해서 들어오면 실행될 수 없다.
비선점형 알고리즘이다.
3. SRTF: Shortest Remaining time First. 남아있는 시간이 가장 짧은 작업을 먼저 수행한다. 우선순 위가 높아지면 선점해서 cpu를 차지할 수 있는 선점형 스케줄링 방식이다. preemptive SJF라고도 한다. SJF와 동일하게 현실적으로 구현하기 어렵다.
4. 우선순위 스케줄링: 도착한 순서나 burst time이 짧은 순서보다 더 중요한 것이 존재할 수 있 다. 중요한 작업을 먼저 하고 부수적인것들은 미뤄둘 수도 있다. 따라서 프로세스마다 우선순 위를 따로 부여해서 동작하도록 하는 스케줄링 알고리즘이 우선순위 스케줄링이다. 발생가능한 문제는 우선순위가 높은 작업이 계속해서 들어오면 현재 기다리는 중인 프로세스 에서 starvation이 발생할 수 있다. 따라서 Aging을 도입해서 레디큐에 있는 시간이 길어지면 age를 증가시켜서 우선순위에 올라가서 수행될 수 있도록 한다.
우선순위 큐를 여러개 만들고 각 큐에서는 다른 스케줄링 알고리즘을 적용할 수 있다. 우선순 위가 높은 큐가 비면 그 다음 우선순위의 큐의 작업을 수행한다.
5. 라운드로빈 (RR): 로빈이라는 새가 돌아가면서 조금씩 먹이를 주는것을 보고 이름 붙은 방식 이다. 타임쉐어링, 멀티프로세스 개념이 적용되었다. 각 프로세스는 타임퀀텀이라고 하는 단위 시간동안 자원을 부여받는다. 시간을 넘기면 선점형으로 다른 프로세스가 cpu자원을 차지한 다.
공평한 시간동안 쓸 수 있도록 해서 fairness가 보장된다. 타임퀀텀을 아주 길게 잡으면 context switching이 발생하지 않아서 FCFS와 동일하게 동작하고 response time이 나빠진다. 타임퀀텀을 아주 작게 설정하면 유저모드를 수행하는 시간이 줄어들고 커널의 오버헤드가 늘 어나므로 tradeoff를 고려해서 얼마로 타임퀀텀을 설정하느냐가 RR의 관건이다. 일반적으로 context switching에는 10ms미만의 시간이 걸리므로 10ms~100ms가 타임퀀텀으로 적절하고, 평균적인 CPU burst 시간의 80%정도로 설정하면 가장 좋다고 알려져있다. 타임퀀텀이 지나면 타이머 인터럽트가 발생하고 컨텍스트 스위칭이 일어난다.
6. Multilevel Queue Scheduling: 레디큐를 여러개의 큐로 나누고 각기 다른 스케줄링 알고리즘을 적용할 수 있다. 예를 들면 foreground와 background로 나눠서 interactive한 작업은 foreground큐에서 RR을 적용하고 CPU burst가 많은 작업은 background에서 FCFS로 스케줄 링한다. foreground작업은 response time이 중요한 작업들이고 background 작업은 cpu bound 작업들이라 연속적으로 수행되도록 해서 효율을 올린다.
foreground는 우선순위가 높은데 우선적으로 처리하면 background는 starvation이 발생할 수 있다. 하지만 aging을 통해서 background작업을 foreground로 보내도 오래걸리는 작업이라면 foreground가 오랫동안 수행되지 않을 수 있다. 그래서 aging을 사용하지 않고 타임퀀텀을 쪼개서 80%정도를 foreground에서 사용하고 나머지를 background에서 사용한다.
실제로는 멀티레벨 큐가 foreground와 background가 아니라 여러개의 큐로 이루어져 있다. 프로세스들은 각자의 성질에 맞는 큐에 들어간다. 각 큐들은 다른 정책을 사용해서 스케줄링 할 수 있다. 하지만 단점이 존재하는데 ide같은 에디팅할 시에는 io가 많이 발생하고 컴파일 할때는 batch의 특성을 지니는 프로세스는 어느 큐에 들어갈지 임의로 정할수밖에 없다.
7. Multilevel Feedback Queue: 유닉스에서 실제로 사용하고 있는 방식. 프로세스가 생성되어서 레디큐에 들어간다. 3개의 우선순위 큐가 존재하는데 RR으로 동작하는 타임퀀텀이 8인 큐에 첫번째로 들어간다. 만약 타임퀀텀 8을 다 채우지 못하고 waiting 큐로 빠진다면 짧은 시간 내에 IO요청을 했다는 것이고 IO바운드 프로세스라는 것이므로 다음에도 RR을 통해 선정됐을
때 q(타임퀀텀)=8인 큐에 들어온다. 만약 타임퀀텀을 다 쓴다면 CPU burst time이 길다는 것 이므로 q가 더 큰 q=16 큐에 들어가게 된다. q=16인 큐에서도 타임퀀텀을 다 쓴다면 FCFS로 동작하는 큐로 내려간다.
피드백 큐는 IO바운드인지 CPU바운드인지 실제로 돌려보고 결정하므로 프로세스에 적응해서 스케줄링할 수 있다. 현재는 더 발전해서 타임퀀텀을 다 쓰는지 여부에 따라 우선순위큐에서 올라갔다 내려갔다 하며 동적으로 우선순위가 변한다.
8. Multiprocessor Scheduling: 코어가 여러개 있는 경우 스케줄링 방법. Symmetric과 Asymmetric
이 있다. 요즘은 다 symmetric을 사용한다. 멀티프로세서에서 중요한것은 각 코어마다 밸런스 를 잘 맞추는 것이다. 한 코어에 태스크가 집중되고 다른 코어는 유휴상태이면 유휴상태의 코 어에 작업을 옮겨 로드밸런싱 하는것을 마이그레이션이라고 한다. 바쁜 코어가 주는것을 push migration, 받는것을 pull migration이라고 부른다.
Processor Affinity는 프로세스나 스레드의 작업을 지정된 CPU에서 실행될 수 있도록 하는것이 다. Soft Affinity는 하나의 레디큐에서 여러개의 코어가 하나씩 작업을 가져가는 것이고, Hard Affinity는 각각 큐를 다르게 둬서 지정된 CPU에서 기존에 하던 작업을 수행할 수 있도록 하 는것이다. Hard인 경우는 기존에 해당 코어가 수행했던 작업이므로 cache hitting rate이 높다 는 장점이 있다. 하지만 스케줄링 큐가 여러개가라서 스케줄링 알고리즘이 무겁다는 단점이 있다.
9. Real Time Scheduling: 리얼타임 스케줄링의 특징은 데드라인이 존재한다는 것이다. 하드 리얼
타임 시스템은 비행기 시스템과 같은 반드시 지켜져야 하는 데드라인이 존재하는 시스템이고, 소프트 리얼타임 시스템은 늦어도 큰 문제가 발생하지 않는 채팅 프로그램 등이다. 데드라인 만족을 보장하지는 않는다. 리얼타임 스케줄링은 임베디드 시스템에서 주기적으로 반복적인 작업을 수행하는 경우가 많다.
리얼타임 우선순위 스케줄링은 Static방식과 Dynamic방식으로 나뉜다. Static 방식은 Rate Monotonic 알고리즘으로 동작하는데, 주기의 역수가 클수록, 즉 주기가 짧을수록 우선순위가 높아진다. 현재 모든 리얼타임 시스템은 static방식을 사용한다. 만약 Static에서 데드라인 미스 가 발생한다면 주기가 데드라인 이상인 경우 등 설계를 잘못한 것이다.
Dynamic 방식은 데드라인이 적게 남은 작업에 대해서 우선순위를 부여하기 때문에 우선순위 가 계속 변경된다. EDF(earliest deadline first)스케줄링이라고 한다. 일반적으로 리얼타임 시스템 은 임베디드 기반으로 구축해서 하드웨어가 좋지 않은데, Dynamic방식은 스케줄링 오버헤드 가 커서 사용하지 않는다.
G. 운영체제 스케줄링 예시
1. 리눅스 스케줄링: 현재 존재하는 대부분의 운영체제와 같이 우선순위 기반으로 동작하고 우선 순위 같은 프로세스는 라운드로빈으로 동작함. 우선순위는 리얼타임과 노말로 나뉘며 리얼타 임이 우선순위가 높다. 리얼타임은 커널이 사용하고 노말은 유저가 사용하는 프로그램이 동작 한다. 멀티레벨 피드백 큐 형태로 되어있고 노말의 피드백 큐를 CFS라고 부른다. CFS는 Completely Fair Scheduling으로 프로세스 탐색과정에서 오버헤드를 줄이기 위해서 Binary
Search Tree로 관리한다.
2. 윈도우 스케줄링: 고정된 우선순위 테이블이 존재하고 프로세스는 create되자마자 우선순위가 정해진다. 같은 우선순위끼리는 라운드로빈으로 동작한다.
3. 솔라리스 스케줄링: 스레드가 생성될때 우선순위를 부여받고 같은 우선순위끼리는 RR. 시스템 커널은 높은 우선순위를 가지고 사용자 프로그램은 낮은 우선순위를 가진다. H. 알고리즘 평가
1. 수학적 모델링(Deterministic modeling, Queueing models)
2. 시뮬레이션: 수학적 모델링과 구현의 중간형태. 구현이 어려운 상황에 사용하고 환경적인 변수 가 적용되지 않을 수 있어서 신뢰성은 구현보다 떨어진다. 시뮬레이션에 필요한 input은 cpu burst, io burst인데, 포아송 분포와 같은 확률분포를 이용해서 input을 생성할수도 있고 실제 데이터를 수집해서 사용할수도 있다. 실제로 수집한 데이터를 사용하는 게 더 효과적이고, 이 데이터를 trace tape이라고 부른다.
3. 구현: 실제환경에서 구현. 시간과 노력이 많이 필요하고 구현이 불가능한 경우 수학적 모델링 과 시뮬레이션으로 평가한다.