[운영체제] 6. CPU 스케줄링

프로세스 스케줄링

 

CPU 스케줄링

- CPU 스케줄러는 프로세서 스케줄러라고도 한다

- 여러 프로세스가 번갈아 사용하는 자원을 어떤 시점에 어떤 프로세스에 할당할지 결정

- 어떤 작업에 CPU를 배정할지 결정하는 것

- 컴퓨터 시스템의 효율은 어떤 프로세스에 CPU를 먼저 배정하느냐에 따라 달라지므로 형평성과 효율성을 결정하는 중요한 일

- CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일

- 대상 : 준비큐에 들어온 프로세스

 

 

스케줄링의 목적

• 공평성 :  모든 프로세스가 자원을 공평하게 배정받아야하며, 자원 배정 과정에서 특정 프로세스가 배제되어서는 안된다.
• 효율성 : 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.
• 안정성 : 우선순위를 사용해 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호
• 확장성 : 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치하고 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야한다.
• 반응시간 보장 : 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응
• 무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어서는 안된다.

스케줄링의 단계

• [1단계] 고수준 스케줄링 : 작업 선택
  • 시스템 내 전체 작업 수를 조절, 동시에 실행 가능한 프로세스의 총 개수 정함
  • 어떤 작업을 시스템이 받아들일지 또는 거부할지를 결정
  • 작업 스케줄링에 따라 작업 프로세스로 나눠 생성, 수행 빈도가 적어 장기 스케줄링에 해당
•  [2단계] 중간 수준 스케줄링 : 사용 권한 부여

  • 중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절해 과부하를 막는다.

  • 일부 프로세스를 중지 상태로 옮김으로써 나머지 프로세스가 원만하게 작동할 수 있도록 지원한다,

  • 프로세스의 상태 중 보류에 해당하며, 저수준 스케줄링이 원만하게 이뤄지도록 완충하는 버퍼 역할을 한다.

• [3단계] 저수준 스케줄링 : 준비 상태의 프로세스에 프로세서 할당(디스패치)

  • 실제로 작업이 이뤄진다.

  • 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 일

  • 디스패처(새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경 설정을 하는 커널 모듈)가 준비 상태에 있는 프로세스 중에서 프로세서 할당할 프로 세스 결정하는 프로세스 할당 스케줄링

 

버스트

•  

고려사항

• 선점형 스케줄링와 비선점형 스케줄링

	선점형	비선점형
개념	어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식	어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식
작업 방식	실행 상태에 있는 작업을 중단시키고 새로운 작업을 실행 가능	CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적다.
장점	프로세스가 CPU를 독점할 수 없어 대화형이나 시분할 시스템에 적합	CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적다.
단점	문맥 교환의 오버헤드가 많다.	기다리는 프로세스가 많아 처리율이 떨어진다.
사용	시분할 방식 스케줄러에 사용	일괄 작업 방식 스케줄러에 사용
중요도	높다	낮다

 

프로세스 우선순위

- 우선 순위가 높다는 것은 더 빨리 자주 실행된다는 의미

- 시스템에는 다양한 우선순위의 프로세스가 공존하며, 우선순위가 높은 프로세스가 CPU를 먼저, 더 오래 차지한다.

- 높은 프로세스 : 커널, 전면, 대화형, 입출력 집중

- 낮은 프로세스 : 일반, 후면, 일괄 작업, CPU 집중

 

 

CPU 집중 프로세스와 입출력 집중 프로세스

전면 프로세스와 후면 프로세스

다중큐

- 프로세스를 효율적으로 관리하기 위해 큐를 여러 개 두어 관리하는 것

- 준비상태에서는 우선순위에 따라 다중 큐를 운영하고, 대기 상태에서는 같은 입출력을 요구한 프로세스들을 모아 다중큐를 운영한다.

 

 

스케줄링 알고리즘 선택 기준

• CPU 사용률 : 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
  
