어떤 프로그램이든 간에 위와 같은 path를 실행하며 진행된다. cpu를 잡고 실행하다가 오래걸리는 I/O 작업과 마주하게 되면 기다리다가 I/O 작업이 끝나면 ready로 들어갔다가 CPU를 쓴다.
프로그램마다 다르겠지만 결론적으로 CPU를 연속적으로 쓰는 단계와 I/O를 실행하는 단계가 번갈아 나타나며 이를 각각 CPU burst, I/O burst라 부른다. 단, 프로그램의 종류에 따라 CPU burst, I/O burst가 빈번한 경우가 있고 CPU가 빈번하다가 I/O가 가끔 들어오는 경우가 있다.

사람이 사용하는 프로그램은 I/O가 굉장히 빈번히 일어난다. 입력 받고, 화면에 출력해주는 일이 많기 때문이다.
과학 계산용 프로그램 같은 경우엔 한참 연산을 해야하므로 오랫동안 CPU를 사용하다가 계산이 끝나면 화면에 출력해준다.

컴퓨터안에서 돌아가는 것들의 CPU burst양을 찍은 것이다. I/O가 많이 끼어드는 경우가 굉장히 많았고, CPU만 사용하는 경우는 빈도가 낮았다. 각각을 I/O bound job, CPU bound job 이라고 부른다. 따라서 컴퓨터 내부에는 여러 종류의 job이 섞여 있다. 따라서 CPU 스케줄링이 필요하다.

위의 도표를 통해 우리는 대부분의 CPU 시간은 I/O bound job에 다 쓰는구나 라는 추론을 해낼 수 있는가? 아니다. I/O bound job은 I/O가 자꾸 끼어들어서 CPU 시간이 짧게 난도질 당해서 그런것이고, CPU bound job은 CPU를 오랫동안 쓰기 때문에 빈도가 적을 수 밖에 없다. 따라서 이 도표를 보고 CPU를 많이 쓰는게 I/O bound job이구나 하면 안되고 CPU bound job이 CPU를 많이 쓰는데, I/O bound job은 짧게 많이 쓰는 구나 라고 해석하면 된다.

I/O job은 보통 사람과 상호작용하는 interactive job으로 적절한 response를 제공해야한다. CPU bound job이 한번 CPU를 잡고 놔주지 않으면 I/O bound job은 CPU를 잡지 못해 사용자가 답답하다. 따라서 사용자가 답답하지 않도록 interactive job을 우선순위로 둔다. 따라서 호율적이고 interactive job을 너무 오래기다리지 않도록 하는 것이 중요하다. 스케줄링은 스케줄링 하기 나름이다. CPU bound job이 스스로 CPU를 반납하도록 기다리게 스케줄링 할 수도 있는 것이다.

• I/O bound process
  • many short CPU bursts
• CPU bound process
  • few very long CPU bursts

CPU Scheduler & Dispatcher

CPU Scheduler

누구한테 CPU를 줄 지 결정하는 역할을 한다. Scheduler는 S/W, H/W, 프로그램 중 무엇인가? 이는 운영체제 안에서 CPU 스케줄링을 하는 코드가 있고 이를 그냥 CPU Scheduler다 라고 하는 것이다. 특정 기능을 하는 것을 부르는 것

Dispatcher

CPU를 누구한테 줄지 결정했으면 CPU를 넘겨주는 역할을 한다. CPU에서 돌아가던 프로그램의 context를 저장하고 새로 배정받은 프로그램의 context를 펼쳐놓은 뒤(CPU내에 레지스터 값 세팅) CPU를 넘겨준다.

이 과정을 context switch라고 한다.

이러한 CPU Scheduling이 언제 필요한가 ?

프로세스에게 다음과 같은 상태 변화가 있는 경우이다.

• Running -> Blocked (ex. I/O)
  • CPU 잡고 있다가 오래 걸리는 작업을(I/O) 마주하면 스스로 자진해서 CPU를 내놓음
