[인프런 워밍업클럽 CS 2기] 3주차 발자국 - elly님의 블로그 - 인프런

3주차 학습 내용

'그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 3(Unit 6~10)
'그림으로 쉽게 배우는 운영체제' Section 8, 9, 10

'그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 3(Unit 6~10)

Section 3. 알고리즘

정렬 - 병합정렬(Merge Sort)

divide and conquer - 분할 정복
- 해결하기 힘든 문제가 발생한다면 이걸 한 번에 해결하려고 하지 말고,
  해결하기 쉬울 정도로 문제를 쪼갠 다음 하나씩 해결하라
- 원소를 하나일 때까지 쪼개고, 역순으로 순서에 맞게 하나의 배열로 병합해줌
  (재귀함수를 호출한 모양과 비슷함)

코드 구현

function MergeSort(arr, leftIndex, rightIndex) {
	if(leftIndex < rightIndex) {
		let midIndex = parseInt((leftIndex + rightIndex) / 2);
		MergeSort(arr, leftIndex, midIndex);
		MergeSort(arr, midIndex + 1, rightIndex);
		Merge(arr, leftIndex, midIndex, rightIndex);
	}
}

function Merge(arr, leftIndex, midIndex, rightIndex) {
	let leftAreaIndex = leftIndex;
	let rightAreaIndex = midIndex + 1;
	
	let tempArr = [];
	tempArr.length = rightIndex + 1;
	tempArr.fill(0, 0, rightIndex + 1);
	
	let tempArrIndex = leftIndex;
	while(leftAreaIndex <= midIndex && rightAreaIndex <= rightIndex) {
		if(arr[leftAreaIndex] <= arr[rightAreaIndex]) {
			tempArr[tempArrIndex] = arr[leftAreaIndex++];
		} else {
			tempArr[tempArrIndex] = arr[rightAreaIndex++];
		}
		tempArrIndex++;
	}
	
	if(leftAreaIndex > idIndex) {
		for(let i = rightAreaIndex; i <= rightIndex; i++) {
			tempArr[tempArrIndex++] = arr[i];
		}
	} else {
		for(let i = leftAreaIndex; i <= midIndex; i++) {
			tempArr[tempArrIndex++] = arr[i];
		}
	}
}

병합정렬 성능
- 성능측정 부분은 Merge() 함수 내 흩어진 배열을 합치는 부분
  - 하나의 데이터와 하나의 데이터가 두 개로 합쳐질 때 비교 연산을 두 번 함
  - 두 개의 데이터와 두 개의 데이터가 네개로 합쳐질 때 비교가 네 번 이뤄짐
- 각 단계를 거칠 때마다 영역의 수가 반으로 줄어 logn이 됨
- 분할된 배열을 병합할 때는 n개의 데이터를 n번 비교하므로 O(nlogn) 성능이 나옴
병합정렬 장단점
- 장점 - 성능이 좋음(O(nlogn))
- 단점 - 이해와 구현이 어려움

정렬 - 퀵정렬(Quick Sort)

분할 정복 알고리즘으로 재귀를 사용함
퀵정렬 설명
- 정렬하기 전에 배열에 있는 숫자 중 하나를 피벗으로 설정해줌
- leftStartIndex는 피벗보다 큰 값을 만나면 멈춤
- rightStartIndex는 피벗보다 작은 값을 만나면 멈춤
- leftStartIndex, rightStartIndex의 값을 스왑해줌
- 서로 지나쳤다면 더이상 진행하지 않음
- 이상태에서 피벗과 rightStartIndex 값 스왑해줌
- 피벗값을 기준으로 오른쪽, 왼쪽을 정렬해줌

코드 구현

function quickSort(arr, left, right) {
	if(left <= right) {
		let pivot = divide(arr, left, right);
		quickSort(arr, left, pivot - 1);
		quickSort(arr, pivot + 1, right);
	}
}

function divide(arr, left, right) {
	let pivot = arr[left];
	let leftStartIndex = left + 1;
	let rightStartIndex = right;
	
	while(leftStartIndex <= rightStartIndex) {
		while(leftStartIndex <= right && pivot >= arr[leftStartIndex]) {
			leftStartIndex++;
		}
		
		while(rightStartIndex <= (left + 1) && pivot >= arr[rightStartIndex]) {
			rightStartIndex++;
		}
		
		if(leftStartIndex <= rightStartIndex) {
			swap(arr, leftStartIndex, rightStartIndex);
		}
	}
	
	swap(arr, left, rightStartIndex);
	return rightStartIndex;
}

function swap(arr, index1, index2) {
	let temp = arr[index];
	arr[index1] = arr[index2];
	arr[index2] = temp;
}

let arr = [5, 3, 7, 2, 6, 4, 9, 1, 8];

console.log("==== 정렬 전 ====");
console.log(arr);

quickSort(arr, 0, arr.length - 1);

console.log("==== 정렬 후 ====");
console.log(arr);

퀵 정렬의 성능
- 피벗이 매번 배열의 반을 가르는 경우
  - O(nlogn)
- 피벗이 배열을 반으로 가르지 않고 한쪽에 쏠리는 경우 - 최악의 경우
  - O(n^2)
- 성능만 보면 병합 정렬이 더 좋다고 볼 수 있는데, 실제로 비교하면 퀵정렬이 더 적은 비교와 더 적은 메모리 공간을 차지하기 때문에 더 좋은 알고리즘으로 평가됨
- 퀵정렬의 장단점 - 병합정렬과 동일

동적 프로그래밍 - 메모이제이션

재귀의 단점

피보나치 수열

피보나치 수열 코드

function fibonacci(n) {
	if(n == 0 || n == 1) return n;
	return fibonacci(n - 2) + fibonacci(n - 1);
}

console.log(fibonacci(5));

성능이 좋지 못함 - 반복 계산
- 단점 - 이미 계산했던 것을 다시 또 계산하게 됨

메모이제이션

재귀의 문제점 해결방법
계산 결과를 저장해두고 사용
해시테이블 사용

피보나치 수열 코드를 메모이제이션을 사용해 수정

function fibonacci1(n) {
	if(n == 0 || n == 1) return n;
	return fibonacci(n - 2) + fibonacci(n - 1);
}

function fibonacci2(n) {
	if(n == 0 || n == 1) return n;
	
	if(memo[n] == null) {
		memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo);
	}
	return memo[n];
}

let start = new Date();
console.log(fibonacci1(40));
let end = new Date();
console.log("fibonacci1 함수 실행시간 : ${end - start}ms");

