운영체제(OS)

사용자와 하드웨어 사이에서 인터페이스 역할 수행

• 프로세스 관리
• 저장장치 관리
• 네트워킹
• 사용자 관리
• 드라이버 관리

커널(Kernel)

운영체제에서 메모리와 디스크, 프로세스를 관리하기 위한 프로그램

• 소프트웨어와 하드웨어 간의 인터페이스 역할 수행

프로세스와 스레드

	프로세스	스레드
설명	프로그램의 자원 할당 단위	CPU의 기본 실행 단위
장점	장애 격리	시스템 자원의 효율적 사용
단점	비효율적인 자원 공유	공유 자원에 관련된 문제 발생 가능

• 프로세스는 프로그램 실행을 위해 OS에서 메모리와 CPU를 할당받는 단위임
  • 따라서 프로세스마다 독립적인 자원을 가짐
  • 따라서 한 프로세스의 장애가 다른 프로세스로 전파되지 않음
    • 브라우저 Chrome은 멀티프로세스 구조여서 탭 하나가 죽어도 다른 탭들은 살아있다!
  • 대신, 자원 공유가 비교적 비효율적임
    • 자원 할당에 시스템콜이 필요하다!
    • IPC 시 통신 부담이 든다!
• 스레드는 CPU 스케줄러가 관리하는 프로그램 실행의 가장 작은 단위임
  • 스레드는 프로세스의 구성 요소임
  • 따라서 같은 프로세스 내 스레드들끼리 자원을 공유함
    • 프로세스가 자원 할당의 단위이기 때문!
    • 멀티프로세싱에 비해 자원 공유가 효율적이다!
  • 대신, 공유 자원에 관한 문제가 발생함
    • 동기화 처리가 없으면 경쟁 상태가, 동기화 처리가 미흡하면 데드락이 발생한다!

스레드 모델

스레드 종류:

• 사용자 스레드: 라이브러리에 의해 생성된 스레드
• 커널 스레드: CPU 스케줄러에 의해 스케줄링되는 실행 단위

세 가지 스레드 모델:

• 커널 수준 스레딩 (1:1 매핑)
  • 사용자 스레드와 커널 스레드가 1:1 대응 (하나의 사용자 스레드에 하나의 커널 스레드가 대응)
  • 장점: 다중 CPU 환경에서 한 프로세스 내 스레드들을 동시에 실행할 수 있음
  • 단점: 문맥 교환이 느림
  • 구현 예시: JVM과 대부분의 OS
• 사용자 수준 스레딩 (N:1 매핑)
  • 사용자 스레드와 커널 스레드가 N:1 대응 (여러 사용자 스레드에 하나의 커널 스레드가 대응)
    • 커널은 사용자 스레드들에 대해 전혀 모르고, 커널 스레드만 스케줄링 한다
    • 따라서 라이브러리가 스케줄링을 해줘야 한다
  • 장점: 문맥 교환이 빠름
  • 단점: 한 프로세스 내 스레드들을 동시에 실행할 수 없음 (다중 CPU 환경이 의미 없음)
• 혼합형 스레딩 (N:M 매핑)
  • N개의 사용자 스레드가 M개의 커널 스레드와 대응 (1:1과 N:1의 절충안)
    • 이때 커널 스레드마다 경량 프로세스(LWP)가 1:1 매핑된다
    • 사용자 스레드는 경량 프로세스와 N:M 매핑된다
  • 장점: 문맥 교환이 빠르고 다중 CPU 활용 가능
  • 단점: 구현이 어려움

메모리 구조

프로세스

• Code 영역: 실행 파일 내 명령어들
• Data 영역: 전역 변수, 정적 변수
• Heap 영역: 동적 할당
• 스레드 마다 개별적인 영역들

스레드

• Stack 영역: 지역 변수, 매개 변수, 리턴 값
• 프로세스의 영역을 공유함

인터럽트(Interrupt)

우선순위가 높은 일이 발생했을 때, 하고 있던 일을 중단하고 바로 처리

• 하드웨어 인터럽트: I/O 장치에서 발생
• 소프트웨어 인터럽트: 명령 수행 중의 Exception이나 System Call으로 발생
  • Exception: 0으로 나누기, 할당되지 않은 주소 공간 액세스 등

인터럽트 벡터 테이블

인터럽트 헨들러의 주소를 보관하는 테이블

• 인터럽트 헨들러(혹은 ISR): 인터럽트 발생 시 실행할 루틴 함수

인터럽트 처리 과정

