CPU 스케줄링

운영체제 관련 글 순서

- 프로세스란
- 쓰레드
- CPU 스케줄링
- 동기화 툴
- 동시성 제어 예제
- 데드락
- 주 메모리
- 페이징과 스와핑
- 가상 메모리와 디맨드 페이징
- 페이지 교체 알고리즘(FIFO, OPT, LRU), 쓰레싱, working set

 

 

 

CPU 스케줄링이란

 

멀티프로그래밍^[각주:1]에서 cpu를 잘 사용하기위해 하는것.

CPU는 동시에 하나의 프로세스만 실행 가능한데, 한순간에 어떤 프로세스가 사용할지 결정해주는 것.

 

프로세스는 CPU burst와 I/O burst를 반복하여 바뀌며 프로그램을 실행한다.

 

오른쪽은 대체적으로 I/O burst 시간이 많은 프로그램이 더 많다는 그래프

그렇기 때문에 I/O burst동안은 다른 프로세스가 CPU를 점유할 수 있게하여 CPU 사용률을 끌어올려야함.

이때 CPU 스케줄러에 의해 변경된다.

 

 

버스트의 뜻

: 연속된 신호 또는 데이터 모임. 또는 데이터를 주고 받는 것.

cpu burst: CPU 명령을 실행

i/o burst: i/O를 요청한다음 대기하는 시간

ex) cpu burst time 10 -> cpu가 10총동안 프로세스 작업

cpu burst가 큰 프로세스를 cpu bound process,

I/O burst가 큰 프로세스를 I/O bound process라고 부름.

ex) 사용자와 대화용으로 동작하는 프로세스는 I/O bound process

bound: ~ 위주의란 뜻으로 알면 됨.

 

 

 

CPU 스케줄러의 결정은 아래와 같은 상황에 발생한다.

1. running - > waiting (I/O발생)
2. running -> ready (인터럽트 발생)
3. waiting -> ready (I/O 종료)
4. terminated (프로세스 종료)

 

• Non-preemptive(비선점형): 프로세스가 CPU를 사용하고 있다면 뺏지 못함.
• Preemptive(선점형): 프로세스가 CPU를 사용하고 있더라도 강제로 빼앗고 진행

1&4번은 Non-preemptive (자발적으로 감:비선점)

 

2&3번은 Premptive or Non-preemptive

 

우분투 환경 내 명령어로 context switching 확인

 

vmstat 명령어 : 프로세스, 메모리, 페이징, I/O 블럭, CPU 활동 사항들의 정보를 출력하는 명령어.

 cs부분을 체크하면 컨텍스트가 몇번 일어나는지도 확인 가능.(초단위)

ex) vmstat 2 3 (2초간 3번 출력)

 

선점/비선점 컨텍스트 스위칭 확인 명령어

cat / proc/1(프로세스 pid)/status

voluntary_ctxt_switches: 비선점 스위칭

nonvoluntary_ctxt_switches: 선점 스위칭

 

 

스케줄링의 목표

• CPU utilization: CPU 사용률 증가
• Throughput: 단일 시간 내 프로세스 완료 개수 증가
• Turnaround time: 실행에서 종료까지 시간 최소화
• Waiting time: ready queue에 대기시간 최소화
• Response time: 응답시간 최소화

 

디스패처(dispatcher)

 

스케줄링을 위해 CPU의 제어권을 선택된 프로세스에게 넘겨주는 모듈.

 

디스패처의 기능

1. Context Switching
2. kernel mode -> User mode로 전환
3. 중지된 작업을 재개할때 올바른 주소로 이동하게 도와준다.

dispatcher latency : 컨텍스트 세이빙,스토어 하는 시간

 

 

cpu scheduling 방법

• FCFS: 먼저 온것 위주로 처리
• SJF: 짧은 일을 먼저 시작(SRTF: 가장 짧게 남은 걸 먼저 시작)
• RR: 시분할
• Priority-based: 우선순위에 의한 스케줄링
• MLQ
• MLFQ 현대엔 다 이걸 사용

 

 

선입 선처리(FCFS)

 

 

CPU에 먼저 요청한 프로세스에 순서대로 배정(비선점)

 

Convoy effect(호위 효과)로 인해 cpu 장치 이용률 저하되는 결과가 나올 수 있음

Convoy effect(호위 효과): 프로세스들이 하나의 긴 프로세스가 cpu작업을 끝내고 양도하길 기다리는 것.

거대한 프로세스가 먼저 들어오면 뒤에 들어오는 프로세스가 오래 기다려야함.

 

 

SJF(Shortest JobFirst)

 

가장 작은 cpu burst시간을 가진 프로세스에게 우선적으로 CPU 할당.

 

burst시간이 동일할시엔 FCFS 적용.

 

 

최소 평균 웨이팅 시간을 가진다

 

하지만 컴퓨터 입장에선 프로세스가 얼만큼의 CPU burst시간을 가지는지 미리 알수가 없다.

 

 

그렇기에 엄격하게 정할 순 없고, 예측해서 하는것.

 

 

