y-log

CPU 스케줄링

메모리에 올라온 프로세스들 중 어떤 프로세스를 먼저 처리할지 순서를 정하는 것
Ready Queue에 있는 프로세스들 중에 누구에게 CPU를 할당해 줄 것인지 정하는 것

왜 필요한가?

CPU는 한 번에 하나의 프로세스만을 실행시킬 수 있다. --> 특정 프로세스가 I/O 요청으로 대기할 경우, CPU는 놀게됨

시간을 생산적으로 활용하고자 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당한다.

CPU 이용률 극대화

선점 및 비선점 스케줄링

CPU 스케줄러가 작동되는 4가지 상황

비선점 nonpreemptive

: 상황 1,4와 같이 프로세스가 자발적으로 CPU를 반납하는 경우

CPU가 한 프로세스에 할당되면 프로세스가 종료되든지, 또는 대기상태로 전환해 CPU를 방출할 때까지 점유한다.

선점 preemptive

: 상황 2,3과 같이 강제적으로 CPU를 빼앗기는 경우

Windows, macOS, Linux를 포함한 거의 모든 최신 운영체제들은 선점 스케줄링 알고리즘을 사용한다.

스케줄링 기준

CPU 이용률

전체 시스템 사용 시간 중 CPU가 작업을 처리하는 시간의 비율 

처리량

단위 시간당 완료된 프로셋의 개수

총 처리 시간

프로세스가 시작해서 끝날 때까지 걸리는 시간 ( 준비 큐에서 대기 시간 + CPU 실행 시간 + I/O 시간 )

대기 시간

프로세스가 준비 큐에서 대기하며 보낸 시간의 합

응답 시간

하나의 요구를 제출한 후 첫번째 응답이 나올 때까지의 시간 ( 응답이 출력되는 시간은 포함하지 않는다 )

CPU 이용률과 처리량을 최대화하고 총 처리 시간, 대기 시간, 응답 시간을 최소화 하는 것으로~!

스케줄링 알고리즘

선입 선처리 FCFS (First Come First Served)

특징

• 먼저 온 고객을 먼저 서비스해주는 방식, 즉 먼저 온 순서대로 처리.
• 비선점형(Non-Preemptive) 스케줄링
  일단 CPU 를 잡으면 CPU burst 가 완료될 때까지 CPU 를 반환하지 않는다. 할당되었던 CPU 가 반환될 때만 스케줄링이 이루어진다.

문제점

• convoy effect
  소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생한다.

SJF(Shortest - Job - First)

특징

• 다른 프로세스가 먼저 도착했어도 CPU burst time 이 짧은 프로세스에게 선 할당
• 비선점형(Non-Preemptive) 스케줄링

문제점

• starvation
  효율성을 추구하는게 가장 중요하지만 특정 프로세스가 지나치게 차별받으면 안되는 것이다. 이 스케줄링은 극단적으로 CPU 사용이 짧은 job 을 선호한다. 그래서 사용 시간이 긴 프로세스는 거의 영원히 CPU 를 할당받을 수 없다.

SRTF(Shortest Remaining Time First)

특징

• 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
• 선점형 (Preemptive) 스케줄링
  현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏긴다.

문제점

• starvation
• 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU burst time(CPU 사용시간)을 측정할 수가 없다.

Priority Scheduling

특징

• 우선순위가 가장 높은 프로세스에게 CPU 를 할당하는 스케줄링이다. 우선순위란 정수로 표현하게 되고 작은 숫자가 우선순위가 높다.
• 선점형 스케줄링(Preemptive) 방식
  더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 를 선점한다.
• 비선점형 스케줄링(Non-Preemptive) 방식
  더 높은 우선순위의 프로세스가 도착하면 Ready Queue 의 Head 에 넣는다.

문제점

• starvation
• 무기한 봉쇄(Indefinite blocking)
  실행 준비는 되어있으나 CPU 를 사용못하는 프로세스를 CPU 가 무기한 대기하는 상태

해결책

• aging
  아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주자.

Round Robin

특징

• 현대적인 CPU 스케줄링
• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖게 된다.
• 할당 시간이 지나면 프로세스는 선점당하고 ready queue 의 제일 뒤에 가서 다시 줄을 선다.
• RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적
• RR이 가능한 이유는 프로세스의 context 를 save 할 수 있기 때문이다.

장점

• Response time이 빨라진다.
  n 개의 프로세스가 ready queue 에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n 을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
• 프로세스가 기다리는 시간이 CPU 를 사용할 만큼 증가한다.
  공정한 스케줄링이라고 할 수 있다.

주의할 점

