프로세서 스케줄링

프로세서 스케줄링

CPU를 언제, 어느 프로세스에 할당할지 결정하는 작업

방법별 분류

• 선점 스케줄링
• 비선점 스케줄링

스케줄링 목적

• 공정한 스케줄링
• 처리량 최대화
  - 단위 시간당 처리되는 프로세스의 개수
• 응답시간 최소화
  - 실행 요청 후 첫 번째 반응이 나올 때까지의 시간
• 소요시간 예측 가능
  - 실행 요청 후 최종 결과를 받을 때까지의 시간
• 균형 있는 자원 사용
• 응답 시간과 자원 이용간의 조화
• 실행의 무기한 연기 배제
• 우선 순위 고려

스케줄링 수준

• 상위 수준 스케줄링
  • 어떤 작업을 자원 경쟁을 참여시킬지 결정
  • 한번에 시스템에 허용되는 전체 프로세스의 개수 조정
• 중간 수준 스케줄링
  • 어떤 프로세스가 프로세서(CPU) 사용을 위해 경쟁할 수 있는지 결정
  • 시스템 부하의 지나친 변동에 대응
• 하위 수준 스케줄링
  • 우선순위 결정
  • 프로세서를 프로세스에 할당

선점/비선점 스케줄링

선점 스케줄링

• 다른 프로세스에 의해 프로세서를 사용중인 프로세스 중지 가능
  - 선점당한 프로세스는 메모리에 잔류
• 우선순위가 높은 프로세스를 먼저 실행해야 할 때 유리
• 빠른 응답시간이 요구되는 시분할 시스템에서 유용
• 선점 때문에 많은 오버헤드 초래 가능

비선점 스케줄링

• 프로세스가 프로세서를 할당받으면, 작업을 끝내거나 자발적으로 프로세서를 반환할 때까지 사용
• 응답시간의 예측 가능
• 우선순위가 낮은 프로세스가 우선순위가 높은 프로세스를 대기시킬 가능성
• 짧은 작업이 긴 작업의 대기 상황 발생 가능

우선순위

정적 우선순위

• 프로세스에 할당된 우선순위 불변
• 구현 용이
• 낮은 오버헤드
• 변화하는 환경에 대한 대응 곤란

동적 우선순위

• 실행 환경 변화에 대응하여 우선순위 변경
• 원만한 상호작용성 지원
• 정적 우선순위 방법에 비해 높은 오버헤드

프로세서 스케줄러와 디스패처

• 실행 준비가 된 프로세스들 중에서 CPU를 할당할 프로세스를 선택
• CPU 스케줄링이 이루어지는 시점
  • 실행중인 프로세스가 대기 상태로 전환
  • 실행중인 프로세스가 준비 상태로 전환
  • 대기 상태의 프로세스가 준비 상태로 전환
  • 프로세스 종료

디스패처

• CPU 스케줄러가 선택한 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 커널 모듈
  • 문맥교환 수행
  • 사용자 모드로 전환
  • 해당 프로세스의 재시작 위치로 점프
• 디스패치 지연
  - 디스패처가 실행중인 프로세스를 중지시키고 다른 프로세스를 시작시킬 때까지 걸리는 시간
  

CPU/입출력 버스트

CPU 버스트

• 프로세스 실행시 CPU를 사용해 명령어를 수행하는 일련의 단계
• 입출력을 한번 수행 후 다음 입출력을 수행하기 까지 CPU를 이용하는 일련의 명령어를 통한 작업 부분

입출력 버스트

• 입출력 요청이 발생해 커널에 의해 입출력 작업이 진행되는 비교적 느린 단계
• 입출력 요청된 후 작업이 완료되어 다시 CPU 버스트로 돌아가기 까지 일어나는 일련의 작업 부분

프로세스는 CPU 버스트와 입출력 버스트가 교대로 일어나면서 실행

CPU 버스트 시간의 분포

