< Day 11>

운영체제

1⃣ 개요

프로그래머는 프로세스가 메로리에 어느 위치에 올라가는지 신경쓰지 않고 0X0번지에 들어간다고 생각하고 프로그래밍 하면 된다.

프로세스(사용자)는 메모리 관리자를 통해 메모리에 접근

가상 메모리는 물리 메모리 크기와 CPU 비트수로 결정( 만약 32bit CPU인 경우, 2³² 주소값이 되고 4GB 정도 된다.)

32bit CPU를 가진 가상 메모리(4GB)가 4GB 프로세스 5개를 실행시키려면 어떻게 해야할까?

물리 메모리 내용의 일부를 하드디스크에 스왑영역으로 옮기고 처리가 필요할 때 물리 메모리로 가져와 실행시키기 때문에 이를 다 실행시킬 수 있다.

메모리 관리 기법의 하나로 컴퓨터가 실제로 이용 가능한 메모리 자원을 추상화하여 이를 사용하는 사용자들에게 큰 메모리로 보이게 하는 것이다.

✔ 동적주소할당 (Dynamic Address)

메모리 관리자는 메모리와 하드디스크 내 스왑영역을 합쳐 가상주소 대신 물리주소로 변환하는 것을 동적주소할당이라 한다.

이를 통해 프로세스는 사용자 데이터를 물리 메모리에 배치할 수 있다.

2⃣ 세그멘테이션(배치 정책)

의미 단위인 세그먼트(Segment)로 나누어 메모리에 할당하는 방법이다. 이 때 세그먼트는 크기가 가변적이고 논리적인 단위인데, 이 방식은 프로그램의 크기가 달라지는 경우 유연하게 대처가 가능하다.

사용자, 프로세스 CPU가 바라보는 주소는 논리주소

3⃣ 페이징(배치 정책)

메모리를 할당할 때 정해진 크기의 페이지로 나눈다.일정한 크기로 나누었기 때문에 관리도 쉽고, 외부 단편화 현상이 발생하지 않는다. (✳ 내부 단편화 발생)

✔ 페이지

사용자, 프로세스가 바라보는 주소공간인 논리주소공간을 일정한 크기로 나눈 것.

✔ 프레임

메모리에 실제 주소공간인 물리주소공간을 일정한 크기로 나눈 것.

3.1 세그멘테이션과 페이징의 차이점

세그멘테이션은 프로세스마다 크기가 달라 크기를 표현하는 Bound Address를 가지고 있지만

페이징은 모든 페이지의 크기가 동일해서 크기를 표현하는 것이 필요하지 않다,

이 때문에 페이징은 내부 단편화가 발생하고, 세그멘테이션은 외부단편화가 발생한다.

정해진 페이지의 크기보다 프로세스의 크기가 작으면 그만큼 공간이 낭비되는데 이를 내부 단편화라고 한다.

• 논리적인 영역으로 나눌 수 없다.

세그멘테이션은 논리적인 영역인 코드, 데이터, 힙, 스택 영역으로 나눌 수 있지만

페이징은 정해진 크기인 페이지로 나누기 때문에 논리적인 영역을 나눌 수 없다.

3.2 메모리에 여러 개의 프로세스가 올라오는 멀티 프로그래밍 환경에서는 어떻게 동작하는가

(1) 가변 분할 방식(세그멘테이션)

프로세스가 크면 메모리도 크게 할당

한 프로세스가 메모리에 연속된 공간에 할당되기 때문에 연속 메모리 할당이라 부른다.

✔ 장점

• 내부 단편화 현상 없음.

✔ 단점

• 외부 단편화 발생

3MB 프로그램과 2MB 프로그램이 종료되어 공간이 발생되어도 5MB 프로그램이 들어가지 못한다.

(2) 고정 분할 방식(페이징)

프로세스의 크기와는 상관없이 메모리를 정해진 방식으로 할당

한 프로세스가 메모리에 분산되어 할당되기 때문에

비연속 메모리 할당이라 부른다.

(5MB 프로그램을 2MB 고정 분할 메모리에 저장 시키려면 2/ 2/ 1 로 분리해야함)

