운영체제 #2 - 스케줄링

스케줄링은 운영체제의 역할 중 자원관리와 관련된다.
한정된 자원을 얼마나 효율적으로 분배하여 이용율을 높일 것인가?

흔히 말하는 멀티태스킹으로 인해 스케줄링의 역할이 보다 중요해진다.
자원의 효율적 사용과 사용자의 응답시간을 고려하여 최적의 방법을 찾아야 한다.


일반적으로 CPU속도에 비해 I/O의 속도가 현저히 낮기 때문에,
I/O 바운드 프로세스의 스케줄링이 더 중요한 과제가 될 것이다.
  * CPU 바운드: CPU연산에 대부분을 보내는 프로세스 상태
  * I/O 바운드: I/O 대기에 대부분을 보내는 프로세스 상태

그렇다면 언제 스케줄링 할 것인가?
  - 새로운 프로세스가 시작될 때
  - 프로세스가 종료될 때
  - I/O, 세마포어 등의 이유로 프로세스가 블록될 때
  - I/O 인터럽트 발생시
  - CPU 클럭 인터럽트 발생시
    비선점(Non-preemptive): 프로세스가 자발적으로 종료할 때까지 대기한다.
    선점(Preemptive): 스케줄러가 자원의 재분배 권한을 가진다.

일반적 스케줄링의 목표
  - 각 프로세스의 공평한 CPU 이용
  - 시스템/자원의 균등한 활용
  - CPU 이용율, 성능, 반환시간 간의 균형된 조합
환경별 스케줄링 알고리즘
  - Batch: 처리에 충분한 시간을 허용하는 선점 or 비선점
  - Interactive: 사용자에게 서비스 제공이 중요, 선점
                     응답시간이 중요하다.
  - Real-time:  바로 수행되어야할 프로세스가 실행되어야 한다.
                     각 프로세스가 적대적 관계일 수 있다.
                     짧은 작업이 대부분이므로 반드시 선점형이 아닐 수도 있다.
                     데드라인을 지키는 것이 중요하다.

Scheduling for batch systems
  - FCFS (First-Come First-Serverd)
    비선점, 단일 큐 사용
    CPU를 요청한 순서대로 원하는 시간만큼 실행
    이해하기 쉽고 프로그램하기도 쉽다. 어느정도 공정한 선착순
    짧은 주기의 CPU바운드에 의해 긴 주기의 I/O바운드의 반환시간이 느려진다.
  - SJF (Shortest Job First)
    비선점, 단일 큐 사용
    작업시간이 가장 짧은 작업을 먼저처리하는 방식
    평균 반환시간을 낮출 수 있다.
    작업시간의 정확한 예측이 필요
    모든 작업이 동시에 시작될 때 최적의 결과
  - SRTN (Shortest Remaining Time Next)
    SJF의 선점버전
    중간에 시작되는 작업과 현재까지 진행된 작업의 양을 비교해 스케줄링
  - 3-Level
    Admission scheduler: 시스템에 넣을 작업을 선택
    Memory scheduler: 메모리에 넣을 작업을 선택
    CPU scheduler: 준비상태의 프로세스중 하나를 실행

Scheduling for interative systems
  - Round Robin
    선점형 스케줄링으로 특정한 시간 할당량을 정해두고 초과할 경우 선점하는 방식
    선점당한 작업은 큐의 제일 마지막에서 대기하게 된다.
    할당량이 너무 작으면 프로세스 스위칭이 자주 발생하여 CPU 효율이 저하된다.
    할당량이 너무 크면 대기 시간이 길어져 적절한 응답시간을 보장할 수 없다.
  - Priority
    각 프로세스는 우선순위에 의해 스케줄링된다.
    기아상태에 빠질 수 있으므로, 시간에 따른 우선순위 감소 등의 해법이 필요하다.
    동적 혹은 정적으로 우선순위를 할당할 수 있다.
    *기아상태: 대기중인 프로세스가 한없이 대기상태로 남아 있는 상태
  - Multiple Queues
    우선순위 스케줄링에 클래스 개념을 적용하여 클래스별로 큐 사용
    프로세스 스위칭이 매우 느리다는 점을 개선한다.
    높은 우선순위의 클래스는 시간 할당량을 작게하고 하위 클래스는 크게 설정
    높은 우선순위 클래스에서 작업후 남은 작업은 하위의 클래스로 이동한다.
    응답시간과 잦은 프로세스 스위칭의 비효율을 개선한 스케줄링
  - SPN (Shortest Process Next)
    가장 짧은 작업을 우선 선택하여 응답시간을 최소화하는 스케줄링
    가장 짧은 작업을 알아내는 방법이 필요
    과거의 동작을 바탕으로 가중치를 부여하는 aging 기법이 있다.
  - Guaranteed
    각 프로세스에 1/n의 성능을 보장하는 기법이다.
    CPU의 사용량과 시간을 기준으로 사용비율이 낮은 프로세스를 우선 스케줄링
  - Lottery
    각 프로세스에게 복권을 주고 무작위로 선택하여 스케줄링한다.
    복권의 개수를 차등 지급하여 자원의 이용비율을 결정할 수 있다.
  - Fair-Share
    프로세스의 소유자(사용자)별로 권한(시스템권한, 지불대금 등)에 따라
    CPU 사용율을 결정하는 프로세스를 스케줄링하는 기법이다.

Scheduling for Real-time systems
  - Rate Monotonic
    실행율(수행횟수/초)에 의해 선형으로 계산되는 우선순위에 의한 스케줄링
    CPU 이용률이 낮은 상황에서만 사용할 수 있다. (0.78 미만)
  - Earliest Deadline First
    데드라인(다음작업 전)을 기준으로 빠른 작업을 우선 스케줄링한다.







Tip.
세계 최초의 전자 컴퓨터는?
  그 구분이 모호하고 2차세계대전시의 사건이라 정확한 답은 없는 듯하다.
  일반적으로 애니악(ENIAC)이 최초라고 알려져 있고,
  최근에는 콜로서스가 최초라는 의견이 많이 나타나는 듯하다.
  그렇지만 비슷한 시기에 완성된 기계가 더 있어 논란의 여지가 있다.
  2차 세계대전이 컴퓨터 기술의 발전에 큰 기여를 했다.
  탄도계산과 암호해독 등을 위한 군사목적으르 개발되었고,
  아직까지 군사기밀인 상태로 밝혀지지 않고 있는 기계도 있을 듯하다.

  애니악(ENIAC)
    1946년 미국 펜실베니아대학에서 모클리와 에커트의 설계로 개발 되었다.
    63㎡의 거대한 크기, 30t의 무게, 진공관 사용
  콜로서스(Colossus)
    1943년 영국의 토미 플라워, 맥스 뉴먼에 의해 개발, 진공관 사용
    애니악 이전의 컴퓨터라고 받아들여지고 있는 추세이다.