OS, 스케쥴링 알고리즘

OS, 스케쥴링 알고리즘

 

 

1. OS (운영체제) 가 하는 일 :

CPU, 그리고 메모리를 관리하는 프로그램 !

파일관리, 메모리 관리, 작업관리 를 한다.

​

자세히 말하자면 CPU에게 무슨 작업을 해야하는지 알려주는 작업관리, 메모리의 자원관리.

주기억 장치(메인메모리)는 빠르게 처리할 수 있어야 하고, 보조기억 장치는 많은 데이터를 저장 가능하게 해야한다.

​

 

​

2-1. OS의 종류 (by 사용자)

​Single-user, Multi-user 그리고 Real time, embedded 가 있다.

 

Single-user는 말 그대로 윈도우 95와 같은 개인 사용자 OS,

Multi-user는 다중 사용자. (윈도우 XP)

이 경우 아이디, 패스워드, 권한 부여와 같은 사용자 관리가 필요하다.

쉽게 말해서 동시에 여러 사람이 사용할 수 있는 것인지 아닌지의 차이가 있다!

real time OS는 매우 빠른 입력, 처리 속도를 필요로 한다. 그렇기 때문에 특수목적의 전용 프로그램을 항상 메모리에 적재하여 반복 수행을 한다. 사용하는 곳은 발전소, 은행 입출금 시스템, atm기계, 그리고 미사일 제어와 같은 무기체계 시스템 등 '시간'이 중요한 곳에서 사용하고 있다.

embedded는 데이터 크기가 크지않은 곳, TV세터박스 정도를 예시로 들 수 있겠다.

​

​

2-2. OS의 종류 (by 작업 방식)

​Uni Programming, Multi Programming 두 가지.

싱글은 한번에 하나의 작업만 처리하고

멀티는 동시에 두 가지 이상의 작업을 처리하는 OS방식인데,

우리가 일반적으로 사용하는 컴퓨터들은 거의 다 멀티프로그래밍 시스템이다.

이 이야기는 밑에서 계속 나오기 때문에 잘 알아두어야 한다.

​

 

​

3. Process Status Diagram : 작업상태

# 준비상태와 대기상태

 

우선 유니 프로그래밍에서 프로세스가 실행되면, 데이터는 준비 상태에 있다가 ->

선택되면 -> 실행 상태로 들어가 작업을 실행하고 -> 종료된다.

여기에 멀티 프로그래밍은 두가지 이상의 작업을 처리해야 해서,

'대기' 상태가 추가된다.

준비상태는 말그대로 메모리 할당 받기를 준비하고 있는, 아직 메모리 할당을 받지 못한 상태이고,

대기상태는 메모리를 할당 받았는데, 실행을 대기하고 있는 상태! 라는 큰~~ 차이가 있다.

 

 

 

다시한번 #멀티 프로그래밍

우리가 일반적으로 노트북에서 노래도 듣고, 과제도 하고, 카톡도 하는 이 모든것은 사실

정말 동시에 이뤄지는 것이 아니라, 프로세스들이 해야할 일 들을 조금씩 나눠서 A작업 잠깐, B작업 잠깐,, 이런식으로 잠깐잠깐씩 반복처리 하는 것인데 컴퓨터가 너무 빨리 처리하기 때문에 동시에 이뤄지는 것처럼 보이는 것이다.

그래서 여러가지 일들을 어떤 순서로 실행시킬까? 하는 방법론이 바로-

​

 

4. 스케쥴링 알고리즘

CPU Scheduling Algorithm

식당에서 줄을 서서 들어가고, 밥을 먹는 사람들로 예시를 들어보겠다.

준비- 실행의 과정에서, 준비상태에 있는 프로세스들을 어떤 순서대로 실행시킬까 하는 방법론들이다.

​

- FIFO, FCFS : 선입선출

First in, First out 이라는 의미로 준비상태에 가장 먼저 들어온 것이 먼저 나가는 알고리즘.

음식점 앞에 줄을 선 순서대로 들어가는 것. 그래서 처리시간이 긴 프로세스, 즉 음식을 많이 오래먹는 사람이 먼저 들어왔을 경우 오랫동안 CPU를 점유해버려서 다음 프로세스의 대기시간이 늘어나는 문제가 있다.

