[101] 운영체제(Operation System)

정(Jeong) 2024. 5. 23. 12:20

2024. 5. 23. 12:20

#1. 운영체제 소개

##1.1. 운영체제 정의

##1.2. 운영체제 역할

##1.3. 컴퓨터 시스템과 운영체제

##1.4. 커널 모드와 사용자 모드

#2. 프로세스와 쓰레드

#3. 프로세스 스케줄링

#4. 병행 프로세스

#3. 프로세스 스케줄링

##3.1. 프로세스 스케줄링

###3.1.1. 스케줄링 단계

###3.1.2. 스케줄링 목표

###3.1.3. 스케줄링 정책

- 문맥(Context)과 문맥 교환(Context Switching)

문맥이란 CPU의 모든 레지스터(특히 프로그램 카운터(PC))와 기타 운영체제에 따라 요구되는 프로세스의 상태들을 의미한다. 문맥 교환이란 CPU가 현재 실행하고 있는 프로세스의 상태를 프로세스 제어 블록(PCB, 그중 PC)에 저장하고, 다른 프로세스의 PCB로부터 문맥을 복원하는 작업을 의미한다.

ex) 프로세스 A 작업이 진행 중이다가 프로세스 B가 갑자기 실행되어야 할 경우. 현 CPU 레지스터에 있는 값들을 프로세스 A PC에 임시보관 후, 프로세스 B의 정보를 프로세스 B의 PC에서 꺼내와 CPU에 할당 후 실행.

###3.1.4 스케줄링 평가 기준

평균대기시간: 각 프로세스가 수행이 완료될 때 까지 준비 큐에서 기다리는 시간의 합의 평균값.

평균반환시간: 각 프로세스가 생성된 시점부터 수행이 완료된 시점까지의 소요시간의 평균값

ex)

##3.2. 스케줄링 알고리즘

###3.2.1. FCFS 스케줄링

- FCFS(First-Come First-Served): 들어온 순서대로 처리

- 비선점 방식: 한 번 들어오면 인터럽트 되지 않음.

- 준비 큐에 도착한 순서에 따라 디스패치

- ex)

여기서

평균대기시간은 A(0) + B(7) + C(11) + D(12) = 30 를 4로 나누면 7.5

평균반환시간은 A(7) + B(11) + C(12) + D(15) = 45 를 4로 나누면 11.25

- 장점: 가장 간단

- 단점: 1) 짧은 프로세스가 긴 프로세스를 기다리거나, 중요한 프로세스가 나중에 수행될 수 있음 -> 시분할 운영체제나 실시간 운영체제에는 부적합. 2) 프로세스들의 도착 순서에 다라 평균 반환 시간 차이가 큼.

###3.2.2. SJF 스케줄링

- SJF(Shortest Job First): 준비 큐 작업들 중 예상 시간이 가장 짧은 작업을 먼저 처리(디스패치)하는 방식.

- 비선점 방식

- ex) FCFS 방식에서 든 예시와 같으나 각 작업의 도착시간이 모두 0으로 같지 않고 제각각이라는 데에서 차이.

대기시간:

A	B	C	D
0	11-2 = 9	7-4=3	8-5=3

평균대기시간: (0+9+3+3) / 4 = 15 / 4 = 3.25

반환시간:

A	B	C	D
7-0=7	15-2=13	8-4=4	11-5=6

평균반환시간: (7+13+4+6) / 4 = 30 / 4 = 7.5

- 장점: 일괄처리 환경에서 구현하기 쉬움.

- 단점: 실제로는 먼저 처리할 프로세스의 시간을 예상할 수 없다. 2) FCFS방식과 마찬가지로 비선점 방식이기 때문에, 새로 들어온 짧은 프로세스가 긴 프로세스를 기다리거나 중요한 프로세스가 나중에 수행될 수 도 있음. -> 시분할 운영체제나 실시간 운영체제에는 부적합.

