ultra_dev
cpu 스케줄링 본문
cpu 스케줄링
운영체제가 프로세스들에게 공정하고 합리적으로 cpu 자원을 배분하는 것
프로세스 우선 순위
프로세스마다 우선순위가 다르기 때문에 차례대로 돌아가며 하는 건 비효율적이다.
ex) 입출력 작업이 많은 프로세스(=입출력 집중 프로세스)의 우선순위는 Cpu 작업이 많은 프로세스(=cpu 집중 프로세스)의 우선순위보다 높다.
→ 입출력 집중 프로세스는 실행 상태보다는 대기 상태에 더 많이 머무르게 될테니까 빨리 처리해버리고 cpu 집중 프로세스한테 몰빵하는게 효율적이기 때문
스케줄링 큐
: 자원을 이용하고 싶어하는 프로세스들이 서는 줄
큐라고 하지만 스케줄링에서의 큐는 반드시 선입선출 방식일 필요는 없다.
cpu쓰고 싶어하는 프로세스들은 관련 스케줄링 큐에 넣어서 줄 세우고
하드디스크 쓰고 싶어하는 프로세스들도 관련 스케줄링 큐에 넣어서 줄 세우고
특정 자원 이용하고 싶은애들 큐에 넣어서 관리하는 느낌
준비큐와 대기큐 ( 대표적인 스케줄링 큐의 종류 )
준비 큐 : CPU를 이용하기 위해 기다리는 줄
대기 큐 : 입출력장치를 이용하기 위해 기다리는 줄
→ 같은 장치를 요구한 프로세스들은 같은 큐에서 대기
ex) 프린터 대기 큐, 하드 디스크 대기 큐 등등
+
먼저 큐에 들어가서 준비상태에 들어갔다고해서 먼저 cpu 이용하는게 아니라 우선 순위 높은 애들이 먼저 이용함
준비상태 → 디스패치 → 실행상태 → 실행시간 완료돼서(타이머 인터럽트) 다시 준비상태로 가거나, 입출력장치 요청받고 대기상태로 가거나 이런 느낌!
선점형과 비선점형 스케줄링
cpu가 A프로세스를 실행 중인데, B프로세스도 실행돼야 한다면?
- 현재 cpu를 사용 중인 프로세스로부터 cpu 자원을 빼앗아 다른 프로세스에 할당
- 현재 cpu를 사용 중인 프로세스의 작업이 끝날 때까지 프로세스 기다리기
- 선점형 스케줄링
- 앞서 알아봤던 스케줄링 기법, 프로세스마다 정해진 시간만큼만 돌아가면서 실행되고 타이머 인터럽트 발생하면 다음 프로세스가 실행되는!!
- 장점 : 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원 배분 가능
- 단점 : 그만큼 문맥 교환 과정에서 오버헤드가 발생할 수 있다.
- 비선점형 스케줄링
- 어떤 프로세스가 한 자원 점거 중이라면 이 프로세스가 종료되거나 대기 상태 전까지 해당 자원 사용 불가
- 장점 : 선점형 스케줄링에 비해 문맥 교환에서 발생하는 오버헤드가 적다.
- 단점 : 모든 프로세스가 골고루 자원을 이용하기 어렵다.
CPU 스케줄링 알고리즘
: 운영체제가 스케줄링 하는 대표적 7가지 방법
- 선입 선처리 스케줄링
- 최단 작업 우선 스케줄링
- 라운드 로빈 스케줄링
- 최소 잔여시간 우선 스케줄링
- 우선순위 스케줄링
- 다단계 큐 스케줄링
- 다단계 피드백 큐 스케줄링
1. 선입 선처리 스케줄링
= FCFS (First Come First Served) 스케줄링
- 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
- 먼저 CPU를 요청한 프로세스부터 CPU 할당
- 단점 : 프로세스들이 기다리는 시간이 매우 길어질 수 있다 (= 호위 효과)
2. 최단 작업 우선 스케줄링
= SJF (Shortest Job First) 스케줄링
- 호위 효과를 방지하려면?
- CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용시간이 짧은 프로세스는 먼저 실행
- CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식
3. 라운드 로빈 스케줄링
= RR (Round Robin) 스케줄링
- 선입 선처리 스케줄링 + 타임 슬라이스(Time Slice)
- 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
- 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
- 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간만큼만 이용
- 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입 (문맥 교환)
- 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
4.최소 잔여 시간 우선 스케줄링
= SRT (Shortest Remaining Time) 스케줄링
- 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
- 최단 작업 우선 스케줄링 : 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘
- 라운드 로빈 스케줄링 : 정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 알고리즘
- 즉 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택
5.우선순위 스케줄링
- 프로세스들에 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행
- 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
- 최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링은 넓은 의미에서 우선순위 스케줄링에 포함!!
단점 :
- 우선순위 스케줄링의 근본적인 문제점, 기아(Starvation) 현상
- 우선순위 높은 프로세스만 주구장창 실행
- 우선순위 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 실행 연기
해결책 : 에이징(Aging)
- 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
- 대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법
- 우선순위가 낮아도 언젠가는 우선순위가 높아진다.
6. 다단계 큐 스케줄링
= Multilevel Queue 스케줄링
- 우선순위 스케줄링의 발전된 형태
- 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식 (우선순위 0번, 1번 이런 식으로 나눠서)
- 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
- 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리
- 이렇게 하면 프로세스 유형별로 우선순위 구분하기가 쉬워짐(어떤 큐에는 우선순위가 높아야하는 입출력장치 관련 프로세스, 어떤 큐는 타임 슬라이스 크게하고, 어떤 큐는 라운드 로빈 방식으로 어떤 큐는 선입선처리방식으로 스케줄링 가능)
- 문제점 : 기본적으로 프로세스가 큐 간에 이동이 불가능함 → 우선순위가 낮은 프로세스는 계속해서 우선순위가 낮은 큐에 머무를 수 밖에 없고 기아 현상이 발생할 수 있음
7. 다단계 피드백 큐 스케줄링( 가장 일반적인 CPU 스케줄링 기법)
= Multilevel feedBack Queue 스케줄링
- 다단계 큐 스케줄링의 발전된 형태
- 큐 간의 이동이 가능한 다단계 큐 스케줄링
- 이전의 다단계 큐 스케줄링에서는 기본적으로 큐 간의 이동 불가했음 → 다단계 피드백 큐 스케줄링으로 보완
- 따라서 우선순위 낮은 프로세스는 계속해서 실행 연기 우려, 기아 현상 발생 가능
- 다단계 피드백 큐 스케줄링에서는 큐 간의 이동이 가능하다.
- 새롭게 준비 상태가 된 프로세스가 있으면 일단 그 프로세스를 가장 우선순위 높은 큐에 삽입
- 할당 받은 타임 슬라이스만큼 실행
- 만약 타임 슬라이스만큼 진행하고도 아직 안끝났으면 다음 우선순위 큐에 삽입해서 실행
- 이걸 반복
- 결국 CPU를 많이 사용해야하는 프로세스일수록 우선순위는 자연스럽게 낮아진다.
- 여기서도 추가로 에이징 기법 적용 ( 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높여서 기아 현상 방지)
결론 : 어떤 프로세스의 CPU 시간이 길면 우선순위가 낮아지고 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는 방식, 가장 일반적인 형태의 CPU 스케줄링 방식으로 알려져 있다.