동기화, 세마포어, 교착상태, 메모리 관리

5장 1절에서는 운영체제가 여러 프로세스에게 CPU를 나눠주는 방법을 배웠습니다.

프로세스
스레드
PCB
문맥 교환
스케줄링
FCFS, SJF, SRT, RR, 우선순위, HRN

이번 절에서는 운영체제에서 가장 중요한 두 축을 배웁니다.

1. 여러 프로세스가 동시에 실행될 때 충돌을 어떻게 막을까?
2. 여러 프로그램에게 메모리를 어떻게 나누어 줄까요?

이번 절의 핵심은 다음과 같습니다.

동기화 = 여러 실행 흐름의 순서를 맞추는 것
임계영역 = 동시에 접근하면 안 되는 공유 자원 사용 구역
세마포어 = P, V 연산으로 임계영역을 보호하는 도구
교착상태 = 프로세스들이 서로 자원을 기다리며 멈춘 상태
메모리 관리 = 운영체제가 주기억장치를 나누고 보호하고 확장해 보이것이 하는 일

이번 절 내용은 운영체제 출제범위의 상호배제와 동기화, 세마포어, 생산자/소비자 문제, 모니터, 메시지 전달, 판독자/기록자 문제, 교착상태, 주기억장치 관리, 페이징, 세그멘테이션, 가상기억장치, 페이지 교체 기법에 해당합니다.

이번 절의 큰 그림

이번 절에서 배울 순서는 다음과 같습니다.

병행성과 경쟁상태
→ 임계영역과 상호배제
→ 세마포어
→ 생산자/소비자 문제
→ 모니터와 메시지 전달
→ 교착상태
→ 교착상태 4조건
→ 교착상태 처리 방법
→ 주기억장치 관리
→ 고정분할과 동적분할
→ 페이징
→ 세그멘테이션
→ 가상기억장치
→ 페이지 교체 기법

내용이 많지만 중심은 두 문장입니다.

동기화는 동시에 실행될 때 데이터가 꼬이지 않게 하는 것.
메모리 관리는 프로그램들이 메모리를 안전하고 효율적으로 쓰게 하는 것.

병행성과 동기화

병행성이란?

병행성은 여러 작업이 겹쳐서 실행되는 성질입니다.

실제로 CPU가 하나라면 한순간에는 하나만 실행하더라도, 운영체제가 매우 빠르게 작업을 바꿔가며 실행하면 여러 작업이 동시에 실행되는 것처럼 보입니다.

음악 재생
파일 다운로드
웹 브라우징
메신저 알림

이런 것들이 동시에 되는 것처럼 보입니다.

병행성 자체는 좋은 것입니다.

하지만 문제가 있습니다.

여러 프로세스나 스레드가 같은 데이터를 동시에 건드리면 값이 꼬일 수 있습니다.

공유 자원

공유 자원은 여러 프로세스나 스레드가 함께 사용하는 자원입니다.

공유 변수
파일
프린터
데이터베이스
메모리 공간
버퍼

예를 들어 은행 계좌 잔액을 생각하자.

balance = 10000

스레드 A는 1000원을 입금합니다.

balance = balance + 1000

스레드 B도 동시에 1000원을 입금합니다.

12000

이어야 합니다.

그런데 동시에 실행되면 잘못해서 11000이 될 수도 있습니다.

경쟁상태, Race Condition

경쟁상태는 여러 프로세스나 스레드가 공유 데이터에 동시에 접근해서 실행 순서에 따라 결과가 달라지는 상황입니다.

예를 살펴보겠습니다.

balance = 10000

balance를 읽음 → 10000
1000 더함 → 11000
balance에 저장

balance를 읽음 → 10000
1000 더함 → 11000
balance에 저장

둘 다 10000을 읽고 각각 11000을 저장하면 최종 결과가 11000이 됩니다.

하지만 실제로는 두 번 입금했으므로 12000이어야 합니다.

이런 문제가 경쟁상태입니다.

경쟁상태 = 실행 순서에 따라 결과가 달라지는 위험한 상황

운영체제 예시문제에서도 세마포어는 상호배제와 임계영역 보호에 사용되며, 경쟁상태를 유도하는 것이 아니라 막기 위한 도구라는 점이 출제됩니다.

임계영역

임계영역은 공유 자원에 접근하는 코드 부분입니다.

balance = balance + 1000;

이 코드는 공유 변수 balance를 수정합니다.

따라서 임계영역이 될 수 있습니다.

정의: 임계영역은 여러 프로세스나 스레드가 동시에 실행하면 문제가 생길 수 있는 공유 자원 접근 구역입니다.

임계영역에서는 중요한 규칙이 있습니다.

한 번에 하나의 프로세스 또는 스레드만 들어가야 합니다.

상호배제

상호배제는 임계영역에 동시에 여러 프로세스가 들어가지 못하게 하는 원칙입니다.

영어로는 Mutual Exclusion입니다.

상호배제 = 한 번에 하나만 임계영역에 들어가게 함

예를 들어 화장실 칸 하나를 생각해 보겠습니다.

한 사람이 들어가면 문을 잠급니다.
다른 사람은 기다립니다.
나오면 다음 사람이 들어갑니다.

임계영역도 비슷합니다.

한 스레드가 공유 데이터를 수정 중이면
다른 스레드는 기다려야 합니다.

임계영역 문제 해결 조건

임계영역 문제를 제대로 해결하려면 보통 세 조건이 필요합니다.

특히 시험에서 가장 중요한 것은 상호배제입니다.