• Running -> Ready (ex. 할당시간 만료 ->timer interrupt)
  • 무한정으로 CPU 줄 수 없기 때문에 타이머가 다 되면 CPU를 강제로 빼앗고 다른 프로그램에 CPU 넘겨줌
• Blocked -> Ready (ex. I/O 완료 -> interrupt)
  • 오래걸리는 작업이 끝나고 device controller가 interrupt를 걸어 ready로 간다.
  • I/O 가 끝났다고 해서 바로 CPU를 점유하지 않고 ready로 갔다가 자신의 순서가 왔을 때 CPU를 사용하는 것이 일반적이나, 우선순위가 있는 스케줄링의 경우(I/O 했던 프로세스가 가장 높은 우선순위) I/O 끝난 프로세스에게 바로 넘겨줘야함
  • 강제로 빼앗김 (우선순위가 낮아서)
• Terminate
  • 프로세스가 종료돼서 더이상 할일이 없으니 새로운 프로세스에 CPU를 줘야할 때
  • CPU를 가지고 있어도 실행할 명령이 없으니 자진 반납

nonpreemptive : 강제로 빼앗지 않고 자진 반납 (더이상 실행할 instruction이 없어 다른 프로그램에 자진 반납)
preemptive : 시간이 다 됐거나, 우선순위 문제로 강제로 빼앗음

CPU 스케줄링 알고리즘은 여러가지가 있고 이를 크게 두가지로 나눌 수 있다. 바로 nonpreemptive(비선점), preemptive(선점)이다.

Scheduling Algorithm

여러 Scheduling 알고리즘을 소개한다.

Scheduling Criteria

Performance Index( = Performance Measure, 성능 척도)

그 전에 어떤 알고리즘이 좋은지 판별하기 위한 성능 평가 요소들을 소개한다. 특별히 CPU 를 위한 성능 척도로 Scheduling Criteria 라고 한다.

이를 두가지로 분류할 수 있다.

시스템 입장

시스템 입장에서는 CPU 하나로 최대한 일을 많이 시키면 좋은 것이다.

• CPU utilization : 이용료
  전체 시간중에서 CPU가 놀지 않고 일한 시간의 비율을 말한다.
  CPU는 가능한 한 바쁘게 일을 시켜라 ! CPU는 굉장히 비싸므로 일하는 시간의 비율을 높여야한다.

• Throughput : 처리량
  주어진 시간동안에 과연 몇개의 일을 처리했느냐, 몇개의 작업을 완료했느냐
  주어진 CPU를 가지고 주어진 시간에 더 많은 일을 처리하면 좋다.

프로그램(프로세스) 입장

내가 CPU를 빨리 얻어 빨리 끝내면 좋은 것 -> 시간을 얼마나 빨리 처리하느냐
사용자 입장 -> 가능하면 내가 빨리 서비스를 받는것, 대기 시간이 적은 것

• Turnaround time : 소요시간, 변환시간
  CPU를 쓰러들어와서 다쓰고 나갈때까지 걸리는 시간을 말한다.
  I/O가 끝나 CPU를 쓰러 Ready에서 줄을 서 기다리다가 CPU를 잡아 일을 하고 I/O를 하러 나갈 때까지의 시간이다.

• Waiting time : 대기 시간
  기다린 시간, 즉 CPU를 쓰고자 하더라도 Ready 큐에서 기다려야 하는데 이때 기다리는 시간이다.

• Response time : 응답 시간
  Ready queue에 들어와서 처음으로 CPU를 얻기까지 걸리는 시간이다.

Waiting time과의 차이점

선점형 스케줄링은 CPU를 쓰다가도 뺏겼다가 다시 쓰다가 뺏길수도 있다. 그래서 쓰다가 다시 기다릴 수도 있다. 따라서 한번의 CPU burst동안에도 CPU를 얻었다 뺏겼다 할 수 있다. 따라서 대기 시간도 굉장히 여러번 일어날 수 있는 것이다. Waiting time은 이러한 대기시간을 다 합친것을 말한다.

Response time은 처음 CPU를 얻기까지의 시간만이다.

