CPU Scheduling ( CPU 스케줄링 )

OS는 주차단위가 아니라 개념단위로 해야할 듯.

좀 순서가 산만하다 그러다보니 이것저것 겹친다.

 

 

근데 이런 이야기에 앞서,

CPU 코어이야기덜을 들었는데,

얘네가 무어냐,,, 하니

 

코어는 Core, 말 그대로 CPU의 중심이다.

여기서 컴퓨터의 연산을 함.

CPU에는 코어를 여러개 담을 수 있는데

이제 코어가 많으면, 연산 성능이 더 좋겠쥬?

 

그렇기 때문에, 코어가 높을수록, 동작속도(클럭수)가 높을수록 좋다는 말이 앵간 맞다.

 

 

 

 

 

CPU Scheduling의 기본 개념

Basic Concepts

• multiprogramming을 통해 CPU 효율을 최대로 살리기( *오버헤드를 최소화 )
• 프로세스의 공평한 분배

 

*오버헤드란?

   overhead : 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 - 메모리 등을 말한다.

 

 

 

 

& CPU burst time : CPU가 일을 수행하는 시간.

& I/O burst time : I/O요청에 대한 응답을 기다리는 시간.

 

 

아래의 그림은 Alternating Sequence of CPU and I/O bursts.

CPU가 일을 하고 대기하고 일하고 대기하고 번갈아 움직이는 그런 두둥탁! 리듬

 

Scheduling Algorithms

 

 

assembly어의 CPU-I/O burst 루틴 짤

 

 

 

 

 

일 준나 할 때는 개높고, IO할땐 거의 낮다.

스케줄링 하는 기준.

Scheduling Criteria

 

cpu utilization -> keep the CPU as busy as possible

CPU를 악덕사장이 외노자 굴리듯 항상 얼마나 바쁘게 하는 지.

쓰루풋(Throughput) - # of processes that complete their execution per time uint

시간당 얼마나 많은 프로세스들을 처리할 수 있는가.

(알쓸신잡 : 쓰루풋 값은 크면 클수록 좋다.)

 

waitingtime, responsetime, turnaroundtime에 따라.

(알쓸신잡 : 얘네는 전부 작아야 좋음)

 

근디 여기서 responsetime은 output(결과)가 아니라 첫 요청이 가고 그 응답이 올 때까지 걸린 시간.

 

 

 

 

 

스케줄링을 해서 이제 CPU의 상태가 워쯔케 되나.

(전부 상태 변화이다. (실행->대기), (실행->준비),(대기->준비))

 

1. Switches from running to waitng state.

2. Switches from running to ready state.

3. Switches from waiting to ready.

4. Terminates.

 

 

 

여기서 디스패처(Dispatcher)가 사용된다.

 

wht is dispatcher

 

사용자가 프로그램을 실행하면 프로세스가 생성되고 ready상태가 된다. 그 후 스케줄러가 ready queue에 있는 프로세스 중 하나를 프로세서가 사용가능한 상태가 될 때 CPU를 할당해준다.

 

이를. 준비상태(ready)에서 실행상태(running)으로 상태전이(state transition)된다고 한다. 이 과정을 디스패칭이라고 하고 이걸 디스패처가 한다.

 

 

 

 

 

여기 1번부터 4번은 전부 non-preemptive Scheduling(비선점 스케줄링)방식이다.

이 방식 이외는 전부 Preemptive Scheduling(선점 스케줄링)이다.

 

비선점 스케줄링이 무ㅜ냐,

 

어떤 프로세스가 CPU를 할당받으면 그 프로세스가 종료되거나, 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 ㅠ한다.

 

순서대로 처리되는 공정성이 있고, 다음에 처리해야할 프로세스와 상관없이 응답시간을 예상할 수 있으며 선점방식보다 스케줄러 호출빈도가 낮고 문맥교환에 의한 오버헤드가 적다. 일과처리 시스템에 적합하며 자칫 CPU사용시간이 긴 프로세스가 다른 프로세스들을 대기시킬 수 있으므로 처리율이 떨어질 수 있다는 단점이 있다.

 

 

반대로, 선점 스케줄링은

OS가 나서서 CPU사용권을 '선점'하고 특정 요건에 따라 각 프로세스의 요청이 있을 때 프로세스에게 분배하는 방식이다

.

-> 가장 자원이 필요한 프로세스에게 CPU를 분배하며 상황에 따라 강제로 회수할 수도 있다. 따라서 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세스를 제어할 수 있다.

 

 

 

 

 

 

 

 

 

Alogrithm Evluation

 

1. FCFS(First Come, First Serve)

먼저 도착한 프로세스 먼저 처리.

 

 

 

 

2. SJF(Shorted Job First)

가장 짧은거 우선. (CPU burst time이 짧은)

그래서 평균 대기시간이 짧다는 특징.

 

-> 만약 CPU 버스트 시간이 동일하다면 FCFS방식을 따름.

-선점형 : 

-비선점형 : 최소잔여시간 우선 법칙.

 

 

 

3. PS (Priority Scheduling, 우선순위 스케줄링)

미리 주어진 프로세스의 우선순위에 따라서 스케줄링하는 방식이다.

SJF도 우선순위 스케줄링의 일종이다.

(우선순위가 낮으면 할당 안되기도하는데 이걸 기아(kia 아니고 starvation)이라고 부른다.

이를 방지하기 위한 해결법으로 노화(Aging)이 있는데 기다리는 시간에 따라 우선순위를 증가시켜주는 방식이다.

-선점형과 비선점형

 

 

4. Round Robin(라운드로빈) 

정해진 시간 할당량만큼 프로세스를 할당한 뒤, 작업이 끝난 프로세스는 준비완류 큐의 가장 마지막에 가서 재할당을 기다린다.

-선점형

 

얘는 시간할당량( *Time Quantum )이중요한데, 너무작으면 빈번한 context swtiching이 발생해서 안줗구, 너무길면 FCFS와 다를 바 없어진다.

 

*Time Quantum

하~ 나는 이게 뭔가 했네, 이거 그냥 공평하게 시간 배분할건데 한 프로세스에 얼만큼의 시간 줄 건지

가령, CPU burst가 10인데 time quantum이 6이다 그럼 CPU burst 6만큼 쓰고 context change가 일어나는 것이고, CPU burst가 10이고 time quantum이 10보다 크다. 하면 CPU가 그 일에 올빵하면 된다. 극단적으로 time quantum이 무한대다 라고 한다면, 프로세스를 전부 처리하고 다른걸로 넘어가니까, FCFS와 같은 알고리즘이 되는 것이다. 즉, time quantum이 작을수록 context switcing이 길어진다. 아주 길면 FCFS처럼 되는 것이고,

 

그래서, 이 time quantum을 잘 짜줘야 하니까 어떤 규칙을 정해두었다.

그 규칙은 rule of thumb인디,

"A rule of thumb is that 80 percent of CPU burst should be shorter than the time quantum"

" CPU 가동의 80퍼센트 <= time Quantum "

 

time quantum이 작으면 context switching이 많아지니까 그럼 "오버헤드" 발생.

근데 오버헤드는 퍼포먼스와 직결되는거니까, 오버헤드는 작아야하고,

그렇다고 타임퀀텀 너무 길게 잡자니 FCFS되니까 적당히 잡는 기준선이라고 보면 된다잉.

 

 

5. Multilevel-Queue(다단계 큐)

준비완료 큐를 여러개의 큐로 분류하여 각 큐가 각각 다른 스케줄링 알고리즘을 가지는 방식.

 

 

 

6.