02. 프로세스 관리

02. 프로세스 스케줄링(Process Scheduling)

1) 스케줄링의 종류

장기(상위) 스케줄링 - 작업 스케줄링
- 프로세스가 자원을 사용하는 시기를 결정하여 대기 큐로 전달하는 작업
- 프로그램들이 주기억 장치에 적재될 시기를 결정하는 것과 같은 스케줄링으로 다소 느린 작업 계획
중기(중위) 스케줄링
- 프로세스가 여러 개의 CPU 중에 어떤 CPU를 할당 받을 것인가를 결정하는 작업
- 중기 스케줄러는 프로세스를 주기억 장치로부터 빼낼 수 있으므로 필요한 경우에는 다중 프로그래밍의 정도를 낮추어 시스템의 전반적인 효율을 높여 주거나, 특정 프로세스에 대한 처리를 원활하게 해 줄 수 있는 효과를 얻을 수 있음
단기(하위) 프로세스 - 프로세스 스케줄링
- 여러 개의 프로세스가 하나의 CPU를 점유하기 위한 시기를 결정하기 위한 작업으로 프로세스 스케줄링이라고 함
- 디스패치, 인터럽트를 통한 문맥 교환 등을 수행하는 것처럼 짧은 시간에 처리해야 하는 작업 계획

2) 프로세스 스케줄링의 원칙

모든 프로세스에 공정하게 배정해야 함
단위 시간당 가능한 최대의 처리가 될 수 있도록 해야 함
처리 응답 시간이 신속해야 함
같은 종류의 작업은 같은 비용으로 실행될 수 있어야 함
오버헤드를 최소화해야 함
시스템 내의 자원이 사용되지 않는 시간이 없도록 유지해야 함
응답 시간과 자원 활용 간의 적절한 균형이 유지되도록 해야 함
프로세스의 무한대기 상태를 피해야 함
- 무한대기
  - 가능성이 있는 상태를 무한히 기다리고 있는 상태고 기아 상태라고도 함
  - 교착상태는 가능성이 없는 상태를 기다리는 상태
중요 자원을 차지하고 있는 프로세스에 우선순위를 주어야 함
문제로 인해 불안하지 않은 프로세스에 서비스를 많이 제공하도록 함

3) 프로세스 스케줄링의 성능 평가 기준(바람직한 스케줄링 정책)

CPU 이용률 : CPU를 쉬지 않고 몇 퍼센트(범위 : 40% ~ 90%)를 이용하는가의 기준
처리 능력(Throughput) : 단위 시간당 처리할 수 있는 CPU의 작업량
대기 시간(Waiting Time) : 준비 상태에서 대기하는 시간
응답 시간(Response Time, 반응 시간) : 입력에 대해 처음 반응하는 시간
반환 시간(Turn Around Time) : 작업을 지시하고 그 결과가 되돌아오는 시간

4) 비선점형 방식과 선점형 방식

1. 비선점형(Non Preemption) 방식

CPU를 점유하고 있을 때는 다른 프로세스가 현재 실행 중인 프로세스를 중단시킬 수 없음
일단 CPU를 할당 받으면 다른 프로세스가 CPU를 강제적으로 빼앗을 수 없는 방식
CPU를 사용하고 있는 현재의 프로세스가 종료된 후 다른 프로세스에 CPU를 할당함
실행이 완료될 때까지 CPU를 독점하는 방식
비선점형 방식들은 모든 프로세스를 관리하는데 공정함
프로세스의 실행 예측치를 미리 통보하고, 프로세스를 수행한다면 응답 시간의 예측이 용이함
일괄 처리 시스템에 적당함

2. 선점형(Preemption) 방식

하나의 프로세스가 CPU를 점유하고 있을 때는 다른 프로세스가 현재 사용 중인 프로세스를 중단시키고 CPU를 차지할 수 있는 방식
선점형 방식들은 높은 우선순위의 프로세스들이 긴급을 필요로 할 때 유용함
빠른 응답 시간을 필요로 하는 대화식, 시분할, 실시간 처리에 적당함

3. 비선점형 방식과 선점형 방식의 종류

비선점형 방식 : FIFO, SJF, HRN, 우선순위, 기한부 스케줄링
선점형 방식 : RR(라운드 로빈), SRT, MFQ

5) FIFO(First In First Out, FCFS) - 비선점형

입력된 순으로 처리되기 때문에 공평함
알고리즘이 가장 간단하고 구현하기 쉬움
짧은 작업이나 중요한 작업을 오랫동안 기다리게 할 수 있음
평균 반환 시간이 김
- 평균 반환 시간 = 평균 실행 시간 + 평균 대기 시간

6) SJF(Short Job First) - 비선점형