굳이 시간과 관련된 성능척도를 세개씩 나누어서 이야기하는게 있는가? 특히 Response Time을 둔 이유는 무엇인가?

Time sharing 환경에서는 처음으로 CPU를 얻는 시간이 사용자 응답과 관련해서 굉장히 중요한 개념이다.
중국집을 예시로 들어보자

중국집을 운영한다고 가정하자. 주방장을 한명 고용하면 주인 입장에서는 주방장이 일을 많이 하면 좋다. 따라서 주인 입장(시스템 입장)에서는 전체 시간중에서 주방장이 일을 쉬지 않고 하는 비율(Utilization)이 높으면 좋다. 단위시간당 손님을 몇명이나 밥을 먹여 내보냈는가(Throughput). 가능하면 손님이 많은게 좋다.

고객입장에서는 중국집에 밥먹으러 들어와서 주문하고 다먹고 나갈때 까지 걸린 시간이 Turnaround Time이다. 짜장면만 시키면 먹고 바로 나가겠지만, 코스 요리를 시키면 하나의 요리를 먹고 다음요리를 기다리고 먹고를 반복한다. 따라서 이러한 대기시간과 식사시간이 다 합쳐진게 Turnaround Time이다.

손님이 밥을 먹은 시간말고 기다린 시간을 합친걸 Waiting Time이고, 첫번째 음식이 나오기까지 기다린 시간이 Response Time이다. 단무지라도 먼저 내오면 허기를 달랠 수 있음 -> 중요한 척도다.

FCFS (Fist-Come First-Served)

먼저온 고객을 먼저 상대해주는 것이다.
스케줄링 방법이라 하기도 민망하다. 먼저 온 순서대로 처리한다고 생각하면 된다.
사람세계에서는 이 스케줄링 기법이 많이 사용된다. 사람이 많아 대기할 때 먼저 대기한사람이 들어가기 때문이다.

효율적이지 않다. CPU를 오래쓰는 프로그램이 도착해 먼저 CPU를 잡으면 interactive하는 job(CPU를 짧게 쓰는)이 와도 굉장히 오래기다려야 한다.

도착하는 프로세스가 위와 같을 때 아래와 같은 Gantt chart를 그릴 수 있다. 간발의 차로 프로세스가 차례대로 도착을 했다.

프로세스를 실행순서대로 보여주고 있다. FCFS이기 때문에 프로세스가 일찍 도착한 순서대로 실행된다.
만약 P1의 실행시간이 백만초라고 가정하면 뒤의 프로세스들은 굉장히 많은 시간 대기를 해야한다. 따라서 좋은 스케줄링 방법이 아니다.

Waiting time을 나타내면 다음과 같다.

P1 = 0;
P2 = 24;
P3 = 27;

이를 평균 내보면 (0+24+27)/3 = 17이다.

CPU를 짧게 쓰는 프로세스들이 먼저 도착한다고 가정해보면 아래와 같이 변경된다.

따라서 각각의 Waiting time은 아래와 같다.

P2 = 0;
P3 = 3;
P1 = 6;

이를 평균 내보면 (0+3+6)/3 = 3으로 앞의 경우보다 굉장히 짧아진다. 그래서 FCFS는 앞의 프로세스가 어떤게 있냐에 따라 성능에 많은 영향을 끼친다.

중국집을 예로 들면 손님이 5시간 걸리는 요리를 주문하면 주방장이 5시간 걸리는 요리를 먼저하고 그 후에 온 손님들은 짜장면 하나만 시켜도 5시간을 기다려야 하는 것이다.

따라서 긴 프로세스가 하나 도착해서 짧은 프로세스들이 지나치게 기다려야 하는 현상은 Convoy effect라 하며 이는 좋은 현상이 아니다.

Convoy는 전쟁 중 물자를 지키도록 앞뒤에서 호송하는 개념이었는데, 컴퓨터 시스템에서는 큐에서 오래기다리는 의미로 변형되어 사용되고 있다.

SJF (Shortest-Job-First)

