혼자 공부하는 컴퓨터구조 + 운영체제 (2)

개요

<개발자를 위한 컴퓨터공학 1: 혼자 공부하는 컴퓨터구조 + 운영체제>

책과 함께 인프런 강의를 수강하며 공부한 내용을 정리하고자 한다. 책과 강의를 이용하면 더욱 자세한 설명과 이해가 가능하다.

• 인프런 강의 링크(무료)
• 책 링크(알라딘)

이번 글은 "챕터9~15"까지 운영체제 에 대해서 공부한 내용을 정리했다.

앞선 "챕터1~8까지 컴퓨터구조" 를 정리한 내용은 다음 링크를 참고바란다.

키워드 정리

챕터9. 운영체제

• 운영체제(OS), 시스템자원(system resource), 커널(kernel), 이중모드(dual mode), 사용자모드(user mode), 커널모드(kernel mode), 시스템호출(system call)

챕터10. 프로세스와 스레드

• 프로세스(process), 프로세스제어블록(PCB; Process Control Block), 문맥교환(context switch), 코드영역/텍스트영역(code/text segment), 데이터영역(data segment), 힙영역(heap segment), 스택영역(stack segment), 가비지컬렉션(garbage collection), 메모리누수(memory leak), 프로세스 상태(process state) : new/ready/running/blocked/terminated, 부모/자식 프로세스(parent/child process), fork-exec, 스레드(thread)

챕터11. CPU 스케줄링

• CPU스케줄링(CPU scheduling), 스케줄링큐(scheduling queue), 선점형/비선점형 스케줄링(preemptive/non-preemptive scheduling), CPU 스케줄링 알고리즘 : 선입선처리, 최단작업우선, 라운드 로빈, 최소 잔여시간 우선, 우선순위, 다단계 큐, 다단계 피드백 큐, 기아현상(starvation), 에이징(aging)기법

챕터12. 프로세스 동기화

• 동기화(synchronization), 공유자원(shared resource), 임계구역(critical section), 레이스컨디션(race condition), 상호배제(mutual exclusion), 진행(progress), 유한대기(bounded waiting), 뮤텍스 락(Mutex lock; MUTual Exclusion lock), 세마포(semaphore), 모니터(monitor)

챕터13. 교착 상태

• 교착상태(deadlock), 자원할당그래프(resource-allocation graph), 교착상태예방 : 상호배제(mutual exclusion), 점유와 대기(hold and wait), 비선점(non-preemptive), 원형대기(circular wait), 교착상태회피 : 안전순서열, 안전상태, 불안정상태, 교착 상태 검출 후 회복, 교착 상태 무시

챕터14. 가상 메모리

• 연속 메모리 할당, 스와핑(swapping), 스왑영역(swap space), 스왑-아웃/인(swap-out/in), 메모리 할당 : 최초 적합(first-fit), 최적 적합(best-fit), 최악 적합(worst-fit), 외부 단편화(external fragmentation), 메모리 압축(compaction), 가상메모리(virtual memory), 페이징(paging), 페이지(page), 프레임(frame), 페이지-아웃/인(page-out/in), 페이지테이블(page table), 내부 단편화(internal fragmentation), 페이지 테이블 베이스 레지스터(PTBR; Page Table Base Register), TLB(Translation Lookaside Buffer), TLB 히트/미스, 페이지 테이블 엔트리(PTE; Page Table Entry) : 유효비트(valid bit), 보호비트(protection bit), 참조비트(reference bit) 수정비트(modified bit, dirty bit), 계층적 페이징(hierarchical paging), 다단계 페이지 테이블(multilevel page table), Outer 페이지테이블, 요구페이징(demand paging), 순수요구페이징(pure demand paging), 페이지교체알고리즘(Page Replacement Algorithm) : FIFO/최적(optimal)/LRU(Least-Recently-Used), 페이지폴트(page fault), 스래싱(thrashing), 프레임할당방식 : 균등(equal)/비례(proportional)/작업집합모델(working set model)/페이지폴트빈도기반모델(PFF; Page-Fault Frequency)

챕터15. 파일 시스템

파일시스템(FS; file system), 파일(file), 디렉터리(directory), 폴더(folder), 디렉터리 엔트리(directory entry), 디렉터리 테이블(directory table), 경로(path), 파티셔닝(partitioning), 파티션(partition), 포매팅(formatting), 블록(block), 연속할당, 불연속할당 : 연결/색인 할당, FAT 파일시스템(File Allocation Table FS), 유닉스 파일시스템, i-node

내용

Chpater 09. 운영체제 시작하기

09-1) 운영체제를 알아야 하는 이유

운영체제(Operating System) 개요

• 프로그램에 필요한 시스템 자원을 할당하고, 프로그램을 올바르게 실행하도록 돕는 프로그램을 위한 프로그램. 
  • 시스템 자원 : CPU, 메모리, 보조기억장치, 입출력장치 등등
• 운영체제도 프로그램이므로 메모리에 할당됨
  • 이 때, 특별히 커널 영역(kernel space)에 할당되고, 그 외 응용 프로그램은 사용자 영역(user space)에 할당됨
• 배워두면 하드웨어와 프로그램을 더 깊이 이해하고, 문제 해결의 실마리를 찾을 수 있음

09-2) 운영체제의 큰 그림

커널(Kernel)

• 운영체제가 제공하는 기능 중 가장 핵심적인 서비스를 담당하는 부분(참고로 운영체제 프로그램은 매우 큼)
  • 그렇다면 운영체제에는 해당하지만, 커널에는 해당하지 않는 것은? UI, CLI 등등

이중모드(dual mode)

• CPU가 명령어를 실행하는 모드를 2가지로 나눠 시스템 자원을 운영체제를 통해서만 접근 가능하도록 한 것
• (1) 사용자모드(user mode)
  • 운영체제 서비스를 제공받을 수 없는 실행모드. 일반적인 응용 프로그램은 기본적으로 사용자 모드로 실행됨
• (2) 커널모드(kernel model)
  • 운영체제 서비스를 제공받을 수 있는 실행모드. 자원 접근 가능
• 참고) 가상머신(VM) 프로그램으로 인해 하이퍼바이저모드(hypervisor mode)도 존재함
  • 가상머신은 응용 프로그램으로 사용자 모드이고, 그 위의 운영체제 프로그램과 응용 프로그램 모두 사용자 모드임
  • 따라서, 가상화를 지원하는 CPU는 하이퍼바이저모드를 가지고 있고, 이를 통해 VM 위의 응용 프로그램이 자원을 이용할 수 있게함

시스템 호출(system call)

