본문으로 건너뛰기

일주일만에 훑어보는 운영체제

운영체제라는 과목은 대학교에서도 많은 시간을 들여 공부하는 분야입니다. 일주일 만에 마스터 할 수는 없겠지만, 운영체제의 기본 개념과 운영체제가 하는 일에 대해 간단히 알아보겠습니다.

일주일만에 훑어보는 운영체제

Day 1: 운영체제 개념 이해​

  1. 운영체제 정의와 역할

    • 운영체제란 무엇인가?
    • 자원 관리(CPU, 메모리, 디스크, 네트워크)
    • 사용자/커널 모드와 특권 명령
    • 시스템 콜과 인터럽트
    • 보안 및 보호 메커니즘, 메모리/CPU 보호

  2. 커널(Kernel) 구조 및 인터럽트 처리

    • 커널 개념, 커널모드 vs 사용자모드
    • 인터럽트(하드웨어/소프트웨어), IRQ
    • 타이머를 통한 CPU 보호

  3. 메모리 계층 구조

    • 레지스터, 캐시, 메인 메모리, 보조기억장치
    • 메모리 계층 활용과 성능 최적화

Day 2: 프로세스와 스레드​

  1. 프로세스 개념

    • 프로세스 상태(new, ready, running, waiting, terminated)
    • PCB(Process Control Block), 컨텍스트 스위칭

  2. 프로세스 생성과 종료

    • fork(), exec(), exit(), wait() 시스템 콜
    • 부모-자식 관계, 자발적/비자발적 종료

  3. 스케줄러와 스케줄링 알고리즘

    • 장기/중기/단기 스케줄러 개념
    • FCFS, SJF, Priority, Round Robin, Multilevel Queue, Multilevel Feedback Queue

  4. 스레드(Thread) 개념 및 동기화 기법 소개

    • 스레드와 멀티스레딩
    • IPC(파이프, 메시지 큐, 공유 메모리 등) 및 동기화 기법(뮤텍스, 세마포어, 모니터)

Day 3: 메모리 관리​

  1. 메모리 할당 기법과 단편화

    • First-Fit, Best-Fit, Worst-Fit
    • 내부/외부 단편화, 스와핑

  2. 가상 메모리(Virtual Memory)

    • 요구 페이징(Demand Paging)
    • 페이지 테이블, Valid-Invalid Bit
    • 페이지 폴트 처리 과정

  3. 페이지 교체 알고리즘

    • FIFO, LRU, LFU, Optimal
    • Clock 알고리즘, Belady’s Anomaly

  4. 메모리 관리 기법 비교

    • 논리/물리 주소, MMU
    • 페이징(Paging), 세그멘테이션(Segmentation) 비교

Day 4: 프로세스 동기화와 데드락​

  1. 동시성(Concurrency)과 경쟁 조건(Race Condition)

    • 임계구역(Critical Section) 문제
    • 상호 배제(Mutual Exclusion), 진행, 한정 대기 조건

  2. 동기화 도구

    • 뮤텍스(Mutex), 세마포어(Semaphore), 모니터(Monitor)
    • 조건변수(Condition Variable)를 통한 조건 대기/신호

  3. 데드락(Deadlock)

    • 데드락 발생 조건(상호 배제, 점유 대기, 비선점, 순환대기)
    • 데드락 예방, 회피(은행원 알고리즘), 탐지 및 회복 기법

Day 5: 파일 시스템​

  1. 파일 시스템 구조

    • 파일/디렉토리 개념
    • 디렉토리 구조(단일, 2단계, 트리, 비순환 그래프)
    • Inode 구조 및 파일명/인덱스 매핑

  2. 파일 접근 방식

    • 순차 접근, 직접 접근, 인덱스 접근

  3. 디스크 스케줄링

    • FCFS, SSTF, SCAN, C-SCAN, LOOK 등 디스크 접근 최적화 기법
day 1: 운영체제 개념 이해

운영체제 개념 이해​

운영체제란? (Operating System)​

운영체제란 컴퓨터 하드웨어 바로 윗단에 설치되는 소프트웨어를 말합니다.

  • 컴퓨터 하드웨어: CPU, 메모리, 디스크, 네트워크 등 컴퓨터의 물리적인 부분
  • 운영체제 역할: 컴퓨터 하드웨어를 관리하고, 응용 프로그램과 하드웨어 간의 인터페이스 역할을 합니다.
    • 자원 관리: CPU, 메모리, 디스크, 네트워크 등의 자원을 관리
    • 프로세스와 쓰레드 관리: 프로세스 생성, 스케줄링, 종료, 스레드 생성, 스케줄링, 종료 등
    • 파일 시스템 관리: 파일 및 디렉토리 생성, 삭제, 읽기, 쓰기, 보호 등 + 케싱, 버퍼링, 저널링 등
    • 메모리 관리: 메모리 할당, 해제, 보호, 주소 변환 등 + 가상 메모리, 페이지 교체, 메모리 단편화 등
    • 입출력 관리: 입출력 장치와 컴퓨터 간의 데이터 전송 관리
    • 보안 및 보호: 권한 체계를 설정해 특정 자원에 대한 접근을 제한하며, 유저 모드와 커널 모드로 구분해 시스템 자원을 오용하거나 침해하는 것을 방지
    • 사용자 인터페이스 제공: 사용자와 컴퓨터 간의 상호작용을 위한 인터페이스 제공 + 시스템 호출, 그래픽 사용자 인터페이스(GUI) 등

위의 역할에 대한 내용들을 자세히 알아보겠습니다.

커널(Kernel)의 개념 및 구조​

컴퓨터에서 프로그램이 실행되려면 메모리 상에 올라가야 합니다. 운영체제 또한 메모리 상에 올라가야하는데 모든 코드가 메모리에 올라가면 메모리가 부족해질 수 있습니다. 이를 해결하기 위해 운영체제는 커널이라는 핵심 부분만 메모리에 올려두고, 나머지 부분은 필요할 때만 메모리에 올립니다.

커널모드 vs 사용자모드

커널모드란 운영체제가 CPU의 제어권을 가지고 운영체제 코드를 실행하는 모드를 말합니다. 이때는 모든 종류의 명령을 다 실행할 수 있다. 반면 사용자모드는 응용 프로그램이 CPU의 제어권을 가지고 사용자 프로그램을 실행하는 모드를 말합니다.

모드비트가 0이면 커널모드, 1이면 사용자모드입니다. 사용자모드에서 커널모드로 전환할 때는 시스템 콜을 사용합니다.

사용자의 프로그램이 하드웨어에 자유롭게 접근한다면 보안에 문제가 생길 수 있습니다. 이를 방지하기 위해 사용자 프로그램이 하드웨어에 직접 접근하는 것을 막고, 운영체제가 대신 하드웨어에 접근하도록 합니다.

  • 특권 명령: 사용자 프로그램이 하드웨어에 직접 접근하는 보안이 필요한 명령 (ex. 입출력 명령, 메모리 할당 명령)
  • 일반 명령: 사용자 프로그램이 실행하는 명령
  • 사용자 모드 to 커널 모드: 시스템 콜/인터럽트/예외 발생 시
  • 커널 모드 to 사용자 모드: 요청된 작업이 완료되었을 때

