[혼공컴운] Ch11. CPU 스케줄링

 

 

 

 

강민철 - 혼자 공부하는 컴퓨터구조 운영체제
 

 

책을 읽으며 개인적으로 정리한 내용입니다.

 

 

 

---

 

목차

• CPU 스케줄링 개요
  • 프로세스 우선순위
  • 스케줄링 큐
  • 선점형과 비선점형 스케줄링
• CPU 스케줄링 알고리즘
  • 알고리즘의 종류

 

 

---

 

 

✅ CPU 스케줄링 개요

 

모든 프로세스는 먼저 CPU를 사용하고 싶어한다. 

프로세스들에게 공정하고 합리적으로 CPU자원을 할당하기 위해 

운영체제(OS)가 CPU를 배분하는데 이것이 CPU스케줄링이다.

 

⏺ 프로세스 우선순위

프로세스에는 우선순위가 존재한다.

OS는 우선순위가 높은 프로세스를 먼저 처리해준다.



우선순위가 높은 프로세스 

• 입출력 작업이 많은 프로세스

 

 

 

 

입출력 작업이 많은 프로세스는 먼저 실행하면 더 효율적이다. 

🤔 왜?

대부분의 프로세스는 CPU와 입출력장치를 모두 사용하는데, 이때 실행상태와 대기상태를 반복하고 있다.

 

글자를 쓰는 프로세스의 경우
1) 입력 내용을 보조기억장치에 저장하고, 
2) CPU를 이용해 명령어를 실행하고
3) 해당 내용을 출력하는 과정이 반복될 것

 

프로세스는 2가지 종류가 있다. 

 

 

✔️ CPU 집중 프로세스 & 입출력 집중 프로세스

 

CPU집중 프로세스 

• CPU 작업이 많은 것들 (복잡한 연산, 컴파일, 그래픽 처리 등)

입출력 집중 프로세스

• 입출력 작업이 많은 것들 (비디오 재생, 디스크 백업 등)

 

입출력 집중 프로세스는 CPU를 상대적으로 덜 사용하기 떄문에

가능한 한 빨리 실행시켜 입출력 장치를 끊임없이 작동시키고,

다음에 CPU 집중 프로세스에 집중적으로 CPU를 할당하는것이 좀더 효율적이다. 

> 어차피 입출력 완료 전까진 대기 상태가 되기 때문에 먼저 처리해버리면 이후에 다른 프로세스가 CPU를 사용할 수 있게 된다.

 

 

 

✔️ 운영체제는 프로세스에 우선순위를 부여한다.
✔️ 각 프로세스의 PCB에 명시 후 우선순위를 바탕으로 먼저 처리할 프로세스를 결정한다.
✔️ 우선순위가 높다고 무조건 먼저 실행되는 것은 아니다. 단, 더 빨리 더 자주 실행될 가능성이 높다. 

 

 

⏺ 스케줄링 큐

 

운영체제가 실행할 다음 프로세스를 찾기위해 PCB를 보는것은 비효율적이다. 

 

이러한 이유로 운영체제는 스케줄링큐를 이용하여

프로세스들의 대기줄을 구현하고 관리한다.

* 반드시 FIFO(선입선출) 방식일 필요는 없다. 

 

 

 

✔️ 큐의 종류

 

준비 큐

• CPU를 이용하고 싶은 프로세스들의 열

 

대기 큐

• 입출력장치를 이용하기 위해 대기상태에 접어든 프로세스들의 열

 

 

1. 준비 상태에 있는 프로세스들은 준비큐에 삽입되어 CPU 사용을 기다린다.
2. OS는 큐에 삽입된 순서대로 꺼내 실행하되, 이 중 우선 순위가 높은 프로세스를 먼저 실행한다 
   1. 우선순위가 낮은 프로세스가 먼저 큐에 삽입되었다고 하더라도, 우선순위가 높은 프로세스가 먼저 처리될 수 있음
3. 같은 장치를 요구한 프로세스들은 같은 대기큐에서 기다린다. 
4. HDD, 프린트 대기큐가 각각 존재한다.
   프로세스의 입출력이 완료되어 <완료 인터럽트> 발생시 
   대기큐에서 완료된 PCB를 찾고,
   준비상태로 변경시킨 후 대기큐에서 제거한다. 
   
   

 

⏺ 선점형과 비선점형 스케줄링

 

어떤 프로세스에  CPU를 허락했으나,

다른 프로세스가 급하게 당장 사용을 요청하면?

 

 

OS는 두가지 선택을 할 수 있다. 

 

1) CPU를 사용중인 프로세스로부터 빼앗아 바로 할당해준다.  == 선점형

2) 현재 프로세스 작업이 끝날때까지, 급한 프로세스를 기다리게 한다. == 비선점형

 

 

✔️ 선점형 스케줄링

프로세스로부터 자원을 강제로 빼앗아, 다른 프로세스에 할당할 수 있는 스케줄링 방식