• 사용자 모드로 실행되는 프로그램에서 운영체제 서비스를 제공받기위해 운영체제에게 커널 모드로의 전환을 요청하는 것
• 정확히 이야기하면 S/W적인 인터럽트로 아래 예시 참고
  • (1) 응용프로그램에서 하드 디스크에 데이터를 저장하는 시스템 호출을 발생시켜 커널 모드로 전환
  • (2) 운영체제의 '하드 디스크에 데이터를 저장하는 코드'를 실행하여 하드디스크에 접근
  • (3) 하드디스크 접근이 종료되면 다시 사용자 모드로 복귀하여 실행을 계속함
• 따라서, 응용 프로그램은 실행 과정에서 시스템 호출을 자주 발생시키고, 사용자모드와 커널모드를 자주 오가며 실행됨
• 종류
  • 프로세스관리 : fork(), execve(), exit(), waitpid()
  • 파일관리 : open(), close(), read(), write(), stat()
  • 디렉토리 관리 : chdir(), mkdir(), rmdir()
  • 파일시스템 관리 : mount(), umount()

운영체제 서비스 종류 개요

• (1) 프로세스 관리
  • 프로세스(process) = 실행 중인 프로그램. 동시에 수많은 프로세스들이 실행됨
  • 프로세스들의 '생성/실행/삭제'를 잘 관리해야 함
  • 앞으로 배울 것
    • 프로세스와 스레드
    • 프로세스 동기화
    • 교착 상태
• (2) 자원 접근 및 할당
  • CPU : CPU스케줄링 - 어떤 프로세스를 먼저, 얼마나 오래 실행할까?
  • 메모리 : 페이징, 스와핑
  • 입출력장치 : 인터럽트 서비스 루틴
• (3) 파일 시스템 관리
  • 파일 : 관련된 정보를 묶은 것
  • 폴더 : 파일들을 묶은 것

Chpater 10. 프로세스와 스레드

10-1) 프로세스 개요

프로세스(process)

• 포그라운드 프로세스(foreground process) : 사용자가 볼 수 있는 공간에서 실행되는 프로세스
• 백그라운드 프로세스(background process) : 사용자가 볼 수 없는 공간에서 실행되는 프로세스로 사용자와 상효작용하지 않고 정해진 일만 수행함
• 백그라운드 프로세스 중 사용자와 직접 상호작용이 가능한 경우 : 데몬(daemon), 서비스(service)

프로세스 제어 블록(PCB; Process Control Block)

• 프로세스 관련정보를 저장하는 자료구조
  • 프로세스는 돌아가며 한정된 시간만큼 CPU 이용
  • 타이머 인터럽트가 발생하면 다음 프로세스에 CPU 자원을 양보하게 됨
  • 이 때, 번갈아가며 수행되는 프로세스 자료구조가 PCB인 것
  • 프로세스 생성 시 커널 영역에 생성되고, 종료 시 폐기
• PCB의 대표 정보(운영체제마다 좀 다름)
  • (1) 프로세스ID (=PID)
    • 특정 프로세스를 식별하기 위한 고유한 번호
  • (2) 레지스터 값
    • 프로세스가 실행하며 사용했던 프로그램카운터, 스택포인터 등의 값
  • (3) 프로세스 상태
    • 입출력 장치를 사용하기 위해 기다리는 상태, CPU를 사용하기 위해 기다리는 상태, CPU를 이용하는 상태 등등
  • (4) CPU 스케줄링 정보
    • 프로세스가 언제, 어떤 순서로 CPU를 할당받을지에 대한 정보
  • (5) 메모리 정보
    • 프로세스가 어느 주소에 저장되어 있는지에 대한 정보
    • 페이지 테이블 정보
  • (6) 사용한 파일과 입출력장치 정보
    • 할당된 입출력장치, 사용 중인 파일 정보

문맥 교환(context switch)

• 기존 실행 중인 프로세스 문맥(context)을 백업하고, 새로운 프로세스 실행을 위한 문맥을 복구하는 과정
• 여러 프로세스가 빠르게 번갈아가며 실행되는 원리

프로세스의 메모리 영역 중 사용자 영역

• 정적 할당 영역 (크기 고정)
  
  • (1) 코드 영역(code segment) = 텍스트 영역(text segment)
    • 기계어로 이루어진 명령어가 저장되는 영역
    • 읽기 전용 공간으로 쓰기가 금지되어 있음(데이터가 아닌 CPU가 실행할 명령이므로)
  • (2) 데이터 영역(data segment)
    • 전역변수(global variable)와 같이 프로그램이 실행되는 동안 유지할 데이터가 저장되는 영역
• 동적 할당 영역 (크기 가변)
  • (3) 힙 영역(heap segment)
    • 프로그래머가 직접 할당할 수 있는 저장공간
    • 가비지컬렉션(garbage collection) : 할당했다면, 나중에는 반환을 해야하는데, 요즘 프로그래밍 언어 중에는 알아서 반환을 해주는 기능
    • 메모리누수(memory leak) : 할당 후, 반환하지 않아 메모리 낭비가 일어나는 것
    • 힙 영역은 동적 할당 영역으로 낮은 주소에서 높은 주소로 할당함(스택과 겹치지 않게)
  • (4) 스택 영역(stack segment)
    • 데이터를 일시적으로 저장하는 영역
    • 매개변수, 지역변수 등등
    • 스택 영역은 동적 할당 영역으로 높은 주소에서 낮은 주소로 할당함(힙과 겹치지 않게)
• 위의 4가지 외에도 다른 영역들도 있긴 함

10-2) 프로세스 상태와 계층 구조

프로세스 상태(운영체제마다 조금씩은 다름)

출처 : https://eunhyejung.github.io/os/2018/07/08/operatingsystem-study06.html

• (1) 생성 상태(new state)
  • 메모리에 적재되어 PCB를 할당 받은 상태지만, 아직 OS에게 승인받지 못한 상태
• (2) 준비 상태(ready state)
  • 당장이라도 CPU를 할당 받아 실행할 수 있으나, 자신의 차례가 아니기에 기다리는 상태
  • 디스패치(dispatch) : 실행 상태로 접어드는 것
• (3) 실행 상태(running state)
  • CPU를 할당받아 실행 중인 상태
  • 타이머 인터럽트 발생 시, 준비 상태로 변환
  • 입출력 요청 시, 입출력 작업이 끝날 때까지 대기 상태로 변환
• (4) 대기 상태(blocked state)
  • 프로세스가 실행 도중 입출력장치를 사용하는 경우
  • 입출력 상태가 끝나면 (입출력 완료 인터럽트를 받으면) 준비 상태로 변환
• (5) 종료 상태(terminated state)
  • 프로세스가 종료되어 PCB, 프로세스의 메모리 영역 정리

프로세스 계층구조

