CPU 스케줄링

https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard 

 

CPU 스케줄링?

운영체제가 프로세스들에게 공정하고 합리적으로 CPU자원을 배분하는 것으로 컴퓨터 전체 성능과 직결되는 중요한 문제

 

 CPU스케줄링의 목적? 

CPU 이용률을 극대화. 항상 어느 프로세스라도 CPU를 사용하고 있어야한다. 

   

 공정한  CPU스케줄링?

프로세스마다 우선 순위가 다름. 빨리 처리해야하는 프로세스가 있고, 천천히 해도 되는 프로세스도 있다.

이것은 사용자가 설정할 수도 있고, 운영체제에서 정해준 우선 순위도 있다.

 

우선순위가 높은 프로세스 : 입출력 작업이 많은 프로세스(IO BOUND)

우선순위가 낮은 프로세스 : CPU 작업이 많은 프로세스

 

IO BOUND는 CPU집중 프로세스에 비해 대기상태에 더 많이 머문다. 실행상태보단 대기에 더 많이 머문다. 

IO BOUND프로세스의 우선 순위를 높여 빨리 처리해주는게 기아 상태를 방지 할 수 있다. 

 

입출력 집중 프로세스는 CPU를 잠깐 쓰고 대기 상태에 머물기 때문에 우선순위를 높여 먼저 빨리 끝내게 해주고, CPU집중 프로세스에게 턴을 넘겨 이 프로세스가 CPU를 사용 할 수 있게 해준다.

 

입출력 중신의 프로그램은 짧은 CPU BURST를 가져간다.

CPU지향 프로그램은 긴 CPU BURST를 가져간다. 

 

CPU할당: IO BOUND -> CPU BOUND

 

[ 용어 정리]-----

- BURST 버스트 : 계속되는 작업, 작업처리에 요구되는 시간, 작업시간 

- IO : INPUT, OUTPUT. 파일을 읽고 쓰거나 데이터를 주고 받는, 입출력 장치와 데이터를 추고 받는 것.

- CPU BURST: 프로세스가 CPU에서 한 번에 연속적으로 실행되는 시간

- IO BURST : 프로세스가 IO 작업을 요청하고 그 결과를 기다리는 시간, IO를 실행하는 기간

장치의 속도가 느리다. CPU BURST보다 느림

-----

 CPU 스케쥴러?

메모리에 있는 프로세스들 중 실행할 준비가 되어있는 READY상태의 프로세스를 선택하고 그 프로세스를 CPU에 할당하는 것.

즉, 실행 준비가 되어있는 메모리 내 프로세스 중 적절한 프로세스를 선택하고 CPU를 할당 하는 것

 

 CPU스케쥴링 결정은 다음 상황에서 발생한다.

- 한 프로세스가 실행에서 대기로 전환 할 때 (비선점)

- 프로세스가 실행에서 준비 완료 상태로 전환 될 때 (선점)

- 프로세스가 대기에서 준비 완료 상태로 전환 될 때 (선점)

- 프로세스 종료시 (비선점)

 

선점: 경쟁, 효율적으로 CPU를 사용하기 위해 스케줄링을 고민한다.

비선점 : CPU가 한 프로세스에 할당이 되면 프로세스 종료, 혹은 대기 상태가 돼서 CPU를 놓아줄 때까지 점유한다. 

 

 

프로세스 우선순위

입출력 집중 프로세스의 우선순위는 CPU집중 프로세스의 우선순위보다 높다.

 

운영체제가 우선순위를 부여한다. 이것은PCB에 저장된다.

운영체제는 PCB를 기반으로 프로세서가 CPU를 얼마나 활용하는지 파악, 우선순위를 정한다.

우선순위가 높다면 더 빨리 더 자주 실행된다.

 

우선순위 정하는 방법:

스케줄링 큐 : 어떤 자원을 사용하고 싶어하는 프로세스들이 서는 줄.