1. CPU 내 인터럽트 라인에 인터럽트 설정
2. CPU는 하나의 명령 수행을 마칠 때마다 인터럽트 라인 검사
3. 감지된 인터럽트가 마스킹되어 있다면 무시
4. 마스킹되지 않은 인터럽트 감지 시, 수행 중이던 프로세스를 멈추고 레지스터를 스택에 보관
5. 인터럽트 처리 루틴 실행
6. 스택에 보관했던 레지스터 복원
7. 인터럽트 해제

인터럽트 vs 폴링

• 인터럽트: 명령어 실행을 마칠 때마다 인터럽트 라인에 들어온 신호 체크
• 폴링: 다른 장치의 상태를 주기적으로 검사 (비교적 느릴 수 밖에 없다)

시스템 콜(System Call)

프로그램의 코드로 커널에 서비스를 요청하는 것

시스템 콜 실행 과정

1. 인자를 레지스터에 넣고 소프트웨어 인터럽트 실행
2. 커널 모드로 해당하는 커널의 함수 호출 (커널 모드: 모든 권한을 가짐)
3. 스케줄러에 의해 사용자 모드로 기존 프로그램에 복귀 (사용자 모드: 제한된 권한을 가짐)

fork()

프로세스 자신을 복사해내어 자식 프로세스 생성

• 주소 공간을 새로 할당받고, 부모로부터 복사함
• 부모의 FD를 복사하여 가짐 (FD를 공유하지 않음!)
• 이때 리턴 값은 자식 프로세스 상에서 0이고, 부모 프로세스 상에서는 자식 프로세스의 pid임

문맥 교환(Context Switching)

CPU가 다음 프로세스를 처리하기 위해 이전 프로세스의 문맥을 보관하고 새 문맥을 적재하는 작업

• 스택에 PCB를 보관하고, 다음 프로세스의 PCB를 복원함
• 문맥 교환 시 다른 작업 수행이 불가능하므로 일종의 오버헤드임

PCB(Process Control Block)

프로세스 관리 정보를 담은 자료 구조

• pid, 프로세스 상태, Program Counter, 레지스터, 스케줄링 정보, 메모리 관련 정보, 입출력 상태 정보 등

32bit OS vs 64bit OS

운영체제가 지원하는 CPU 구조의 사양 (레지스터의 크기)

• 32bit 레지스터는 4GB까지의 RAM을 인식할 수 있음
  • 32bit로 표현할 수 있는 주소가 최대 4GB(=232bytes)이기 때문!
• 인텔의 x86 아키텍처는 32bit CPU를, x64 아키텍처는 64bit CPU를 지원함

IPC

자원 공유를 위한 프로세스 간 통신

• 익명 PIPE: 부모-자식 프로세스 간 단방향 통신
• Named PIPE(FIFO): 이름있는 파일을 통해 다른 프로세스와도 통신 가능
• Message Queue: 메모리를 통해 한 쪽에서는 주고 한 쪽에서는 받는 통신
• 공유 메모리: 프로세스 간 메모리 공유, 가장 빠른 양방향 통신
• 시그널: 프로세스 간 신호 전달
• 소켓: 원격에서 프로세스 간 통신

CPU 스케줄링

프로세스 상태

• 생성(created): 프로세스 생성 중
• 준비(waiting): 프로세스가 CPU 할당을 기다리고 있음
• 실행(running): 프로세스가 CPU를 차지하고, 명령어가 실행되고 있음
• 대기(blocked): I/O나 시그널 등 이벤트를 기다리고 있는 보류 상태
• 종료(terminated): 프로세스가 종료됨

스케줄링

작업 수행을 위해 자원을 할당하는 방법

• 목적:
  • 처리율(단위 시간 당 작업 처리량) 최대화
  • 대기 시간(waiting에서 running이 될 때까지 기다린 시간의 총합) 최소화
  • 응답 시간(blocked에서 running이 될 때까지 기다린 시간) 최소화

프로세스 스케줄러

• 장기 스케줄러: 어떤 작업을 준비 큐에 넣을지 결정해서 승인 (Admit)
  • created → waiting
  • running → terminated
• 중기 스케줄러: 메모리에 적재되는 프로세스 수를 조절 (Swap out, Swap in)
  • waiting ↔ swapped out waiting
  • blocked ↔ swapped out blocked
  • 근래에는 중기 스케줄러가 장기 스케줄링 역할도 한다 (스왑 아웃된 프로세스로 다룸! 요구 페이징 기법)
• 단기 스케줄러: 준비 상태의 프로세스 중 어떤 것에 CPU를 할당할지 결정 (Dispatch)
  • waiting ↔ running
  • CPU 스케줄러라고도 부름

