CS/OS

5. 프로세스 스케줄링 (1)

🥭맹2 2021. 5. 10. 03:06

프로세스 스케줄링 (Process Scheduling)

프로세스가 실제로 시스템에서 어떻게 스케줄링이 되어 자원을 할당 받는지

1. 스케줄링을 하는 이유 ?

다중 프로그래밍(Multi-programming)이란,

여러 개의 프로세스가 시스템 내에 존재하는 것입니다.

따라서 자원을 할당 할 프로세스를 선택해야하는데요,

이 때 사용하는 것이 스케줄링입니다.

자원 관리에는 2가지가 있습니다.

  1. 시간 분할 (time sharing) 관리
  2. 공간 분할 (spacing sharing) 관리
  1. 시간 분할 관리란 ?
    • 하나의 자원을 여러 스레드들이 번갈아 가며 사용하는 것입니다.프로세서(CPU)는 한 번에 프로세스 하나만 사용할 수 있기 때문이죵
    • 따라서 프로세스 스케줄링(process scheduling)을 통해 프로세서 사용시간을 프로세스들에게 분배해줘야합니다.
    • 예를 들면, 프로세서가 있습니다
  2. 공간 분할 관리란?
    • 하나의 자원을 분할하여 동시에 사용하는 것입니다.
    • 예를 들면, 메모리가 있습니다.
    • 메모리는 프로세스들이 공간을 나누어 동시에 사용하기 때문이죵

2. 스케줄링(scheduling)의 목적

그럼 스케줄링을 하는 이유는 뭘까요 ?

바로, 시스템의 성능(performance)을 향상시키기 위해서입니다.

그런데 여기서 성능은 무엇을 기준으로 확인할 수 있는 것일까요 ?

여러 지표가 있지만 그 중 3가지를 먼저 보겠습니다.

  • 응답시간 (response time)
    • 작업 요청(submission)으로부터 응답을 받을 때까지의 시간
    • 주로 interacitve system(대화형 시스템), real-time system(제한된 시간 내에 답을 줘야하는 시스템)에서 우선시 되는 성능 지표 (사용자 지향적임)
  • 작업 처리량 (throughput)
    • 단위 시간 동안 완료된 작업의 수
    • 주로 batch system(일괄처리 시스템)에서 우선시 되는 성능 지표(시스템 지향적임)
  • 자원 활용도 (resource utilization)
    • 주어진 시간(Tc)동안 자원이 활용된 시간 (Tr) == (Tr/Tc)
    • 주로 비싼 장비 사용 시ㅎㅋ, 최대한 뽕 뽑아야하니까 우선시 되는 성능 지표

이 외에도 공평성(fairness), 실행 대기 방지(무기한 대기 방지), 예측 가능성(predictability, 적절한 시간안에 응답을 보장하는가) 등등이 있습니다.

3. 스케줄링에서 사용하는 용어

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

  • 대기 시간은 프로세스가 도착한 이후 ~ 실행이 시작될 때까지의 시간입니다.
  • 응답 시간은 프로세스가 도착한 이후 ~ 첫번째 출력 (응답)이 있을 때까지의 시간입니다.
  • 실행 시간은 프로세스가 실행된 이후 ~ 실행이 종료될 때까지의 시간입니다.
  • 반환 시간은 프로세스가 도착한 이후 ~ 실행이 종료될 때까지의 시간입니다.

그림으로 보시죵~!

용어를 익힙시다요

4. 스케줄링 기준 (Criteria)

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

  • 프로세스(process)의 특성
    • I/O-bounded(CPU burst time보다 I/O burst time이 긴 경우) or computed-bounded(CPU burst time이 I/O burst time보다 긴 경우)
  • 시스템 특성
    • Batch system or interative system -> 특성에 따라 목적이 달라지므로
  • 프로세스의 긴급성(urgency)
    • Hard- or soft- real time, non-real time systems
  • 프로세스 우선순위(priority)
  • 프로세스 총 실행 시간 (total service time)

1) CPU burst와 I/O burst는 뭔가요?

  • 프로세스 수행은 CPU 사용과 I/O를 요청한 다음 기다리는 시간으로 이루어져 있습니다
  • 즉, 프로세스 수행 = CPU 사용 + I/O 대기

이 때, CPU를 사용하는 것을 CPU burst라고 하며, CPU burst에 소요되는 시간을 CPU burst time이라고 합니다.

이와 동일하게, I/O를 요청한 다음 기다리는 것을 I/O burst라고 하며, I/O burst에 소요되는 시간을 I/O burst time이라고 합니다.

5. 스케줄링의 단계 (Level)

발생하는 빈도 및 할당 자원에 따른 구분

  1. Long-term scheduling(장기 스케줄링)
  • 가끔 일어나는 것
  • Job scheduling이 이에 속함
  1. Mid-term scheduling (중기 스케줄링)
  • 종종 일어나는 것
  • Memory allocation이 이에 속함
  1. Short-term scheduling(단기 스케줄링)
  • 자주 일어나는 것
  • Process scheduling이 이에 속함

