Operating Systems Chapter 04 CPU 스케줄링

1. 스케줄링 고려사항 Scheduling Level (스케줄링 단계) CPU 스케줄링이란 어떤 프로세스에게 먼저 CPU를 배정할지를 결정하는 작업을 말한다. 준비상태에 있는 여러 프로세스 중 어떤 프로세스에게 CPU를 할당할 것인가를 결정하는 것이 매우 중요하고 이는 시스템의 성능을 결정짓는 CPU 스케줄러의 몫이다. Level 1 : high level scheduling(상위 단계 스케줄링) 어떤 작업을 시스템이 받아들일지 혹은 거부할지를 결정하는 단계, 즉 시스템 상황을 고려하여 해당 작업의 승인 여부를 결정하는 단계 로 승인 스케줄링(admission scheduling)이라고도 함. Level 2 : middle level scheduling(중간 단계 스케줄링) 여러 프로세스 중 어떤 프로세스를 활성화 시킬 것인가 결정하는 단 계. 시스템의 과부하를 방지하기 위해 활성화 시킬 프로세스의 수를 조절하는 단계 Practical Operating Systems

1. 스케쥴링 고려사항 Scheduling Level (스케줄링 단계) Level 3 : low level scheduling(하위 단계 스케줄링) 활성화된 프로세스 중 어떤 프로세스에게 CPU를 할당할 것인지 결정하는 단계 현대의 스케줄러는 대부분 중간단계와 하위단계 스케줄링으로 구성되어 있다. Practical Operating Systems

1. 스케줄링 고려사항 admission Practical Operating Systems

1. 스케줄링 고려사항 프로세스 스케줄링 방법 별 분류 Preemptive Scheduling(선점형 스케줄링) 프로세스 스케줄링에 있어서 preemptive 라 함은 ‘선점할 수 있는＇혹은 ‘뺏을 수 있는＇이란 표현으로 운영체제가 CPU와 같은 자원을 먼저 소유하고 있다가 필요할 때 나눠준다는 의미이다. Non-preemptive Scheduling(비선점형 스케줄링) 어떤 프로세스가 CPU를 점유 하면 다른 프로세스가 이를 선점할 수 없는(뺏을 수 없는) 방식이다. 즉, 실행단계에 들어가 CPU를 사용하면 그 프로세스가 종료되거나 자발적으로 대기 상태에 들어가기 전까지 계속 실행된다. Practical Operating Systems

1. 스케줄링 고려사항 Preemptive Scheduling(선점형 스케줄링) 어떤 프로세스가 CPU를 할당 받아 실행 중에 있어도 운영체제가 CPU를 강제로 선점할 수 있는 방식이다. 빠른 응답 시간을 요하는 대화형시스템이나 시분할 시스템에 적합하며 현재 대부분의 하위 단계 스케줄러는 선점형 스케줄링 방식이다. 선점형 스케줄링의 종류 Round-Robin SRT(Shortest Remaining Time) - 선점 SJF MLQ(Multi-Level Queue) MFQ(Multi-level Feedback Queue) Practical Operating Systems

1. 스케줄링 고려사항 Non-preemptive Scheduling(비선점형 스케줄링) 비선점형 스케줄링은 선점형보다 스케줄러의 작업량이 적고 문맥교환에 의한 낭비가 적다는 장점이 있다. 그러나 CPU 사용시간이 긴 프로세스로 인한 CPU 사용시간이 짧은 여러 프로세스들이 오랫동안 기다리게 되어 전체의 throughput이 떨어지게 되는 단점이 있다. 일괄처리시스템에서 사용하던 방식이다. 비선점형 스케줄링의 종류 우선순위(Priority) FCFS(First- Come First-Served) SJF(Shortest Job First) HRRN(Highest Response Ration Next) Practical Operating Systems

1. 스케쥴링 고려사항 Priority (우선순위) Static priority (고정우선순위) : 운영체제가 프로세스에게 우선순위 를 부여하면 프로세스가 끝날 때까지 해당 우선순위가 바뀌지 않 은 방식으로 구현이 쉽다는 장점이 있다. dynamic priority (변동우선순위) : 프로세스 생성 시 부여 받은 우선 순위가 프로세스 작업 중간에 변하는 방식으로 구현이 복잡하지만 시스템의 효율을 높일 수 있다는 장점이 있다. 참고 : 우선순위의 표시는 낮은 수치가 높은 우선순위를 의미하고 있음. Practical Operating Systems

