12. Process Scheduling (3)

 

지난 내용

1. Starvation : 모종의 이유로 인해 CPU를 할당하지 못하는 것
2. Preemtive Scheduling : 다른 프로세스를 처리하기 위해 CPU를 다른 프로세스에게 넘겨주는 것
3. FCFS (Fist-Come, First-Served) : 가장 먼저 온 프로세스부터 처리
4. SJF (Shortest Job First) : 가장 짧은 것부터 처리
5. SRTF (Shortest Remaining Time First) : SJF의 preemptive version

---

Priority Scheduling

우선순위가 가장 높은 애들을 처리한다.

Preemptive 가 될 수도 있고, Non-preemptive가 될 수도 있다.

 

SJF : 프로세스의 실행시간이 가장 짧은 애부터 처리하는 것

여기에도 Priority Scheduling이 있다. 실행시간은 짧은 애를 priority를 높게 주는 것이므로.

---

 

 

priority가 높은 애들만 처리하면 Starvation이 발생할 수 있다.

낮은 priority를 갖는 애들은 높은 priority 로부터 계속 기다릴 수 있으므로.

 

스케줄링을 못 받고 있을 때 Age를 반영해서

해당하는 프로세스에 priority를 조정해주는 것이 Aging 이라고 한다. 

 

특정한 애들이 starvation이 발생할 때 priority를 부여하는 것을 priority boosting 이라고 한다.

---

주기적으로 컴퓨터상태를 봐서 컴퓨터를 강제로 셧다운 시켜버린다.

 

---

지질학 데이터를 뽑는 : aquire

lock : 특정데이터를 쓰레드나 프로세스가 동시에 접근하지 못하게 보호하게 함

Bus management task 갑자기 떠서 aquire 됨

 

---

Priority Inversion 

priority scheduling 을 하는 시스템에서

높은 priority 인 task가 있고 낮은 priority task가 있는데,

제 3의 task 가 끼어들어서 높은 priority task를 진행하지 못하게 하는 것

 

---

Priority ceiling protocol (PCP)

shared resource를 잡을 때 마다 priority를 확 높여주고 필요 없으면 다시 놓아주는 방식

장점 : 짜기가 쉽다.

 

Priority Inheritance Protocol (PIP)

resource를 잡을 때마다 priority를 높여주지 말고

내가 만약 높은 priority task가 낮은 priority task가 가지는 resource가 필요하다면

임시적으로 낮은 priority를 가지고 도는 프로세스에 priority를 임시적으로 확 높여주는 방식. 

 

---

 

요약

Priority Scheduling : Task 마다 Priority를 가지고 있고 높은 Priority 갖은 Task를 먼저 처리하는 것

Preemptive의 속성을 가질 수 있다.

Starvation이 발생할 수 있지만 Aging이나 Priority Boosting을 통해 해결할 수 있다.

Priority Inversion 문제가 발생할 수 있지만

Priority Ceiling Protocol이나 Priority Inversion Protocol로 해결할 수 있다.

 

Prioirty Scheduling 요약

****************************************************************************************************************************************

Priority Scheduling

•  우선순위로 스케줄링을 한다. 우선순위에 대한 정보를 가지고 있어야 한다.
•  가장 큰 문제점은 무기한 봉쇄 또는 기아 상태이다. 해결방법으로 시간이 지날때 마다 우선순위를 증가시켜준다.
•  Waiting time for P1  = 6; P2  = 0; P3 = 18; P4 = 0; P5=1

•  Average waiting time = (6 + 0 + 16 +18 + 1)/5 = 8.2

 

****************************************************************************************************************************************

 

Priority Scheduling

• 우선순위를 정해줘서 프로세스를 진행한다.
• 책에서는 낮은 수가 high priority를 가지는 것으로 되어있다.
• prioriy를 측정하는 방법은 두가지이다.

1. Internal : time limit, memory required
2. external : OS 밖에서 정해진 것으로 중요도, fund, political factors

• preempt 가능하다.
• indefinite blocking이라는 우선순위 낮은 친구는 아예 수행이 계속 안될 수도 있다.
• 이를 해결하기 위해서 aging을 통해 시간이 지남에 따라 priority를 높여준다.

****************************************************************************************************************************************

 

---

전반적으로 모든 task를 queue에 꺼내와서 스케줄링해서 돌린다.

time slice 만큼 돌린다.

 

Round robin 요약

****************************************************************************************************************************************

RR(라운드 로빈) Scheduling

• 시분할 시스템을 위하여 설계되었다.
• 먼저 들어온 것이 먼저 나가지만 CPU를 점유 할 수 있는 시간이 제한되어있다.
• Time Quantum이 작으면 오버헤드가 크고 너무 크면 FCFS와 똑같다.
• CPU를 얻기 까지의 최대 대기 시간은 (n-1)•Quantum이다.