• CPU 버스트 시간이 프로세스가 CPU 사용을 요구하는 시간
• 대부분의 프로세스는 할당된 시간을 다 사용하지 않음

스케줄링 알고리즘

• 선입선처리 스케줄링
• 라운드 로빈 스케줄링
• 최단작업 우선 스케줄링
• 최고 반응율 우선 알고리즘
• 최단 잔여시간 우선 스케줄링
• 우선순위 스케줄링
• 다단계 큐 스케줄링
• 다단계 피드백 큐 스케줄링

선입선처리 스케줄링

• First-Come-First-Serve 스케줄링
• 도착 순서에 따라 처리
• 비선점 스케줄링
• 짧은 처리시간을 갖는 작업이 상대적으로 불리
• 중요하지 않은 작업이 중요한 작업을 기다리게 할 수 있음
• 대화식 시스템에는 부적합

라운드 로빈 스케줄링

• 각 프로세스에 일정 크기의 CPU 시간 할당
  - time quantum은 10~100 ms

• 프로세스가 time quantum이 만료될 때까지 처리를 완료하지 못하면, 대기중인 다임 프로세스로 넘어감
  - 실행 중이던 프로세스는 ready queue의 맨 뒤에 추가

• 선점 스케줄링

• 시분할 시스템에 적합

• 너무 긴 할당 시간

  • FIFO 형태 특성
  • 반응시간 불량

• 너무 짧은 할당 시간

  • 빈번한 문맥교환 발생에 따른 오버헤드
  • 비효율적 CPU 사용

• 적당한 할당 시간 크기
  - 70~80% 프로세스가 할당 시간 내에 중단이 발생하는 크기
  

최단시간 우선 스케줄링

• Shortest-Job-Next/Shortest-Process-First 스케줄링
• 준비 대기열에 기다리고 있는 프로세스 중 처리시간이 가장 짧다고 판단되는 것 먼저 수행
• 비선점 스케줄링
• FIFO 보다 평균 대기시간 감소
• 큰 작업에 대해서는 FIFO에서 보다 대기시간 예측 곤란
• 짧은 작업이 유리
  - 긴 작업은 무기한 대기 가능성
• 프로세스에 대한 처리시간 예측 필요
  - 예측 부정확 및 오류 가능성
• 대화형 시스템에 부적합

최고 반응율 우선 알고리즘

• 최단작업우선 방법 개선

• 비선점 스케줄링

• 대기 시간과 처리 시간을 고려하여 우선순위 결정

  우선순위 = (대기시간+처리시간) / 처리시간

• 무기한 대기 가능성 배제

최단 잔여시간 우선 스케줄링

• 최단작업 우선 스케줄링의 선점형 방법
• 도착하는 프로세스가 실행 중인 프로세스 보다 처리시간이 짧으면 CPU 선점
• 반응시간의 변화가 큼
• SJF에서 보다 작업시간이 긴 프로세스는 더 오래 대기 가능
• 더 짧은 프로세스가 들어오면 완료 직전의 프로세스도 선점당함
  - 문맥 교환 오버헤드 발생
  

우선순위 스케줄링

• 프로세스 별로 우선순위 부여
• 가장 높은 우선순위의 프로세스에게 프로세서 할당
• 동일 우선순위의 프로세스들은 FCFS 방식으로 스케줄링
• 우선순위는 내부적 또는 외부에서 정의
• 선점형 우선순위 스케줄링
  - 새로 도착한 프로세스의 우선순위가 실행중인 프로세스의 우선순위보다 높으면 선점
• 비선점형 우선순위 스케줄링
  - 도착한 프로세스의 우선순위에 따라 ready queue의 해당 위치에 삽입
• 무기한 대기 상태 발생 가능 -> aging 기법

다단계 큐 스케줄링

• 우선순위가 다른 복수의 큐 관리
• 각 프로세스는 하나의 큐에 영구 할당
• 각 큐는 개별 스케줄링 알고리즘 적용
  - ex) RR, FCFS