상호배제 = 임계영역 동시 진입 금지

동기화란?

동기화는 여러 프로세스나 스레드의 실행 순서를 조정하는 것입니다.

상호배제는 동기화의 한 종류라고 볼 수 있습니다.

공유 데이터 보호
작업 순서 보장
경쟁상태 방지
자원 접근 조절

예를 들어 생산자/소비자 문제에서 생산자는 데이터를 만든 뒤 버퍼에 넣고, 소비자는 버퍼에서 데이터를 꺼냅니다.

소비자는 버퍼가 비어 있으면 꺼낼 수 없습니다.

생산자가 먼저 넣어야 소비자가 꺼낼 수 있습니다.

이런 순서 조정이 동기화입니다.

바쁜 대기, Busy Waiting

상호배제를 구현하는 가장 단순한 방식은 계속 확인하는 것입니다.

while (lock == 1) {
    // 계속 기다림
}
lock = 1;

// 임계영역

lock = 0;

이렇게 조건이 풀릴 때까지 계속 반복하며 기다리는 것을 바쁜 대기라고 합니다.

기다리는 동안 CPU를 계속 낭비합니다.

즉, 아무 일도 안 하면서 CPU를 잡아먹습니다.

그래서 운영체제에서는 더 좋은 동기화 도구가 필요합니다.

하드웨어 지원

상호배제를 위해 하드웨어가 지원하는 방법도 있습니다.

운영체제 범위에는 상호배제를 위한 하드웨어 지원으로 인터럽트 금지와 기계 명령어가 포함됩니다.

인터럽트 금지

단일 CPU 환경에서는 임계영역에 들어갈 때 인터럽트를 잠시 금지하면 CPU가 다른 프로세스로 전환되지 않습니다.

인터럽트 금지
임계영역 실행
인터럽트 허용

하지만 단점이 있습니다.

멀티프로세서 환경에서는 한 CPU의 인터럽트만 막아도 다른 CPU가 접근할 수 있습니다.
시스템 전체 응답성이 떨어질 수 있습니다.

기계 명령어

대표적으로 Test-and-Set 같은 원자적 명령어가 있습니다.

원자적이라는 말은 중간에 끊기지 않는다는 뜻입니다.

검사와 설정을 한 번에 수행

이런 명령어를 이용해 락을 구현할 수 있습니다.

세마포어와 동기화 기법

세마포어란?

이제 핵심인 세마포어입니다.

세마포어는 공유 자원 접근을 제어하기 위한 정수형 동기화 도구입니다.

세마포어는 두 연산을 사용합니다.

P 연산
V 연산

운영체제 예시문제에서도 세마포어는 상호배제를 위해 사용하고, P·V 연산을 사용하며, 임계영역을 보호한다고 나옵니다. 경쟁상태를 유도한다는 설명은 틀린 설명입니다.

P 연산과 V 연산

세마포어의 핵심은 P와 V다.

이름은 시험마다 다르게 나올 수 있습니다.

P = wait = down
V = signal = up

P 연산

P 연산은 자원을 사용하기 전에 수행합니다.

세마포어 값을 1 감소시킵니다.
사용 가능하면 들어갑니다.
사용 불가능하면 기다립니다.

P = 들어가기 전에 허락받기

V 연산

V 연산은 자원 사용이 끝난 뒤 수행합니다.

세마포어 값을 1 증가시킵니다.
기다리던 프로세스가 있으면 깨웁니다.

V = 나가면서 반납하기

세마포어 기본 구조

임계영역을 보호할 때는 보통 이렇게 씁니다.

P(mutex);

// 임계영역

V(mutex);

여기서 mutex는 상호배제를 위한 세마포어입니다.

mutex 초기값은 보통 1입니다.

mutex = 1

한 번에 하나만 들어갈 수 있습니다.

이진 세마포어와 범용 세마포어

세마포어는 크게 두 종류로 볼 수 있습니다.

이진 세마포어

값이 0 또는 1입니다.

1 = 들어갈 수 있음
0 = 누군가 사용 중

뮤텍스처럼 사용됩니다.

범용 세마포어

값이 여러 개일 수 있습니다.

semaphore = 3

프로세스 하나가 프린터를 사용하면 P 연산으로 1 감소합니다.

3 → 2

다 쓰면 V 연산으로 1 증가합니다.

2 → 3

세마포어 예시: 프린터 3대

프린터가 3대 있다고 가정하겠습니다.

printer = 3

P(printer)
printer = 2

printer = 1

printer = 0

이제 프로세스 D가 프린터를 쓰려고 하면 기다립니다.

printer = 0 → 사용 가능 자원 없음 → 대기

V(printer)
printer = 1

D가 깨어나 사용할 수 있습니다.

생산자/소비자 문제

운영체제에서 대표적인 동기화 문제입니다.

생산자는 데이터를 만듭니다.

생산자 = 데이터를 버퍼에 넣음

소비자는 데이터를 사용합니다.

소비자 = 버퍼에서 데이터를 꺼냄

문제는 버퍼 크기가 제한되어 있다는 것입니다.

버퍼가 가득 차면 생산자는 기다려야 합니다.
버퍼가 비어 있으면 소비자는 기다려야 합니다.

필요한 세마포어는 보통 세 개입니다.

mutex = 1
empty = N
full = 0

생산자 코드 흐름

생산자는 데이터를 넣어야 합니다.

P(empty);   // 빈 칸이 있는지 확인
P(mutex);   // 버퍼 임계영역 진입

