[운영체제(OS)] 6-2. CPU 스케줄링 (CPU scheduling)

CPU스케줄링에서 SJF알고리즘을 사용한 스케줄링을 하려면 process들의 cpu 사용시간을 알아야했다. 하지만 process들의 미래 cpu사용시간을 아는 것은 불가능하고 SJF 알고리즘을 사용하는데 문제가 생기게되었다. 따라서 SJF 알고리즘을 사용하기 위해서 사람들은 process들의 CPU 사용시간을 예측하는 수학적 모델을 만들었다.

Exponential Averaging 수학적 모델

 Exponential Averaging 모델 : 이전에 프로세스가 쓴 CPU 사용시간을 가지고, 미래 프로세스가 사용할 CPU 사용시간을 예측한다.

다음은 후에 나올 수식에서 사용되는 용어들을 정의한 것으로 밑의 그림과 같이 연관되어 보면 이해할 수 있다.

1.  n번째에 CPU를 사용한 실제 시간
2. n+1 번째의 CPU 사용시간을 예측한 값
3. 알파는 0과 1 사이의 값으로 가중치이다. 알파 값을 조정해 이전에 사용한 CPU 사용시간을 가지고 2번의 n+1 값을 예측한다.
4. 우리가 CPU 사용시간을 예측할 때 사용하는 수식이다.

4번의 수식에서 알파가 0일 때, n+1 예측값은 n의 예측값과 같다. 알파가 1이면 tn값만 남기 때문에 직전에 사용한 실제 CPU 값(n번째 사용 값)을 n+1 예측값으로 사용한다. 

출처 : https://kidhoarchive.tistory.com/25

4번의 식을 풀어서 쓰면 다음과 같이 풀어 쓸 수 있다. 알파와 1-알파는 1보다 작거나 같기 때문에 다음 그림의 항들은 뒤로 갈수록 값의 크기가 작아진다. (1보다 작은값들을 곱하기 때문에) 이 말은 뒤로 갈수록 과거 데이터의 가중치가 줄어들게 됩니다. (tn-1, tn-2...등등은 점점 더 작은 값을 곱해 n+1 값을 예측하기 때문에) 

---

Priority Scheduling

우선순위를 프로세스에 부여해 우선순위가 높은 프로세스에게 cpu를 먼저 부여하는 스케줄링이다.

 

이 스케줄링 또한 지금 실행중인 프로세스보다 우선순위가 높은 프로세스가 들어오면 CPU를 강제로 뺏는 Preemptive 방식과 CPU를 강제로 뺏지 않고 실행하는 Nonpreemptive 방식 두가지가 있다.

 

앞선 Shortest Job First Scheduling도 Priority Scheduling 방식이 될 수 있다. (여기서 priority는 다음 CPU 사용시간) 즉 priority의 기준을 뭐로 두느냐에 따라 Scheduling 방식이 달라질 수 있다.

 

문제점

priority가 낮은 프로세스들은 실행이 안되는 Starvation 문제가 발생할 수 있다. 

• Starvation이란 굶주림이라는 영어 뜻으로 여기서는 프로세들이 cpu 자원을 할당받지 못해 실행이 안되는 것을 말한다. 

 

해결책

프로세스가 기다리는 시간이 길어지면 priority를 올려준다. 이를 Aging 기법이라고 한다. 

• Aging이란 나이를 먹게한다는 뜻으로 여기선 priority를 올려주는 것을 의미한다.

---

Round Robin(RR)

Round Robin은 First Come First Served와 time quantum을 합쳐놓은 방식으로 각 프로세스가 최대 사용할 수 있는 CPU 시간을 정해놓고 프로세스를 교체해가며 실행하는 기술이다. multiprogramming을 지원하기 위해서는 RR방식을 사용해야한다. 

 

각 프로세스가 CPU를 받아 실행할 수 있는 시간(time quantum)을 가지고 프로세스에게 CPU를 준다. 이를 time quantum이라고 한다. 대부분 10-100millisecond 정도이다. 

이 시간이 지나면 프로세스는 할 일이 끝나지 않더라도 Ready queue로 들어가게 된다. 

만약 Ready queue에 n개의 프로세스가 있고 time quantum이 q초인 경우, 각 프로세스는 cpu를 할당받았을 떄, 한 번에 최대 q초만 cpu를 사용할 수 있다.

 

마지막 프로세스는 최대 (n-1)q 시간 동안만 기다리면 된다. 이 점이 큰 장점이다. 최대 얼마만큼만 기다리면 된다는 upper bound가 존재하기 때문에 계획적인 일을 할 수가 있다.

 