• 큐 간의 스케줄링 필요
  - 각 큐는 낮은 우선순위 큐보다 먼저 처리
  

다단계 피드백 큐 스케줄링

• 여러 개의 대기열 사용
• 상위 대기열은 짧은 time quantum
• 상위 대기열이 높은 우선순위
• 도착하는 프로세스는 최상위 대기열 진입
• 주어진 time quantum 내에 처리되지 않은 프로세스는 다음 대기열에 진입
• 짧은 I/O 중심 프로세스가 높은 우선순위 차지
• 마지막 큐는 라운드 로빈 방식 또는 FIFO 방식 운용
• 너무 오래 낮은 우선순위에서 대기한 프로세스는 높은 우선순위 대기열로 이동 가능 (aging 기법)

공정분배 스케줄링

• 프로세스들을 사용자별 또는 특성에 따라 그룹으로 분할
• 그룹별로 CPU 시간의 비율을 할당
• 그룹별로 할당된 자원을 분배하여 사용
• 할애된 CPU 시간을 적게 사용한 그룹이 높은 우선순위 차지
• 중요하지 않은 그룹이 CPU를 독점하는 것 방지

마감시간 스케줄링

• 지정된 시간 내에 프로세스가 완료되도록 스케줄링
• 제 때 실행되지 않은 처리결과 무의미한 경우
• 구현 복잡
  • 미리 프로세스가 요구하는 정확한 저원 요구량 정보 필요
  • 높은 오버헤드
  • 다른 프로세스에 대한 서비스 질 저하 가능

실시간 스케줄링

• 모든 프로세스가 정해진 시간 내에 완료되도록 스케줄링
• 마감시간 스케줄링과 관련
• 주기적으로 실행되는 작업을 갖는 프로세스의 스케줄링
  • 제어 시스템
  • 동영상 등 멀티미디어 응용
    
    
• 경성 실시간 스케줄링
  • 마감시간을 지키지 않으면 치명적 결과 초래 가능
    - ex) 항공관제 시스템
    
  
  
• 연성 실시간 스케줄링
  • 마감 시간을 맞추지 못하면 데이터 손실 등 피해가 발생하지만 시스템의 운영 가능
    - ex) 멀티미디어 실행

정적 실시간 스케줄링

• 시간에 따른 우선순위 불변
• 낮은 오버헤드
• 환경적 변화가 적은 시스템에 적합

RM(비율단조) 스케줄링

- 크기를 알고 있는 일정개수의 프로세스들이 각자 주기적으로 발생되는 환경에서 사용
- 각 프로세스의 마감시간이 주기와 같다고 가정
- 주기가 짧을수록 높은 우선순위 부여

동적 실시간 스케줄링

• 상황 변화에 따라 우선순위 조정
• 우선순위는 일반적으로 프로세스 마감시간에 따라 결정

Earliest-Deadline-First(최근접 마감시간 우선) 알고리즘

• 마감시간이 가장 짧게 남은 프로세스가 최우선 순위
• 선점형 알고리즘

Minimum-Laxity-First(최소여유 우선) 알고리즘

• 프로세스의 마감시각와 남은 처리시간을 기초로 우선순위 결정

  여유시간 = 마감시각 - 현재시각 - 남은 처리시간

• 최소 여유시간을 갖는 프로세스가 가장 높은 우선순위 차지

다중 프로세서 스케줄링

다중 프로세서 시스템

• 동일한 기능의 여러 개의 프로세스를 갖는 시스템
• 부하공유 가능

다중 프로세서 스케줄링 방법

• 비대칭 다중처리
  • 모든 프로세서가 동일한 구조일 필요는 없음
  • 주 서버 역할을 하는 프로세서 하나가 운영체제를 실행하면서, 전체 프로세서들에 대한 스케줄링 담당
  • 주 서버만 시스템의 자료구조 접근
  • 주 서버인 프로세서 장애시 다른 프로세스가 주 서버 역할 수행
  • 슬레이브 프로세서는 주 서버의 통제를 받으며, 슬레이브 프로세서간의 통신 불필요