CPU를 사용하고자 하는 시간이 (CPU burst 시간) 가장 짧은 프로세스 부터 실행하는 것이다.
예를 들어 은행에서 볼일이 한시간 걸리는 사람이 있고 1분씩 걸리는 사람이 대기를 한다고 가정했을 때 짧은 시간이 걸리는 사람에게 먼저 볼 일을 보도록 하는 것이다. 그러면 줄이 빨리 빠져서 Waiting time이 줄어들고 평균 Waiting time이 가장 최소화 된다.

두가지 방식을 생각해볼 수 있다.

Nonpreemptive

일단 기다리는 프로세스 중에서 CPU를 짧게 쓰는 친구에게 줬으면, 더 짧게 쓰는 친구가 와도 기존에 쓰던 프로세스에게서 CPU를 뺏지 않고 완료되는 것을 보장하는 것이다.

따라서 위와 같이 프로세스가 존재하고 Arrival time에 도착한다고 가정해보자.
0초에는 P1밖에 도착하지 않았으므로 P1을 실행시간인 7초 만큼 실행한다. 7초 후에는 모든 프로세스들이 도착했으므로 이 중 가장 짧은 실행시간을 가진 프로세스가 실행된다.

preemptive

CPU를 줬다고 하더라도 더 짧은 프로세스가 도착하면 CPU를 뺏어 넘겨주는 방식이다.
그래서 이 버전을 Shortest-Remaining-Time-First(SRTF)라고도 부른다.
매번 CPU를 줄 때 짧다는 개념이 과거에 썼을 때 앞으로 남은 시간이 짧은 프로세스에게 CPU를 주는 것이므로 !
P1이 총 5초 걸리는데, 이미 CPU를 점유해서 3초를 씀. 새로운 프로세스 P2가 들어오는데 P2의 실행시간은 3초이다. 이때 짧은 것을 대조하는 방법은 P1의 남은 실행 시간 vs P2의 실행시간 이므로 SRTF 라고도 부르는 것이다.

average waiting time을 최소화 하는 것은 preemptive 방식이다.

0초 시점에는 P1 혼자 도착했으므로 P1이 실행된다. 2초에 P2가 도착한다. 이때 P1의 남은 실행시간은 5초이고, P2의 실행시간은 4초이다. 따라서 P2의 실행시간이 더 짧으므로 P2에게 CPU를 넘겨준다. 그다음에 4초가 되면 P3가 도착한다. 이때 P2의 남은 실행시간은 2초이고 P3의 실행시간은 1초이므로 P3에게 CPU를 넘겨준다. P3가 1초를 쓰고 나면 모든 프로세스가 도착하게 되는데, 이때 실행시간이 각각 5(P1), 2(P2), 4(P4)이므로 P2, P4, P1 순으로 실행된다. 따라서 대기시간의 평균을 구하면 (9+1+0+2)/4=3이다.

따라서 nonpreemptive보다 더 적은 평균 waiting time을 가짐을 알 수 있다.

또한 preemptive의 average waiting time이 minimum이므로 어떠한 알고리즘을 사용해도 위의 예제에선 3초가 최소이다.

만약 도착 시간 없이 위와 같이 도착한다면 아래와 같은 Gantt chart가 그려질 것이다.

그렇다면 optimal, 즉 minimum average waiting time을 가지므로 SJF가 좋은가? 아니다. SJF에는 두가지 문제점이 있다.

문제점

starvation

극단적으로 CPU 사용시간이 짧은 프로세스를 선호 한다. 그래서 CPU 사용시간이 긴 프로세스는 영원히 CPU를 사용하지 못할 수도 있다. 계속해서 사용시간이 짧은 프로세스가 들어오면 사용시간이 긴 프로세스는 계속 기다리기만 해야하기 때문이다.

우리말로 번역하면 기아 현상으로 굶어죽는 것이다.

long process가 starvation 될 수 있다 !

CPU 사용시간을 미리 알 수 없음

프로그램이라는 것이 실행하다보면, input을 받아서 실행되기도 하고 상황에 따라 branch가 일어나기도 한다. 따라서 매번 CPU를 쓰러 들어와서 내가 얼마나 쓰고 나갈지 모른다는 것이 문제다.
따라서 실제 사용시간을 미리 알 수 없다. 하지만 추정은 할 수 있다.

