[운영체제] Process Scheduling 방법 정리 (1) - FCFS, SJF, STCF, RR

Scheduling!

 오랜만에 다시 블로그 포스팅을 적어보려고 한다. 그동안 BoB도 했었고, 바로 논문까지 써버리느라 정신없었는데 운영체제 시험을 대폭망급으로 망해버려서 운영체제부터 다시 공부를 시작해야할 것 같다...ㅎㅎ

 

 그럼 이미 내가 정리해놨던 내용인 Process Scheduling 방법부터 차근차근 정리해보도록 하겠다. 여러 블로그의 좋은 포스팅들이 많지만, 우리 학교 김교수님께서 해주시는 강의가 정말 깔끔하고도 심오하기 때문에 따로 나와 김교수님의 언어로 적어보려고 한다.

 

---

1. FCFS(OR FIFO) - First-Come First-Served Scheduling

What is FCFS(FIFO)?

: FIFO(First in First out)이라고도 불리는 알고리즘이다.

• 도착하는 순서대로 작업을 처리하는 알고리즘
• Real World에서 사람들이 줄을 설 때 사용하는 일반적인 Scheduling 방법
• 일반적으로 non-preemptive(비선점형, 되도록이면 영어 표현을 기억하도록 하자)
• starvation이 발생하지 않음

대부분 운영체제의 알고리즘을 배울 때 FCFS(FIFO)를 가장 먼저 다루는 이유는 다른 알고리즘들에 비해서 가장 Fair하기 때문이다.

이름에서도 유추할 수 있듯, 처음 오는 작업을 먼저 처리하고, 다음 작업을 처리하는 단순한 알고리즘이라고 이해하면 된다.

 

출처:뉴스1

우리 교수님께서는 모든 스케줄링 알고리즘의 예시를 ‘기숙사식당’으로 들어 설명하셨다.

간단하게 예시를 들자면, 우리 학교 식당은 뷔페식으로 되어있다. 하지만, 자리가 한 자리씩밖에 없다고 생각해보자.

한 명씩 밥을 먹고자 하는데, 온 순서대로 밥을 먹고 나가는 형태라고 생각하면 이해하기 쉽다.

가장 단순하면서도, 가장 공평한 방법이 바로 FCFS(FIFO)일 것이다.

이를 어떻게 구현하면 좋을까?

Implementation of FCFS(FIFO)

1. readyqueue에 도착한 순서에 따라 프로세서에 프로세스를 하나씩 할당한다.
2. 프로세서가 모두 가득 차면, 처리가 종료될 때까지 기다린다.
3. 더 이상 처리할 프로세스가 없으면, 프로그램을 종료한다.

여기까지는 간단해서 더 좋다!

하지만, 약간만 생각을 비틀어보면 바로 문제점이 보인다.

Problems of FCFS(FIFO)

앞에서 생각한 예시의 하나의 상황을 가정해보도록 하자.

예를 들어 기숙사 식당에 들어가는데, 처음 온 사람이 엄청나게 많은 음식을 밥알 한 톨 한 톨 음미하면서 먹고 있다면, 밥을 먹는 시간이 당연하게 길어질 것이다.

그러면, 줄을 기다리는 사람의 시간 또한 길어질 것이고, 이 사람들은 지치고, 식당의 앞은 사람들로 엄청나게 붐빌 것이다.

컴퓨터도 마찬가지이다. 똑같이 컴퓨터의 상황으로 가져와보자.

 

 

수명이 굉장히 긴 프로세스가 가장 먼저 처리되는 시점에서는 뒤이어 처리되어야 할 프로세스는 프로세서 대기줄에서 끊임없이 기다릴 것이고, 이는 과부하를 일으킨다.

이 때의 기다리는 시간을 waiting time이라고 하고, waiting time이 엄청나게 길어지는 현상 자체를 convey effect 라고 한다.

How to resolve Convey effect?

어떻게 하면 위와 같은 문제를 해결할 수 있을까?

가장 빠르게, 누구나 생각할 수 있는 방법은 들어오는 프로세스 중, 처리 시간이 가장 짧은 것을 먼저 처리하고 긴 것을 나중에 처리하는 방법을 떠올릴 수 있을 것이다.

 

---

 

2. SJF - Shortest Job First Scheduling

What is SJF(Shortest Job First)?

• CPU 사용량이 가장 작을 것으로 예상되는 작업을 선정
• waiting time의 최소 평균을 보장
• Non-preemptive
• Priority scheduling 방식

식당의 회전율을 가장 단순하면서도 확실하게 올리려면 어떻게 하면 좋을까?

 

 