let start = new Date();
console.log(fibonacci2(40, {}));
let end = new Date();
console.log("fibonacci2 함수 실행시간 : ${end - start}ms");

메모이제이션 장단점
- 장점
  - 성능 O(n)을 보임
  - 재귀덕분에 하향식 계산 방식으로 어려운 문제를 간단하게 해결할 수 있음
  - 중복 계산을 하지 않아서 속도가 빠름
- 단점
  - 메모리 영역을 사용함(ex, 캐시)

동적 프로그래밍 - 타뷸레이션
- 상향식 계산 방식으로, 계산에 필요하지 않을 수 있는 값도 미리 계산해 테이블에 저장해둠
- 코드 구현
```
function fibonacci1(n) {
	if(n == 0 || n == 1) return n;
	return fibonacci(n - 2) + fibonacci(n - 1);
}

function fibonacci2(n) {
	if(n == 0 || n == 1) return n;
	
	if(memo[n] == null) {
		memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo);
	}
	return memo[n];
}

function fibonacci3(n) {
	if(n <= 1) return n;
	
	let table = [0, 1];
	
	for(let i = 2; i <= n; i++) {
		table[i] = table[i - 2] + table[i - 1];
	}
	return table[n];
}

let start = new Date();
console.log(fibonacci1(40));
let end = new Date();
console.log("fibonacci1 함수 실행시간 : ${end - start}ms");

let start = new Date();
console.log(fibonacci2(40, {}));
let end = new Date();
console.log("fibonacci2 함수 실행시간 : ${end - start}ms");

let start = new Date();
console.log(fibonacci3(40));
let end = new Date();
console.log("fibonacci3 함수 실행시간 : ${end - start}ms");
```
- 성능
  - 메모이제이션은 여러번의 함수 호출로 메모리 공간에 스택을 차지하고, 메모이제이션을 위한 해시 테이블 공간까지 차지하기 때문에 메모리를 더 많이 사용함
  - 타뷸레이션은 적은 메모리 사용임에도 불구하고 빠른 시간을 보임
- 메모이제이션 vs 타뷸레이션
  - 메모이제이션
    - 재귀를 이용해 문제를 하향식으로 해결함
    - 재귀만 이용한다면 중복 계산을 하기 때문에 성능의 문제가 발생했는데 계산 결과를 저장하는 방식으로 단점을 해결함
    - 해결하기 힘든 문제를 하향식으로 접근하고, 더 많은 메모리를 이용해 성능을 향상시킴
    - 이러한 이유로 분할 정복을 해결할 때 재귀가 더 직관적이라면 메모이제이션을 이용하는 것이 유리함
  - 타뷸레이션
    - 재귀가 직관적이지 않을 때는 상향식 접근인 타뷸레이션을 이용해 메모리도 절약하고 속도도 빠르게 할 수 있음

'그림으로 쉽게 배우는 운영체제' Section 8, 9, 10

Section 8. 가상메모리

가상메모리 개요
- 컴퓨터마다 실제 메모리 크기가 다른데, 만약 운영체제나 프로세스가 특정 크기에서 동작하도록 만들어졌다면 그 크기보다 작은 메모리를 가진 컴퓨터에서는 실행되지 않음 → 가상 메모리는 이 문제를 해결함
- 가상 메모리
  - 프로세스는 운영체제의 영역이 어디있는지, 물리 메모리의 크기가 얼마나 큰지 몰라도 됨
  - 프로세스는 메모리 관리자에게 요청만 하면됨
  - 메모리 관리자는 프로세스의 요청이 있으면 그에 맞는 물리 메모리로 연결시켜줌
  - 가상메모리의 크기는 이론적으로는 무한대이지만 실제로는 물리 메모리 크기와 CPU의 비트 수로 결정됨 (ex, 32bit CPU(대략 4GB) → 가상 메모리 크기도 4GB가 됨)
- 가상메모리로 프로세스들 실행시키는 방법
  - 물리메모리 내용의 일부를 하드 디스크에 있는 스왑영역으로 옮기고, 처리가 필요할 때 물리 메모리로 가져와 실행시키기 때문에 운영체제와 프로세스 5개를 전부 실행시킬 수 있음
- 동적주소변환(Dynamic Address Translation)
  - 메모리 관리자는 물리메모리와 스왑영역을 합쳐서 프로세스가 사용하는 가상주소를 물리주소로 변환함
  - 동적 주소 변환을 거치면 프로세스는 마음대로 사용자 데이터를 물리 메모리에 배치할 수 있음
  - 메모리 관리자의 역할
    - 물리 메모리를 어떻게 나눌지
    - 프로세스를 어디다 배치할지
    - 부족한 물리 메모리는 어떻게 처리할지 등등을 위해 복잡한 과정을 거침
- 가상 메모리 시스템의 메모리 할당 방법
  - 가상 메모리 시스템에서는 운영체제 영역을 제외한 나머지 영역을 일정한 크기로 나누어서 프로세스에게 할당함
  - 할당하는 방식은 메모리 분할방식과 마찬가지로 ‘가변 분할 방식’, ‘고정 분할 방식’으로 나뉨
    - 가변 분할 방식(세그멘테이션)
      - 단점 - 외부 단편화
    - 고정 분할 방식(페이징)
      - 단점 - 내부 단편화
    - 각각의 단점을 보완한 ‘세그멘테이션-페이징 혼용기법 ’ 사용
  - 세그멘테이션-페이징 혼용기법
    - 가상메모리 시스템에서 가상주소는 메모리나 스왑영역 한 곳 중에 위치
    - 메모리 관리자는 가상주소와 물리주소를 일대일 매핑 테이블로 관리함
세그멘테이션(배치정책)
- 가변 분할 방식을 이용하는 세그멘테이션 기법
  - 프로그램은 함수나 모듈등으로 세그먼트 구성
    - 프로그램(사용자) 관점 메모리 - 코드, 데이터, 힙, 라이브러리, 스택 각각 구성(인접할 필요 없음)
    - 프로세스 관점 메모리 - 코드, 데이터, 힙, 스택 영역을 서로 인접한 것처럼 바라봄
  - 논리주소
    - 사용자, 프로세스, CPU가 바라보는 주소
    - 실제 물리주소로 변환은 중간에서 메모리 관리자(MMU)가 해줌
  - 메모리 관리자가 논리주소 → 물리주소 변환 방법
    - 메모리 관리자가 가지고 있는 세그멘테이션 테이블에 Base Address, Bound Address(Segment 크기) 정보가 저장되고 이걸 이용해 물리 메모리 주소를 계산함
    - 운영체제는 컨텍스트 스위칭을 할 떄마다 메모리 관리자 내에 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야함 → 굉장히 무거운 동작
    - 논리주소가 Bound Address보다 작다면, 논리주소 + Base Address 로 물리주소를 구함
    - 논리주소가 Bound Address보다 크다면, 메모리를 침범했다고 생각하고 에러를 발생
  - 세그멘테이션 장점
    - 메모리를 가변적으로 분할할 수 있고, 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있음 → 공유와 각 영역에 대한 메모리 접근보호가 편리함
  - 세그멘테이션 단점
    - 가변 분할 방식의 단점인 “외부 단편화”가 발생함