운영체제는 프로세스가 자원이 필요하다고 하면, 스케줄링큐는 줄을 서라고 한다.

큐는 선입선출인데, 스케줄링큐는 선입선출일 필요 없다. 

준비큐 : 준비 상태에 접어든 프로세스. 언제든 할당받아 실행 가능하나 순서가 안 온 상태.

대기큐 : 대기 상태에 접어든 프로세스, 입출력을 해야해 지금 당장 CPU를 사용할 필요는 없다.

 

우선 순위가 다르기 때문에 먼저 준비, 대기를 한다고 지금 당장 CPU를 사용하는게 아니다. 

 

각각의 자원별로 큐를 따로 만든다. 대기가 편하게. 

같이 대기하다가 작업 완료 시, 대기 큐에서 나와 준비큐로 들어간다.

입출력이 완료돼 완료 인터럽트가 발생하면 운영체제는 대기큐에서 작업이 완료된 PCB를 찾고, 이 PCB의 상태를 대기에서 준비 상태로 변경한 다음 대기큐에서 제거하고, 준비큐로 넣어준다.

디스패치: 준비 리스트 맨 앞에 있던 프로세스가 CPU를 점유하게 되는 것, 즉 준비 상태에서 실행 상태로 바뀌는 것을 디스패치라고 한다 

 

 선점형과 비선점형

프로세스가 자원을 할당받아 CPU를 사용하고 있는데 다른 프로세스가 자원을 요구한다면?

뺏기 OR 기다리기

 

선점형: 선점 = 남보다 앞서 차지함. 우선순위가 높은 프로세스가 언제든 뺏을 수 있다. CPU독점 불가. 정해진 시간을 쓰게 하고 타임 아웃 인터럽트를 사용해 관리.

자원 독점 방지, 프로세스들에게 골고루 자원을 분배한다는 장점이 있다

잦은 문맥교환 발생으로 인한 오버헤드 발생 가능성이 높아진다는 단점이 있다

 

비선점: 프로세스가 종료되거나 대기 상태에 들어가기 전까지 이 프로세스가 사용하고 있는 자원을 빼앗을 수 없다. 사용할 수 없다. 대기해야함.

문맥교환에서 발생하는 오버헤드가 적다는 장점이 있지만, 모든 프로세스가 골고루 자원을 이용하기 어렵다는 단점이 있다.

 

디스패처와 디스패치는 뭐가 다를까... 같은건가

디스패처 : CPU스케줄링에 포함된 기능. CPU제어를 단기 스케줄러가 선택된 프로세스에게 전해주는 모듈이다.

프로그램 시작하기 위해 유저 프로그램을 적당한 위치로 이동시키는 것. 문맥교환의 일종

 

 

 

알고리즘 선택 기준: 

CPU 이용률: 높을 수록 효율적. CPU를 항상 바쁘게 유지

처리량: 높을 수록 효율적. 일정 시간 내에 처리된 프로세스의 개수

총 처리 시간: 낮을 수록 효율적. 프로세스의 제출 시간과 완료 시간의 간격

대기 시간: 낮을 수록 효율적. 준비 완료 큐에서 대기하며 보낸 시간의 합

응답시간: 낮을 수록 효율적. 하나의 요구를 제출한 후 첫번째 응답이 발생할 때까지의 시간. 

 

좋은 스케줄링의 기준: CPU이용률이 높을 수록, 처리량이 많을 수록

 총 처리 시간, 대기시간, 응답시간이 적을수록, 빠를수록 

 

스케줄링 알고리즘

 선입선처리 스케줄링

= FCFS(FIRST COME FIRST SERVED) 

단순히 준비 큐에 온 순서대로 처리하는 비선점 스케줄링

먼저 CPU를 요청한 프로세스부터 할당

가장 간단한 형태이고 코드 작성이 쉽고 이해하기 쉽다.

비선점이므로 시분할에 부적합. 

프로세스들이 기다리는 시간이 매우 길어지는 호위효과가 나타날수도

 

 최단 작업 우선 스케줄링