1. 스케쥴링 고려사항 Consideration for Scheduling (스케줄링 고려사항) 프로세스를 작업의 형태에 따라 구분 CPU bound process (CPU 영역 프로세스) : CPU를 많이 사용하는 프로세스 I/O bound process (I/O 영역 프로세스) : 입출력을 많이 사용하는 foreground process (전면 프로세스) : 상호작용이 가능한 프로세스 (상호작용 프로세스) background process (후면 프로세스) : 사용자와 상호작용이 없는 프로세스(일괄작업 프로세스) Practical Operating Systems

1. 스케쥴링 고려사항 Consideration for Scheduling (스케줄링 고려사항) Practical Operating Systems

1. 스케줄링 고려사항 Scheduling goals (스케줄링의 목적) 공평성 : 모든 프로세스는 공평하게 작업이 진행되어야 한다. 효율성 : 시스템 전체의 성능을 높일 수 있도록 계획되어야 한다. 확장성 : 프로세스의 개수가 증가함에 따라 성능에 갑작스런 변화가 없어야 한다. 자원의 활용 : 시스템 자원을 고루 균형 있게 사용할 수 있어야 한다 시스템의 효율을 높이기 위해서는 일정 부분 공평성에 희생이 따른다 Practical Operating Systems

1. 스케줄링 고려사항 시스템 평가 기준들 CPU utilization (사용률) : 전체 시스템의 동작기간 중 CPU가 사용된 시간을 측정. 100%가 이상적이지만 실제 90%에도 못 미침 Throughput (처리량) : 단위 시간당 작업을 마친 프로세스의 수로 측정 Waiting time (대기시간) : 작업을 요청한 프로세스들이 작업 시작 전까지 대기하는 시간의 합 Response time (응답시간) : 사용자 요구에 대하여 반응하는 시간을 측정 시스템의 효율성 향상을 위하여 CPU 사용률, 처리량을 극대화하고 대기시간과 응답시간을 줄이려고 한다. 또한 공평성 확보도 필요 Practical Operating Systems

2. 스케줄링 알고리즘 First Come, First Served (FCFS) 스케줄링 가장 단순한 스케줄링 알고리즘, FIFO라고도 불리지만 Queue 구조와 구분하기 위해 FCFS라 함. 프로세스는 queue에 도착한 순서대로 실행되는 알고리즘이다. 따라서 한번 실행되면 해당 프로세스가 종료될 때까지 CPU를 사용하는 비선점형 알고리즘이다. 초기 일괄처리 시스템에서 사용 장점 : 단순하고 공평하다 단점 : 시스템 효율성이 떨어짐, 평균 응답시간이 길어짐. Practical Operating Systems

2. 스케줄링 알고리즘 스케줄링 알고리즘 FCFS(First Come First Service) 스케줄링 - non preemptive 가장 간단한 기법으로, 프로세스들은 대기 큐(준비 큐)에 도착한 순서에 따라 CPU를 할당 받는다 FCFS 스케줄링의 특징 일단 프로세스가 CPU를 차지하면 완료될 때까지 수행 다른 방식에 비하여 작업 완료 시간 예측 용이 긴 작업이 짧은 작업을 오랫동안 기다리게 할 수 있으며, 중요하지 않은 작업이 중요한 작업을 기다리게 하므로 어느 정도 불합리 대화식 사용자들에게는 부적합 Practical Operating Systems

2. 스케줄링 알고리즘 Shortest Job First (SJF) 스케줄링 FCFS와 유사한 방식이지만 프로세스가 준비 큐에 있는 순서대로 실행되는 것이 아니라 준비 큐에 있는 프로세스들 중에서 실행시간이 가장 짧은 작업부터 CPU를 할당하는 방식으로 비선점형 알고리즘이다. Practical Operating Systems