###3.2.3. SRT 스케줄링

- SRT(Shortest Remaining Time): 준비 큐 작업들 중 예상 시간이 가장 짧은 작업을 먼저 처리(디스패치)하는 방식. 치.

- SJF 알고리즘의 선점 방식

- ex) 선점 방식(실행 중인 프로세스에 인터럽트 가능. 이 알고리즘에서 인터럽트 기준은 예상 시간)이기 때문에 A가 시랳ㅇ중이다가도 B가 들어오면

대기시간:

A	B	C	D
10-2=8	5-4=1	0	7-5=2

평균대기시간: (8+1+0+2)/4 = 11/4 = 2.75

반환시간:

A	B	C	D
15-0=15	7-2=5	5-4=1	10-5=5

평균반환시간: (15+5+1+5) / 4 = 26/4 = 6.5

- 장점: SJF보다 평균대기시간이나 평균반환시간에서 효율적

- 단점: 1) 마찬가지로 실제로는 프로세스의 시간을 예상할 수 없고, 2) 각 프로세스의 실행시간 추적, 선점 위한 문맥 교환 등의 오버헤드가 큼

###3.2.4. RR 스케줄링

- RR(Round Robin): 앞서 봤던 FCFS 방식(준비 큐에 도착한 순서대로 디스패치)이지만, 차이점은 정해진 시간 할당량에 의해 실행 시간 제한이 있다는 점. 주어진 시간이 넘어가면 다시 CPU를 빼앗기고 준비 큐의 뒤로 이동하게 된다.

- 선점 방식

- ex) 시간 할당량 = 4 라고 가정한다면, 아래와 같이 처리되게 된다.

- 대기시간

A	B	C	D
9-4=5	4-2=2	8-4=4	12-5=7

- 평균대기시간: (5+2+4+7)/4 = 18/4 = 4.5

- 반환시간

A	B	C	D
12-0=12	8-2=6	9-4=5	15-5=10

- 평균반환시간: (12+6+5+10)/4 = 33/4 = 8.25

- 장점: CPU를 독점하지 않고 공평하게 이용 -> 시분할 운영체제에 가장 적합

- 단점: 1) 시간할당량이 너무 크면 FCFS 스케줄링과 동일 2) 시간할당량이 너무 작으면 너무 많은 문맥 교환 발생으로 오버헤드 커짐

###3.2.5. HRN 스케줄링

- HRN(Highest Response Ration Next): 준비 큐에서 기다리는 프로세스 중 응답 비율이 가장 큰 것을 먼저 디스패치

- 비선점 방식

- 응답 비율: 예상실행시간이 짧을 수록, 대기시간이 길수록(오래 기다릴 수록) -> 응답 비율이 커짐

- ex) 비선점 방식이므로 한 작업이 끝날 때까지 인터럽트 되지 않는다. 가장 먼저 들어온 A가 처리되는 동안 들어온 B,C,D는 A가 작업이 끝나는 시점에 맞춰 응답 비율을 비교하게 된다. 이 시점에서의 응답 비율은 각각 2.25, 4, 1.67로, 가장 응답 빙비율이 큰 C가 다음 작업으로 선정되어 CPU를 할당 받게 된다. C가 끝나는 시점에서도 마찬가지로 추후 작업 발생.

- A가 끝나는 시점의 남은 작업 B,C,D의 응답 비율

B	C	D
대기시간: 7-2=5 예상시간: 4 응답비율: 5/4 +1 = 9/4 = 2.25	대기시간: 7-4=3 예상시간: 1 응답비율: 3/1 +1 = 4	대기시간: 7-5=2 예상시간: 3 응답비율: 2/3 +1 = 5/3 = 1.67

- B가 끝나는 시점의 남은 작업 B,D의 응답 비율

B	D
대기시간: 8-2=6 예상시간: 4 응답비율: 6/4 +1 = 10/4 = 2.5	대기시간: 8-5=3 예상시간: 3 응답비율: 3/3 +1 = 2