****************************************************************************************************************************************

Round-Robin Scheduling

• RR은 Time sharing System이다.
• FCFS랑 유사한데 preempt를 가능하게 한 것이다.
• Time quantum을 설정해서 이 단위 만큼 일을 수행할 수 있도록 한다.
• Time quantum마다 interrupt를 날려서 실행 시간이 퀀텀보다 작으면 process release
• 아니면 하던 일을 다시 queue에 집어 넣어
• quantum size를 잘 설정해줘야 한다. 왜냐하면 엄청 작으면 실행하는 내내 context switching이 너무 costy해
• 때문에 큐에 있는 친구들의 CPU burst의 80% 이내가 Time quantum 안에 들어와야 한다.

****************************************************************************************************************************************

---

 

time quantum 만큼 하고 뒤로 빠지고 하면서 하므로 Starvation이 발생하지 않는다.

Response time이 개선된 것이다.

일반적으로 RR 쓴다.

 

RR에도 Priority Scheduling을 적용할 수도 있다. 생각해봐라

---

각각의 레벨에 맞는 스케줄링을 쓰자.

 

 

---

Multilevel Feedback Queue

• 각 큐마다 스케줄링 알고리즘을 가진다.
• 우선순이가 높은 큐의 프로세스를 먼저 처리한다. -> 기아현상을 일으킬 수 있다.

• Multilevel Queue로 프로세스가 큐간 이동이 가능하도록 하게 한다.

---

Multilevel Queue Scheduling

• 프로세스를 여러 그룹으로 구분 가능할 때(foreground, background)
• queue를 여러개로 쪼개고 각자의 algorithm을 적용한다.
• queue를 scheduling해 (priority setting) 후 순서대로 확인한다.

---

 

서로 다른 큐를 여러개 놓고

각각의 큐마다 Scheduling 방법을 다르게 하자. 

---

 

MLQ 상세설명

---

Multi Level Queue : 다단계 큐

어떤 프로세스냐에 따라서 여러 종류의 그룹으로 나누고 여러개의 큐에 다양한 알고리즘을 적용하는 스케줄링 기법

 

운영체제는 프로세스들을 분류할 때 보통 사용자와 상호작용하는 앞단의 프로세스들은 중요하다고 판단하고 백그라운드에서 돌아가는 프로세스(일괄처리형 batch processes)들은 상대적으로 덜 중요하다고 판단하여 분류하는 것이 일반적이다.

 

이렇게 분류를 해서 서로 다른 스케줄링 기법을 적용하는 것이 다단계 큐 알고리즘이다.

 

앞단의 프로세스들은 백그라운드에서 조용히 돌아가는 프로세스들 보다 더 높은 우선순위를 갖게 되고, 빠른 응답 시간을 주기 위해서 당연히 다른 알고리즘이 적용되어야 더 효율적으로 성능을 끌어낼 수 있다.

back ground queue는 보통 FCFS 알고리즘이 작동할 것이고 (내가 게임할 동안 다운로드느 쭉 끝날때까지 실행되어야 하기 때문)

우선순위가 높은 fore ground queue에는 아마 RR 알고리즘이 적용될 것이다. (게임하는데 자꾸 CPU가 다른 프로세스 처리해서 느려져)

 

배치 큐에 있는 프로세스가 실행되려면 앞의 큐들이 다 비어있어야 한다.

앞의 큐들이 다 비어있어서 배치 큐에 있는 프로세스가 실행이 되고 있는데 갑자기 편집 프로세스가 ready queue에 들어오면?!

그러면 배치 프로세스는 잠시 뒤로 물러나고 우선순위가 더 높은 편집 프로세스가 실행이 된다. >> premptive 방식

 

이외에, 큐 사이에 time-slice를 적용하는 방식도 있다.

RR 방식을 도입한 것이다. 각각 큐에게 다른 time quantum을 설정해 주는 것이다.

예를 들어 foreground - background 큐 방식에서는, 중요한 foreground 큐에는 총 CPU burst의 80퍼센트를 커버할 수 있도록 설정해주고, background에는 20퍼센트만 주는 것이다. RR 에서 배웠듯이, time quantum이 길어질수록 FCFC방식을 뛴다고 했다. 결국 우선순위가 낮은 background 프로세스에 상대적으로 더 긴 time quantum을 할당함으로써 FCFS 느낌을 띄게 되는 것이다.

- 여러 종류의 그룹으로 나누어 여러개의 큐를 이용하는 스케줄링 기법이다.

- 그룹화된 작업들은 각각의 준비 큐에 넣어두고 각 큐의 독자적인 스케줄링 알고리즘에 따라서 CPU를 할당받는 방법이다.

---

---

상황에 맞춰서 하자

MLFQ

퀀텀안에 넣고 돌리면서 피드백을 받으면서 보자

 