작업이 끝나기까지의 실행 시간 추정치가 가장 작은 작업을 먼저 실행시키는 방식
FIFO보다 평균 대기 시간이 작지만 긴 작업의 경우 FIFO 기법보다 더 크고 예측이 어려움
실행 시간이 많은 작업일 경우에 무한 대기 상태가 발생할 수 있음
무한 대기 상태를 방지하기 위해 Aging(노화) 기법을 사용하여 해결함
- Aging(에이징, 노화) 기법
  - 무한 대기 상태를 해결하기 위해서 자원이 할당 되기를 오랜 시간 동안 기다린 프로세스에 대하여 기다린 시간에 비례하여 높은 우선순위를 부여하여 가까운 시간 안에 자원이 할당되도록 하는 기법

7) HRN(Highest Response-ratio Next) - 비선점형

FIFO와 SJF의 단점을 보완하여 개발된 방법
긴 작업과 짧은 작업 간의 지나친 불평등을 해소할 수 있음
대기 시간이 긴 프로세스일 경우 우선순위가 높아짐
HRN은 실행 시간 추정과 선점 기능 떄문에 스케줄러가 복잡해지고 남은 계산 시간을 저장해 놓아야 하는 단점을 보완함
HRN은 작업의 서비스 받을 시간과 그 작업이 서비스를 기다린 시간으로 결정되는 우선순위에 따라 CPU를 할당함
HRN은 우선순위 공식으로 계산하여 그 수치가 큰 값부터 낮은 순으로 우선순위가 부여됨
- HRN 우선순위 = (대기 시간 + 서비스 시간) / 서비스 시간

8) RR(Round-Robin) - 선점형

대표적인 선점형 방식
동일한 시간 할당량을 사용하는 시분할 처리 시스템에 효과적으로 적용됨
시간 할당량 안에 작업을 마치지 않으면 준비 대기 리스트의 가장 뒤로 배치되는 방식
가장 큰 작업의 실행 시간이 시간 할당량보다 작으면 비선점의 FIFO와 동일함
시간 할당량이 작으면 문맥 교환수와 오버헤드가 증가함
적절한 응답 시간을 보장해주는 대화식 사용자에게 효과적

9) SRT(Shortest Remaining Time) - 선점형

작업이 끝나기까지 "남아 있는" 실행 시간의 추정치가 가장 작은 프로세스를 먼저 실행하는 방식
서비스 받은 시간을 기록해야 하기 때문에 오버헤드가 증가함
평균 대기 시간과 대기 시간의 분산(편차의 제곱)도 큼
임계치(Threshold Value)를 사용함

10) MFQ(Multi level Feedback Queue, MLFQ) - 선점형

짧은 작업이나 입출력 위주의 작업에 우선순위를 부여하기 위해 개발된 방식
큐가 여러 개이며 우선순위가 있음
각 큐마다 시간 할당량이 존재하며 우선순위가 낮은 큐일수록 시간 할당량은 커짐
각각의 큐들은 종속적으로 연결되어 있음
CPU를 시간 할당량만큼 사용한 프로세스는 낮은 큐로 이동됨
맨 마지막 단계의 큐는 RR 스케줄러를 사용함

11) MLQ(Multi level Queue, MQ) - 혼합형

선점형, 비선점형 방식
우선순위가 가장 높은 큐에서는 비선점형으로 사용됨
우선순위가 낮은 큐에서는 선점형으로 사용됨
상위 큐가 우선순위가 가장 높은 큐로 신속한 처리를 필요로 하는 시스템 프로세스가 입력됨
중위는 대화형 프로세스, 하위는 일괄처리 프로세스가 입력됨
대기 리스트 간 프로세스의 이동은 되지 않음

03. 임계 구역(Critical Section, 위험지구)

임계구역의 정의
- 다중 프로그래밍 기법에서 두 개 이상의 프로세스가 운영될 때 서로 공유하게 되는 자원(CPU, 메모리, 공유 변수, 디스크, 프린터, 파일, 기타 I/O 장치, ...)을 말함
- 임계구역으로 프로세스 간의 통신을 하는 매개 변수 역할을 할 수도 있음
임계구역의 원칙
- 두 개 이상의 프로세스가 동시에 사용될 수 없음
- 배타적이어야 함
- 작업은 순서를 지키면서 신속하게 이루어져야 함
- 하나의 프로세스가 독점하게 해서는 안 됨
- 사용 중에 중단, 무한 반복되어서는 안 됨

04. 상호배제(Mutual Exclusion)

1) 상호배제

임계구역을 어느 시점에서 단지 한 개의 프로세스만이 사용할 수 있도록 하며, 다른 프로세스가 현재 사용 중인 임계구역에 대하여 접근하려고 할 때 이를 금지하는 행위

2) 상호배제 알고리즘

잠금
- 하나의 프로세스가 임계구역을 점유한 후에 다른 프로세스가 접근할 수 없도록 잠금
인터럽트 봉쇄
- 하나의 프로세스가 임계구역을 점유한 후에 모든 인터럽트를 중단시킴
- 인터럽트의 중단은 새로운 프로세스의 생성이나 프로세스의 전이가 일어나지 않기 때문에 이미 점유하고 있는 임계구역을 다른 프로세스가 접근할 수 없게 됨
  - 전이 : 프로세스 상태 변화를 말하는 것으로 인터럽트가 봉쇄되면 프로세스의 준비, 실행, 대기 상태로의 변화가 일어나지 않음
