[OS / 운영 체제] Priority Scheduling, Round Robin Scheduling, Multilevel Queue Scheduling, Multilevel FeedBack-Queue Scheduling, Multi Processor Scheduling, Processor Affinity

 

Priority Scheduling

프로세스 별 우선순위가 다 다르다. System call의 우선순위를 높게 줘야 한다. 우선순위 높은 것 먼저 실행하자는 알고리즘이다. P1 - P5까지 있고 Burst Time이 있다. Burst Time은 CPU 의 하나의 길이를 의미한다. 그리고 각 프로세스 별 우선순위가 주어져 있다. Priority 번호가 낮을 수록 우선순위가 높은 것이다. 1번이 가장 높은 것이고 5번이 가장 우선순위가 낮은 것이다. 동시에 프로세스가 들어오면 P2가 제일 먼저 실행된다. (번호가 낮은 우선순위가 높은 것이 먼저 실행됨). 1ms 만큼 돌게 되고 그 다음으로 P5가 5ms 만큼 돌게 된다. 이렇게 돌아가게 된다. 

 

 

Prority Scheduling

External 외부에서 주는 경우.

어느 정도 우선순위가 된다고 지정을 해버리는 경우이다.

Internal 에서 주는 경우

External에서 우선순위를 부여하더라도 내부에서 상대적으로 조정할 수 있는 경우가 있다. 

IO Bound Process의 우선순위가 더 높게 측정된다. Vi와 Compiler를 사용하는 경우. Vi가 딜레이가 걸린다. IO Bound Process가 우선순위가 높아야 한다. 왜나하면 User하고 Interact하는 Process이기 때문이다. 사용자를 위해 우선순위를 높여줘야 한다. Compiler가 2초 걸릴 것을 3초 걸렸다고 하더라도 사용자가 체감할 수 없기 때문에 IO Bound Process의 우선순위를 높게 해야 한다. 
IO Bound Process는 Time quantum을 다 사용하지 않는다. 나한테 주어진 Time quantum을 다 사용하면 CPU Bound Process일 확률이 높다. (*****) 이런 경우 Internal 하게 우선순위를 높여주는 것이다. 

중간에 Interceptive를 받을 수 있으면 Preemtive이고 받을 수 없으면 Nonpreemtive라고 표현을 한다. Waiting Queue에서 들어온 것이 우선순위가 더 높은 경우 CPU Scheduling을 한다면 Preemtive Schedule이다. 우선순위가 낮은 프로세스는 시간을 할당받지 못해서 굶어죽을 수 도 있다. 하지만 기다릴 때마다 우선순위를 높여줘서 실행을 할 수 있도록 만들어주는 방법을 Aging이라고 한다. 

 

 

Round Robin Scheduling

화살표의 길이를 Time slice, Time Quantum이라고 부른다. 일정시간이 지나면 강제로 Switching을 해버리는 알고리즘을 의미한다. FCFS의 preemtive한 방식을 Round Robin 이라고 말한다. 

 

 

Round Robin Scheduling

Time quantum = 4인 경우 P1이 돌때 4ms 만큼 돌고 P2로 돌아간다.

 

 

Round Robin Scheduling

Time quantum을 12로 잡으면 Context Switching이 게 된다. 1로 잡게 되면 무려 9번이나 바꾸면 1ms마다 Switching하게 된다. 하지만 Switching을 많이 할 수록 CPU를 많이 잡아먹게 된다. Time quantum에 따라서 Behavior가 달라진다. Time quantum이 아주 길어지면 FCFS처럼 동작하게 된다. 작아도 안좋고 커도 좋지 않다. 

 

 

Round Robin Scheduling

Turnaround

80%이라는 것은 대부분의 프로세스를 커버할 수 있는 것을 의미한다. IO Bound Process

 

 

Multilevel Queue Scheduling