✔ 장점

• 구현이 간단하고 오버헤드가 적음

✔ 단점

• 작은 프로세스도 큰 영역에 할당되어서 공간이 낭비되는 내부 단편화가 발생

(3) 버디 시스템(가변 + 고정)

2의 승수로 메모리를 분할하여 메모리를 할당하는 방식

• 전체 메모리 영역을 하나의 프로세스가 올라갈 수 있을 정도로 2의 승수로 나눠서 분할

• 최소한의 내부 단편화, 간단한 메모리 합치기가 가능

4⃣ 페이지드 세그멘테이션(배치 정책)

세그멘테이션은 보호와 공유에 효율적이고, 페이징은 외부 단편화 문제를 해결할 수 있다. 이 두 가지를 합쳐서 나온게 세그먼트를 페이징 기법으로 나누는 페이지드 세그멘테이션이다.

4.1 메모리 접근 권한

메모리의 특정 번지에 부여된 권한

• 코드 영역

프로그램 그 자체이기 때문에 읽기/실행 권한이 가능하다.

• 데이터 영역

일반변수, 전역변수, 상수로 선언한 변수가 저장한다. 읽기(쓰기) 권한은 있으나 실행 권한은 없다.

• 힙 영역

읽기/쓰기 권한 O / 실행 권한 X

• 스택 영역

읽기/쓰기 권한 O / 실행 권한 X

메모리 접근 권한에 대한 검사 가상주소 → 물리주소로 변환될 때 마다 일어나는데, 만약 권한을 위반한다면, 에러를 발생 시키고 종료시킨다.

2. 페이지드 세그멘테이션

세그멘테이션 테이블은 세그먼트의 번호, 시작 주소, 세그먼트의 크기를 엔트리로 갖는다.

세그멘테이션 테이블에서

• 권한 비트 추가

• Base Address → 페이지 넘버 : 이름 변경

• Bound Address → 페이지 개수 : 이름 변경

논리 주소 0x12300번지 접근 요청시,

• 논리 주소를 이용해 몇 번 세그먼트인지 알아냄.

• 세그멘테이션 테이블에서 1번 인덱스를 참조

• 해당 세그먼트가 메모리 접근 권한을 위반하는지 검사

   

  ✔ 접근 권한 위반할 시, 프로세스가 종료

   

  ✔ 위반 하지 않으면, 페이지 넘버와 페이지 개수 가져옴

• 페이지 넘버로 페이지 테이블에 접근해서 프레임 번호 가져옴

• 논리 주소에서 오프셋을 알아내고

• 오프셋 + 프레임 번호 위치 = 물리 주소

물리 메모리에 해당 프레임이 없다면, 스왑 영역에서 물리 메모리로 가져온다.

✔ 단점

물리 메모리에 접근 하기 위해서 메모리에 접근을 2번 해야한다.

1. 세그멘테이션 테이블 참조할 때

2. 페이지 테이블 참조 할 때

    

알고리즘

삽입정렬

1. 개념

배열을 정렬된 영역과 정렬되지 않은 영역으로 나눈다.

삽입정렬은 정렬되지 않은 영역에서 데이터를 하나씩 꺼내서 정렬된 영역 내 적절한 위치에 삽입하는 알고리즘이다.

가장 첫 번째 숫자 3은 정렬되어있고, 나머지 숫자들은 정렬되지 않았다고 가정하면

먼저 정렬되지 않은 영역의 첫 번째 원소인 7을 정렬된 영역에 삽입합니다.

삽입할 원소인 숫자 7과 정렬된 영역의 마지막 원소(숫자 3)를 비교합니다.

이 때, 숫자 3과 숫자 7을 비교하는데, 7은 3보다 크므로 바뀌지 않고 그대로 유지됩니다.

그 다음 (b)에서 다시 정렬된 영역 3,7 그리고 나머지 정렬되지 않은 영역을 나눕니다.

이제 정렬되지 않응 영역의 첫 번째 원소인 2를 정렬된 영역의 가장 뒤에 있는 원소 (숫자 7)부터 역순으로 비교합니다.