엄격한 교대
- 두 개의 프로세스가 하나의 임계구역을 사용할 때, 서로 교대로 한 번씩만 접근하도록 하는 방법
- 하나의 프로세스는 임계구역을 두 번 연속으로 접근할 수 없으며, 반드시 상대 프로세스가 임계구역을 사용하고 난 후에만 접근할 수 있는 방법

3) 바쁜 대기(Busy Wait)

잠금, 인터럽트 봉쇄, 엄격한 교대 등은 임계구역을 동시에 접근하지 못하게 할 수 있지만, 임계구역에 접근하기 위하여 대기하고 있는 다른 프로세스는 계속적으로 접근 시도를 하게 되는 바쁜 대기 현상이 나타남
프로세스의 수가 많아지고, 바쁜 대기 현상이 증가하게 되면 운영체제는 부담을 갖게 되어 컴퓨터 시스템의 전체 성능이 떨어지게 됨
바쁜 대기 현상을 제거하는 기능을 추가한 상호배제 알고리즘에는 세마포어가 있음

4) 잠자기와 꺠우기(Sleep and Wakeup)

상호배제 과정에서 바쁜 대기를 제거하기 위한 기초 알고리즘
잠자기와 깨우기는 이발사와 손님의 관계가 대표적인 예
잠자기의 Sleep(S)은 Wait(S), P(S) 등으로도 사용됨
깨우기의 Wakeup(S)은 Signal(S), V(S) 등으로도 사용됨

5) 상호배제의 4가지 요구 조건

두 개 이상의 프로세스들이 동시에 임계구역에 있으면 안 됨
어떤 프로세스도 임계구역에 진입하는 것이 무한정 연기되면 안 됨
임계구역 안에 있는 프로세스가 다른 프로세스의 임계구역 진입을 막을 수 있어야 함
프로세스들의 상대적인 속도(각 프로세스의 처리 속도, 접근 방법, 상태 등)에 대해 어떠한 가정을 하면 안 됨
- 운영체제는 이러한 상황을 고려하지 않고, 객관적으로 정해진 규칙에 따라 프로세스들을 상호배제해야 함

05. 세마포어(Semaphore)

1) 세마포어

E. J. Dijkstra가 제안한 방법으로 상호배제의 원리를 보장하는 알고리즘
임계구역에 대하여 각각의 프로세스들의 접근을 제어하고 프로세스 사이의 동기를 유지함
잠자기와 깨우기의 연산을 이용하며, 공유 자원의 수를 나타내는 변수를 세마포어 변수 S라고 함
세마포어 변수는 일반적으로 정수형 변수를 사용함
세마포어의 종류
- 이진형 세마포어
  - 세마포어 변수 S값 : 0과 1값
  - 한 개의 공유자원을 상호배제
  - 0과 1값
    - 공유 자원(임계구역)이 하나 있는 경우 프로세스가 사용(점유)하지 않으면 1, 사용하면 0으로 표시함
- 계수형 세마포어
  - 세마포어 변수 S값 : 0과 양의 정수
  - 여러 개의 공유자원을 상호배제
  - 0과 양의 정수
    - 공유 자원(임계구역)이 여러 개 있는 경우 프로세스들이 모든 공유 자원을 사용(점유)하고 있으면 0으로 표기함
    - 하나도 사용하고 있지 않으면 전체 공유 자원 개수를 표기함
    - 사용하고 남아 있는 공유 자원의 개수는 전체 공유 자원의 개수에서 사용 중인 자원의 수를 제외하면 됨
    - 음의 정수를 사용하지 않음

2) 세마포어의 특징

세마포어는 상호배제를 위한 알고리즘으로 상호배제의 원리를 보장하는 데 사용됨
여러 개의 프로세스가 동시에 그 값을 수정하거나 접근하지 못함
세마포어에 대한 연산은 처리 중에 인터럽트 되어서는 안 됨
세마포어에 대한 연산은 소프트웨어나 하드웨어로 구현 가능함
이진 세마포어는 오직 0과 1의 두 가지 값을 가지며, 계수(산술) 세마포어는 0과 양의 정수를 값으로 가질 수 있음
세마포어 알고리즘은 프로세스 사이의 동기를 유지하게 함
세마포어 알고리즘은 P 연산(Wait 연산)과 V 연산(Signal 연산)을 사용함
P 연산과 V 연산의 구현 방법에 따라 바쁜 대기를 해결할 수 있음
V 조작은 큐에 대기 중인 프로세스를 깨우는 신호로써, 흔히 Signal 동작이라 함
P 조작은 임계영역을 사용하려는 프로세스들의 진입 여부를 결정하는 조작으로, 흔히 Wait 동작이라 함

저작자표시 비영리 변경금지 (새창열림)