스케줄링 기법

• 비선점형: 프로세스가 종료되거나 중지될 때까지 실행 보장 (중간에 빼앗지 않음)
  • 일괄 처리 시스템에 적합
• 선점형: 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있음
  • 시분할 시스템에 적합

FCFS(First come, first served)

단순히 FIFO 방식의 비선점 방법으로 실행

평가 요소	FCFS
문맥 교환 오버헤드	✓ 낮음 (비선점형이므로)
처리율(Throughput)	✕ 낮음 (콘보이 효과 발생)
응답 시간(Response Time)	✕ 커질 수 있음 (콘보이 효과 발생)
아사 현상(Starvation)	✓ 없음 (결국 언젠가는 실행됨)

• 콘보이 효과: 앞의 긴 작업 때문에 짧은 작업들이 기다려야 함

SJF(Shortest job first)

비선점 방법으로 짧은 작업을 먼저 실행 (단, 작업에 걸리는 시간을 미리 알고 있어야 함)

평가 요소	SJF
문맥 교환 오버헤드	✓ 낮음 (비선점형이므로)
처리율(Throughput)	✓ 높음 (이상적이므로)
응답 시간(Response Time)	✕ 커질 수 있음 (아사 현상 때문에)
아사 현상(Starvation)	✕ 발생함

• 아사 현상: 짧은 작업이 계속 추가되면 긴 작업은 무한히 기다려야 함
• CPU는 작업에 걸리는 시간을 미리 알 수 없음
  • 작업에 걸리는 시간 = I/O 요청 전까지의 시간 (예측 불가!)
  • 따라서 CPU 스케줄링에는 활용하기 어려움
• 중간에 더 짧은 작업이 생기면 이에 대응하지 못 함 (따라서 이론상 SRTF의 처리율이 더 높다!)

RR(Round-robin)

작업을 번갈아가면서 단위 시간만큼 실행

평가 요소	RR
문맥 교환 오버헤드	▵ 커질 수 있음
처리율(Throughput)	✓ FCFS와 SJF 사이
응답 시간(Response Time)	✓ 짧음
아사 현상(Starvation)	✓ 없음

• 단위 시간이 짧을 수록 문맥 교환 오버헤드가 커지고, 길 수록 FCFS처럼 작동함
• 짧은 작업은 FCFS보다 빠르고, 긴 작업은 SJF보다 빠름
• 응답 시간이 중요한 Interactive 시스템에 적합한 방식 (제일 합리적이다!)

SRTF(Shortest remaining time first)

SJF의 선점형 방식, 잔여 시간 순으로 실행 (작업에 걸리는 시간을 미리 계산할 수 있어야 함)

평가 요소	SRTF
문맥 교환 오버헤드	▵ 커질 수 있음 (RR과 마찬가지)
처리율(Throughput)	✓ 가장 높음 (가장 이상적이므로)
응답 시간(Response Time)	✕ 커질 수 있음 (아사 현상 때문에)
아사 현상(Starvation)	✕ 발생함

• SJF와 달리, 중간에 더 짧은 작업이 생겨도 대응 가능 (따라서 이론상 SJF보다 처리율이 더 높다!)
• 가능한 많은 일을 해야하는 Batch 시스템에 적합한 방식 (처리율이 가장 높으므로!)

Priority Scheduling

우선순위가 높은 순서대로 실행

평가 요소	Priority Scheduling
문맥 교환 오버헤드	▵ 선점형: 커질 수 있음, 비선점형: 낮음
응답 시간(Response Time)	▵ 커질 수 있음 (아사 현상 때문에)
아사 현상(Starvation)	▵ 발생하지만 완화 가능

• Aging: 오래 대기한 프로세스의 우선순위를 높이면 아사 현상이 완화됨
• 작업에 기한이 주어지고 이를 꼭 지켜야 하는 Real-time 시스템에 최적인 방식 (우선순위를 주면 되니까!)

Multilevel queue

작업들을 여러 종류의 그룹으로 나누고, 그룹마다 우선순위가 다른 큐를 이용하는 선점형 방식

• 큐마다 각 그룹의 목적에 적합한 스케줄링 기법을 사용함
• 작업이 실행될 큐보다 높은 우선순위의 큐들이 모두 비어있어야 함
• 큐에 들어간 작업은 다른 큐로 이동하지 않음

평가 요소	Multilevel queue
문맥 교환 오버헤드	▵ 커질 수 있음 (RR과 마찬가지)
아사 현상(Starvation)	✕ 발생함