페이징(배치정책)
- 고정분할방식을 이용한 페이징
- 세그멘테이션 기법은 외부 단편화 문제가 있기 때문에 이를 해결하기 위해 고안됨
- 페이징
  - 메모리를 할당할 때 정해진 크기의 페이지로 나눔
  - 모든 페이지는 크기가 같기때문에 관리가 편하고, 일정한 크기로 나눴기 때문에 외부 단편화 현상이 일어나지 않음
  - 논리주소공간에서의 페이징 → 페이지
  - 물리주소공간에서의 페이징 → 프레임
- 페이징의 주소변환 방법
  - 메모리 관리자가 “페이지 테이블”을 통해 CPU에서 전달받은 논리주소가 몇번 페이지, 오프셋은 얼마인지 알아냄
  - 메모리 관리자 내에 Page Table Base Register(PTBR)를 이용해서 물리 메모리에 있는 페이지 테이블을 찾고, 페이지 번호를 인덱스로 프레임 번호를 알아내고, 오프셋을 이용해 물리주소로 변환을 함
  - 페이지 테이블에 Invalid로 표시되어 있으면 스왑영역, 즉 하드디스크레 저장되어 있다는 의미임
  - PTBR은 운영체제가 컨텍스트 스위칭을 할 때마다 해당 프로세스의 것으로 업데이트 해줌
- 세그멘테이션 vs 페이징 차이점
  - 페이지의 크기가 다름
  - 세그멘테이션은 프로세스마다 크기가 달라 Bound Address를 가지고 있지만, 페이징은 모든 페이지의 크기가 동일해서 크기를 표현하는 Bound Addresss는 필요하지 않음
    - 페이징은 이런 특성때문에 외부단편화는 발생하지 않지만 내부단편화가 발생함 (정해진 크기의 페이징보다 프로세스의 정보가 작으면 그만큼 공간이 낭비됨)
    - 세그멘테이션의 단점과 비교하면 많은 고간이 낭비되는게 아니라서 심각하게 생각하지 않음
  - 세그멘테이션은 논리적인 영역별로 세그먼트를 나눔(코드, 데이터, 스택, 힙 영역), 그러나 페이징은 페이지의 크기가 고정되어 있어 논리적인 영역별로 나누는 것이 아니라 페이지로 나누기 때문에 논리적인 영역을 나눌 수 없음 그래서 특정 영역만 공유하거나 권한을 부여하는게 더 어려움
    - 페이징에서 가장 신경써야하는 것은 페이지 테이블 크기임
    - 각 프로세스마다 페이지 테이블을 가지고 있는데 프로세스가 많아질수록 페이지 테이블도 많아지기 때문에 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어듦
    - 실제로 메모리 관리자가 참조하는 페이지 테이블도 물리 메모리의 운영체제 영역에 저장되어 있기 때문에 페이지 테이블 크기가 너무 크면 사용자 영역이 부족하게 됨 → 페이지 테이블의 크기를 적절하게 유지하는 것이 굉장히 중요함
페이지드 세그멘테이션(배치정책)
- 페이징과 세그멘테이션의 각각의 장점을 취한 방식 → 새로운 단점이 생기기도 함
  - 세그멘테이션 장점
    - 가변 분할 방식이라서 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 세그먼트로 나눠서 관리할 수 있음
    - 그에 따라 다른 프로세스와 공유하기도 편하고, 각 영역에 대한 메모리 접근보호를 하기가 쉬움
  - 페이징 장점
    - 고정분할 방식으로 메모리를 효율적으로 관리할 수 있음
- 메모리 접근 권한
  - 메모리의 특정 번지에 부여된 권한으로 읽기(Read), 쓰기(Write), 실행(Execute) 세 가지가 있음
  - 프로세스는 코드 여역, 데이터 여역, 스택 영역, 힙 영역이 있는데 각 영역마다 접근 권한이 있음
  - 코드 영역
    - 프로그램 그 자체이기 때문에 수정되면 안되므로, 읽기와 실행 권한만 있음
  - 데이터 영역
    - 일반변수, 전역변수, 상수로 선언한 변수가 저장되기 때문에 읽기 권한이 있고, 쓰기 권한은 있거나 없거나 함 실행권한은 없음
  - 스택, 힙 영역
    - 읽기, 쓰기 권한이 있고, 실행권한은 없음
  - 메모리 접근권한에 대한 검사는 가상주소에서 물리주소로 변환될 때마다 일어나는데, 만약 권한을 위반하면 에러를 발생시킴
- 페이지드 세그멘테이션
  - 세그멘테이션 기법 - 세그멘테이션 테이블은 Base Address와 Bound Address로 구성됨
  - 페이징 기법 - 페이지 테이블은 프레임 번호로 구성됨
  - 위의 둘을 혼합해 페이지드 세그멘테이션으로 만듦 (각각의 역할은 이름만 바꼈을 뿐 달라진 것은 없음)
    - 세그멘테이션 테이블에 권한 비트를 추가함
    - Base Address는 페이지 넘버로 바뀜
    - Bound Address는 이 세그먼트 페이지 개수로 바뀜
  - 페이지드 세그멘테이션의 단점은 물리메모리에 접근하기 위해서 메모리에 접근을 두 번해야 된다는 것
    - 첫번째, 세그멘테이션 테이블을 참조할 때
    - 두번째, 페이지 테이블을 참조할 때 일어남
  - 위의 단점 때문에 운영체제는 페이징과 페이지드 세그멘테이션 기법을 적절히 섞어서 사용함