7은 2보다 크기 때문에 7을 오른쪽 인덱스(숫자 2의 인덱스)에 덮어써줍니다. 그리고 숫자 2를 인덱스 1번째에 삽입합니다. ( 3 2 7 5 1 4 )

그 다음 2를 정렬된 영역의 그 다음 원소인 3과 비교해줍니다.

3은 2보다 크기 때문에 3을 오른쪽 인덱스(인덱스 1번째)에 덮어써줍니다. 그리고 숫자 2를 인덱스 0번째에 삽입합니다. (2 3 7 5 1 4)

< Day 12 >

운영체제

1⃣디멘드 페이징(가져오기 정책)

1. 지역성 이론

• 공간의 지역성

현재 위치와 가장 가까운 데이터에 접근할 확률이 높은 것

• 시간 지역성

최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높은 것

지역성 이론은 조만간 쓰일 데이터만 메모리에 올리고 당분간 사용하지 않을 데이터는 하드디스크의 스왑 영역에 보내 성능을 향상 시키는 것, 이를 디멘드 페이징이라 한다.

2. 메모리 계층 구조

✔ 레지스터(CPU 한 사이클)

같은 방에 상자를 가지러 가는 것

✔ 캐시( n ~ nnn 사이클)

같은 건물에 있는 상자를 가지러 가는 것

✔ 메인메모리(RAM) (nnn 사이클)

같은 동네에 있는 상자를 가지러 가는 것

✔ 보조기억장치(HDD, SSD) (nnnnnn 사이클)

상자를 가지러 달나라까지 가는 것

디멘드 페이징은 스왑영역을 보조저장장치에 저장하는데 성능향상을 위해선 스왑영역으로 데이터를 이동시키는 것을 최소화 해야한다.

✳ 스왑인(Swap in)

가상 메모리의 크기는 물리 메모리 크기에 스왑영역을 합친 것

스왑영역에서 물리 메모리로 데이터를 가져오는 것을 스왑인이라한다.

스왑아웃(Swap out)

물리 메모리에서 스왑영역으로 데이터를 보내는 것

✔ 페이지 테이블 엔트리(PTE)

가상주소가 주어지면 메모리 관리자는 페이지 테이블을 참조해서 스왑영역의 위치를 알아낸다.

이를 위해 페이지 테이블에는 여러가지 비트가 존재한다.

이 페이지 테이블의 한 행을 이루고 있는 것이 페이지 테이블 엔트리(PTE)이다.

• 유효 비트(Valid Bit)

현재 해당 page에 접근 가능한지 여부를 알려준다

항상 모든 page가 물리 메모리에 존재하는 것은 아니고, 대부분 보조기억장치의 스왑영역에 존재한다.

그래서 유효 비트는 현재 page가 메모리에 적재되어있는지, 보조기억장치에 있는지 알려주는 bit이다.

만약 메모리에 적재되어있다면 유효 비트가 1, 그렇지 않다면 0으로 표기된다.

• 보호 비트 ( Protection Bit )

보호 비트는 해당 page가 읽기.쓰기가 모두 가능한 page인지, 혹은 읽기 전용인지를 나타낸다.

보호 비트가 0인 경우, 해당 page는 읽기 전용이고, 1일 경우 읽기.쓰기가 모두 가능하다.

• 참조 비트(Reference Bit)

CPU가 page에 접근한 이력이 있는지의 여부를 나타낸다.

메모리 적재 이후의 CPU가 읽기 또는 쓰기를 한 page는 참조 비트가 1로 설정되고, 적재 이후 한 번도 읽기.쓰기 한 이력이 없는 page는 0으로 유지된다.

알고리즘

병합 정렬

1. 개념

    

   대표적인 분할 정복(Divide and Conquer) 알고리즘 중 하나로, 리스트를 반으로 나눈 뒤 각각을 재귀적으로 정렬하고, 정렬된 두 개의 리스트를 합쳐서 정렬된 하나의 리스트를 만드는 알고리즘이다.