// 버퍼에 데이터 삽입

V(mutex);   // 임계영역 나감
V(full);    // 찬 칸 증가

빈 칸이 있어야 넣을 수 있습니다.
버퍼를 수정할 때는 한 번에 하나만 들어갑니다.
데이터를 넣으면 찬 칸이 증가합니다.

소비자 코드 흐름

소비자는 데이터를 꺼내야 합니다.

P(full);    // 찬 칸이 있는지 확인
P(mutex);   // 버퍼 임계영역 진입

// 버퍼에서 데이터 삭제

V(mutex);   // 임계영역 나감
V(empty);   // 빈 칸 증가

데이터가 있어야 꺼낼 수 있습니다.
버퍼를 수정할 때는 상호배제가 필요합니다.
꺼내면 빈 칸이 증가합니다.

세마포어에서 주의할 점

P와 V 순서를 잘못 쓰면 문제가 생깁니다.

예를 들어 P를 하고 V를 안 하면?

자원이 영원히 반납되지 않음
다른 프로세스가 계속 기다림

또 여러 세마포어를 잘못된 순서로 잡으면 교착상태가 생길 수 있습니다.

프로세스 A: 자원 1 잡고 자원 2 기다림
프로세스 B: 자원 2 잡고 자원 1 기다림

이것이 이번 절 뒤에서 배울 교착상태입니다.

모니터

모니터는 공유 자원과 그 자원에 접근하는 절차를 하나로 묶은 고수준 동기화 도구입니다.

세마포어는 강력하지만 사용자가 P, V 순서를 직접 잘 관리해야 합니다.

실수하면 문제가 생깁니다.

모니터는 더 구조화된 방식입니다.

모니터 안에는 한 번에 하나의 프로세스만 들어갈 수 있습니다.

모니터는 보통 조건 변수와 함께 사용됩니다.

wait
signal

같은 연산으로 특정 조건을 기다리거나 깨울 수 있습니다.

운영체제 범위에도 모니터 구조와 시그널 기반 모니터가 포함됩니다.

메시지 전달

동기화와 통신을 위해 메시지를 주고받을 수도 있습니다.

send(message)
receive(message)

프로세스끼리 직접 메모리를 공유하지 않고 메시지를 통해 통신합니다.

분산 시스템에서 유리
공유 메모리보다 충돌 위험이 적을 수 있음

메시지 복사와 전달 비용이 생김

운영체제 범위에도 메시지 전달의 동기화와 주소 지정이 포함됩니다.

판독자/기록자 문제

판독자/기록자 문제도 대표적인 동기화 문제입니다.

공유 데이터가 있다고 가정하겠습니다.

판독자 = 읽기만 하는 프로세스
기록자 = 쓰기를 하는 프로세스

읽기만 하는 판독자 여러 명은 동시에 접근해도 문제가 없습니다.

하지만 기록자가 쓰는 동안에는 다른 판독자나 기록자가 접근하면 안 됩니다.

여러 판독자는 동시에 읽을 수 있습니다.
기록자는 혼자만 접근해야 합니다.
기록 중에는 읽기도 쓰기도 막아야 합니다.

운영체제 범위에도 판독자/기록자 문제와 판독자 우선, 기록자 우선이 포함됩니다.

교착상태

교착상태란?

이제 교착상태로 넘어갑니다.

교착상태, Deadlock은 여러 프로세스가 서로가 가진 자원을 기다리며 영원히 멈춰 있는 상태입니다.

예를 들어 두 사람이 길에서 마주쳤다고 가정하겠습니다.

A: 상대 프로세스가 먼저 자원을 놓기를 기다립니다.
B: 상대 프로세스가 먼저 자원을 놓기를 기다립니다.

둘 다 기다리기만 하면 아무도 움직이지 않습니다.

컴퓨터에서는 이런 상황입니다.

프로세스 P1은 프린터를 가지고 있고, 스캐너를 기다립니다.
프로세스 P2는 스캐너를 가지고 있고, 프린터를 기다립니다.

P1: 프린터 보유, 스캐너 대기
P2: 스캐너 보유, 프린터 대기

서로 상대방이 가진 자원을 기다리므로 멈춥니다.

교착상태 발생 4조건

교착상태가 발생하려면 네 조건이 모두 필요합니다.

상호배제
점유와 대기
비선점
환형대기

Mutual Exclusion
Hold and Wait
No Preemption
Circular Wait

운영체제 예시문제에서도 교착상태 발생 조건으로 mutual exclusion, hold-and-wait, circular wait, no preemption을 고르는 문제가 나옵니다.

조건 1: 상호배제

상호배제는 어떤 자원을 한 번에 하나의 프로세스만 사용할 수 있는 조건입니다.

프린터는 한 번에 한 프로세스만 사용 가능

공유 가능한 읽기 전용 파일처럼 여러 프로세스가 동시에 사용할 수 있는 자원은 교착상태 가능성이 낮습니다.

하지만 프린터, 쓰기 가능한 파일, 배타적 장치처럼 동시에 하나만 사용해야 하는 자원은 문제가 될 수 있습니다.

조건 2: 점유와 대기

점유와 대기는 프로세스가 이미 어떤 자원을 가진 상태에서 다른 자원을 기다리는 조건입니다.

P1은 프린터를 가진 상태에서 스캐너를 기다림
P2는 스캐너를 가진 상태에서 프린터를 기다림

하나는 쥐고 있으면서 다른 것을 기다림

이것이 점유와 대기입니다.