- 대기시간: 생략

- 평균대기시간: 4

- 반환시간: 생략

- 평균반환시간: 7.75

- 장점: SJF 스케줄링의 단점 보완(기다릴 수록 응답비율이 커져 무작정 대기시간이 길어지는 걸 막아줌)

- 단점: 실제로는 프로세스의 시간 예상 불가.

###3.2.6. 다단계 피드백 큐 스케줄링

- 다단계 피드백 큐 스케줄링: 앞서 나온 RR방식의 확대. I/O 혹은 연산 프로셋스의 특성에 따라 서로 다른 시간 할당량 부여.

- 선점 방식

-- 1) RR방식과 마찬가지로 일정 시간 내에 처리되지 못하면 할당된 CPU 뺴앗기고 준비 단계로 돌아간다. 하지만 다단계 방식은 단계별로 준비 큐가 따로 존재해, 기존에 있던 준비큐의 뒤로 돌아가는 것이 아닌 다음 단계의 준비큐의 뒤로 들어가게 된다는 차이가 있다. 2) 단계가 커질 수록 시간 할당량이 커진다. 즉, 뒤로 갈 수록 CPU를 잡고 작업을 처리할 수 있는 시가닝 길어진다. 3) 단계 k의 준비 큐에 있는 프로세스가 디스패치 되려면, 단계 1부터 k-1까지 모든 준비큐가 비어있어야만 한다.

- 특징:

1) I/O 위주 프로세스는 높은 우선권 유지

2) 연산 위주의 프로세스는 낮은 우선권이지만 긴 시간 할당량

###3.2.7. 스케줄링 알고리즘 정리

- 비선점 방식의 3가지

- 선점 방식의 3가지

- 각 방식 사이의 관계:

1) FCFS을 선점 방식 + 시간 할당량 부여 = RR

2) RR을 단계별로 처리 => 다단계 피드백 큐

3) SJF 를 선점 방식 -> SRT

4) SJF 에 대기 시간(응답 비율 개념) 추가 => HRN

한 단계 더 나아가기)

각 알고리즘은 언제 가장 적절하게 사용될까?

4. 병행 프로세스

4.1. 병행 프로세스 개요

병행성(cocurrency)

여러 개의 프로세스 또는 스레드가 동시 수행되는 시스템의 특성

병행 프로세스

정의: 동시 수행되는 여러 개의 프로세스 또는 스레드

실행 형태:

1) CPU의 갯수에 따라 -> (1) 1개의 CPU: 인터리빙 형식 (2) 여러 개의 CPU: 병렬 처리 형식

2) 멀티프로세서 시스템에서 메모리 구조에 따라 -> (1) 강결합 시스템 (2) 약결합 시스템

프로세스 간의 관계

독립 프로세스: 수행 중인 다른 프로세스에 영향을 주지도, 받지도 않음. 데이터 및 상태를 다른 프로세스와 공유 x. 특징: 1) 결정적(실행 결과는 입력에 의해서만 결정됨) 2) 재생 가능(같은 입력에 대해 항상 동일한 실행 결과)
협력 프로세스: 수행 중인 다른 프로세스와 영향을 주고 받는다. 데이터 및 상태를 다른 프로세스와 공유한다. 특징: 1) 비결정적(실행 결과는 실행 순서에 좌우됨) 2) 재생 불가능(같은 입력에 대해 항상 동일한 실행 결과 보장 x)

4.2. 병행성 문제

병행성 문제

정의: 협력 프로세스인 경우 발생 가능한 문제로, 동시에 임계 영역에 접근해 무결성 문제가 발생한다. 이러한 무결성 문제 방지를 위해 임계영역에 동시 접근 시 처리 순서를 정해야한다. 프로세스들끼리 어떻게 전반적으로 통신할 것인가에 대해서도 논해야 한다.

논의점: 1) 상호 배제 2) 동기화 3) 통신

