[정보처리기사] 응용 SW 기초 기술 활용 : 운영체제의 특징(3)

 

3️⃣ 운영체제 핵심 기능 파악

☆☆☆

 

---

(2) 프로세스(Process) 관리

 

1. 프로세스의 개념

 

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

---

2. 프로세스 상태

 

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

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

• 완료(Complete) 상태는 종료(Terminated, Exit) 상태라고도 함

※ 준비 리스트는 각각 우선순위를 부여하여 가장 높은 우선순위를 갖는 프로세스가 다음 순서에 CPU를 할당받음 반면에 대기 리스트는 우선순위가 존재하지 않고, 입출력 등 처리가 끝나면 준비 상태로 바뀌면서 준비 리스트로 이동함

 

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

 

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

※ 문맥 교환(Context Switching) : CPU가 현재 실행하고 있는 프로세스의 문맥 상태를 프로세스 제어 블록(PCB)에 저장하고 다음 프로세스의 PCB로부터 문맥을 복원하는 작업

---

3. 프로세스 스케줄링

 

⓵ 프로세스 스케줄링의 개념 : CPU를 사용하려고 하는 프로세스들 간의 우선순위를 관리하는 작업

 

• 스케줄링은 처리율과 CPU 이용률을 증가시키고 오버헤드, 응답 시간, 반환 시간, 대기 시간을 최소화시키기 위한 기법
• 특정 프로세스가 적합하게 실행되도록 프로세스 스케줄링에 의해 프로세스 사이에서 CPU 교체가 일어남
• 프로세스 스케줄링을 실행하는 스케줄러의 유형 : 장기 스케줄러, 중기 스케줄러, 단기 스케줄러

---

⓶ 프로세스 스케줄링의 주요 용어

 

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

※ 준비 큐는 CPU 사용을 위해 기다리는 큐이고 대기 큐는 입출력 장치 사용을 위해 기다리는 큐임

---

⓷ 프로세스 스케줄링의 유형

 

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

 

---

⓸ 프로세스 스케줄링 알고리즘

 

  ㉮ 선점형 스케줄링 알고리즘

 

< 선점형 스케줄링 알고리즘의 유형 > 

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

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

---

  ㉯ 비선점형 스케줄링 알고리즘

 

< 비선점형 스케줄링 알고리즘의 유형 >

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

※ 기아(Starvation) 현상 : 시스템 부하가 많아서 준비 큐에 있는 낮은 등급의 프로세스가 무한정 기다리는 형상

※ 기아 현상을 해결하기 위해서 오랫동안 기다린 프로세스에게 우선순위를 높여주도록 처리하는 기법인 에이징(Aging)을 활용함

---

■ 프로세스 스케줄링 알고리즘 계산방법

 

 - 각 프로세스의 평균 대기 시간, 평균 반환 시간)을 구하려고 한다(단, 프로세서는 시간 0에 시작한다고 가정하며, OS로 인한 오버헤드는 무시함).

 ※ (반환 시간) = (종료 시간) - (도착 시간)

 ※ (대기 시간) = (반환 시간) - (서비스 시간)

 

 ⓵ FCFS(First Come First Service) = FIFO(First In First Out) 스케줄링 - 비선점

  - P1 ~ P4라는 4개의 프로세스들에 대하여 준비 상태에서 도착 시간과 각 프로세스가 필요로 하는 총 실행시간(서비스 시간)을 보여준다.

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

  - 다음과 같이 프로세스 상태를 통해 종료 시간을 계산한다.

 

  - 먼저 종료 시간을 구한 후, 반환 시간과 대기 시간을 구한다.

 

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

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

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

---

 ⓶ SJF(Shortest Job First) 스케줄링 - 비선점

  - P1 ~ P4라는 4개의 프로세스들에 대하여 준비 상태에서 도착 시간과 각 프로세스가 필요로 하는 총 실행시간(서비스 시간)을 보여준다.

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

  - 다음과 같이 프로세스 상태를 통해 종료 시간을 계산한다.

 

  - 먼저 종료 시간을 구한 후, 반환 시간과 대기 시간을 구한다.

 

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

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

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

---

 ⓷ SRT(Shortest Remaining Time) 스케줄링 - 선점

  - P1 ~ P4라는 4개의 프로세스들에 대하여 준비 상태에서 도착 시간과 각 프로세스가 필요로 하는 총 실행시간(서비스 시간)을 보여준다.

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

  - 다음과 같이 프로세스 상태를 통해 종료 시간을 계산한다.

 

  - 먼저 종료 시간을 구한 후, 반환 시간과 대기 시간을 구한다.

 

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

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

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

---

 ⓸ RR(Round Robin) 스케줄링 - 선점

  - P1 ~ P4라는 4개의 프로세스들에 대하여 준비 상태에서 도착 시간과 각 프로세스가 필요로 하는 총 실행시간(서비스 시간)을 보여준다.

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

  - 다음과 같이 프로세스 상태를 통해 종료 시간을 계산한다.

 

  - 먼저 종료 시간을 구한 후, 반환 시간과 대기 시간을 구한다.

 

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

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

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

---

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

 

⓵ 교착상태의 개념

 

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

---

⓶ 교착상태 발생 조건

 

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

 

---

⓷ 교착상태 해결 방법

 

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

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

---

5. 디스크 스케줄링(Disk Scheduling)

 

⓵ 디스크 스케줄링의 개념

 

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

---

⓶ 디스크 스케줄링의 종류

 

종류	설명
FCFS(First Come First Service) = FIFO(First In First Out)	디스크 대기 큐에 가장 먼저 들어온 트랙에 대한 요청을 먼저 서비스하는 기법
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

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	50 → 30 → 20 → 60 → 70 → 150 → 200