CS/운영체제

Chapter 4: CPU 스케줄링

GaeunLee 2022. 4. 4. 18:01

4.1 스케줄링의 단계

 

4.2 스케줄링의 목적과 기준

  • 사용자 관점
    • 응답 시간(reponse time) : 대화형 시스템에서 프로세스의 요청에 시스템이 최초 출력을 하는 시간
      • 인터렉티브시스템
    • 반환 시간(turn around time) : 일괄 처리의 경우, 요청으로부터 결과를 받는데 걸린 시간
      • 배치시스템(일괄처리 시스템)
    • 예측가능성 : 언제 끝날지 예측가능한가?
  • 시스템 관점
    • 처리량 : 단위 시간 동안 완료한 프로세스의 개수
      • ex. 인터렉티브시스템
    • 활용도 : 주어진 시간 동안 특정 자원이 가동된 시간의 비율
      • ex. 배치시스템(일괄처리 시스템)
    • 공평성 : CPU사용시간 공평하게 나누었나?
  • 스케줄링 정책을 만들 때 고려해야할 기준
    • 연산위주(CPU- bound) /입출력위주(I/O-bound)(비중높다)
    • 응답 시간/처리량
    • 특정프로세스 빠른 응답 보장
    • 프로세스 실행 시간(크키) 크고 작을 때의 우선순위

 

4.3 스케줄링의 기법들

  • 스케줄링이 가동되어야 하는 시점
    • 실행 → 대기 상태 (ex. 입출력 대기)
    • 실행 → 준비 상태 (ex. 시간 종료time out 같은 인터럽트 발생)
    • 대기 → 준비 상태 (ex. 입출력 종료)
    • 수행 후 종료

 

  • 스케줄링 기법 분류
    • 비선점 스케줄링 : 프로세스가 CPU를 할당 받으면 반납할 때까지 계속 허용 (1,4)
    • 선점 스케줄링 : 실행중인 프로세스로부터 CPU를 선점(뺏어서) 다른 프로세스에게 할당 가능(2,3)

 

  • 스케줄링 기법들
    1. FCFS 스케줄링 (=FIFO스케줄링)
      • 먼저 도착한 프로세스가 먼저 CPU할당하는 비선점 방식
      • 평균 응답시간이 길어짐
        • 평균 완료 시간: CPU요구량 다 더해서 나누기
      • 예측가능
      • 공평하다
      • 순서에 따라 긴 프로세스가 앞에오면 평균 응답시간이 길어진다

    2. SPN 스케줄링
      • 가장 짧을 것을 먼저 실행시켜주는 비선점 방식
      • 평균 응답 시간 최소화
      • 예측가능성 떨어짐
      • 긴 프로세스 무한 대기
        • 에이징 기법 : 기다린 만큼 우선순위를 둔다.
    3. SRT 스케줄링
      • SPN을 선점 방식으로 운영하는 것
      • 실행 도중 더 작은 프로세스가 들어오면 뺏긴다
      • 문맥교환의 시간이 많이 걸릴 수 있음
      • Future Knowledge 스케줄링
        • SRT발전 시킴
        • 미래를 알 수 있으면 최적으로 스케줄링
      • SRT내 잦은 문맥교환
        • 임계값(Threshold Value) 설정

    4. HRRN 스케줄링
      • 수행시간이 긴 프로세스의 무한 대기 현상을 방지하기 위한 기법
      • 응답률이 가장 높은 프로세스에게 우선순위를 주는 비선점 방식
      • aging을 우선 순위에 반영했다

    5. 라운드로빈 스케줄링
      • FIFO스케줄링을 기반으로 시간 할당량이 지나면 시간 종료 인터럽트에 의해 CPU를 뺏는 선점 방식
      • 문맥교환의 오버헤드가 많다
      • 대화식 시스템, 시분할 시스템에 적합
      • 시간할당량 (크면 : FCFS, 작으면 : 문맥교환의 오버헤드가 커짐)
      • 가상라운드로빈
        • 입출력프로세스에서 다 못쓴 시간 할당량을 마저 주는 방식
    6. 우선순위 스케줄링
      1. 정적우선순위 = 프로세스 생성~완료까지 우선순위가 변하지 않음
      2. 동적우선순위 = 시스템에 있는 동안 우선순위가 조정된다.

    7. 다단계 큐 스케줄링
      • 정적 우선순위
      • 같은 값을 받는 큐가 있어야하니까 우선순위 갯수만큼 큐가 필요하다
      • 선점방식
      • 큐들간의 프로세스 이동이 불가능(정적우선순위)

    8. 다단계 피드백 큐 스케줄링
      • CPU요구량을 몰라도 짧은 프로세스 유리 && 입출력 프로세스 우대
      • SPN SRT 비슷한 효과
      • 동적 우선순위를 기반으로 하는 선점 방식
      • 우선 순위 개수 만큼의 큐 ⇒ 단계마다 서로 다른 CPU할당량
      • 어느 단계든 시간 할당량이 끝나기 전 CPU를 내놓게 되면 한단계 위의 큐에 들어가게 해준다.

    9. Fair-Share 스케줄링
      • 프로세스들을 특성과 중요도에 따라 그룹화하고 각 그룹에 CPU 시간을 일정량 할당해줌
      • 특정 프로세스의 극단적인 사이즈가 다른 프로세스에게 영향을 미치지 못하게 하기 위함

 

  • 실시간 스케줄링
    • 실시간 시스템
      • 실행될 모든 프로세스가 정해진 시간 내에 완료되어야함
      • 경성 실시간 시스템 : 마감 시간을 못지키면 큰 문제가 생긴다
      • 연성 실시간 시스템 : 마감 시간을 못지키면 데이터 손실, 그래도 시스템 운영은 가능 가치가 떨어짐.
    • 실시간 시스템 스케줄링
      • 정적인 방법 : 프로세스의 특징과 개수 알 수 있을 때 유용
      • 동적인 방법 : 프로세스의 특징과 개수 알 수 없을 때 유용
    1. RM 알고리즘
      • 정적 스케줄링 방식
      • 주기가 짧을수록 높은 우선 순위를 받는다.
    2. EDF 알고리즘
      • 동적 스케줄링 방식 = 마감시간이 가까울수록 우선순위를 높게 부여하는 방식
      • 새로운 프로세스가 도착할 때 자로 대응 할수 있다
      • 모든 프로세스가 주기적일 필요가 없다. 주기적이지 않으면 마감시간을 알려줘야함