O(n) / O(1) 스케쥴러 비교 분석

소개

"O(n) / O(1) 스케쥴러 비교 분석"에 대한 내용입니다.

목차

1. Scheduler

2. Big O 표기 법

3. Linux Scheduler와 Big O 표기 법

4. O(n) 복잡도를 가진 O(n) Scheduler
1) O(n) Scheduler의 동작 설명
2) O(n) Scheduler의 한계

5. O(1) 복잡도를 가진 O(1) Scheduler
1) O(1) Scheduler 기본 동작 설명
2) O(1) Scheduler의 Priority
3) O(1) Scheduler의 한계
4) O(1) Scheduler의 한계 극복 CFS

참고 문헌

본문내용

1. Scheduler
PC에서 프로그램의 구동은 CPU 기준 한 순간에 한가지 작업만이 가능하기 때문에 다수의 작업을 동시에 수행하고자 함에 있어 이를 극복하기 위해 OS를 통해 프로세스 별로 처리 시간을 나눠주며, 사용자는 다중 작업이 동시 수행되는 것처럼 사용할 수 있는 환경을 제공할 수 있다. 이때 스케줄러의 성능에 따라 동일 H/W환경에서 프로세스의 처리에 큰 차이를 느낄 수 있다.
Scheduler는 메모리에 존재하는 여러 프로세스 중 어떤 프로세스(혹 Task)가 CPU의 점유 권한을 가지고 실제 작업을 수행할지 결정해주는 작업으로 크게 세가지 종류가 있다.
 Long-term Scheduler (Job scheduler)
하드 디스크에서 메모리로 프로세를 load 하는 역할을 수행

 Short-term Scheduler (CPU scheduler)
메모리에 있는 프로세스 중 CPU점유 권을 가질 프로세스를 선택하는 역할

참고자료

· https://operatingsystems.tistory.com/entry/OS-스케쥴러-scheduler?category=495588,
· http://jake.dothome.co.kr/preemption/
· International Journal of Control Theory and Applications (ISSN: 0974-5572)
· Understanding the Linux 2.6.8.1 CPU Scheduler by Josh Aas
· University of OSLO Department of Informatics, A Comparison of Two Linux Schedulers, Master thesis, Gang Cheng
· Tuning the task scheduler. "http://doc.opensuse.org/
· Josh Aas. Understanding the linux 2.6.8.1 cpu scheduler.
· M. Tim Jones. Anatomy of linux process management.
· Linux performance and tuning guidelines.
· S. Lauzac, R. Melhem, and D. Moose, “An efficient RMS admission control and its application to multiprocessor scheduling”, 『In Parallel Processing Symposium, 1998. IPPS/SPDP 1998. in Proc. First Merged International... and Symposium on Parallel and Distributed Processing 1998. IEEE』, pp. 511-518, : Mar. 1998.