어떤 알고리즘에서 upper bound가 존재한다는 것은 좋은 알고리즘이라는 뜻이 될 수 있다.

Performance
만약 q값이 크면 FIFO 알고리즘이 된다. 즉 q값이 너무크면 프로세스가 끝날 때 까지 CPU를 안놓게 된다. 
만약 q값이 작으면 Context switch가 계속 발생해서 오버헤드가 엄청나게 커진다. 따라서 q가 너무 작으면 안된다. 

 

Round Robin 예제 

time quantum이 20일 때 실행은 다음과 같다. Ready queue에는 P1부터 P4가 차례로 들어와 있으며 time quantum이 끝나면 다음 프로세스로 넘어간다. 

 

출처 : https://www.programmersought.com/article/62533377993/ 

SJF 방식보다 평균적으로 turnaround time(처음 시작하고 끝날 떄 까지 걸리는 시간)은 더 길수도 있지만 응답시간(response time)은 Round Robin 방식이 더 짧다.

---

Multilevel Queue

잊고 있을지 모르겠지만 우리는 사용자랑 상호작용하는 프로세스(I/O bound job)에게 CPU를 먼저 할당해야한다.

 

Shortest Job First, Shortest Remaining First는 자연스럽게 I/O bound job에게 cpu를 먼저 할당한다. I/O bound job은 cpu 사용시간이 짧기 때문에 SJF는 자연스럽게 I/O bound job에게 cpu를 먼저 할당하게 된다. 

 

하지만 Round Robin은 I/O bound job에게 먼저 cpu를 할당하지 않는다. 그래서 나온것이 Multilevel Queue이다. 

 

Reday queue를 사용자와 상호작용하는 queue와 상호작용하지 않는 queue들로 분할해 놓는다. 

• foreground (사람들과 상호작용 하는 queue들)
• background (사람들과 상호작용하지 않는 queue들)

각 queue에는 자신만의 scheduling 알고리즘이 있다.

예를 들면

• foreground – RR알고리즘 사용
• background – FCFS알고리즘 사용

Scheduling은 큐 사이에서 수행되어야 합니다.

 

Fixed priority scheduling(고정 우선순위 스케줄링)

• foreground queue들에 존재하는 process가 모두 끝나면 background queue들의 프로세스를 실행한다.
• 하지만 이 scheduling은 starvation 문제가 발생할 수 있다.

Time slice(시간 배분)

foreground에만 cpu를 많이 할당하면 background에 존재하는 process들은 starvation 문제가 발생하기 때문에 시간배분을 해서 multilevel queue를 사용한다.

예를 들면 RR방식을 사용하는 foreground에 80%의 시간을, FCFS방식을 사용하는 background에 20%의 시간을 할당해서 사용한다. (foreground에 더 많은 시간을 할당해 사용자와 상호작용에 집중 할 수 있도록 한다)

 

다음 그림은 각각 queue라고 생각하면 되고 queue에 우선순위를 가지고 만들 수 있다. (foreground에 높은 운선순위를 부여)

출처 : https://coderworld109.blogspot.com/2018/01/operating-system-multilevel-queue.html

---

Multilevel Feedback Queue

Multilevel Feedback Queue는 Multilevel Queue의 형태이면서 프로세스가 queue간에 이동이 가능한 알고리즘이다. 

Multilevel Feedback Queue는 다음 다섯가지 조건을 정해야 만들어질 수 있다.

• queue의 개수
• 각각의 queue에 대해 scheduling 알고리즘이 필요하다.
• 프로세스가 더 높은 우선순위를 가지는 queue로 언제 이동할지 정해야 한다.
• 프로세스가 더 낮은 우선순위를 가지는 queue로 언제 이동할지 정해야 한다.
• 프로세스가 처음 시작될때, 어떤 queue에 먼저 들어가 실행될 것인지를 정해야한다.

---

Real-Time Scheduling(실시간 스케줄링)

실시간 스케줄링에 대해 자세히 다루진 않지만 보장된 시간내에 끝내기 위해서 복잡한 계산이 필요하며 두가지로 나뉘어진다.

 

Hard real-time system – 제한된 시간 내에 작업을 반드시 완료해야한다. deadline이 존재하며 복잡한 연산을 해서 cpu를 할당해야한다. ex) 날아오는 미사일을 요격하기 하는 것은 시간이 매우 중요하다. 복잡한 연산을 통해 미사일의 방향과 고도를 예측시켜 요격시켜야 한다.

Soft real-time computing – 우선순위가 높은 프로세스가 더 많이 scheduling이 필요하다. ex)동영상 : 끊기지 않도록 우선순위를 두고 실행시킴.