가장 빠르다.

​

- SJF : Shortest Job First

작업 시간이 가장 짧은 프로세스부터 실행한다.

음식점 앞에 줄을 선 사람들 중 가장 빨리 먹을 수 있는 사람부터 들어가게 하는 것. 공평성이 위배 된다. 때문에 작업이 긴 프로세스(많이 먹는 사람)가 뒤로 밀려버리는 아사현상 이 발생한다.

(* 에이징 기법으로 해결이 가능하다)

​

- HRN : Highest Response Ratio Next

대기 시간과 작업시간을 통해 우선순위를 정해 CPU에 할당해 준다.는 점에서는 앞의 SJF와 같다. 그러나

대기시간이 긴, 많이 오래 먹는 사람이 음식점에 먼저 들어가게될 확률을 높여 위의 SJF 아사현상을 완화 한다. 대기열 관리가 쉬움.

​

* 우선순위 = (대기시간 + CPU 사용시간) / CPU 사용시간

​

(그러나 이 또한 공평성에 위배 된다는 문제점이 있다.)

​

- Round Robin (RR)

엄마새가 새 둥지의 아기 새들에게 밥을 줄 때 조금씩 돌아가면서 주는 것을 의미한다.

일단 음식점 앞에 먼저 줄을 선 순서대로 실행이 되는데, 하나가 끝날때 까지 실행하는 것이 아니라 일정시간동안 CPU를 할당하고 작업이 완료되지 않으면 마지막 순서로 돌리는 것이다.

가장 먼저 말한 FIFO 의 문제점을 보완할 수 있지만, 그 일정시간(타임 슬라이스)이 너무 길면 FIFO와 똑같아져서 그 효율이 떨어지고, 반대로 타임 슬라이스가 너무 짧으면 왔다갔다(:작업교환)하는 시간낭비 가 발생해 전반적인 성능이 떨어져버린다.

 

- SRT : Shortest Remaining Time

위의 RR과 앞서말한 SJF를 합친 것.

정해진 시간만큼 CPU를 할당하고 작업이 완료되지 않으면 준비상태에 다시 넣어서 작업 시간이 가장 짧은 프로세스를 새로 선택해서 할당한다.

문제점은 작업시간, 종료시간의 정확한 예측이 힘들고, SJF와 동일하게 아사현상이 있다.

​

이 스케쥴링을 선점형 그리고 비선점형 이라는 것으로 나눌 수 있는데,

선점형	비선점형 (높은 우선순위 프로세스가 등장해도 실행 순서의 조정이 없음)
- 프로세스 우선순위가 높으면 권한을 뺏어 조정이 가능하다. - 응답시간 예측이 어렵다. - 문맥교환이 많아서 오버헤드가 많다.	- 일단 프로세스가 CPU에 할당되면 권한을 뺏을 수 없다. - 응답시간 예측이 가능하다. - 문맥교환이 적어 오버헤드가 적음.
RR, SRT	FIFO, SJF, HRN

 

선점형 OS인 경우,

스케쥴러에 의해 '우선순위가 높은 프로세스가 우선순위가 낮은 프로세스를 밀어내고 실행' 된다. 식당앞 줄이 길면 주인이 이제 슬슬 나가달라고 부탁하고, 부탁을 들어줄 수 있는 것. 테이블 순환이 좋다!

비선점형 OS는 명시적으로 우선순위가 낮은 프로세스를 밀어내지 않는 한, 먼저 실행된 프로세스의 작업이 끝나야 다음 프로세스를 실행할 수 있는 것! (비선점형은 구식~)

오래 먹는 사람이 식당에 먼저 들어가서 계속 먹다가 주인이 뭐라고 하면 오히려 버럭 하는 것과 비슷한 상황.

선점형 방식이 항상 좋은 것은 아니지만, CPU가 노는 시간이 현저히 줄어들었다는 점에서 효율성이 높다.

선점형 OS에서 스케쥴러가 프로세스의 실행에 대해 더 많이 관여한다고 할 수 있다!