1) 상호 배제

2개 이상의 프로세스가 동시에 임계 영역(동시에 사용하면 안되는 공유자원에 접근하는 코드 영역)을 수행하지 못하도록 하는 것.

2) 동기화

2개 이상 프로세스에 대한 처리 순서를 결정하는 것. 결국 상호 배제란 임계 영역에 대한 동기화 문제로 볼 수 있다.

3) 통신

프로세스들이 데이터를 공유하기 위해 통신이 필요하다. 이러한 프로세스 간 통신을 IPC(InterProcess Communication)라고 한다.

통신 방법에는 2가지 방법이 있다: 1) 하나의 변수를 사용 2) 메시지를 서로 주고 받음

4.3. 세마포어 ⭐️⭐️

정의: 상호배제와 동기화 문제를 해결하기 위한 도구로 Dijkstra가 제안한 정수형 공용 변수. 즉, 2개 이상의 프로세스가 공유하는 변수.

특징:

이 세마포어(변수)에 저장되는 값은 보통 사용 가능한 자원의 수 또는 잠금/풀림의 상태 등 정수로 표현 가능한 값이다.
상황에 맞춰 0 이상인 정수로 초기화한다.
두 기본 연산 P, V에 의해서만 사용된다. 즉, 기존 기본 변수와 다르게 그냥 접근해서 사용할 수 있는 것이 아니라, 두 연산에 의해서만 접근 및 사용 가능하다.
하나 주의 점은 이러한 연산 P와 V는 기본 연산(인터럽트 되지 않고 하나의 단위로 처리되는 연산)이라는 점이다. 즉, 연산 P 또는 V 중에는 작업이 끊기지 않는다.
이러한 세마포어는 대기 큐(FIFO 방식으로 동작)을 가져야 한다.

연산P: 검사, 감소시키려는 시도. 이러한 연산 P에 의해서 현재 프로세스가 대기 상태가 될 수 도 있다.

void P(semaphore s)
{
	if (s > 0)
    		s--;
        else
            현재 프로세스를 대기시킴;
}

연산V: 증가. 이러한 연산 V에 의해 현재 프로세스가 다시 진행이 될 수 도 있다.

void V(semaphore s) 
{
	if (대기 중인 프로세스 없음)
            s++;
        else
            대기 중인 프로세스 1개 진행;
}

예1: 세마포어를 이용한 상호 배제 문제 해결 예시: 세마포어 mutex(=mutual exclusion lock) 초깃값은 1.

예2: 세마포어를 이용한 동기화 문제 해결 예시: 세마포어 sync 초깃값은 0

4.4 생산자-소비자 문제 ⭐️

정의: 두 협력 프로세스 사이에 버퍼를 두고, 생산자와 소비자의 상황을 다루는 문제

*생산자: 데이터를 넣는 프로세스

*소비자: 데이터를 꺼내는 프로세스

조건:

상호배제(버퍼에 여러 프로세스가 동시에 접근할 수 없어야 한다. 즉, 버퍼에 데이터를 넣고 꺼내는 동안에는 데이터를 꺼내거나 넣을 수 없다.)
동기화(버퍼의 크기가 유한하므로 동기화가 필요하다. 예를 들어, 버퍼가 가득 찬 경우 생산자는 대기해야 하고, 버퍼가 빈 경우에는 소비자가 대기해야 하는 상황이 발생한다. 이 때 동기화가 필요하다.)

세마포어를 이용한 해결: 3개의 세마포어 사용.

mutex: mutul exclusion의 약자
empty: 버퍼에 존재하는 빈 공간의 갯수. 초깃값: 버퍼의 크기 n. 버퍼가 가득 찬 경우(empty=0) 생산자는 데이터를 생산하더라도 소비자가 버퍼에서 데이터를 꺼낸 후에야 버퍼에 데이터 넣는 것 가능.
full: 버퍼에 존재하는 데이터의 갯수. 초깃값: 0. 가용 데이터가 0인 경우에 소비자는 사용할 데이터가 없으므로 생산자가 버퍼에 데이터를 넣은 후에야 소비자는 버퍼에서 데이터를 꺼낼 수 있음.

