CPU 스케줄링

CPU 스케줄링 개요

• 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
• 컴퓨터 선응과도 직결

프로세스 우선 순위

• 우선 순위가 높은 프로세스 순서대로 이용
• 우선 순위가 높은 프로세스들 : 대표적으로 입출력 작업이 많은 프레세스
• 입출력 집중 프로세스 : 비디오 재생이나 디스크 백업 작업 같이 입출력 작업이 많은 프로세스
• CPU 집중 프로세스 : 복잡한 수학 연산, 컴파일, 그래픽 처리 작업 같이 CPU 작업이 많은 프로세스

  CPU 집중 프로세스와 입출력 집중 프로세스가 동시에 CPU 자원을 요구했다고 가정하면, 입출력 집중 프로세스를 가능한 빨리 실행시켜 입출력 장치를 끊임없이 작동시키고, 그 다음 CPU 집중 프로세스에 집중적으로 CPU를 할당하는게 더 효율적
  => 각각의 상황에 맞게 CPU를 배분하는것이 중요
  -> 운영체제는 각 프로세스의 PCB에 우선순위를 명시

스케줄링 큐

• 프로세스들에 '줄을 서서 기다릴 것'을 요구
• 준비 큐 : CPU를 이용하고 싶은 프로세스
• 대기 큐 : 입출력장치를 이요하기 위해 대기 상태에 접어든 프로세스
• 입출력이 완료되어 완료 인터럽트가 발생하면,
  1. 대기 큐에서 작업을 끝낸 PCB를 준비상태로 변경
  2. 대기 큐에서 제거
  3. 준비 큐로 이동

선점형과 비선점형 스케줄링

CPU를 사용 중인 프로세스로 부터 CPU 자원을 빼앗아 다른 프로세스에 할당하거나, CPU를 사용 중인 프로세스의 작업이 끝날 때까지 다른 급한 프로세스를 기다리게 하는걸 선점형 스케줄링과 비선점형 스케줄링 이라고 함.

• 선점형 : 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 포로세스에 할당
  * 장점 : 자원 독점을 막고, 프로세스들에 골구루 자원을 배분
  • 단점 : 문맥 교환 과정에서 오버헤드 발생 가능성이 높음
• 비선점형 : 어떤 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들수 없음
  * 장점 : 오버헤드 발생 가능성은 선점형보다 적음
  • 단점 : 당장 자원을 사용해야 하는 상황에서도 무작정 기다려야함.

CPU 스케줄링 알고리즘

• CPU 스케줄링 알고리즘는 매우 다양하고 운영체제마다 다른 알고리즘 사용.

스케줄링 알고리즘의 종류

1. 선입 선처리 스케줄링(FCFS : First Come First Served Scheduling)

   • 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식
   • CPU를 먼저 요청한 프로세스부터 CPU를 할당
   • 떄떄로 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 점에서 부작용이 존재(호위 효과)

2. 최단 작업 우선 스케줄링(SJF : Shortest Job First Scheduling)

   • 호위 효과를 방지하기 위한 방식
   • CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행
   • 기본적으로 비선점형으로 분류되지만, 선점형으로도 구현가능

3. 라운드 로빈 스케줄링(Round Robin Scheduling)

   • 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 방식
   • 타임 슬라이스는 CPU를 사용할 수 있는 정해진 시간을 의미
   • 선점형 스케줄링
   • 큐에 삽입된 프로세스들은 삽인된 순서대로 CPU를 이요하되 정해진 시간만큼만 CPU를 이요하고, 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입됨=> 문맥 교환 발생
   • 타임 슬라이스 크기가 매우 중요!!!

4. 최소 잔여 시간 우선 스케줄링(SRT : Shortest Remaining Time)

   • 선점형 스케줄링
   • 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로ㅔㅅ스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택

5. 우선 순위 스케줄링(Priority Scheduling)
   가장 높은 우선순위를 가진 프로세스부터 실행
   우선순위가 높은 프로세스만 계속 먼지 실행되다보니 우선 순위가 낮은 프로세스의 실행은 계속 밀릴 수 있음 => 기아 현상
   * 기아 현상을 방지하기 위해 에이징이라는 기법이 존재
   오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

6. 다단계 큐 스케줄링

   • 우선순위 스케줄링의 발전된 형태
   • 준비 큐를 여러개 사용하여, 유형별로 우선순위를 구분하여 실행

7. 다단게 피드백 큐 스케줄링

   • 다단계 큐 스케줄링의 발전된 형태
   • 다단계 큐에서는 프로세스들이 큐 사이를 이동할 수 없어서, 우선 순위가 낮은 프로세스는 계속 연기될 여지가 존재 => 기아 현상
   • 큐 사이를 프로세스들이 이동 가능
   • CPU를 오래 사용해야하는 프로세스는 점차 우선순위가 낮아짐
   • 낮은 우선순위 큐에서 너무 오래 기다리면 높은 우선순위 큐로 이동