분할(Divide)

입력 리스트를 같은 크기의 두 개의 부분 리스트로 분할합니다. 이때 분할은 리스트의 중간 지점에서 수행됩니다.

정복(Conquer)

각 부분 리스트를 재귀적으로 병합정렬을 이용해 정렬합니다. 이 과정은 입력 리스트의 크기가 충분히 작아질 때까지 반복됩니다.

병합(Merge)

정렬된 두 부분 리스트를 하나의 정렬된 리스트로 병합합니다.

0개 요소, 1개 요소 배열이 이미 정렬되어 있다는 점을 활용합니다.

배열을 더 작은 배열 나누는 방식입니다.

분할 정복 알고리즘이라 알려진 방식이고, 더 큰 배열을 나누고, 더 작은 하위 배열로 정렬합니다.

배열의 요소가 0 또는 1개가 될 때까지 반복합니다.

계속 분할한 다음 다시 병합시킵니다.

장점

앞선 정렬들 보다 성능이 훨씬 좋다

단점

이해와 구현이 어렵다.

< Day 13 >

운영체제

1. 페이지 교체

프로세스는 데이터 접근을 위해 메모리를 참조하는데 해당 데이터가 메모리에 없으면 Page Falut가 발생한다.

필요한 페이지를 물리 메모리에 적재해야할 때, 만약 물리 메모리가 가득 차 있는 상태라면 특정 페이지는 page out 해야한다.

대표적인 페이지 교체로는 FIFO 페이지 교체, 최적 페이지 교체, LRU 페이지 교체, LFU 페이지 교체, MFU 페이지 교체 등이 있다.

1.1 FIFO 페이지 교체

가장 간단하고 직관적인 페이지 교체 방법.

먼저 물리 메모리에 들어온 순으로 페이지 교체가 이루어진다.

이해하기 쉽고 구현도 쉽지만, 단순히 먼저 들어온 페이지가 더 이상 사용되지 않는다는 것은 아니기 때문에, 활발하게 사용되는 페이지를 교체해서 page fault를 발생 빈도를 높힐 수도 있다.

✳ 빌레이디의 모순 (Belady’s Anomaly)

FIFO에서만 발생하는 역설이다.

일반적으로 페이지의 frame의 수를 늘리면, 메모리에 적재될 수 있는 페이지의 수가 늘어나기 때문에, page fault 발생 확률이 감소한다.

그러나, FIFO 페이지 교체에서는 단순히 오래된 페이지를 교체하기 때문에, 산술적으로 오히려 더 많은 page fault가 발생하게 된다.

즉, 성능 개선을 위해 frame의 수를 늘렸지만, 반대로 page fault가 더 자주 발생하여 성능이 악화되는 일이 일어난다.

1.2 최적 페이지 교체(Optimal Page Replacement)

앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식.

이론적으로 최적 성능을 보장하지만, 실제로는 알고리즘 구현이 어려워 대체로 사용되지 않는다.

1.3 LRU 페이지 교체 (LRU Page Replacement)

LRU : Least Recently Used

가장 오랫동안 사용되지 않을 페이지를 찾는 것이 아니라, 결과적으로 가장 오랫동안 사용되지 않은 페이지를 찾는 것.

지역성 이론의 시간의 지역성에 따르면 최근 사용한 데이터가 앞으로도 사용될 확률이 높으므로, 최근에 사용되지 않은 데이터가 앞으로도 사용될 확률이 적다는 결론이 나온다.

최적 페이지 교체와 근접한 성능을 보인다.

그러나 시간을 기록하려면 비트가 많이 필요한데 많은 비트의 사용은 어렵기 때문에 접근 비트를 사용한다.

✳ LRU의 시간 기록 문제 해결 방법

1.4 Clock 또는 Second-Chance

FIFO와 LRU를 결합한 방식

일정 시간 간격 마다 모든 페이지의 접근 비트를 0으로 초기화한다.

접근 비트의 초기값은 0 만약 페이지가 참조되었다면 1로 설정

일정 시간마다 페이지가 사용되었는지 확인 가능하다.