• 프로세스 실행 도중 시스템 호출을 통해 다른 프로세스 생성 가능
  • 부모 프로세스(parent process) : 새 프로세스를 생성한 프로세스
  • 자식 프로세스(child process) : 부모 프로세스에 의해 생성된 프로세스
• 특징
  • 부모 프로세스와 자식 프로세스는 각기 다른 PID를 가짐
  • 일부 운영체제에서는 자식 프로세스 PCB에 부모 프로세스의 PID(PPID; Parent PID)를 명시하기도 함
  • 자식 프로세스도 또 자식 프로세스를 낳을 수 있음. 따라서, 계층적일 수 있음

프로세스 생성기법 : fork-exec

• (1) 부모 프로세스는 fork 시스템 호출을 통해 자신의 복사본을 자식 프로세스로 생성
  • fork 시스템 호출
    • 복사본을 생성
    • 부모 프로세스의 자원 상속
• (2) 자식 프로세스는 exec 시스템 호출을 통해 자신의 메모리 공간을 다른 프로그램으로 교체
  • exec 시스템 호출
    • 메모리 공간을 새로운 프로그램으로 덮어쓰기
    • 코드/데이터 영역은 실행할 프로그램으로 바뀌고, 나머지 영역은 초기화
• 예시) bash셸에서 ls 명령어 실행
  • bash 셸 프로세스는 fork()를 통해 자신과 동일한 자식 프로세스를 생성
  • 자식 프로세스는 exec()을 통해 ls 명령어를 실행하기 위한 프로세스로 전환되면서 메모리 공간을 변경

10-3) (S/W적인) 스레드

(S/W적인) 스레드(Thread)

• 프로세스를 구성하는 실행 흐름의 단위
• 하나의 프로세스는 하나 이상의 스레드를 가짐
• 종류
  • 단일 스레드 프로세스 : 실행 흐름이 하나인 프로세스
  • 멀티 스레드 프로세스 : 프로세스를 이루는 여러 명령어가 동시 실행이 가능함
    • 예시) 웹 브라우저 프로세스 - 화면 출력 스레드, 입력 스레드, 검색 스레드
• 구성 요소
  • 스레드ID, 레지스터값(프로그램 카운터 등등), 스택
  • 실행에 필요한 최소한의 정보만을 가짐
  • 하지만, 프로세스를 이루는 모든 스레드들은 프로세스의 자원을 공유하면서 실행됨! (중요!!)

멀티프로세스와 멀티스레드

• 동일한 작업을 수행하는 단일 스레드 프로세스 여러개 vs 하나의 프로세스를 여러 스레드로 실행? 어떤 차이?
  • 프로세스끼리는 기본적으로 서로 자원을 공유하지 않지만, 스레드는 서로 자원을 공유함
  • 그리고 프로세스는 여러 PCB를 가진다면, 스레드는 하나의 PCB를 가지고 그 내에서 여러 스레드ID를 가짐
  • 따라서, 스레드는 협력과 통신에 유리하지만 하나의 스레드가 문제가 생기면 다른 스레드에도 영향이 있을 수 있음
• 참고로, 프로세스 간 통신(IPC; Inter Process Communication)으로 자원을 공유할 수도 있긴 함
  • 파일, 공유메모리, 소켓, 파이프 등등

Chpater 11. CPU 스케줄링

11-1) CPU 스케줄링 개요

CPU 스케줄링(CPU scheduling)

• 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
• 프로세스 우선순위(priority)가 다르므로, 순서대로 처리하는 것은 비합리적
  • 예시로, 입출력 집중 프로세스(I/O bound process) > CPU 집중 프로세스(CPU bound process)
  • 어차피 입출력에는 시간이 많이 소요되므로 빠르게 처리해주고 CPU에 집중하는 것이 합리적
  • 참고로, CPU를 이용하는 작업을 CPU버스트(CPU burst), 입출력 장치를 기다리는 작업을 입출력 버스트(I/O burst)라고 함
  • 프로세스는 일반적으로 CPU버스트와 입출력 버스트를 반복하며 실행되고, 각각의 버스트가 많은 프로세스를 'OOO 집중 프로세스'라 부름

스케줄링 큐(scheduling queue)

• 운영체제가 관리하는 각 자원별로 이를 사용하고 싶은 프로세스를 줄 세우는 스케줄링 큐를 만들어 운영함(FIFO 아님)
  • (1) 준비 큐(ready queue) : CPU를 이용하기 위한 스케줄링 큐
  • (2) 대기 큐(waiting queue) : 입출력장치를 이용하기 위한 스케줄링 큐
    • 같은 장치를 요구한 프로세스들은 같은 큐에서 대기
    • 예시) 프린터 대기 큐, 프린터 대기 큐, CD-ROW 대기 큐 등등

선점형/비선점형 스케줄링

• (1) 선점형 스케줄링(preemptive scheduling)
  • 하나의 프로세스가 CPU를 이용하고 있더라도, 다른 프로세스가 선점할 수 있음
  • 장점 : 한 프로세스의 독점을 막고, 프로세스들에 골고루 자원을 배분할 수 있음
  • 단점 : 문맥 교환 과정에서 오버헤드가 발생함
• (2) 비선점형 스케줄링(non-preemptive scheduling)
  • 한 프로세스가 종료되거나 대기상태로 가기전 까지 다른 프로세스가 끼어들 수 없음
  • 장점 : 문맥 교환에서 발생하는 오버헤드가 적음
  • 단점 : 모든 프로세스가 자원을 골고루 이용하기는 어려움

11-2) CPU 스케줄링 알고리즘 (미완성)

1. 선입 선처리 스케줄링
2. 최단 작업 우선 스케줄링
3. 라운드 로빈 스케줄링
4. 최소 잔여시간 우선 스케줄링
5. 우선순위 스케줄링 : 기아현상(starvation), 에이징(aging) 기법
6. 다단계 큐 스케줄링(Multilevel queue)
7. 다단계 피드백 큐 스케줄링(Multilevel feedback queue)

Chpater 12. 프로세스 동기화

12-1) 동기화란

동기화(synchronization)

• 동시에 실행되는 프로세스들은 서로 협력하며 영향을 주고받음
• 이 때, 자원의 일관성을 보장해야하고, 프로세스들의 수행시기를 맞춰야 함
  • 실행 순서 제어 : 프로세스를 올바른 순서대로 실행하기
  • 상호 배제 : 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 할 것
• (1) 실행순서 제어
  • Reader Writer Problem
    • 실행의 순서가 있음!
    • Writer : Book.txt 파일에 값을 저장하는 프로세스
    • Reader : Book.txt 파일에 저장된 값을 읽어들이는 프로세스
    • 즉, Reader 는 "Book.txt 값이 존재한다"는 특정 조건이 만족되어야만 실행 가능