I/O bound job은 CPU가 짧게 나타나고 CPU bound job은 길게 나타나므로 과거에 CPU를 사용한 흔적을 통해 CPU를 얼마나 쓸지 예측하는 것이다. 정확하진 않겠지만 비슷한 패턴을 나타내므로 예측이 가능하다.

과거의 CPU burst time을 토대로 예측 -> exponential average를 사용한다.

t : 실제 실행 시간 (n번째 실제 실행 시간)
τ : 예측 시간 (n+1번째 CPU 예측 시간)

과거에 어떻게 사용했는지 n개가 주어진 상황에서 n+1번째 사용시간이 어떻게 될 지 예측하는 것

α는 0이상 1이하의 값이다. 이 식을 풀어볼 수 있는데, n자리에 n-1을 집어넣고 계속 -1된 값을 집어 넣으면 아래와 같다.

n이 작아질 수록 (1-α)를 더 곱해지는 것을 볼 수 있는데 (1-α)는 0과 1사이의 값으로 점점 더 작아진다. 따라서 n 번째 보다 n-1 번째의 실행시간을 조금 덜 반영하고 n-1번째 보다 n-2 번째의 실행시간을 덜 반영한다는 것을 알 수 있다.

현재를 기준으로 최근의 일은 가중치를 좀 더 높여 반영하고 더 오래전의 일은 가중치를 좀 더 줄여 반영하는 것이다.

Priority Scheduling

우선순위 Scheduling 로 추상적으로 이야기하면 우선순위가 높은 프로세스에게 CPU를 주는 것이다. 이 알고리즘 또한 nonpreemptive와 preemptive 방식으로 나눌 수 있다. 우선순위가 높은 프로세스에게 CPU를 줬는데, 더 높은 프로세스가 왔을 때 CPU를 뺏어서 주면 preemptive이고 뺏지 않고 완료를 보장하면 nonpreemptive이다.

우선순위를 정의하는 방법은 다양할 것이다. 우선순위를 나타내는 숫자가 보통 정수값으로 표현된다. 가장 높은 우선순위는 가장 적은 숫자로 나타낸다. 따라서 samllest integer = highest priority이다.

SJF 또한 우선순위 스케줄링의 일종이라고 말할 수 있다. 우선순위를 CPU 사용시간이 작은 순으로 주면 된다.

nonpreemptive

위와 같은 프로세스가 도착했다고 할 때 아래와 같은 Gantt chart를 그릴 수 있다.

문제점

starvation

SJF와 같이 우선순위가 낮은 프로세스들은 우선순위가 높은 프로세스들에 밀려 영원히 실행되지 못할 수 있는 문제점이 있다.

컴퓨터 시스템에서는 효율성을 추구하는 것이 가장 중요한지만 특정 프로세스가 지나치게 차별받지 않도록 해야한다.
따라서 이를 해결하기 위해 Aging이라는 기법을 도입한다. 아무리 우선순위가 낮은 프로세스라 하더라도 오래기다리게 되면 우선순위를 조금씩 높여주자는 것이다. 그래서 오래 기다리면 우선순위가 높아져 언젠가 실행될 수 있는 것이다.

Round Robin (RR)

현대적인 컴퓨터 시스템에서 사용하는 CPU Scheduling 은 round robin에 기반하고 있다.
CPU를 줄때는 그냥 주는게 아니고 할당 시간을 같이 줘 시간이 다 되면 time interrupt가 걸려 CPU를 빼앗긴다.

CPU를 줄 때 동일한 크기의 할당시간을 세팅해서 주고 시간이 끝나면 time interrupt가 걸려 CPU를 빼앗기고 Ready queue로 돌아간다. 그러면 다음 프로세스가 또 할당 시간 만큼 실행한다.

