프로세스(PROCESS) 상태, 스케줄러, 스케줄러 알고리즘 #3

프로세스의 상태

 

프로세스의 상태에는 생성 / 준비 / 실행 / 대기 / 종료 총 5개의 단계로 나누어져있다.

 

프로세스 상태

맨 처음 프로세스가 create 상태가 됩니다.  그 후 사용자가 프로그램을 실행시키면 프로그램을 메모리에 load 시키면서 프로세스는 ready상태로 변화하게 됩니다. 메모리에 올라온 프로그램( = 프로세스 )중 어떤 프로세스를 먼저 실행시킬 것인가에 대해 cpu는 고민하게 되고, 이것은 cpu의 스케쥴링에 의해 결정되게 됩니다. (실제로는 dispatcher가 한다고 합니다.) 그렇게 running 상태에 있는 프로세스는 I/O 작업 요청이 오게 되면 block(=대기) 상태로 빠지게 됩니다. 그렇게 I/O 작업이 끝나면 바로 running상태로 가는것이 아닌 ready  상태로 돌아가게 됩니다. 

 

주의사항

 

1. ready 상태에서 계속해서 cpu의 점유권을 가져가지 못하는 프로세스 발생

2. block 상태에서 ready 상태로 넘어가지 못하는 프로세스 발생

 

프로세스 상태에서 문제가 발생할때

 

프로세스 상태가 block 상태로 되면 프로세스는 메모리에서 대기하는 상태이기에 메모리만 차지하고 있습니다. 이런 문제로 프로세스는 보조기억장치로 swap out해서 suspended block 상태로 바꿔주고 필요할 때 swap in으로 다시 메모리에 load 할 수 있게 됩니다. 이러한 과정을 통해 exit 상태가 되고 프로세스가 차지하고 있던 cpu 점유와 메모리를 반납하고 종료합니다.

 

---

스케줄러

 

스케줄링의 목적

• 처리량 최대화
• 자원활용도 최대화
• 무기한 연기 회피
• 우선순위 강화
• 오버헤드 최소화

스케줄러 수준 초록색으로 표시했습니다.

Long-term 스케줄러 ( = Job scheduler)

- 디스크와 메모리 스케줄링 담당

- 장기스케줄러로 하드 디스크에 있는 프로그램을 메모리에 load 하는 역할을 담당합니다

- 메모리에 몇개의 프로그램이 올라갈 것인 제어

- 프로세스의 상태는 new -> ready

- 보조기억장치에 있는 JOB QUEUE로 부터 프로세스를 끌어와서 메모리에 LOAD 시키는 스케줄러 입니다.

 

Short-term 스케줄러 ( = CPU scheduler)

- cpu와 메모리 사이의 스케줄링 담당

- 단기 스케줄러로 메모리에 있는 프로그램들 중 어떤 프로세스를 cpu에 할당할 지 결정하는 역할을 담당합니다

- 프로세스의 상태는 ready -> running -> waiting(block) -> ready

- READY QUEUE에 있는 프로세스를 대상으로 스케줄러 합니다.

 

Medium-term 스케줄러 (= Swapper)

-  위의 주의사항 내용에 관해 스케줄링하는 역할을 담당합니다.

-  현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러

-  메모리의 여유공간을 마련하기 위해서 프로세스를 통째로 디스크로 쫓아 냄(swapping)

-  프로세스 상태는 ready -> suspended

---

CPU 스케줄링 알고리즘

 

CPU 스케줄링을 하기전에 먼저 선점과 비선점에 대해서 알아야 합니다. 

선점과 비선점은 running 상태에서 ready 상태로 강제로 스케줄러에 의해 이동 유무에 따라 선점과 비선점으로 나누어지게됩니다. 

 

Cpu에서 실행되고 있는 프로세스가 Cpu 스케줄링에 의해서 Ready queue에서 대기하는 프로세스들 중 하나를 Cpu에 올리고, Cpu에서 실행되고 있던 프로세스는 Ready queue로 보내는 작업이 허용되는 운영체제를 선점 OS 라고 하고 이런 작업이 허용되지않는 운영체제를 비선점 OS 라고 합니다.

 

그럼 언제 스케줄링을 하는가??

 

1. I/O 작업 요청 발생 ( Running -> Block (wait) )
2. Interrupt 발생 ( Running -> Ready)
3. I/O 작업 종료 (Block -> ready)
4. 프로세스가 끝날 때  

 

스케줄링 알고리즘

 

1. First come, First Served Scheduling 

- ready queue에 들어온 프로세스가 먼저 실행된다.

 

Process	Burst Time
p1	5
p2	2
p3	3

 

