CHAPTER 01 - 운영체제의 특징(3)

2024년도 수제비 실기책(6판) 내용 

---

2) 프로세스(Process) 관리

(1) 개념

 

• CPU에 의해 처리되는 프로그램이며 실행 중인 프로그램을 의미하고 작업(Job) 또는 태스크(Task)라고도 함

(2) 상태(생준실대완)

 

• 하나의 프로세스는 여러 가지 이벤트에 의해 일련의 서로 구분되는 상태 변화를 겪음 

프로세스 상태	설명
생성(Create) 상태	사용자에 의해 프로세스가 생성된 상태
준비(Ready) 상태	CPU를 할당받을 수 있는 상태, 준비 리스트(Ready List) 대기
실행(Running) 상태	프로세스가 CPU를 할당받아 동작 중인 상태
대기(Waiting) 상태	프로세스 실행 중 입출력 처리 등으로 인해 CPU를 양도하고 입출력 처리가 완료까지 대기 리스트에서 기다리는 상태 대기 리스트(Waiting List)대기
완료(Complete) 상태	프로세스가 CPU를 할당받아 주어진 시간 내에 완전히 수행을 종료한 상태 종료(Terminated, Exit) 상태라고도 함

 

** 준비 리스트와 대기 리스트의 차이

 - 준비 리스트는 각각 우선순위를 부여하여 가장 높은 우선순위를 갖는 프로세스가 다음 순서에 CPU를 할당 받음

 - 대기 리스트는 우선순위가 존재하지 않고 입출력 등 처리가 끝나면 준비 상태로 바뀌면서 준비 리스트로 이동함

 

[1] 프로세스 상태 전이(디타블웨)

 

• 하나의 작업이 컴퓨터 시스템에 입력되어 완료되기 까지 프로세스의 상태가 준비, 실행 및 대기 상태로 변하는 활동을 말

프로세스 상태 전이	설명
디스패치 (Dispatch)	- 준비 상태에 있는 여러 프로세스 중 실행될 프로세스를 선정하여 CPU를 할당 -> 문맥교환 발생 - 프로세스는 준비 상태에서 실행 상태로 전이 ** 문맥교환(context switching) - CPU가 현재 실행하고 있는 프로세스의 문 상태를 프로세스 제어블록(PCB)에 저장하고 다음 프로세스의 PCB로 부터 문맥을 복원하는 작업
타이머 런 아웃 (Timer Run Out) = 할당 시간 초과	- CPU를 할당받은 프로세스는 지정된 시간이 초과되면 스케줄러에 의해 PCB를 저장, CPU 반납 후 다시 준비 상태로 전이됨 - 프로세스는 실행 상태에서 준비 상태로 전이 - 타임 슬라이스(Time Slice) 만료, 선점(Preemption)시 타임아웃 발생
블록 (Block) = 입출력 발생	- 실행 상태에 있는 프로세스가 지정된 할당시간을 초과하기 전에 입출력이나 기타 사건이 발생(block)하면 CPU를 스스로 반납하고 입출력이 완료될 때까지 대기 상태로 전이됨 - 프로세스는 실행 상태에서대기 상태로 전이 - 즉시 실행 불가능한 시스템 콜, I/O 작업 시작, 프로세스간 통신 시 Block 발생
웨이크 업 (Wake Up) = 깨움	- 어느 순간에 입출력이 종료되면 대기 상태의 프로세스에게 입출력 종료 사실을 알려주고 준비 상태로 전이됨 - 프로세스는 대기 상태에서 준비 상태로 전이

** PCB : 운영체제가 프로세스를 제어하기 위해 정보를 저장해 놓은 곳(프로세스의 상태 정보를 저장하는 구조체)

 

(3) 프로세스 스케줄링

 

• CPU를 사용하려고 하는 프로세스들 사이의 우선순위를 관리하는 작업
• 처리율과 CPU 이용률을 증가시키고 오버헤드, 응답시간, 반환시간, 대기시간을 최소화시키기 위한 기법
• 특정 프로세스가 적합하게 실행되도록 프로세스 스케줄링에 의해 프로세스 사이에서 CPU교체가 일어남