알고리즘

<퀵 정렬>

퀵 정렬은 in place 방법과 in place가 아닌 방법 2가지가 있는데 실제로 많이 쓰이는 방법은 메모리 사용량이 적은 in place 방법이다.

In Place

정렬되지 않은 데이터에서 가운데 원소를 pivot으로 설정하고 가장 왼쪽 요소와 가장 오른쪽 요소가 시작점이다.

가장 왼쪽부터 값을 pivot값을 비교하여 pivot보다 큰 값이 나타날 때까지 칸을 오른쪽으로 이동한다.

가장 오른쪽부터 값을 pivot값을 비교하여 pivot보다 작은 값이 나타날 때까지 칸을 왼쪽으로 이동한다.

pivot보다 큰 왼쪽 값과 pivot보다 작은 오른쪽 값을 서로 교환한다.

왼쪽 인덱스가 오른쪽 인덱스보다 커지면 이동을 멈추고 그 자리에서 두 배열로 갈라서

각 배열에 위와 같은 방식으로 재귀 호출하여 정렬한다.

이 방법은 추가적인 공간을 필요로하지 않기 때문에 메모리 공간이 절약된다는 장점이 있으나, 왼쪽과 오른쪽 값을 교환하는 과정에서 중복값의 위치가 바뀔 수 있으므로 unstable한 정렬 방법이다.

(+추가내용)

Not In Place

퀵 정렬은 병합 정렬과 같이 Divide and Conquer 전략을 사용한 알고리즘이다. 

즉, 정렬하는데 가장 간단한 배열은 바로 요소가 없거나 하나만 있는 배열이므로 모든 배열이 기본 배열이 될 때까지 큰 배열을 나눠야한다.

이 때 퀵 정렬에서는 요소 하나를 기준 원소인 pivot으로 설정한다. 그리고 기준 원소의 왼쪽에는 기준 원소보다 작은 값의 배열을 놓고 오른쪽에는 기준 원소보다 큰 값을 놓는다.

pivot 왼쪽에 놓여진 기준 원소보다 작은 배열에서 위와 같은 방법으로 다시 pivot을 설정하고 배열을 pivot을 기준으로 나눈다. 이 방법을 반복하면 결국 기본 단계인 원소가 하나만 있는 배열이 남는다.

1. 기준 원소를 고른다.

2. 배열을 기준 원소보다 작은 원소의 배열과 기준 원소보다 큰 원소의 배열, 이렇게 2개의 하위 배열로 분할한다.

3. 하위 배열에 대해 재귀적으로 퀵 정렬을 호출한다.

< Day 14 >

운영체제

1⃣ 주변장치(I/O 디바이스, 저장장치)

주변장치에는 그래픽 카드, HDD, SSD, 키보드, 마우스 등 여러가지가 있다.

1.1 주변장치의 내부 구조

• 각 하드웨어에 맞게 외부 인터페이스가 존재

• 레지스터

입출력 작업 시 데이터를 저장하며 CPU가 필요로 할 때 메모리로 이동

• 메인보드에 있는 버스를 통해 연결

• I/O 버스는 Address, Data, Control 이 세 가지 버스를 따로 받을 수 있다.

1.2 캐릭터 디바이스와 블록 디바이스

데이터의 전송단위가 캐릭터(글자)인지 블록인지로 나눈 것

✔ 캐릭터 디바이스

• 마우스, 키보드, 사운드카드, 직렬/병렬 포트 등이 있다.

• 상대적으로 적은 양의 데이터를 전송

✔ 블록 디바이스

• 하드디스크, SSD, 그래픽카드 등이 있다.

• 상대적으로 많은 양의 데이터를 전송

1.3 입출력 버스 구조

초기의 입출력 버스

버스 하나에 주변 장치를 모두 연결해서 사용했는데, CPU가 작업을 진행하다가 입출력 명령을 받으면 직접 입출력장치에서 데이터를 가져오는 폴링방식을 이용했다. 이는 CPU 사용률을 감소시킨다.

2⃣ 마우스와 키보드

광학 마우스의 작동원리