• 낮은 우선순위의 작업에 아사 현상이 발생함
• 처리해야 할 작업의 종류가 다양한 시스템에 적합함 (그룹을 나눠 각기 다른 기법을 사용하므로!)

Multilevel feedback queue

Multilevel queue에 Aging이 적용된 방식

• 단위 시간 안에 끝나지 못 한 작업이 다음 단계의 큐로 이동함 (가장 아래 큐는 RR 형식으로 작동)
• 낮은 우선순위의 작업에 발생하는 아사 현상을 완화함

평가 요소	Multilevel feedback queue
문맥 교환 오버헤드	▵ 커질 수 있음 (RR과 마찬가지)
아사 현상(Starvation)	✓ 완화됨

• 처리해야 할 작업의 종류가 다양한 시스템에 적합함 (Multilevel queue와 마찬가지!)
• 사용 예시: Windows, macOS

교착 상태(Deadlock)

두 개 이상의 작업이 서로 상대방의 작업이 끝나기를 기다려 아무 것도 완료되지 못 하는 상태

교착 상태의 조건

• 상호 배제: 한 자원 당 정해진 수의 프로세스만 점유 가능
• 점유 대기: 자원을 얻기 위해 대기해야 함
• 비선점: 이미 점유된 자원을 빼앗을 수 없음
• 순환 대기: 각 프로세스가 순환적으로 다음 프로세스가 요구하는 자원을 점유하는 상황

예방과 회피

교착 상태가 발생하지 않도록 미리 예방하거나 회피할 수 있음

• 교착 상태의 예방: 교착 상태의 조건 중 하나를 제거 (비현실적이거나 비용이 듬)
  • 상호 배제 제거: 여러 프로세스가 동시에 자원 점유 → 경쟁 상태가 만들어짐
  • 점유 대기 제거: 애초에 기다릴 필요 없도록 프로세스 실행 전 모든 자원을 할당 → 비현실적
  • 비선점 제거: 다른 프로세스가 점유 중인 자원을 빼앗을 수 있도록 허용 → 효율성이 떨어짐
  • 순환 대기 제거: 자원에 고유번호를 붙이고 순서대로 요구하도록 함 → 고유번호를 붙이는 기준이 필요함
• 교착 상태의 회피: 시스템에 순환 대기가 발생하지 않도록 자원 할당 상태를 미리 검사
  • 은행원 알고리즘: 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사

탐지와 회복

교착 상태가 발생했을 때 이를 회복하기 위해 탐지와 회복 단계를 진행함

• 교착 상태의 탐지: 자원 할당 그래프를 통해 교착 상태 탐지
  • 이때, 탐지 알고리즘으로 인한 오버헤드가 발생함
• 교착 상태의 회복: 자원을 할당받은 프로세스들을 종료하거나, 할당한 자원을 해제하여 교착 상태로부터 회복
  • 프로세스 종료: 교착 상태를 일으킨 프로세스 하나 혹은 여러 개를 종료함
  • 자원 해제: 할당한 자원을 해제하고 대기하고 있는 다른 프로세스에게 다시 할당

예시: 식사하는 철학자 문제

N명의 철학자가 원탁에 앉아 식사를 할 때, 철학자들 사이에 포크가 놓여있는 상황에서:

1. 왼쪽 포크를 점유하기 위해 대기
2. 오른쪽 포크를 점유하기 위해 대기
3. 양쪽 포크를 잡으면 식사
4. 오른쪽 포크, 왼쪽 포크 순으로 내려놓음
5. 다시 1번으로 가서 반복

이때 기아 상태가 발생하여 모든 철학자가 영원히 2번에서 대기하게 됨

• 기아 상태: 끊임없이 자원을 가져오지 못 하는 교착 상태

해결책

• 교착 상태 예방의 순환 대기 제거 방식:
  • n-1명의 철학자만 식사하도록 함
  • 한 명이 오른쪽 포크를 먼저 점유하도록 함
• 교착 상태 회피 방식:
  • 한 철학자가 양쪽 포크를 모두 잡을 수 있는 상황에서만 잡도록 하용

경쟁 상태(Race condition)

상호 배제의 부재로 공유 자원에 동시에 접근할 때 데이터의 일관성을 깨트리는 상태

• 이를 예방하기 위해 적절한 동기화 처리가 필요함!
• 임계 구역(Critical Section): 공유 자원에 접근하는 프로그램 코드 부분

세마포어(Semaphore)

• 정수 변수 S를 통해 다른 프로세스의 접근을 제한 (S 값: 더 점유할 수 있는 프로세스 수)