설정한 time quantum이 너무 커지면 FCFS와 같아진다. 또 너무 작아지면 스케줄링 알고리즘의 목적에는 이상적이지만 잦은 context switch 로 overhead 가 발생한다. 그렇기 때문에 적당한 time quantum을 설정하는 것이 중요하다.

< 참고 >

https://velog.io/@mu1616/CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81

스케줄러

Ready Queue에 존재하는 프로세스들을
특정한 우선순위를 기반으로 CPU를 할당받게 하는 역할로
장기, 중기, 단기 스케줄러가 있다.

프로세스를 스케줄링하기 위한 queue의 종류
1. Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합
2. Ready Queue : 현재 메모리 내에 있으면서 CPU를 할당 받기를 기다리는 프로세스의 집합
3. Device Queue : Device I/O 작업을 대기하고 있는 프로세스 집합

장기 스케줄러 Long - Term Scheduler

수행할 job이 10개, 메모리에는 6개 밖에 올릴 수 없는 상황
job 10개 중 6개를 골라서 올려야 하는데 이때 job을 고르는 역할을 하는 것이 장기 스케줄러
따라서 잡 스케줄러라고 불리기도 한다.

ready queue에 적재하는 메모리와 디스크 사이의 스케줄링을 담당하는 스케줄러인데,  I/O bound 중심의 프로세스들과 CPU bound 프로세스들의 적절한 비율을 조절해 올린다.

* I/O bound process : 입출력 많은 프로세스 (이 비율이 높으면 놀고 있는 cpu 많아짐)

CPU bound process : CPU가 계산을 해줘야 하는 비중이 큰 프로세스 (이 비율이 높으면 사용자와 상호적이지 못해서 실시간적인 의미 없어짐)

1. 어떤 프로세스를 Ready Queue에 삽입할지 결정

2. 메모리와 디스크 사이의 스케줄링을 담당

3. 프로세스에 메모리를 할당 

4. 메모리에 동시에 올라가 있는 프로세스의 수를 조절 

5. 프로세스의 상태[new -> ready(inmemory)]

단기 스케줄러 Short - Term Scheduler

장기 스케줄러를 통해서 job을 6개를 고른 상태
CPU에서 하나를 수행완료하고 나머지 job중 에서 하나를 골라야하는데 이걸 골라주는 스케줄러
따라서 CPU 스케줄러라고 불리기도 한다.

CPU가 낭비되지 않게 A라는 프로세스가 수행되다가 사용자의 입력을 받기 위해 cpu가 대기하는 상황이 되면 바로 B 프로세스로 교체해서 수행시킨다. 그러다 사용자의 I/O가 끝나면 다시 A프로세스를 cpu로 불러온다.

최소 100밀리 세컨즈마다 수행되어 단기 스케줄러라 불린다.

장기 스케줄러와 단기 스케줄러 -> CPU 스케줄러

요즘엔 virtual memory management가 발달해서 job이 10개면 메모리로 10개가 다 올라온다. 

즉, 장기 스케줄러의 의미가 없다는 것인데, long term이 없다면 short term의 의미가 무색해지기 때문에 주로 CPU 스케줄러라고 불린다. 

1. CPU와 메모리 사이의 스케줄링을 담당하며 CPU 스케줄러라고도함

2. Ready Queue에 존재하는 프로세스들 중 스케줄링 알고리즘에 따라 CPU를 할당할 프로세스 선택

3. 프로세스의 상태[ready -> running -> waiting -> ready]

중기 스케줄러 Medium - Term Scheduler

장기/단기 이후에 나왔다. 위에서 말했듯이 현재 개념은 가상 메모리개념이기 때문에 중기 스케줄러 또한 이용되지 않는다.

장기 스케줄러에 의해 10개 중 6개의 job을 올려서 수행중인 상태
CPU가 수행하려고 보니 감당하기엔 너무 많아 문제가 생겨 6개 중 2개를 내려보내면 상황이 해결될 것
6개 중 뭘 내려보낼지 결정하는 것이 중기 스케줄러의 역할 
Swapper라고도 불린다.

프로세스를 내릴 때 우선순위가 가장 낮은 프로세스나 일정 시간 동안 활성화되지 않았던 프로세스들을 내린다.

프로세스를 내리고 (swapping out) 다시 올려지는 (swapping in) swapping과정을 수행하기 때문에 swapper라고 불린다.

 1. 메모리에 적재된 프로세스의 수를 동적으로 조절

2. 메모리적재된 프로세스의 수가 많을 때 메모리를 통째로 디스크의 스왑 영역에 저장(Swap Out)

3. 프로세스의 상태[ready -> suspended]

<참고>

https://kmseop.tistory.com/119 https://jhnyang.tistory.com/372