1) 비선점 (Non-Preemptive) 스케줄링 기법 프로세스에게 이미 할당된 프로세스를 강제로 빼앗을 수 없고, 그 프로세스의 사용이 끝난 후에 스케줄링 해야 하는 방법을 말한다. - 모든 프로세스들에 대해 공정이 처리한다. - 응답 시간의 예측이 용이하다. - 짧은 작업이 긴 작업을 기다리는 경우가 종종 발생한다. ▶ FIFO(First In First Out) = FCFS(First Come First Service) 가장 간단한 방법으로 먼저 대기 큐에 들어온 작업에게 프로세서를 먼저 할당하는 비선점 기법이다. - 중요하지 않은 작업이 중요한 작업을 기다리게 할 수 있다. - 대화식 시스템에 부적합하다. ▶ SJF(Shortest Job First) 수행시간이 가장 짧다고 판단되는 것을 먼저 수행하는 비선점 방식으로 짧은 작업에 유리하다. - 각 프로세스의 프로세서 요구시간을 미리 알기 어렵다는 단점이 있다. ▶ HRN(Highest Response ratio Next) 긴 작업 처리에 불리한 SJF 방식과 선점형인 SRT(Shortest Remaining Time)방식의 단점을 보완하기 위해 대기 시간을 고려한 프로세스의 응답률을 가지고 최고의 응답률을 가진 프로세스를 먼저 처리한다. 응답률 = ( 대기시간 + 서비스를 받을시간) / 서비스를 받을 시간 짧은 작업 뿐만 아니라 긴 작업중 대기 시간이 큰 작업의 응답률이 높아졌다. ▶ 우선 순위 스케줄링 각 프로세스에게 특정한 기준으로 우선순위(priority)를 부여한다. 그리고 우선순위가 높은 순서대로 처리한다. 우선 순위가 낮은 작업은 무한 봉쇄(Indefinite blocking)나 기아 상태(Starvation)에 빠질 수 있고, 이에 대한 해결책으로 체류 시간에 따라 우선 순위가 높아지는 에이징(Aging)기법을 사용할 수 있다. ▶ 기한부(deadline)스케줄링 작업들이 정해진 시간 내에 종료되도록 처리한다. 실시간 시스템에서 사용한다. 2) 선점(Preemptive)스케줄링 기법 하나의 프로세스가 CPU를 항당 받아 실행중에 있어도 다른 프로세스가 현재 프로세스를 중지시키고 CPU를 강제로 뺏을 수 있는 방식이다. 하나의 프로세스를 주어진 시간 할당량(time slice 또는 time quantum)동안만 실행을 허락하고, 시간 할당량을 초과하거나 입출력이 발생하면 프로세스 스케줄러는 다른 준비 상태의 프로세스를 선택하여 실행시킨다. 이는 입출력이 거의 없이 길게 CPU를 사용하는 프로세스와 그렇지 않은 다른 프로세스들과 병행 실행시킬 수 있어서 다중 프로그래밍의 기본이 된다. 그러므로 선점방식은 빠른 응답을 요구하는 시분할 시스템에서 주로 사용한다. 장점 : 긴급하게 처리해야 될 높은 우선순위를 가진 프로세스들이 빠르게 처리될 수 있다. 문맥교환에 따른 운영체제의 오버헤드를 중가시킬 수 있으나 모든 프로세스들은 CPU의 공평한 사용을 유지시킨다. 특히, 짧은 작업들은 큰 작업들에 의해 CPU를 독점하는 불리함에서 배제될 수 있다. 결과적으로 프로세스들은 비순차적으로 병행 실행될 수 있고, 짤븐 작업이 긴 작업 뒤에 실행될지라도 좋은 경과(응답)시간을 얻는다. 단점 : 선점 비선점방식다 프로세스간의 문맥교환이 자주 발생하게 되어 운영체제의 오버헤드를 중가시킬 수 있다. 시간 할당량을 초과하는지를 검사할 수 있는 시간 배당에 대한 인터럽트용 클럭(clock) 인 하드웨어/소프트웨어가 요구된다. 그러므로 선점방식의 스케줄링에서는 각 시간 할당량에 대한 인터럽트 레벨의 오버헤드를 최소화하기 위해 노력해야 한다. ▶ 라운드 로빈(Round Robin) 가장 대표적인 선점방식으로 대부분의 시분할 시스템에서 사용하고 있다. FCFS방식에다 시간할당량을 부여하여 시간내에 처리안된 것은 다시 준비상태로 된다. ▶ SRT(Shortest Remaining Time) 비선점인 SJF에 선점 방식을 도입하여 처리중에 있는 프로세스보다 잔여처리 시간이 더 짧은 프로세스가 준비큐에 생기면 실행중인 프로세스를 선점한다. 시분할 처리에 유용하다 이를 위해 프로세스의 최대 처리시간과 이미 사용한 시간을 항상 검사하여 잔여 시간을 알고 있어야 하는 오버헤드가 있다. ▶ 다단계 큐 스케줄링(Multi-level queue) 프로세스들을 우선순위에 따라 시스템 프로세스, 대화형 프로세스, 일괄처리 프로세스 등으로 상위, 중위, 하위 단계의 단계별 준비 큐를 배치한다. ▶ 다단계 피드백 큐 스케줄링(Multi-level Feedback Queue) 멀티레벨 큐에 시간할당량을 부여하여 각 단계마다 일정시간 CPU를 사용후 처리를 다 못했을 경우 하위레벨로 할당한다. ★ 오버헤드 : 근본적으로 해야할 일을 하기 위한 준비나 먼저 처리해야할 일등으로 원래의 목적이 아닌 부가적인 작업을 말한다. 정보처리기사 [필기] 1. 운영체제(4) - 프로세스 스케줄링운영체제(4) - 프로세스 스케줄링 1. 프로세스 스케줄링 (= CPU 스케줄링) - 처리율 증가 - CPU 이용률 증가 - 우선 순위 제도 - 오버헤드(부하) 최소화 - 응답 시간/반환 - 균형 있는 자원의 사용(공평성 유지)
- 무한 연기 회피 2. 프로세스 스케줄링 기법 1) 비선점 스케줄링 (Non Preemptive) : 비효율적, 비양보 2) 선점 스케줄링 (양보) : 효율적 - 선점을 위한 시간 배당에 대한 인터럽트용 타이머 클럭이 필요함 1. 비선점 > FIFO (First-In First-Out) = FCFS (First-Come First-Service)
-> 평균 반환시간 = 평균 실행시간+평균 대기시간 2. 비선점 > SJF (Shortest Job First) - 작업이 끝나기까지의 실행 시간 추정치가 가장 작은 작업을 먼저 실행 실행시간 : A(20초), B(6초), C(3초)
* 제출(도착)시간이 주어졌을 경우 : A(0초), B(1초), C(2초)
-> 실행시간이 큰 작업은 무한연기(기근현상) 가능성 있음 -> 해결(Aging 기법):강제 우선순위 부여 3. 비선점 > HRN (Highest response ratio Next) - 그 작업이 서비스 받을 시간과 서비스를 기다린 시간으로 결정되는 우선순위에 따라 CPU에 할당됨 기출) 우선 순위가 가장 높은 작업
4. 그 외 비선점 스케줄링
: 대기 큐에서 기다리는 각 프로세스마다 우선 순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법 5. 선점 > RR (Round Robin) - Interactive 시스템에 많이 사용 실행시간 : A(8초), B(7초), C(6초)
6. 선점 > SRT (Shortest Remaining Time) - SJF 방식으로 선점형 기법, 현재 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의
7. 그 외 선점 스케줄링 1) 다단계 큐 (MQ, Multi level Queue) 프로세스들을 우선 순위에 따라 시스템 프로세스, 대화형 프로세스, 2) 다단계 피드백 큐 (MFQ, Multi level Feedback Queue) 여러 개의 큐를 두어 낮은 단계로 내려갈수록 프로세스의 시간 할당량을 크게 하는 프로세스 스케쥴링 방식 8. 기타 1) 문맥교환 (Context switching) 다중 프로그래밍 시스템에서 운영체제에 의하여 중앙처리장치가 할당되는 프로세스를 변경하기 위하여 현재 -> 운영체제에서 overhead의 큰 요인 중 하나 2. 노화(aging) 기법 자원이 할당되기를 오랜 시간 동안 기다린 프로세스에 대하여 기다린 시간에 비례하는 높은 우선 순위를 -> 우선 순위스케줄링에서 무한 연기를 방지하기 위한 기법 |
프로세스 들을 우선순위에 따라 시스템 프로세스, 대화형 프로 세 스 일괄 처리 프로세스 등으로 상위 중위 하위 단계의 단계별 준비 큐 를 배치 하는 CPU 스케줄링 기법 - peuloseseu deul-eul useonsun-wie ttala siseutem peuloseseu, daehwahyeong peulo se seu ilgwal cheoli peuloseseu deung-eulo sang-wi jung-wi hawi dangyeui dangyebyeol junbi kyu leul baechi haneun CPU seukejulling gibeob
관련 게시물
저작권 © 2024 ko.apacode Inc.