• (2) 상호 배제(mutual exclusion)
  • Bank Account Problem
    • 공유가 불가능한 자원의 동시 사용을 피하기 위한 동기화
    • 잔액 10만원.
    • 프로세스 A : 잔액에 2만원을 추가하는 프로세스(읽기 - 잔액 + 2만원 계산 - 저장)
    • 프로세스 B : 잔액에 5만원을 추가하는 프로세스(읽기 - 잔액 + 5만원 계산 - 저장)
    • 즉, 한 번에 하나의 프로세스만 접근해야 하는 자원에 동시 접근을 피하기 위함
    • "잔액"이라는 자원은 하나의 프로세스가 이용하다고 다른 프로세스로 문맥교환이 일어나도... 기다려야함!
  • 생산자와 소비자 문제(Producer & Consumer Problem)
    • 물건을 계속해서 생산하는 생산자(producer)
    • 물건을 계속해서 소비하는 소비자(consumer)
    • "총합" 변수 공유
    • 동기화가 되지 않았기 때문에 발생한 문제로, 동시에 접근해서는 안 되는 자원("총합")에 동시에 접근해서 발생한 문제
    • 생성자() {버퍼에 데이터 삽입; '총합' 변수 1 증가}, 소비자() {버퍼에 데이터 빼내기; '총합' 변수 1 감소}

공유 자원과 임계구역

• (1) 공유 자원(shared resource) : 여러 프로세스 or 스레드가 공유하는 자원
  • 전역 변수 ,파일, 입출력장치, 보조기억장치
• (2) 임계 구역(critical section) : 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역
  • 위의 예시에서 "총합", "잔액" 변수
• (3) 레이스 컨디션(race condition) : 임계 구역에 동시에 접근하면 자원의 일관성이 깨질 수 있는 상태
  • 따라서, 임계 구역에 진입하고자 하면, 진입한 프로세스 이외에는 대기해야 함
• 왜 이런 일이 발생하는지?
  • 소스코드는 한 줄이어도, 이는 기계어로 번역하면 여러 줄이 발생가능하고
    이러한 기계어 간의 문맥교환으로 인해 레이스 컨디션이 발생할 수 있음

운영체제가 임계구역 문제를 해결하는 3가지 원칙

• (1) 상호배제(mutual exclusion)
  • 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 들어올 수 없음
• (2) 진행(progress)
  • 임계 구역에 어떤 프로세스도 진입하지 않았다면 진입하고자 하는 프로세스는 들어갈 수 있어야 함
• (3) 유한대기(bounded waiting)
  • 한 프로세스가 임계 구역에 진입하고 싶다면, 언젠가는 임계 구역에 들어올 수 있어야 함 (즉, 무한정 대기는 안 됨)

12-2) 동기화 기법

뮤텍스 락(Mutex lock; MUTual EXclusion lock)

• 상호 배제를 위한 동기화 도구. 일종의 자물쇠 기능
• 전역 변수 1개, 함수 2개로 구현
  • 자물쇠 역할 : 프로세스들이 공유하는 전역 변수 lock
  • 임계 구역을 잠그는 역할 : acquire 함수
  • 임계 구역의 잠금을 해제하는 역할 : release 함수
    

    lock = false
    acquire(){
        while (lock == true); /* 만약, 임계 구역이 잠겨 있다면, 반복적으로 확인 */
        lock = true; /* 만약, 임계 구역이 잠겨 있지 않다면 임계 구역 잠금 */
    }
    release(){
        lock = false; /* 임계 구역 잡업이 끝나면 잠금 해제 */
    }
    
    /* 실제 사용 예시 */
    acquire()
    // 임계구역
    release()

• acquire()
  • 프로세스가 임계 구역에 진입하기 전에 호출
  • 임계 구역이 잠겨 있다면, 열릴 때 까지 임계 구역을 반복적으로 확인
  • 임계 구역이 열려 있다면, 임계 구역을 잠그기
  • while (lock == true) : 바쁜 대기(busy waiting) - 반복적으로 무한히 반복하면서 확인하므로 그렇게 좋은 방식은 아님!
• release()
  • 임계 구역에서의 작업이 끝나고 호출
  • 현재 잠긴 임계 구역을 열기

세마포(semaphore)-상호배제

• 좀 더 일반화된 방식의 동기화도구로 공유 자원이 여러 개 있는 경우에도 적용 가능
• 종류 : 이진 세마포(뮤텍스와 매우 유사함), 카운팅 세마포 -> 아래는 이걸로 설명할 예정
• 전역 변수 1개, 함수 2개
  • 임계 구역에 진입할 수 있는 프로세스 개수(사용 가능한 공유 자원의 개수)를 나타내는 전역변수 S
  • 임계 구역에 들어가도 좋은지, 기다려야 할지를 알려주는 wait함수
  • 임계 구역 앞에서 기다리는 프로세스에 '가도 된다'는 신호를 주는 signal함수
  • 코드(busy waiting)
    

    wait(){
        while (S <=0); /* 만일, 임계 구역에 진입할 수 있는 프로세스 개수가 0 이하라면 반복적으로 확인 */
        S-- /* 임계 구역에 진입 후 프로세스 개수가 하나 이상이면 S를 1 감소시키고 임계 구역 진입 */
    }
    signal(){
        S++ /* 임계 구역에서의 작업을 마친 뒤 S를 1 증가시킴 */
    }
    
    /* 실제 사용 예시 */
    wait()
    // 임계구역
    signal()

• 여전히, busy waiting(CPU싸이클 낭비) 이 있다보니 좀 더 현명한 방법을 사용함
  • 사용할 수 있는 자원이 없을 경우 PCB를 대기큐에 넣어 "대기 상태"로 만듦
  • 사용할 수 있는 자원이 생기면, 대기 큐의 프로세스 준비 큐에 넣어 "준비 상태"로 만듦
  • 코드(해결)

    wait(){
        S--;
        if (S < 0){
            add this process to Queue       /* 해당 프로세스 PCB를 대기 큐에 삽입 */
            sleep()                         /* 대기 상태로 접어듦 */
        }
    }
    signal(){
        S++;
        if (S <= 0){
            remove a process p from Queue   /* 대기 큐에 있는 프로세스 p를 제거 */
            wakeup(p)                       /* 프로세스p를 대기 상태에서 준비상태로 만듦 */
        }
    }

• 상호배제 뿐만 아니라 "실행 순서 동기화"에도 사용 가능
  • 세마포의 전역변수 S를 0으로 두고
  • 먼저 실행할 프로세스의 위에 signal() 함수. 다음에 실행할 프로세스 앞에 wait()함수를 붙이면 됨
  • 코드 (아래 P1, P2 2개는 순서가 바뀌어도 반드시 P1부터 시작됨)

    S = 0
    /* P1 */
    //임계구역
    signal()
    
    /* P2 */
    wait()
    //임계구역