조건 3: 비선점

비선점은 운영체제가 프로세스가 가진 자원을 강제로 빼앗을 수 없는 조건입니다.

P1이 프린터를 사용 중이면 운영체제가 강제로 빼앗을 수 없음

자원은 프로세스가 스스로 반납해야 합니다.

자발적으로 반납해야 함

이 조건이 있으면 다른 프로세스는 기다릴 수밖에 없습니다.

조건 4: 환형대기

환형대기는 프로세스들이 원형으로 서로 자원을 기다리는 조건입니다.

P1은 P2가 가진 자원을 기다림
P2는 P3가 가진 자원을 기다림
P3는 P1이 가진 자원을 기다림

P1 → P2 → P3 → P1

원처럼 서로 물고 있는 상태입니다.

2개 프로세스에서도 가능합니다.

P1 → P2
P2 → P1

교착상태 4조건 정리표

상점비환

Mutual Exclusion
Hold and Wait
No Preemption
Circular Wait

시험에서는 critical section, busy-wait 같은 헷갈리는 보기를 섞어냅니다. 교착상태의 필수조건은 위 네 가지입니다.

자원할당 그래프

교착상태를 그림으로 표현할 때 자원할당 그래프를 씁니다.

프로세스 노드
자원 노드
요청 간선
할당 간선

프로세스 → 자원

은 요청을 의미합니다.

자원 → 프로세스

는 할당을 의미합니다.

P1 → R2
R1 → P1

P1은 R1을 가지고 있고 R2를 기다립니다.

자원할당 그래프에서 사이클이 있으면 교착상태 가능성이 있습니다.

단, 자원 종류당 인스턴스가 하나뿐이면 사이클은 교착상태를 의미합니다.

교착상태 처리 방법

교착상태 처리 방법은 크게 네 가지입니다.

예방
회피
탐지
복구

운영체제 범위에도 교착상태 방지, 회피, 탐지, 복구가 모두 포함됩니다.

교착상태 예방

예방은 교착상태 발생 4조건 중 하나를 깨뜨리는 방법입니다.

상호배제 조건 방지

가능하면 자원을 공유 가능하게 만듭니다.

하지만 프린터 같은 자원은 현실적으로 상호배제를 없애기 어렵습니다.

점유와 대기 조건 방지

프로세스가 필요한 자원을 한 번에 모두 요청하게 합니다.

필요한 자원을 모두 확보하거나
아예 시작하지 못하게 함

자원 이용률이 낮아질 수 있습니다.

비선점 조건 방지

기다려야 하면 이미 가진 자원을 강제로 반납하게 합니다.

환형대기 조건 방지

자원에 번호를 붙이고 항상 번호 순서대로만 요청하게 합니다.

R1 → R2 → R3 순서로만 요청 가능

그러면 원형 대기가 생기기 어렵습니다.

교착상태 회피

회피는 자원을 할당하기 전에 생각합니다.

이 자원을 지금 주면 시스템이 위험해질까?

안전하면 할당하고, 위험하면 기다리게 합니다.

대표 알고리즘은 은행원 알고리즘입니다.

모든 프로세스가 최대 요구량을 미리 알려줍니다.
운영체제는 자원을 할당해도 안전 상태가 유지되는지 검사합니다.
안전하면 할당합니다.
불안전하면 할당하지 않습니다.

안전 상태

안전 상태는 모든 프로세스가 어떤 순서로든 결국 완료될 수 있는 상태입니다.

안전 상태 = 교착상태 없이 끝낼 순서가 존재

불안전 상태라고 해서 반드시 교착상태는 아닙니다.

하지만 교착상태가 될 가능성이 있습니다.

교착상태 탐지

탐지는 일단 자원을 할당하고 시스템을 운영하다가, 주기적으로 교착상태가 생겼는지 검사하는 방법입니다.

교착상태가 생겼는가?

를 검사합니다.

자원할당 그래프나 탐지 알고리즘을 사용합니다.

자원 이용률이 높을 수 있습니다.

교착상태 검사 비용이 듭니다.

교착상태 복구

교착상태가 탐지되면 복구해야 합니다.

프로세스 종료
자원 선점

프로세스 종료

교착상태에 관련된 프로세스 중 하나 또는 전부를 종료합니다.

작업 손실이 생길 수 있습니다.

자원 선점

어떤 프로세스가 가진 자원을 빼앗아 다른 프로세스에게 줍니다.

어떤 자원을 누구에게서 빼앗을지 결정해야 합니다.
기아 문제가 생길 수 있습니다.

교착상태와 기아 차이

교착상태와 기아는 다릅니다.

교착상태 = 서로 물고 멈춤
기아 = 계속 차례가 안 옴

메모리 관리

메모리 관리란?

이제 메모리 관리로 넘어갑니다.

메모리 관리는 운영체제가 주기억장치를 효율적이고 안전하게 나누어 사용하는 일입니다.

여러 프로그램이 동시에 실행됩니다.
각 프로그램은 메모리가 필요합니다.
프로그램끼리 서로의 메모리를 침범하면 안 됩니다.
메모리 공간은 제한되어 있습니다.

운영체제 범위에는 주기억장치 관리로 논리적 구성, 물리적 구성, 재배치, 보호, 공유, 고정분할, 동적분할, 페이징, 세그멘테이션이 포함됩니다.

논리 주소와 물리 주소

프로그램이 사용하는 주소와 실제 메모리 주소는 다를 수 있습니다.

논리 주소