메모리 보안과 CPU 보호​

운영체제는 메모리 보안을 위해 메모리 보호를 제공합니다. 메모리 보호는 사용자 프로그램이 다른 프로그램이나 운영체제의 메모리 영역을 침범하지 못하도록 하는 것을 말합니다.

메모리 보호를 위해 Base, Limit Register를 사용합니다. Base Register는 프로그램이 메모리에 올라갈 때 시작 주소를 저장하고, Limit Register는 프로그램이 사용할 수 있는 메모리의 크기를 저장합니다. (기준 레지스터와 한계 레지스터)

  • Base Register: 프로그램이 메모리에 올라갈 때 시작 주소를 저장
  • Limit Register: 프로그램이 사용할 수 있는 메모리의 크기를 저장

두개를 통해 메모리 시작 주소 + 메모리 크기를 더한 값이 운영체제의 메모리 주소를 넘어가면 인터럽트를 발생시켜 프로그램을 종료시킵니다.

timer를 통한 CPU 보호는 프로그램이 무한 루프에 빠지거나, 다른 프로그램을 방해하는 경우를 방지하기 위해 사용됩니다. timer는 일정 시간이 지나면 인터럽트를 발생시켜 CPU의 제어권을 운영체제로 넘깁니다.

인터럽트(Interrupt)와 시스템 콜(System Call)​

인터럽트 는 CPU가 프로그램을 실행하고 있을 때, 입출력 하드웨어 등의 장치나 예외 상황이 발생하여 처리가 필요한 경우 CPU에게 알려 처리할 수 있도록 하는 것을 말합니다.

CPU는 인터럽트가 발생하면 현재 실행 중인 프로그램을 멈추고, 인터럽트 처리 루틴을 실행합니다. 인터럽트 처리 루틴이 끝나면 다시 중단된 프로그램을 실행합니다. (중단된 프로그램의 상태를 저장해두고 복구)

인터럽트는 하드웨어 인터럽트와 소프트웨어 인터럽트로 나뉩니다.

  • 하드웨어 인터럽트: 하드웨어 장치에서 발생하는 인터럽트
  • 소프트웨어 인터럽트: 프로그램이 CPU에서 실행 중에 발생하는 인터럽트

인터럽트 작업 처리 중 다른 인터럽트가 발생하면, 인터럽트 중첩이 발생할 수 있습니다. 이때 기본적으로 인터럽트 중첩을 허용하지 않습니다. (인터럽트 중첩을 허용하면 인터럽트 처리 루틴이 복잡해지고, 시스템의 안정성이 떨어질 수 있습니다.)

그러나 예외가 존재합니다. 새로 들어온 인터럽트가 현재 처리 중인 인터럽트보다 더 중요하다면, 현재 처리 중인 인터럽트를 중단하고 새로운 인터럽트를 처리합니다.

Interrupt Request Line (IRQ): 인터럽트가 발생했을 때 CPU에게 알리는 선으로 CPU는 IRQ를 통해 인터럽트가 발생했음을 알게 됩니다.

시스템 콜은 사용자 프로그램이 운영체제의 서비스를 받기 위해 커널에게 요청하는 것을 말합니다. 사용자 프로그램이 직접 운영체제의 서비스를 받을 수 없기 때문에, 시스템 콜을 통해 운영체제에게 요청합니다. (ex. 파일 읽기, 쓰기, 프로세스 생성, 종료 등)

메모리의 계층 구조​

메모리는 계층 구조로 이루어져 있습니다. 레지스터, 캐시, 메인 메모리, 보조기억장치로 나뉩니다.

속도가 빠를 수록 비싸고, 이 때문에 속도가 빠른 것에는 적은 양의 데이터를 저장하고, 속도가 느린 것에는 많은 양의 데이터를 저장합니다.

  • 레지스터(Register): CPU 내부에 있는 메모리로, 가장 빠르고 소량입니다.
  • 캐시(Cache): 메인 메모리와 CPU 사이에 위치하며, 메인 메모리의 일부를 저장합니다. 레지스터보다 느리지만 메인 메모리보다 빠릅니다.
  • 메인 메모리(Main Memory): 프로그램이 실행되는 메모리로, 캐시보다 느리지만 용량이 큽니다.
  • 보조기억장치(Secondary Storage): 하드디스크, SSD 등의 저장 장치로, 메인 메모리보다 느리지만 용량이 큽니다.

메모리의 계층 구조를 통해 레지스터와 캐시에는 자주 사용되는 데이터를 저장하고, 메인 메모리와 보조기억장치에는 자주 사용되지 않는 데이터를 저장하여 메모리의 속도와 용량을 효율적으로 사용할 수 있습니다.

day 2: 프로세스와 스레드

프로세스와 스레드​

프로세스(Process) 개념​

프로세스 는 실행 중인 프로그램으로, 운영체제로부터 자원을 할당받는 작업의 단위를 말합니다. 프로세스는 프로그램을 실행하는데 필요한 데이터, 메모리, 파일, 디바이스 등의 자원을 포함합니다.

process contect: 프로세스가 실행되는 동안 변화하는 정보들을 말합니다. (프로세스 상태, 프로그램 카운터, 레지스터, 메모리 정보, 입출력 상태 등)

프로세스는 다음과 같은 상태를 가집니다.

  • New: 프로세스가 생성 중인 상태
  • Ready: 프로세스가 CPU를 기다리는 상태 (메모리에 올라가 있지만 CPU를 사용하지 않는 상태)
  • Running: 프로세스가 CPU를 사용하여 실행 중인 상태
  • Waiting: 프로세스가 입출력 등의 이벤트를 기다리는 상태
  • Terminated: 프로세스가 실행을 마친 상태 (but 메모리에서 제거되지 않은 상태)

프로세스는 프로세스 제어 블록(PCB)에 의해 관리됩니다. PCB는 프로세스에 대한 정보를 저장하고, 프로세스의 상태 전이를 관리합니다.

컨텍스트 스위칭(Context Switching)은 CPU가 한 프로세스에서 다른 프로세스로 전환하는 것을 말합니다. 컨텍스트 스위칭은 프로세스의 상태를 저장하고 복구하는 작업을 수행합니다.

원래 실행 중이던 프로세스의 상태를 PCB에 저장하고, 다음 실행할 프로세스의 상태를 PCB에서 읽어와 CPU에 적재합니다. (PCB에 저장하면서 해당 프로세스 상태는 ready로 변경, 읽어온 프로세스 상태는 running으로 변경)

모드 변경은 같은 프로세스 내에서 특권 레벨만 전환하는 가벼운 작업인 반면, 컨텍스트 스위칭은 실행 주체 자체를 다른 프로세스로 넘어가는 상대적으로 무거운 작업이다. 따라서 모드 변경을 컨텍스트 스위칭이라고 할 수는 없으며, 컨텍스트 스위칭의 한 부분 집합이나 동등 개념으로 취급하지 않는다.