[1] 주요 용어

용어	설명
서비스 시간( = 수행시간) (Burst Time)	프로세스가 결과를 산출하기까지 소요되는 시간
응답시간 (Response Time)	프로세스들이 입력되어 서비스를 요청하고, 반응하기 시작할 때까지 소요되는 시간
반환시간 (Turnaround Time)	프로세스들이 입력되어 서비스를 수행하고 결과를 산출하기까지 소요되는 시간 반환시간 = 대기시간 + 수행시간
대기시간 (Waiting Time)	- 프로세스가 프로세서에 할당되기까지 큐에 대기하는시간 - 프로세스가 도착 즉시 프로세서에 할당되면 대기시간은 0이 됨
평균 대기시간 (Average Waiting Time)	- 프로세스가 준비 큐에서 대기하는 평균 시간 - 대기시간인 0인 프로세스도 평균 대기시간에 합산하여 결과 도출
종료 시간(End Time)	프로세스가 요구하는 서비스 시간을 모두 수행하고 종료된 시간
시간 할당량 (Time Quantum 또는 Time Slice)	한 프로세스가 프로세서를 독점하는 것을 방지하기 위해 서비스되는 시간 할당량
응답률 (Response Ratio)	(대기시간 + 서비스 시간) / (서비스 시간) - HRN(Highset Response ratio Next) 스케줄링에서 사용 - HRN 스케줄에서 응답률이 높으면 우선순위가 높다고 판단

 

[2] 유형

구분	선점형 스케줄링 (Preemptive Scheduling)	비선점형 스케줄링 (Non Preemptive Scheduling)
개념	하나의 프로세스가 CPU를 차지하고 있을 때 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식	한 프로세스가 CPU를 할당 받으면 작업 종료 후 CPU 반환시 까지 다른 프로세스는 CPU 점유가 불가능한 스케줄링 방식
개념도	1. 낮은 우선순위 프로세스 CPU 할당 2. 높은 우선순위 프로세스 CPU 할당 -> CPU 선점	1. 낮은 우선순위 프로세스 CPU 할당 2. 높은 우선순위 프로세스 CPU 할당 시도 ->  점유 불가
장점	- 비교적 빠른 응답 - 대화식 시분할 시스템에 적합	- 응답시간 예상이 용이 - 모든 프로세스에 대한 요구를 공정하게 처리
단점	높은 우선순위 프로세스들이 들어오는 경우 오버헤드 초래	짧은 작업을 수행하는 프로세스가 긴 작업 종료 시까지 대기
알고리즘	- SRT(Shortest Remaining Time First) - 다단계 큐(Multi-Level Queue) - 다단계 피드백 큐(Multi-Level Feedback Queue) - 라운드 로빈(Round Robin)	- 우선순위(Priority) - 기한부(Deadline) - HRN (High Response Ratio Next) - FCFS - SJF(Shortest Job First)
활용	실시간 응답 환경, Deadline 응답환경	처리시간 편차가 적은 특정 프로세스 환경

 

[3-1] 프로세스 스케줄링 알고리즘 - 선점형 스케줄링 알고리즘(SMMR)

유형	설명
SRT (Shortest Remaining Time First)	- 가장 짧은 시간이 소요되는 프로세스를 먼저 수행, 남은 처리시간이 더 짧다고 판단되는 프로세스가 준비 큐에 생기면 언제라도 프로세스가 선점되는 스케줄링 기법 - 비선점 방식의 스케줄링 기법에 선점 방식을 도입한 기법
다단계 큐 (MLQ; Multi Level Queue)	- 작업을 여러 종류 그룹으로 분할하고, 여러 개의 큐를 이용하여 상위단계 작업에 의한 하위단계 작업이 선점 당하는 스케줄링 기법 - 각 큐는 자신만의 독자적인 스케줄링을 가짐
다단계 피드백 큐 (MLFQ; Mulit Level Feedback Queue)	-새로운 프로세스는 높은 우선순위가 부여되고 프로세스의 실행시간이 길어질수록 점점 낮은 우선순위 큐로 이동하고 마지막 단계는 라운드 로빈 방식이 적용되는 스케줄링 기법 - 입출력 위주와 CPU 위주인 프로세스의 특성에 따라 큐마다 서로 다른 CPU 시간 할당량 부여 - FCFS(FIFO)와 라운드 로빈 스케줄링 기법을 혼합한 방식
라운드 로빈 (RR; round Robin)	모든 프로세스에 대해 같은 크기의 CPU 시간을 할당하고 프로세스가 할당된 시간 내에 처리 완료를 못하면 준비 큐 리스트의 가장 뒤로 보내지고, CPU는 대기 중인 다음 프로세스로 넘어가는 스케줄링 기법