먼저 들어오는 순서대로 cpu에서 처리를 하게 됨

1) p1이 걸리는 시간이 5초를 실행

2) 5초 이후 p2가 걸리는 2초 실행

3) p2까지 걸리는 7초 이후 p3 실행

 

평균대기시간 

p1 대기시간 = 0     / 바로 ready 큐에서 들어왔기 때문에 대기시간없이 바로 실행

p2 대기시간 = 5     / p1 작업이 끝날때 까지 대기

p3 대기시간 = 7     / p1 , p2의 작업이 끝날 때 까지 대기

 

(0 + 5 + 7) / 3  = 4초

 

이런 스케줄링은 오랜 시간을 사용하는 프로세스가 도착하면 다른 프로세스들이 cpu를 사용하기까지 대기하는 시간이 매우 커지는 상황이 발생하여 비효율적이게 됩니다. 이런 현상을 콘보이(convoy)효과라고 합니다. 

 

선점인가 비선점인가?

위의 그림을 보면 선점인지 비선점인지 금방 파악할 수 있다. 실행시간과 상관없이 먼저 들어온 프로세스를 cpu에서 계속해서 처리하기 때문에 강제로 cpu 점유를 바꾸지 않는다는걸 확인할 수 있습니다. 그렇기에 비선점 스케줄링 알고리즘입니다.

 

 

2. Shortest job First / (Shortest Remaining time First)

가장 시간이 적게 걸리는 작업을 먼저하는 스케줄링을 말합니다. 

SJF는와 SRT는 크게 같은 점은 처리하는데 걸리는 시간이 짧은 작업을 먼저하는 것에서는 동일합니다.

하지만 SJF는 선점 ,SRT는 비선점인 차이를 보이는데 아래 그림을 보면서 알아보도록 하겠습니다.

 

Process	Arrival Time	Burst Time
p1	0	4
p2	1	1
p3	2	3
p4	3	2

 

SJF 스케줄링

맨 처음 CPU에 할당된 프로세스가 없기에 가장 먼저 들어온 P1을 4초간 실행시킵니다. 그 사이에 P2,P3,P4는 도착하게 되고, P1이 끝난 후 가장 짧은 시간인 P2, P4, P3 순으로 실행시킵니다. 

 

평균대기시간 

P1 = 0     / 도착하자마자 실행되기 때문에 대기시간 0초

P2 = 4     / p1 작업 실행시간 만큼 대기

P4 = 5     / p1 + p2 작업 실행 시간 만큼 대기

P3 = 7     / p1 + p2 + p3 작업 실행 시간 만큼 대기

 

(0 + 4 + 5 + 7) / 4 = 4초

 

SJF 스케줄링의 단점은 효율성을 지나치게 강조하다 보니 실행시간이 너무나도 긴 프로세스가 있어서 새로 들어오는 프로세스들의 실행시간이 짧은 경우 영원히 CPU에 할당 받지 못하는 기아상태에 빠질 수 있다.

 

SJF는 선점인가 비선점인가?

이 방법 역시 실행시간에 따른 프로세스의 우선순위만 바뀔 뿐 작업중인 프로세스의 상태를 강제로 바꾸지 않기 때문에 비선점 스케줄링 알고리즘입니다.

 

 

SRT 스케줄링

맨 처음 CPU를 점유하고 있는 프로세스가 없기 때문에 P1을 실행합니다. 하지만 1초뒤 실행시간이 P1 보다 짧은 P2가 도착하기 때문에 P2를 먼저 실행 시킵니다. P4는 P1보다 실행시간은 짧지만  2초에 P2의 작업이 끝났기 때문에 아직 P4는 도착하지 못했습니다. 그렇기 때문에 P1을 다시 실행 시켜줍니다. 3초에 도착한 P4의 실행시간은 2초로 P1보다 작지않기 때문에 P1을 끝까지 실행시켜주고 나서 실행시간이 짧은 P4 다음으로 실행시킨 후 P3을 실행시켜 줍니다

 

평균대기시간

P1 = 1     / 맨 처음 대기시간 0초 + P2가 끝날때 까지 대기한 시간 1초

P2 = 0     / 도착시간 1초, 먼저 점유하고 있던 P1이 1초간 실행하는 동안 도착했고, 도착하자마자 실행했기 때문에 0초

P3 = 5     / 도착시간 2초, P1+P2 +P4가 작업을 끝낸 시간 7초 = 실행되는 시간 - 도착한 시간 ( 7 - 2)

P4 = 2     / 도착시간 3초, P1 + P2 가 작업을 끝낸 시간 5초 = 실행되는 시간 - 도착한 시간 ( 5 - 3)

 