4.5. 판독기-기록기 문제 ⭐️

정의: 여러 협력 프로세스 사이에 공유 자원을 두고, 판독기와 기록기의 상황을 다루는 문제.

*판독기: 데이터를 읽는 프로세스

*기록기: 데이터를 쓰는 프로세스

조건:

1) 상호배제: 기록기가 공유자원에 데이터 쓰는 중에는 다른 기록기나 판독기는 공유 자원에 접근 불가.

2) 그러나 여러 판독기는 동시에 공유자원에서 데이터 읽기 가능.

문제:

제1판독기-기록기 문제와 세마포어를 이용한 해결: 판독기가 공유자원에 접근 중이라면 기록기보다 판독기에 우선 순위를 주는 경우. 즉, 새로운 "판독기"는 공유 자원에 접근 가능하다. -> 기록기의 기아 상태 유발 가능한 문제.

제2판독기-기록기 문제와 세마포어를 이용한 해결: 판독기가 공유자원에 접근 중이라면 판독기보다 기록기에 우선순위를 주는 경우. 즉, 대기 중인 기록기가 있다면 새로운 판독기는 공유 자원에 접근이 불가하다. -> 판독기의 병행성이 떨어지고, 판독기의 기아 상태 유발 가능한 문제 발생.

##4.6. 프로세스 간 통신(IPC, InterProcess Communication)

병행 프로세스가 데이터를 서로 공유하는 방법으로, 1) 공유 메모리 방법 2) 메시지 전달 방법 2가지 방법이 쓰인다. 하나의 운영체제에서 두 방법을 함께 사용하는 것도 가능하다.

1) 공유 메모리 방법 ⭐️

정의: 협력 프로세스가 동일한 변수(= 공유 자원인 메모리 공간 사용)를 사용.

특징:

1) 대량 데이터 교환 가능 -> 고속 통신 가능

2) 통신상 발생 가능 문제 해결 - 응용 프로그램

2) 메시지 전달 방법 ⭐️

정의: 협력 프로세스가 시스템 호출 send(), receive()을 통해 메시지를 직접적으로 주고 받음.

특징:

1) 소량 데이터 교환에 적합

2) 통신상 발생 가능 문제 해결 - 운영 체제

논리적 구조

-통신 링크

-통신 링크의 구현

-통신 링크의 용량

직접 통신 & 간접 통신 ⭐️

직접 통신:

간접 통신: 두 프로세스 사이에 우체국을 두고 통신.

5. 교착 상태

5.1. 교착 상태 개요

프로세스의 자원 사용 절차

요구 -> (대기) -> 사용 -> 해제

교착 상태(deadlock)

여러 개의 프로세스가 서로 상대방의 작업이 끝나기만을 기다리고 있어 어느 쪽도 영원히 진행하지 못하는 상태.

* 기아상태와 교착 상태의 차이

기아 상태는 일부는 진행될 수 있는 가능성이라도 있지만, 교착 상태는 가능성이 없다는 데에서 차이가 있다.

5.2. 교착 상태 특성

교착 상태 발생 가능 조건 4가지 ⭐️

상호배제(mutual exclusion): 필요로 하는 자원을 다른 프로세스가 점유하고 있으면 반드시 대기해야 함.
점유대기(hold and wait): 한 프로세스가 한 자원을 이미 할당 받아 점유하고 있는 상황에서, 다른 프로세스가 점유하고 있는 또 다른 자원을 요청하여 해제 되기를 기다리는 상황 가능.
비선점(nonpreemption): 프로세스가 할당된 자원은 그 프로세스가 사용을 마치고 스스로 반납하기 전에는 해제되지 않음.
환형대기(circular wait): 프로세스의 자원 점유 및 점유된 자원의 요구관계가 환형을 이루며 대기하는 상황.