프로그램이 보는 주소입니다.

프로세스 입장에서의 주소

물리 주소

실제 RAM의 주소입니다.

하드웨어 메모리에서의 실제 위치

운영체제와 하드웨어는 논리 주소를 물리 주소로 변환합니다.

논리 주소 → 주소 변환 → 물리 주소

이 과정이 있어야 프로그램을 메모리의 어느 위치에 올려도 실행할 수 있습니다.

재배치

재배치는 프로그램을 메모리의 어느 위치에 올려도 실행할 수 있게 주소를 조정하는 것입니다.

예를 들어 프로그램은 자기 코드가 0번지부터 시작한다고 생각할 수 있습니다.

하지만 실제 메모리에서는 5000번지에 올라갈 수 있습니다.

논리 주소 100
실제 시작 위치 5000
물리 주소 5100

물리 주소 = 기준 주소 + 논리 주소

이런 계산이 필요합니다.

메모리 보호

메모리 보호는 한 프로세스가 다른 프로세스의 메모리 영역을 침범하지 못하게 막는 것입니다.

프로세스 A가 프로세스 B의 메모리에 쓰면 안 됨

이를 위해 경계 레지스터, 재배치 레지스터 같은 하드웨어 지원을 사용할 수 있습니다.

운영체제 예시문제에도 다중 프로그래밍 환경에서 메모리 보호를 위해 사용되는 레지스터로 경계 레지스터가 출제됩니다.

경계 레지스터

경계 레지스터는 프로세스가 접근할 수 있는 메모리 범위를 제한하는 데 사용됩니다.

허용 범위 밖 주소 접근 → 오류

메모리 공유

메모리 보호만 중요한 것이 아닙니다.

때로는 여러 프로세스가 같은 메모리 영역을 공유해야 합니다.

공유 라이브러리
프로세스 간 공유 메모리
여러 프로세스가 같은 읽기 전용 코드 사용

운영체제는 보호와 공유를 동시에 지원해야 합니다.

막아야 할 것은 막고,
공유해야 할 것은 안전하게 공유합니다.

고정분할

고정분할은 메모리를 미리 정해진 크기의 여러 구역으로 나누는 방식입니다.

메모리 전체를 100MB씩 5개 구역으로 나눔

각 분할에 하나의 프로세스를 넣습니다.

구현이 단순합니다.

분할 크기보다 작은 프로세스가 들어오면 남는 공간이 낭비됩니다.

이 낭비를 내부 단편화라고 합니다.

내부 단편화

내부 단편화는 할당된 공간 안에서 사용하지 못하고 낭비되는 공간입니다.

분할 크기 = 100MB
프로세스 크기 = 70MB

프로세스는 100MB 분할에 들어갑니다.

30MB

이 30MB는 같은 분할 안에 있지만 다른 프로세스가 쓰기 어렵습니다.

내부 단편화 = 할당받은 공간 내부의 낭비

동적분할

동적분할은 프로세스 크기에 맞게 메모리 공간을 나누는 방식입니다.

70MB 프로세스 → 70MB 할당
120MB 프로세스 → 120MB 할당

고정분할보다 내부 낭비가 적습니다.

프로세스가 들어오고 나가면서 작은 빈 공간들이 여기저기 생깁니다.

이것을 외부 단편화라고 합니다.

외부 단편화

외부 단편화는 메모리 전체 빈 공간은 충분하지만, 연속된 큰 공간이 없어서 할당하지 못하는 현상입니다.

빈 공간: 10MB, 20MB, 15MB, 30MB
총 빈 공간 = 75MB

그런데 50MB 프로세스를 넣으려면?

연속된 50MB 공간이 없음

그래서 할당하지 못합니다.

외부 단편화 = 빈 공간이 조각조각 흩어져 생기는 낭비

압축, Compaction

외부 단편화를 줄이기 위해 흩어진 빈 공간을 한쪽으로 모을 수 있습니다.

이것을 압축이라고 합니다.

프로세스 | 빈칸 | 프로세스 | 빈칸 | 프로세스 | 빈칸

프로세스 | 프로세스 | 프로세스 | 큰 빈칸

큰 연속 공간을 만들 수 있습니다.

프로세스를 메모리에서 이동시켜야 하므로 비용이 듭니다.

메모리 배치 전략

동적분할에서 빈 공간 중 어디에 프로세스를 넣을지 결정해야 합니다.

대표 전략은 다음과 같습니다.

최초 적합

빠릅니다.

앞에서부터 보다가 들어갈 수 있는 첫 공간에 배치

최적 적합

남는 공간을 최소화하려 합니다.

가장 잘 맞는 공간 선택

하지만 작은 조각이 많이 생길 수 있습니다.

최악 적합

가장 큰 공간에 넣습니다.

큰 빈 공간을 쪼개어 남은 공간도 활용 가능하게 하려는 방식

페이징과 가상기억장치

페이징

페이징은 프로세스의 논리 메모리와 실제 메모리를 같은 크기의 블록으로 나누어 관리하는 방식입니다.

용어가 중요합니다.

페이지 = 프로세스의 논리 메모리를 나눈 조각
프레임 = 실제 물리 메모리를 나눈 조각

논리 메모리: 페이지 0, 페이지 1, 페이지 2
물리 메모리: 프레임 0, 프레임 1, 프레임 2, 프레임 3

페이지는 꼭 연속된 프레임에 들어갈 필요가 없습니다.

페이지 0 → 프레임 3
페이지 1 → 프레임 0
페이지 2 → 프레임 2

