운영체제 정리 7. 단일처리기 스케줄링

단일처리기 스케줄링

-단일처리기 스케줄링 정책들

-FCFS는 가장 단순한 형태의 스케줄링 정책으로써 FIFO라고도 한다. 큐잉 체계를 엄격하게 지키고 있다는 의미이다. 프로세스는 준비상태가 되면 준비 큐에 들어가고 현재 실행 중인 프로세스가 실행을 종료하면 대기 중이던 프로세스 중 가장 오랫동안 기다렸던 프로세스가 다음번 실행할 프로세스로 선정된다. 그렇기에 FCFS는 긴 프로세스에게 유리하다.

-라운드 로빈(Round Robin)은 FCFS에서 짧은 프로세스가 피해보는 현상을 완화하는 가장 간단한 방법으로 시간을 측정하고 있다가 어떤 긴 프로세스가 일정 시간 이상을 넘어가는 순간 실행을 강제로 선점시키는 것이다. 이 방법은 긴 프로세스에게나 입출력 프로세스에게 상당히 불리하게 작용한다.

-가상 라운드 로빈(Virtual Round Robin)은 일반 라운드 로빈을 발전 시킨 형태이다. 작동 방식은 이러하다 새로 도착한 프로세스는 일단 준비 큐의 끝으로 진입한다. 준비 큐에 있는 프로세스들은 FCFS 방식으로 스케줄링되고 실행중이던프로세스의 시간 할당량이 만료되면 다시 준비 큐로 들어가 대기한다. 플세스가 입출력을 요구 했다면 입출력이 완료될 때까지 입출력 큐로 들어가 대기한다. 여기까지가 일반적인 라운드 로빈이라면 가상 라운드 로빈은 이 이후에 다르게 작동된다. 기존 라운드 로빈은 입출력이 끝나면 준비 큐 끝으로 들어가지만 완료된 프로세스는 보조 큐라고 하는 별도의 FCFS 큐로 진입한다. 이후 다음번 프로세스를 고르는 시점에서 스케줄러는 이 보조 큐에서 대기 중인 프로세스를 준비 큐보다 먼저 실행시키고 실행 시간을 저번 실행 때 못 채우고 반납한 시간 만큼만 실행하게하여 처리기-중심 프로세스가 역차별을 당하지 않도록 한다.

-SPN(Shortest Process Next)은 FCFS에서 긴 프로세스만 우대하는 편향성을 완화시키는 또 다른 접근법으로 가장 짧은 프로세스를 먼저 실행시키는 정책이다. 이 방법은 비선점으로 동작하고 종료 시까지 남은 프로세스중 가장 짧은 프로세스를 다음번 프로세스로 선택한다.

-SRT(Shortest Remaining Time)은 SPN이 선점을 하는 버전에 해당한다. 따라서 SPN에서는 예상되는 전체 실행 시간이 가장 짧은 프로세스가 다음번 프로세스로 선택되었으나 SRT에서는 남아있는 예상 실행 시간이 가장 짧은 프로세스가 다음번 프로세스로 선택된다. 만약 새롭게 준비큐에 들어온 프로세스가 실행 중인 모든 프로세스보다 예상 실행 시간이 짧다면 그 프로세스가 다음번 프로세스가 된다.

-HRRN(Highest Response Ratio Next)은 정규화된 반환 시간이라는 "(대기시간+서비스시간)/서비스시간"을 사용해서 우선순위를 정한다. 즉 처음 들어갈 때에는 서비스시간이 짧은 프로세스가 먼저 들어가겠지만 서비스시간이 긴 프로세스들도 대기시간이 길어지면서 SPN처럼 무작정 긴 프로세스가 오래기다릴 필요가 없어진다. 구현상 이 방법도 SRT나 SPN처럼 미리 서비스시간이 예상되어 있어야한다.