모니터(monitor)

• 세마포는 훌륭한 프로세스 동기화 도구이지만, 매번 함수를 명시하는 것은 번거롭고 실수하기 좋음
• 따라서, 사용자(개발자)가 다루기에 편한 동기화 도구가 필요함
• 상호 배제를 위한 동기화
  • 인터페이스를 위한 큐
  • 공유 자원에 접근하고자 하는 프로세스를 인터페이스를 위한 큐에 삽임
  • 큐에 삽입된 순서대로 (한 번에 하나의 프로세스만) 공유 자원 이용
  • 공유 자원과 공유 자원에 접근하기 위한 인터페이스(통로)를 묶어서 관리함. 즉, 공유자원은 반드시 인터페이스로만 접근 가능한 것
• 실행 순서 제어를 위한 동기화
  • 조건 변수(condition variable) 이용 : 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수
  • 조건변수.wait() : 대기 상태로 변경, 조건 변수에 대한 큐에 삽입 -> 실행 조건이 되지 않으면 실행을 중단
  • 조건변수.signal() : wiat()으로 대기 상태로 접어든 조건 변수를 실행상태로 변경 -> 실행 조건이 충족되면 실행을 재개

Chpater 13. 교착 상태

13-1) 교착 상태란

교착상태(deadlock)

• 식사하는 철학자 문제(dining philosophers problem)
• 일어나지 않는 사건을 기다리며 진행이 멈춰버리는 현상

자원 할당 그래프(resource-allocation graph)

• 그리는 방법
  • (1) 프로세스는 원, 자원의 종류는 사각형
  • (2) 사용할 수 있는 자원의 개수는 사격형 내 점으로 표현
  • (3) 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스로 화살표 표시
  • (4) 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표 표시
• 핵심은 교착 상태가 일어난 그래프의 특징은 "원의 형태"를 띄고 있다는 것

교착 상태가 발생할 조건

• 아래 4가지 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않음! (즉, 4가지를 모두 고려하지 않아야 교착상태가 발생)
  • (1) 상호배제(mutual exclusion)
    • 하나의 자원에 대해 한 번에 한 프로세스만 사용할 수 있는 것
  • (2) 점유와 대기(hold and wait)
    • 프로세스가 자원을 할당 받은 상태에서 다른 자원의 할당 받기를 기다리는 상태
  • (3) 비선점(non-preemptive)
    • 자원은 그 자원을 보유하고 있는 프로세스가 자신의 작업을 완료 후 자발적으로만 해제할 수 있다는 것
    • 즉, 어떤 프로세스도 다른 프로세스의 사용 자원을 강제로 빼앗지 못하는 상태
  • (4) 원형 대기(circular wait)
    • 프로세스들이 원의 형태로 자원을 대기하는 상태

13-2) 교착 상태 해결 방법

1) 교착 상태 예방

• 교착 상태가 발생하지 않도록 "교착 상태 발생 조건" 중 하나를 없애버림으로써 예방하는 것
• (1) 상호배제를 없애면?
  • 모든 자원을 공유 가능하게 만든다? 말이 안 됨...2개 이상의 프로세스가 어떻게 1개의 CPU를 공유해서 사용하겠음...
  • 이론 상 가능하나, 현실적으로는 안 됨
• (2) 점유와 대기를 없애면?
  • 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분
  • 자원의 활용률이 낮아질 수 있음
• (3) 비선점 조건을 없애면?
  • 선점이 가능한 자원(CPU)에 한해 효과적이지만, 모든 자원이 선점 가능한 것은 아님
  • 예를 들어, 프린터를 여러 프로세스가 선점해버릴 수는 없는 것...(프린트 중간에 바꿀 수는 없으니깐...)
• (4) 원형 대기 조건을 없애면?
  • 모든 자원에다가 번호를 붙이고, 그 붙인 번호의 오름차순으로 자원을 할당하면 원형 대기 조건은 발생하지 않음
    • 식사하는 철학자 문제를 예를 들면, 포크에 번호를 붙이고 작은 번호를 들어야만 큰 번호를 들 수 있다고 한 것
    • 이는 원형 탁자를 일자형 탁자로 바꾼 것과 유사함...
  • 자원에 번호를 붙이는 것은 어려운 일이고, 어떤 자원에 어떤 번호를 붙이냐에 따라 자원 활용률이 달라짐
  • 앞선 방법 중 가장 현실적이지만, 위와 같은 어려움이 있음

2) 교착 상태 회피

• 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주하고, 배분할 수 있는 자원의 양을 고려해서 자원을 배분하는 것
• 회피 방법은 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하는 방식으로 안전 상태를 유지하는 것 (은행원 알고리즘)
  • (1) 안전 순서열
    • 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
  • (2) 안전 상태
    • 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태
  • (3) 불안정 상태
    • 교착 상태가 발생할 수도 있는 상태

3) 교착 상태 검출 후 회복

• 교착 상태의 발생을 인정하고, 사후에 조치하는 방식으로 일단 자원을 할당하고, 교착 상태가 검출되면 회복
• 회복 방법
  • (1) 선점을 통한 회복
    • 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
  • (2) 프로세스 강제 종료를 통한 회복
    • 교착 상태에 놓인 프로세스 모두 강제 종료 (작업 내역을 잃을수도 있음)
    • 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료 (오버헤드)

4) 교착 상태 무시

• 타조 알고리즘 : 그냥 무시하는 방법...

Chpater 14. 가상 메모리

14-1) 연속 메모리 할당

연속 메모리 할당

• 프로세스에 연속적인 메모리 공간을 할당
• 2가지 문제점
  • 외부 단편화
  • 물리 메모리보다 큰 프로세스 실행 불가

스와핑(swapping)

• 현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역으로 쫓아내고, 그렇게 생긴 빈 공간에 새 프로세스를 적재하는 것
  
  • (1) 스왑 영역(swap space) : 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
  • (2) 스왑 아웃(swap-out) : 프로세스가 메모리 -> 스왑 영역
  • (3) 스왑 인(swap-in) : 프로세스가 메모리 <- 스왑 영역
• 장점 : 프로세스들이 요구하는 메모리 공간 크기가 실제 메모리 크기보다 크더라도 동시에 시행 가능
• 스왑 시 물리주소는 달라질 수 있음

메모리 할당

• 프로세스를 메모리 내의 빈 공간에 어떻게 적재할지에 대한 방식
• (1) 최초 적합(first-fit)
  • 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 할당하는 방식
  • 검색 최소화, 빠른 할당
• (2) 최적 적합(best-fit)
  • 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 작은 공간에 프로세스를 할당하는 방식
• (3) 최악 적합(worst-fit)
  • 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 큰 공간에 할당 하는 방식