-> 자원독점을 막을 수 있다. 단 문맥교환과정의 오버헤드가 발생할 수 있다. 

 

✔️ 비선점형 스케줄링

프로세스가 종료되거나, 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식

-> 자원 사용의 독점이 가능하다(골고루 자원을 사용할 수 없음). 오버헤드가 적다. 

 

 

* 대부분의 운영체제는 선점형을 차용하고 있다. 

 

---

 

✅ CPU 스케줄링 알고리즘

 

운영체제는 저마다 다른 스케줄링 알고리즘을 사용한다. 

여러가지 스케줄링 알고리즘의 작동방식과 장단점을 알아보자

 

⏺ 알고리즘의 종류

 

1. 선입 선출 스케줄링 (FCFS)

• First Come First Served Scheduling 
• 준비 큐에 삽입 된 순서대로 프로세스들을 처리 함
• 비선점형
• CPU를 오래 사용하는 프로세스가 먼저 들어올 경우, 다른 프로세스들은 무작정 기다려야한다. 
• 호위 효과 : A (17ms ) - B (7ms) - C(1ms) 순서대로 삽입되었다고 가정했을 때
  C는 1ms 를 실행하기 위해 17 + 7 = 24ms의 시간을 기다려야한다.

2. 최단 작업 우선 스케줄링 (SJF)

• Shortest Job First Scheduling
• 호위효과를 방지하기 위한 스케줄링 방식
• 사용시간이 짧은 프로세스부터 실행하고,  긴 프로세스를 나중에 실행 함
• 비선점형 (기본) /  선점형으로 구현될 수 있음

 

3. 라운드 로빈 스케줄링 (Round Robin)

• 선입 선출 스케줄링 + 타임 슬라이스
• 타임슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미 함
  • 정해진 타임 슬라이스만큼의 시간동안 돌아가며 CPU를 이용함.
• 선점형
• 큐에 삽입된 순서대로 CPU를 이용하되, 정해진 시간만큼만 이용하고,
  정해진 시간을 모두 사용했음에도 완료되지 않은 경우 다시 큐의 맨뒤에 삽입된다.(문맥교환)
• 타임 슬라이스의 크기는 아주 중요하다
  - 너무 크면 선입선출과 다르지 않다.
  - 너무 작으면 문맥교환 비용이 커진다. 

4. 최소 잔여시간 우선 스케줄링 (SRT)

• Shortest Remainig Time
• 최단 작업 우선 스케줄링 + 라운드 로빈
• 작업 시간이 짧은 프로세스부터 처리하되, 타임슬라이스만큼 돌아가며 CPU를 사용
• 선점형
• 다음 프로세스는 남아있는 작업시간이 가장 적은 프로세스가 선택된다.

 

5. 우선순위 스케줄링 (Priority)

• 프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행
• 기아 현상 발생 가능성 : 우선순위가 낮은 프로세스는 계속해서 연기될 수 있음
• 에이징 기법 : 오랫동안 대기한 프로세스의 우선순위를 점차 높여서 기아현상 방지
• (언젠가는 높은 우선순위가 되기 때문에)

 

6. 다단계 큐 스케줄링 (MultiLevel Queue)

• 우선순위 스케줄링에서 발전된 형태
• 우선순위별로 준비큐를 여러개 사용 (준비 큐 자체에 우선순위가 있음)
• 우선순위가 가장 높은 큐에 있는 프로세스들은 먼저 처리하고,
  가장 높은 큐가 비어있으면 다음 우선순위큐에 있는 프로세스를 처리하는 방식
• 큐 별로 타임 슬라이스 여러개 지정도 가능하고, 큐마다 다른 스케줄링 알고리즘을 사용해도 된다. 

 

 

7. 다단계 피드백 큐 스케줄링 (MultiLevel Queue)

• 다단계 큐 스케줄링에서 발전된 형태
• 다단계 큐 스케줄링은 프로세스들이 큐 사이를 이동 할 수 없음 (우선순위가 낮은 큐에서 기아 현상이 발생할 수 있다.)
• 프로세스들이 큐 사이를 이동할 수 있다는 것이 차이점 
• 새롭게 준비 상태가 된 프로세스가 있다면, 우선 우선순위가 가장 높은 큐에 삽입되고, 일정 시간동안 실행된다.
  이때 프로세스의 실행이 끝나지 않으면 다음 우선순위 큐에 삽입된다. (점차 우선순위가 낮아진다)
  CPU를 오래 사용해야하는 프로세스들은 자연스럽게 우선순위가 낮아지게 된다.
• 만약 우선순위가 낮은 큐에 너무 오래 대기하고 있다면, 점차 높은 큐로 이동시키는 에이징기법을 적용해 기아현상을 예방할 수 있다. 

 

구현은 복잡해도 가장 일반적인 CPU스케줄링 알고리즘

 

 

 

references

혼자 공부하는 컴퓨터구조 운영체제 (강민철)