우선순위를 확실하게 지켜주기 위해서 Queue를 여러 개 사용한다. 각 Queue에서 후보가 하나씩 나오게 된다. 각각 나온 대표 Queue 중 누구를 넣을지를 결정해야 한다.

 

 

Multilevel Queue Scheduling

최종적으로 누구를 택할 것인가. 우선순위가 가장 높은 것을 선택하는 것이 첫 번째 방법이다. 그 방식이 Fixed Priority Preemtive schduling이라고 한다. 만약 Queue가 2개밖에 없다고 가정해보자. foreground의 우선순위가 background queue보다 높다. 이렇게 만들면 자기보다 위쪽에 Process가 있어도 20%라는 공간이 있으므로 우선순위가 낮은 Process도 처리할 수 있게 된다. 

 

 

Multilevel FeedBack-Queue Scheduling

CPU Bound Process는 Interactive 하지 않다. 

 

 

Multilevel FeedBack-Queue Scheduling

굉장히 많은 알고리즘 디자인이 존재한다. 아래로 내려오는 화살표가 있다는 것은 FeedBack Queue임을 의미한다. Process의 시작은 가장 우선순위가 높은 것부터 시작을 한다. Time quantum 이 짧다는 것은 IO Bound Process이고 Interactive한 Process라는 것이다. 8+24 ms 보다 큰 경우 나갔다가 다시 8ms로 돌아오게 된다. Burst가 길다는 것은 CPU Bound Process라는 것이고 우선순위를 낮춰도 좋다라는 것이다. 

 

 

Multiple process scheduling

프로세스가 많으면 scheduling 입장에서 복잡해진다.

 

 

Symmetric vs Asymmetric 

Symmetric과 Asymmetric을 나누는 경계는 Master Slave 관계를 가지는 지의 유무이다. 이 관계가 있다면 Asymmetric이고 동일하다면 Symmetric이라고 한다. 

 

 

Multi Processor Scheduling

요즘 운영체제는 여러 개의 CPU를 두고 CPU 마다 Ready Queue를 가지고 있도록 설계를 한다.

 

 

Processor Affinity

어떤 프로그램을 실행시켰는데 2번 CPU에서 돌고 있다. Time quantum을 돌고 다시 돌아왔다. 기존에 2번에 돌고 있는 CPU가 있는데 2번을 유지하는 것이 좋을 까 1,3번으로 보내는 것이 좋을까? 유지하는 것이 더 좋다. "누가 하던 일이 있는데 전에 하던 사람한테 주는 것이 좋다. 왜냐하면 이전에 기억하고 있던 뭔가가 있으니까!!" 기억하고 있는 것은 Cache Contents이다. 메모리와 CPU의 속도차이를 해결해주는 메커니즘인데 이를 보완해준다. 2번 CPU Cache에 관련 내용이 이미 들어가 있으므로 원래 돌던 친구한테 주는 것이 더 좋다는 것이 Affinity라고 부른다. 

1. Soft Affinity

같은 프로세스에서 돌게 만들려고 하지만 이동하는 것이 더 낫다라고 한다.

2. Hard Affinity

무조건 돌던 프로세스에서 도는 것이 좋다. 

 

 

Processor Affinity

NUMA, CPU마다 각각 로컬 Memory가 존재한다. 한 CPU에서 잘 돌던 Process를 다른 CPU로 옮기게 되면 작업이 굉장히 느려진다. 

 

 

Load Balancing

바쁜 데 있었던 프로세스를 다른 쪽으로 이동시키는 것은 Load Balancing이라고 한다. 다들 공평하게 CPU Time을 받았으면 좋겟다는 것이다. Push가 있고 Pull이 있다. 널널한 프로세스를 밀어주는 것을 Push migration이라고 한다. Pull migration은 좀 더 자발적인 것이다. 양심이 있는 CPU라면 나는 한가하니 나한테 달라는 것이 Pull migration이다. 두 가지를 같이 사용할 수 도 있다.