** 시간 할당량(time Quantum) : 프로세스가 선점방식의 다중 작업 시스템에서 작업을 실행할 수 있는 시간대를 말함

 

[3-2] 프로세스 스케줄링 알고리즘 - 비선점형 스케줄링 알고리즘(우기HFS)

유형	설명
우선순위 (Priority)	- 프로세스 별로 우선순위가 주어지고, 우선순위에 따라 CPU를 할당하는 스케줄링 기법 - 동일 순서는 FCFS 방식 적용 - 주요/긴급 프로세스에 대한 우선 처리 및 설정, 자원 상황 등에 따른 우선순위 선정이 가능한 기법
기한부 (Deadline)	- 작업들이 명시된 시간이나 기한 내에 완료되도록 계획하는 스케줄링 기법 - 요청에 명시된 시간 내 처리를 보장하는 기법
HRN(Highest Response Ratio Next)	- 대기 중인 프로세스 중 현재 응답률(Response Ratio)이 가장 높은 것을 선택하는 스케줄링 기법 - SJF의 약점인 기아현상을 보완한 기법으로 긴 작업과 짧은 작업 간의 불평등 완화 (HRN 우선순위) = ((대기시간) + 서비스시간)) / (서비스시간)
FCFS (First Come Fisrt Service)	- 프로세스가 준비 큐에 도착한 순서에 따라 CPU를 할당하는 스케줄링 기법 - FIFO 알고리즘이라고도 함
SJF(Shortest Job First)	프로세스가 도착하는 시점에 따라 그 당시 가장 작은 서비스 시간을 갖는 프로세스가 종료 시까지 자원을 점유하는 스케줄링 기법

** HRN의 우선순위(대서서)

** 기아(Starvation) 현상: 시스템 부하가 많아서 준비 큐에 있는 낮은 등급의 프로세스가 무한정 기다리는 현상, 기아 현상을 해결하기 위해서 오랫동안 기다린 프로세스에게 우선순위를 높여주도록 처리하는 기법인 에이징(Aging)을 활용함

 

[4] 프로세스 스케줄링 알고리즘 계산 : 각 프로세스의 평균 대기시간, 평균 반환시간을 구하기 (단, 프로세서는 시간 0에서 시작한다고 가정하고 운영체제로 인한 오버헤드는 무시)

 

** 반환시간 및 대기시간계산 방법(반종도 대반서) : 반환시간 = 종료시간 - 도착시간, 대기시간 = 반환시간 - 서비스 시간

 

[4-1] FIFO 스케줄링(비선점)

 

* P1 ~ P4 4개의 프로세스들에 대해 준비상태에서의 도착 시간과 각 프로세스가 필요로 하는 총 실행시간을 보여줌

프로세스	도착 시간	서비스 시간
P1	0	3
P2	1	7
P3	3	2
P4	5	5

 

순서	시간	사건
1	0~2	0시간만에 P1만 도착해서 P1 3시간 자원 점유
2	3~9	3시간에 P1종료, P2가 P3보다 먼저 도착했으므로 P2가 자원을 점유
3	10~11	10시간에 P2 종료, P3가 3시간에 도착 P4가 5시간에 도착해 있어서 먼저 도착한 P3가 자원을 점유
4	12~16	12시간에 P3 종료, 남아 있는 P4가 자원을 점유하여 17시간까지 서비스를 수행하고 종료

 

* 먼저 종료 시간을 구한 후, 반환시간과 대기시간을 구함

* 반환시간 = 종료시간 - 도착 시간