예측하는방법

과거를 통해 비교. 과거에 많이 썼냐 안썼냐로 지수적 평균을 내서 체크

 

 

선점이랑 비선점 둘다 가능하다.

 

 

SRTF(Shortest Remaining Time First)

 

위의 SJF를 선점형태로 한것.

 

다른 프로세스가 들어왔을때 현재까지 작업하고 남은 CPU burst와 새로 들어온 프로세스의 CPU burst와 비교하여 짧은 것을 우선 실행. 그 후 ready queue에서 가장 짧은 burst를 실행.

 

 

RR(Round Robin)

 

선점형 FCFS. 시간 할당량(time quantum)을 정의하고 그 시간에 의해 컨텍스트 스위칭 되는 스케줄링

 

(ready queue 형태는 circular queue)

 

 

프로세스의 cpu burst가 시간 할당량보다 적다면, 프로세스는 작업 후 자발적으로 cpu 사용을 끝내고 종료된다.

 

시간 할당량보다 크다면, 시간 할당량만큼 작업 후 운영체제에 인터럽트를 발생. 그 후 Context Switching이 일어나고 ready queue의 다음 프로세스가 cpu 사용.

 

 

시간 할당량이 매우 작게되면 context switching에 시간을 많이 쓰게 되고,

 

매우 크다면 FCFS와 같이 작동하게 된다.

 

 

Priority-base

 

 

우선순위에 따른 스케줄링.

 

선점형이 될수도 있고 비선점형이 될 수도 있음.

 

선점형: 새로 도착한 프로세스가 우선순위가 더 높으면 CPU를 선점.

비선점형: ready queue내에서 우선순위 정렬.

 

우선순위 결정법

 

우선순위는 내부적, 외부적으로 정의할 수 있다.

 

• 내부적 우선순위 결정
  • 제한 시간, 기억장소 요청량, 사용 파일 수, 평균 프로세서 버스트에 대한 평균 입출력 버스트의 비율(SJF)

• 외부적 우선순위 결정
  • 프로세스의 중요성, 사용료를 많이 낸 사용자, 작업을 지원하는 부서, 정책적 요인

 

 

이 스케줄링은 아래와 같은 문제가 발생할 수 있다.

• 무한 봉쇄(indefinite blocking) or 기아현상(starvation)
  • 어떤 프로세스가 우선순위가 낮아서 계속 뒤로 밀려 실행이 안되는 현상
  • 해결방법: aging 기법. 프로세스에 나이를 주어 시간이 지나면 우선순위를 올리는 방법. 언젠가는 높은 우선순위를 갖게되어 실행하게 된다.

일반적으론 RR- Priority 를 같이 적용.

 

: 우선순위 기준으로 실행하나, 우선순위가 같을땐 RR형태로 실행.

 

 

 

다단계 큐(MLQ: Multilevel Queue)

우선순위에 따라 여러개의 ready queue를 가지는 방법.

우선순위가 높은 큐부터 존재하는 프로세스 다 실행한 후 아래 큐를 실행하는 스케줄링.

큐들간의 절대적인 우선순위에 의해 기아현상 발생할 수도 있음.

이 경우엔 큐들 사이에 시간을 나누어 사용할 수도 있음.

 

 

다단계 피드백 큐(MLFQ:Multilevel Feedback Queue)

다단계 큐의 문제점을 해결하기

멀티레벨큐에서 각각의 우선순위 레디큐마다 타임 퀀텀을 다르게 줘서 처리(보통 우선순위 낮은 큐에 타임 퀀텀을 더 크게 줌)

상위의 큐에서의 프로세스가 타임퀀텀만큼 작업했지만 다 작업하지 못했다면, 더 낮은 우선순위 레디큐로 이동.

낮은 우선순위큐에서 너무 오래 대기하는 프로세스는 에이징을 통해 높은 우선순위큐로 이동도 가능하다.

 

실제론 현대적인 운영체제에선 프로세스를 사용하는게 아닌 쓰레드를 가지고 스케줄링 처리

O/S 커널 스레드에 방금까지 배운걸 적용

(유저 쓰레드는 쓰레드 라이브러리가 관리해줌)

 

 

 

Real-Time 운영체제에서 스케줄링

: 주어진 시간내에 해결해야하는 운영체제

 

소프트 리얼타임 vs 하드 리얼타임

소프트: 반드시 그 시간내에 끝내야하는게 아니라 중요하지않은 일이라면 일부 데이터는 누락이 되어 끝내도 된다.

하드: 반드시 그 시간내에 끝내야함.

 

 

참조

[주니온님의 인프런 운영체제강의(공룡책)](https://goodgid.github.io/What-is-Multi-Thread/)

[CPU 스케줄링 mu1616님 블로그](https://velog.io/@mu1616/CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81)

CPU 스케줄링 우선순위 결정 관련 참조

1. 단일 프로세서(CPU) 상에서 여러 개의 프로세스가 동시에 실행되는 것.
   [본문으로]