PCB(Process Control Block) 는 프로세스에 대한 정보를 저장하고, 프로세스의 상태 전이를 관리합니다.(커널 내부에 존재하는 자료구조)

PCB에는 다음과 같은 정보가 포함됩니다.

  • 프로세스 상태: new, ready, running, waiting, terminated
  • 프로그램 카운터: 프로세스가 다음에 실행할 명령어의 주소
  • CPU 레지스터: 누산기, 베이스 레지스터, 스택 포인터 등
  • CPU 스케줄링 정보: 프로세스의 우선순위, 스케줄 큐 포인터 등
  • 메모리 관리 정보: 메모리 사이즈, 메모리 영역 정보
  • 입출력 상태 정보: 프로세스에 할당된 입출력 장치 목록
  • 자원 사용 정보: 사용 중인 자원 목록

장기 스케줄러, 단기 스케줄러, 중기 스케줄러​

스케줄러는 어떤 프로세스에게 자원을 할당할지 결정하는 역할을 합니다. 스케줄러는 장기 스케줄러, 단기 스케줄러, 중기 스케줄러로 나뉩니다. (운영체제 커널 내부 코드)

  • 장기 스케줄러(Long-term Scheduler): 디스크에서 메모리로 프로세스를 적재하는 역할을 합니다. 메모리에 적재되는 프로세스의 수를 제어하여 다중 프로그래밍 환경을 유지합니다. (job scheduling)

  • 단기 스케줄러(Short-term Scheduler): CPU를 ready 상태의 프로세스 중 어떤 프로세스에게 할당할지 결정하는 역할을 합니다. CPU 스케줄링을 통해 프로세스를 실행할 순서를 결정합니다. 타이머 인터럽트에 의해 주기적으로 실행됩니다. (CPU scheduling)

현대 운영체제는 대부분 시분할 시스템을 사용하며, 시분할 시스템은 CPU를 여러 프로세스가 공유하여 사용하는 시스템을 말합니다. 시분할 시스템은 프로세스 간의 공정한 CPU 사용을 보장하며, 프로세스의 응답 시간을 최소화합니다. 일반적으로 시분할 시스템은 장기 스케줄러가 없습니다.

  • 중기 스케줄러(Medium-term Scheduler): 메모리에 너무 많은 프로세스가 올라가는 것을 방지하기 위해, 메모리에 있는 프로세스를 디스크로 쫓아내는 역할을 합니다. (swapping, swap out)

프로세스의 생성과 종료​

시스템이 부팅된 후, 운영체제가 실행되면서 프로세스가 생성됩니다. 그 이후에 생성되는 프로세스는 부모 프로세스에 의해 생성됩니다.

만약 자식 프로세스가 모두 종료되면, 부모 프로세스는 자식 프로세스의 종료 상태를 수집해야 합니다. 이를 위해 wait() 시스템 콜을 사용합니다.

wait() 시스템 콜은 자식 프로세스가 종료될 때까지 부모 프로세스를 대기 상태로 만들고, 자식 프로세스가 종료되면 자식 프로세스의 종료 상태를 수집합니다.

자식 프로세스가 생성될 떄, 부모 프로세스의 메모리 공간을 복사하여 자식 프로세스를 생성합니다. 이를 fork() 시스템 콜이라고 합니다.

프로세스가 종료될 때, 프로세스는 종료 상태를 운영체제에게 알리고, 운영체제는 프로세스가 사용하던 자원을 회수합니다. 이를 exit() 시스템 콜이라고 합니다.

exec() 시스템 콜은 새로운 프로그램을 실행하는 시스템 콜입니다. exec() 시스템 콜을 사용하면 현재 프로세스의 메모리 공간을 새로운 프로그램으로 덮어씁니다. (fork()와 exec() 시스템 콜을 사용하여 새로운 프로세스를 생성하고 실행할 수 있습니다.)

프로세스 종료의 종류

  • 자발적 종료: 프로세스가 마지막 명령을 수행한 후 exit() 시스템 콜을 호출하여 종료하는 것
  • 비자발적 종료: 부모 프로세스가 자식 프로세스를 강제로 종료시키는 것 (abort 시그널 등)
    1. 자식 프로세스가 자원을 많이 사용하여 시스템 전체의 성능을 해치는 경우
    2. 자식 프로세스가 더 이상 필요하지 않은 경우
    3. 부모 프로세스가 종료되는 경우

기본적으로 fork된 프로세스는 부모 프로세스의 모든 정보와 동일하다. 그렇기 때문에 자신이 복사된 것인지, 원본인지 알 수 없다. 이를 확인하기 위해 fork() 시스템 콜의 반환값을 확인한다. 만약 반환값이 0이라면 자식 프로세스, 0이 아니라면 부모 프로세스이다.

프로세스 간의 협력

  • 프로세스 간 협력: 프로세스 간 협력을 위해 IPC(Inter-Process Communication)를 사용합니다. IPC는 프로세스 간 데이터를 주고받는 것을 말합니다. IPC를 위해 파이프, 메시지 큐, 공유 메모리, 소켓 등의 방법을 사용합니다.

스레드(Thread) 개념​

스레드 는 프로세스 내에서 실행되는 흐름의 단위를 말합니다. 스레드는 프로세스 내에서 자원을 공유하며, 프로세스 내의 주소 공간이나 자원을 공유할 수 있습니다. (하나의 프로세스에는 최소 하나의 스레드가 존재합니다.)

스레드는 프로세스 내의 주소 공간이나 자원을 공유하기 때문에, 프로세스 내의 스레드들은 프로세스 내의 데이터 영역이나 코드 영역을 공유합니다. 이를 통해 스레드 간의 통신이 쉽고 빠릅니다.

멀티 스레딩은 멀티 프로세싱보다 적은 자원을 사용하며, 스레드 간의 통신이 쉽고 빠르다는 장점이 있습니다. 그러나 스레드 간의 자원 공유로 인해 동기화 문제가 발생할 수 있습니다.

동기화 문제를 해결하기 위해 뮤텍스(Mutex), 세마포어(Semaphore), 모니터(Monitor) 등의 동기화 기법을 사용합니다.

  • 뮤텍스(Mutex): 상호배제를 위한 동기화 기법으로, 임계 구역에 진입하는 스레드가 다른 스레드에 의해 방해받지 않도록 하는 동기화 기법입니다.

  • 세마포어(Semaphore): 뮤텍스와 유사한 동기화 기법으로, 임계 구역에 진입하는 스레드의 수를 제한하는 동기화 기법입니다.

  • 모니터(Monitor): 뮤텍스와 세마포어를 보다 쉽게 사용하기 위한 추상화된 동기화 기법으로, 임계 구역에 진입하는 스레드의 수를 제한하는 동기화 기법입니다.

CPU 스케줄링 알고리즘​

CPU는 여러 프로세스가 동시에 실행되는 것처럼 보이지만, 실제로는 CPU가 여러 프로세스를 번갈아가며 실행하는 시분할 시스템입니다. 프로그램 카운터(PC)를 통해 다음에 실행할 명령어의 주소를 가리키며, CPU 스케줄링 알고리즘을 통해 프로세스를 실행할 순서를 결정합니다.

