[인프런 워밍업 클럽 스터디 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를 조금 더 채워야겠다.