= SJF (SHORTESSET JOB FIRST)

CPU BURST가 짧은 것이 먼저 실행.

호위 효과를 방지하기 위해 CPU사용 시간이 짧은 걸 먼저 실행한다.

 

 라운드로빈 스케줄링

=RR (ROUND ROBIN)

선입 선처리 + 타임 슬라이스

타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간.

정해진 타임 슬라이스만큼의 시간 동안 CPU를 사용하는 선점형 스케줄링.

정해진 시간을 모두 사용했음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입 (문맥교환)

시분할 시스템에 최적화.

시간 할당량(=타임슬라이스)이 너무 크다면, 선입선처리와 동일 알고리즘이 되어 호위 효과가 발생. 시간이 너무 작다면, 문맥교환에 시간을 뺏긴다. 

 

 최소 잔여 시간 우선 스케줄링

=SRT ( SHORTEST REMAINING TIME)

최단 작업 우선 스케줄링 + 라운드 로빈

최단 작업 우선 스케줄링 : 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘

라운드 로빈 : 타임 슬라이스를 받아 돌아가며 CPU 스케줄링

정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스는 남은 작업 시간이 가장 적은 프로세스 선택.

 

 우선순위 스케줄링

프로세스들에게 우선 순위를 부여, 우선 순위 높은 프로세스부터 실행.

우선순위가 같다면 먼저 들어온 프로세스부터 처리.

내부적 정의 (시간 제한, 메모리 요구 ) 활용가능

외부적 정의 ( 프로세스의 중요성 ) 활용가능

무한 봉쇄, 기아 상태 발생 가능( AGING 고려)

우선순위가 낮은 것들은 실행되지 못할 수도 있다.

 

우선순위가 낮은 것들은 실행이 연기되고, 실행되지 못할수도,

->방지하기 위한 기법 : 에이징 AGING 

오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식. 

대기 중인 프로세스의 우선 순위를 마치 나이 먹듯 점차 증가시키는 방법.

우선순위가 낮아도 언젠간 우선순위가 높아지고, 실행된다. 

기아현상 해결하기 위해 사용

 

 다단계 큐 스케줄링

우선순위 스케줄링의 발전된 형태

우선순위 별로 준비 큐를 여러개 사용하는 스케줄링 방식

우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리

우선순위가 비어있으면 그 다음 우선순위 큐에 있는 프로세스 처리

프로세스 타입에 따라 포그라운드 (대화형), 백그라운드( 일괄처리) 로 나누어 프로세스 분류.

쿠별로 별도의 스케줄링 알고리즘을 가진다. 포그라운드 -RR, 백그라운드 - FCFS.

각 큐는 낮은 우선순위 큐보다 절대적인 우선순위를 가진다.

각 큐는 일정비율로  CPU 시간을 나누어 사용한다.

 포그라운드 큐 : RR. CPU시간의 80%

 백그라운드 큐: FCFS, CPU 시간의 20%

큐 별로 스케줄링을 달리 적용해 유형별로 처리하는게 쉬워진다.

단, 다단계 큐에선 기본적으로 프로세스가 큐간 이동이 불가하다 -> 기아현상 발생

한 번 우선순위 낮은 프로세스는 계속 낮은 우선순위의 큐에 머문다. 

 

  다단계 피드백 큐 스케줄링 

 다단계 큐 스케줄링의 발전된 형태.

큐 간의 이동이 가능한 다단계 큐.

프로세스를 CPU BURST성격에 따라 분류.

에이징을 통해 기아 상태 예방.

새롭게 준비 상태가 된 프로세스가 있으면 얘를 가장 우선순위가 높은 큐에 삽입한다.

CPU를 많이 사용하는 프로세스일수록 우선순위가 낮아지게 만든다. 

어떤 프로세스가 낮은 순위 큐에 너무 오래 머물면 우선순위를 높게 만든다.

CPU스케줄링 방식으로 알려져있다.