디맨드 페이징(가져오기 정책)
- 프로세스가 실행될 때, 프로세스를 이루고 있는 코드영역, 데이터영역, 힙영역, 스택영역과 같은 모듈이 모두 메모리에 올라와 실행된다고 알고 있음
- 하지만 실제로는 모든 모듈이 메모리에 올라오는 것이 아니라 필요한 모듈만 올라와서 실행됨
- 도널드 커누스의 발견 - 90:10 법칙
  - 90%의 시간이 10% 코드에서 보내는 것 → 지역성 이론이라고 함
  - 지역성(두가지)
    - 공간의 지역성
      - 현재 위치에서 가까운 데이터에 접근할 확률이 높다는 것
    - 시간의 지역성
      - 최근 접근했던 데이터가 오래전에 접근했던 데이터보다 접근할 확률이 높음
    - goto문 - 지역성 이론에 따라 성능이 좋지 않기 때문에 쓰지 않는 것을 추천
    - 지역성 이론은 조만간 쓰일 데이터만 메모리에 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑영역으로 보내 성능을 향상시킴
    - 디맨드 페이징은 조만간 필요할 것 같은 데이터를 메모리로 가져오고 쓰이지 않을 것 같은 데이터는 스왑영역으로 이동시키는 정책
    - ex, 포토샵
      - 포토샵은 본 프로그램 외에도 이미지에 효과를 주는 외부 필터들이 있는데, 이 필터들을 포토샵과 같이 메모리에 모두 올리면 메모리를 많이 차지해서 프로그램이 더 무거워짐
      - 그래서 본 프로그램만 메모리에 올리고 외부 필터들은 사용자의 요청이 있을 때만 메모리로 가져오는 것이 메모리도 절약되고, 메모리를 효율적으로 관리할 수 있고, 프로세스의 응답속도도 빨라짐
- 메모리 계층구조
  - 메모리는 레지스터, 캐시, 메인 메모리, 보조저장장치로 나눌 수 있음
  - 메인 메모리에 접근하는 시간
    - 레지스터
      - CPU 내에 존재하고, CPU의 한사이클에 접근할 수 있어서 굉장히 빠름
    - 캐시
      - CPU의 수 사이클에서 수십 사이클에 접근 가능
    - 메인 메모리
      - CPU의 수백 사이클에 접근 가능
    - 보조저장장치(HDD, SSD)
      - CPU의 수백만 사이클에 접근 가능
- 디맨드 페이징은 스왑영역을 보조저장장치에 저장하는데, 성능향상을 위해서는 스왑영역으로 데이터를 이동시키는 것을 최소화 시켜야 함
- 가상 메모리의 크기 = 물리 메모리 크기 + 스왑영역임
- 스왑인, 스왑아웃
  - 스왑인 - 스왑영역에서 물리메모리로 데이터를 가져오는 것
  - 스왑아웃 - 물리메모리에서 스왑영역으로 데이터를 내보내는 것
- 메모리 관리자는 페이지 테이블을 참조해서 물리 메모리가 있는 프레임을 알아내거나 스왑영역의 위치를 알아내야 하는데, 이를 위해 페이지 테이블에는 여러가지 비트가 있음
  - 페이지 테이블을 이루고 있는 한 행을 페이지 테이블 엔트리(PTE)라고 부름
  - 페이지 테이블 엔트리(PTE)
    - 접근 비트
      - 페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트
      - 메모리에 읽거나 실행 작업을 했다면 1로 바뀌게 됨
    - 변경비트
      - 페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려주는 비트
      - 메모리에 쓰기 작업을 했으면 1로 바뀌게 됨
    - 유효비트
      - 페이지가 물리 메모리에 있는지 알려주는 비트
      - 만약 유효비트가 1이라면 페이지가 스왑영역에 있고, 0이라면 물리 메모리에 있다는 의미임
    - 읽기, 쓰기, 실행 비트
      - 권한 비트로 해당 메모리에 접근권한이 있는지 검사하는 비트
  - 프로세스가 가상 메모리에 접근요청을 했을 때
    - 메모리 관리자는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아냄
    - 만약 물리 메모리에 없다면 Page Fault라는 인터럽트를 발생시킴
    - Page Fault가 발생하면 보조저장장치의 스왑영역에 접근하게 되고 해당 프로세스는 대기상태가 됨
    - 스왑영역에 있는 데이터가 메모리에 올라가는 작업을 시작하고, 메모리에 올라갔다면 대기상태에 있던 프로세스는 다시 실행하게 됨
  - 물리 메모리와 스왑영역에서 어떻게 참조되는가(세가지)
    - 스왑이 필요없는 경우
      - ex, 프로세스가 페이지 0을 요청
        페이지 테이블의 0번 인덱스를 살펴보면 유효비트 0, 프레임 넘버 1 → 해당 주소가 물리메모리의 1번 프레임
        물리 메모리에 있는 1번 프레임에 접근해 데이터를 참조함
    - 스왑영역에 있는 데이터를 참조하는 경우
      - ex, 프로세스가 페이지 2번을 요청
        
        페이지 테이블의 2번 인덱스를 살펴보면, 유효비트가 1이고 프레임 넘버가 2임 → 페이지가 스왑영역 2번에 있다는 뜻
        물리메모리에 적절히 빈 공간을 찾음
        스왑영역 2번에 저장된 C를 물리메모리 3번 프레임으로 가져오고
        페이지 테이블에서 해당 엔트리의 유효비트를 0으로, 프레임 넘버를 3으로 수정함
        프로세스에게 데이터를 참조하게 해줌
    - 물리메모리가 꽉찼을 때 스왑영역에 있는 데이터를 참조하는 경우
      - ex, 프로세스가 페이지 1번을 요청했다고 가정
        
        페이지 테이블 1번 인덱스를 살펴보면, 유효비트 1, 프레임 넘버 0 → 페이지가 스왑영역 0번에 있음
        물리메모리로 가져오기 위해 적절한 빈공간을 찾지만 꽉 차서 여유가 없음
        현재 물리 메모리에서 필요하지 않다고 판단하는 영역을 스왑영역으로 옮김
        A가 필요하지 않다고 가정하고 스왑영역 3번으로 옮김
        페이지 테이블에서 0번 인덱스의 유효비트를 1, 프레임 넘버를 3으로 변경
        물리메모리 빈공간이 된 1번으로 B를 가져옴
        페이지 테이블에서 1번 인덱스의 유효비트를 0으로, 프레임 넘버를 1로 수정함
        프로세스에게 데이터를 참조하게 해줌
      - 스왑인(스왑영역 → 물리메모리), 스왑아웃(물리메모리 → 스왑영역) 시, 어떤게 적절한지는 운영체제가 판단함 → 페이지 교체 알고리즘