평균대기시간

(1 + 0 + 5 + 2) / 4 = 2초

SJF 시간보다 평균 대기시간이 줄어든 걸 확인 할 수 있다.

 

SJF 스케줄링과 동일하게 SRT 단점은 효율성을 지나치게 강조하다 보니 실행시간이 너무나도 긴 프로세스가 있어서 새로 들어오는 프로세스들의 실행시간이 짧은 경우 영원히 CPU에 할당 받지 못하는 기아상태에 빠질 수 있다. 

 

SRT는 선점인가 비선점인가?

위의 SJF 스케줄링과는 다르게 P1이 먼저 CPU를 점유하고 있었음에도 불구하고 실행시간이 짧은 P2가 도착하자마자 P1은 CPU의 점유를 내주고 P2가 CPU를 점유하고 먼저 작업을 수행하는 것으로 보아 강제로 프로세스의 상태를 바꿔주기 때문에 선점 스케줄링 알고리즘입니다.

 

 

3. Priority Scheduling

우선순위가 가장 높은 프로세스에게 cpu를 할당하는 스케줄링을 말합니다.

 

Process	Brust Time	Priority
P1	1	3
P2	2	2
P3	3	4
P4	4	1

 

Priority 스케줄링

말 그대로 우선순위가 높은거 ( 정수로 숫자가 낮은거 ) 순으로 CPU에서 실행합니다. Ready queue안에 프로세스가 있다면 cpu 스케줄링을 통해 우선순위가 가장 높은 순으로 P4, P2, P1, P3 순으로 실행합니다. 

 

Priority 스케줄링 역시 우선 순위가 너무 낮은 경우 cpu 할당을 못 받게 되는 기아 상태에 빠지게 되고 실행 준비는 되었지만 프로세스가 cpu를 사용하지 못해 cpu가 무한히 대기하는 상태인 무기한 봉쇄 상태에 빠질 수 있게 된다. 이러한 문제를 해결하기 위해서 aging(노화) 기법을 이용하는데, 이 기법은 일정 시간이 지나면 사용되지 않은 프로세스들의 우선순위를 높여주는 방법으로, 프로세스가 cpu를 할당 받을 수 있게 해주는 방법입니다.

 

Priority 스케줄링은 선점인가 비선점인가?

우선순위가 낮은 프로세스가 들어올 때 Ready queue의 헤드에 넣어주면 위의 그림처럼 프로세스 상태를 강제로 바꿔주는 곳이 없기 때문에 비선점 스케줄링 알고리즘입니다. 하지만 도착시간이 따로 주어지면 cpu 우선순위가 달라지게 됨에 따라 선점형 방식으로 바뀌기도 합니다. ( 추후에 선점형 priority 스케줄링은 공부해서 첨부하겠습니다.)

 

 

4. Round Robin

현대적인 cpu 스케줄링 방식입니다. 각 프로세스는 동일한 할당 시간을 갖게 되고 할당시간이 지나고 나면 Ready queue 맨 끝으로 가서 다시 줄을 선 후 cpu 할당을 기다립니다.

 

Process	Burst Time
p1	3
p2	4
p3	1
p4	2

Time Quantum = 2초

 

각각의 프로세스들은 2초의 동일한 할당 시간을 가지게 된다. 그렇기 때문에 맨 처음 들어온 p1은 2초간 작업을 수행하고 다음 p2에게 cpu 점유권을 넘겨주고 Ready queue 맨 끝에서 줄을 섭니다.  그 다음 cpu 할당을 받은 p2는 2초간 작업을 하고 다시 뒤로가서 줄을 섭니다. 실행시간이 1초인 p3은 1초간 수행하고 다음 cpu점유권을 p4로 넘겨 작업을 수행합니다. 2초간 작업을 끝내고 남아 있던 p1의 작업을 마무리한 후 p2에게 cpu 점유권을 넘겨 작업을 마무리하게 됩니다.

 

이렇게 할당된 시간에 따라 자주 프로세스의 상태를 바꿀 수  있는 이유는 무엇일까? 

바로 문맥교환시 프로세스의 context를 저장할 수 있기 때문이다. 하지만 할당된 시간이 너무 짧아서 너무나 많은 문맥교환이 일어난다면 이때 오버헤드가 발생 할 수 있기 때문에 적절한 시간을 설정하는 것이 중요하다.

 

Round Robin은 선점일까 비선점일까?

이글을 읽으신 분이라면 이제는 혼자서 생각 할 수 있을껍니다. 할당된 시간동안 계속해서 cpu의 상태를 강제로 변화시켜주기 때문에 선점 스케줄링 알고리즘입니다.