2. 스케줄링 알고리즘 SJF(Shortest Job First) 스케줄링 - non preemptive FCFS 보다 평균 대기 시간 감소 큰 작업에는 FCFS에 비하여 예측하기 어려움 수행하게 될 작업이나 프로세스가 얼마나 긴 것인가를 정확히 알아야 하는데, 이 정보는 얻기가 어려움 최선의 방법은 수행 예측을 사용자에 의존하는 것 장점 : FCFS에 비하여 평균 대기 시간을 줄여 시스템의 효율을 향상 단점 : 현재 사용되지 않은 방식이다. FCFS 스케줄링 방식보다 효율성은 기대되나 프로세스의 종료시간을 정확하게 예측하기가 어려운 스케줄링 방식이다. 공평성에 위배된다. 즉, 준비 큐에 먼저 도착한 프로세스라도 수행시간이 많이 걸린다는 이유로 계속 지연이 되는 현상(아사현상, starvation)이 발생하게 된다. 이러한 아사현상은 aging(나이먹기)으로 해결될 수 있다. Practical Operating Systems

2. 스케줄링 알고리즘 Round Robin(라운드 로빈) 스케쥴링 선점형(preemptive) 알고리즘 방식으로 가장 단순하고 대표적인 방식이다. FCFS방식처럼 먼저 도착한 프로세스를 순서대로 선정하는데 일정 시간(time slice)을 할당하여 그 시간 만큼 수행 후 준비 큐 맨 뒤로 돌아간다. 또한 priority(우선 순위)가 적용되지 않은 방식이다. Practical Operating Systems

2. 스케줄링 알고리즘 스케줄링 알고리즘 라운드 로빈(Round Robin) 스케줄링 – preemptive FCFS로 프로세스들이 내보내지며 각 프로세스는 같은 크기의 CPU 시간을 할당 받음 만약 프로세스가 CPU 시간이 만료될 때까지 처리를 완료하지 못하면 그 CPU는 대기 중인 다음 프로세스로 넘어가며 (preemptive), 실행 중이던 프로세스는 준비 완료 리스트의 가장 뒤로 보내짐 라운드 로빈 스케줄링의 특징 시분할 방식의 시스템에서 효과적 할당 시간(time quantum)의 크기는 컴퓨터 시스템의 효과적인 동작에 절대적인 영향을 미침. (보통 time quantum의 크기는 10~100milli seconds) 할당 시간이 크면 FCFS 방식과 동일 할당 시간이 작으면, 자주 문맥 교환이 발생하므로 문맥 교환을 하려는 오버헤드가 증가 Practical Operating Systems

2. 스케줄링 알고리즘 Practical Operating Systems

2. 스케줄링 알고리즘 Time slice와 문맥교환과의 관계 Time slice의 크기를 크게 설정할 경우 사용자 측면에서 프로세스의 작업 시간이 길어 시스템의 동시성이 떨어짐 Time slice의 크기를 작게 설정할 경우 잦은 문맥교환으로 인한 소비되는 시간이 발생 UNIX 운영체제의 time slice 평균 값은 100msec 이지만 다단계 피드백 큐 스케줄링 사용 시 우선순위에 따라 10 ~ 200msec의 다양한 폭을 가짐 Practical Operating Systems

2. 스케줄링 알고리즘 SRTF(Short Remaining Time First) 스케줄링 – preemptive 라운드 로빈과 SJT 스케쥴링 방식을 혼합 SJF 스케줄링과 마찬가지로 새로 도착한 프로세스를 포함하여 처리가 완료 준비 큐에 있는 프로세스들 중 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행 Practical Operating Systems

2. 스케줄링 알고리즘 SRTF(Short Remaining Time First) 스케줄링 – preemptive 현재 실행 중인 프로세스라도 남은 처리 시간이 더 짧다고 판단되는 프로세스가 준비 큐에 생기면 언제라도 실행 중인 프로세스가 선점될 수 있다 SJF 기법에 선점 방식을 도입한 변형된 방법으로서 시분할 시스템에 유용 수행 중인 각각의 작업들의 실행 시간을 추적 보유하고 있어야 한다(선점 때문에 오버헤드가 증가) 긴 작업은 SJF보다 대기 시간이 김 SRT에서의 대기 시간은 도착 시간에서 CPU를 할당 받기까지 대기한 시간을 빼서 계산 작업의 길이에 대한 추정이 어렵고 아사현상 발생 때문에 잘 사용하지 않는다. Practical Operating Systems

