cpu scheduling
전반적인 설명
프로그램이 실행이 되면 어떤 프로그램이 던 간에 위의 절차를 따라서 실행되며 진행된다.
load store, add store
cpu에서 인스트럭션을 실행하는 것이다.
I/O작업을 하면 I/O작업을 하다가 다시 cpu를 잡고서 실행한다.
프로그램의path
cpu만 연속적으로 하는 단계와 I/O작업을 하는 단계가 번갈아가면서 진행된다.
즉, 프로그램은 cpu를 잡고 수행하는 것과, I/O작업을 하는 것을 번갈아 가면서 수행한다.
CPU burst
cpu를 잡고서 프로그램이 실행되는 단계를 의미한다.
I/O burst
I/O작업을 하는 단계를 의미한다.
프로그램이 실행된다는 것은 cpu burst와 io burst를 번갈아 가면서 실행되는 것이다.
프로그램의 종류에 따라서 cpu burst와 I/O burst 빈번히 있는 것도 있고,
cpu burst가 많고 I/O burst가 적은 종류가 있을 수도 있다.
또한, 프로그램의 종류에 따라서 cpu burst와 I/O burst의 빈도와 길이가 다를 수 있다.
I/O bound Job
cpu를 짧게 쓰고 빈도가 잦으며, I/O작업이 많이 끼어드는 경우를 I/O bound job이라고 한다.
cpu bound Job
cpu를 아주 오랫동안 쓰고 빈도가 적으며, I/O작업이 드문 경우를 cpu bound job이라고 한다.
컴퓨터에는 여러종류의 프로그램이 있고, 프로그램별로 위에서 설명한 다양한 job(I/O bound job, cpu bound job등)이 섞여 있기 때문에 cpu 스케쥴링이 필요하다.
I/O바운드잡은 사람과 인터렉션을하는 Job이기 때문에 cpu바운드잡이 한번 cpu를 잡고 놓치 않으면 I/O바운드 잡은 오래 기다려야하고, 결국 사람은 답답함을 느낀다.
그렇기 때문에 cpu를 io바운드잡에 우선적으로 주는게 필요하다. 공평보다는 효율적인게 중요하다. cpu스캐쥴링 누구에게 우선으로 줄것인가, 언제 뺏을 것인가, 어느정도의 시간을 주고 뺏을 것인가. 역시 스캐쥴링의 중요 고려 사항이다.
I/O bound process VS CPU bound process
I/O bound process
주로 사람과 interactive하는 잡이다.
중간에 I/O가 많이 끼어들기 때문에 cpu burst는 빈번하고 짧아지게 된다,
cpu bound process
중간에 I/O가 없기 때문에 cpu를 연속적으로 쓰는 시간이 길어진다.
과학계산, 응용등에 활용 cpu burst가 길고, 빈번하지 않다.
why cpu scheduler
누구한테 cpu를 줄지를 결정하는 것을 cpu 스캐쥴러라고 한다.
스캐쥴러는 운영체제 안에 스캐쥴러를 하는 코드가 있다. 그 부분을 cpu 스캐쥴러라고 부르는 것이다. cpu를 누구에게 줄지 결정하는 운영체제 코드를 말한다.
dispatcher는 cpu를 누구한테 줄지를 결정했으면, 그 프로세스에게 cpu를 넘겨주는 역할을 하는 운영체제 커널 코드를 의미한다.
cpu를 줄려면 지금 cpu에서 돌아가는 프로세스의 context를 저장해야하고, 새로운 프로세스의 context를 준비해야한다.
cpu스캐쥴링이 필요한 경우
- 1.cpu를 어떤 프로세스를 잡고 있다가 I/O작업과 같이 오랜시간이 걸리는 작업을 하러가는 경우
- 2.나는 계속 cpu를 쓰고 싶은데, 무한정 cpu를 줄수 없기 때문에 빼앗아서 다른 프로세스한테 넘겨주는 경우 (timer interrupt)
- 3.I/O작업이 끝나고나서 devices controller가 인터럽트를 걸어서 프로세스의 상태를 block에서 ready로 바꾼경우
- 4.프로세스가 종료되서 새로운 프로세스에 cpu를 넘겨야 하는 경우
그 이외의 경우도 있다.
nonpreemptive(강제로 빼앗지 않고 자진해서 반납)
1,4는 더이상 작업을 할 게 없어서 자진 반납하는 경우이다.
preemptive(강제로 빼앗음)
2,3은 아직 더 cpu를 쓰고 싶은데 번갈아가면서 써야하기 때문에 넘겨주어야 하는 경우이다.
프로세스는 cpu로 인스트럭션을 실행하는 단계와 I/O작업을 하는 단계를 거치게 된다. 프로그램의 종류에 따라서 다른 경우도 있다.
I/O작업이 별로 없는 경우는 cpu burst가 길게 나타나고, 사람과 인터렉션하는 경우는 cpu burst가 잦고, 짧아지게 된다. cpu를 연속적으로 쓰는 것이 짧아진다.
cpu버스트가 짧다는 것은 I/O버스트가 끼어드는 경우이며, cpu버스트가 길다는 것은 I/O버스트의 난입이 적은 것이다.
컴퓨터은 다양한 종류의 프로세스가 섞여 있기 때문에 cpu scheduling 필요하다.
cpu버스트가 짧은 경우의 경우 cpu를 늦게 넘겨 주게 되면, 응답시간이 길어져서 사람이 답답함을 느낀다.
cpu스케쥴링은 ready q에 들어와 있는 cpu를 얻고자 하는 프로세스 중에서 어떤 프로세스에게 cpu를 줄것인지를 결정하는 것을 의미한다.
크게 두가지 이슈가 있다.
- 1.누구 한테 당장 cpu를 줄것인가.
- 2.cpu를 주었으면, 계속 쓰게 할것인가. 아니면 중간에 빼앗을 것인가. 빼앗으면 언제 빼앗을 것인가.
뺏지 않고 cpu를 다 쓸 때 까지 기다린다면, 뒤에 있는 I/O바운드 잡의 프로세스는 다른 프로세스가 끝날때 까지 오래 기다릴 수도 있다.
Scheduling 알고리즘
선점형 vs 비선점형
scheduling알고리즘은 두가지로 나누어서 생각할수 있다.
preemptive(강제로 빼앗음),nonpreemptive(강제로 빼앗지 않고 자진해서 반납)가 두가지 형태이다.
강제로 빼앗는가,아니면 자진해서 반납하는가에 따라서 선점형과 비선점형으로 나뉜다.
- nopreemptive 스캐쥴링 (비선점형)
- preemptive 스캐쥴링 (선점형)
알고림즘 성능 척도
스캐쥴링 알고리즘의 좋은 방법인지를 판단하는 방법
시스템입장과 프로그램 입장에서의 성능척도로 나눌 수 있다.
시스템입장의 성능척도
- cpu utilization
- throughput
cpu utilization
전체시간 중에서 cpu가 놀지 않고 일한 시간의 비율을 의미한다.
cpu는 가능한 바쁘게 일을 시켜야 한다. 전체시간 중에서 일한 시간 비율을 높게 하는 것이. 시스템입장에서 cpu를 잘 쓰는 것이다.
Throughput
주어지 시간동안에 몇개의 작업을 완료했는가를 의미한다. 주어지 cpu를 가지고 많은 작업을 하면 좋은 것이다.
프로그램 입장의 성능척도
cpu를 빨리 얻어서 빨리 끝나기를 원하는 경우, 가능하면 내가 먼저 서비스를 받고, 빨리 끝나기를 원하는 시간이 빨리 처리되는 것이 중요
- turnaround time
- wating time
- response time
Turnaround time(소요시간, 반환시간)
cpu를 사용하러 들어와서(q에서 기다리는 것 까지 포함) 다 쓰고 나갈 때 까지 걸린 시간.
waiting time
기다린 시간을 의미한다. cpu를 쓰고자 하더라고 ready q에 기다려야 하는 데, 순수하게 기다린 시간만을 의미한다.
response time
ready q에 들어와서 처음으로 cpu를 얻기 까지 걸린 시간
선점형의 경우 한번의 버스트 기간에도 얻었다, 뺏겼다 할 수 있다.
waiting time은 뺏겻을 때 다시 기다린 시간을 포함 한 모든 기다린 시간을 의미하다
response time은 처음 cpu를 얻기 까지 걸린 시간을 의미한다.
time share환경에서는 처음 cpu를 얻는 시간이 사용자 응답시간과 관련된 중요사항이다.
turnaround time 중국집에 들어와서 주문을 하고 먹고 나갈 때 까지의 시간
waiting time 손님이 밥을 먹은 시간이 아닌 기다린 시간이다.
response time 첫번째 음식이 나올 떄 까지 기다린 시간
FCFS(first come first served)
먼저오면 먼저 서비스 한다. 먼저 온 순서데로 처리를 하는 것이다.
비선점형 스캐쥴링이다. cpu를 주면, 다시 줄때 까지 빼앗을 수 없다.
cpu를 오래쓰는 프로세스가 있고 해당 프로세스가 cpu를 잡게 되면, 뒤에 있는 프로세스들은 앞의 프로세스가 끝날 때까지 기다려야 한다.
위의 그림이 아래와 같이 된다면, 들어오는 순서만 바뀔 뿐인데 완전히 달라지게 된다. waiting time의 평균이 바뀌게 된다.
FCFS는 앞에 어떤 프로세스가 있냐에 따라서 기다리는 시간에 많은 차이가 난다. 긴프로세스가 와서 짧은 프로세스가 오래 기다려야 하는 현상을 convoy effect라고 한다.
SJF(shortest-job-first)
전체적으로 좋은 결과가 나온다. cpu 버스트 타임이 가장 짧은 프로세스를 제일 먼저 스케쥴링을 한다. q가 전체적으로 짧아지게 된다.
선점형과 비선점형으로 나누어서 생각할 수 있다.
비선점형의 경우라면, 더짧은 프로세스가 와도 현재 cpu를 내어놓을 때까지는 cpu사용권을 보장한다.
선점형의 경우라면, cpu를 사용하다가도, 더짧은 프로세스가 오면 빼앗아서 넘겨주게 되는 방식이다. SRTF(shortest-remaining-time-first)라고 한다.
SJF is optimal
평균 대기 시간의 최소화를 보장한다.
SJF의 선점형에 해당한다.
비선점형 SJF의 경우는 cpu를 다 쓰고 나가는 시점에 스케쥴링을 할지말지를 결정한다.
선점형 SJF의 경우는 새로운 프로세스가 들어오면은 스케쥴링을 할지말지를 결정한다.
두가지 문제가 있다.
starvation문제(기아현상)
SJF는 극단적으로 짧은 잡을 선호하게 되므로, cpu가 사용시간이 긴 것은 영원히 서비스를 못 받을 수도 잇다.
cpu사용시간을 미리 알 수 없다는 문제
실제 미래를 알수 없기 때문에, 과거에 얼마나 썻는지로 예측을 할 수는 있다.
priority scheduling
우선순위 스케쥴링으로 우선순위가 높은 프로세스에게 cpu를 주는 것이다.
비선점형과 선점형이 있다.
비선점형은 우선순위가 높은 것에 주고, 수행하다가 더 높은 우선순위가 와도 빼았지 않는것이다.
선점형은 우선순위가 높은 것이 오면 빼앗는 것이다.
각프로세스마다 우선순위를 나타내는 숫자가 주어지게 된다.
작은 숫자가 우선숫자가 높은 것이다.
SJF도 우선순위 스케쥴링의 일종이라고 할 수 있다.
SJF의 경우는 우선순위가 cpu사용시간이라는 숫자로 할 수 있다.
우선순위 스캐쥴링의 문제는 sjf와 같은 기아현상이다. 낮은 우선순위의 프로세스가 cpu를 잡지 못할 수 있다.
시스템에서는 효율성을 추구하는 것이 중요하지만 특정 프로세스가 지나치게 차별받는 것을 막을 수 있어야 한다. aging(노화) 는 하나의 해결방법
너무 오래 기다리면 우선순위를 높혀주는 것이다.
starvation(기아현상) 를 막아 줄수도 있다.
Round Robin(RR)
현대적인 시스템에서는 라운드로빈을 기반으로 하고 있다.
할당시간을 셋팅해서 주고, 타임이 지나면 timer를 통해서 인터럽트를 받고 cpu를 빼앗기게 되는 선점형이다.
할당시간을 셋팅해서 주고, 그 시간이 끝나면, timer인터럽트로 cpu를 빼앗겨서 q에서 다시 기다리게 된다.
가장 좋은 점은 응답시간(Response time) 이 빨라진다는 점이 있다. 줬다 빼었다. 줬다. 빼었다 하기 때문에 응답시간이 빠르다.
기다리는 시간이 본인의 cpu사용시간에 비례하게 된다.
길경우 여러번 나누어서 반복해서 기다리게 된다.
할당시간을 아주 길게 하면 FCFC와 같은 알고리즘이 된다.
할당시간을 아주 짤게 한다면, context switch 오버헤드가 커진다.
적당한 규모의 time quantum을 주는 것이 중요하다.
일반적으로 SJF보다 평균 turnaround time이 길지만 response time은 더 짧다.
특이한 경우로 cpu 사용시간이 모두 동일한 프로세스가 있다고 가정하면, time quantum을 아주 짧게 한다면 모두 동이한 시점에 비슷하게 종료하게 된다.
