[운영체제-양희재 교수님]7-9강 CPU 스케줄링 알고리즘

Posted Oct 21, 2022

By your_full_name 9 min read

CPU Scheduling

Preemptive(선점, 先占) vs. Non-preemptive(비선점, 非先占)
- 선점은 이미 실행 중인 프로세스를 강제로 끝내버리고 스케줄링을 진행 가능
- 비선점은 프로세스가 IO를 만나거나 종료되기 전까지 스케줄링을 진행하지 않음
Scheduling criteria: 스케줄링에 사용할 기준
- CPU Utilization(CPU 이용률): CPU가 놀지 않고 일하는 비율(%)
- Throughput(처리율): 단위 시간당 처리하는 작업량(jobs/time)
- Turnaround time(반환 시간): 메인 메모리로 들어간 작업이 끝나서 다시 나오는 데까지 걸리는 시간(time)
- Waiting time(대기 시간): Ready queue에서 대기한 시간(time)
- Response time(응답 시간): 처음 응답이 나오기까지 걸리는 시간(time)
  - 주로 interactive system에서 중요
- 이외에도 여러 기준 존재

Simple & Fair
- 가장 간단하며 공평한 방법이지만 가장 좋은 성능을 보장하지는 않음
대기 시간을 기준으로 보는 경우 ⇒ 비효율적
- 만약 오래 걸리는 작업이 가장 먼저 오고 그 이후로 짧은 시간이 걸리는 작업이 온다면 이 작업은 앞서 온 오래 걸리는 작업을 기다림 ⇒ Average Waiting Time 증가
- 대기 시간 측면에선 짧게 걸리는 작업을 먼저 하는 게 낫다.
Convoy Effect (호위 효과)
- 오래 걸리는 작업 뒤에 짧게 걸리는 작업이 호위하는 것처럼 따라다니는 것과 같은 현상
Non-preemptive scheduling
- 오래 걸리는 작업을 강제 종료하고 짧게 걸리는 작업을 먼저 할 수 없다.

실행 시간이 가장 짧은 작업을 먼저 수행 ⇒ 평균 대기 시간 감소
Provably optimal
- 증명된 최적의 방법(대기 시간 감소 기준)
Not realistic; prediction may be needed
- 실제 실행 시간을 알 수 없기 때문에 예측값을 사용해야 한다.
- 예측을 위해 과거 실행 기록을 저장하고 값을 계산하려다 보면 오버헤드 발생 ⇒ 결과적으로 잘 사용하지 않음
Preemptive or Non-preemptive 둘 다 가능
- Preemptive의 경우 남은 시간이 주기적으로 갱신된다.
- Preemptive SJF = Shortest-Remaining-Time-First (최소 잔여 시간 우선)

Priority(우선순위)
- typically an integer number
- Low number represents high priority in general(Unix/Linux)
Priority는 어떻게 정하는가
- Internal(내부적 요소)
  - time limit
    - 짧은 시간 안에 완료될 수 있는 작업이 우선순위가 높다.
  - memory requirement
    - 메모리를 적게 차지하는 작업이 우선순위가 높다.
  - i/o to CPU burst
    - IO 사용 시간이 길고 CPU 사용 시간이 짧은 작업이 우선순위가 높다.
- External(외부적 요소)
  - amount of funds being paid
    - 예) 서버 컴퓨터에 투자를 많이 한 부서의 작업이 우선순위가 높다.
  - political factors(정치적 요소)
    - 예) 숙제 업무보단 입시 업무의 우선순위가 더 높다.
Preemptive or Non-preemptive 둘 다 가능
Problem
- starvation(기아)
  - Indefinite blocking
  - 프로세스가 우선순위가 낮아 아무리 기다려도 자신의 차례가 오지 않는 경우
- Solution) aging
  - 프로세스가 오래 기다릴수록 우선순위를 높이는 방법

Time-sharing system(시분할/시공유 시스템)에서 많이 사용
Time quantum(시간 양자) = time slice
- 일반적으로 10~100msec
- 시간을 time quantum으로 나누어 그 기간만큼 프로세스를 작업
Preemptive scheduling
- time quantum 뒤에 자동으로 프로세스를 종료하기 때문에 Non-preemptive 불가
Performance depends on the size of the time quantum
- time quantum에 따라 성능이 좌우된다.
- ∆ → ∞) FCFS
- ∆ → 0) Processor sharing
  - 프로세스가 동시에 실행되는 것처럼 보임
  - context switching overhead 부담 증가
    - context switching overhead: 기존의 프로세스 작업 내역을 저장하고, 새로운 프로세스의 작업 내역을 불러오는 데 걸리는 시간
Preemptive SJF와 차이점
- Preemptive SJF는 매번 최소 잔여 시간 프로세스를 작업하지만, Round-Robin은 그런 계산 없이 순서대로 작업

프로세스 그룹에 따라 우선순위를 다르게 매겨서 그에 따라 실행하는 방법
Process groups
- System processes
  - OS 내부에서 OS가 하는 작업
  - 가장 중요한 프로세스
  - 예) 가상 메모리 매핑, 통신 등
- Interactive processes
  - 게임, 워드 등 사용자와 대화하는 프로세스
  - 사용자 프로세스 중 Batch processes보다 중요
- Interactive editing processes
- Batch processes
  - 대화형이 아닌 프로세스
  - 꾸러미로 일관적으로 처리하는 프로세스
- Student processes
Single ready queue → Several separate queues
- 프로세스 그룹마다 queue 할당
- 각각의 Queue에 절대적 우선순위를 매겨 그에 따라 실행 또는 CPU time을 각 Queue에 차등 배분하여 실행
- 각 Queue는 독립된 scheduling 정책을 채택할 수 있다.

복수 개의 Queue 사용
- 각 Queue는 독립된 scheduling 정책을 채택할 수 있다.
다른 Queue로 점진적 이동
- 모든 프로세스는 하나의 입구로 진입
- 너무 많은 CPU time 사용 시 다른 Queue로 이동시킴
- 기아 상태 우려 시 우선순위 높은 Queue로 이동시킴

프로세스는 프로세스에 의해 만들어진다.
- 부모 프로세스(Parent process)
  - 최초의 부모 프로세스는 부팅 이후 만들어진다.
- 자식 프로세스(Child process)
  - 부모가 같은 프로세스 ⇒ Sibling processes
- 부모-자식 관계는 트리처럼 생겨난다 ⇒ 프로세스 트리(process tree)
Process Identifier(PID)
- 프로세스에 붙은 고유한 번호
- Typically an integer number
  - 최초의 부모 프로세스의 PID는 0
- cf. PPID(Parent PID)
프로세스 생성
- fork() system call
  - 새로운 프로세스 생성
  - 부모 프로세스 복사
- exec()
  - 만들어진 프로세스의 실행 파일을 메모리로 가져오기

프로세스 종료
- exit() system call
- 해당 프로세스가 가졌던 모든 자원 및 권한은 OS에게 반환(메모리, 파일, 입출력장치 등)

This post is licensed under CC BY 4.0 by the author.