[OS] 5-1. 프로세스 스케줄링 (Process Scheduling)

목차

1. 스케줄링의 목적
2. 스케줄링 기준 및 단계
3. 스케줄링 정책
4. 기본 스케줄링 알고리즘들
5. Case study

---

다중 프로그래밍

여러개의 프로세스가 시스템 내 존재
자원을 할당 할 프로세스를 선택 해야 함 --> 스케줄링 

자원 관리

시간 분할 (time sharing) 관리

• 하나의 자원을 여러 스레드들이 번갈아 가며 사용
• 예 ) 프로세서 
• 프로세스 스케줄링 (Process scheduling) : 프로세서 사용시간을 프로세스들에게 분배

공간 분할 (space sharing) 관리

• 하나의 자원을 분할하여 동시에 사용
• 예 ) 메모리 (memory)

---

스케줄링(Scheduling) 의 목적

시스템의 성능(perfornamce) 향상

 

대표적 시스템 성능 지표 (index)

• 응답시간 (response) : 작업 요청(submission) 으로부터 응답을 받을때까지의 시간 (real-time system)
• 작업 처리량 (throughput) : 단위 시간 동안 완료된 작업의 수 (일괄처리시스템(batch-system))
• 자원 활용도 (resource utilization) : 주어진 시간 (Tc) 동안 자원이 활용된 시간 (Tr) (Utilization = Tr/Tc) (비싼장비..?)

목적에 맞는 지표를 고려하여 스케줄링 기법을 선택 (위 성능 지표중에 어느것이 제일 중요한가를 생각할 때 목적에 맞추어 생각해야 한다.)

 

시스템 성능 지표들

• 평균 응답 시간 (mean response time) : 사용자 지향적, 예 ) interactive systems
• 처리량 (throughput) : 시스템 지향적, 예 ) batch systems
• 자원 활용도 (resource utilization)
• 공평성 (fairness) : 예 ) FIFO
• 실행 대기 방지 : 무기한 대기 방지
• 예측 가능성 (predictability) : 적절한 시간안에 응답을 보장하는가

• 자원 할당의 공정성 보장
• 단위시간당 처리량 최대화
• 적절한 반환시간 보장
• 예측 가능성 보장
• 오버헤드 최소화
• 자원 사용의 균형 유지
• 반환시간과 자원의 활용 간에 균형 유지
• 실행 대기 방지
• 우선순위
• 서비스 사용 기회 확대
• 서비스 수 감소 방지
•  

대기시간, 응답시간, 반환시간

반환시간, 대기시간, 응답시간의 관계

 

스케줄링 기준 (Criteria)

스케줄링 기법이 고려하는 항목들

• 프로세스 (Process) 의 특성 : I/O bounded or compute bounded
• 시스템 특성 : Batch system or interactive system
• 프로세스의 긴급성 (urgency) : Hard or soft real time, non real time systems
• 프로세스 우선순위 (priority)
• 프로세스 총 실행 시간 (total service time)

 

CPU burst vs I/O burst

• 프로세스 수행 = CPU 사용 + I/O 대기
• CPU burst : CPU 사용 시간 (CPU buurst time이 더 긴 경우 compute-bounded process라 한다)
• I/O burst : I/O 대기 시간 (I/O 가 더 긴 경우 I/O bounded process 라 한다.)
• Burst time 은 스케줄링의 중요한 기준 중 하나

 

스케줄링의 단계 (LEVEL)

Long-term Scheduling

• Job scheduling : 시스템에 제출 할 (Kernel 에 등록 할) 작업 (Job) 결정 (Admission scheduling, High level scheduling)
• Job scheduling은 다중프로그래밍 정도 (degree) 조절 : 시스템 내에 프로세스 수 조절

I/O bounded 와 compute bounded 프로세스들을 잘 섞어서 선택해야 함

컴퓨터에는 CPU가 있고 I/O device들이 있을 것이다. 

CB만(CPU) 굴린다면 I/O device들은 작동하지 않을 것이고 비 효율적이다.

반대경우도 마찬가지

이 경우들은 비효율적이다. 결론은 효율을 높이기 위해 둘다 잘 섞어 쓰는 것이 좋다.

시분할 시스템에서는 모든 작업을 시스템에 등록 : Long term scheduling 이 덜 중요하다.

프로세스: Job이 커널에 등록되서 Process가 된다.

Job Scheduling: Job이 처리되기 위해 대기되어 있고 이 중에서 어떤 Job을 우선순위로 등록할 것인지 결정하는 것

 

Mid-term Scheduling

메모리 할당 결정 (memory)

• Intermediate level scheduling
• Swapping (swap in/swap out)

Process State에 대해서 공부하였을 때 suspend에서 ready로 가는 과정에 메모리를 할당한다. 

suspended ready에서 누구에게 메모리를 줄지 결정하는 것을 메모리 할당 결정이라고 한다. 

Job 스케쥴링이 시스템에 들어오는 빈도보다 자주 일어남. 

 

Short-term Scheduling

Process scheduling

• Low level scheduling
• 프로세서를 할당할 프로세스를 결정(Processor scheduler, dispatcher)

가장 빈번하게 발생

Interrupt, block (I/O), time out, Etc.

매우 빨라야 함

프로세서를 할당해주는 스케쥴링 --> short-term 

자주 일어나니까 프로세스 스케줄링이 느리면 시스템 전반적으로 느려진다. 

느리면 어떻게 될까?

CPU 100ms 를쓰는 스케줄링을 위해 10ms가 추가로 필요하다면 총 프로세스가 일하는 시간은 110ms가 된다.

이때 10ms 는 오버헤드가 되고 약 9%가 오버헤드가 된다. (10/110 * 100= 9%)

즉 스케줄링에 필요한 시간이 오래걸리면 문제가 된다.

 

스케줄링의 단계 (Level)

 

스케줄링 정책 (Policy)

• 선점 vs 비선점 (Preemptive scheduling, Non preemptive scheduling)
• 우선순위 (Priority)

Preemptive / Non preemptive scheduling

Non preemptive scheduling (비선점 스케줄링)

• 할당 받을 자원을 스스로 반납할 때까지 사용
• 예 ) system call, I/O,
• 장점 : Context switch overhead 가 적음 
• 단점: 잦은 우선순위 역전, 평균 응답 시간 증가 (계속 사용하기 때문에..)

Preemptive scheduling

• 타의에 의해 자원을 빼앗길 수 있음
• 예 ) 할당 시간 종료 , 우선순위가 높은 프로세스 등장
• Context switch overhead 가 큼 => 시스템에 부하가 크다.
• Time sharing system, real time system 등에 적합 => 응답성 증가

 

Priority

프로세스의 중요도

Static priority (정적 우선순위)

• 프로세스 생성시 결정된 priority 가 유지 됨
• 구현이 쉽고 , overhead 가 적음
• 시스템 환경 변화에 대한 대응이 어려움

Dynamic priority (동적 우선순위)

• 프로세스의 상태 변화에 따라 priority 변경
• 구현이 복잡 , priority 재계산 overhead 가 큼
• 시스템 환경 변화에 유연한 대응 가능

작업관리자에서 프로세스에 우선순위를 선택할 수 있음

---

요약 : Scheduling Concepts

• 멀티프로그래밍 (멀티테스킹)
• 스케줄링 개념
  
  • 목적
  • 성능 지표 (index) : CPU burst VS I/O burst
  • 스케줄링 기준 (Criteria)
•  
• 스케줄링 레벨 :Long term, Mid term, Short term
• 스케줄링 정책
  • Preemptive/non preemptive
  • Priority

 

 

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---