가장 좋은 점은 응답시간이 빨라진다는 것이다. 최초로 CPU를 받는 시간이 빠르다는 것이다. 누가 CPU를 오래쓸지 모르는 상황에서 굳이 예측할 필요 없이 CPU를 짧게 쓰는 프로세스가 빨리 쓰고 나가도록 할 수 있게 하는 것이 장점이다. 현재 Queue에 n개의 프로세스가 있고 할당시간이 q라고 하면 내가 적어도 (n-1)*q 시간만 기다리면 적어도 내차례가 한번은 돌아온다. q를 굉장히 짧게 잡으면 내가 CPU를 잡을 수 있는 시간이 빨리 오게 된다. CPU를 아주 짧게 쓰는 프로세스는 한번에 할당시간만에 쓰고 나가니 응답시간이 빨라지고, CPU를 길게 쓰는 프로세스는 여러번 할당시간을 사용할 것이다.

또한가지 재미있는 특징은 CPU를 길게 쓰는 프로세스는 기다리는 시간도 길어지고 CPU를 짧게 쓰는 프로세스는 기다리는 시간도 짧아진다. 기다리는 시간이 본인이 CPU를 사용하려는 시간에 비례하게 된다는 것이다.

극단적인 상황을 생각해보자

q를 아주 크게 잡으면 FCFS와 같은 알고리즘이 된다.
q를 지나치게 작게 잡으면 계속 CPU를 얻었다 뺏겼다 반복되기 때문에 context switch가 빈번하게 일어나 오버헤드가 커진다. 따라서 시스템 전체의 성능이 나빠지는 결과를 초래할 수 있다.

그래서 q를 적절히 잡는 것이 중요하고 일반적으로 from 10 to 100 milliseconds로 잡는다.

예제를 살펴보자.

quantum을 4라고 잡으면 아래와 같은 Gantt chart가 그려질 것이다.

P2, P3는 할당시간 보다 자신의 실행시간이 적기 때문에 할당시간을 다 쓰지 않고 나간다. 따라서 RR은 SJF보다 turnaround time 이나 waiting time이 길어질 수 있지만 response time은 더 짧다.

프로세스가 한개만 존재하고 10초의 실행시간을 가진다고 가정할 때, quantum에 따라 context switch가 달라지는 것을 볼 수 있다.

RR은 CPU 시간이 짧은 프로세스와 긴 프로세스가 얼마나 쓸지를 알 수 없고 마구잡이로 섞여있을 때 사용하기 좋다.
CPU 사용시간이 모두 동일한 프로세스가 모여있다면 번갈아 실행하면 거의 동시에 빠져나가게 된다. (사용시간이 100초인 process 4개에 q가 1인 RR scheduling이라면 1초씩 나눠서 실행하다가 마지막에 1초간의 간격을 두고 거의 동시에 4개가 다 빠져나간다. 하지만 FCFS를 사용하면 100초씩 실행해 4개의 process가 순서대로 먼저 나갈 수 있다. )

모든 프로세스가 기다리다가 동시에 나가는 것 vs 그때 그때 CPU를 쓰고 나가는 것
RR을 하게 되면 거의 모든 프로세스들이 마지막까지 남아있어 waiting time이 길어져 안좋은 점이 있다.

하지만 일반적으로는 긴 프로세스와 짧은 프로세스가 섞여있어서 RR이 효율적이다.
아래의 예제를 보자.

quantum을 1부터 7까지 늘려가며 turnaround time을 분석한 것이다.

Priority + RR

같은 prioriy를 가질 때 RR을 사용한다고 가정하고 quantum을 2로 잡으면 아래와 같은 Gantt chart를 그릴 수 있다.

Multilevel Queue Scheduling

이제까지는 Ready queue에 한줄로 줄을 섰다. 이제는 여러 줄로 줄을 선다.

밑으로 갈 수록 우선순위가 낮은 줄이다. 여러 줄 서기에는 줄 마다 우선순위가 있다. 위의 그림에서는 5개의 우선순위로 나뉘어져있으며 system, interactive, interactive editing, batch, student 순이다. 계급제이므로 본인의 우선순위에 따라 줄을 서야한다. 따라서 우선순위가 높은 줄에서 부터 프로세스를 빼서 실행하는데 비어있으면 아래 우선순위 줄을 본다. 따라서 출신에 따라 영원히 우선순위를 극복하지 못하는 스케줄링이다.