* 대기시간 = 반환시간 - 서비스 시간

 

프로세스	도착 시간	서비스 시간	종료 시간	반환시간	대기시간
P1	0	3	3	3 = 3-0	0 = 3-3
P2	1	7	10	9 = 10 - 1	3 = 9 - 7
P3	3	2	12	9 = 12 - 3	7 = 9 - 2
P4	5	5	17	12 = 17 - 5	7 = 12 - 5

 

* 평균 반환시간 = (3 + 9 + 9 + 12) / 4 = 8.25

* 평균 대기시간 = (0 + 2 + 7 + 7) / 4 = 4

 

[4-2] SJF(Shortest Job First) 스케줄링(비선점) 

 

* 위와 동일한 조건으로 종료 시간을 계산

순서	시간	사건
1	0~2	0시간만에 P1만 도착해서 P1 3시간 자원 점유
2	3~4	3시간에 P1 종료, 3시간에 P2, P3가 도착해 있지만 서비스 시간이 짧은 P3가 자원을 점유(2시간 실행)
3	5~9	5시간에 P3 종료, 5시간에 P2, P4가 도착해 있지만 서비스 시간이 짧은 P4가 자원을 점유(5시간 실행)
4	10~16	10시간에 P4 종료, 남아 있는 P2가 자원을 점유하여 17시간까지 서비스를 수행하고 종료

 

프로세스	도착 시간	서비스 시간	종료 시간	반환시간	대기시간
P1	0	3	3	3 = 3 - 0	0 = 3 - 3
P2	1	7	17	16 = 17 - 1	9 = 16 - 7
P3	3	2	5	2 = 5 - 3	0 = 2 - 2
P4	5	5	10	5 = 10 - 5	0 = 5 - 5

* 평균 반환시간 = (3 + 16 + 2 + 5) / 4 = 6.5

* 평균 대기시간 = (0 + 9 + 0 + 0) / 4 = 2.25

 

[4-3] SRT(shortest Remaining Time) 스케줄링(선점)

 

* P1 ~ P4 4개의 프로세스들에 대해 준비상태에서의 도착 시간과 각 프로세스가 필요로 하는 총 실행시간을 보여줌

프로세스	도착 시간	서비스 시간
P1	0	3
P2	2	6
P3	4	4
P4	8	2

 

순서	시간	사건
1	0~1	0시간에 P1 도착 후 자원을 점유
2	2	2시간에 P2 도착, P1의 남은 서비스 시간이 P2의 서비스 시간보다 짧아서 그대로 P1이 자원 점유
3	3	3시간에 P1이 종료되고 P2가 점유
4	4~7	4시간에 P3가 도착, P2의 남은 서비스 시간이 P3의 서비스 시간보다 길어서 P3가 자원 점유
5	8~9	8시간에 P4가 도착 후 P3는 종료, P2의 남은 서비스 시간이 P4의 서비스 시간보다 길어서 P4가 자원 점유
6	10~14	10시간에 P4 종료, 남아있는 P2가 15시간까지 서비스를 수행(남아있는 서비스 시간동안)하고 종료

 

프로세스	도착 시간	서비스 시간	종료 시간	반환시간	대기시간
P1	0	3	3	3 = 3 - 0	0 = 3 - 3
P2	2	6	15	13 = 15 - 2	7 = 13 - 6
P3	4	4	8	4 = 8 - 4	0 = 4 - 4
P4	8	2	10	2 = 10 - 8	0 = 2 - 2

 

* 평균 반환시간 = (3 + 13 + 4 + 2) / 4 = 5.5

* 평균 대기시간 = (0 + 7 + 0 + 0) / 4 = 1.75

 

[4-4] RR(Round-Robin) 스케줄링(선점)

 

* 시간 할당량은 2라고 가정

프로세스	도착 시간	서비스 시간
P1	0	3
P2	1	7
P3	3	2
P4	5	5

 

* 큐의 순서는 왼쪽부터 오른쪽으로 진행한다고 가정, 상태의( )는 남은시간