2. 스케줄링 알고리즘 Highest Response Ration Next(HRRN) 스케줄링 - 비선점형 SRTF 스케줄링 방식에서 발생할 수 있는 아사현상을 해결하고 프로세스 작업시간 측정이 어려움을 완화시키기 위해 만들어진 알고리즘이다. 프로세스의 우선순위를 결정할 때에 다음과 같은 기준으로 결정한다. 기다린 시간 + CPU 사용 시간(버스트시간) 우선순위 = CPU 사용 시간(버스트시간) SRT 스케줄링 알고리즘과 같이 실행 시간이 짧은 프로세스에게 우선순위를 높게 주지만, 기다린 시간(waiting time)을 고려함으로써 아사현상을 줄일 수 있는 알고리즘이다. 하지만 여전히 공평성이 위배되어 잘 사용되지 않는다. Practical Operating Systems

2. 스케줄링 알고리즘 스케줄링 알고리즘 HRN(Highest Response ratio Next) 스케줄링 - non preemptive SJF의 약점, 특히 긴 작업과 짧은 작업 간의 지나친 불평등을 어느 정도 보완한 기법 HRN 스케줄링의 특징 일단 한 작업이 CPU를 차지하면 그 작업은 완성될 때까지 실행 긴 작업과 짧은 작업 간의 불평등을 어느 정도 완화 우선순위 =(대기 시간 + 버스트 시간) / 버스트 시간 = 시스템 응답 시간 짧은 작업이나 대기 시간이 큰 작업은 우선순위가 높아짐 2 3 4 5 우선순위 Practical Operating Systems

2. 스케줄링 알고리즘 다단계 큐(Multi Level Queue) 스케줄링 – preemptive 작업들을 여러 종류의 그룹으로 나누어 우선 순위를 가진 여러 개의 큐를 이용하는 스케줄링 기법 그룹화된 작업들은 각각의 준비 큐에 넣어두고 각 큐의 독자적인 스케줄링 알고리즘에 따라서 CPU를 할당 받는 방법 시스템에 상위 단계에서 하위 단계까지의 큐로 분할되어 있다 Practical Operating Systems

2. 스케줄링 알고리즘 다단계 큐 스케줄링 – preemptive 다단계 큐 스케줄링의 특징 다단계 큐 알고리즘은 준비 상태 큐를 여러 종류로 분할해 둠 각 큐는 자신만의 독자적인 스케줄링을 가지고 있다 각각의 서로 다른 작업들이 다른 묶음으로 분류될 수 있을 때 사용되는 알고리즘 일괄 처리 작업이 실행 중일지라도 상위 단계 큐에 작업이 들어오면 일괄 처리 작업은 CPU를 내주어야 되므로 “선점”당해야 한다 한 큐에서 다른 큐로의 작업 이동 불가 즉, 각 큐들 간에 작업 이동은 불가능 Practical Operating Systems

2. 스케줄링 알고리즘 다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링 - preemptive 일반적으로 프로세스들은 CPU의 사용 시간에 따라 입출력 위주와 CPU 위주로 구분 입출력 위주와 CPU 위주인 프로세스의 특성에 따라 서로 다른 CPU의 time slice를 부여 Practical Operating Systems

2. 스케줄링 알고리즘 다단계 피드백 큐 스케줄링 - preemptive 다단계 피드백 큐 스케줄링의 특징 짧은 작업에 유리, 입출력 위주의 작업들에 우선권을 준다 가능한 한 빨리 작업의 특성을 알고 그것에 맞게 해당 작업을 스케줄링 프로세스가 보다 하위 단계의 큐로 옮겨갈수록 주어진 할당 시간은 점차 크게 설정 함.( 이유 : 더 높은 단계에 있는 큐의 프로세스가 더 높은 우선순위를 갖기 때문) 이 기법은 CPU에 대한 요구량에 따라 프로세스들을 분류하는 데 이상적 변동 우선순위 방식의 전형적인 예 Practical Operating Systems

스케줄링 알고리즘들의 비교 프로세스의 반환시간과 대기시간 프로세스 3개가 동시에 도착하여 P1, P2, P3 순으로 실행 *Gantt 챠트 : 참여한 각 프로세스의 시작과 종료 시간을 포함하여 특정 스케줄링 기법을 도시하는 막대형 챠트임.

2. 스케줄링 알고리즘의 예 SJF 스케줄링의 적용 예 (대기시간) Practical Operating Systems

2. 스케줄링 알고리즘의 예 FCFS 스케줄링의 예 1 Practical Operating Systems

