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

학습 내용

운영체제

프로세스는 메모리 관리자를 통해 메모리에 접근
메모리 관리자: 프로세스 요청이 있을 때 그에 맞는 물리 메모리로 연결시켜줌
가상 메모리
- 운영체제(0x0) 영역을 제외한 나머지 영역을 일정한 크기로 분리
  - 가변 분할 방식 (세그멘테이션)
    단점: 외부 단편화
  - 고정 분할 방식 (페이징)
    단점: 내부 단편화
  - 단점 보완: 세그멘테이션-페이징 혼용 기법 사용
세그멘테이션
- 장점: 메모리를 가변적으로 분할할 수 있음, 각 영역에
  대한 편리한 메모리 접근 보호
- 단점:
  내부 단편화 발생
- 변환 과정
  - CPU에서 논리 주소 전달
  - 메모리 관리자가 이 주소가 몇 번째 값인 확인
  - 베이스 레지스터를 이용해 물리 메모리 내 세그멘테이션 테이블 탐색
  - 세그멘테이션 번호를 인덱스로 베이스 어드레스와 바운드 어드레스 검색
페이징
- 외부 단편화 문제를 해결하기 위해 고안
- 메모리 할당 시 정해진 크기로 나눔
- 장점:
  관리 쉬움,
  외부 단편화 현상이 일어나지 않음
세그멘테이션 vs 페이징
- 대표 차이점: 페이지 크기가 다름
- 세그멘테이션은 논리 영역별로 나눔. 코드, 데이터, 스택, 힙 영역을 나눌 수 있음
  - 각 영역에 대한 공유 쉬움, 메모리 접근 보호 쉬움
- 페이징은 페이지로 나눔. 특정 영역만 공유 및 권한 부여 어려움,
  오버헤드가 적음
메모리 접근 권한
- 메모리 접근 권한: 메모리의 특정 번지에 부여된 권환 (rwx)
- 코드 영역은 프로그램 그 자체 ⇒ r-x
- 데이터 영역은 일반, 전역, 상수로 선언한 변수 포함 ⇒ rw?x
- 스택/힙 영역 ⇒ rx-
페이지드 세그멘테이션 기법
- 세그멘테이션 테이블에 권한 비트 추가 (RW, R, RWE 등)
- 과정
  - 가상 주소로 몇 번 세그먼트인지 탐색
  - 세그먼테이션 테이블에서 해당 세그먼트의 인덱스 참조
  - 해당 세그먼트가 메모리 접근 권한을 위반하는 지 검사
  - 접근 권한 위반 시 프로세스 종료
  - 위반하지 않으면 페이지 넘버와 페이지 개수를 가져옴
  - 페이지 넘버로 페이지 테이블 접근, 프레임 번호 가져옴
  - 물리 메모리 내 해당 프레임에 접근
  - 그 위치에 페이지 개수를 더해 물리 주소 구함
  - 물리메모리에 해당 프레임이 없다면 스왑 영역에서 물리메모리로 가져옴
지역성 이론
- 공간의 지역성: 현재 위치에서 가까운 데이터에 접근할 확률이 높음
- 시간의 지역성: 최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높음
디멘드 페이징: 조만간 필요할 것 같은 데이터를 메모리로 가져오고 쓰이지 않을 것 같은 데이터는 스왑영역으로 이동함
메모리 계층 구조 (CPU 접근 순):
레지스터 -> 캐시 -> 메인 메모리 -> 보조 저장 장치
스왑
- 가상 메모리 크기 = 물리 메모리 크기 + 스왑 영역
- 스왑 인: 스왑 영역 → 물리 메모리
- 스왑 아웃: 물리 메모리 → 스왑 영역
- 페이지 테이블 기반하여 물리 메모리에서 프레임을 찾을 때 없으면 Page Fault 인터럽트 발생
- 스왑이 필요없는 경우
  - 프로세스가 페이지 요청 → 인덱스로 유효 비트와 프레임 넘버 확인 ⇒ 이를 기반으로 물리 메모리 확인 ⇒ 물리 메모리의 프레임 접근 ⇒ 데이터 참조
- 스왑 영역에 있는 데이터 참조
  - 프로세스가 페이지 요청 → 인덱스로 유효 비트와 프레임 넘버 확인 → 이를 기반으로 스왑 영역 확인 →
  - 물리 메모리에서 빈 공간 확인 → 스왑 영역에 저장된 데이터를 물리 메모리의 빈 프레임에 저장 → 페이지 테이블에서 해당 엔트리의 유효 비트와 프레임 업데이트 → 프로세스에게 데이터 참조 가능하게 함
  - 물리 메모리에 빈 공간 없음 → 물리 메모리에서 필요 없는 영역을 스왑 영역으로 이동 → 필요 없는 영역의 페이지 테이블의 유효 비트와 프레임 업데이트 → 물리 메모리에 공간 생김 → 스왑 영역에서 데이터를 물리 메모리로 이동 → 페이지 테이블의 유효 비트와 프레임 업데이트 → 프로세스에게 데이터 참조 가능하게 함
