[운영체제] Process Scheduling 방법 정리(2) - Priority, PIP, PCP

Scheduling!

 

 바로 1달만에 돌아온 Process Scheduling의 방법을 정리해보는 블로그이다. 지난 Process Scheduling 방법으로는 FCFS, SJF, STCF, RR Scheduling에 대해서 정리하는 포스팅을 진행했었다.

 

 사실 지난번에 모든 내용을 정리해도 됐었는데, 한 번 끊은 이유는 이번에 정리할 Priority Scheduling을 한 호흡에 정리하기에는 너무나 내용이 많았기 때문이다. 그래서 따로 빼서 스핀오프 형태로 다루고자 한 것이다. 그럼 바로 시작해보자!

 

---

1. Naive Priority Scheduling 

What is Priority Scheduling?

• 각 프로세스에는 우선 순위(Priority)가 존재한다.
• CPU는 프로세스의 우선 순위에 따라 차례대로 scheduling 한다.
  • 이는 preemptive(선점형)일 수도 있고, non-preemptive(비선점형)일 수도 있다.

 

Priority Scheduling 방법은 다른 어떤 Scheduling 방법보다 "가장 이해타산적인" 알고리즘이다. 객관적인 지표인 우선 순위를 통해 Scheduling을 진행하는 간단한 방법이다.

 

이전 포스팅과 마찬가지로 예를 들어 설명해보겠다. 모종의 과정에 의해 개개인마다 우선순위가 정해진 단체 예약 손님이 식사를 하러 왔다. 사람마다 도착하는 순서에는 차이가 있을 수 있겠지만, 우선 순위를 기준으로 식사를 진행한다.

 

위에서 언급했듯이, 이러한 scheduling 방법은 preemptive할 수도 있고, non-preemptive할 수도 있다. 이 말인 즉슨, 다음과 같은 상황에 어울린다.

 

우선순위는 숫자가 클수록 낮아진다고 하자.식당이 점심시간에 문을 열자마자 우선순위가 10인 사람이 들어와서 식사를 시작한다.

 

그러다, 이 사람이 식사를 하던 중에 우선순위가 1인 사람이 들어와서 식사를 하고자 할 수도 있다. 이때, 우선순위가 낮은 손님의 자리를 빼앗고 자리에 앉아 식자를 하기 시작하면 preemptive, 자리를 빼앗지 않고 기다렸다가 1보다 우선순위가 높은 손님이 식사를 마쳤을 때 식사를 시작하면 non-preemptive 방식이 되는 것이다.

 

이는 식당 주인(설계자)의 취향 차이이다.

 

이를 컴퓨터의 상황으로 가져와서 생각해보자.

 

 

프로그램에서 돌아가는 프로세스의 구조를 설계할 때 Priority를 담당하는 필드를 따로 설정해 둔다. 그리고 스케줄러는 Priority에 따라서 프로세스 순서대로 처리한다.

 

위의 예시에 따르면, 한 번에 5개의 프로세스가 들어온다. 그 후에는 5개의 프로세스 중, 가장 우선 순위가 높은 2번 프로세스부터 스케줄링되어 실행되는 것이다.

 

그런데 이 Priority Scheduling 방식에는 다음의 두 가지 문제가 존재한다.

 

What is the problem with Priority Scheduling?

1. Priority Scheduling에서의 Starvation 문제

위 예시처럼, 한 번에 5개의 프로세스만 들어오고 이후에 들어오지 않을 수도 있지만, 대부분의 환경에서는 끊임없이 실행되어야 프로세스가 들어올 것이다. 이때, 우선순위가 높은 프로세스가 지속적으로 들어온다면, 우선순위가 낮은 프로세스는 실행되지 않아 starvation이 발생할 것이다.

 

2. Priority Scheduling에서의 우선순위역전(Priority Inversion) 문제

: 해당 문제를 이해하기 전에 리소스(resource), 소유(acquire), 해제(release), 잠금(lock)의 개념을 이해해야 한다.

• 리소스(Resource) : 프로세스가 알고리즘에 따라 작업을 처리할 때 처리하고자 하는 대상이다.
• 소유(Acquire) : 프로세스가 처리하고자 하는 리소스를 가져오는 작업이다.
• 해제(Release) : 프로세스가 리소스를 모두 처리하고, 잡고 있는 리소스를 놓는 것이다.
• 잠금(Lock) : 프로세스가 리소스를 처리할 때, 다른 프로세스에서 접근하지 못하도록 막는 것이다. 

통일성을 위해 모두 영어로 표기하도록 하겠다. 다음과 같은 상황을 가정해보자.

 

prio가 1인 프로세스 A, 5인 프로세스 B, 10인 프로세스 C가 존재한다고 가정하자.

 

먼저, C가 작업을 수행하기 위해 CPU에 스케줄링되고, resource를 사용하기 시작, lock이 걸린다. 따라서 다른 프로세스들은 들어와도 C가 처리중인 resource에 접근할 수 없다.

 

그러던 중, resource의 처리를 위해서 프로세스 A가 들어오게 된다. 하지만, C에서 resource를 사용하기 위해 lock을 걸어놨기에 A는 우선순위가 높음에도 불구하고 스케줄링되지 못한다.

 