foreground는 interactive이므로 response time이 짧은 RR이 낫다. background는 CPU를 오래 붙잡고 있는 것들이므로 FCFS가 효율적일 것이다. 따라서 줄 마다의 특성을 고려해 스케줄링 알고리즘을 할당한다.

starvation을 해결하기 위해 Time slice -> 각 큐에 CPU time을 적절한 비율로 할당하는 것이다. 80%는 우선순위가 높은 줄, 20%는 우선순위가 낮은 줄에 준다. RR은 공정하나 이 방법은 공정하진 않고 차별적이다.

신분을 영원히 극복하지 못하는 방식은 문제가 있다.

Multilevel Feedback Queue Scheduling

이 스케줄링은 여기도 여러 줄이 있지만, 출신이 낮아도 중간에 승격되기도 하고, 출신이 좋아도 강등당하기도 하는 스케줄링이다.

줄 간 이동이 가능하다. 즉, 프로세스가 다른 큐로 이동이 가능하다.
Aging을 이와 같은 방식으로 구현할 수 있다.

Multilevel Feedback Queue Scheduler를 정의하는 파라미터들

• queue의 수
• 각 queue의 scheduling algorithm
• 프로세스를 상위 queue로 보내는 기준
• 프로세스를 하위 queue로 내쫓는 기준
• 프로세스가 CPU 서비스를 받으려 할 때 들어갈 queue를 결정하는 기준
  • 처음 프로세스가 들어갈 때 어떻게 들어갈 것인가

일반적으로는
처음에 들어오는 프로세스를 우선순위가 가장 높은 queue에 넣는다. 우선순위가 높은 queue는 quantum을 짧게 주고 낮을 수록 길게 준다. 맨 아래에는 FCFS로 처리한다.
그래서 큐 내에서 할당시간 내에 일을 처리하지 못하면 우선순위가 낮은 queue로 쫓겨난다. 그래서 아주 CPU burst가 짧은 프로세스는 도착하자마자 바로 CPU를 받아 빠져나갈 수 있고, CPU burst가 긴 프로세스는 계속 일을 끝내지 못해 아래 queue로 계속 내려간다. CPU 사용시간이 짧은 프로세스들에게 선택권을 많이 주는 방식이다.
RR로만은 해결이 안되기 때문에 이러한 방식을 사용한다. 이 방식은 CPU 사용시간이 긴지 짧은지 예측 또한 필요없다.

ex)

지금까지 본 CPU Scheduling은 CPU가 하나 밖에 없는 Scheduling이다. 이제는 CPU가 여러개 있거나, 시간에 대한 deadline 조건이 있거나 등의 특이한 조건에서의 Scheduling을 알아보자

Multiple Processor Scheduling

CPU가 여러개 있으면 ? -> 은행 창구가 하나였다가 여러개로 늘어난 것 뿐이다.

Homogeneous processor인 경우

queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
어떤 job은 특정 CPU가 실행해야하는 경우가 있을 수 있다. 예를 들어 머리를 깎으러 갈때 디자이너가 여러명 있다면 들어가서 비어있는 디자이너 아무한테나 맡길 수 있지만, 나는 특정 디자이너에게만 머리를 맡긴다면 그 디자이너를 기다려야한다.

CPU가 여러개 있는데 특정 CPU에서 실행해야 하는 프로세스가 있다면 이걸 할당해놓고 Scheduling하던가의 방법이 있을 것이다.

Load sharing

CPU가 여러개 있으면 Load sharing이 잘 되어야 한다. 즉, 한 CPU만 일하고 다른 CPU들은 놀면 안된다.
일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요하다.

별개의 queue를 두는 방법(CPU마다 줄을 세우는 방법) vs 공동 queue를 사용하는 방법(한줄 서기를 사용)

Symmetric Multiprocessing (SMP)