밥을 빨리 먹는 사람을 가장 먼저 배치하고, 천천히 먹는 사람을 뒤로 배치한다면, 테이블 회전율이 빨리 올라가서 전체 소요 시간은 FCFS 방법과 같겠지만, 적어도 손님들이 가만히 서있는 시간을 최소화할 수 는 있을 것이다.

하지만 이 역시나, 문제점이 존재한다.

Problems of SJF

위의 예시에서는 밥을 빨리 먹는 사람과 그렇지 않은 사람을 판단하여 빨리 먹는 사람을 앞에 배치한다고 했었는데, 문제는 ‘그것을 관리자가 어떻게 알아내는가?’ 하는 것이다.

우리는 사람의 얼굴만 보고 관상으로 왕이 될 상은 알아볼 수는 있어도, 밥을 빨리 먹고 말고는 알아내기 힘들 것이다.

컴퓨터도 마찬가지이다.

컴퓨터의 프로세서는 프로세스만 보고 이 프로세스가 미래에 CPU 사용량을 얼마나 가져가도록 변화할 지 예측하기 어렵다. 따라서 옛 컴퓨터에서는 이 방법이 해결책이 될 수 있을지는 몰라도, 현재의 컴퓨터 운영체제까지 이 scheduling 방법이 이어져 오지 않은 것이다.

이 외에도 starvation이 발생할 수 있다는 문제점이 있다.

What is starvation?

사실 FCFS때도 살짝 언급한 이력이 있지만, 여기서 설명하기 위해서 빼놓았다.

Starvation을 구글에 검색해보면, 뼈만 앙상하게 남은 어린이 사진이 보인다. 말 그대로 starvation은 굶주림이다.

OS에서도 비슷한 느낌으로 가져가보면 될 것 같다.

운영체제가 이해하는 starvation이라는 개념은, 프로세스가 ‘어떠한’ 이유로 인해서 처리되지 못하고 계속해서 대기하는 상태를 의미한다.

위에서 제시한 예를 가져와서 설명해보면, P1은 식당에 가장 먼저 도착했지만, 단순히 밥을 천천히 먹는 이유로 맨 마지막 순서까지 식사 순서를 기다린다.

그러면 P1의 상태는 어떨까? 배고프다.(starvation) 우선은 이런 개념으로 이해하면 될 것 같다.

전문적인 용어를 사용하면 아래와 같다.

 

• A situation where a job is prevented from making progress because another jobs keep holding a resource it requires
  • 여기서 리소스는 CPU 혹은 lock이 될 수 있다.
• : 다른 작업이 필요한 리소스를 계속 보유하고 있어 어떠한 작업이 처리되지 못하게 막고있는 상황
• A poor scheduling policy can cause starvation
  • 잘못 짜여진 scheduling 정책은 starvation을 발생시킬 수 있다.
  • 우선 순위가 낮은 작업은 높은 우선 순위의 작업이 들어오면 영원히 처리되지 않을 수도 있다.

 

---

 

3. STCF - Shortest Time-to-Complete First Scheduling

Why STCF?

SJF는 프로세스의 수명을 예상하기 어렵다는 문제점이 존재한다.

컴퓨터 운영체제를 연구하는 사람들도 이러한 문제점 때문에 이를 대체하는 scheduling 방식을 고안하였다.

What is STCF?

• SJF의 preemptive한 형태(선점형)
• 실행 시간이 현재 작업의 남은 시간보다 짧은 새 작업이 도착하는 경우 미리 준비

 

 

STCF를 정의하는 데에서는 FIFO(FCFS), SJF에서의 하나의 가정을 제거한다.

바로, “작업이 시작되면 끝날 때까지 다른 작업을 실행하지 않는다.” 이다.

또한, scheduler에 time interrupt와 context switch 기능을 추가하여 구현한다.

 

STCF 또한 교수님께서 예를 들어주신 것으로 생각해보면 이렇다고 생각하면 된다.

SJF scheduling 방식으로 손님을 받는다면, 한 번 빨리 먹고 나간다는 사람이 들어오면 그 사람이 다 먹을 때까지 다른 손님이 테이블에 앉지 못한다.

하지만, STCF scheduling 방식으로 손님을 받는다면, 한 손님이 빨리 먹고 나간다고 하면 그 사람부터 테이블에 앉히는 것은 SJF와 똑같다.

여기에 만약, 테이블에 앉아있는 사람보다 빨리 먹을 자신이 있는 손님이 식당에 도착하면 테이블에 앉아있던 손님은 다시 나가고 새로 온 손님이 테이블에 앉아 식사를 하기 시작하는 것이다.

굉장히 도덕적으로는 옳지 못한(?) scheduling 방식이 아닐까 싶다.

 

