[운영체제] 프로세스 스케쥴링(Process Scheduling)

Multi-tasking

"그건 제 잔상입니다만..?"    -  CPU

'멀티테스킹'이라 하면 '동시에 일을 처리한다.'는 뜻으로 모두 알고 있을 것이다.

컴퓨터, 스마트폰 등 전자기기의 CPU에게 쓰이는 '멀티테스킹'이란 단어는 엄밀히 말하면 동시에 일을 처리하는 것은 아니다.

CPU는 동시에 한가지 프로세스(CPU의 일의 단위)밖에 처리할 수 없다. 하지만, 여러 프로세스가 밀려있는데 한 가지 프로세스가 끝날 때까지 그것만 한다면, 유저 입장에서는 매우 답답하다고 느낄 것이다. 동영상을 켰더니, 동영상을 로드하느라 마우스를 움직이거나 키보드를 치는 행동을 뒤로 미룬다면, 마우스, 키보드 인풋은 동영상이 끝나고나서야 작동할 것이다.

'멀티테스킹'은 CPU가 한 순간에 한가지 일만 처리하 되, 아주 짧은 텀을 가지고 처리하는 일을 계속 바꿔가면서 모든 일을 '동시에 처리하는 것처럼 보이게 하는 것'을 말한다. 물론 오래전부터 듀얼코어, 쿼드코어, 옥타코어 등 멀티 코어 PC가 나오면서 CPU가 여러개 달려서 동시에 처리할 수는 있지만, CPU가 동시에 처리해야 하는 프로세스의 수는 셀 수 없이 많기 때문에 여전히 '진정한 멀티테스킹'은 이루어지지 않고 있다고 할 수 있다.

 

결론 : 멀티테스킹은 빠른 텀을 두고 프로세스를 바꿔가며 수행하여 동시에 처리하는 것처럼 보이는 것이다.

---

Process Scheduling

그렇다면, 어떻게 해야 가장 효율적으로 프로세스를 처리할 수 있을까?

컴퓨터가 해야할 일은 셀 수 없이 많고, 프로세스 마다 중요도와, UX에 끼치는 영향의 크기는 천차만별이다. 그렇다면 어떤 프로세스를 먼저 처리할 지 시간표를 짜는 일은 굉장히 중요할 것이다.

 

1. First Come First Served (FCFS)

• 어떤 일이 있어도 먼저 Ready State에 도달한 프로세스를 먼저 처리하는 것
• 가장 Fair하고 단순하지만, 자주 사용하거나 중요한 프로세스에 대한 배려가 필요
• 그래서 프로세스에 priority가 등장

2. Priority Scheduling

• 항상 높은 priority를 가진 프로세스를 먼저 수행하는 것
  • High Priority: 키보드 키입력 읽기, 마우스 움직임 읽기
  • Mid Priority: Focus가 맞춰진 윈도우
  • Low Priority: Focus가 없는 윈도우, Network Message 체크 등
• 이렇게 수행 할 경우 High Priority 프로세스가 계속 들어오면 상대적으로 priority가 낮은 프로세스는 계속 뒤로 밀리면서 영원히 수행되지 않을 수 있는데, 이것을 Starvation이라고 부른다.
• 이 Starvation을 해결하기 위해서 Aging이라는 것이 생겼다. 말 그대로 나이를 매기는 것으로, 해당 프로세스가 뒤로 밀려서 얼마나 기다렸는지를 체크하는 것이다.
• Starvation이 길게 지속된 프로세스는 PCB에 저장된 본인의 priority가 높아지며 선택될 수 있다.

3. Real-Time Scheduling or Guaranteed Scheduling

• 모든 Real-Time 프로세스는 최대 대기 시간(Maximum Waiting Time)을 가진다.
• 해당 프로세스의 Age가 최대 대기시간을 초과하면 해당 프로세스가 선택되어 수행된다.

4. Shortest Remaining Time First (SRTF)

• 해당 프로세스를 수행하는데 걸리는 시간이 짧은 순으로 프로세스를 수행하는 것
• 따라서 프로세스를 수행하는데 걸리는 시간을 계산해야함
• 계산된 프로세스 수행 시간 = (과거까지 계산된 수행시간 + 직전 수행시간) / 2
• 최초 수행 시 계산된 프로세스 수행시간을 0으로 한다
  • 예를 들어 어떤 프로세스를 수행하는데 걸리는 시간을 1초라고하면, 최초에 예상을 0초라고 하고, 다음 프로세스를 수행했을 때 1초가 걸리면 계산된 프로세스 수행시간이 (0 + 1) /2 = 0.5초가 된다.
  • 그다음 수행 시 계산된 프로세스 수행시간은 (0.5 + 1) / 2 = 0.75초가 된다.
  • 계속 수행하다보면 계산된 프로세스 수행시간은 실제 수행시간에 수렴하게 되면서 근접한 수행시간을 얻을 수 있다
• SRTF를 사용하면 빠른 프로세스들이 먼저 빠르게 수행되면서 대부분의 프로세스들이 기다리는 시간이 줄어든다
• 하지만 느린 프로세스들은 starvation을 겪게 된다
• 추가) SRTF엔 이미 들어온 프로세스는 일단 끝까지 수행하는 Non-preemitive한 버전의 SJF(Shortest-Job-First)가 있고, 수행중이어도, 더 짧은 프로세스가 들어오면 context switch로 전환하는 preemitive한 버전의 SRTF가 있다.
  • preemitive에 관한 내용은 6번 round-robin에서 확인