순서	시간	사건	상태
1	0	0시간에 P1 도착 후 자원 점유	큐 : 없음 프로세스 실행 : P1(2)
2	1	1시간에 P2 도착, 큐의 맨 뒤에 대기	큐 : P2(7) 프로세스 실행 : P1(1)
3	2	P1은 시간할당량을 모두 채웠기 때문에 큐 맨뒤에 대기 큐의 맨 앞에 있는 P2가 시간할당량 만큼 자원을 점유	큐 : P1(1) 프로세스 실행 : P2(6)
4	3	3시간에 P3 도착, 큐의 맨 뒤에 대기	큐 : P3(2), P1(1) 프로세스 실행 : P2(5)
5	4	P2는 시간할당량을 모두 채웠기 때문에 큐 맨뒤에 대기 큐의 맨 앞에 있는 P1이 시간 할당량 만큼 자원을 점유	큐: P2(5), P3(2) 프로세스 실행 : P1(0)
6	5	5시간에 P4가 도착하여 큐에 맨 뒤에 대기하고 P1이 종료되어 큐의 맨 앞에 있는 P3가 시간할당량 만큼 자원을 점유	큐: P4(5), P2(5) 프로세스 실행 : P3(2)
7	6~7	7시간에 P3가 서비스 할당량을 모두 채웠으므로 종료, 큐의 맨앞에 있는 P2가 자원을 점유	큐: P4(5), P2(5) 프로세스 실행 : P3(0)
8	8~9	P2가 시간 할당량 만큼 자원을 점유 후 큐 맨뒤에 대기 P4가 자원을 점유	큐: P4(5) 프로세스 실행 : P2(3)
9	10~11	P4가 시간 할당량 만큼 자원을 점유 후 큐 맨뒤에 대기 P2가 자원을 점유	큐 : P2(3) 프로세스 실행 : P4(3)
10	12~13	P2가 시간 할당량 만큼 자원을 점유 후 큐 맨뒤에 대기 P4가 자원을 점유	큐 : P4(3) 프로세스 실행 : P2(1)
11	14~15	P4가 시간 할당량 만큼 자원을 점유 후 큐 맨뒤에 대기 P2가 자원을 점유	큐: P2(1) 프로세스 실행 P4(1)
12	16~17	16시간에 P2가 서비스 시간을 모두 채웠으므로 종료 17시간에 P4가 서비스 시간을 모두 채웠으므로 종료	-

 

프로세스	도착 시간	서비스 시간	종료 시간	반환시간	대기시간
P1	0	3	5	5 = 5 - 0	2 = 5 - 3
P2	1	7	16	15 = 16 - 1	8 = 15 - 7
P3	3	2	7	4 = 7 - 3	2 = 4 - 2
P4	5	5	17	12 = 17 - 5	7= 12 - 5

 

* 평균 반환시간 = (5 + 15 + 4 + 12) / 4 = 9

* 평균 대기시간 = (2 + 8 + 2 + 7) / 4 = 4.75

 

(4) 프로세스 관리 - 교착상태(Deadlock)

 

• 다중프로세싱 환경에서 두 개 이상의 프로세스가 특정 자원할당을 무한정 대기하는 상태

[1] 교착상태 발생 조건(상점비환)

발생 조건	설명
상호 배제 (Mutual Exclusive)	프로세스가 자원을 배타적으로 점유하여 다른 프로세스가 그 자원을 사용할 수 없는 상태
점유와 대기 (Hold & Wait)	한 프로세스가 자원을 점유하고 있으면서 또 다른 자원을 요청하여 대기하고 있는 상태
비선점 (Non Preemption)	한 프로세스가 점유한 자원에 대해 다른 프로세스가 선점할 수 없고, 오직 점유한 프로세스만이 해제 가능한 상태
환형 대기 (Circle Wait)	두 개 이상의 프로세스 간 자원의 점유와 대기가 하나의 원형을 구성한 상태

 

[2] 교착상태 해결방법(예회발복)