외부 단편화(external fragmentation)

• 프로세스들이 실행되고 종료되길 반복하며 메모리 사이 사이에 빈공간이 발생
• 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리 낭비가 발생하는 현상
• 해결1) 메모리 압축(compaction)
  • 흩어진 빈 공간들을 하나로 모으는 방식
  • 즉, 프로세스를 적당히 재배치시켜 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법
  • 단점 : 프로세스의 오버헤드라던가, 어떻게 배치해야하는지에 대한 것도 조금 어려움...
• 해결2) 가상 메모리 기법, 페이지
  • 다음 챕터에서 자세하게...

14-2) 페이징을 통한 가상 메모리 관리

가상메모리(virtual memory)

• 실행하고자 하는 프로그램 중 일부만 메모리에 적재하여 실제 물리 메모리보다 더 큰 프로세스를 실행할 수 있게 만드는 기술
• 이러한 가상 메모리 관리 기법으로 페이징과 세그멘테이션이 존재함 (페이징이 주류)

페이징(paging)

• 아이디어
  
  • 외부 단편화의 근본적인 문제는 "각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문"
  • 프로세스를 일정 크기로 자르고 이를 메모리에 불연속적으로 할당하는 기법
• 용어
  • 페이지(page) : 프로세스의 논리 주소 공간을 일정 단위로 자른 것
  • 프레임(frame) : 메모리의 물리 주소 공간을 페이지와 동일한 일정 단위로 자른 것
  • 페이징(paging) : 페이지를 프레임에 할당하는 가상 메모리 관리 기법
• 페이징에서의 스와핑도 가능
  • 기존 스와핑을 통해 프로세스 전체가 스왑 아웃, 스왑 인 되는 것이 아닌 페이지 단위로 스왑 아웃, 스왑 인 되는 것
  • 페이지 아웃(page out), 페이지 인(page in)이라 부름
  • 이는, 하나의 프로세스가 실행될 때, 모든 페이지가 필요한 것은 아님을 시사함
• 참고로, 일부 운영체제(리눅스 포함)에서는 기본 설정된 페이지보다 큰 대형 페이지(huge page)를 사용하여 메모리에 유지하기도 함

페이지 테이블(page table)

• 페이지 번호와 프레임 번호를 짝지어 준 테이블
• 물리주소는 불연속적이어도, CPU가 바라보는 논리주소에는 연속적으로 배치되도록 만들어줌

내부 단편화(internal fragmentation)

• 프로세스 크기가 페이지 크기의 배수에 딱 맞지 않아 남게 되는 메모리 낭비
  • 예시) 페이지 크기 10KB, 프로세스 크기 108 KB -> 2KB 내부 단편화!

페이지 테이블 베이스 레지스터(PTBR; Page Tabe Base Register)

• 프로세스마다 페이지 테이블이 존재하고, CPU내의 PTBR이라는 레지스터가 해당 페이지 테이블을 가리킨다
• 만약, 페이지 테이블이 메모리에 존재한다면?
  • 메모리 접근 시간은 2배가 됨
  • 메모리에 있는 페이지 테이블에 접근하기 위해 1번, 이를 참조하여 다시 페이지에 접근하기 위해 2번
  • 따라서, TLB에 저장함

• TLB(Translation Lookaside Buffer)
  • 캐시 메모리로 페이지 테이블의 일부를 저장함
  • 일반적으로 MMU(Memory Management Unit; 메모리관리장치) 내에 저장되어, CPU 곁에 있음
  • TLB 히트(Hit) / TLB 미스(Miss) : CPU가 접근하려는 논리주소가 TLB에 존재하는지 아닌지 측정

페이징에서의 주소 변환

• 페이징 시스템에서의 논리주소 : 페이지번호(page number) + 변위(offset)
  
  • 근데, 이는 "프레임번호 + 변위"로 주소를 변경할텐데 이 때 변위의 값은 동일함!! 페이지와 프레임의 크기는 동일하므로!!

페이지 테이블 엔트리(PTE; Page Table Entry)

• 페이지 테이블 내에 각각의 행들을 의미함. 각 행 내에는 페이지번호와 프레임번호 외 다른 정보도 존재함
• (1) 유효 비트(valid ibt)
  • 현재 해당 페이지에 접근 가능한지 여부. 즉, 페이지 스와핑을 통해 페이지가 메모리에 없을수도 있는데 이를 확인하는 값
  • 유효 비트가 0(현재 메모리에 없으면) -> 페이지 폴트(page fault) 인터럽트 발생
    • CPU는 기존의 작업 내역을 백업
    • 페이지 폴트 처리 루틴을 실행
    • 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경
    • 페이지 폴트를 처리 후, CPU는 해당 페이지에 접근 가능해짐
• (2) 보호 비트(protection bit)
  • 페이지 보호기능을 위해 존재하는 비트. 예를 들어 읽기만 가능한 페이지, 쓰기만 가능한 페이지 등등
  • 페이지에 접근할 권한을 제한하여 페이지를 보호하는 비트
• (3) 참조 비트(referece bit)
  • CPU가 페이지에 접근한 적이 있는지 여부를 나타낸 것
• (4) 수정 비트(modified bit, dirty bit)
  • 해당 페이지에 데이터를 write한적 적 있는지 아닌지 알려주는 것
  • 이는 스와핑과 관련된 것. 수정한 내역을 살펴보고 보조기억장치에 페이지 아웃 시 새로 작성해야할지 말지 결정 가능

페이징 장점

• 이론적인 fork()에서 "쓰기 시 복사" 방법의 이점이 있음
  
  • 부모 프로세스가 적재된 별도의 공간에 자식 프로세스가 통째로 복제되어 적재(프로세스 생성 시간 지연, 메모리 낭비)
  • 즉, 기본적으로 자원을 공유하지 않음
  • 하지만, "쓰기 시 복사" 관점에서는 자식 프로세스도 부모 프로세스와 동일한 프레임을 가리킴 (쓰기 작업이 없다면!)
  • 만약, 둘 중 하나가 페이지에 쓰기 작업을 수행한다면, 해당 페이지만 별도의 공간으로 복제(프로세스 생성 시간 절약, 메모리 절약)

계층적 페이징(hierarchical paging)

• 페이지 테이블의 크기는 생각보다 작지 않음(프로세스가 커지면 테이블도 커짐)
• 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식으로 "다단계 페이지 테이블"(multilevel page table)이라고 부름
• 이 때, 페이지 테이블을 페이징한 페이지 테이블을 "Outer 페이지 테이블"이라 함
• CPU와 가장 가까이 위치한 페이지 테이블은 Outer 페이지 테이블이고 이는 항상 메모리에 유지함
• 논리주소 = 바깥 페이지 번호 + 안쪽 페이지 번호 + 변위