페이지 교체정책
- 메모리가 꽉찼을 때, 어떤 페이지를 스왑영역으로 보낼지 결정하는 정책임
  - 프로세스는 데이터 접근을 위해 메모리를 참조하는데, 해당 데이터가 메모리에 없으면 Page Fault가 발생함
  - Page Fault가 발생하면, 해당 페이지를 스왑영역에서 메모리로 불러들여야하는데 메모리가 꽉차서 공간이 없다면 메모리에 있는 페이지 중 하나를 선택해서 스왑영역으로 옮겨야함
  - 메모리에 있는 페이지를 스왑영역으로 옮길 때 어떤 페이지를 선택할지 결정하는 정책을 페이지 교체 정책이라고 부르고, 페이지 교체 정책에는 여러가지가 있음
- 페이지 교체 정책의 방법들
  - 무작위로 선택하는 방법(Random)
    - 지역성을 고려하지 않기 때문에 자주 사용되는 페이지가 선택될 때도 있어 성능이 별로 좋지 않음
    - 그래서 거의 사용되지 않음
  - 메모리에 들어온지 가장 오래된 페이지를 선택하는 방법(FIFO)
    - 자주 쓰이는 페이지가 먼저 들어왔다는 이유로 해당 페이지가 교체되면 공평하지 않음
    - 위의 단점이 있지만 구현이 간단하고 성능도 꽤 괜찮아서 조금 변형해서 많이 쓰임
  - 앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법(Optimum)
    - 사실상 구현이 불가능한 이론적인 선택방법
    - 구현이 불가능해서 필요가 없을 것 같지만, 다른 알고리즘과 성능 비교를 할 때 참조용으로 쓰임
  - 최근에 가장 사용이 적은 페이지를 선택하는 방법(LRU - Least Recently Used)
    - 지역성 이론의 시간의 지역성에 따르면 최근 사용한 데이터가 앞으로도 사용될 확률이 높기 때문에 최근에 가장 사용을 적게한 페이지가 앞으로도 사용될 확률이 적다는 결론이 나옴
    - 실제로도 Optimum 알고리즘에 근접한 성능을 보임
    - 그러나 프로그램이 지역성을 띄지 않을땐 성능이 떨어지게됨
    - 페이지 테이블 엔트리는 여러개의 비트와 페이지 넘버가 저장되는데, 이곳에 시간을 기록하려면 비트가 많이 필요하게됨
    - 많은 비트를 준비하기 어려우므로 실제 LRU를 구현할 때는 접근비트를 이용해서 LRU에 근접하게 구현함
- Optimum vs FIFO vs LRU 비교
  - ex, 페이지가 A B C A C D A D C A B 순서대로 요청되는 상황
    - 세 방법 모두 메모리가 비어있기 때문에 처음 요청에서는 전부 Page Fault가 발생함
    - A 요청 들어옴
      - 세 알고리즘 모두 Page Fault가 일어나지 않음
    - C 요청 들어옴
      - 세 알고리즘 모두 Page Fault가 일어나지 않음
    - D 요청 들어옴
      - Page Fault 발생
        Optimum
        뒤에 들어오는 요청을 훑어봄
        페이지 B가 가장 사용되지 않을 것을 알기 때문에 페이지 B를 스왑영역으로 옮기고, B가 있던 자리에 D를 가져옴
        FIFO
        먼저 들어온 페이지가 먼저 나가기 때문에 가장 먼저 들어온 페이지 A를 스왑영역으로 보내고, A가 있던 자리에 D를 가져옴
        LRU
        최근에 가장 사용이 적은 페이지가 나가기 때문에 최근에 들어온 페이지의 참조 수를 계산함
        A 2번, B 1번, C 2번으로 B가 가장 덜 사용됐으니 B를 스왑영역으로 옮기고 B가 있던 자리에 D가 들어옴
- 빌레이디의 역설(Belady’s Anomaly)
  - Page Fault를 줄이려고 메모리를 더 늘려서 프레임 수를 늘렸는데, 오히려 Page Fault가 더 많이 발생하는 현상
    → FIFO의 가장 큰 문제임
  - FIFO에서만 발생하며 LRU에서는 발생하지 않음
- LRU 문제점
  - 시간을 기록해야하는 LRU는 구현이 힘듦
  - 시간을 기록할 bit가 많이 필요
  - 많은 bit가 있어도 시간이 아주 오래 지난다고 가정하면 어쩔수없이 오버플로우가 발생 → 오버플로우로 값이 초기화되면서 시간을 올바르게 표현할 수 없게됨
- 클락 알고리즘
  - LRU 알고리즘과 유사하게 구현하는 방법
  - 접근비트 하나만 이용
    - 일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화함
    - 접근비트의 초기값은 0으로 설정되어 있고, 만약 페이지가 참조되었다면 1로 설정됨
  - 페이지를 원형으로 연결함
    - 스왑영역으로 옮길 페이지를 포인터로 가르키는데, 이 포인터를 클락 핸드라고 부름
    - 클락 핸드는 시계방향으로 돌게됨
    - 만약 Page Fault가 발생해서 스왑영역으로 보내야하는 상황이 나오면, 클락 핸드는 현재 참조하고 있는 페이지의 접근비트를 봄
    - 만약 접근비트가 1이라면 해당 접근비트를 0으로 바꾸고, 클락핸드가 다음 페이지를 가르킴
    - 이렇게 반복하다가 접근비트가 0인 페이지를 발견하면, 해당 페이지를 스왑영역으로 보냄
  - 향상된 클락 알고리즘(Enhanced Clock Algorithm)
    - 이 알고리즘은 접근비트만 이용하는 것이 아니라 변경비트까지 봄
    - 스왑 영역으로 보내지는 순위가 가장 높은 것은 접근비트가 0이고, 변경비트도 0인 페이지임
    - 그 다음으로 접근비트가 0, 변경비트가 1인 페이지임
    - 그 다음으로 접근비트가 1, 변경비트가 0인 페이지임
    - 마지막으로 접근비트가 1, 변경비트가 1인 페이지가 교체됨
- FIFO를 사용하는 경우
  - LRU에서는 접근비트를 이용하는데, 하드웨어적으로 접근비트를 지원하지 않는 시스템에서는 FIFO를 이용할 수 밖에 없음
  - 어쩔 수 없이 FIFO를 이용하기 위해 성능을 높이는 방법을 고안함
  - 2차 기회 페이지 교체 알고리즘
    - FIFO방식에서 자주 사용하는 페이지에게는 또 한번의 기회를 줌
    - FIFO방식과 동일하게 동작하지만, 만약 Page Fault없이 페이지 접근에 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시켜주는 방식
    - 이 알고리즘은 LRU보다는 안좋고, FIFO보다는 좋음