1. 마우스 밑면에 작은 카메라 탑재, 초당 1500회가 넘는 사진을 찍어 디바이스 컨트롤러 내 DSP(Digital Signal Processor)로 보낸다.

2. DSP는 사진을 분석해 마우스의 x축 좌표와 y축 좌표 움직임 분석

3. 디바이스 컨트롤러는 CPU에게 인터럽트를 보내고 마우스 드라이버가 동작해 데이터를 읽는다.

⭐여기서 잠깐!⭐

인터럽트를 복습해보자면

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

1. 마우스 드라이버는 운영체제에게 이벤트 신호를 보내고 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달

2. 해당 애플리케이션은 받은 마우스 이벤트 처리, 해당 동작 수행

키보드의 작동원리

1. 사용자가 키 입력

2. 디바이스 컨트롤러가 어떤 키를 입력 받았는지 알아냄

3. CPU에게 인터럽트를 보냄

4. 키보드 드라이버는 운영체제에 이벤트를 보내고 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달

5. 해당 애플리케이션은 받은 키보드 이벤트 처리, 해당 동작 수행

3⃣ 하드디스크

하드디스크의 구조

• 스핀들(spindle)

플래터의 중심 축 막대

• 플래터(platter)

자기화된 원판으로 구성. 여러개의 트랙(track)으로 구성되어 있으며 표면에 자성이 있어 표면이 N극을 띄면 0, S극을 띄면 1로 인식

• 디스크암(Disk Arm)

플래터쪽을 향한 끝부분에 있는 읽기/쓰기 헤드(read/write head)로 플래터의 표면을 읽는다. 이 헤드들은 항상 같이 움직인다.

• 실린더(cylinder)

여러 개의 플래터에 있는 같은 트랙의 집합

• 섹터(sector)

하드디스크의 가장 작은 단위

알고리즘

<메모이제이션>

메모이제이션(memoization)은 값비싼 함수 호출의 결과를 캐싱하고 동일한 입력이 다시 발생할 때 불필요하게 다시 계산하는 대신 캐싱된 결과를 반환하는 프로그래밍 기술로, 동일한 입력으로 여러 번 호출되는 함수 또는 컴포넌트가 있을 때 유용합니다.

메모이제이션은 메모리에 특정한 값을 저장하는 것이기 때문에, 정말 필요하지 않은 경우에도 남용하면 오히려 성능을 저하시킬 수 있습니다.

1. 함수형 프로그래밍과 메모이제이션

함수형 프로그래밍과 메모이제이션은 밀접하게 관련된 개념이다. 메모이제이션은 순수 함수의 실행을 최적화하기 위해 함수형 프로그래밍에서 일반적으로 사용된다.

• 불변성

   

  함수형 프로그래밍은 불변 데이터를 선호하여, 값이 할당되면 변경할 수 없다. 원본 데이터를 수정하는 대신 복사본을 사용하여 새 데이터 구조를 만든다.

• 순수 함수

  • 동일한 입력에 대해 동일한 출력을 생성한다.

  • 외부 상태를 수정하거나 변경 가능한 데이터에 의존하지 않는다(no side effect).

   

• 고차 함수

   

  다른 함수를 인수로 사용하거나 함수를 결과로 반환할 수 있다. 이를 통해 강력한 추상화가 가능하고 보다 일반적이고 재사용 가능한 코드를 작성할 수 있다.

• 재귀

   

  함수형 언어의 반복은 재귀에 의해 구현된다. 재귀 함수는 종료 조건이 충족될 때까지 수정된 매개변수로 자신을 호출한다.

• 기능 구성

   

  기능적 프로그래밍은 기능을 함께 연결하여 보다 복잡한 작업을 형성함으로써 기능을 구성한다. 이를 통해 한 함수의 출력이 다음 함수의 입력이 되는 파이프라인을 구성할 수 있다.

함수형 프로그래밍과 메모이제이션의 관계는 순수 함수가 참조적으로 투명하다는 사실에서 발생한다. 함수형 프로그래밍은 동일한 입력에 대해 동일한 출력을 생성하고 부작용(side effect)이 없는 함수인 순수 함수의 사용을 강조하는 프로그래밍이다.