2. 스케줄링 알고리즘의 예 SJF 스케줄링의 예 Practical Operating Systems

2. 스케줄링 알고리즘의 예 Round Robin(라운드 로빈) 스케줄링의 예 시간 할당량 = 5 Practical Operating Systems

2. 스케줄링 알고리즘의 예 알고리즘의 평가 예) 왼쪽과 같이 5개의 프로세스가 시간 0 을 기준으로 순서대로 도착했을 때 각 프로세스에 대하여 FCFS, SJF, RR (시간할당량=10) 스케줄링의 평균대기 시간을 조사해 보자 FCFS 방식의 간트 도표 프로세스 버스트시간 p1 10 p2 29 p3 3 p4 7 p5 12 p1 p2 p3 p4 p5 10 39 42 49 61 평균대기시간은 (p1+p2+p3+p4+p5)/5=(0+10+39+42+49)/5 = 28 Practical Operating Systems

2. 스케줄링 알고리즘의 예 알고리즘의 평가 예) 왼쪽과 같이 5개의 프로세스가 시간 0 을 기준으로 순서대로 도착했을 때 각 프로세스에 대하여 FCFS, SJF, RR (시간할당량=10) 스케줄링의 평균대기 시간을 조사해 보자 SJF 방식의 간트 도표 프로세스 버스트시간 p1 10 p2 29 p3 3 p4 7 p5 12 p3 p4 p1 p5 p2 3 10 20 32 61 평균대기시간은 (p3+p4+p1+p5+p4)/5=(0+3+10+20+32)/5 = 13 Practical Operating Systems

2. 스케줄링 알고리즘의 예 알고리즘의 평가 예) 왼쪽과 같이 5개의 프로세스가 시간 0 을 기준으로 순서대로 도착했을 때 각 프로세스에 대하여 FCFS, SJF, RR (시간할당량=10) 스케줄링의 평균대기 시간을 조사해 보자 RR 방식의 간트 도표 (시간할당량=10) 프로세스 버스트시간 p1 10 p2 29 p3 3 p4 7 p5 12 p1 p2 p3 p4 p5 p2 p5 p2 10 20 23 30 52 40 50 61 P1의 대기시간은 0, p2의 대기시간은 32(=10+(40-20)+(52-50)), p3의 대기시간은 20, p4의 대기시간은 23, p5의 대기시간은 40(=30+(50-40))이므로 평균대기시간은 (p1+p2+p3+p4+p5)/5=(0+32+20+23+40)/5 = 23 Practical Operating Systems

2. 스케줄링 알고리즘의 예 알고리즘의 평가 예) 왼쪽과 같이 5개의 프로세스가 시간 0 을 기준으로 순서대로 도착했을 때 각 프로세스에 대하여 FCFS, SJF, 비선 점 우선순위, RR(시간할당량=1) 스케줄 링의 평균대기 시간을 조사해 보자 FCFS 방식의 간트 도표 프로세스 버스트시간 우선순위 p1 10 3 p2 1 p3 2 p4 4 p5 5 p1 p2 p3 p4 p5 10 11 13 14 19 평균대기시간은 (p1+p2+p3+p4+p5)/5=(0+10+11+13+14)/5 = 9.6 Practical Operating Systems

2. 스케줄링 알고리즘의 예 알고리즘의 평가 예) 왼쪽과 같이 5개의 프로세스가 시간 0 을 기준으로 순서대로 도착했을 때 각 프로세스에 대하여 FCFS, SJF, 비선 점 우선순위, RR(시간할당량=1) 스케줄 링의 평균대기 시간을 조사해 보자 SJF 방식의 간트 도표 프로세스 버스트시간 우선순위 p1 10 3 p2 1 p3 2 p4 4 p5 5 p2 p4 p3 p5 p1 1 2 4 9 19 평균대기시간은 (p1+p2+p3+p4+p5)/5=(9+0+2+1+4)/5 = 3.2 Practical Operating Systems

