대표 방식 7가지
1. 선입 선처리 스케줄링
2. 최단 작업 우선 스케줄링
3. 라운드 로빈 스케줄링
4. 최소 잔여 시간 우선 스케줄링
5. 우선순위 스케줄링
6. 다단계 큐 스케줄링
7. 다단계 피드백 큐 스케줄링
1. 선입 선처리 스케줄링
- First Come First Served
- 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링.
- 단점: 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용이 있다. (먼저 들어간 프로세스의 실행시간이 길어질 경우)
2. 최단 작업 우선 스케줄링
- SJF(Shortest Job First) 스케줄링
- 호위 효과를 방지하기 위함
- CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스 먼저 실행
- CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식
- 선점형, 비선점형 둘다 있지만 보통 비선점형으로 분류된다.
3. 라운드 로빈 스케줄링
- RR(Round Robin) : 돌아가면서 뭔가를 한다는 용어이다.
- 선입 선처리 스케줄링 + 타임 슬라이스(time slice)
- 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
- 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
- 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간 만큼만 이용
- 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입 (문맥 교환)
4. 최소 잔여 시간 우선 스케줄링
- SRT (Shortest Remaining Time) 스케줄링
- 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
- 최단 작업 우선 스케줄링 : 작업시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘
- 라운드 로빈 스케줄링: 정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 알고리즘
- 즉, 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택
5. 우선 순위 스케줄링
- 프로세스들에 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행
- 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
- 최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링 또한 우선순위 스케줄링 방식으로 볼 수있다.
- 근본적인 문제점: 기아(starvation 스타베이션) 현상
- 우선순위 높은 프로세스만 주구장창 실행 하게되면
- 우선순위 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 한도끝도없이 실행이 연기된다.
- 해결책: 에이징(aging) 기법
- 나이를 먹게하는 효과 라고 이해하자
- 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
- 대기중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법
- 우선순위가 낮아도 언젠가는 우선순위가 높아진다.
6. 다단계 큐 스케줄링
- Multilevel queue 스케줄링
- 우선순위 스케줄링의 발전된 형태
- 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
- 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
- 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리
- 장점: 프로세스 유형별로 우선순위를 구분하는것이 되게 쉬워진다. (큐별로 스케줄링을 달리적용해서 프로세스를 유형별로 처리하는것이 쉬워진다.)
- 단점: 기본적으로 프로세스가 큐간의 이동을 할 수밖에 없다. 우선순위 낮은녀석들이 계속해서 밀리는 현상이 발생할 수 있다. 즉, 기아현상이 발생할 수 있다.
7. 다단계 피드백 큐 스케줄링
- Multilevel feedback queue 스케줄링
- 다단계 큐 스케줄링의 단점을 해결한 형태
- 큐 간의 이동이 가능한 다단계 큐 스케줄링
- 새롭게 준비상태가 된 프로세스가 있으면 일단 가장 우선순위가 높은 큐에다가 삽입한다.
- 그런 뒤 일정시간(타임슬라이스)만큼 할당을 받아 CPU를 사용을 하게 한다.
- 이때 실행이 끝났다면 나이스, CPU가 안끝났다면 그 다음 우선순위 큐에 삽입을 해놓는다.
- 거기서 실행이 끝났다면 나이스, 여기서도 실행이 끝나지 않았다면 그 다음 우선순위 큐에 삽입을 한다.
즉, CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고 입출력 집중 프로세스의 우선순위는 상대적으로 높아진다.
"너, 타임 슬라이스 동안 실행을 다 못 끝내겠으면 일단 낮은 우선순위로 이동해!"
- 다단계 피드백 큐에서도 에이징 기법 적용 할 수 있다.
- 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높여준다.
구현이 조금 복잡할 수는 있지만, CPU 스케줄링 방식의 가장 일반적인 형태로 알려져있다.
'프로그래밍 > 컴퓨터구조 및 운영체제' 카테고리의 다른 글
| 프로세스 교착상태 (1) | 2023.11.21 |
|---|---|
| 프로세스 동기화 (2) | 2023.11.19 |
| CPU 스케쥴링 개념 (0) | 2023.11.16 |
| 스레드 알아보기 (1) | 2023.11.15 |
| 프로세스 상태, 계층 구조, 생성 기법 (0) | 2023.11.14 |