Scheduling Algorithm 썸네일형 리스트형 CPU Scheduling - Scheduling Algorithm_6 Multiple -Processor Scheduling(이하 MPS), 다중 처리기 스케쥴링 이전까지 소개했던 알고리즘들은 Processor 즉, 처리기가 하나일때의 알고리즘들이다. 그렇다면 만일 Processor가 여러개라면 어떻게 스케쥴링을 해야할까? Processor가 여러개라고 해도 Processor를 다루는 방식에도 차이가 있다. 예전 포스트에서도 소개 한적이 있는데 바로 그것이 Symmetric( or Homogeneous) Multi-Processing(이하 SMP)과 Asymmetric( or Heterogeneous) Multi-Processing(이하 AMP)이다. 여러개의 Processor가 있으면 Load Sharing(부하 분담, 많은 처리량을 분담해서 처리)이 가능해 지고 각 P.. 더보기 CPU Scheduling - Scheduling Algorithm_5 Multilevel Queue(이하 MQ) Scheduling Algorithm, 멀티레벨 스케쥴링 알고리즘 MQ 알고리즘은 Process를 종류별로 구분하여 그룹으로 만들고 그 그룹별로 Queue를 제공한다. 그리고 그 그룹별로 별도의 Priority를 주어 Process를 수행하는 방식이다. 즉, 별도의 Priority를 가진 Ready Queue를 여러개로 나눈 알고리즘이다. MQ 알고리즘에서 각각의 Queue들은 별도의 스케쥴링 알고리즘을 가지고 있다. Process들은 영구적으로 한 Queue에 소속되어 수행되는데 각 Qeueu별로 우선순위를 가지고 있기 때문에 각각 다른 수행 시간을 가지게 된다. 하지만 이런 알고리즘의 가장 큰 문제점은 Starvation이다. 때문에 Aging기법이 필요하게.. 더보기 CPU Scheduling - Scheduling Algorithm_4 Round Robin(이하 RR) Algorithm RR알고리즘은 Process에게 일정 시간동안 CPU의 제어권을 주고 시간이 종료되면 다음 Process에게 제어권을 넘기는 알고리즘이다. 주로 Time-Sharing System에서 사용하는 알고리즘으로 FCFS 알고리즘에 Time Quantum q(사용제한시간)을 넣어 Preemptive 기능을 추가시키고 Ready Queue를 Circle Queue로 구현하여 대기 중인 Process를 순환하면서 제어권을 주는 방법이다. 보통 Time Quantum(이하 q)은 10~100 milliseconds정도로 정한다. 만일 Process가 제한시간 q가 끝나기 전에 수행이 종료되면 Ready Queue에서 다음 Process를 찾아서 수행시킨다. 하지만 .. 더보기 CPU Scheduling - Scheduling Algorithm_3 Priority Scheduling(이하 PS), 우선순위 스케쥴링 Priority Scheduling이란 각각의 Process에게 우선순위를 주어 그 우선순위에 따라 스케쥴링 하는 방식이다. SJF 알고리즘의 경우 CPU-Burst Time의 값이 작은 순으로 스케쥴링을 하고 PS의 경우 Priority의 값이 작은 순으로 스케쥴링을 한다. 즉, Priority의 값이 작을수록 높은 우선순위를 가지게 되는 것이다. 예를 들어보자. P1, P2, P3, P4의 CPU-Burst Time의 값과 Priority가 아래와 같다고 보자. 이를 PS 알고리즘을 이용해서 스케쥴링 한 결과를 Grantt Chart로 나타내면 아래와 같다. 이 결과 Average Waiting Time은 (0+1+6+16+18)/5.. 더보기 CPU Scheduling - Scheduling Algorithm_2 Shortest-Job-First(이하 SJF) Algorithm SJF 알고리즘의 경우 더 정확히 말한다면 Shortest-Next CPU Burst가 더 적절한 표현이다. 왜냐하면 SJF 알고리즘은 다음에 수행될 Process들 중에서 CPU Burst Time이 짧은 것부터 수행하기 때문이다. 예를 들어보자. Process P1, P2, P3, P4가 있고 각각의 CPU-Burst Time이 아래와 같다고 가정하자. 이 Process들을 SJF에 따라 스케쥴링 한걸 Grandtt Chart로 나타내면 아래와 같다. 이때 Average Waiting Time은 (0+3+9+16)/4 = 7 milliseconds이다. 만일 이 Process들을 FCFS 알고리즘에 따라서 스케쥴링 한다면 Average.. 더보기 CPU Scheduling - Scheduling Algorithm_1 Scheduling Algorithm, 스케쥴링 알고리증 First-Come, First-Served Scheduling(이하 FCFS) 가장 단순한 형태의 알고리즘으로 First-In, First-Out(FIFO) Queue에 의해서 구현된다. FCFS는 말그대로 먼저 처리를 요청한 Process를 먼저 처리하는 방식으로 Process의 PCB를 Linked List로 연결시켜 CPU의 상태가 대기상태로 바뀌면 현재의 PCB를 제거하고 다음 PCB에게 CPU를 제어권을 넘긴다. FCFS의 경우 단순하고 구현하기 쉽지만 Average Waiting Time(평균 대기 시간)면에서 보면 비효율적이다. 예를 들어보자. 만일 아래와 그림과 같이 순서대로 Process P1, P2, P3가 수행을 요청해 왔다고.. 더보기 이전 1 다음