2. 스케줄링 알고리즘의 예 알고리즘의 평가 예) 왼쪽과 같이 5개의 프로세스가 시간 0 을 기준으로 순서대로 도착했을 때 각 프로세스에 대하여 FCFS, SJF, 비선 점 우선순위, RR(시간할당량=1) 스케줄 링의 평균대기 시간을 조사해 보자 비선점 우선순위 방식의 간트 도표 프로세스 버스트시간 우선순위 p1 10 3 p2 1 p3 2 p4 4 p5 5 p2 p5 p1 p3 p4 1 6 18 16 19 평균대기시간은 (p1+p2+p3+p4+p5)/5=(6+0+16+18+1)/5 = 8.2 Practical Operating Systems

2. 스케줄링 알고리즘의 예 알고리즘의 평가 예) 왼쪽과 같이 5개의 프로세스가 시간 0 을 기준으로 순서대로 도착했을 때 각 프로세스에 대하여 FCFS, SJF, 비선 점 우선순위, RR(시간할당량=1) 스케줄 링의 평균대기 시간을 조사해 보자 RR 방식(시간할당량=1)의 간트 도표 프로세스 버스트시간 우선순위 p1 10 3 p2 1 p3 2 p4 4 p5 5 p1 p2 p3 p4 p5 p1 p3 p5 p1 p5 p1 p5 p1 p5 p1 1 10 8 9 12 2 3 4 5 6 7 11 13 14 19 평균대기시간은 (p1+p2+p3+p4+p5)/5=(9+1+5+3+9)/5 = 5.4 Practical Operating Systems

2. 스케줄링 알고리즘의 예 알고리즘의 평가 예) 왼쪽과 같이 5개의 프로세스가 시간 0 을 기준으로 순서대로 도착했을 때 각 프로세스에 대하여 FCFS, SJF, 비선 점 우선순위, RR(시간할당량=1) 스케줄 링의 평균반환시간을 조사해 보자 FCFS 방식의 간트 도표 프로세스 버스트시간 우선순위 p1 10 3 p2 1 p3 2 p4 4 p5 5 p1 p2 p3 p4 p5 10 11 13 14 19 평균반환시간은 (p1+p2+p3+p4+p5)/5=(10+11+13+14+19)/5 = 13.4 Practical Operating Systems

2. 스케줄링 알고리즘의 예 알고리즘의 평가 평균반환시간은 (p1+p2+p3+p4+p5)/5=(19+1+4+2+9)/5 = 7 예) 왼쪽과 같이 5개의 프로세스가 시간 0 을 기준으로 순서대로 도착했을 때 각 프로세스에 대하여 FCFS, SJF, 비선 점 우선순위, RR(시간할당량=1) 스케줄 링의 평균반환시간을 조사해 보자 SJF 방식의 간트 도표 프로세스 버스트시간 우선순위 p1 10 3 p2 1 p3 2 p4 4 p5 5 p2 p4 p3 p5 p1 1 2 4 9 19 평균반환시간은 (p1+p2+p3+p4+p5)/5=(19+1+4+2+9)/5 = 7 Practical Operating Systems

2. 스케줄링 알고리즘의 예 알고리즘의 평가 예) 왼쪽과 같이 5개의 프로세스가 시간 0 을 기준으로 순서대로 도착했을 때 각 프로세스에 대하여 FCFS, SJF, 비선 점 우선순위, RR(시간할당량=1) 스케줄 링의 평균반환시간을 조사해 보자 비선점 우선순위 방식의 간트 도표 프로세스 버스트시간 우선순위 p1 10 3 p2 1 p3 2 p4 4 p5 5 p2 p5 p1 p3 p4 1 6 18 16 19 평균반환시간은 (p1+p2+p3+p4+p5)/5=(16+1+18+19+6)/5 = 12 Practical Operating Systems

2. 스케줄링 알고리즘의 예 알고리즘의 평가 예) 왼쪽과 같이 5개의 프로세스가 시간 0 을 기준으로 순서대로 도착했을 때 각 프로세스에 대하여 FCFS, SJF, 비선 점우선순위, RR(시간할당량=1) 스케줄 링의 평균반환 시간을 조사해 보자 RR 방식(시간할당량=1)의 간트 도표 프로세스 버스트시간 우선순위 p1 10 3 p2 1 p3 2 p4 4 p5 5 p1 p2 p3 p4 p5 p1 p3 p5 p1 p5 p1 p5 p1 p5 p1 1 10 8 9 12 2 3 4 5 6 7 11 13 14 19 평균반환시간은 (p1+p2+p3+p4+p5)/5=(19+2+7+4+14)/5 = 9.2 Practical Operating Systems