프로그램 카운터(PC, Program Counter): CPU가 다음에 실행할 명령어의 주소를 가리키는 레지스터

스케줄링의 목표는 다음과 같습니다.

  1. CPU 이용률 최대화: CPU가 놀지 않고 일을 처리하도록 하는 것
  2. 처리율 최대화: 단위 시간당 처리하는 프로세스의 수를 최대화하는 것
  3. 응답 시간 최소화: 사용자가 명령을 입력한 후 첫 번째 응답을 받는 시간을 최소화하는 것
  4. 대기 시간 최소화: 프로세스가 CPU를 사용하기 위해 대기하는 시간을 최소화하는 것
  5. 소요 시간 최소화: 프로세스가 시스템을 사용하는 시간을 최소화하는 것

1,2번은 시스템 성능에 관련된 목표, 3,4,5번은 사용자 관점의 목표입니다.

CPU 스케줄링 알고리즘은 다음과 같은 종류가 있습니다.

  • FCFS(First-Come, First-Served): 먼저 도착한 프로세스를 먼저 실행하는 알고리즘
  • SJF(Shortest Job First): 실행 시간이 가장 짧은 프로세스를 먼저 실행하는 알고리즘
  • Round Robin: 시분할 시스템에서 사용되는 알고리즘으로, 각 프로세스에게 동일한 시간을 할당하여 실행하는 알고리즘
  • Priority Scheduling: 우선순위가 높은 프로세스를 먼저 실행하는 알고리즘
  • Multilevel Queue Scheduling: 여러 개의 큐를 사용하여 다양한 우선순위를 가진 프로세스를 처리하는 알고리즘
  • Multilevel Feedback Queue Scheduling: 프로세스의 상태에 따라 다른 큐로 이동하는 알고리즘

  1. FCFS(First-Come, First-Served)

    • 개념: 프로세스가 CPU를 요청한 순서대로 처리하는 가장 단순한 스케줄링 방식이다.

    • 장점: 구현이 간단하며, 공정성을 어느 정도 보장(먼저 온 순서대로 처리)한다.

    • 단점: 평균 대기 시간이 길어질 수 있으며, CPU 사용 시간이 긴 프로세스가 먼저 오면 뒤에 도착한 짧은 작업들이 오래 기다릴 수 있다(Convoy Effect).

    • 예시: 예를 들어, 3개의 프로세스 A(실행 시간 10ms), B(실행 시간 3ms), C(실행 시간 2ms)가 순서대로 도착했다고 하자. FCFS에서는 A를 모두 처리(10ms)한 뒤 B(3ms), 그 다음 C(2ms) 순으로 처리한다. C는 실행 시간이 짧음에도 A와 B를 기다려 총 15ms를 대기하게 된다.

  2. SJF(Shortest Job First)

    • 개념: 준비 큐에 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스를 먼저 처리하는 알고리즘이다. 최적 스케줄링(비선점형 가정)이라 불릴 정도로 평균 대기 시간을 최소화한다.

    • 장점: 평균 대기 시간을 최소화할 수 있다.

    • 단점: 실행 시간을 정확히 예측하기 어렵고, 긴 작업(Long Job)이 뒤로 밀려 “기아(Starvation)” 현상이 발생할 수 있다.

    • 예시: 프로세스 A(8ms), B(4ms), C(2ms), D(1ms)가 거의 동시에 도착했다고 하자. SJF에서는 D(1ms) → C(2ms) → B(4ms) → A(8ms) 순으로 실행한다. 이로써 평균 대기 시간을 최소화한다. 하지만 A처럼 긴 작업은 뒤로 밀릴 가능성이 있다.

    버스트 시간(Burst Time): 프로세스가 CPU를 사용하는 시간을 의미한다. SJF는 프로세스의 버스트 시간을 미리 알고 있어야 하며, 이는 실제 시스템에서는 알기 어려운 문제이다.

    기아 현상(Starvation): 우선순위가 낮은 프로세스가 계속해서 CPU를 할당받지 못하는 상황을 말한다. SJF에서는 실행 시간이 짧은 프로세스가 계속해서 CPU를 할당받아 기아 상태에 빠질 수 있다.

  3. Priority Scheduling

    • 개념: 프로세스마다 우선순위를 부여하고, 우선순위가 높은 프로세스에게 CPU를 먼저 할당한다. 우선순위는 정적일 수도 있고, 동적으로 변경할 수도 있다.

    • 장점: 긴급 처리가 필요한 프로세스를 빠르게 처리 가능하다.

    • 단점: 우선순위가 낮은 프로세스는 실행 기회를 얻지 못하고 기아(Starvation)에 빠질 수 있다. 이를 해결하기 위해 우선순위를 일정 시간이 지나면 높여주는 에이징(Aging) 기법을 적용한다.

    • 예시: A(우선순위 3), B(우선순위 1), C(우선순위 5), D(우선순위 2)라고 할 때, 우선순위가 숫자가 클수록 높다고 가정하면 C(5) → A(3) → D(2) → B(1) 순으로 실행된다.

    에이징(Aging): 우선순위가 낮은 프로세스가 오래 기다리면 우선순위를 높여주는 기법이다. 기아 상태를 방지하기 위해 사용된다.

  4. Round Robin (RR)

    • 개념: 시분할(Time-Sharing) 시스템에서 사용하는 알고리즘으로, 각 프로세스에 동일한 시간 할당량(Time Quantum)을 부여하고, 해당 시간이 지나면 다음 프로세스로 CPU를 넘긴다. 모든 프로세스가 공평하게 CPU를 일정 시간씩 번갈아가며 사용한다.

    • 장점: 모든 프로세스에 대한 응답 시간을 짧게 유지하고, 특정 프로세스가 CPU를 독점하는 상황을 방지한다.

    • 단점: Time Quantum이 너무 짧으면 빈번한 컨텍스트 스위칭으로 오버헤드가 커지고, 너무 길면 FCFS와 유사해진다. 최적의 Time Quantum 설정이 관건이다.

    • 예시: 프로세스 A, B, C가 있고 각자 10ms, 5ms, 6ms의 실행 시간이 필요하다고 하자. Time Quantum을 2ms로 설정하면, 스케줄러는 A(2ms) → B(2ms) → C(2ms) → 다시 A(2ms) → B(남은 3ms 중 2ms) → C(남은 4ms 중 2ms) → A(남은 6ms 중 2ms) … 와 같이 모든 프로세스를 골고루 조금씩 실행한다.

  5. Multilevel Queue Scheduling

    • 개념: 프로세스를 성격이나 우선순위에 따라 여러 개의 큐로 나누고, 각 큐별로 최적의 스케줄링 알고리즘을 적용한다. 예를 들어, 인터랙티브 작업은 RR, 배치(batch) 작업은 FCFS로 처리하는 식이다.

    • 장점: 서로 다른 특성을 지닌 프로세스를 다루기 쉽고, 시스템 요구사항에 따라 다양한 정책 적용이 가능하다.

    • 단점: 큐 간에 우선순위가 정해져 있으면 하위 큐에 속한 프로세스는 계속 뒤로 밀릴 수 있다(기아 문제). 이를 해결하기 위해 Multilevel Feedback Queue 스케줄링을 적용하여 프로세스 특성에 따라 큐를 이동시킬 수 있다.

    • 예시: 상위 우선순위 큐1: 대화형 프로세스(대부분 짧은 CPU 버스트), RR 적용 하위 우선순위 큐2: 배치 프로세스(긴 CPU 버스트), FCFS 적용 인풋 데이터 처리나 사용자 입력 대기 프로그램은 큐1에, 대용량 데이터 연산 같은 배치 작업은 큐2에 분리하여 각각에 맞는 스케줄링을 활용한다.

  6. Multilevel Feedback Queue

    • 개념: Multilevel Queue Scheduling의 단점을 보완하기 위해 고안된 스케줄링 알고리즘으로, 프로세스의 특성에 따라 큐를 이동시키는 기법이다. 프로세스가 CPU를 사용하는 시간이 길면 우선순위를 낮추고, 짧으면 우선순위를 높이는 방식으로 기아 문제를 해결한다.

    • 장점: 프로세스의 특성에 따라 큐를 이동시키기 때문에 다양한 프로세스를 효율적으로 처리할 수 있다.

    • 단점: 큐의 수가 많아지면 관리가 복잡해진다.

    • 예시: 큐1: 우선순위가 높은 큐, RR 적용 (time quantum: 8ms) 큐2: 우선순위가 낮은 큐, RR 적용 (time quantum: 16ms) 큐3: 우선순위가 낮은 큐, FCFS 적용 프로세스가 큐1에서 실행 중일 때, CPU 버스트 시간이 길어지면 큐2로 이동하고, 버스트 시간이 짧아지면 큐1로 이동한다. 큐2에서도 마찬가지로 버스트 시간에 따라 큐3으로 이동할 수 있다.