14-3) 페이지 교체와 프레임 할당

요구 페이징(demand paging)

• 요구되는 페이지만 적재하는 기법
  
  • CPU가 특정 페이지에 접근하는 명령어를 실행 - 유효 비트 확인 - 없을 경우 페이지 폴트 발생 - 메모리에 적재
• 순수 요구 페이징(pure demand paging) 기법
  • 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행하면서 지속적으로 페이지 폴트를 발생시켜 쭉 적재하고 시작하는 방법
• 요구 페이징 시스템이 안정적으로 작동하기 위해 해결할 문제 2가지
  • 페이지 교체
  • 프레임 할당

페이지 교체 알고리즘(Page Replacement Algorithm)

• 어떤 페이지를 페이지-아웃(스왑 아웃) 해야하는지 결정하는 방법으로 "페이지 폴트가 적은 알고리즘"이 중요함!
• 페이지 참조열(page refernce string) : CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
  • 2 2 2 3 5 5 5 3 3 7 -> 2 3 5 3 7
• (1) FIFO 페이지 교체 알고리즘(FIFO)
  • 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
  • 단점은 프로그램 실행 초기에 잠깐 실행되었으나 실행 내내 중요한 프로그램의 페이지를 내쫓을수도 있음
  • 디벨롭(보완책) : 2차 기회(second-chance) 페이지 교체 알고리즘
    • 가장 오래된 페이지를 내쫓으려고 시도하는 것은 동일함. 하지만 가장 오래된 페이지의 참조 비트를 추가적으로 확인
    • 참조 비트 1 = CPU가 한 번 참조한 적이 있는 페이지. 교체하기 전, 한 번 더 기회를 줌. 참조 비트 0으로 초기화 후 적재 시간을 현재 시간으로 설정
    • 참조 비트 0 : 내쫓음
• (2) 최적 페이지 교체 알고리즘(optimal)
  • 앞으로의 사용 빈도가 가장 낮은 페이지, 즉 CPU에 의해 참조되는 횟수를 고려하여 교체하는 알고리즘
  • 말 그대로 가장 낮은 페이지 폴트율을 보장하는 알고리즘
  • 앞으로 사용 빈도가 가장 낮은 페이지를 도대체 어떻게 예측할 것...? 그래서, 사실 이론적으로만 존재함
  • 다른 페이지 교체 알고리즘 성능을 평가하기 위한 기준선으로 간주
• (3) LRU 페이지 교체 알고리즘(Least-Recently-Used)
  • 가장 오랫동안 사용되지 않은 페이지 교체. 즉, 가장 오랫동안 사용되지 않은 페이지를 교체하는 것
• (4) 기타... 상당히 많음!
  • 다만, 이게 무엇인지? 왜 해야하고? 어떤 게 좋은 교체 알고리즘인지에 대해 설명할 수 있는 게 중요

페이지 폴트가 자주 발생하는 이유 2가지

• (1) 나쁜 페이지 교체 알고리즘을 사용해서 -> 페이지 교체
• (2) 프로세스가 사용할 수 있는 프레임수 자체가 적어서!! -> 프레임 할당

스래싱(thrashing)

• 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능(CPU 이용률)이 저해되는 문제
• 동시 실행되는 프로세스의 수를 늘린다고 CPU 이용률이 높아지다가, 훅 떨어지는 구간이 스래싱인 것

출처 : https://velog.io/@mingkimk/%EC%8A%A4%EB%9E%98%EC%8B%B1Thrashing

• 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문에 발생
  • 즉, 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 프레임을 할당할 것

프레임 할당 방식

• 정적 할당 방식 : 단순히 프로세스 크기와 물리 메모리의 크기만 고려한 방식
  • (1) 균등 할당(equal allocation)
    • 가장 단순한 할당 방식으로 모든 프로세스들에게 균등하게 프레임을 할당하는 방식
  • (2) 비례 할당(proportional allocation)
    • 프로세스 크기에 비례하게 프레임 할당
• 동적 할당 방식 : 사실 프로세스가 필요로 하는 프레임 수는 실행해 봐야 알 수 있음
  • (3) 작업 집합 모델(working set model)
    • CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당
    • 작업 집합(working set) : 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합
    • 실제 구하려면 프로세스가 참조한 페이지, 시간 간격이 필요함
    • 어떤 시간(t1)으로부터 과거에 떨어진 시간 간격(delta_t)까지 참조한 페이지들의 집합 {5,6,7}이면 3개라고 하는 것
  • (4) 페이지 폴트 빈도 기반 모델(PFF; Page-Fault Frequency)
    • 2가지 가정
      • 페이지 폴트율이 너무 높으면 프로세스는 너무 적은 프레임을 가짐
      • 페이지 폴트율이 너무 낮으면 프로세스가 너무 많은 프레임을 가짐
    • 즉, 페이지 폴트율과 할당된 프레임 수는 반비례하다는 가정
    • 따라서, 적당한 페이지 폴트율에 대한 상한선과 하한선을 정하고 해당 범위 안에서만 프레임을 할당하는 방식

Chpater 15. 파일 시스템

15-1) 파일과 디렉터리

파일 시스템(file system) 개요

• 파일과 디렉터리를 관리하는 운영체제 내의 프로그램
• 이 때, 파일과 디렉터리란 보조기억장치의 데이터 덩어리를 의미함

파일 시스템 내 요소

• (1) 파일(file)
  
  • 보조기억장치에 저장된 의미있고 관련 있는 정보를 모은 논리적 단위, 관련 정보의 집합
  • 파일 내 데이터 종류
    • 파일을 실행하기 위한 정보
    • 파일을 구성하고 있는 정보
      • 부가정보 = 속성(attribute) = 메타데이터(metadata)
      • 속성 : 유형(확장자, extension), 크기, 보호, 생성날짜, 마지막 접근 날짜, 마지막 수정 날짜, 생성자, 소유자, 위치...
  • 파일 연산을 위한 시스템 호출 (반드시 파일은 운영체제에 의해 다루어짐)
    • 파일 생성/삭제/열기/닫기/읽기/쓰기 등등
• (2) 디렉터리(directory) = 폴더(folder)
  • 1단계 디렉터리(single-level directory) : 과거에 존재하여 하나의 디렉토리 내 모든 파일이 존재
  • 트리 구조 디렉터리(tree-structured directory) : 여러 계층으로 파일 및 폴더를 관리하는 구조
    • 최상위디렉터리 = 루트디렉터리 = '/'
  • 많은 OS에서는 디렉터리를 그저 '특별한 형태의 파일'로 간주하긴 함
  • 디렉터리 엔트리(Directory Entry)
    • 디렉터리 내부에는 디렉터리에 담긴 대상과 관련된 정보를 담은 디렉터리 테이블(Directory table)이 존재함
    • 디렉터리 테이블의 각 행을 디렉터리 엔트리라 부름
    • 각 엔트리(행)에는 '대상 이름', '보조기억장치 내 저장된 위치(를 유추할 정보)'가 있음 (다른 정보도 있기도 함)