자원 할당 그래프 G = (V,E) ⭐️⭐️

자원이 어떻게 할당되고 있는지를 나타내는 그래프. 이 그래프 해석을 통해 교착 상태에 있는지 확인할 수 있다.

사이클이 없으면 교착 상태가 존재하지 않음.
사이클이 있으면 교착 상태가 발생할 수 도 있고 아닐 수도 있음.

5.3. 교착 상태 처리 기법

교착 생태를 처리하는 3가지 방법

예방(prevention) : 교착 상태의 네 가지 필요 조건이 동시에 만족되는 것을 피함으로써(4가지 중 1개라도 만족되지 않도록 함으로써) 교착 상태가 발생하지 않도록 하는 방법
회피(avoidance) : 프로세스에 필요한 자원의 최대량에 대한 정보를 이용하여 교착 상태가 발생하지 않도록 하는 방법 ⭐️
탐지 및 복구(detection and recovery) : 교착 상태의 발생 여부를 조사해, 발생한 경우에는 적절한 조치를 취하도록 하는 방법

1. 예방

2. 회피 ⭐️

안전 상태와 불안정 상태
회피 알고리즘(2가지)
- 변형된 자원 할당 그래프 (각 자원의 단위 자원이 1개뿐인 경우): 선언 간선을 요구 간선으로 변경. 이후 요구 간선을 할당 간선으로 변경. 이 때 요구를 할당으로 바꿔도 사이클이 생기지 않는 경우에만 자원을 할당하고 할당 간선으로 변환.
- 은행원 알고리즘 이용(각 자원의 단위 자원이 여러 개일 수 있는 경우): 자원을 요구 받으면 그 자원을 할당해 주고 난 후의 상태를 계산해서 그것이 안전상태인지 확인.

3. 탐지 및 복구

6. 메모리 관리

6.1. 프로세스와 메모리

메모리 관리

일반적으로 메모리를 효율적으로 관리하기 위해 다양한 관리 유형과 기법이 필요하다.

메모리 분할: 메모리를 고정 분할 할 것인지, 동적 분할 할 것인지
메모리 보호: 메모리를 어떻게 보호할 것인지
메모리 배치: 다음에 실행될 프로세스를 메모리 내의 어느 곳에 둘 것인지 고려
메모리 호출: 언제 새로운 프로세스를 메모리에 둘 것인지 고려
메모리 교체: 메모리가 꽉 찬 상태에서 어떤 프로세스를 제거할 지 고려
...

기억장치 계층구조

레지 - 캐시 - (주)메모리 - 보조기억장치

6.2. 단일 프로그래밍 환경

초기의 시스템
하나의 프로세스만 메모리를 단독으로 사용
연속 메모리 할당: 프로세스는 하나의 연속된 블록으로 메모리에 할당
문제점
- 메모리의 용량을 초과하는 프로세스는 실행할 수 x
- 지속적으로 사용되지 않는 프로세스도 메모리에 계속 적재
- 한 명의 사용자가 메모리를 전용으로 사용 -> 자원 낭비

6.3. 다중 프로그래밍 환경

현대의 시스템
여러 프로세스가 메모리에 동시 적재
현재 실행 중인 프로세스가 입출력 대기를 해야하면, 다른 프로세스에 CPU 할당 가능
CPU 연산과 입출력을 동시에 -> 자원 활용성 증가

6.3.1.메모리 분할 ⭐️

정의: 이러한 여러 프로세스를 메모리에 적재하기 위한 방법

종류:

