[혼공컴운] ch.11 CPU 스케줄링

11-1. CPU 스케줄링 개요

1. 프로세스 우선순위

• 프로세스마다 우선순위가 다름
  • 우선순위가 높을수록 빨리 처리해야함
• 입출력 집중 프로세스 : 입출력 작업이 많은 프로세스
  • 입출력을 위한 대기 상태에 더 많이 머무름
• CPU 집중 프로세서 : CPU 작업이 많은 프로세스
  • 대기 상태보다 실행 상태에 더 많이 머무름
• 프로세스의 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 하기 위해 OS는 프로세스마다 우선순위 부여.

2. 스케줄링 큐

• 스케줄링 큐(scheduling queue) : os가 CPU를 사용하고 싶은 프로세스들, 메모리에 적재되고 싶은 프로세스들, 특정 입출력장치를 사용하고 싶은 프로세스들을 모두 줄 세우는 것
  • 준비 큐 : CPU를 이용하고 싶은 프로세스들이 서는 줄
  • 대기 큐 : 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄

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

• 선점형 스케줄링(preemptive scheduling) : os가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식

  • 자원 독점 막고 골고루 자원 배분 가능
  • 문맥 교환 과정에서 오버헤드 발생 가능

• 비선점형 스케줄링(non-preemptive scheduling) : 하나의 프로세스가 자원을 사용하고 있을 경우 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 스케줄링 방식

  • 다른 프로세스가 자원이 당장 필요하더라도 기다려야함
  • 모든 프로세스가 골고루 자원을 사용할 수 없음
  • 오버헤드 빈도수는 선점형에 비해 적음

/

11-2. CPU 스케줄링 알고리즘

1. 스케줄링 알고리즘의 종류

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

• FCFS 스케줄링이라고도 불림
• 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링

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

• SJF 스케줄링이라고도 불림
• 준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식

3) 라운드 로빈 스케줄링(round robin scheduling)

• 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링
  • 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링

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

• SRT 스케줄링이라고도 함
• 최단 작업 우선 스케줄링 알고리즘 + 라운드 로빈 알고리즘 합친 스케줄링
  • 최단 작업 우선 스케줄링 : 작업 시간이 짧은 프로세스부터 처리
  • 라운드 로빈 알고리즘 : 정해진 타임 슬라이스만큼 돌아가며 CPU 사용하는 선점형 스케줄링 알고리즘

5) 우선순위 스케줄링(priority scheduling)

• 프로세스들에 우선순위 부여하고, 가장 높은 우선순위 가진 프로세스부터 실행하는 스케줄링 알고리즘

• 에이징(aging) : 오래 대기한 프로세스의 우선순위를 점차 높이는 방식

6) 다단계 큐 스케줄링

• 우선순위 스케줄링의 발전된 형태
• 우선순위별로 준비 큐를 여러 개 사용
• 우선순위가 가장 높은 큐에 있는 프로세스 먼저 처리, 우선순위가 가장 높은 큐가 비어 있으면 그다음 우선순위 큐에 있는 프로세스 처리

7) 다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)

• 다단게 큐 스케줄링과 유사하나 프로세스들이 큐 사이를 이용할 수 있다는 점에서 차이가 있음

4주차 추가 과제
Q. 준비 큐에 A, B, C, D 순으로 삽입되었다고 가정했을 때, 선입 선처리 스케줄링 알고리즘을 적용하면 어떤 프로세스 순서대로 CPU를 할당 받는가
A. A-B-C-D 순