day 3: 메모리 관리

메모리 관리​

메모리란 프로그램이 실행되는 공간으로, 프로그램이 실행되기 위해 필요한 데이터와 명령어를 저장합니다. 메모리 관리는 프로그램이 메모리에 올라가는 방법과 메모리를 효율적으로 사용하는 방법을 다룹니다.

메모리 주소의 종류​

메모리 주소(Memory Address) 는 프로그램이 메모리에 접근하기 위해 사용하는 값으로, 메모리 주소는 다음과 같이 나뉩니다.

  • 논리 주소(Logical Address): 프로그램이 메모리에 접근하기 위해 사용하는 주소로, 프로그램이 생성하는 주소입니다.
  • 물리 주소(Physical Address): 실제 메모리에 저장되는 주소로, 논리 주소를 물리 주소로 변환하는 메모리 관리 장치(MMU)에 의해 변환됩니다.

MMU (Memory Management Unit): 논리 주소를 물리 주소로 변환하는 장치로, CPU와 메모리 사이에 위치합니다.

메모리 할당 및 관리​

스와핑(Swapping) 은 메모리에 올라온 프로세스 중 일부를 디스크로 내보내어 더 많은 프로세스를 실행할 수 있도록 하는 기법을 말합니다. 스와핑은 다음과 같은 경우에 사용됩니다.

  • 메모리에 여유 공간이 없을 때
  • 프로세스가 일정 시간 동안 사용되지 않을 때
  • 프로세스의 우선순위가 낮아질 때

메모리 할당은 프로그램이 메모리에 올라가는 방법을 말합니다. 메모리 할당은 다음과 같이 나뉩니다.

연속 메모리 할당(Contiguous Memory Allocation): 프로그램이 연속적인 메모리 공간에 할당되는 방법으로, 프로그램이 실행되는 동안 메모리 공간이 변하지 않습니다.

  • 정적 메모리 할당(Static Memory Allocation): 프로그램이 실행되기 전에 메모리를 할당하는 방법으로, 컴파일 시간에 메모리의 크기가 결정됩니다.
  • 동적 메모리 할당(Dynamic Memory Allocation): 프로그램이 실행 중에 메모리를 할당하는 방법으로, 실행 시간에 메모리의 크기가 결정됩니다.
  1. First-Fit 알고리즘
  • 개념: 빈 메모리 블록 리스트를 앞에서부터 순서대로 탐색하여, 해당 프로세스가 요구하는 크기보다 큰 첫 번째 빈 블록을 할당한다.
  • 특징:
    • 단순하고 빠르며, 구현이 비교적 용이하다.
    • 메모리 블록 분할 후 앞부분에 작은 단편화들이 남기 쉬워, 시간이 지날수록 앞쪽 공간이 쓸모없는 조각들로 채워질 수 있다.
  • 예시: 빈 블록이 [5MB, 12MB, 3MB, 7MB] 순서로 있다고 하고, 4MB 할당 요청이 왔을 때, First-Fit은 제일 앞에서 만난 5MB 블록을 4MB로 나누어 4MB 할당 후 1MB 남겨두는 식으로 진행한다.
  1. Best-Fit 알고리즘
  • 개념: 빈 메모리 블록 중 할당 요청 크기에 “가장 근접한(가장 작은 오차로 맞아떨어지는)” 블록을 선택한다. 즉, 프로세스가 요구하는 메모리 크기 이상인 블록들 중, 남는 공간이 최소가 되는 블록을 할당하는 방식이다.
  • 특징:
    • 단편화를 줄이기 위한 시도: 가능한 한 정확한 크기의 블록에 할당하여 남는 공간(단편화)을 최소화한다.
    • 하지만 실제로는 Best-Fit에서도 작은 단편화가 여러 곳에 산재하기 쉽고, 필요한 블록을 찾기 위해 전체 리스트를 훑어야 하므로 탐색 비용이 크다.
  • 예시: 빈 블록이 [5MB, 12MB, 3MB, 7MB]이고, 4MB 할당 요청이 왔다면, Best-Fit은 가능한 블록(5MB, 12MB, 7MB) 중, 남는 공간이 가장 적은 5MB 블록을 선택한다. 이로써 1MB 남는 공간이 발생하지만, 다른 블록(7MB나 12MB)을 선택했다면 남는 공간이 더 커질 것이다.
  1. Worst-Fit 알고리즘
  • 개념: 요청 크기보다 큰 블록들 중 가장 큰 블록을 선택해 할당한다.
  • 특징:
    • 의도: 가장 큰 블록을 나누어 쓰면, 나머지 부분이 상대적으로 크게 남아 이후 큰 요청을 수용하기 쉽다고 기대할 수 있다.
    • 실전에서는 큰 덩어리를 잘라쓰는 과정에서 실제 단편화가 더 커질 수도 있어 효율성을 장담하기 어렵다.
    • Best-Fit과 반대로 가장 큰 블록을 선택하기 때문에, 탐색 비용이 클 수 있으며, 단편화 문제가 여전히 발생한다.
  • 예시: 빈 블록이 [5MB, 12MB, 3MB, 7MB]에서 4MB 할당 요청이 왔다면, Worst-Fit은 [12MB] 블록을 선택하여 4MB 할당 후 8MB가 남는다. 나중에 큰 요청이 들어오면 남은 8MB 블록이 유용할 수 있다.

