CPU Scheduling 썸네일형 리스트형 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가 수행을 요청해 왔다고.. 더보기 CPU Scheduling - Scheduling Criteria Scheduling Criteria, 스케쥴링 평가 기준 CPU Scheduling Algorithm의 종류에는 여러가지가 있다. 이러한 다양한 Algorithm들의 특성을 나타내는 몇가지 기준들이 있는데 이런 기준들을 Scheduling Criteria이라고 한다. Scheduling Criteria에는 여러가지 있을 수 있지만 대표적으로 아래의 5가지가 있다. 1. CPU Utilization : CPU에 얼마나 많은 부하가 걸리는가? 2. Throughput : 단위 시간당 처리 할 수 있는 Process의 수는 얼마인가? 3. Turnaround Time : 특정 Process가 시작하여 종료하는데 얼마나 걸리는가? 4. Waiting Time : Process가 Ready Queue에서 대기하는.. 더보기 CPU Scheduling - DIspatcher DIspatcher, 디스패처 DIspatcher란 CPU의 제어권을 STS(Short-Term Scheduling)에 의하여 선택된 Process에게 넘겨주는 모듈을 말한다. 이러한 DIspatcher의 기능은 아래의 3가지이다. 1. Context Switching 2. User Mode로 전환 3. 사용자 프로그램의 재시작을 위해 해당주소로 이동 DIspatcher의 경우 STS에 의해서 수행되기 때문에 Process Switching이 일어 날때마다 수행된다. 때문에 고속 수행이 가능해야만 한다. DIspatcher가 한 Process를 멈추고 다른 Process에게 CPU의 제어권을 넘기는 데 걸리는 시간을 DIspatch Latency라고 한다. 더보기 이전 1 2 다음