• (3) 경로(path)
  • 디렉토리를 이용한 파일/디렉토리의 위치, 이름까지도 특정 지을 수 있는 정보
  • 절대 경로와 상대 경로가 존재함
    • 절대 경로 : 루트 디렉토리로부터 자기 자신까지 이르는 고유한 경로
    • 상대 경로 : 현재 디렉토리로부터 자기 자신까지 이르는 경로

15-2) 파일 시스템

파일 시스템

• 파일과 디렉터리를 보조기억장치에 할당하고 접근하는 방법
• FAT 파일 시스템, 유닉스 파일 시스템 등등이 존재
• 파일시스템은 파티셔닝과 포매팅을 한 후에 사용이 가능함
  • 파티셔닝(Partitioning)
    • 저장 장치의 논리적인 영역을 구획하는 작업으로 논리적인 하나의 영역을 파티션(partition)이라 부름
  • 포매팅(Formatting)
    • 파일 시스템을 설정하고, 어떤 방식으로 파일을 관리할지 결정하고 새로운 데이터를 쓸 준비를 하는 작업
    • 파티션마다 각기 다른 파일 시스템을 설정할 수도 있음

파일 할당 방법

• OS는 파일/디렉터리를 블록 단위로 읽고 쓴다
  • 하나의 파일이 보조기억장치에 저장될 때는, 여러 블록에 걸쳐 저장됨
  • 하드 디스크의 가장 작은 저장 단위는 섹터이지만 보통 섹터가 모인 블록 단위로 읽고 씀
• 파일 할당 방법 종류
  • (1) 연속 할당
    • 보조기억장치 내 연속적인 블록에 파일을 할당
    • 디렉터리 엔트리 내 "파일 이름", "첫 번째 블록주소", "블록 단위 길이" 를 명시함
    • 구현은 단순하지만 외부 단편화를 야기할 수 있음
  • (2) 불연속 할당
    • (2)-1. 연결 할당
      • 각 블록의 일부에 다음 블록의 주소를 저장하여 다음 블록을 가리키도록 함
      • 즉, 데이터 블록을 연결 리스트로 관리하여 불연속 할당되어도 순차적으로 알아낼 수 있는 방식
      • 디렉터리 엔트리 내 "파일이름", "첫 번째 블록주소", "블록 단위의 길이"(or "마지막 블록주소")를 명시함
      • 외부 단편화는 해결하지만 반드시 첫 번째 블록부터 하나씩 읽어들여야 하므로 오류 발생 시 그 이후 블록은 접근이 어려움
    • (2)-2. 색인 할당
      • 파일의 모든 블록 주소를 색인 블록이라는 하나의 블록에 모아 관리하는 방식
      • 디렉터리 엔트리 내 "파일이름", "색인블록주소"를 명시함

FAT 파일 시스템

• 연결 할당 기반 파일 시스템
• 연결 할당의 단점을 보완하고자 FAT(File Allocation Table)을 관리함
  • 각 블록에 포함된 다음 블록 주소를 한데 모아 놓은 표
  • 추가로, FAT 데이터는 메모리에 캐시될 수 있기 때문에 임의 접근 속도 개선 가능
• MS-DOS, 각종 USB 메모리, SD카드에 사용됨
• FAT-12, FAT-16, FAT-32 와 같은 종류가 존재하고, 숫자는 블록의 비트수를 의미함
• FAT 파일 시스템의 파티션 내 영역은 다음 4가지로 단순화할 수 있음
  • 예약 영역
  • FAT 영역
  • 루트 디렉터리 영역
  • 데이터 영역
• 디렉터리 엔트리
  • 파일 이름, 시작블록, 속성(...)

유닉스 파일 시스템

• 색인 할당 기반 파일 시스템
• "색인 블록"을 "i-node"라 부름. 파일의 속성 정보와 15개의 블록 주소가 저장 가능
• 유닉스 파일 시스템의 파티션 내 영역(단순화)
  • 예약 영역
  • i-node 영역
  • 데이터 영역
• 블록 주소가 15개?
  • (1) 블록 주소 15개 중 12개에는 "직접 블록 주소" 저장
  • (2) 데이터 크기가 블록 12개를 넘으면 13번째 주소에 "단일 간접 블록 주소" 저장
  • (3) 데이터 크기가 이 또한 넘어서면, 14번째 주소에 "이중 간접 블록 주소" 저장
  • (4) 데이터 크기가 이 또한 넘어서면, 15번째 주소에 "삼중 간접 블록 주소" 저장
    • 직접 블록 주소 = 파일 데이터가 저장된 블록
    • 간접 블록 주소 = 파일 데이터를 저장한 블록주소가 저장된 블록
    • 이중 간접 블록 주소 = 단일 간접 블록들의 주소를 저장한 블록
    • 삼중 간접 블록 주소 = 이중 간접 블록들의 주소를 저장한 블록
• 디렉터리 엔트리
  • i-node번호, 파일 이름
  • i-node가 사실 모든 걸 알고 있어서 위의 2개만 있어도 크게 상관이 없는 것!

그 외 파일시스템

• NTFS : Window OS에서 사용하는 NT파일시스템
• EXT 파일시스템 : 리눅스 OS에서 사용되는 파일시스템

마무리

챕터1~15까지 공부하면서 컴퓨터구조와 운영체제의 전반적인 내용을 훑어볼 수 있어서 매우 좋았다. 설명도 너무 좋았고, 정말 핵심적인 내용만 담아서 최대한 이해하기 쉽게 만들려는 노력이 책과 강의에서 느껴지기도 했다. 좀 더 깊은 내용들은 다른 곳에서 다시 살펴봐야겠지만 비전공자이자 개념을 모르는 사람에게 전반적인 흐름을 이해하고 핵심적인 개념들을 잡을 때는 매우 좋은 자료라고 생각한다.

 

사실, 이번 강의를 통해 "강민철" 강사님에 대한 신뢰도가 매우 올랐고 무료 강의라는 점에서 또 다시 어떻게든 홍보를 하고 싶은데 아래에 있는 강의와 책 링크는 다음과 같다. 해당 블로그에서는 단순 줄글로만 되어 있으나 책이나 강의를 통해 다양한 그림과 예시를 통해 설명하니 더욱 이해가 잘 되는 듯 하다.

• 인프런 강의 링크(무료)
• 책 링크(알라딘)

추가로,  "챕터1~8까지 컴퓨터구조" 를 정리한 내용은 다음 링크를 참고바란다.