메모리 단편화(Fragmentation) 는 메모리에 빈 공간이 산재하여, 프로세스가 할당되지 못하는 상황을 말합니다. 메모리 단편화는 외부 단편화와 내부 단편화로 나뉩니다.

  • 외부 단편화(External Fragmentation): 메모리에 사용하지 못하는 작은 조각들이 산재하는 상황을 말합니다. 외부 단편화는 메모리 공간이 충분하지만, 연속적이지 않아 프로세스를 할당할 수 없는 상황입니다.

  • 내부 단편화(Internal Fragmentation): 프로세스가 요구하는 메모리보다 더 큰 메모리 공간을 할당하는 상황을 말합니다. 내부 단편화는 메모리 공간이 충분하지만, 프로세스가 사용하지 않는 메모리 공간이 발생하는 상황입니다.

불연속 메모리 할당(Non-Contiguous Memory Allocation): 프로그램이 연속적인 메모리 공간에 할당되지 않는 방법으로, 프로그램이 실행되는 동안 메모리 공간이 변할 수 있습니다.

  • 페이징(Paging): 프로그램을 고정된 크기의 페이지로 나누어 메모리에 할당하는 방법
  • 세그멘테이션(Segmentation): 프로그램을 논리적인 단위인 세그먼트로 나누어 메모리에 할당하는 방법

가상 메모리(Virtual Memory)​

가상 메모리(Virtual Memory) 는 물리 메모리를 보조기억장치로 확장하는 기법으로, 프로그램이 물리 메모리보다 큰 메모리 공간을 사용할 수 있도록 합니다.

가상 메모리는 프로그램이 필요한 부분만 물리 메모리에 올리고, 나머지 부분은 보조기억장치에 저장합니다. 프로그램이 실행되는 동안 필요한 부분만 물리 메모리에 올려 사용하고, 필요 없는 부분은 보조기억장치에 저장합니다.

  • 요구 페이징(Demand Paging): 프로그램이 실행되는 동안 필요한 페이지만 물리 메모리에 올리는 방식
  • 유효-무효 비트(Valid-Invalid Bit): 페이지 테이블에 있는 비트로, 페이지가 물리 메모리에 있는지 여부를 나타냅니다.
  • 페이지 폴트(Page Fault): 프로그램이 실행되는 동안 필요한 페이지가 물리 메모리에 없어서 보조기억장치에서 가져오는 현상

요구 페이징의 성능은 페이지 폴트의 발생 빈도에 크게 영향을 받습니다. 페이지 폴트는 디스크에서 정보를 읽어오는 막대한 시간이 소요되기 때문에, 페이지 폴트의 발생 빈도를 줄이는 것이 중요합니다.

  • 페이지 교체 알고리즘: 페이지 폴트가 발생할 때, 물리 메모리에 있는 페이지 중 어떤 페이지를 교체할지 결정하는 알고리즘

    • FIFO(First-In, First-Out): 가장 먼저 들어온 페이지를 교체하는 알고리즘
    • LRU(Least Recently Used): 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘
    • LFU(Least Frequently Used): 사용 빈도가 가장 적은 페이지를 교체하는 알고리즘
    • Optimal: 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘
    • Clock: 하드웨어 지원을 받아 LRU를 근사하는 알고리즘, 참조 비트를 사용하여 페이지를 교체한다.
  1. FIFO (First-In, First-Out) 알고리즘
  • 개념: 가장 먼저 들어온(가장 오래된) 페이지를 우선적으로 제거한다.
  • 특징:
    • 구현이 단순하며 큐(Queue) 자료구조를 사용해 쉽게 관리할 수 있다.
    • 프로그램의 실제 메모리 참조 패턴을 고려하지 않기 때문에, 실질적인 성능 측면에서 비효율적일 수 있다.
    • Belady의 모순(Belady’s anomaly) 라고도 불리는 FIFO 알고리즘의 오류(FIFO Anomaly) 가 발생할 수 있다. 페이지 프레임 수를 늘렸을 때 페이지 부재 횟수가 증가하는 현상이다.
  • 적용 예시:
    • 메모리 프레임이 3개일 때, A → B → C → A → B → D 순서로 페이지 참조가 발생할 경우, 가장 먼저 들어왔던 A, B, C 순서대로 내보낸다.
  1. LRU (Least Recently Used) 알고리즘
  • 개념: 가장 최근에 사용된 시점을 기준으로 오래 사용되지 않은 페이지부터 교체한다.
  • 특징:
    • 최근에 많이 사용된 페이지는 앞으로도 사용될 가능성이 높다는 지역성(Locality)을 가정한다.
    • FIFO보다 성능 면에서 대개 우수하지만, 각 페이지 접근 시점에 대한 기록이 필요해 구현 복잡도가 올라간다.
    • 페이지 접근 시마다 시간을 기록하거나 스택과 유사한 자료구조를 활용하여 현재 사용 패턴을 추적할 수 있다.
  • 적용 예시:
    • 메모리 프레임이 3개, 참조 순서가 A → B → C → A → B → D → A → C라 할 때, D를 로드할 때는 A, B, C 중 가장 오래 참조되지 않은 페이지를 찾아 제거한다(예: C가 가장 오랫동안 미사용 상태였다면 C 제거).
  1. LFU (Least Frequently Used) 알고리즘
  • 개념: 사용 빈도(참조 횟수)가 가장 낮은 페이지를 교체한다.
  • 특징:
    • 단순히 최근 시점이 아닌 전체 참조 횟수를 기준으로 교체를 결정한다.
    • 장기간 거의 사용되지 않은 페이지가 분명히 제외될 수 있다는 장점이 있으나, 최근에 많이 쓰였지만 아주 과거에 사용 횟수가 적었던 페이지가 비효율적으로 제거될 수 있다.
    • 참조 횟수를 관리하기 위한 추가적인 카운터나 자료구조가 필요하다.
  • 적용 예시:
    • A, B, C 페이지가 있고, A는 총 5번, B는 총 3번, C는 총 1번 참조되었다면, 새로운 페이지를 로드할 때 C(1회 참조)를 우선 제거한다.
  1. Optimal 알고리즘
  • 개념: 이론상 가장 이상적인 알고리즘으로, 앞으로의 페이지 참조 패턴을 모두 알고 있다고 가정했을 때, 앞으로 가장 오랫동안 사용되지 않을 페이지를 제거한다.
  • 특징:
    • 실제로 미래에 어떤 페이지가 필요할지 정확히 알 수 없으므로, 현실적으로 구현 불가능하다.
    • 다른 알고리즘의 성능을 평가하기 위한 기준(비교 대상)이 된다.
    • 가능한 페이지 부재 횟수를 최소화한다.
  • 적용 예시:
    • 참조 순서가 A → B → C → D → A → B일 때, D를 로드하기 위해 어떤 페이지를 빼야 할 지를 미래 참조 기반으로 판단한다. 앞으로 가장 늦게 사용할 페이지를 선택해 제거한다(예: A와 B는 곧 필요하나 C는 한참 뒤나 필요 없으므로 C 제거).
  1. Clock 알고리즘
  • 개념: LRU를 근사하는 알고리즘으로, 참조 비트를 사용하여 페이지를 교체한다. LRU와 비슷한 성능을 보이면서도 구현이 간단하다. 하드웨어가 지원해주기 때문이다.
  • 특징:
    • 페이지를 참조하면 해당 페이지의 참조 비트를 1로 설정한다.
    • 교체 시, 시계 바늘을 회전시키며 참조 비트가 0인 페이지를 찾을 때까지 이동한다. 참조 비트가 1인 페이지는 0으로 재설정만 하고 넘어간다.
    • 한 바퀴 돌아도 0인 페이지가 없다면, 그제서야 이미 1에서 0으로 리셋한 페이지 중 하나를 제거한다.
    • FIFO에 비해 자주 사용되는 페이지의 잔류 확률을 높여 성능을 개선한다.