각 프로세서가 각자 알아서 Scheduling 결정
symmetric: 모든 CPU가 대등

Asymmetric multiprocessing

asymmetric: CPU가 여러개 있는데 그 중 하나의 CPU가 전체적인 컨트롤을 담당
하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

Real-Time Scheduling

real time : 데드라인이 있는 것
따라서 반드시 dead line을 보장해야한다.

보통은 그때그때 Scheduling하기 보다는 미리 Scheduling해서 적재적소에 배치하는 방법을 사용한다. 미리 offline으로 Scheduling해놓거나, 대게 주기적으로 CPU를 써야한다는 조건이 있는 경우가 많기 때문에 이에 맞게 Scheduling하는 것이 중요하다.

Hard real-time systems

정해진 시간안에 무조건 Scheduling해야한다.

soft real-time computing

다른 프로세스에 비해 높은 우선순위만 갖도록 하고 dead line을 꼭 보장하지는 않는다.

Thread Scheduling

Local Scheduling

User level thread : 사용자가 직접 구현한 스레드 -> 운영체제는 모름
운영체제는 스레드를 모르기 때문에 그 프로세스에게 CPU를 줄지 안줄지를 결정
프로세스로 갔을 때 -> 어떤 스레드로 CPU가 갈지는 프로세스 내부에서 결정 => 따라서 운영체제가 하는 것이 아니고 사용자 프로그램이 직접 하는 것

Global Scheduling

Kernel level thread : 운영체제가 관리
운영체제가 스레드를 알고 있기 때문에 process Scheduling 하듯이 커널의 단기 Scheduler가 어떤 thread를 Schedule할지 결정

Algorithm Evaluation

어떤 알고리즘이 좋은지 평가할 수 있는 방법이 필요하다.

Queueing models

굉장히 이론적인 방법이다.

job들이 도착해(도착률 arrival rate) queue에서 대기한다. queueing model에서는 server라 표현하지만 우리는 CPU Scheduling이기 때문에 CPU라고 생각하면 된다. 도착한 프로세스들을 CPU 능력에 따라 처리하고 빠져나간 능력 (처리율인 service rate)있다.

확률분포로 주어지는 arrival rate와 service rate등을 통해 각종 performance index값을 계산한다. (처리량, 대기시간 등)

Implementation(구현) & Measurement(성능 측정)

실제 시스템에 알고리즘을 구현해 실제 작업(workload)에 대해 성능을 측정 비교

예를 들어 CPU 알고리즘을 새로 만들었다고 가정하면 이를 리눅스 커널 코드를 수정해 구현해서 원래 리눅스와 새로 만든 것을 비교해 얼마나 빨리 끝나는가를 측정

실측하는 방법이다. 이 방법은 특히 리눅스 커널, 운영체제 내부에 있는 것을 고치는 것은 어려운 일이다. 따라서 이러한 방법을 사용하긴 어렵다. 따라서 다음의 방법을 사용한다.

Simulation (모의 실험)

위에서 계속 살펴본 예제와 같이 arrival time, burst time을 주고 Gantt chart를 그려볼 수 있다. 하지만 간단한 예에서는 위와같이 손으로 그려보고 풀어볼 수 있지만 굉장히 복잡한 예제에서는 손으로 그려보는 건 너무 오래걸린다. 그래서 이걸 돌려보는 코드를 만들어 실행해보는게 simulation이다.

어떤 알고리즘이 좋고 나쁘고를 말함에 있어서 하나의 예제를 두고 주장하는 것은 적절하지 않다. 따라서 실제 사용되는 패턴들을 여러개 뽑아 simulation 해보는 것은 신빙성이 있을 것이다.

실제 프로그램을 통해 추출한 input data를 trace라고 부른다. trace를 임의로 만들수도 있고 실제 프로그램을 돌리면서 뽑을 수도 있다. 후자의 방법은 실제 상황을 더 잘 반영할 수 있을 것이다.

출처

Operating System Concepts 10th
KOCW 강의 - [운영체제] 이화여자대학교 반효경 교수