프로세스 스케줄링

• • 프로세스 상태 전이
                                                                       (Dispatch)
       제출(submit) →→ 접수(Hold) →→ 준비(Ready) ↔↔ 실행(Run) →→ 완료(Complete)
                                      ↓                       ↖                   ↙
                       (spooling)↓           입출력종료 ↖            ↙입출력 발생
                                      ↓          (wake up)     ↖     ↙
                                  디스크                    대기(wait, Block)

  • 프로세스 상태
     * 제출 : 작업을 처리하기 위해 사용자가 작업을 시스템에 제출한 상태
     * 접수 : 제출된 작업이 스풀 공간인 디스크의 할당 위치에 저장된 상태
     * 준비 - 프로세스가 프로세서를 할당받기 위해 기다리고 있는상태
            - 프로세스는 준비상태 큐에서 실행을 준비하고 있다.
            - 접수 상태에서 준비 상태로의 전이는 Job 스케줄러에 의해 수행된다.
            - 준비 리스트에 있는 프로세스는 각각 우선순위가 주어진다.
     * 실행 - 준비상태 큐에 있는 프로세스가 프로세서를 항당받아 살행되는 상태
            - 실행중인 프로세스에 입출력 처리가 필요하면 실행중인 프로세스는 대기 상태로 전이된다.
            - 프로세스 수행이 완료되기 전에 프로세스에게 주어진 할당 시간이 종료되면 프로세스는 준비 상태로 전이된다.
     * 대기, 보류, 플록
            - 프로세스에 입출력 처리가 필요하면 현재 실행 중인 프로세스가 중단되고, 입출력 처리가 완료될 때까지 대기하고 잇는 상태
            - 대기 리스트에 있는 프로세스는 우선순위가 주어지지 않는다.
     * 완료 - 프로세서를 할당받아 주어진 시간 안에 수행을 완료한 상태

  
   

  • 스케줄링(Scheduling)
     * 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업을 의미한다.
     * 목적 : CPU나 자원을 효율적으로 사용하기 위한 정책
  • 비선점 스케줄링(Non-Preemptive)
     * 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할수 없는 기법
     * 한번 CPU를 할당 받으면 작업이 완료될때 까지 CPU를 사용
       ->문제점 : 짧은 작업(중요한 작업)이 긴 작업(중요하지 않은 작업)을 기다리는 경우 발생
     * 종류 : FCFS(FIFO), SJF, 우선순위, HRN, 기한부(Deadline)
  • 선점 스케줄링(Preemptive)
     * 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 기법
     * 빠른 응답 시간을 요구하는 대화식 시분할 시스템(Time Sharing System)에 사용
     * 많은 오버헤드 초래
     * 인터럽트용 타이머 클럭 필요( 프로세스가 자원을 독점하는것을 방지)
     * 종류 : RR(Round Robin, SRT, 선점 우선순위, 다단계 큐(MQ), 다단계 피드백큐(MFQ)

  
   

  • 비선점 스케줄링 종류
     * FCFS(First Come First Service, 선입 선출)
       - 준비 상태 큐에 도착한 순서에 따라 차례로 CPU를 할당하는 기법
     
     * SJF(Shortest Job First, 단기작업 우선)
       - 실행 시간이 가장 짧은 프로세스에게 먼저 CPU할당
       - 평균 대기시간이 가장 적은 알고리즘
       - 실행시간이 긴 프로세스가 순위기 밀려 무한 연기상태가 발생될 수 있다.
     
     * HRN(Highest Response-ratio Next)
       - 실행시간이 긴 프로세스가 불리한 SJF기법 보완
       - 우선순위 공식을 이요하여 실행시간이 짧은 프로세스나 대시 시간이 긴 프로세스에게 우선순위를 줌
       - 우선순위를 계산하여 술자가 높은것부터 우선순위가 부여됨
       - 우선순위 계산식 = (대기시간+실행시간)/실행시간
    
    * 기한부(Deadline)
       - 일정시간동안 프로세스 완료하는 기법
       - 제한된 시간 안에 완료되지 않을 경우 제거 되거나 처음부터 다시 실행해야함
       - 여러 프로세스들이 동시에 실행되면 스케줄링이 복잡해지며, 프로세스 실행 시 집중적으로 요구되는
         자원관리에 오버헤드가 발생한다.
    
     * 우선순위(Priority)
       - 프로세스마다 우선순위 부여
       - 우선순위가 동일한경우 FCFS 기법으로 할당
       - 가장 낮은 순위를 부여받은 프로세스는 무한 연기 또는 기아상태가 발생할 수 있다.

   

  • 선점 스케줄링 종류
     * Round Robin
       - 시분할 시스템을 위해 고안된 방식, FCFS 기법 변형
       - 각 프로세스는 시간 할당량 동안만 실행한 후 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고
         준비상태 큐의 가장 뒤로 배치
       - 할당된 시간이 클수록 FCFS와 같다.
       - 시간이 작을 수록 문맥교환과 오버헤드가 자주 발생
    
     * SRT(Shortest Remaining Time)
       - SJF 기법을 변형, 선점 SJF라고도 한다.
       - 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 짧은
         실행 시간을 요구하는 프로세스에게 CPU를 할당.
       - 준비상태 큐에 있는 프로세스의 실행 기간 추적으로 오버헤드 증가
    
     * 다단계 큐
       - 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비단계 큐 사용
       - 시스템, 대화형, 편집, 일괄처리 프로세스 등으로 분류
       - 준비상태 큐 마다 다른 스케줄링 기법 사용가능
       - 다른 준비상태 큐로 이동 불가
       - 하위단계 준비 큐에 있는 프로세스를 실행하는 도중이라도 상위 단계 준비상태 큐에 프로세스가 들어오면
         상위단계 프로세스에게 CPU를 할당
    
     * 다단계 피드백 큐
       - 다단계 큐 기법 개선하여 다른 준비상태 큐로 이동 가능
       - 각 큐마다 시간 할당량부여 시간동안 완료 되지 못한 프로세스는 다음 단계 큐로 이동
       - 마지막 단계 큐에서는 RR스케줄링으로 할당
    

  
  * Dispatch : 준비 상태에서 대기하고 있는 프로세스 중 하나가 프로세서를 할당받아 실행 상태로 전이되는 과정
  * 실행 시간 = 서비스 시간 = 버스트 시간
  * 에이징(Aging)기법 : 대기 시간 등에 따라 우선순위를 높여주는 것을 의미