day 4: 프로세스 동기화와 데드락

동시성(Concurrency)의 개념​

현대 운영체제에서는 동시에 여러 프로세스나 스레드가 실행되는 환경이 일반적이다. CPU가 하나라도 시분할 시스템을 통해 여러 작업이 마치 동시에 실행되는 것처럼 보이게 할 수 있으며, 멀티코어 환경에서는 실제로 여러 스레드가 물리적으로 동시에 실행되기도 한다.

이런 동시성 환경에서 여러 스레드가 같은 메모리 영역이나 공유 자원에 동시 접근하면 예측 불가능한 결과가 발생할 수 있다. 이런 문제가 바로 경쟁 조건(Race Condition) 이다.

경쟁 조건(Race Condition)​

두 개 이상의 스레드나 프로세스가 공유 자원에 접근할 때, 접근 순서나 시점에 따라 결과가 달라지는 상황을 경쟁 조건이라 한다. 예를 들어, 은행 계좌 잔고를 갱신하는 두 개의 스레드가 동시에 작동할 때, 한 스레드의 업데이트가 다른 스레드의 업데이트와 충돌하면 잘못된 최종 잔고가 기록될 수 있다.

경쟁 조건을 제거하기 위해서는 접근 순서를 적절히 제어하는 동기화(Synchronization) 메커니즘이 필요하다.

임계구역(Critical Section) 문제​

여러 스레드가 동시에 접근하면 안 되는 코드 영역을 임계구역이라 한다. 임계구역 문제의 해결책은 다음 세 가지 조건을 만족하는 프로토콜을 디자인하는 것이다.

  1. 상호 배제(Mutual Exclusion): 한 번에 하나의 스레드만 임계구역에 들어갈 수 있어야 한다.
  2. 진행(Progress): 임계구역에 들어가려는 스레드가 없으면, 임계구역 진입을 무한정 지연하지 않아야 한다.
  3. 한정 대기(Bounded Waiting): 특정 스레드가 임계구역 진입을 너무 오래 대기하지 않도록 보장해야 한다.

이러한 조건을 만족하기 위해 다양한 동기화 도구가 개발되었다.

2. 동기화 기법​

락(Lock)과 뮤텍스(Mutex)​

뮤텍스(Mutex) 는 상호 배제를 위한 가장 기본적인 도구이다. 뮤텍스는 오직 하나의 스레드만 소유할 수 있는 잠금(락)을 제공하고, 다른 스레드는 이미 누군가가 뮤텍스를 획득한 경우 대기하게 된다. 뮤텍스를 사용하면 동시에 공유 자원에 접근하는 스레드를 하나로 제한할 수 있다.

  • 획득(Acquire): 잠겨있지 않은 뮤텍스를 얻으면 해당 스레드는 임계구역에 들어갈 수 있다.
  • 해제(Release): 임계구역을 다 쓴 후 뮤텍스를 해제하면 다른 대기 중인 스레드가 접근할 수 있다.

세마포어(Semaphore)​

세마포어(Semaphore) 는 정수형 카운터를 통해 접근 가능한 자원의 개수를 제어하는 동기화 도구다. 뮤텍스는 이진(0 또는 1) 형태로 동작하는 세마포어로 볼 수 있다. 세마포어는 프로세스나 스레드가 P(또는 wait) 연산을 통해 자원 획득을 시도하고, V(또는 signal) 연산을 통해 자원을 반환한다.

  • 카운팅 세마포어: N개의 자원이 있을 때, 0 이상 N 이하의 값을 갖는다.
  • 이진 세마포어(뮤텍스): 값이 0 또는 1만 가능하며, 뮤텍스 용도로 사용.

모니터(Monitor)​

모니터(Monitor) 는 동기화 문제를 추상화한 고급 언어 차원의 동기화 메커니즘이다. 모니터 내에서만 접근 가능한 공유 자원과 함수를 정의하고, 진입 시 자동으로 상호 배제가 보장되도록 언어 차원에서 제공한다. 모니터는 조건변수(Condition Variable)를 통해 스레드 간 신호 전달도 지원한다.

조건변수(Condition Variable)​

모니터 내부에서 사용되는 조건변수는 특정 조건을 만족할 때까지 스레드를 대기시켰다가, 조건을 만족하면 대기 중인 스레드에게 신호를 보내 재개하는 기법을 제공한다. wait() 연산으로 조건이 충족될 때까지 스레드를 재우고, signal() 연산으로 조건을 만족시켜 대기 스레드를 깨운다.

3. 데드락(Deadlock)​

데드락의 정의​

**데드락(Deadlock)**은 두 개 이상의 프로세스나 스레드가 서로가 가진 자원을 기다리며 무한정 대기하는 상황이다. 결과적으로 시스템은 교착 상태에 빠져 어떤 것도 전진하지 못하게 된다.

데드락 발생 조건 (Coffman’s Condition)​

데드락이 발생하기 위해서는 다음 네 가지 조건이 동시에 만족해야 한다.

  1. 상호 배제(Mutual Exclusion): 자원은 한 번에 한 프로세스만 사용할 수 있어야 한다.
  2. 점유 대기(Hold and Wait): 최소 한 개 이상의 자원을 점유한 상태에서 다른 자원을 추가로 기다린다.
  3. 비선점(Non-Preemption): 자원을 점유한 프로세스가 그 자원을 강제로 빼앗기지 않는다.
  4. 순환 대기(Circular Wait): 프로세스들이 자원을 서로 순환 형태로 기다린다. 예를 들어 A는 B가 가진 자원을 기다리고, B는 C가 가진 자원을 기다리며, C는 다시 A가 가진 자원을 기다리는 순환 고리가 형성된다.

이 조건들 중 하나라도 깨뜨리면 데드락은 발생하지 않는다.

데드락 처리 기법​

