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

출처 : https://www.youtube.com/watch?v=_gNeoGQx-Tc&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=8

 

 

 

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

 

• 여러개의 프로세스가 시스템 내 존재
• 자원을 할당 할 프로세스를 선택 해야 함
  • 스케줄링(Scheduling)
• 자원 관리 방법은 2가지가 있다.
  • 시간 분할(time sharing) 관리
    • 하나의 자원을 여러 스레드들이 번갈아 가며 사용
    • ex) 프로세서 (Processor)
    • 프로세스 스케줄링 (Process scheduling)
      • 프로세서 사용시간을 프로세스들에게 분배
  • 공간 분할 (space sharing) 관리
    • 하나의 자원을 분할하여 동시에 사용
    • ex) 메모리

 

 

스케줄링(Scheduling)의 목적

 

• 스케줄링의 목적은 시스템의 성능 (performance)을 향상시키는 것이다.
• 대표적 시스템 성능 지표 (index)
  • 응답 시간 (response time)
    • 작업 요청(submission)으로부터 응답을 받을 때까지의 시간
  • 작업 처리량(throughtput)
    • 단위 시간 동안 완료된 작업의 수
  • 자원 활용도 (resource utilization)
    • 주어진 시간(Tc) 동안 자원이 활용된 시간 (Tr)
• 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택

 

프로세스가 도착해서 실행을 시작하는 시간을 대기 시간(Waiting time), 첫 번째 출력(응답)까지의 시간을 응답 시간(response time)이라고 한다.

그리고 실제로 프로세스가 실행된 시간(실행 시작 ~ 실행 종료)을 실행 시간(burst time), 최초의 도착부터 원하는 작업이 모두 끝날 때까지의 시간을 반

환 시간(turn-around time)이라고 한다.

 

 

스케줄링 기준 (Criteria)

다음 순서에 프로세서를 어떤 프로세스에게 할당해 줄지

• 스케줄링 기법이 고려하는 항목들
  • 프로세스의 특성
    • I/O-bounded 혹은 compute-bounded
  • 시스템 특성
  • 프로세스의 긴급성
  • 프로세스 우선 순위
  • 프로세스 총 실행 시간

 

 

CPU burst vs I/O burst

 

프로세스가 작업을 수행하는 과정은 CPU 사용(계산)과 I/O 대기(or 사용)의 반복으로 이루어진다.

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

 

 

스케줄링의 단계 (Level)

 

• 발생하는 빈도 및 할당 자원에 따른 구분
• Long-term scheduling (가끔)
  • 장기 스케줄링
  • Job scheduling
• Mid-term scheduling (종종)
  • 중기 스케줄링
  • Memory allocation
• Short-term scheduling (자주)
  • 단기 스케줄링
  • Process scheduling

 

Long-term scheduling

 

• Job scheduling
  • 시스템에 제출 할 (Kernel에 등록 할) 작업(Job) 결정, Job이 커널에 등록이 되면 프로세스가 되는데, 이때 대기하고 있는 Job들 중에 어느 것을 커널에 등록할지를 결정하는 것을 Job scheduling이라고 한다. 발생빈도는 낮다.
    • Admission scheduling, High-level scheduling
• 다중 프로그래밍 정도(degree) 조절
  • 시스템 내에 프로세스 수 조절
• I/O bounded 와 compute-bounded 프로세스들을 잘 섞어서 선택해야 함. 이 두 프로세스들을 적절히 섞어줘야 효율이 올라간다.
• 시분할 시스템에서는 모든 작업을 시스템에 등록
  • Long-term scheduling이 불필요
   

 

Mid-term Scheduling

 

• 메모리 할당 결정 (memory allocation)
  • Intermediate-level scheduling
  • Swapping (swap-in / swap-out)

 

 

Short-term scheduling

 

• Process scheduling
  • Low-level scheduling
  • 프로세서를 할당할 프로세스를 결정
    • Processor scheduler, dispatcher(ready 상태에서 CPU(프로세서)를 할당받고 running 상태로 만드는 스케줄링)
• 가장 빈번하게 발생
  • Interrupt, block (I/O), time-out, 등등
  • 매우 빨라야 함
  • scheduling decision time(=overhead)이 너무 길면 문제가 된다.

 

 

정리하면 위 그림과 같다.

 

 

스케줄링 정책 (Policy) : 스케줄링을 어떠한 방법으로 할 것인가

 

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

 

 

Preemptive(선점 : 누가 와서 내 것을 빼앗을 수 있음) / Non-preemptive(비선점 : 누구도 내 것을 뺏을 수 없음) scheduling

 

• Non-preemptive scheduling
  • 할당 받을 자원을 스스로 반납할 때까지 사용
    • ex) system call, I/O 등
  • 장점
    • Context switch overhead가 적음 (한번 자원을 받으면 계속 일을 할 수 있으므로)
  • 단점
    • 잦은 우선순위 역전(긴급하게 처리해야할 다른 프로세스가 있어도 기존의 프로세스를 처리할 때까지 처리할 수 없음)
    • 평균 응답 시간 증가(프로세스 하나가 혼자 리소스를 100시간 사용하면 다른 프로세스의 응답시간이 길어지게 된다.)
• Preemptive scheduling
  • 타의에 의해 자원을 빼앗길 수 있음
    • ex) 할당 시간 종료, 우선순위가 높은 프로세스 등장
  • Context switch overhead가 큼 (프로세스가 자주 바뀜)
  • Time-sharing system, real-time system 등에 적합함 (응답성이 높음)

 

 

우선 순위(Priority)

 

• 프로세스의 중요도
• Static priority (정적 우선순위)
  • 프로세스 생성시 결정된 priority가 유지 됨
  • 장점
    • 구현이 쉽고, overhead가 적음
  • 단점
    • 시스템 환경 변화에 대한 대응이 어려움
• Dynamic priority (동적 우선순위)
  • 프로세스의 상태 변화에 따라 priority 변경
  • 장점
    • 시스템 환경 변화에 유연한 대응 가능
  • 단점
    • 구현이 복잡, priority 재계산 overhead가 큼