[운영체제] 120504 스케줄링 알고리즘 - 다중처리기 스케줄링 부터~

2. 스케줄링 알고리즘
 * 다중 처리기 스케줄링
  1) 강결합 다중처리기 시스템을 중심으로 다중 프로세스의 구조를 살펴봄
   (1) 각 프로세서들은 독자적인 큐와 독자적인 알고리즘을 가지므로 프로세서가 다르면 선택의 여지는 상대적으로 제한됨
   (2) 작업은 프로세스의 구조에 따라 특정하게 지정, 특정 프로세서의 의해 실행되어야 함.
   (3) 같은 종류의 프로세서가 한 시스템에 여러 개 있다면 부하 공유가 발생함
   (4) 이를 방지하기 위해 각 프로세서에 서로 독립된 큐를 제공
    -
    -
   (5)

  2) 두 가지 스케줄링 방법이 사용.
   (1) 프로세서 자신이 스스로 스케줄링 하는 것
    - 각 프로세서는 공통의 준비 ㅅㅇ태 큐에서 실행 시킬 프로세스 하나를 선택
    -
    -
   (2) 한 프로세서를 다른 모든 프로세서의 스케줄러로 지정, 주/종 구조를 갖게함
    - 비대칭 다중 프로세싱
    - OS의 핵심 커널 기능은 특정 프로세서에서 수행, 타 프로세서들은 사용자 프로그램들만 수행
    - 주 프로세서는 프로세스들을 스케줄링하여 프로세스를 활성화 시킴
    - 종 프로세스가 입출력 호출 등의 서비스가 필요할 때 주 프로세서에 요청하여 서비스의 처리가 완료 되길 기다림
    - 단일 프로세서 다중 프로그래밍 기법과 유사하며 자원 충돌 문제를 해결할 수 있음.
    - 주 프로세서의 오류는 시스템 전체를 정지시키며, 주 ㅍ로세서의 과중한 오버헤드는 성능의 병목지점이 될 수 있다는 단점이 존재


 * 스레드 스케줄링
  1) 스레드 실행의 개념
   (1) 어플리케이션과 같은 주소 공간에서 동시에 실행하고 협동하는 스레드들로 구현 가능
   (2) 스레드 교환은 프로세스 교환보다 오버헤드가 적어 성능을 향상시킬 수 있음

  2) 부하 공유(Load Sharing)
   (1) 프로세서를 특정 프로세스 하나에 할당하지 않고 전역 큐에서 프로세서를 유지
   (2) 쉬고 있는 프로세스는 전역 큐에서 스레드 하나를 선택함
   (3) 단일 프로세서 환경에서 사용한 기법을 그대로 채택한 가장 간단한 다중 프로세서 기법
   (4) 부하공유의 장점
    - 부하는 프로세서들에 균등하게 분산되며 실행 대기 중인 작업에는 분산되지 않음
    - 스레드 제어를 위한 중앙 제어 스케줄러 없이 사용 시, 현재 작업을 진행한 프로세서에서 다음 작업 선정
    - 전역(공유) 큐는 선입선처리(FCFS)나 우선순위 기법을 이용하여 구성 가능
   (5) 부하공유의 단점
    - 중앙 큐는 상호 배제 방식으로 접근되는 메모리 영역으로 많은 프로세서가 동시에 작업을 찾을 시 병목지점이 될 수 있음.
    - 선점된 스레드들은 동일한 프로세서 상에서 실행을 재개하기 어려움
    - 프로그램의 스레드들 사이에 밀접한 협조가 요구된다면 관련된 프로세스 교환은 성능을 저하시킬 수 있음
     % 현재 다중 프로세서 상에서 가장 일반적으로 사용되고 있음!!!

  3) 갱(Gang) 스케줄링
   (1) 관련된 스레드의 집합이 일대일 대응 원칙에 따라 프로세서집합에서 동시에 실행될 수 있도록 스케줄링하는 기법
   (2) 단일 프로세스에 속한 스레드들이 동시에 스케줄링 됨
   (3) 동기화 보류 및 프로세스 문맥교환의 횟수를 최소화하여 성능을 향상시킬 수 있음.
   (4) 스케줄링 오버헤드를 감소시킬 수 있음

  4) 전용 프로세서 할당
   (1) 스레드들을 실행 전담 프로세서에 할당하여 정의된 스케줄링 제공
   (2) 각 프로그램을 실행되는 동안 프로그램 내의 스레드 갯수와 동일한 수의 프로세스를 할당받으므로 프로세스가 낭비될 수 있음 -> 자세한 이해 요망
    - 할당된 프로세스 중 타 프로세스와 통신이 필요해서 대기가 발생할 경우 종료되지 않고 자원을 점유하고 있어야 할 수도 있다.
   (3) 프로세서의 합리적인 이용의 지원이 필요함
    - 활성화된 스레드이 개수를 시스템상의 프로세서와 동일한 개수로 제한하여 효율성을 높임

  5) 동적 스케줄링
   (1) 프로세스 내의 스레드 수를 동적ㅇ로 변경하여 OS가 시스템 이용률을 높일 수 있도록 부하 조절을 허용한 기법
   % 갱 스케줄링과 전용 프로세서 할당은 프로세서 단편화 문제를 회피하기 위한 기법
   % 동적 스케줄링 기법이 갱 스케줄링, 전용 프로세서 할당 기법보다 우수하나 오버헤드로 인한 성능 감소가 일어날 수 있음

  

3. 알고리즘 평가
 * 알고리즘 선택 기준
  1) 알고리즘 선택 시 사용할 기준의 정의가 모호함으로 인해 선택이 어려움.
   (1) 일반적으로 프로세스 이용률, 응답시간, 처리율을 선택 기준으로 이용하나, 이들의 기준을 정의하는 것이 어려움
   (2) 이용하기 위해선 측적한 내용의 상대적인 중요성을 정의하는 것이 필요함
   (3) 아래의 예가 기준이 되며, 선택 기준이 정의되면 다양한 알고리즘을 평가할 수 있음.
    - 최대 응답시간이 1초라는 제약조건에서 프로세서 이용률
    - 평균 반환시간이 전체 실행 시간에 선형적으로 비례하는 처리율


 * 분석적(해석적) 평가
  1) 작업부하(Work Load)를 줄이기 위해 알고리즘의 성능을 평가하는 공식, 값을 생성하기 위한 알고리즘, 시스템 작업부하를 이용
   (1) 결정성 모형화 : 분석적 평가의 한 형태로 이 방식은 사전에 정의된 특정한 작업에 대하여 각 알고리즘의 성능을 평가
    -
    -

  2) 선입 선처리 평가
   (1) 들어간 순서대로 처리
   (2) 평균 대기시간이 길어짐

  3) 비선점 최소 작업 우선 스케줄링 평가
   (1) 작업시간이 짧은 작업부터 수행됨
   (2) 짧은 작업이 바로 처리되므로 결과적으로 평균 대기시간이 짧아짐
  
  4) 순환 할당 평가 -> 개념 이해 필요!
   (1) 일정 작업 시간을 균일하게 할당 하여 남은 작업은 큐 뒤로 보내 또 다시 처리하는 방식
   (2)