데드락을 처리하기 위한 전통적인 방법은 다음과 같다.

  1. 데드락 예방(Prevention): 데드락 발생 조건 중 하나를 아예 사전에 없애버린다. 예를 들어, 자원을 요청할 때마다 한 번에 모두 요구하게 하거나, 항상 특정 순서에 따라 자원을 획득하도록 하여 순환대기를 막는다.

  2. 데드락 회피(Avoidance): 프로세스들이 자원을 요청할 때, 시스템은 데드락에 빠지지 않는 안전 상태(Safe State)인지 검증한 뒤 자원을 할당한다. Banker's Algorithm과 같은 알고리즘을 통해 데드락을 회피할 수 있다.

  3. 데드락 탐지(Detection) 와 회복(Recovery): 데드락을 허용한 뒤, 주기적으로 데드락이 발생했는지 검사하고, 데드락 상태를 확인하면 프로세스 중 일부를 중단하거나 자원을 강제 회수하여 회복한다.

  4. 무시(Ignore): 일부 시스템(예: 데스크톱 OS)은 데드락이 매우 드물게 발생한다고 가정하고, 발생 시 사용자가 강제 종료하는 식으로 무시하기도 한다.

4. 요약​

  • 동시성은 현대 운영체제에서 필수적이지만, 경쟁 조건을 야기한다.
  • 임계구역 문제 해결을 위해 뮤텍스, 세마포어, 모니터 등 다양한 동기화 도구를 활용한다.
  • 데드락은 자원 대기 상태가 순환 구조를 이루며 발생하는 문제로, 예방, 회피, 탐지 및 회복 전략을 통해 다룰 수 있다.
day 5: 파일 시스템

파일과 디렉토리의 개념​

운영체제는 보조기억장치(예: HDD, SSD) 위에 저장된 데이터를 효율적이고 안전하게 관리하기 위해 파일 시스템을 사용한다. 파일(File)은 연속된 바이트(byte) 집합으로, 프로그램이나 사용자 데이터를 논리적으로 묶은 단위이다. 디렉토리(Directory)는 파일을 계층적으로 정리하는 구조물로, 파일을 식별하고 조직화하는데 도움을 준다.

디렉토리 구조 (Directory Structure)​

  • 단일 디렉토리 구조(Single-Level Directory): 모든 파일이 하나의 디렉토리에 모여있는 단순 구조이다. 파일명이 충돌하기 쉽고, 대규모 시스템에서는 관리가 어렵다.
  • 2단계 디렉토리 구조(Two-Level Directory): 사용자별로 고유한 디렉토리를 제공한다. 다른 사용자의 파일명과 충돌을 방지할 수 있지만, 계층화된 조직이 어렵다.
  • 트리 구조 디렉토리(Tree-Structured Directory): 가장 일반적이며, 디렉토리 안에 다른 디렉토리를 포함할 수 있어 계층적 구조를 형성한다. 검색, 관리, 분류가 용이하다.
  • 비순환 그래프(ACYCLIC Graph) 및 일반 그래프 디렉토리 구조: 파일이나 디렉토리를 여러 디렉토리에서 참조할 수 있지만, 사이클이 형성되지 않도록 관리해야 한다.

Inode (아이노드) 구조​

유닉스 계열 파일 시스템은 Inode라는 자료구조를 사용한다. Inode는 파일에 대한 메타데이터(파일 크기, 소유자, 그룹, 접근 권한, 파일 생성 및 수정 시간, 실제 데이터 블록의 위치)를 담고 있다. 파일명은 디렉토리에 저장되며, 디렉토리는 파일명과 Inode 번호를 매핑한다.

Inode를 통해 파일의 물리적 위치(블록 정보)를 알아낼 수 있으므로, 디렉토리 검색 시 파일명을 Inode 번호로 변환한 뒤, Inode를 참조해 실제 데이터에 접근한다. 이를 통해 파일명과 데이터 배치를 분리하여 효율적인 파일 관리와 빠른 검색을 가능하게 한다.

파일 접근 방식​

파일 접근 방식은 파일 내 데이터에 접근하는 방법으로 나뉜다.

  1. 순차 접근(Sequential Access)
    파일을 순서대로 읽거나 쓰는 방식이다. 초기 테이프 기반 시스템이나 단순 텍스트 파일 처리에 많이 사용된다. 순차 접근은 연속적인 처리에는 단순하고 효율적이지만, 특정 위치로 곧바로 이동할 수 없어 임의 접근에 비효율적이다.

  2. 직접 접근(Direct Access)
    파일을 레코드 단위로 나누고, 원하는 레코드 번호를 직접 지정하여 접근한다. 디스크와 같이 블록 단위 접근이 가능한 매체에서 주로 사용되며, 특정 위치로 바로 점프할 수 있어 검색에 유리하다.

  3. 인덱스 접근(Indexed Access)
    별도의 인덱스 블록을 두어, 인덱스가 레코드나 블록의 위치 정보를 제공한다. 특정 데이터로 빠르게 점프할 수 있으며, 순차 접근과 직접 접근의 장점을 결합한 구조다. 다만 인덱스를 관리하기 위한 추가적 공간과 관리 오버헤드가 발생한다.

디스크 스케줄링(Disk Scheduling)​

디스크 스케줄링은 디스크 헤드가 어떤 순서로 블록을 읽고 쓸지 결정하는 알고리즘이다. 디스크는 물리적으로 회전하는 플래터와 이동하는 헤드로 구성되어 있어, 접근 순서에 따라 디스크 입출력 성능이 크게 달라진다.

  1. FCFS (First-Come, First-Served)
    요청이 들어온 순서대로 디스크 요청을 처리하는 가장 단순한 방식이다. 구현이 쉽지만, 디스크 헤드가 디스크 전체를 무작위로 왕복할 수 있어 대기 시간이 비효율적으로 길어질 수 있다.

  2. SSTF (Shortest Seek Time First)
    현재 헤드 위치에서 가장 가까운 요청을 우선 처리한다. 헤드 이동 거리를 최소화하여 대기 시간을 개선할 수 있지만, 특정 영역에 집중된 요청이 있을 경우 다른 요청이 기아 상태(Starvation)에 빠질 수 있다.

  3. SCAN (전방향 스캔) 알고리즘
    전형적으로 ‘전동기 엘리베이터’ 알고리즘이라고도 불리며, 헤드가 디스크 한쪽 끝에서 다른 쪽 끝까지 이동하며 만나는 요청을 처리한다. 끝에 도달하면 반대 방향으로 이동하며 요청을 처리한다. 이렇게 하면 SSTF보다 기아 현상을 줄일 수 있다. 변형 알고리즘으로 C-SCAN, LOOK, C-LOOK 등이 있다.

  • LOOK 알고리즘: SCAN과 유사하지만, 양 끝까지 가지 않고 더 이상 처리할 요청이 없는 지점에서 방향을 바꾼다.
  • C-SCAN(Circular-SCAN): 한 방향으로만 이동하며, 끝에 도달하면 가장 처음 트랙으로 순간이동(혹은 빠른 이동)한다. 이렇게 하면 접근 시간 편차를 균등화할 수 있다.