스레싱과 워킹셋
- CPU 스케줄링
  - CPU 사용률을 높이는 것이 목표
    - CPU 사용률을 높이기 위해서는 동시에 실행하는 프로세스의 수, 멀티프로그래밍의 정도를 올리는 것
    - 동시에 실행하는 프로세스의 수가 늘어나면, 어떤 프로세스가 I/O작업으로 CPU를 사용할 수 없을 때 다른 프로세스로 컨텍스트 스위칭을 해서 CPU 사용률을 높일 수 있음
    - CPU 사용률을 위해 멀티프로그래밍의 정도를 높였으면, 프로세스들이 필요로하는 공간이 있기때문에 물리메모리에 프레임을 할당해야함
    - 물리메모리의 크기는 한계가 있기 때문에 모든 프로세스의 모든 프레임을 물리메모리에 올릴 수 없고, 일부는 스왑영역에 저장됨
  - 멀티프로그래밍 정도가 늘어나는 경우에 문제가 나타남
    - 멀티프로그래밍 정도가 늘어나면 제한된 물리메모리에 모든 프로세스를 올려야하고, 당장 실행되는 프레임을 제외한 나머지 프레임들은 스왑영역에 저장되고 Page Fault가 많이 발생하게 됨
    - CPU가 작업하는 시간보다 스왑작업의 시간이 더 길어지고, CPU 사용률은 떨어지게됨
    - CPU 스케줄러는 CPU 사용률이 낮아지면, 더 많은 프로세스를 메모리에 올리게되고, 이렇게 반복하다보면 어느새 CPU 사용률이 0에 가깝게 떨어지게됨
    - 스레싱
      - CPU 사용률을 높이려했지만 오히려 더 떨어지는 상황
      - 근본적인 원인은 물리메모리의 크기가 부족한 것
      - 하드웨어적으로 해결하려면 메모리 크기를 늘리면 됨
        그러나 4GB 램에서 16GB 램으로 올려도 성능향상을 느끼기 힘듦
        현재 메모리가 프로세스들이 작업을 하는데 충분한 크기라서 스레싱이 발생하지 않는다면 크기를 늘려도 별 다른점이 없기 때문임
      - 운영체제가 스레싱을 소프트웨어적으로 해결하기 위한 방법
        한 프로세스가 실행될 때 너무 많은 페이지를 할당하면 다른 프로세스가 사용할 페이지가 줄어들기 때문에 효율이 떨어지게됨
        반대로 너무 적은 페이지를 할당하면 빈번한 Page Fault가 발생하고, 스왑요청이 많아 스레싱이 발생하게됨
        이를 해결하기 위한, 프로세스가 실행되는 동안 해당 프로세스에게 맞는 적절한 페이지 수 결정 방법
        프로세스가 실행되면 일정량의 페이지를 할당 후, 만약 Page Fault가 발생하면 더 많은 페이지를 할당하고, 반대로 Page Fault가 너무 적게 발생하면 페이지를 과하게 할당해 메모리가 낭비되는 것이라고 판단하고 페이지를 회수함
        어떤 페이지를 유지할 것인지 결정 방법
        지역성 이론을 따름
        현재 메모리에 올라온 페이지는 다시 사용할 확률이 높기 때문에 하나의 세트로 묶어서 메모리에 올림 → 워킹셋
        워킹셋은 프로세스가 준비상태에서 실행상태가 되는 컨텍스트 스위칭을 할 때 사용됨

Section 9. 입출력

주변장치(I/O 디바이스, 저장장치)
- 주변장치 종류
  - 그래픽카드, 하드디스크, SSD, 키보드, 마우스 등이 있음
    - 주변장치들은 메인보드에 있는 버스로 연결됨
  - 버스
    - Address 버스, Data 버스, Control 버스로 이루어져 있음
    - I/O 디바이스는 이 세가지 버스를 따로 받을 수 있음
  - 외부 인터페이스
    - 각 하드웨어에 맞게 존재함
  - 각종 레지스터
    - 장치의 상태와 데이터를 보관할 수 있음
    - 입출력 작업을 할 때 데이터를 저장하는 역할을 함
    - 값들은 CPU가 사용하기위해 메모리로 이동되기도 함
- 데이터의 전송단위에 따른 주변장치 분류
  - 데이터의 전송단위가 캐릭터(글자)인지, 블록인지에 따라 나뉨
    - 캐릭터 디바이스
      - 마우스, 키보드, 사운드카드, 직별렬포트 등
      - 데이터 전송 단위가 캐릭터(글자)로 상대적으로 크기가 작음
    - 블록 디바이스
      - 하드디스크, SSD, 그래픽카드 등
      - 데이터 전송 단위가 블록(범위)로 상대적으로 크기가 큼
- 각 장치 세부 설명
  - 버스
    - 예전에는 주변장치들을 하나의 버스로 연결해서 사용함
    - CPU가 작업을 하다가 I/O 명령을 만나면 직접 입출력장치에서 데이터를 가져왔는데 입출력중에는 다른 작업을 하지 못했기 때문에 CPU사용률이 떨어짐
    - 이를 해결하기 위해 입출력 제어기(I/O Controller)와 여러개의 버스가 추가됨
    - CPU는 I/O 명령을 만나면 입출력 제어기에게 입출력작업을 맡기고 다른 작업을 실행함
    - 입출력 제어기
      - 시스템 버스, 입출력 버스로 구분하여 두 개의 채널을 가지고 있음
      - 시스템 버스
        고속으로 작동하는 CPU와 메모리가 사용
      - 입출력 버스
        주변장치가 사용
      - 입출력 버스는 세부적으로 느린장치와 빠른장치를 구분하기 위해 다시 고속 입출력 버스, 저속 입출력 버스 두 개의 채널로 나뉨 → 느린장치와 빠른장치로 구분 해 속도차이로 인한 병목현상을 해결함
  - 그래픽 카드
    - 그래픽 카드가 다루는 데이터는 매우 대용량이라 고속 입출력 버스로도 감당이 안됨
    - 그에 따라 그래픽 카드는 입출력 버스에 있지 않고, 시스템 버스에 바로 연결해 사용함
  - 입출력 제어기
    - 입출력 제어기는 여러 주변장치를 처리하는데 입출력 버스에서 온 데이터를 메모리로 옮김
    - 메모리는 CPU의 명령으로 움직이기 때문에 입출력 제어기가 메모리에 접근하기 위해서는 CPU가 필요함
    - 입출력 제어기가 CPU의 도움이 필요없도록 DMA(Direct Memory Access - 직접 메모리 접근) 제어기가 추가됨
    - 입출력 제어기는 DMA로 데이터를 직접 메모리에 저장하거나 가져올 수 있음
    - Memory Mapped I/O
      - CPU와 DMA가 사용하는 메모리가 겹치지 않도록 CPU가 사용하는 메모리 영역과 DMA가 사용하는 메모리 영역을 나눔