그리고 메모이제이션은 함수를 다시 평가하는 대신 캐싱된 결과를 반환하여 함수의 성능을 향상시킨다. 이때 부작용이나 변경 가능한 상태를 고려하지 않기 때문에 함수형 프로그래밍의 원칙과 부합한다. 순수한 함수 호출의 결과가 프로그램의 정확성에 영향을 주지 않고 안전하게 캐싱될 수 있는 것이다.

따라서 메모이제이션을 사용하면 기능적 프로그래머가 참조 투명성을 희생하거나 부작용을 일으키지 않고 코드를 최적화할 수 있다. 즉, 메모이제이션은 순수 함수 호출을 최적화하고 중복 계산을 줄이며 성능을 향상시키는 방법을 제공함으로써 함수형 프로그래밍 패러다임을 보완하는 강력한 기술이다.

< Day 15 >

운영체제

1⃣ 파일과 파일 시스템

파일들은 하드디스크나 SSD같은 저장 장치에 저장되는데, 사용자가 직접 저장하면 손상시킬 수 있어 운영체제가 안전하게 저장한다.

✔ 파일시스템

운영체제가 파일을 관리하기 위해 둔 파일 관리자로, 파일테이블을 이용한다.

1.1 파일 시스템 기능

• 파일과 디렉토리 생성

• 파일과 디렉토리 수정/삭제

• 파일 권한 관리(다중 사용자 환경)

• 무결성 보장

• 백업 및 복구

• 파일 암호화로 파일 보호

파일은 하드디스크나 Flash Memory같은 블록 디바이스에 저장되기 때문에 전송 단위는 블록인데, 바이트 단위로 접근해야하는 사용자를 위해 파일 시스템이 중간에서 바이트 단위로 변환

1.2 파일의 구조

• 헤더

해당 파일의 속성 기록(파일 이름, 식별자, 유형, 크기, 시간, 저장 위치, 접근 권한, 소유자 등)

• 데이터

✔ 파일 디스크립터(File Descriptor)

운영체제가 파일을 관리하기 위해 정보를 보관하는 파일 제어 블록(File Control Block). 각 파일마다 독립적으로 존재하고, 저장장치에 존재하다 파일이 오픈되면 메모리로 이동한다.

사용자는 직접 참조할 수 없고, 파일시스템이 건내준 파일 디스크립터로 파일에 접근할 수 있다.

파일은 데이터의 집합으로 이루어지는데, 이 집합을 어떻게 구성하느냐에 따라 종류가 나뉜다.

1.3 파일의 분류

순차 파일 구조

파일의 내용이 연속적으로 이어지는 구조

• 작동 원리

사용자가 파일을 열기 위해 open()함수를 사용하면 파일 시스템은 파일 디스크립터를 사용자에게 전달한다. 파일 디스크립터는 파일의 맨 앞에 위치해 사용자가 읽기/쓰기를 시작하면 처음부터 진행한다. 다른 영역으로 가고싶다면 lseek() 함수를 이용해 파일디스크립터의 위치를 옮긴다.

• 장점

모든 데이터가 순서대로 기록되어 공간의 낭비가 없고 구조가 단순

• 단점

특정지점으로의 이동이 어려워 데이터 삽입, 삭제를 위한 탐색 시간 소요

직접 파일 구조

저장하려는 데이터를 해시함수를 통해 저장 위치를 결정하는 구조

예) 해시 테이블 자료구조, json

• 장점

해시함수 이용으로 데이터 접근 속도 빠름

• 단점

알맞은 해시함수를 잘 골라야하고 저장공간이 낭비될 가능성 존재

인덱스 파일구조

순차접근과 직접접근 방식의 장점을 취해 두 가지 모두 가능하게 한 구조

예) 재생목록