• 처리량 : 단위 시간 당 작업을 마친 프로세스의 수
• 대기시간 : 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간
• 응답시간 : 프로세스 시작 후 첫번째 출력 또는 반응이 나올 때까지 걸리는 시간
• 반환 시간 : 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간

 

비선점형 알고리즘

1. FCFS 스케줄링

- 준비 큐에 도착한 순서대로 CPU를 할당하는 방식

- 프로세스가 큐에 도착한 순서대로 실행되며, 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있다.

- 큐가 하나라 모든 프로세스는 우선순위가 동일하다.

- 콘보이(호위) 효과 : 단순하고 공평하지만, 처리시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들을 하염없이 기다려 시스템의 효율이 떨어지는 문제

- 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어진다.

 

2. SJF 스케줄링

- 준비큐에 있는 프로세스 중에서 실행시간이 가장 짧은 작업부터 CPU를 할당하는 방식

- 프로세스에 CPU를 배정할 때 시간이 오래 걸리는 작업이 앞에 있고 간단한 작업이 뒤에 있으면 그 순서를 바꿔 실행

- 운영체제가 프로세스의 종료 시간을 정확히 에측하기가 어려워 사용하기가 힘들다.

- 실행시간이 긴 작업이 계속 연기되어 아사현상이 일어날 수 있다.

 

3. HRN 스케줄링

- SJF 스케줄링에서 발생할 수 있는 아사현상을 해결하기 위해 만들어진 비선점형 알고리즘

- 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려해 스케줄링하는 방식

- 우선순위 = (대기 시간 + CPU 사용시간) / CPU 사용시간

 

 

선점형 알고리즘

1. 라운드 로빈 스케줄링

- 한 프로세스가 할당받은 시간(타임 슬라이스)동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식

- 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행

- 평균 대기 시간이 같다면 문맥 교환 시간이 추가되어 비효율적

- 문맥 교환에 따른 추가 시간을 고려해 타임 슬라이스를 적절히 설정해야 한다.

- 타임 슬라이스가 너무 크면 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보인다.

- 타임 슬라이스가 작은 경우 사용자는 여러 프로스램이 동시에 실행되는 것처럼 느끼고, 문맥 교환에 많은 시간을 낭비해 실제 작업을 못하는 문제가 발생

 

2. SRT 스케줄링

- SJF 스케줄링과 라운드 로빈 스케줄링 방식을 혼합한 방식

- 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당박을 프로세스를 선택할 때 남아 있는 작업이 가장 적은 프로세스 선택

- 남은 시간이 적은 프로세스에 CPU 먼저 할당

- 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야하므로 SJF에는 없는 작업이 추가

- 운영체제가 프로세스의 종료 시간을 정확히 에측하기가 어렵고, 아사현상이 일어날 수 있다.

 

3. 다단계 큐 스케줄링

- 고정형 우선순위에 따라 준비 큐를 여러 개 사용하는 방식

- 프로세스는 운영체제로 부터 부여받은 우선순위에 따라 해당 우선순위 큐에 삽입

- 우선순위에 따라 타임슬라이스를 조절 해 작업효율을 높일 수 있다.

 

4. 다단계 피드백 큐 스케줄링

- 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점 보완한 방식

- CPU를 사용하고 난 프로세스는 원래의 큐로 돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.

- 우선순위가 낮은 큐의 타임슬라이스를 크게 설정

 

 

둘 다 가능

1. 우선순위 스케줄링

- 프로세스는 중요도에 따라 우선순위를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘

- 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현

- 시스템의 효율성이 아닌 프로세스 중요도를 기준으로 결정 

- 고정 우선순위 알고리즘 : 단순하게 구현할 수 있지만 시시각각 변하는 시스템의 상황을 반영하지 못해 효율성이 떨어진다.

- 변동 우선순위 알고리즘 : 일정 시간마다 우선순위를 새로 계산하고 이를 반영하기 때문에 시스템이 복잡하지만 시스템의 상황을 반영해 효율적인 운영이 가능하다.

 

 

https://velog.io/@pa324/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81