스케줄링 = 운영체제가 공정하고 합리적으로 자원(CPU, 디스크, 메모리 등등) 을 배분하는 방법 - 모든 프로세스(및 스레드)는 실행되기 위해 자원을 필요
CPU 스케줄링 = 운영체제가 공정하고 합리적으로 CPU를 배분하는 방법 - 모든 프로세스(및 스레드)는 실행되기 위해 CPU를 필요로 함 - CPU 자원은 한정되어 있고 실행 중인 프로세스는 여러 개
: 정해진 시간마다 돌아가면서 cpu를 사용하면 XXX : 우선순위(PCB에 명시)가 다르다!!!! - 우선순위가 높을수록 더 많이 더 자주 할당받아서 실행!!!!! - 우선순위 확인 명령어 : $ ps -el : PRI, NI : 낮을수록 높은 우선순위
우선순위의 차이를 보이는 대표적인 프로세스 유형 : I/O bound process, CPU bound process, 일부 백그라운드 프로세스 - I/O bound(입출력장치가 이용하는 시간이 많은 프로세스)가 CPU bound(CPU를 사용하는 시간이 많은 프로세스)보다 우선순위가 높다.
- 일반적으로 CPU사용->입출력장치 사용->CPU 사용->....이렇게 이루어진다 - cpu 사용 시간 : CPU burst : 예시) 컴파일 작용 등등 - I/O 사용 시간 : I/O burst - I/O bound는 조금만 실행해도 곧바로 대기상태에 접어듬 : 한동안 부를 일이 없음 - 입출력장치는 cpu 보다 연산속도가 느림
CPU 우선순위 연산 방법 == CPU 스케줄링 알고리즘
스케줄링 큐(Queue) - 자원은 한정되어 있고 실행 중인 프로세스는 여러 개 - 어떤 프로세스는 메모리, 어떤 프로세스는 cpu, 어떤 프로세스는 디스크 등등 : 요구사항이 서로 다름 - 프로세스들의 요구사항을 일목요연하게 관리하는 방법 == "줄" : 각각 사용하고 싶은 자원에 pcb를 삽입하고 우선순위에 맞게 할당받을 수 있음
- 자료구조에서 Queue는 먼저삽인된 데이터는 먼저 나옴 (FIFO : frist in frist out) - 운영체제가 관리하는 큐는 우선순위별로 나가기에 꼭 FIFO가 아님!!!!!!!!!
- 대표적인 스케줄링 큐
- 준비 큐 (ready queue, run queue ) : CPU 이용을 기다리는 프로세스들의 큐 - 지금 당장이라도 자원을 할당받아 할 수 있지만, 아직 차례가 아닌 것 - 대기 큐 : 대기 상태 프로세스들의 큐 (입출력 요청) - 지금 당장 실행이 불가!!!! 보통 입출력을 기다리면서 발생 - 여러가지 종류가 있음 : 프린터기 대기큐, CD-ROM 대기큐, 하드디스크 대기큐
- 우선순위 낮은 프로세스가 먼저 큐에 삽입되었어도 우선순위 높은 프로세스가 먼저 처리될 수 있음
선점형 스케줄링가 비선점형 스케줄링 - 한 프로세스 실행 도중 다른 급한 프로세스가 실행할 때!!!!! - 선점형 스케줄링 : 현재 실행 중인 프로세스의 자원을 빼앗아 해당 프로세스에게 할당 - 타임아웃 기반의 문맥교환 - 장점 : 프로세스에 자원을 고루 할당 가능 - 단점 : 문맥 교환 과정의 오버헤드 (성능저하) - 비선점형 스케줄링 : 현재 실행 중인 프로세스 실행이 끝날 때까지 해당 프로세스 대기 - 장점 : 고르지 않은 자원 분배 - 단점 : 문맥 교환 과정에서의 오버헤드 적음 - 더 유리한 상황에 맞게 활용이 됨
CPU 스케줄링 알고리즘
*전공서 기준 CPU 스케줄링 알고리즘 : 운영체제마다 CPU 스케줄링 알고리즘이 다름 - 큰 그림을 그리기 위함
CPU 스케줄링 알고리즘 목록
선입 선처리 스케줄링 (FIFO 스케줄링 , FCFS 스케줄링) - CPU를 먼저 요청한 프로세스부터 CPU 할당 - 준비 큐에 삽입된 순서대로 실행되는 비선점형 스케줄링 - 합리적이고 공정한 방법은 아님 : 실행시간이 긴 것이 먼저 들어오면 후의 프로세스는 실행시간에 비해 너무 오래 기다림 -> 부작용: 호위 효과 (convoy effect) (실행시간에 비해 오래 기다림) - A(11) B(3) C(7)을 삽입 : A(11)->B(3, 11초 기다림)->C(7, 14초 기다림)
최단 작업 우선 스케줄링 (SJF 스케줄링) - 준비 큐 프로세스 중 CPU 이용 시간이 짧은 프로세스부터 실행 : 호위효과 방지 - 대기시간이 많이 줄어듬! -A(11) B(3) C(7)을 삽입 : B(3)->C(7, 3초 기다림)->A(11, 10초 기다림)
라운드 로빈 스케줄링 (Round Robin 스케줄링, RR 스케줄링) - 라운드 로빈이라는 말 자체가 굉장히 많이 나오는 말!! : 돌아가면서 순차적으로 무언가 하겠다라는 의미 - 선입 선처리 스케줄링 + 타임 슬라이스(정해져있는 시간 : 딱 정해진 시간만큼만 진행) - 준비 큐에 삽입된 순서로 실행하되, 타임 슬라이스만큼 실행 - 선점형 스케줄링 - A(11) B(3) C(7)을 삽입/ 타임슬라이스를 4초 : A(4)->B(3)->C(4)->A(4)->C(3)->A(3)
최소 잔여 시간 우선 스케줄링 (SRT 스케줄링) - 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링 - 작업 시간 짧은 프로세스부터 처리하되, 타임 슬라이스만큼 돌아가며 - A(11) B(3) C(7)을 삽입/ 타임슬라이스를 4초 : B(3)->C(4)->A(4)->C(3)->A(4)->A(3)
우선순위 스케줄링 : 굉장히 범용적인 스케줄링 : 가장 많이 사용됨!!!!!! - 프로세스마다 우선순위 부여, 우선순위 높은 순으로 스케줄링 - 최단 작업 우선 스케줄링 : 작업 시간 짧은 순으로 우선순위 부여 - 최소 잔여 시간 스케줄링 : 남은 시간 짧은 순으로 우선순위 부여 - 아사(starvation) 현상(근원적인 문제) - 모든 우선순위 스케줄링 알고리즘의 근본적인 문제 - 우선순위 낮은 프로세스의 실행이 계속 연기되는 현상 ( 우선순위 높은 프로세스 실행하느라 우선순위 낮은 프로세스 실행을 못한다) - 해결책: 에이징(aging) : 대기 시간이 길어지면 점차 우선순위를 높이는 방식
다단계 큐 스케줄링 - 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 ( 우선순위가 높은 프로세스 처리 -> 다음으로 우선순위 높은 프로세스 처리 -> 다음으로 우선순위 높은 프로세스 처리) - 다단계 큐 스케줄링 종류 - 프로세스 유형 별로 큐 구분 가능 (CPU 바운드, I/O 바운드, 백그라운드, 포그라운드, 실시간 프로세스, ...) - 큐 별로 다른 스케줄링 알고리즘 적용 가능 (선입 선처리 큐, 라운드 로빈 큐, ....) - 큐 별로 다른 타임 슬라이스 적용 가능 - 기본적으로 프로세스는 큐 간의 이동 불가능 : 아사현상 발생이 가능 -> 위에 있는 우선순위의 큐에 계속 삽입이 되는 우선순위가 높은 큐만 계속 적용됨
다단계 피드백 큐 스케줄링 - 다단계 큐 스케줄링에서 아사현상을 방지하는 것 - 프로세스가 큐 간의 이동 가능 : 높은 우선순위 큐에 삽입, 실행이 끝나지 않을 경우 낮은 우선순위 큐에 삽입 - 에이징 적용 - CPU bound, I/O bound 프로세스 구분 가능 : 서로 우선순위가 오갈 수 있음
리눅스와 스케줄링
리눅스 스케줄링 정책 - 스케줄링 정책을 여러개로 나누어 둠 : 상황/프로세스 유형에 따라 각기 다르게 사용
- 실시간 정책 스케줄링 (우선순위 높음) - dead라인이 있는(끝나야할 시간) 프로세스 - SCHED_FIFO, SCHED_RR - 일반 정책 스케줄링 (우선순위 낮음) - SCHED_OTHER/SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE
CFS (Completely Fair Scheduler) -일반적인 비실시간 프로세스를 대상으로 하는 스케줄링 방식 (linux kernel 2.6.23~) < 이전에는 O(1) 스케줄링 알고리즘을 사용함 - CFS에서 사용되는 주된 걔념 - vruntime (virtual runtime) : 가상 실행시간 - 프로세스가 그 동안 실행한 시간을 정규화한 정보 -vruntime이 작은 프로세스를 다음 실행할 프로세스로 삼음 (vruntime 별 태스크를 고르는 과정에서 RB tree 사용) - sched 정보를 열어보면 se.vruntime이라고 정보를 볼 수 있음 -타임 슬라이스 -nice 값에 비례해 가중치 할당, 가중치를 바탕으로 타임 슬라이스 할당 - nice : 사용자 영역에서 설정한 프로세스 우선순위 - 사용자 영역에서의 값은 -20~19 - 커널 영역에서의 값은 0~139 (실시간 스케줄링되는 프로세스: 0~99 , CFS 프로세스(비실시간 프로세스) : 100~139) - nice 명령어를 통해서 직접 우선순위를 부여할 수 있음 - 새 프로세스를 실행할 때 해당 프로세스의 우선순위 부여 - 기본적으로 설정된 nice 값은 0 - $ nice –n [우선순위] [program] ( $ nice –n 19 uptime ) - renice 명령어 : 이미 실행 중인 프로세스의 우선순위 부여 - $ renice [우선순위] [PID] ( $ renice +5 1234 )