1) Long-term Scheduling

긴 시간에 한 번씩 일어나는 스케줄링

  • Job scheduling
    • 여러 Job 중 시스템에 제출 할 (Kernel에 등록 할) 작업(Job) 결정
      • Job이 커널에 등록되면 ==> 프로세스가 됨 !
      • Admission scheduling, High-level scheduling
    • 다중프로그래밍 정도(degree) 조절
      • 다중프로그래밍 정도(multi-programming degree)란?
        • 시스템 내의 프로세스 수
      • 따라서 시스템 내의 프로세스 수를 조절하는 것임
      • 이는 성능을 결정하는데 중요함
    • I/O-bounded와 compute-bounded 프로세스들을 잘 섞어서 선택해야함
      • 이유
        • 프로세스 수행은 CPU와 I/O device가 있음. 이 때 coumpute-bounded process만 선택하게 되면, CPU만 일하고 I/O device는 놀게 됨. 반대로 I/O-bounded process만 선택하게 되면 I/O device만 일하고 CPU는 놀게 됨. 이는 상당히 비효율적임. 따라서 둘을 잘 섞어야함
    • 시분할 시스템(time-sharing system)에서는 모든 작업을 시스템에 등록함.
      • 이유
        • 어차피 시간을 나누어 사용하므로 상대적으로 다른 시스템에 비해 long-term scheduling이 덜 중요함. 불필요까지는 아니고.. 왜냐하면 프로세스를 너무 많이 올리면 전반적으로 느려지니까.

2) Mid-term Scheduling

  • 메모리 할당 결정(memory allocation)
    • Job-scheduling 보다는 더 자주 일어나서 mid-term scheduling임.
    • Intermediate-level scheduling
    • Swapping (swap-in/swap-out) : 메모리의 관리를 위해 사용되는 기법
      • swap-in : 주 기억장치(RAM)으로 불러오는 과정
      • swap-out : 보조 기억장치로 내보내는 과정

누구한테 메모리를 할당해줄지 결정해주는 것

3) Short-term Scheduling

  • Process scheduling
    • Low-level scheduling
    • 프로세서(processor, CPU)를 할당할 프로세스(process)를 결정
      • Processor scheduler, dispatcher
  • 가장 빈번하게 발생함
    • Interrupt, block(I/O), time-out, Etc ..
    • 가장 빈번하게 발생하기 때문에 얘가 느리면 시스템 전반적으로 느려지게 되므로 매우 빨라야 함
      • 예를 들어, average CPU burst = 100ms 이고 scheduling decision = 10ms이면 오버헤드는 10ms인데, 총 소요시간인 110ms에서 오버헤드가 차지하는 비율이 9%나 된다.

프로세서를 할당할 프로세스 결정

4) 총 정리 그림

눈에 익혀봅시다요

6. 스케줄링 정책 (Policy)

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

1) Preemptive / Non-preemptive scheduling

선점 : 누가 내 것을 빼앗을 수 있다.

비선점 : 누가 내 것을 뺏을 수 없다.

(1) Preemptive scheduling

  • 타의에 의해 자원을 빼앗길 수 있음
    • ex) 할당 시간 종료, 우선순위가 높은 프로세스 등장
  • context switch overhead가 큼
    • 왜냐하면, 프로세스가 자주 바뀌기 때문
  • Time-sharing system, real-time system등에 적합
    • 왜냐하면, 응답성이 높아지기 때문임.

(2) Non-preemptive scheduling

  • 할당 받을 자원을 스스로 반납할 때까지 사용
    • ex) system call, I/O, Etc..
  • Context switch overhead가 적음
    • 왜냐하면, 뺏을 수 없으므로 프로세스가 바뀌지 않음
  • 잦은 우선순위 역전
    • 우선 순위가 높은 프로세스를 먼저 처리할 수 없는 현상이 발생함
  • 평균 응답 시간 증가
    • 다른 프로세스들의 응답시간이 증가하게 됨
      • 왜냐하면, 할당을 반납할 때까지 기다려야하기 때문임

2) Priority(우선순위)

프로세스의 중요도

(1) Static priority (정적 우선순위)

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

(2) Dynamic priority(동적 우선순위)

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

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

 

'CS > OS' 카테고리의 다른 글

5. 프로세스 스케줄링 (3)  (0) 2021.05.10
5. 프로세스 스케줄링 (2)  (0) 2021.05.10
4. 스레드 관리  (0) 2021.05.09
3. 프로세스 관리(2)  (0) 2021.05.09
3. 프로세스 관리(1)  (0) 2021.03.14

'CS/OS'의 다른글

  • 현재글5. 프로세스 스케줄링 (1)

관련글

댓글

티스토리툴바