마우스/키보드
- 마우스
  - 볼 마우스
    - 회전을 감지해서 움직임을 처리하는 방식
  - 광학 마우스
    - 아래쪽에 작은 카메라가 표면으로 초당 1500회가 넘는 사진을 찍어 마우스의 디바이스 컨트롤러 내 DSP(Digital Signal Processor)로 보냄
    - DSP는 이 사진을 분석해 마우스의 X축 좌표와 Y축 좌표 움직임을 캐치함
    - DSP가 마우스의 움직임과 클릭같은 데이터를 감지하면, 디바이스 컨트롤러는 CPU에게 인터럽트를 보내고, 마우스 드라이버가 동작해서 데이터를 읽어감
    - 마우스 드라이버는 운영체제에게 이벤트 신호를 주는데, 운영체제는 이 이벤트 Foreground 애플리케이션으로 전달해주고 해당 애플리케이션은 받은 마우스 이벤트 처리를 함
- 키보드
  - 사용자가 키보드 버튼을 누르면 키보드의 디바이스 컨트롤러가 어떤 키를 입력 받았는지 알아냄
  - CPU에게 인터럽트를 보내고 키보드 드라이버는 운영체제에게 이벤트를 보냄
  - 운영체제는 Foreground 애플리케이션으로 이 이벤트를 전달해주고, 애플리케이션에서 해당 키에 맞는 동작을 수행함
하드디스크/Flash Memory(SSD)
- 하드디스크 구조
  - spindle
  - platter
    - 여러개의 트랙으로 구성됨
    - 표면에 자성이 있어 N극을 띄면 0, S극을 띄면 1로 인식함
    - 보통 하드디스크의 플래터 수는 2개 이상임
    - 실린더(cylinder)
      - 트랙은 다시 여러개의 섹터로 나뉘는데, 섹터가 하드디스크의 가장 작은 단위임
  - disk Arm
    - 읽기/쓰기 헤드로 플래터의 표면을 읽음
  - read/write head
    - 헤드는 disk Arm에 고정되어 있기 때문에 모든 헤드는 항상 같이 움직임
    - 헤드가 움직이면 이 헤드들은 여러 개의 플래터를 가리키게 되는데, 이때 여러개의 플래터에 있는 같은 트랙의 집합을 실린더(cylinder)라고 부름
- 하드디스크에서 데이터 읽어오는 예시
  - 유저프로세스가 하드디스크의 특정 섹터에 접근을 위해 요청을 보냄 (ex, 실린더 C로 가서 트랙 B에 있는 섹터 D를 읽어라)
  - 디스크암은 헤드를 실린더 C로 이동시키는데, 이를 Seek라고 부름
  - 헤드를 실린더로 이동시키는데 걸리는 시간을 Seek Time이라고 부름 → 이것때문에 하드디스크가 굉장히 느림
  - 트랙 B의 섹터 D가 헤드에 닿을 때까지 스핀들을 회전시키고, 헤드에 섹터 D가 읽히면 작업이 끝남
- Flash Memory
  - 요즘은 하드디스크보다 Flash Memory를 더 많이 사용함
  - 데스크탑에는 Flash Memory 이점으로 많은 사람이 SSD를 사용함
  - 핸드폰, 테블릿은 하드디스크를 넣을 큰 공간이 없어서 Flash Memory를 사용함
  - 하드디스크 vs Flash Memory
    - 하드디스크
      - 기계적으로 헤드를 움직여 속도가 많이 느리고 소음도 남
      - 자기적으로 처리하는 하드디스크는 자석을 갖다대면 데이터가 손상됨
      - 스핀들처럼 회전축같은 것들이 있어서 충격에 매우 약함
    - Flash Memory
      - 전기적으로 읽기 때문에 굉장히 빠르고 조용함
      - 자석을 갖다대도 데이터가 안전함
      - 충격에 약하지 않음
      - 그러나 특정한 지점에 데이터를 썼다면 덮어쓰기가 불가능 하다는 단점이 있음 똑같은 지점에 데이터를 쓰려면 기존에 있던 데이터를 지우고 새로 써야하는데, Flash Memory는 지우기 가능한 횟수가 정해져있음(읽기/쓰기를 반복하면 망가져 사용할 수 없음)

Section 10. 파일시스템

파일과 파일시스템
- 파일들을 하드디스크나 SSD와 같은 저장장치에 저장됨
- 사용자가 운영체제에게 요청 시, 운영체제가 하드디스크에 안전하게 저장함
- 운영체제는 파일 관리를 위해 파일 관리자를 둠 → 파일 시스템
- 파일 시스템
  - 파일 관리자는 가상메모리에서 메모리 관리자가 페이지 테이블을 이용해서 가상주소를 물리주소로 변환하는 것처럼 파일 테이블을 이용해서 파일을 관리함
  - 파일 시스템의 기능
    - 파일과 디렉토리를 만듦
    - 파일과 디렉토리의 수정, 삭제를 함
    - 다른 사용자로부터 파일을 보호하기 위해 접근권한을 관리함 (요즘 운영체제는 다중 사용자 기능을 지원하기 때문에 파일을 보호하기 위해서 꼭 필요한 기능임)
    - 파일의 내용이 손상되지 않도록 무결성을 보장함
    - 예기치 못한 사고로부터 백업과 복구를 함
    - 파일을 암호화해 파일을 보호함
  - 파일시스팀 전송단위
    - 하드디스크와 Flash Memory는 블록 디바이스임 따라서 전송단위가 블록임
    - 저장 단위는 블록이지만, 사용자는 바이트 단위로 파일에 접근이 가능해야하기 때문에 파일관리자가 중간에서 관리해줌
  - 파일확장자
    - 유닉스 운영체제에는 파일확장자가 없음
    - 윈도우즈는 파일확장자가 있음
    - 파일 내부 구성
      - 헤더, 데이터로 이루어져있음
      - 헤더
        파일의 속성들이 담겨 있음
  - 파일 디스크립터(File Descriptor)
    - 운영체제는 파일을 관리하기 위해 정보를 보관하는 파일제어블록(File Control Block, FCB)을 가지고 있는데, 이를 파일 디스크립터(File Descriptor)라고 부름
    - 파일 디스크립터는 파일마다 독립적으로 존재하고, 저장장치에 존재하다가 파일이 오픈되면 메모리로 이동함
    - 파일 디스크립터는 파일시스템(운영체제)이 관리하고, 사용자가 직접 참조할 수는 없음
    - 사용자는 파일시스템이 건내준 파일 디스크립터로 파일에 접근할 수 있음
  - 파일 종류 분류
    - 파일은 데이터의 집합으로, 데이터의 집합을 어떻게 구성하느냐에 따라 종류를 나눌 수 있음
    - 순차파일구조
      - 파일의 내용이 연속적으로 이어진 상태 (ex, 카세트테이프)
      - 파일시스템이 사용자에게 전달해준 파일디스크립터는 파일의 맨 앞에 위치해서 사용자가 쓰거나 읽기를 시작하면 처음부터 진행함
      - 파일의 다른영역으로 가고 싶을 때 - lseek함수를 이용해 파일디스크립터 위치를 옮김
      - 장점
        모든 데이터가 순서대로 기록되기 때문에 공간의 낭비가 없고 구조가 단순함
      - 단점
        특정지점에 바로 이동이 어려워 데이터를 삽입하거나 삭제하려면 탐색하는데 시간이 많이 걸림
    - 직접파일구조
      - 저장하려는 데이터를 해시함수를 통해 저장위치를 결정하는 파일구조
      - 자료구조에서 해시 테이블이라는 이름으로 불리는 방식
      - json도 이 방식임
      - 장점
        해시함수를 이용하기 때문에 데이터 접근이 굉장히 빠르다는 것
      - 단점
        해시함수의 선정이 굉장히 중요하기 때문에 해시함수를 잘 골라야한다는 점과 저장공간이 낭비될 수 있다는 점
    - 인덱스파일구조
      - 순차접근과 직접접근 방식의 장점을 취한 것으로 두가지 방식 모두 가능함
      - ex, 음악재생 프로그램의 재생목록