5. Higher Response Ratio Next (HRRN)

• SRTF 와 Aging을 합친 process scheduling
• 계산된 수행시간은 SRTF와 같게 계산한다
• 이를 바탕으로 age와 함께 priority를 결정한다
• priority = (age + 계산된 수행시간)/계산된 수행시간
• 즉 모든 프로세스가 priority가 1에서 시작하여, age가 증가하면서 priority가 증가한다.
• 계산된 수행시간이 크면 클수록 priority가 느리게 증가하고, 짧으면 priority가 빠르게 증가하여, 수행시간이 짧을 수록 먼저 수행하게되긴 하지만, 수행시간이 긴 프로세스도 결국 priority가 오르므로 starvation을 겪지 않는다.

 

6. Round-Robin (순환 할당 스케쥴링)

• FCFS + Preemptive한 스케쥴링이다
  • Preemptive(선점): 어떠한 조건이 발동되었을 때, 수행하던 프로세스를 멈추고 다른 프로세스를 수행할 수도 있는 scheduling algorithm
  • 특정한 조건에는 프로세스에게 CPU 사용 할당 시간을 초과했거나, 인터럽트가 발생했거나, 더 높은 priority의 프로세스가 들어왔을 때 등을 뜻한다.
• time quantum이라고 불리는 단위시간을 설정하고, 먼저 ready state가 된 프로세스를 단위시간 만큼 수행한다.
• time quantum동안 프로세스가 전부 실행되지 않았더라도, 해당 프로세스 진행과정을 저장한 후 waiting queue의 맨 뒤로 보낸 후 다음 ready state프로세스를 수행한다.
• 이런식으로 계속 순환시켜가며 돌아가면서 프로세스를 수행한다. 
• time quantum이 너무 작으면 waiting time이 줄어들겠지만, context switching에 소모되는 시간이 증가한다
• time quantum이 너무 크면 FCFS와 다를 바가 없다.
• 따라서 time quantum은 CPU Burst의 80% 정도를 포함할 수 있도록 설정하라고 되어 있다.

 

7. Multi-Level Queues

• priority에 따라서 그룹을 나눠서 프로세스를 분류한다.
• 가장 높은 priority 그룹이 다 수행되어야 그다음 priority를 가진 그룹의 프로세스를 수행할 수 있다.
• 낮은 priority 그룹의 프로세스를 수행하다가 상대적으로 높은 priority 그룹의 프로세스가 들어오면 context switching을 통해서 해당 프로세스를 먼저 수행해야 한다.

 

결론 : 프로세스 스케쥴링을 통해서 프로세스의 우선순위를 정하며, 프로세스 스케쥴링엔 다양한 종류가 있다.

 

---

프로세스 스케쥴링의 효율성 검증

어떤 process scheduling의 효율성이 가장 큰지는 어떻게 판단할까?

 

위에서 보았듯이 process scheduling에는 다양한 종류의 알고리즘이 존재한다. 이 알고리즘 중 어떤 것이 가장 효율적인지를 파악해야 골라서 사용할 수 있다.

알고리즘의 효율성을 파악할 수 있는 지표들엔 여러가지가 있다.

 

1. Throughput

• 1시간동안 몇개의 프로세스를 수행할 수 있는가?

2. Average Turnaround Time

• 프로세스를 시작하여서 끝날때까지 걸린 시간의 평균

3. Average Response Time

• cpu가 프로세스들을 수행하기 시작한 최초 시간(start time)에서 프로세스가 선택되어 수행되기 까지(arrival time)의 평균
• 즉 각 프로세스들이 수행되기 시작하는데까지 걸린 시간의 평균

4. CPU Utilization

• 프로세스를 수행할 때 걸린 시간 중, Context Switching으로 낭비된 시간을 제외하고 실제로 프로세스를 수행하는 명령을 수행하는데 소모된 시간의 비율

5. Average Waiting Time

• 프로세스가 Waiting Queue에 도달하여 수행되기까지 걸린 시간의 평균
• 3번의 Average Response Time과 비슷해 보이지만, 3번의 시작점은 CPU가 작업을 최초로 시작한 지점이고, 이 경우는 process가 queue에 들어서서 기다리기 시작한 시간부터이다. 프로세스별로 waiting queue에 도달한 시간이 각각 다르기 때문에 이 지표도 굉장히 중요하다.

5번 지표인 Average Waiting Time과 프로세스 별 실질 수행시간을 가지고 비교했을 때 SRTF가 가장 효과적인 것으로 나타난다. 하지만 실제 수행시간은 우리가 알 수 없고, 계산된 수행시간만 가지고 스케쥴링을 할 수 밖에 없다.

따라서 HRRN 방식이 실제 상황에서는 SRTF보다 나을 수 있다.

 

결론: 각 process scheduling 기법은 장단점이 있지만, 기준을 통해서 파악하면, 이상적인 것은 SRTF, 현실적으로 가장 효과적인 것은 HRRN이다.