페이지 교체 정책
- 메모리가 꽉 찼을 때 어떤 페이지를 스왑 영역으로 보낼 지 결정하는 정책
- 방법1: 무작위로 선택
  - 지역성을 고려하지 않아 자주 사용되는 페이지가 선택될 수도 있다
  - 성능이 좋지 않다
- FIFO 방법2: 메모리에 들어온 가장 오래된 페이지 선택
  - FIFO는 공평하지 않음 → 변형해서 쓰임
  - 구현 간단, 성능 꽤 괜찮다
- OPT 방법3: 앞으로 가장 오랫동안 쓰이지 않을 페이지 선택
  - 구현이 불가능한 이론적인 방법, 다른 알고리즘과의 성능 비교 시 사용
- LRU 방법4: 최근 사용이 가장 적은 페이지 선택
  - 시간 지역성에 따라 선택,
    OPT 알고리즘에 근접한 성능
  - 실제 구현 시 접근 비트를 이용해서 LRU에 근접하게 구현
빌레이디의 역설: Page Fault를 줄이려고 메모리를 늘려서 프레임 수도 늘렸는데 오히려 Page Fault가 더 많이 발생하는 현상
Clock Algorithm
- LRU와 가장 비슷하게 구현하는 알고리즘
- 일정 시간마다 모든 페이지의 접근 비트 초기화 (0), 페이지 참조 시 (1)
- 일정 시간마다 페이지의 참조 여부 확인
Enhanced Clock Algorithm
- 접근 비트 + 변경 비트까지 사용
2차 기획 페이지 교체 알고리즘: 자주 사용되는 페이지에게 기회를 주는 것
- Page Fault 없이 접근했다면 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장 시켜 줌 (한번만)
스레싱: CPU 사용률을 높이려 했지만 오히려 더 떨어지는 상황
워킹셋: 메모리에 올라온 페이지는 다시 사용할 가능성 많음 → 하나의 세트로 묶어서 메모리에 올림
캐릭터 디바이스 vs 블록 디바이스
- 캐릭터 디바이스
  - 마우스, 키보드, 사운드카드, 직렬/병렬 포트 등
  - 데이터 전송 단위: 캐릭터
  - 상대적으로 크기가 작음
- 블록 디바이스
  - 하드디스크, SSD, 그래픽 카드 등
  - 데이터 전송 단위: 블록 (범위)
  - 상대적으로 크기가 큼
입출력 제어기
- I/O 명령 → 입출력 제어기에 입출력 작업 맡김, 다른 작업 시
- 버스
  - 시스템 버스: 고속으로 작동 (CPU, 메모리 등)
  - 입출력 버스: 주변 창지 사용 (고속 입출력 버스 & 저속 입출력 버스 → 속도 차이로 인한 병목 현상 해결)
- DMA 제어기 Direct Memory Access: 입출력 제어기가 메모리에 접근하기 위해 필요
  - 데이터를 직접 메모리 저장, 가져옴
- Memory Mapped I/O: CPU가 사용하는 메모리 영역과 DMA가 사용하는 메모리 영역을 나누는 것
하드디스크
- 구성요소
  - 스핀들: 원판(플래터)을 회전시키는 축
  - 플래터: 데이터를 저장하는 자기 원판 (2개 이상 존재)
  - 헤드: 데이터를 읽고 쓰는 장치, 플래터 표면과 가까이 위치
  - 디스크함: 플래터와 헤드가 들어 있는 본체
- 동작 원리
  - 플래터는 자성을 이용해 데이터를 0과 1로 저장
  - 헤드는 디스크함과 함께 움직이며 데이터를 읽고 씀
  - 데이터를 읽기 위해서는:
    1. 헤드를 원하는 실린더로 이동
    2. 회전하면서 해당 섹터에 도달하면 데이터 접근