재생목록은 전부 순차 데이터로 저장되어있으며, 재생을 누르면 앞에서부터 뒤로 순차적 재생을 한다. 사용자가 듣고 싶은 노래를 클릭하면 인덱스 테이블의 해당 노래가 저장된 행에 접근해 블록 번호를 알아낸다. 순차 데이터의 해당 블록번호로 이동해 클릭한 노래가 재생될 수 있도록 한다.

2⃣ 디렉토리

디렉토리(Directory)

디렉토리는 파일과 다른 디렉토리를 포함할 수 있는 컨테이너로, 파일을 주제나 유형별로 그룹화하여 조직화할 수 있다. 디렉토리도 하나의 파일로, 파일이 데이터를 저장한다면 디렉토리는 파일 정보를 저장한다.

디렉토리 헤더

디렉토리 정보가 시작하는 위치를 가리킨다.

디렉토리에 점 한 개(.)와 점 두 개(..)가 있는데 이는 현재 디렉토리와 상위 디렉토리를 가리킨다.

루트 디렉토리의 경우 상위 디렉토리가 없기 때문에 점 두 개(..)도 자기 자신을 가리킨다.

디렉토리 구조

계층적 구조: 최상위에 루트 디렉토리(/)가 존재

초기

루트 디렉토리에만 디렉토리가 존재할 수 있고 다른 디렉토리에서는 하위 디렉토리를 만들 수 없는 구조

현재

다단계 디렉토리 구조로, 모든 디렉토리가 하위 디렉토리를 만들 수 있는 트리구조

3⃣ 파일과 디스크

파일과 디스크

전체 디스크 공간을 일정한 크기로 나누고 그 공간에 주소를 할당해 관리한다.

일정한 크기로 나눈 공간을 파일시스템에선 블록이라고 부른다.

디스크는 블록(1~8kb)으로 나뉘어있다.

파일 시스템은 파일 정보를 파일 테이블로 관리하며 파일 테이블엔 파일이 시작하는 블록 위치 정보도 기록되어있다.

1.1 파일의 할당 방식

하나의 파일은 여러 개의 블록으로 이루어지는데, 이 블록들을 연결하는 방식에 따라 할당 방식 결정

연속 할당

파일을 구성하는 블록들을 디스크에 연속적으로 저장

• 파일의 시작 부분만 알면 파일의 전체를 찾을 수 있다.

• 외부 단편화가 발생해 실제로 쓰이지 않는다.

불연속 할당

파일을 구성하는 블록들을 디스크의 비어있는 공간에 분산 저장

이 분산된 블록은 파일시스템이 관리

• 연결 할당

파일에 속한 데이터를 연결리스트로 관리파일 테이블에는 시작 블록에 대한 정보만 저장하고 다른 블록은 연결리스트를 통해 접근

• 인덱스 할당(i-node 방식)

파일 테이블의 블록 포인터가 데이터 블록에 직접 연결하는것이 아닌, 데이터들의 인덱스를 가지고 있는 인덱스 블록에 연결데이터가 많아 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어 연결하기 때문에 테이블 확장 가능파일 크기가 작다면 데이터를 바로 참조하는 블록 포인터 이용, 파일 크기가 크다면 간접 포인터를 이용해 많은 데이터에 접근 가능

블록 크기에 따른 문제점

• 디스크를 구성하는 블록의 크기가 너무 작을 경우공간 낭비는 줄지만 관리해야 할 블록의 수가 많아진다.

• 디스크를 구성하는 블록의 크기가 너무 클 경우관리해야하는 블록의 수는 적지만 내부단편화로 낭비되는 공간이 많아진다.

파일 저장, 삭제 방식

블록을 저장하려 할 때 마다 디스크의 빈 공간을 찾는 방식은 비효율적이다.

파일 시스템은 효율적 관리를 위해 빈 공간을 모아둔 free block list를 가지며 파일 삭제시 파일 시스템은 파일의 모든 정보를 지우는 것이 아닌, 파일 테이블의 헤더만을 삭제하고 블럭을 free block list에 추가

사용자는 파일이 삭제된 것 처럼 느끼지만 사용했던 블록의 데이터는 그대로 남아 있어 포렌식을 통해 데이터를 복구할 수 있다.

알고리즘