function V(semaphore S, integer I):
    [S ← S + I]

function P(semaphore S, integer I):
    repeat:
        [if S ≥ I:
        S ← S − I
        break]

• P(S, I): 임계 구역에 들어갈 때 실행
• V(S, I): 임계 구역에서 나올 때 실행

락(Lock) 혹은 뮤텍스(Mutex)

• 이진 세마포어와 같은 방식으로 자원을 잠굼
• 자원의 잠금이 해제될 때까지 대기하도록 함

가상 메모리

실제 메모리 주소를 추상화하여 메모리 크기나 주소 영역에 구애받지 않도록 만드는 기법

• 논리 주소가 실제 메모리에서 연속적일 필요가 없음 (세그먼테이션과 페이징 가능!)

메모리 관리 기법

세그먼테이션(Segmentation)

메모리를 논리적인 단위의 가변 크기 세그먼트(Segment)로 분할하여 프로그램 할당

• 논리적인 단위로 나누면 커널 입장에서 메모리 보호(접근 제어)가 쉬움 (e.g. Segmentation Fault)
• 단, 외부 단편화가 발생함 (메모리가 작은 공간 여럿으로 나눠져 큰 세그먼트를 할당할 수 없게 됨)
  • 이를 해결하기 위해 세그먼트를 스왑 영역에 넣었다 빼야 함 (이는 I/O 작업이므로 아주 느림!)

페이징(Paging)

메모리를 고정 크기의 프레임(Frame)으로 분할하고, 프로그램의 가상 주소 공간을 같은 크기의 페이지(Page)로 분할하여 할당

• 연속적인 가상 주소 공간이 분할된 메모리로 할당됨 (외부 단편화가 없다!)
• 단, 내부 단편화가 발생함 (프레임의 크기보다 작은 페이지가 할당되면 남는 부분이 생겨 메모리가 낭비됨)

페이징 세그먼테이션 혼용 기법(Segmentation with Paging)

페이징 기법을 적용하고, 페이지를 기준으로 세그먼테이션 기법을 적용
이때, 세그먼트가 실제 메모리 위치가 아닌 페이지 위치를 참조하도록 함

• 참조 관계: 세그먼트(논리 주소) → 페이지 → 프레임(물리 주소)
• 세그먼트로 분할하므로 메모리 보호가 쉬움 (세그먼테이션을 통해 얻는 장점!)
• 세그먼트의 페이지들이 메모리에서 연속적일 필요가 없음 (세그먼테이션으로 인한 외부 단편화가 없다!)

요구 페이징(Demand paging)

가상 메모리 기법에서 필요한 페이지만 메모리에 올려두는 기법

• 최소한의 메모리만으로 프로그램을 실행 (프로그램 전체를 메모리에 올릴 필요가 없음!)
• 메모리에 페이지가 없다면 페이지 부재 발생, 해당 페이지를 스왑 영역에서 가져옴
• 페이지를 올릴 빈 프레임이 없다면, 희생 페이지를 찾고 새로 올릴 페이지와 교체해야 함

페이지 교체 알고리즘

페이지 부재 시 새로운 페이지 할당을 위해 어떤 페이지와 교체할 것인지 결정

FIFO(First-in, first-out)

먼저 올라온 페이지 순으로 선택

• 가장 간단하지만 실제로 성능이 좋지 않음

OPT(Optimal)

앞으로 가장 사용하지 않을 페이지를 먼저 선택 (미래 예측)

• 이론적으로 최적이지만 비현실적

LRU(Least recently used)

오랫동안 사용되지 않은 순으로 선택 (과거를 통해 판단)

• 과거에 자주 사용된 페이지는 앞으로도 자주 사용될 것이라는 판단
• 이론적으로 OPT에 가까운 성능을 보임

메모리(Memory)

캐시 메모리

주기억장치(RAM)의 데이터를 임시로 저장해두는 곳

• CPU와 RAM의 속도 차이를 완화함

캐시 미스

찾는 데이터가 캐시에 존재하면 캐시 히트, 그렇지 않으면 캐시 미스가 발생하여 RAM에서 데이터를 꺼냄

• RAM에서 캐시 라인 단위로 데이터를 꺼내 캐시에 저장하고 CPU에게 찾는 데이터를 전달함
• 캐시 라인: 참조 지역성의 원리에 기반해 메모리에서 연속적인 데이터를 가져옴
  • 참조 지역성: CPU가 짧은 시간 내에 동일한 부분을 반복적으로 접근하는 경향성 (e.g. 반복문의 변수, 배열)