[정보보안기사] 운영체제 이해 및 관리(5) - 프로세스 스케줄링

CPU 스케줄링

 

말그대로 스케줄을 짜는 것과 같다.

CPU 자원을 언제 어떤 프로세스에 지정해줄 것인지 결정하는 작업을 CPU Schduling이라고 한다.

CPU가 쉬고 있을 때마다 운영체제는 준비완료 큐에 있는 프로세스 하나를 선택해 실행하게 된다.

 

그렇다면 최적의 스케줄링을 하는 기준은 무엇일까?

 

1. CPU 이용률(utilization) : CPU를 어떻게 하면 쉬지않고 일하게 할 수 있을까?

2. 처리량(throughput) : 시간 당 몇개의 프로세스를 처리해 내는가?

3. 총 처리시간(turnaround time) : 프로세스 제출 후 완료될때 까지의 시간차를 총 처리시간이라 한다.

4. 대기시간(waiting time) : 준비완료 큐에서 대기하면서 보낸 시간의 합

5. 응답시간(response time) : 대화식 시스템(interactive system)에서는 총 처리시간을 기준으로 잡기는 힘들다. 따라서 하나의 요구를 제출한 후 첫 번째 응답에 나올 때까지의 시간을 또 다른 기준으로 삼을 수가 있다.

 

프로세스 스케줄링에는 두가지 방식이 있다.

 

선점 스케줄링(Preemptive)

선점 스케줄링은 실행 중인 다른 프로세스를 중지시키고 자신이 CPU를 차지할 수 있는 기법이다.

종류 : RR(Round-Robin), SRT(Shortest-Remaining-Time), MLQ(MultiLevel Queue), MFQ(Multilevel Feedback Queue)

 

비선점 스케줄링(Nonpreemptive)

선점과는 반대되는 개념으로 이미 다른 프로세스가 CPU에 할당되어 있다면 CPU를 가져오지 못하게 막아둔 기법이다.

종류 : FIFO(First-In-First-Out), SJF(Shortest-Job-First), HRN(Highest Response-ratio Next)

 

다양한 스케줄링 알고리즘이 있다!

핡핡 어서 다 구현해 봐야겠..읍읍!!

 

그럼 프로세스 스케줄링 알고리즘들을 간단히 짚고 가겠다.

나중에 이 부분은 따로 자세히 올릴 예정이다.

 

 

RR (Round Robin)

라운드 로빈이라 하며 시분할 시스템을 위해 설계된 알고리즘이다.

선입선처리를 기반으로 프로세스 사이를 시스템이 옮겨다니는 것이 특징이다.

시분할 시스템에서 계산을 위하여 시간 할당량이란 것을 정의하며 RR의 성능은 이 시간 할당량에 매우 많은 영향을 받는다.

시분할 방식에 효과가 좋으며 할당시간이 클경우네느 FIFO와 흡사해진다.

그렇지만 만약 할당시간이 적게되면 문맥교환이 자주 발생하는 현상이 있다.

 

SRT (Shortest Remaining Time)

준비 큐에 있는 프로세스 중에서 가장 짧은 시간이 걸리는 프로세스를 우선 실행한다.

그래서 Shortest Remainig time이라는 이름이 붙혀졌다.

다른 프로세스가 실행하는 중이더라도 자신이 남은 수행시간보다 더 짧은 시간을 갖은 프로세스가 들어오면 그 프로세스에게 CPU를 넘기게 된다.

SJF와 작업처리가 같으나 이론상 SRT는 가장 작은 대기시간이 걸리는 알고리즘이다.

 

MLQ (Multi Level Queue)

이름 그대로 다단계 큐를 구성하고 있으며 준비 완료 큐가 다수 존재한다. 일반적으로 프로세스는 메모리 크기, 프로세스의 우선순의 혹은 프로세스 유형과 같은 프로세스의 특성에 따라 한 개의 큐에 영구적으로 할당된다.

각 큐는 자신의 스케줄링 알고리즘을 갖고 있어서 포그라운드와 백그라운드에 사용하는 큐를 나누는 등의 상황이 가능하다.

다단계 큐 알고리즘은 상위에서 하위까지 5개의 큐로 분할되어 있다.

(시스템 프로세스, 대화형 프로세스. 편집 프로세스, 일괄처리 프로세스, 학생 프로세스)

 

 