디렉토리
- 디렉토리란?
  - 파일을 하나의 공간이 아닌, 관련있는 파일을 모아둘 수 있게 하기 위함
  - 한 개 이상의 파일을 가질 수 있고, 자식 디렉토리도 가질 수 있음
  - 디렉토리는 여러층으로 구성됨
    - 최상위에 있는 디렉토리 - 루트 디렉토리
    - 유닉스, 리눅스에서는 루트 디렉토리를 “/”로 표시함, 디렉토리 별 구분을 위해서도 “/”를 사용함
    - 윈도우즈는 루트 디렉토리를 파티션 이름으로 사용하는데, 보통 “C:”으로 표시함
    - 윈도우즈는 디렉토리와 디렉토리 구분을 “\”로 함
    - 디렉토리도 파일임. 단지 일반 파일에는 데이터가 저장되어 있고, 디렉토리에는 파일 정보가 저장되어 있음
- 디렉토리 구조
  - 과거 - 루트 디렉토리에만 하위 디렉토리 존재했었음
  - 파일이 많아지면서 다단계 디렉토리구조가 등장함
  - 다단계 디렉토리구조
    - 어떤 디렉토리에서도 하위 디렉토리를 만들 수 있는 트리구조
    - 운영체제는 트리구조에서 순환이 생기는데, 바로가기 기능이 있기 때문임
파일과 디스크
- 파일은 메모리와 비슷한데, 페이징과 같이 전체 디스크 공간을 일정한 크기로 나누고, 그 공간에 주소를 할당해 관리함
- 일정한 크기로 나눈 공간을 파일시스템에서는 블록이라고 함 (메모리에서는 페이지라고 부름)
- 한 블록의 크기는 1~8KB
- 파일시스템은 파일정보를 파일테이블로 관리하는데, 파일이 시작하는 블록의 위치정보도 담겨있음
- 파일 내 블록 분류
  - 여러 개의 블록들로 이루어져 있는 하나의 파일에서, 그 블록들이 어떻게 연결되었는지에 따라 분류됨
  - 연속할당
    - 파일을 구성하는 블록들을 디스크에 연속적으로 저장하는 방식임
    - 파일의 시작 블록만 알면 파일의 전체를 찾을 수 있음
    - 메모리에서 세그멘테이션 기법처럼 외부 단편화가 발생하기 때문에 실제로 사용되지 않는 방식임
  - 불연속할당
    - 디스크에 비어있는 공간에 데이터를 분산해 저장하는 방식
    - 분산된 블록은 파일시스템이 관리함
    - 연결할당, 인덱스 할당이 있음
    - 연결할당
      - 파일에 속한 데이터를 연결리스트로 관리함
      - 파일테이블에는 시작 블록에 대한 정보만 저장하고, 나머지는 연결리스트를 이용해 다른 블록에 접근하는 방식
    - 인덱스할당
      - 테이블의 블록포인터가 데이터 블록에 직접 연결하는 것이 아니라 데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결함
      - 인덱스 할당은 데이터가 많아서 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어서 연결하기 때문에 테이블을 확장할 수 있음
      - 파일의 크기가 작다면, 데이터를 바로 참조하는 블록 포인터를 이용하고, 파일의 크기가 크다면 간접 포인터를 이용해 많은 데이터에 접근할 수 있음
      - 만약 더 큰 데이터가 필요하다면, 이중 간접 포인터, 삼중 간접 포인터를 이용할 수 있음 (i-node라는 이름으로 유닉스와 리눅스에서 많이 사용되고 있음)
- free block list
  - 빈 공간을 찾기위해 매번 모든 메모리를 찾지 않기 위해 빈 공간을 모아둠
  - 만약 특정 파일 삭제 시, 파일시스템은 파일의 모든 정보를 지우는 것이 아니라 파일 테이블의 헤더를 삭제하고 free block list에 추가함

회고

일주일 동안 스스로 칭찬하고 싶은 점, 아쉬웠던 점, 보완하고 싶은 점
- 칭찬하고 싶은 점 : 이번주 강의가 조금 어렵게 느껴졌지만 포기하지 않고 끝까지 잘 학습한 점
- 아쉬웠던 점 : 이번주에 회사일이 많아서 내용 중 이틀 치를 몰아서 듣게 되었는데 충분한 학습을 하지 못했다는 아쉬움이 남음
- 보완하고 싶은 점 : 중간중간 이해가 안되는 부분들이 있었는데, 그 부분을 반복학습 해야겠습니다🙌
다음주에는 어떤 식으로 학습하겠다는 스스로의 목표
- 수료식 전까지 따로 스터디 스케쥴이 없는 것 같으니 이번주 강의를 다시한번 봐야겠습니다💪