• 대칭 다중처리(SMP)
  • 각 프로세서가 독자적으로 스케줄링
  • 각 프로세서의 스케줄러가 준비 대기열을 검사하여 실행할 프로세서 선택
  • 준비 대기열이 공동으로 하나 있거나, 각 프로세서별로 존재
  • 각 프로세서가 공동 자료구조를 접근하고 갱신한다면 신중한 프로그래밍 필요
  • 대부분의 운영체제가 SMP 지원
    • Windows, Solaris, Linux, Mac OS X

프로세서 선호도

• 캐시 메모리

  • 가장 최근 접근한 데이터 및 명령어 저장
  • 프로세스가 다른 프로세서로 이주하면, 캐시 메모리 내용 무효화

• 프로세스를 다른 프로세서로의 이주를 피하고 같은 프로세서에서 처리시키려는 특성

• 약한 선호도

  • 운영체제가 동일한 프로세서에서 프로세스를 실행시키려고 노력하는 정책 사용
  • 다른 프로세서로 이주 가능

• 강한 선호도
  - 다른 프로세서로 이주 불허

부하 균등화

• SMP 시스템의 모든 프로세서 사이에 부하가 고르게 배분되도록 시도
• 프로세서 별로 프로세스의 준비 대기열을 가지고 있는 경우 필요
  - SMP 지원 대부분의 OS는 프로세서별 준비 대기열 보유
  
• Push 이주 방식
  • 특정 태스크가 주기적으로 각 프로세서의 부하 검사
  • 불균형시 과부하인 프로세서의 프로세스들은 다른 프로세서로 이주
• Pull 이주 방식
  - 쉬고 있는 프로세서가 바쁜 프로세서를 기다리는 프로세스를 pull
  
• Push 방식과 Pull 방식이 종종 병렬적으로 구현
  - Linux의 경우 200ms 마다 push 이주, 준비 대기열이 빌 때마다 pull 이주
  

대칭적 다중 쓰레딩 (SMT)

• 다수의 물리적 프로세서 대신, 동일한 프로세서 상에서 다수의 논리적 프로세서를 제공하는 기술
  - Intel의 하이퍼쓰레딩 기술
• 논리적 프로세서
  • 자기 자신의 구조상태 보유
  • 각자 인터럽트 처리
  • 캐시메모리와 버스 등의 물리적인 프로세서의 자원은 공유
  • 운영체제 관점에서는 별개의 프로세서로 간주

우선순위 역전

• 낮은 우선순위 태스크가 높은 우선순위 태스크보다 먼저 CPU를 할당받아 사용하게 되는 상황
• 우선순위가 높은 태스크가 낮은 우선순위의 태스크에 의해 임계영역 대기를 하게 되는 상황
• 화성 패스파인더의 SW에서 발생 (1997)
  - 실시간 임베디드 시스템 VxWork의 선점형 우선순위 스케줄링
  

우선순위 상속 기반의 우선순위 역전 해결

• 특정 태스크가 더 낮은 우선순위 태스크 소유의 세마포어를 대기하는 경우, 세마포어 소유 태스크의 우선순위를 대기자의 우선순위로 증가
• 커널이 우선순위 동적 변경
• 단순한 우선순위 역전현상만 해결 가능

우선순위 올림 기반의 우선순위 역전 해결

• 태스크가 세마포어를 소유하는 동안은 지정된 우선순위에서 동작
• 지정된 우선순위 올림값보다 낮은 우선순위인 경우에만 우선순위 변경
• 세마포어를 확보한 태스크는 선점되지 않고 자신의 작업 종료 가능
• 우선순위 변동에 대한 부하 적음
• 태스크가 지원을 요청하지 않아도 항상 높은 우선순위를 할당
  - 불필요한 성능 저하