고정 분할: 메모리를 여러 개의 고정된 크기 영역으로 분할하여 프로세스를 배치
- 방법1) 각 분할 영역마다 큐를 두고, 큐에 들어온 프로세스는 해당 분할 영역에만 적재 (컴파일 시 절대 주소로 번역)
- 방법2) 모든 프로세스를 하나의 작업 큐에 넣어, 어느 분할에서든 실행 가능하게 함 (컴파일 시 상대 주소로 번역)
- 문제: 내부 단편화 발생 가능. 프로세스의 크기가 적재된 분할 영역의 크기보다 훨씬 작아서 분할 영역 내에 낭비되는 메모리 발생.
동적 분할: 메모리의 분할 경계가 고정되지 않고 각 프로세스에 필요한 만큼의 메모리만 할당
- 방법: 프로세스에 필요한 만큼의 메모리를 할당하는 방식.
- 문제: 외부 단편화 발생 가능.
- 해결 방법: 통합, 집약
  - 통합: 인접된 공백을 더 큰 하나의 공백으로 만드는 것.
  - 집약: 메모리 내의 모든 공백을 하나로 모으는 것.

6.3.2.메모리 보호

하한-상한
하한-크기

6.3.3. 메모리 배치 기법 ⭐️

최초적합
후속적합
최적적합
최악적합

한 걸음 더 나아가기) 후속 적합과 최악 적합은 도대체 왜 만들어졌을까? 어디에 쓰이는 걸까?

6.5. 가상 메모리 ⭐️

가상 메모리(virtual memory): 컴퓨터 시스템의 메모리크기보다 더 큰 기억 공간이 필요한 프로세스를 실행할 수 있게 하는 방법. 실행 중인 프로세스에 의해 참조되는 주소(가상 주소)를 메모리에서 사용하는 주소(실주소)와 분리.
사상(mapping): 가상 주소를 실 주소로 변환하는 과정.
동적 주소 변환(DAT): 프로세스가 실행되는 동안 사상을 하는 과정
인위적 연속성: 가상 주소 공간에서 연속적인 주소가 실주소 공간에서도 연속적일 필요는 없음.

블록단위 주소 변환 ⭐️

블록 사상 시스템: 바이트나 워드 단위로 처리하던 항목별 주소 변환의 문제점을 보완해(처리 시간,자원 많이 듬), 정보를 블록 단위로 구분하여 각 블록이 메모리의 어디에 위치하는지만 관리하는 기법.
블록 크기가 커질 수록 사상 정보 저장에 필요한 메모리양은 작아짐. 단점은, 블록 이동에 필요한 전송 시간이 늘고, 메모리를 공유할 프로세스 수가 줄어든다.
블록 구성 방식에는 페이지(블록 크기 동일)와 세그먼트(블록 크기 다름)이 존재.

블록 구성 방식

페이징 기법: 가상 메모리를 페이지 단위(블록 크기 동일)로 나누어 관리하는 기법.
세그먼트 기법
페이징/세그먼트 혼용 기법

6.6. 메모리(페이징) 호출 기법

요구 페이지 호출 기법: 한 프로세스의 페이지 요구가 있을 때 비로소 요구 페이지를 메모리에 적재하는 방법
예상 페이지 호출 기법: 곧 사용될 것으로 예상되는 페이지를 미리 메모리에 옮겨 놓는 방법
- 예상이 잘못된 경우에는 예상 적재에 따른 시간과 메모리 공간 낭비가 발생한다.

6.7. 메모리(페이징) 교체 알고리즘

앞서 페이지를 호출하는 2가지 방법에 대해 배웠다.

그렇다면 페이지의 교체는 언제, 어떻게 발생할까? 페이지를 메모리에 추가하려 할 때 빈 페이지 프레임(페이지를 위한 실 메모리 공간)이 없다면 기존 페이지를 삭제하여 자리를 만들어야 한다. 이 때 기존 어떤 페이지를 삭제할 지 선택에 따라 효율이 달라진다.

참고:

