Study/혼자 공부하는 컴퓨터구조+운영체제 정리

11. CPU스케쥴링

공부하기 좋은 날 2023. 2. 5. 23:36

11-1) CPU스케쥴링 개요

CPU 스케쥴링 : 운영체제가 프로세스들에게 공정하고 합리적으로 CPU자원을 배분하는 것

1) 프로세스 우선순위

프로세스 우선순위에 따라 각각의 상황에 맞게 CPU를 배분한다.
프로세스마다 PCB에 우선순위를 부여하여 CPU가 먼저 처리할 프로세스를 결정함.

2) 스케쥴링 큐

운영체제는 메모리로 적재되고 싶은 프로세스들을 줄세우고, 이 줄을 스케쥴링 큐라고 한다.
운영체제가 관리하는 줄, 즉 큐에는 준비 큐(CPU를 이용하고 싶은 프로세스들이 서는 줄), 대기 큐(입출력장치를 이용하기 위해 대기상태에 접어든 프로세스들이 서는 줄)가 있음.

운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내 실행하되, 그 중 우선순위가 높은것을 먼저 실행한다.

3) 선점형과 비선점형 스케쥴링


선점형 스케쥴링
: 프로세스가 CPU와 같은 자원을 사용중이더라도 운영체제가 그 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케쥴링 방식
장점: 한 프로세스의 자원 독점을 막고 골고루 자원 배분
단점: 문맥교환을 많이 하여 오버헤드 발생 가능

비선점형 스케쥴링
: 하나의 프로세스가 자원을 사용중이라면 스스로 대기상태가 되기 전까지 다른 프로세스가 끼어들 수 없는 방식
장점: 문맥교환의 횟수가 적어 오버헤드가 적음
단점: 자원을 골고루 사용 못함


대부분의 운영체제는 선점형 스케쥴링 방식을 사용



<확인문제>
1. 4번 -> 선점형 스케쥴링은 프로세스가 이용중인 자원을 빼앗아 다른 프로세스에 자원을 골고루 할당할 수 있는 방식
2. 1) 준비 큐 2) 대기 큐
3. 2번 -> 선점형 스케쥴링은 문맥교환에서 발생하는 오버헤드가 비선점형에 비해 많다.

11-2) CPU스케쥴링 알고리즘

준비 큐에 A, B, C, D 순으로 삽입될 때 어떤 프로세스로 CPU를 할당받을까?

1) 선입 선처리 스케쥴링

: First Come First Served Scheduling
먼저 들어온 프로세스를 먼저 처리하는 비 선점형 스케쥴링 방식

A, B, C, D 순서대로 CPU를 할당받지만, 때때로 프로세스들이 기다리는 시간이 매우 길어지면 그 다음 프로세스들은 무작정 기다려야 함. 그 다음 프로세스들이 빠르게 작업이 끝나는 것이더라도 앞의 프로세스들을 기다리느라 긴 시간을 허비하는 것을 호위효과라고 함.


2) 최단 작업 우선 스케쥴링

: Shortest Job First Scheduling
앞선 선입 선처리와 달리 작업시간이 빠른 것부터 먼저 실행하여 호위효과를 줄여주는 알고리즘
A, B, C, D중 작업시간이 짧은 것 부터 먼저 실행 됨

3) 라운드 로빈 스케쥴링

: 앞선 선입 선처리 스케쥴링에 타임 슬라이스라는 개념이 더해짐.
A, B, C, D순서대로 실행되지만 정해진 타임 슬라이스 시간만큼 실행된 후 다음 프로세스로 넘어감.
타임 슬라이스 크기를 잘 설정하여 많은 문맥교환이 생기지 않게 하거나 호위효과가 생기지 않도록 주의해야 함.

4) 최소 잔여시간 우선 스케쥴링 = 선점형 최단 작업 우선 스케쥴링

: Shortest Remain Time Scheduling
최단작업 우선 스케쥴링과 라운드 로빈 스케쥴링을 합친 스케쥴링 방식
타임슬라이스 시간 동안 실행되고 다음 프로세스가 실행될 때 남아있는 잔여시간이 가장 짧은 다음 프로세스로 넘어감.

5) 우선순위 스케쥴링

프로세스들에 우선순위를 부여하여 가장 높은 우선순위를 가진 프로세스부터 실행하는 알고리즘
A, B, C, D중 우선순위가 높은 것 부터 실행됨.
우선순위가 낮은 프로세스는 우선순위가 높은 프로세스들에 의해 실행이 계속 연기될 수 있음. 이를 기아(starvation)현상이라고 한다.
이를 방지하기 위해 에이징(Aging)기법을 사용하여 오래 대기한 프로세스의 우선순위를 나이 먹듯이 높여 기아현상을 방지한다.


6) 다단계 큐 스케쥴링

우선순위 스케쥴링이 발전된 형태
우선순위별로 준비 큐를 여러개 사용한다.
우선순위가 높은 큐부터 프로세스를 처리함.
큐별로 각자 다른 타임 슬라이스, 다양한 알고리즘을 사용할 수 있음


7) 다단계 피드백 큐 스케쥴링

다단계 스케쥴링이 발전된 형태
프로세스들이 큐 사이를 이동할 수 있다. 낮은 우선순위의 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 사용하여 기아현상을 예방한다.

<확인 문제>
1) 3번 - 선입선처리는 큐에 삽입된 순서대로 처리됨
2) 우선순위가 낮아 실행이 계속 연기되는 문제 : 기아현상
이를 해결하기 위해 우선순위를 높이는 기법: 에이징