MFQ ( Multi Level Feedback Queue)

다단계 피드백 큐, CPU의 사용시간에 따라서 입출력 위주와 CPU위주로 구분하는데 MFQ에서는 입출력 위주와, CPU위주냐에 따라서 서로 다른 타임 슬라이스를 부여해준다.

MFQ는 프로세스가 큐 사이를 이동하는 기법으로 프로그램이 들어오면 높은 우선순위를 할당해 단계 1에서 즉시 수행하고, 점차 낮은 우선순위를 부여하여 단계 n에 이르면 작업이 완료될 때까지 라운드로빈으로 순환한다.

이렇게하면 CPU 사용시간이 짧은 입출력 중심의 프로세스와 대화형 프로세스가 높은 우선순위 큐에서 실행되고, 반대로 계산 위주의 작업은 낮은 단계의 큐에 머물면서 비록 우선순위는 낮지만 충분한 시간동안 CPU를 할당받게 된다.

ex) UNIX

CPU와 I/O장치의 효율을 높일 수 있다는 장점이 있다.

 

 

FIFO (First in First Out)

가게에서 일을 할 때면 중요한 원칙이 있다. 그것은 바로 선입선출이다.

먼저 들어온 것부터 먼저 나가야한다. 어떻게 보면 당연하지만 막상 이대로 하려고 하면 꽤나 신경을 써주어야한다.

여담은 여기까지 하고 프로세스적인 측면에서의 알고리즘을 얘기해보도록하자.

FIFO는 FCFS(First Come First Service)라고도 불리며 먼저 CPU를 요청했던 프로세스가 먼저 할당을 받게되는 간단한 규칙이다.

대화형에는 부적절하지만 구조가 간단하며 우선순위가 공평한 장점이 있고 반응속도를 예측할 수 있다.

 

SJF (Shortest Job Fit)

프로세스를 CPU 버스트 길이와 연관시킨 알고리즘이다.

CPU 사용이 가능해지면 가장 작은 버스트를 가진 프로세스에게 CPU가 할당이 되어진다.

만약 같은 값을 갖고 있다면 선착순원칙을 적용하게된다.

따라서 작은 시간값을 가진 프로세스가 상당히 유리한 알고리즘이다.

에이징 기법으로 기아상태를 해결하는 특징이 있다.

 

HRN (Highest Response ratio Next)

SJF의 단점을 보안한 알고리즘이다.

긴 시간이 걸리는 작업과 짧은 시간이 걸리는 작업의 순서의 불평등을 줄이고자 만들어진 것이다.

그래서 일단 한 작업을 시작하게 되면 그작업이 완성될때까지 CPU를 차지하고 있는다.

우선순위의 기준도 바뀐다.

우선순위 = (대기시간 + 서비스를 받을 시간) / 서비스를 받을 시간 = 시스템 응답시간

 

 

 

교착상태 (Deadlock)

한마디로 뒤져서 잠긴 상태이다.

하염없이 기다리지만 기다리는 이벤트는 일어날 수가 없는 이벤트여서 뒤저버린 프로세스가 하나 혹은 그 이상 있는 상태이다.

교착상태로 정의되기 위해서는 4가지 조건을 성립해야한다.

 

1. 상호배제(Mutual Exclusion)

         - 프로세스가 자원을 베타적으로 점유하여 다른 프로세스들이 자원을 사용할 수 없게 만드는 것. (자원의 베타적 제어권)

2. 점유와 대기(Hold & Wait)

        - 최소 한개의 자원을 점유하고 있는 프로세스가 존재해야하며, 이 프로세스는 다른 프로세스에 할당된 자원을 추가로 점유하기 위해 대기한다. (자원을 갖고 있으면서 다른 자원을 또 받기 위해 대기 중인 상태)

3. 비선점(Non-preemption)

        - 비선점 자원은 그들을 점유하는 프로세스로부터 벗어나지 못한다. 다만 프로세스 자신만이 점유한 자원을 해제할 수 있을 뿐이다.

4. 환형 대기(Circular Wait)

        - 프로세스와 자원이 원형을 이루어 대기하는 형태로 각 프로세스들이 자신에게 할당된 자원을 가지면서 상대방 프로세스의 자원을 상호 요청하여 고리처럼 맞물린 경우를 말하며 흔히말해 무한루프에 빠졌다고 볼수 있다.