발생 조건	설명	세부 기법
예방 (Prevention)	상호 배제를 제외한 나머지 교착상태 발생 조건을 위배(부정)하는 방안	범유 자원 해제 후 새 자원 요청
회피 (Avoidance)	안전한 상태를 유지할 수 있는 요구만 수락 (프로세스별 자원 최대요구량 확보)	은행가 알고리즘, Wound-Wait, Wait-Die
발견 (Detection)	시스템의 상태를 감시 알고리즘을 통해 교착 상태 검사	자원할당 그래프, Wait for Graph
복구 (Recovery)	교착상태가 없어질 때까지 프로세스를 순차적으로 Kill하여 제거, 희생자 선택해야 하고 기아 상태 발생	프로세스 Kill, 자원선점

 

** 은행가 알고리즘(Banker's Algorithm) : 사용자 프로세스는 사전에 자기 작업에 필요한 자원의 수를 제시하고 운영체제가 자원의 상태를 감시, 안정상태일 때만 자원을 할당하는 교착상태 회피기법

 

(5) 디스크 스케줄링(Disk Scheculing)

 

• 사용할 데이터가 디스크상의 여러 곳에 저장되어 있을 경우, 데이터를 액세스 하기 위해 디스크 헤드를 움직이는 경로를 결정하는 기법
• 디스크 스케줄링은 운영체제가 담당하고 목정은 처리량 최대화, 응답시간 최소화임

종류	설명
FCFS (First Come First Served) = FIFO	디스크 대기 큐에 가장 먼저 들어온 트랙에 대한 요청을 먼저 서비스 하는 기법
SSTF (Shortest Seek Time First)	- 현재 위치에서 탐색거리(Seek Distance)가 가장 짧은 트랙에 대한 요청을 먼저 서비스 하는 기법 - 일괄처리 시스템에 유용 - 현재 헤드 위치에서 가장 가까운 거리에 있는 트랙으로 헤드를 이동시킴
SCAN	현재 헤드의 위치에서 진행 방향이 결정되면 탐색 거리가 짧은 순서에 따라 그 방향의 모든 요청을 서비스 하고, 끝까지 이동한 후 역방향의 요청 사항을 서비스하는 기법
C-SCAN (Circular SCAN)	항상 바깥쪽에서 안쪽으로 움직이며 가장 짧은 탐색 거리를 갖는 요청을 서비스 하는 기법 안쪽 끝까지 이동했으면 다시 바깥쪽부터 탐색하는 방법으로 비교적 공평한 기법
LOOK = 엘리베이터 알고리즘	- SCAN을 기초로 사용하는 기법으로 진행 방향으로 더 이상의 요청이 없으면 역방향으로 진행하는 기법 - SCAN은 이동 방향의 끝까지 간 후 방향을 바꾸지만, LOOK 은 요청까지만 간 후 방향을 바꿈
N-STEP SCAN	- SCAN 기법을 기초로 하여 어떤 방향의 진행이 시작될 당시에 대기 중이던 요청들만 서비스하고, 진행 도중 도착한 요청들은 한꺼번에 모아서 다음의 반대 진행 방향으로 진행할 때 서비스하는 기법
SLTF (Shortest Latency Time First)	- 섹터 큐잉(Sector Queuing)이라고 하며, 회전지연시간 최적화를 위해 구현된 기법 - 디스크 헤드가 특정 실린더에 도착하면 그 실린더 내의 여러 트랙에 대한 요청들을 검사한 후, 회전지연시간이 가장 짧은 요청부터 서비스 하는기법

 

디스크 스케줄링 예시

 

* 디스크의 대기 큐의 트랙 번호

150

0

70

200

30

20

60

 

* 초기 헤드 위치가 50번 트랙이고 방향은 안쪽 방향(0번) 으로 이동중이라고 할 때의 계산

알고리즘	이동 순서
FCFS	50 -> 150 -> 0-> 70-> 200 -> 30 -> 20 -> 60
SSTF	50 -> 60 -> 70 -> 30 -> 20 -> 0 -> 150 -> 200
SCAN	50 -> 30 -> 20 -> 0 -> 60 -> 70 -> 150 -> 200
C-SCAN	50 -> 30 -> 20 -> 0 -> 200 -> 150 -> 70 -> 60
LOOK	대기큐에 0이 없다고 가정 | 50 -> 30 -> 20 -> 60 -> 70 -> 150 -> 200