그 사이에 B가 들어왔고, B는 C가 Acquire하여 처리중인 resource를 처리하지 않아도 되기 때문에 C보다 우선순위가 높기 때문에 B가 먼저 처리되고 C가 처리되게 되는 것이다. 그리고 A는 가장 마지막에 처리될 것이다.

 

이 현상이 바로 우선순위역전 현상이다. 가장 먼저 처리 되었어야 할 A가 가장 나중에, 가장 낮은 우선순위를 가진 것처럼 사용되는 것이다.

 

How to solve Starvation Problem?

: 위의 문제들을 해결하기 위해서 아래의 방법들이 대책으로 사용된다.

• Aging을 활용하는 방법(Priority Scheduling with Aging)
• Priority boosting을 활용하는 방법(Priority Inheritance Protocol, Priority Ceiling Protocol)

 

---

2. PA - Priority Scheduling with Aging

What is PA?

: Priority scheduling 알고리즘에서 Aging을 활용하는 방법은 1에서 설명한 Naive Priority Scehduling에 Round-Robin 방식을 도입하는 것이다.   

간단하게 말해서, 프로그램 동작에 있어서 특정한 단위 시간(burst time)이 지나면, 현재 진행중이지 않은 우선순위가 낮은 프로세스들의 prio 값을 높여주는 방법이다.

 

일반적으로 Aging을 활용하여 Priority Scheduling을 구현하는 것에 단위 시간은 1 tick이 소요되도록 설정하며, Priority Scheduling 방식의 구현에 기반하기에 구현하는 데에 크게 어려운 점은 없다.

 

---

3. PIP - Priority Inheritance Protocol

: Priority Scheduling의 자식(?) 급으로 많은 Scheduling 방식이 등장하고 있는데, 그나마 좋은 점은 이름에서 대부분 그 구현 방식이 유추된다는 점이다.

PIP는 Priority, 우선순위를 Inheritance, 다른 프로세스가 상속받는다는 뜻이다.

 

정확한 의미는, 복수의 프로세스가 처리해야만 하는 resource를 공유하고 있는 프로세스가 scheduling 되었을 때, 우선순위가 낮은 프로세스라도 이미 resource를 acquire해서 lock을 걸어 둔 상태라고 하면, 우선순위가 낮은 프로세스는 같은 resource의 처리를 위해 scheduling된 프로세스 중 가장 높은 우선순위를 상속받아 사용한다는 의미이다. 

 

자, 식당을 예로 들어 보자면, 중국집에서 "쟁반짜장을 모두 먹는 것"이라는 resource가 존재한다고 생각해보자.

식당이 영업을 시작하자마자, 가장 우선순위가 낮은 손님 C가 들어와서 쟁반짜장을 먹기 시작(acquire)했다면, 우선순위가 높은 손님 A가 마찬가지로 쟁반짜장을 먹으려 할 경우, 손님 C는 A의 높은 우선순위가 적인 번호표를 빼앗아 손에 쥐고 마저 먹는다는 것이다.

 

그러면 손님 B가 들어와서 짬뽕을 시켜먹으려고 해도, 이미 가장 높은 우선순위인 C 손님이 쟁반짜장을 먹고 있기 때문에 B는 A와 함께 대기하게 될 것이다.

 

이렇게 되면, 손님 A는 약간 어이없을 수는 있지만, 우선순위가 높음에도 resource 처리를 하지 못하는 어이없음은 면할 수 있다.

 

---

4. PCP - Priority Ceiling Protocol

: PCP는 우선순위를 Ceiling, 엄청 높여서 처리한다는 것이다.

 

또한 정확한 의미는, 복수의 프로세스가 처리해야만 하는 resource를 scheduling 받은 프로세스가 존재하는 그 시점부터 해당 프로세스의 우선순위를 Ceiling, 엄청나게 높여주는 방식이다.

 

또 다시 식당을 예로 들어보면, 손님 C가 들어와서 쟁반짜장을 먹기 시작(acquire) 했다면, 중국집 사장님이 나와서 '무적 우선순위권'을 손에 쥐어주는 것이다. 그러면 손님 A, B는 중국집에 들어왔을 때 C가 들고 있는 무적 우선순위권을 보고 납득하며 아무 말 없이 밖에서만 보고 있을 것이다.

 

다만, 이는 현실에서 그렇다는 것이지, 실제 컴퓨터에서 구현이 어려운 점이, 프로세스 상에서 prio 값이 어떨 때 가장 클 수 있을지에 대한 고민이 필요하다는 것이다. 굉장히 단순하면서도 까다로운 구현일 수 있을 것 같다.

 

---

이번 포스팅에서는 Priority Scheduling의 여러 방식을 리뷰해보았다. 사실 1번 빼고는 즉석해서 예시를 생각해서 킥킥대며 썼던 블로그 포스팅이라, 터무니 없는 예시는 아니지만 좀 근본 없는 것 같아서 우려되기도 한다. 

 

다음 포스팅에서부터는 메모리에 대해서 다뤄볼 생각이다.

 

이 글이 많은 사람들에게 도움이 되었으면 좋겠다.