이렇게 흩어져도 됩니다.

운영체제 범위에도 주기억장치 관리의 페이징, 가상기억장치 관리의 페이지 개념과 페이지 교체 기법이 포함됩니다.

페이징의 장점과 단점

장점

외부 단편화를 해결할 수 있습니다.
프로세스가 연속된 메모리에 올라갈 필요가 없습니다.
메모리 관리가 편해집니다.

단점

페이지 테이블이 필요합니다.
주소 변환 비용이 듭니다.
마지막 페이지에서 내부 단편화가 생길 수 있습니다.

페이징에서는 외부 단편화는 줄지만, 마지막 페이지가 꽉 차지 않으면 내부 단편화가 생길 수 있습니다.

페이지 테이블

페이지 테이블은 페이지 번호를 프레임 번호로 바꿔주는 표입니다.

예는 다음과 같습니다.

논리 주소는 보통 이렇게 나뉩니다.

페이지 번호 + 변위

물리 주소는 이렇게 됩니다.

프레임 번호 + 변위

논리 주소 = 페이지 2, 변위 100
페이지 2 → 프레임 2
물리 주소 = 프레임 2, 변위 100

컴퓨터구조 범위에도 가상 기억장치에서 페이지 테이블을 다룹니다.

TLB

페이지 테이블을 매번 메모리에서 찾으면 느립니다.

그래서 자주 쓰는 페이지 테이블 항목을 빠른 캐시에 저장합니다.

이것을 TLB라고 합니다.

TLB = Translation Lookaside Buffer

최근 주소 변환 정보를 빠르게 저장

논리 주소 발생
→ TLB 확인
→ 있으면 빠르게 프레임 번호 획득
→ 없으면 페이지 테이블 확인

TLB = 주소 변환용 캐시

세그멘테이션

세그멘테이션은 프로그램을 의미 있는 단위로 나누는 방식입니다.

코드 세그먼트
데이터 세그먼트
스택 세그먼트
힙 세그먼트

페이징은 고정 크기 블록으로 나누지만, 세그멘테이션은 의미 단위로 나눕니다.

세그멘테이션 주소는 보통 이렇게 봅니다.

세그먼트 번호 + 변위

가상기억장치

가상기억장치는 4장 2절에서도 봤습니다.

정의: 가상기억장치는 실제 RAM보다 더 큰 메모리를 사용하는 것처럼 보이것이 하는 기술입니다.

프로그램 전체를 한 번에 RAM에 올리지 않아도 됩니다.

필요한 부분만 RAM에 올리고, 나머지는 보조기억장치에 둡니다.

자주 쓰는 페이지 → RAM
당장 안 쓰는 페이지 → 디스크

실제 RAM보다 큰 프로그램 실행 가능
다중 프로그래밍 정도 증가
메모리 사용 효율 향상

운영체제 범위에는 가상기억장치의 개념, 페이징 기법, 페이지 호출 기법, 페이지 교체 기법, 워킹 집합이 포함됩니다.

요구 페이징

요구 페이징은 필요한 페이지가 실제로 요구될 때 메모리에 올리는 방식입니다.

처음부터 모든 페이지를 올리지 않습니다.
필요할 때 해당 페이지를 불러옵니다.

프로그램 실행
→ 현재 필요한 코드 페이지만 RAM에 적재
→ 나중에 다른 함수가 호출되면 해당 페이지를 불러옴

초기 적재 시간이 줄어듭니다.
메모리를 덜 사용합니다.

필요한 페이지가 없으면 페이지 폴트가 발생합니다.

페이지 폴트

페이지 폴트는 CPU가 접근하려는 페이지가 현재 RAM에 없을 때 발생합니다.

1. CPU가 어떤 페이지에 접근합니다.
2. 페이지 테이블을 확인합니다.
3. 해당 페이지가 메모리에 없습니다.
4. 페이지 폴트 발생.
5. 운영체제가 디스크에서 해당 페이지를 가져옵니다.
6. 페이지 테이블을 갱신합니다.
7. 중단되었던 명령어를 다시 실행합니다.

페이지 폴트는 비용이 큽니다.

왜냐하면 디스크 접근이 필요할 수 있기 때문입니다.

페이지 폴트가 너무 많으면 시스템이 매우 느려집니다.

페이지 교체

페이지 교체란?

메모리가 가득 찬 상태에서 새 페이지를 가져와야 하면 기존 페이지 하나를 내보내야 합니다.

이것이 페이지 교체입니다.

어떤 페이지를 내보낼 것인가?

OPT
FIFO
LRU
LFU
Clock

운영체제 예시문제에서도 페이지 교체 기법에서 가장 이상적인 교체 대상은 이후에 가장 오랫동안 사용되지 않을 페이지라고 나옵니다. 이것이 OPT, 즉 최적 페이지 교체의 기준입니다.

OPT, 최적 페이지 교체

OPT는 Optimal Page Replacement다.

앞으로 가장 오랫동안 사용되지 않을 페이지를 교체합니다.

현재 메모리: A, B, C
앞으로 사용 순서: A, B, D, A, B, E, ...

C가 앞으로 가장 늦게 쓰이거나 아예 안 쓰이면 C를 교체합니다.

이론적으로 가장 좋습니다.

미래를 알아야 하므로 실제 구현은 어렵습니다.

그래서 OPT는 실제 구현보다는 비교 기준으로 사용됩니다.

FIFO 페이지 교체

FIFO는 First In First Out입니다.

