저는 이번에 CPU scheduling에 대해서 조사해보았습니다.
1.CPU scheduling 의 정의
일단 이 것을 정의 하려면 Process를 알아야 됩니다. 프로세스는 프로그램이 실행되어 메모리에 적재된 상태를 말합니다. 그 때 컴퓨터는 작업들을 처리하기 위해 이 프로세스들에게 중앙처리장치나 각종 처리기를 할당하게 되는데요. 이 것을 최대한 효율적으로 분배하여 CPU의 유휴시간(idle time-컴퓨터 시스템이 사용 가능한 상태이나 실제적으로 작업을 하지 않는시간)을 줄이고 CPU의 효율성을 높이기 위해 하는 것이 CPU scheduling입니다. 이 것은 컴퓨터가 단일 프로그래밍 환경에서 다중 프로그래밍환경이 되어가면서 필요하게 되었습니다.
2.CPU Scheduling에서 사용되는 대표적인 측량값
(1)CPU Utilization: CPU가 일하는시간/흐른 시간으로 퍼센트 값으로 나타줍니다.
(2)Throughput:: 단위시간당 처리된 프로세스의 수
(3)Turnaround Time: 한 프로세스가 등장해서 이 것이 완전히 끝날 때까지 걸리는 시간= 프소세스가 메모리에 올려지기까지 기다리는 시간+레디큐에서 CPU로 진입하기까지 기다리는 시간+CPU에서 실행되는시간+I/O(input/output: 입출력)를 처리하는 시간
3.Scheduling 결정의 4가지 상황
(1). 한 프로세스가 실행 상태에서 대기상태로 전환될 때
(2). 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때
(3). 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때
(4). 프로세스가 종료될 때
:1-4 방법을 이용하게 되면 non-preemptive scheduling방법을 사용하게 되고,
2-3 방법을 이용하게 되면 preemptive scheduling방법을 사용하게 된다.
4.Scheduling 방식의 종류
(1)선점 스케줄링(preemptive scheduling)
-한 프로세스가 CPU를 차지하고 있을 때 우선 순위가 높은 다른 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 차지할 수 있는 경우
-높은 우선 순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유용
-빠른 응답시간을 요구하는 시분할 시스템에 유용
(2)비선점 스케줄링(nonpreemptive scheduling)
-한 프로세스가 CPU를 할당 받으면 다른 프로세스는 CPU를 점유 못함
-짧은 작업을 수행하는 프로세스가 긴 작업이 종료될 때까지 기다려야함
-모든 프로세스들에게 공정하고 응답시간의 예측이 가능
5.Scheduling Algorithm의 종류
(1).First-Come, First-Served Scheduling(FCFS= FIFO)
-nonpreemptive
-먼저 대기열에 올라온 프로세서부터 하나씩 처리하는 방식이다.
-이 방식은 상당히 비효율적이다. 예를 들어 처음 들어오는 프로세스가 CPU Burst가 클 경우, 다른 중요한 프로세스가 입력될 경우 처리하기가 힘들어진다.
(2)Shortest-Job-First(SJF) Scheduling
-nonpreemptive와 preemptive방식 둘 다 존재한다. 선점형의 방식을 도입할시에는 이 알고리즘의 이름은 Shorttest-remaining-time-first로 바뀐다.
-크기가 작은 프로세스의 순으로 처리를 해주는 알고리즘이다. 이론상으로는 확실한 효과를 가지고 있지만 다음 CPU 요청의 길이를 알 수 없기 때문에 실질적으로는 완벽히 구현을 하지 못한다고 한다. 그래서 자신이 설계한 CPU scheduling방식의 효율성을 비교할 때 쓰이는 scheduling방식이라고 합니다.
(3).Priority Scheduling
-nonpreemptive
-각 프로세스를 특정한 기준으로 우선순위를 따져서 우선순위가 높은 프로세스부터 CPU를 할당하는 방식입니다. 또한 우선순위가 같은 프로세스가 있을 경우에는 FCFS방식으로 우선순위를 정해서 CPU를 할당한다고 합니다. 이 방식은 결정적 문제점을 가지고 있습니다. 무한 블로킹(infinite blocking)와 고사(starvation)이라고 합니다. 우선순위가 낮은 프로세스가 높은 순위에 밀려서 CPU를 할당받지 못하고 계속 기다릴수도 있다고 합니다. 이같은 사실 때문에 1973년에 셧다운한 IBM7094라는 대형 컴퓨터에서 1967년에 생성되었는데 처리되지 못한 낮은 우선순위의 프로세스가 있다는 루머도 있다고 합니다. 이같은 방법을 해결하기 위해 프로세스에게 나이를 부여하는 방법이 있다고 합니다. 나이가 들수록 프로세스의 우선순위를 증가시키는 방법이라고 합니다.
(4).Round-Robin(RR) Scheduling
-preemptive
-이 scheduling은 시분할 시스템을 위해 특별히 설계되었다고 합니다. 일단 FCFS방식에 의해서 프로세스들이 보내지고 각 프로세스는 같은 크기의 CPU시간을 할당받는다고 합니다. 이 같은 시간을 타임퀀텀(time quantum)이라고 하며, 만약 프로세스가 이 정해진 시간내에 프로세스를 끝내지 못해도 다음 프로세스에게 선점당하게 되고, 레디큐로 내려가게 된다고 합니다. 그런데 이 타임퀀텀을 길게 설정하게 될 경우 그냥 FCFS scheduling이 되버립니다. 그리고 짧게 설정할 경우 컨텍스트 스위칭(context switching-다중 프로그램 작성 환경에서 어떤 프로그램의 실현을 중단하고 다른 프로그램의 실행을 재개할 때, 그 프로그램의 재개에 필요한 환경을 다시 설정하는 것)하느라 시간을 너무 많이 잡아먹기 때문에 비효율적이라고 합니다. 그래서 일반적으로 한 타임 퀀텀은 이 컨텍스트 스위칭에 걸리는 시간의 10배로 설정한다고 합니다.
(5).Multilevel Queue Scheduling
-preemptive
-여러 개의 우선순위가 다른 큐를 두고, 각 큐마다 따로 scheduling 알고리즘을 구현해서 CPU를 할당받는다고 합니다. 이 방법도 블로킹(infinite blocking)와 고사(starvation)가 일어날 가능성이 있다고 합니다. 그래서 이 점을 보완하기 위해 Multilevel Feedback Queue Scheduling방식을 사용하게 됩니다. 이는 위 방식은 프로세스들이 큐 사이를 이동하지 않지만, Multilevel Feedback Queue Scheduling은 프로세스들이 큐 사이를 이동할 수 있다고 합니다.
이번에 조사하면서 시간을 계산하는 법도 올리려고 했는데, 아직 이해가 부족해서 좀 더 조사해서 이해해보려고 합니다.
출처:
http://blog.naver.com/anbv3/130001885175
댓글 없음:
댓글 쓰기