MLFQ 상세 설명

다단계큐 알고리즘은 각각 프로세스의 중요도에 따라 큐로 나누고 각 큐에서 다른 알고리즘을 적용해 효율을 높일 수 있는 장점이 있다. 반면에 한 번 해당 큐에 들어가면 프로세스는 다른 큐로 이동되거나 변경되는 것이 거의 불가능하다는 단점이 있다. 즉 스케줄링 오버헤드가 낮은 대신에 inflexible 하지 못하다.

 

멀티레벨 큐는 우선순위 스케줄링에서 언급했던 것처럼, 그냥 우리가 뭐가뭐가 있으면 중요도가 좀 더 높을 것이다라고 판단해서 우선순위를 높게 줄지 낮게 줄지 분류할 수 밖에 없다. 그치만 이건 절대적일 수가 없다. 한 예로 대화영 프로세스는 중요한데 그걸 미리 알 수가 없다. 그냥 저럴 경우 높더라 추측으로 분류할 뿐... 그런데 이게 잘못돼도 변경할 수 없는 유동적이지 못한 단점이 있다.

 

앞으로 배울 MLFQ는 MLQ와 다르게 프로세스가 큐 사이 이동이 가능하다. 분류되는 방식도 차이가 있다.

 

MLFQ에서는 어떤게 중요한지 모르니까 일단 시작은 다 똑같이 한다. MLQ가 우선순위에 따라 들어가는 입구가 달랐다면 MLFQ는 모든 프로세스들이 제일 위에 있는 큐로 일단 들어온다. 

만약 제일 위에 있는 queue는 RR로 스케줄링을 하는데 time-quantum을 8로 스케줄링 한다. 자신의 time-quantum을 다 채우지 못한 process는 냅두고 time-quantum을 다 채운 프로세스는 그 밑의 레벨에 있는 큐로 들어가게 된다. 특징은 밑에 있는 큐는 time-quantum의 크기를 첫 번째에 있는 큐의 두배로 늘린다. 마지막 큐는 백그라운드 프로세스가 보통 그랬듯이 대게 FCFS로 처리한다.

 

그러면 왜 피드백인가?

일단 MLQ인데 queue에 서로 피드백이 있다. 그래서 MLFQ 라고 한다.

일단 시작은 다 똑같은 데로 들어왔는데 자신의 time quantum을 다 채운 애는 밑으로 내려가고 자신의 time quantum을 다 채우지 못한 애는 그냥 원래대로 들어간다. 자신의 time quantum을 다 채운거랑, 다 못 채운거랑 의미는 뭘까?

이 특징은 바로 CPU burst의 중요도와 상관관계를 사람들이 발견한데서 있다.

보통 사용자와 interactive 하지 않은, background 프로세스는 CPU burst가 매우 크다는 특징을 이용한 것이다.

 

우리가 사양이 매우 큰 게임을 다운로드한다고 생각해보자. 게임을 다운로드 하는데 적어도 30분은 기다려야 한다고 하자. 그럼 우리는 이걸 백그라운드로 돌려놓고 인터넷. 서칭을 한다. 즉 바로바로 처리해야할 일은 인터넷 서칭이 된다. 만약 게임 다운로드 하는 동안 나는 아무것도 할 수 없다면 답답하고 짜증날 것이다. 이렇게 게임 다운로드처럼 CPU를 계속 써야하는, CPU burst가 큰 프로세스를 우선순위가 낮다고 판별하는 것이다. 그리고 나와 상호작용할 가능성이 높은 프로세스, 내 입출력을 필요로 하는(마우스, 키보드) 애들은 CPU처리가 I/O 작업이랑 번갈아 가며 일어나므로 CPU burst가 적다는 특징을 가진다. 그리고 이를 우선순위가 높구나!라고 판단하여 활용한 것이 MLFQ 이다.

 

time quantum을 다 채웠다는 것은 CPU burst 프로세스일 가능성이 높다. 그래서 한번 더 밑으로 내려보는 것이다. 16으로 했더니 그걸 또 다 채웠어? 아 그럼 이거는 CPU bound process 구나. 그러니까 아예 밑으로 내려가서 CPU bound process들은 사용자하고 대화형으로 동작하는 것이 아니니까 context switching을 안하고 그냥 걔를 쭉 수행시켜주는 것이 유리하다. 그러니까 그냥 FCFS로 하는 것이다.

즉 다음단계로 넘어갈수록 CPU burst가 크다는 거니까 우선순위가 점점 낮아진다. 이런 룰이다.

 

www.blog.naver.com/jhnyang/221519697258

---

리눅스는 프로세스 스케줄링을 MLFQ로 한다.

Preemptive 하다.

Time-shared를 하는 Round Robin 방식으로 하고

Priority를 동적으로 조절하는 방식을 취한다.

****