가장 먼저 들어온 페이지를 먼저 내보냅니다.

메모리 적재 순서: A → B → C

새 페이지 D가 필요하면 A를 내보냅니다.

구현이 쉽습니다.

오래 있었지만 자주 쓰는 페이지도 내보낼 수 있습니다.

LRU 페이지 교체

LRU는 Least Recently Used다.

가장 오랫동안 사용되지 않은 페이지를 내보냅니다.

즉 과거 사용 기록을 봅니다.

현재 메모리: A, B, C
최근 사용 순서: A가 방금 사용됨, B도 최근 사용됨, C는 오래 안 쓰임

그러면 C를 교체합니다.

지역성 원리에 잘 맞습니다.

최근 사용 기록을 관리하는 비용이 필요합니다.

LFU 페이지 교체

LFU는 Least Frequently Used다.

참조 횟수가 가장 적은 페이지를 내보냅니다.

예는 다음과 같습니다.

새 페이지가 필요하면 C를 내보냅니다.

예전에 많이 쓰였지만 지금은 안 쓰는 페이지가 남을 수 있습니다.

페이지 교체 알고리즘 비교

OPT = 미래
FIFO = 들어온 순서
LRU = 최근 사용
LFU = 사용 횟수

스래싱

스래싱은 페이지 폴트가 너무 자주 발생해서 CPU가 실제 작업보다 페이지 교체에 시간을 더 많이 쓰는 상태입니다.

계속 페이지를 가져오고 내보냄
실제 프로그램 실행은 거의 못 함

메모리에 비해 너무 많은 프로세스 실행
프로세스가 필요한 페이지 수보다 적은 프레임 할당

CPU 이용률 감소
디스크 사용량 증가
시스템 전체 느려짐

워킹 집합

워킹 집합은 어떤 시점에 프로세스가 자주 사용하는 페이지들의 집합입니다.

Working Set = 최근 일정 시간 동안 참조한 페이지 집합

운영체제는 각 프로세스의 워킹 집합이 메모리에 올라와 있도록 하면 페이지 폴트를 줄일 수 있습니다.

프로세스 A의 워킹 집합 = {2, 3, 5, 7}

이 페이지들이 RAM에 있으면 A는 비교적 잘 실행됩니다.

워킹 집합보다 적은 프레임을 주면 페이지 폴트가 자주 발생합니다.

자주 혼동되는 출제 포인트

혼동 포인트 1. 세마포어는 경쟁상태를 유도하는 것이 아닙니다

세마포어는 경쟁상태를 막고 임계영역을 보호하기 위한 도구입니다. 운영체제 예시문제에서도 “경쟁상태를 유도합니다”는 설명이 틀린 설명으로 나옵니다.

혼동 포인트 2. P와 V 연산 구분

P = wait = 자원 요청, 값 감소
V = signal = 자원 반납, 값 증가

혼동 포인트 3. 임계영역과 상호배제

임계영역 = 공유 자원 접근 코드
상호배제 = 한 번에 하나만 들어가게 함

혼동 포인트 4. 교착상태 4조건

상호배제
점유와 대기
비선점
환형대기

critical section이나 busy-wait는 교착상태 필수조건이 아닙니다.

혼동 포인트 5. 교착상태와 기아는 다릅니다

교착상태 = 서로 기다리며 멈춤
기아 = 계속 순서가 밀림

혼동 포인트 6. 내부 단편화와 외부 단편화

내부 단편화 = 할당받은 공간 안의 낭비
외부 단편화 = 빈 공간이 조각조각 흩어짐

혼동 포인트 7. 페이징과 세그멘테이션 차이

페이징 = 고정 크기
세그멘테이션 = 의미 단위, 가변 크기

혼동 포인트 8. 페이지와 프레임

페이지 = 논리 메모리 조각
프레임 = 물리 메모리 조각

혼동 포인트 9. 페이지 폴트

필요한 페이지가 RAM에 없을 때 발생

혼동 포인트 10. 최적 페이지 교체

가장 이상적인 교체 대상은 “앞으로 가장 오랫동안 사용되지 않을 페이지”입니다. 운영체제 예시문제의 정답도 이 기준입니다.

이번 절의 핵심 정리

동기화

여러 프로세스나 스레드의 실행 순서를 조정하는 것

경쟁상태

공유 데이터 접근 순서에 따라 결과가 달라지는 상황

임계영역

동시에 실행하면 안 되는 공유 자원 접근 코드

상호배제

한 번에 하나만 임계영역에 들어가게 함

세마포어

P, V 연산으로 공유 자원 접근을 제어하는 정수형 동기화 도구

P와 V

P = wait = 감소, 들어가기 전
V = signal = 증가, 나올 때

생산자/소비자 문제

빈 버퍼와 찬 버퍼를 세마포어로 조절

교착상태

프로세스들이 서로 자원을 기다리며 멈춘 상태

교착상태 4조건

상호배제
점유와 대기
비선점
환형대기

교착상태 처리

예방
회피
탐지
복구

메모리 관리

운영체제가 주기억장치를 할당, 보호, 공유, 회수하는 일

단편화

내부 단편화 = 할당 공간 내부 낭비
외부 단편화 = 빈 공간이 흩어짐

페이징

페이지와 프레임으로 나누어 관리

세그멘테이션

프로그램을 의미 있는 가변 크기 단위로 나누어 관리

가상기억장치

실제 RAM보다 큰 메모리를 쓰는 것처럼 보이것이 하는 기술

페이지 교체