이를 프로세스의 관점에서 생각해보면 꽤나 간단한 scheduling 방식인 것을 알 수 있다.

0번 시점에 들어오는 프로세스는 수명이 짧은 프로세스부터 작업을 처리하되, 이후에 다른 프로세스의 남은 수명보다 더 짧은 수명의 프로세스가 들어오면 해당 프로세스로 current 프로세스를 변경하여 처리해주면 되는 것이다.

순서대로 처리하면 다음과 같다.

How to Implement STCF?

1. 프로세스를 readyqueue에 넣어준다.
2. 시작 시점에 readyqueue에 남아있는 프로세스 중, 수명이 가장 짧은 프로세스부터 실행시킨다.
3. 작업을 반복하는 중, 현재 작업 중 프로세스의 잔여 수명보다 짧은 수명의 프로세스가 들어오면 작업을 중단하고 그 프로세스를 실행시킨다.
4. 이 작업을 반복한다.

Problems of STCF

하지만, 여전히 STCF에서는 해결되지 못하는 문제점이 있다.

바로, starvation인데, 여전히 프로세스의 수명이 긴 프로세스는 그보다 짧은 프로세스가 계속해서 들어오면 영원히 처리되지 못한 채 컴퓨터에 남아있을 것이다.

 

---

4. RR - Round Robin Scheduling

What is RR?

• Round Robin 방식의 실행 대기열은 원형 FIFO 대기열로 처리
• 각 작업은 time slice(또는 scheduling quantum)를 기준으로 처리
  • 특정 시간 간격의 timer-interrupt 기간을 기준으로 하거나, time tick을 기준으로 판단
  • 기준이 너무 짧으면, 높은 context switch로 인한 overhead가 일어날 수 있고,
  • 기준이 너무 길면, FIFO와 크게 다른 점이 없어지는 문제가 발생할 수 있음
• time slice에 대한 작업 실행 후 실행 대기열에서 다음 작업으로 전환
• Preemptive한 방식의 알고리즘이며, starvation이 발생하지 않음
• time slice만 적절히 맞춰준다면, response time을 최적화할 수 있음

 

Round Robin Scheduling 방식은 지금까지의 Scheduling 알고리즘의 방식을 원형 큐에 넣어서 실행시키는 방식이라고 생각하면 된다.

이번에도 교수님의 예시를 가져와서 생각해보자.

역시나 식당에 밥을 먹기 위해서 식당에 찾아온 여러 손님들이 있다.

그런데 여전히 STCF 방식으로 배식을 받아서 밥을 먹으면, 가뜩이나 식사하는 데 오래걸리는 사람은 먼저 오더라도 중간에 일어나서 자리를 비켜줘야 하는 상황이 발생하는 것이다.

그래서 식당 사장은 학부생 시절 배웠던 운영체제 수업을 떠올려 Round Robin 방식으로, 4 단위시간 동안 손님을 로테이션 하기로 했다.

 

 

SJF와 STCF의 수명을 기준으로 한다는 것을 제외하고, 단위시간마다 손님이 로테이션 되는 방식이 바로 이 Round Robin 방식이다.

 

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

위의 사진을 참고해보면서 생각해보자. 4가지의 프로세스가 동시에 들어오고 4 time slice라는 기준을 잡는다고 생각해 보자.

Process 1부터 차례대로 프로세스를 번갈아 실행하고, 모든 Process들의 lifetime이 종료되면 프로그램의 실행을 마치는 원리이다.

 

'원형 큐'에 담아서 생각해보라는 이유는, Process 1부터 Process 4까지 원형 큐에 있다고 생각하고 이 큐가 빙글빙글 돌면서 하나씩 프로세스를 실행하는 원리와 같기 때문이다.

 

Round Robin에서의 가장 중요한 점은 time slice 혹은 scheduling quantum을 얼마나 교묘하게 맞춰주느냐 하는 것이다.

 

How to Implement Round Robin?

1. 프로세스를 readyqueue에 넣어준다.
2. readyqueue에 들어가 있는 프로세스의 순서대로 프로세스를 time slice만큼 실행한다.
3. time slice가 실행되었는데도 lifetime이 남아있다면 다시 readyqueue에 넣어준다.
4. lifetime이 남아있지 않는다면 readyqueue에 넣어주지 않고 프로세스가 종료됨을 기록한다.
5. 이 작업을 반복한다.

 

---

이번 포스팅에서는 FCFS, SJF, STCF, Round Robin 방식을 리뷰해보았다. 쓰다 보니까 더 세부적인 내용을 다뤄야만 할 것 같다. 일단 scheduling에 대해서 모두 정리해본 후, 세부적인 내용까지 정리된 글을 작성해 볼 생각이다.

 

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