최적화 원칙: 앞으로 가장 적게 사용될 페이지를 예측하여 삭제하는 알고리즘이다. 하지만 실제로 이걸 예상하는 것은 불가능하므로, 삭제할 때 사용된다기 보다는, 효율성을 따지기 위해 실제 사용된 알고리즘과 비교하는 용도로 사용된다.
교체 제외 페이지: 페이지 중에는 교체 되어서는 안되는 페이지도 존재한다. 이러한 교체 제외 페이지는 페이지 프레임에 고정되어 교체되지 않는다. 페이징을 위한 커널 코드 영역, 보조 기억장치 드라이버 영역, 시간을 맞춰 동작해야 하는 코드 영역, 입출력 장치로부터 직접 데이터가 교환외더야 하는 데이터 버퍼 영역 등이 여기에 해당된다.

종류:

FIFO(First-In First-Out): 매모리 내에 가장 오래된 페이지(큐의 가장 오른쪽)를 교체한다.
LRU(Least Recently Used): 매모리 내에 가장 오래 사용되지 않은 페이지를 교체한다.
- 국부성(locality)을 활용한 방식이다.
- 2가지 구현법: 1) 리스트 2) 참조시간
LFU(Least Frequently Used): 메모리 내에 참조된 횟수가 가장 적은 페이지를 교체한다.
2차 기회 페이지 교체: FIFO 교체 방식 + 참조 비트 개념 도입. 참조비트가 0이면서 메모리 내에 가장 오래된 페이지를 교체 한다.
- 참조 비트: 0으로 시작해서 참조될 때마다 +1 추가.
- 클럭 페이지 교체 알고리즘

6.8. 프로세스별 페이지 집합관리

개념: 각 프로세스가 사용할 수 있는 페이지 프레임의 개수 제한

종류:

워킹 세트 알고리즘: 페이지 부재 비율을 감소시키지 위해 데닝(Denning)이 제안한 모델
- W(t, s): 워킹 세트 단위. 시각 t에 t를 포함한 직전 s시간 동안 참조한 페이지의 집합
PFF 알고리즘: 페이지의 부재 빈도(PFF, Page Fault Frequency)를 이용해 프로세스별 페이지 집합의 크기를 변화시키는 기법.

Reference

김진욱(2023). 운영체제. 서울: 한국방송통신대학교출판부.

https://medium.com/@sohailk1999/five-state-process-model-6e83d7428c8c

Five State Process Model

Five-State Process Model is an extension of the Two-State Model. The two-stage model is efficient if all the processes in the Not-running…

medium.com

https://oizys.tistory.com/14

문맥교환(context switching)과 오버헤드(overhead)

1. 문맥교환 Context Switching 하나의 프로세스가 CPU를 사용 중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기 위해, 이전의 프로세스의 상태(문맥)를 보관하고 새로운 프로세스의 상태를 적재

oizys.tistory.com

https://junsangkwon.tistory.com/45#:~:text=%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C%EA%B0%80%20%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4%EB%A5%BC%20%EC%A0%9C%EC%96%B4,Switching)%EC%9D%84%20%EC%9C%84%ED%95%B4%EC%84%9C%20%ED%95%84%EC%9A%94%ED%95%A9%EB%8B%88%EB%8B%A4.

[OS] PCB(Process Control Block)와 문맥 교환(Context Switching)

PCB (Process Control Block) 운영체제가 프로세스를 제어하기 위해 정보를 저장해 놓는 곳으로, 프로세스의 상태 정보를 저장하는구조체입니다. 프로세스의 상태 관리와 문맥 교환(Context Switching)을 위

junsangkwon.tistory.com

'Computer Science 101' 카테고리의 다른 글

[101] 데이터베이스시스템(DBMS) (1)	2024.06.02
[암호학] 대칭키 암호화와 비대칭키 암호화 (0)	2024.05.14
[암호학] 전자봉투(Digital Envelope) (0)	2024.05.03
[암호학] 메시지 인증(Authentication)과 해시 함수(Hash Function) (0)	2024.05.03
[암호학] 블록화 암호의 종류와 운영 모드 개요 (0)	2024.05.03

Jeong in Tech