플래시 메모리: 블록 디바이스의 또 다른 종류로, 하드디스크보다 더 자주 사용됨
- 장점: 전기적 처리(조용함), 자석에 영향 없음, 내구성 좋음
- 단점: 특정 지점에 데이터 덮어쓰기 불가, 데이터 덮어쓰려면 데이터를 지워야함, 지우기 가능 횟수 제한 등등
파일 시스템
- 파일은 저장장치에 저장됨
- 파일 관리를 위해 파일 시스템이라는 파일 관리자를 둠
- 파일 시스템 기능
  - 파일/디렉토리 생성, 파일/디렉토리 수정/삭제,
    파일 권한 관리,
    무결성 보장,
    백업과 복구,
    암호화
데이터 집합 구성에 따른 분류
- 순차 파일 구조, 직접 파일 구조, 인덱스 파일 구조
파일 내 블록의 연결에 따른 분류
- 연속 할당:
  블록들을 디스크에 연속적으로 저장 (실제 사용 X)
- 불연속 할당:
  디스크의 비어있는 공간에 데이터를 분산 저장
  - 연결 할당:
    파일의 데이터를 연결 리스트로 관리
  - 인덱스 할당:
    테이블의 블록 포인터가 인덱스 블록을 연결 (i-node)

자료구조 & 알고리즘

삽입 정렬: 정렬되지 않은 영역에서 가장 앞에 있는 데이터를 꺼내 영역에 삽입하는 것

복잡하지는 않지만 성능이 좋지 않음

class InsertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let insertingDdata = arr[i]
		
    for (let j = i - 1; j >= 0; j--) {
      if (arr[j] > insertingData) {
        arr[j + 1] = arr[j]
      } else {
        break;
      }
    }
  }
}

const arr = [4, 1, 5, 3, 6, 2]

console.log(arr)  // [4, 1, 5, 3, 6, 2]
console.log(InsertionSort(arr))  // [1, 2, 3, 4, 5, 6]

병합 정렬: 분할 정복 divide and conquer: 큰 문제를 작은 문제로 나누어서 해결

재귀와 비슷한 모양

function mergeSort(arr, left, right) {
  if (left < right) {
    const mid = parseInt((left + right) / 2)
    mergeSort(arr, left, mid)
    mergeSort(arr, mid + 1, right)
    merge(arr, left, mid, right)
  }
}

function merge(arr, left, mid, right) {
  const leftArea = left;
  const rightArea = mid + 1
	
  const tmp = []
  tmp.length = right + 1
  tmp.fill(0, 0, right + 1)
	
  const tmpIndex = left;
  while (leftArea <= mid && rightArea <= right) {
    if (arr[leftArea] <= arr[rightArea]) {
    	tmp[tmpIndex] = arr[leftArea++]
    } else {
      tmp[tmpIndex] = arr[rightArea++]
    }
    tmpIndex++
  }
}

퀵 정렬: 분할 정복 알고리즘의 일종

성능: O(NlogN), 최악의 경우 O(N^2)

더 적은 비교와 적은 메모리 공간을 차지하지 때문에 병합 정렬보다 좋음

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

function divide(arr, left, right) {
  const pivot = arr[left]
  let leftStartIndex = left + 1;
  let rightStartIndex = right;
	
  while(leftStartIndex <= rightStartIndex) {
    while(leftStartIndex <= right && pivo >= 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) {
  const tmp = arr[index1]
  arr[index1] = arr[index2]
  arr[index2] = tmp
}

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

// 정렬 전
console.log(arr)

// 정렬 후
quickSort(arr, 0, arr.length - 1)
console.log(arr) // [1, 2, 3, 4, 5, 6, 7, 8, 9]

다이나믹 프로그래밍 - 메모이제이션
- 하향식 계산, 계산하려는 데이터가 없으면 값을 저장하고 있다면 가져다쓰는 방식
- 일반 재귀 시간복잡도: O(N^2), 다이나믹 프로그래밍 시간복잡도: O(N)
- 메모이제이션 장점: 재귀적 기법으로 단순히 풀 수 있음, 재사용으로 속도가 빠름
- 메모이제이션 단점: 재귀, 오버헤드 큼
```
function fibonacci2(n, memo) {
  if (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;
	
  const table = [0, 1]
	
  for (let i = 2; i <= n; i++) {
    table.push(table[i - 2] + table[i - 1])
  }
	
  return table[n]
}
```

회고

지난 3주를 생각해보니 마지막 주에는 조금 해이해지지는 않았는지 아쉬움이 든다. 그래도 혼자 공부할 때는 제대로 공부하고 있는 게 맞는 지 고민했었는데, 다른 사람들과 같이 학습하고 또 미션도 풀면서 한 주를 마무리하니까 정말 참여하기 잘했다는 생각이 들었다.

3주 동안 학습한 내용을 바탕으로 감자님의 알고리즘/네트워크 강의도 들으면서 부족한 CS를 조금 더 채워야겠다.