OPT = 앞으로 가장 오래 안 쓸 페이지
FIFO = 가장 먼저 들어온 페이지
LRU = 가장 오래 사용 안 한 페이지
LFU = 가장 적게 사용된 페이지

핵심 한 문장

이번 절의 핵심을 한 문장으로 정리하면 다음과 같습니다.

운영체제는 여러 프로세스가 공유 자원을 안전하게 사용하도록 동기화와 세마포어를 제공하고, 교착상태를 예방·회피·탐지·복구하며, 메모리를 보호하고 효율적으로 나누기 위해 분할, 페이징, 세그멘테이션, 가상기억장치, 페이지 교체 기법을 사용합니다.

동기화 = 충돌 방지
세마포어 = P/V로 임계영역 보호
교착상태 = 서로 기다리며 멈춤
메모리 관리 = 나누고 보호하고 확장해 보이것이 함

확인 문제

문제 1

여러 프로세스나 스레드가 공유 데이터에 동시에 접근하여 실행 순서에 따라 결과가 달라지는 상황은?

① 캐시 히트 ② 경쟁상태 ③ 전위순회 ④ 페이지 테이블

문제 2

동시에 여러 프로세스가 접근하면 문제가 생길 수 있는 공유 자원 접근 코드 영역은?

① 임계영역 ② 보조기억장치 ③ 전역 HTML ④ 데이터버스

문제 3

임계영역에 한 번에 하나의 프로세스만 들어가게 하는 원칙은?

① 상호배제 ② 환형대기 ③ 스래싱 ④ 외부 단편화

문제 4

세마포어에 대한 설명으로 적절하지 않은 것은?

① 상호배제를 위해 사용합니다 ② P, V 연산을 사용합니다 ③ 임계영역을 보호합니다 ④ 경쟁상태를 유도합니다

문제 5

세마포어의 P 연산 의미로 알맞은 것은?

① 자원을 요청하고 세마포어 값을 감소시킵니다 ② 자원을 반납하고 세마포어 값을 증가시킵니다 ③ 페이지를 디스크로 내보냅니다 ④ 프로세스를 무조건 종료합니다

문제 6

세마포어의 V 연산 의미로 알맞은 것은?

① 자원을 요청합니다 ② 자원을 반납하고 세마포어 값을 증가시킵니다 ③ 임계영역을 삭제합니다 ④ 메모리 주소를 변환합니다

문제 7

교착상태의 발생 조건이 아닌 것은?

① 상호배제 ② 점유와 대기 ③ 비선점 ④ 캐시 히트

문제 8

교착상태의 4조건 중 프로세스가 이미 자원을 가진 상태에서 다른 자원을 기다리는 조건은?

① 점유와 대기 ② 외부 단편화 ③ 페이지 폴트 ④ 응답률

문제 9

교착상태의 4조건 중 프로세스들이 원형으로 서로 자원을 기다리는 조건은?

① 환형대기 ② 내부 단편화 ③ 시분할 ④ 주소 변환

문제 10

교착상태 처리 방법으로 보기 어려운 것은?

① 예방 ② 회피 ③ 탐지와 복구 ④ 후위표기식 변환

문제 11

다중 프로그래밍 환경에서 메모리 보호를 위해 사용되는 레지스터로 알맞은 것은?

① 경계 레지스터 ② 프로그램 카운터 ③ 범용 레지스터 ④ 누산기

문제 12

할당받은 메모리 공간 내부에서 사용하지 못하고 낭비되는 공간은?

① 내부 단편화 ② 외부 단편화 ③ 페이지 폴트 ④ 교착상태

문제 13

빈 공간의 총량은 충분하지만 연속된 큰 공간이 없어 할당하지 못하는 현상은?

① 내부 단편화 ② 외부 단편화 ③ 상호배제 ④ 캐시 히트

문제 14

페이징에서 논리 메모리를 나눈 고정 크기 조각은?

① 페이지 ② 프레임 ③ 세그먼트 ④ 버스

문제 15

페이징에서 물리 메모리를 나눈 고정 크기 조각은?

① 페이지 ② 프레임 ③ 프로세스 ④ 세마포어

문제 16

페이지 번호를 프레임 번호로 바꿔주는 표는?

① 페이지 테이블 ② 해시 함수 ③ 연결 리스트 ④ 접근제어행렬

문제 17

필요한 페이지가 현재 RAM에 없을 때 발생하는 것은?

① 페이지 폴트 ② 캐시 히트 ③ 전위순회 ④ 에이징

문제 18

페이지 교체 기법에서 이론적으로 가장 이상적인 교체 대상은?

① 참조된 횟수가 가장 적은 페이지 ② 주기억장치에 가장 오래 있었던 페이지 ③ 이전에 가장 오랫동안 사용되지 않은 페이지 ④ 이후에 가장 오랫동안 사용되지 않을 페이지

문제 19

가장 먼저 메모리에 들어온 페이지를 먼저 교체하는 방식은?

① FIFO ② LRU ③ LFU ④ OPT

문제 20

가장 오랫동안 사용되지 않은 페이지를 교체하는 방식은?

① FIFO ② LRU ③ LFU ④ 직접 사상

정답과 해설은 절별 확인문제 정답해설에서 확인합니다.

다음 6장 1절은 객체지향: 클래스, 객체, 상속, 다형성입니다. 5장 2절까지로 컴퓨터구조·운영체제 핵심이 끝났고, 이제 프로그램을 더 큰 단위로 설계하는 방법으로 넘어갑니다.