1. What is Process Scheduling?
> 각 프로세스들은 각자 주소 공간을 가지고 있음
> 멀티 프로세스 환경에서는 각 코어가 각각의 프로세스 코드를 실행함.
>> 그렇다면 단일 프로세스인 경우에는??
>> 각 프로세스의 실행을 CPU가 번갈아가면서 작업함.
>> 1번 프로세스 조금 2번 프로세스 조금 3번 프로세스 조금 이런식으로 스위칭
>> 그럼 이 순서는 누가 정하냐?
>> 당연히 OS가 정하게 됨 OS에서 어떤 프로세스가 실행 될지 정해줌
프로세스 스케쥴링의 목표는 CPU 리소스에 대해서 여러 프로세스들을 가능한 빠르게 교체하는 것.
즉 프로세스간 스위칭을 굉장히 빠르게 하는 것.
스케쥴링 하는 방법을 말하기 전에, 프로세스들의 타입에 대해 설명하려 함.
A) CPU-bounded process
> 이는 CPU를 사용하는 시간이 대부분인 프로세스를 말함
B) I/O bounded process
> 이는 I/O operation을 자주 하는 프로세스를 말함
2. CPU Switching
CPU가 현재 진행중인 프로세스의 상태를 해당 PCB에 저장해 놓고, 다음에 진행 할 프로세스의 PCB에서 해당 프로세스의 상태를 load해서 흐름에 맞게 진행하는것
>> 이를 Context Switching이라 함.
Context Switching에는 결국 OS의 개입이 있다보니까 오버헤드가 발생함.
프로세스 스케쥴링의 state diagram을 보면
위와 같다.
Admmitted: 프로세스가 생성이 되면, OS에 의해 READY QUEUE에 들어가서 준비상태가 되고, 자신의 시간을 기다리게 된다.
Scheduler dispatch : CPU를 점유할 준비가 되어 있는 프로세스(Ready Queue에 있는)가 scheduler에 의해 Cpu의 리소스를 할당받아 실행된다.
Interrupt : 실행되고 있던 프로세스가 인터럽트에 의해서 실행을 멈추고 ready상태가 된다.
I/O or event wait : 실행중이던 프로세스가 I/O operation 또는 event가 필요한 instruction에 도착했을 시, 해당 작업이 끝날 때 까지 wait상태가 된다.
I/O or event completion : I/O operation또는 event의 작업이 완료되면 프로세스는 wait을 멈추고 다시 ready queue로 들어간다.
exit : 현재 돌고있는 프로세스가 작업을 완료하여 exit()을 통해 종료된다.
I/O or event wait과 exit은 현재 돌고있는 프로세스가 스스로 CPU를 놓아주는것이고
interrupt와 I/O or event completion은 현재 프로세스로부터 OS가 강제로 권한을 뺐어서 다른 프로세스에 할당해 주는것
3. Starvation
> Starvation은 다른 프로세스가 CPU를 차지하고있어서 특정 프로세스가 리소스를 사용하지 못하는 현상
> 잘못된 스케쥴링 정책을 사용 시 스타베이션 문제가 발생 할 수 있음
> 시스템의 공통 목표는 스타베이션이 없고, CPU할당의 기회가 공평하게 돌아가고, 모든 시스템의 부분이 busy하게 돌아가야 함
따라서 throughput과 CPU utilization을 항상 높게 가지는것이 중요함.
4. Preemptive Scheduling
여러 스케쥴링 알고리즘이 있는데 크게 두 부분으로 나뉨
a) Non-Preemptive schediling
> 한 프로세스가 CPU를 잡고있으면 스스로 놓지 않는 이상 p2는 절대 점유 불가
b) Preemptive schduling
> OS가 현재 프로세스를 강제로 빼서 다른 프로세스를 할당 가능 >> Context switching이 가능
>> 이 부분에서 만약 현재 진행중인 프로세스가 공유데이터를 가용중이면 싱크로나이제이션 문제가 생김.
>> 또한 현재 프로세스가 시스템 콜을 하는 도중에 preemptive되는 경우 문제가 생김.
5. 알고리즘의 평가
a) CPU utilization
> CPU를 얼마나 사용하는가?에 대한 것
b) Throughput
> 단위 시간당 실행 완료한 프로세스의 개수
c) Turnaround Time
> 프로세스가 완료되기까지의 전체 걸린 시간.
d) Waiting Time
> 대기시간, 해당 프로세스가 waiting queue에서 기다린 시간
e) Response Time
> 처음으로 응답받기까지에 걸린 시간
6. 스케쥴링 알고리즘
a) FCFS / FIFO
> First in first out
> 단순하게 제일 먼저 도달한 순서대로 작업을 수행하는 것
> non-preemtive알고리즘
> Convoy effect 현상이 일어남
>> 이는 실행시간이 적은 프로세스가 엄청 긴 프로세스때문에 기다리는 현상
위의 경우 평균 waiting Time을 계산해 보면
P1 + P2 + P3 = 0 + 24 + 27
평균 waiting Time = 51/3 = 21
평균 turnaround Time을 계산해보면)(> 프로세스가 완료되기까지의 전체 걸린 시간.)
P1 + P2 + P3 = 24 + 27 + 30
평균 turnaround Time = 27
이 경우는 평균 waiting time을 계산하면
P1 + P2 + P3 = 0 + 3 + 6
평균 waiting time = 3
평균 turnaround time을 계산하면
P1 + P2 + P3 = 3 + 6 + 30
평균 turnaround time = 13
계산결과 확연히 아래 부분이 성능이 좋다는걸 확인할 수 있다. 1번과 같은 현상이 convoy effect이다.
b) SJF
convoy effect의 해결책으로 나온 알고리즘
> 실행시간이 짧은 프로세스부터 실행되는 알고리즘
> Non-preemptive 알고리즘
우선순위 스케쥴링의 한 방법이다.
> 이는 이론적으로 증명된 알고리즘인데, SJF를 사용하는 경우, average waiting time이 가장 최소값을 가진다.
하지만 현실적으로는 불가능한데, CPU burst time을 예측하는것이 불가능하기 때문이다.
> 또한 잠재적으로 스타베이션 현상이 있을 수 있음
>> 실행시간이 짧은 프로세스가 일정 시간을 두고 계속 들어오는 경우
평균 waiting time 을 계산해 보면
P1 + P2 + P3 = 7 + 0 + 2
평균 waiting time = 3
평균 turnaround time을 계산해보면
P1 + P2 + P3 = 30 + 2 + 7
평균 turnaround time = 13
c) SRTF
> Job의 남은 시간이 짧은것부터
> preemptive 버전의 SJF임.
평균 waiting time을 계산해보면
Waiting time 쉽게 계산하려면 Turnaround Time - CPU burstTime을 하면 된다.
p1 + P2 + P3 + P4 = 9 + 0 + 13 + 0 = 22
평균 Waitting time = 5.5
평균 Turnaround Time을 계산해보면
P1 + P2 + P3 + P4 = 17 + 4 + 22 + 5
평균 Turnaround Time = 12
댓글