인프런 워밍업 클럽 - CS Week 3

Algorithm

Insertion Sort

• 영역을 2개로 나누어서 정렬을 수행하는 알고리즘

  • 정렬된 영역

  • 정렬되지 않은 영역

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

• 시간 복잡도 : O(n^2)

   

장점

• 구현이 간단하고 이해하기 쉬움

• 추가적인 메모리 소비가 적다.

단점

• 데이터의 상태에 따라 성능 편차가 크다.

  • 최선 : O(n)

  • 최악 : O(n^2)

Merge Sort

• 재귀로 구현하는 정렬 알고리즘

• 시간 복잡도 : O(n log n)

Divide & Conquer

• 복잡한 문제를 더 작고 관리하기 쉬운 하위 문제들로 나누어 해결하는 알고리즘 설계 기법

구현 방법

1. 분할(Divide): 정렬할 배열을 거의 같은 크기의 두 부분 배열로 나눈다.

2. 정복(Conquer): 각 부분 배열을 재귀적으로 정렬한다.

3. 결합(Combine): 정렬된 부분 배열들을 하나의 정렬된 배열로 병합한다.

장점

• 속도가 빠르다.

단점

• 병합 과정에서 임시 배열이 필요하여 추가적인 메모리 공간을 사용한다.

• 이해와 구현이 어렵다.

Quick Sort

• Pivot을 사용하여 정렬하는 알고리즘

• 시간 복잡도

  • 평균 케이스: O(n log n)

  • 최악의 케이스: O(n^2)

  • 최선의 케이스: O(n log n)

구현 방법

1. 피벗 선택

   • 배열에서 피벗으로 사용할 요소를 선택

   • 일반적으로 첫 번째, 마지막, 또는 중간 요소를 선택

2. 분할 (Partition)

   • 피벗을 기준으로 배열을 두 부분으로 나눈다.

   • 피벗보다 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 이동

3. 재귀 호출

   • 분할된 두 부분 배열에 대해 Quick Sort를 재귀적으로 적용한다.

4. 종료 조건

   • 부분 배열의 크기가 1 이하가 될 때까지 재귀를 반복한다.

5. 결합

   • 정렬된 부분 배열들이 자동으로 하나의 정렬된 배열로 합친다.

장점

• 공간 효율성: 추가 메모리 공간을 거의 필요로 하지 않는 제자리 정렬 알고리즘

• 캐시 친화적: 지역성이 좋아 캐시 성능이 우수

• 병렬화 가능: 분할 정복 접근 방식으로 인해 병렬 처리에 적합

단점

• 불안정 정렬: 동일한 키 값을 가진 요소들의 상대적 순서가 보존되지 않을 수 있다.

• 최악의 경우 성능: 피벗 선택이 잘못되면 O(n^2)의 시간 복잡도를 가질 수 있다.

• 재귀적 특성: 재귀 호출로 인해 스택 오버플로우가 발생할 수 있다.

Memoization

• 중복되는 연산을 저장하고, 같은 계산이 필요할 때 저장된 결과를 사용한다.

• 재귀 호출로 구현한다.

• 재귀 함수에 비해 함수 호출 수가 줄어들어 성능이 비교적 우수하다.

• 분할 정복을 해결할 때 재귀가 더 직관적인 경우에 사용한다.

Tabulation

• 상향식 계산 방식

• 계산에 필요하지 않을 수 있는 값도 미리 계산해 테이블에 저장하는 방식

• 재귀가 직관적이지 않은 경우에 사용한다.

OS

가상 메모리

• 물리 메모리가 처리할 수 없는 용량을 프로세스들이 요구할 때 물리 메모리 내용의 일부를 하드 디스크에 있는 스왑 영역으로 옮기고 처리가 필요할 때 물리 메모리로 가져와서 처리한다.

  
  → 물리 메모리가 처리할 수 없는 용량의 작업들을 처리할 수 있게 한다.

• 메모리 관리자는 가상주소와 물리 주소를 1: 1 매핑 테이블로 관리한다.

• 가상 메모리 시스템에서는 OS 영역을 제외한 나머지 영역을 일정한 크기로 나누어서 프로세스에게 할당한다.

Segmentation(가변 분할 방식)

• 세그멘테이션 테이블이라는 테이블이 존재

  • Base Address

  • Bound Address
    ⇒ 두 주소를 사용하여 물리 메모리 주소를 계산한다.

• Address

  • Base Address

    • 프로세스나 세그먼트의 물리 메모리 상 시작 주소를 나타낸다.

    • MMU의 base register에 저장되어 주소 변환에 사용

  • Bound Address (또는 Limit)

    • 프로세스나 세그먼트의 크기를 나타낸다.

    • MMU의 bound/limit register에 저장되어 메모리 보호에 사용된다.

STBR(Segment Table Base Register)

• OS는 컨텍스트 스위칭을 할 때마다 메모리 관리자내의 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야 한다.
  → Context Switching이 고비용 작업인 이유

장점

• 메모리를 가변적으로 분할할 수 있다.

• 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있어 공유와 각 영역에 대한 메모리 접근보호가 편리하다.

단점

• 외부 단편화 발생

Paging(고정 분할 방식)

• 세그멘테이션 기법의 외부 단편화를 해결하기 위해 고안된 배치 정책

• 페이징은 메모리를 할당할 때 정해진 크기의 페이지로 나눈다.
  → 외부 단편화가 발생되지 않는다.

• Page : 일정한 크기로 균일하게 나뉘어진 논리주소공간

• Frame : 일정한 크기로 균일하게 나뉘어진 물리주소공간

• Page Table

  • 가상 주소를 물리 주소로 변환하는데 사용하는 테이블

  • 각 프로세스의 가상 페이지 번호(VPN)을 물리 프레임 번호(PFN)로 매핑한다.

  • 각 프로세스마다 독립적인 Page Table을 갖는다.

  • 페이지 테이블에 Invalid로 되어 있으면 스왑영역에 저장되어 있는 상태

• Page Table Base Register(PTER)

  • 각 프로세스의 PCB에 위치하며, 해당 프로세스의 Page Table의 시작 주소를 가리킨다.

  • OS는 컨텍스트 스위칭을 할 때마다 메모리 관리자내의 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야 한다.

장점

• 메모리를 효율적으로 관리할 수 있다.

단점

• 내부 단편화 발생

  • 세그멘테이션의 외부 단편화와 비교하면 많은 공간을 비교하지 않는다.

Segmentation vs Paging

• 세그멘테이션은 논리적인 영역별로 세그먼트를 나눈다.

  
  → 세그먼트마다 크기를 다르게 나눌 수 있다.
  → 크도 영역, 데이터 영역, 스택 영역, 힙 영역을 나눌 수 있다.

• 페이징은 페이지의 크기가 고정되어 있어 논리적인 영역을 나눌 수 없다.
  →특정 영역만 떼어내서 공유하거나 권한을 부여하기 어렵다.

Paged Segmentation

• Segmentation + Paging

• Segmentation Table과 Page Table을 결합하여 사용한다.

메모리 접근 권한

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

• Read, Write, Execute

• 각 프로세스는 코드 영역, 데이터 영역, 힙 영역, 스택 영역이 존재한다.
  → 각 영역마다 접근 권한이 있다.

  • 코드 영역 : 프로그램 자체 ⇒ 읽기/실행 권한

  • 데이터 영역 : 일반변수, 전역변수, 상수로 선언한 변수 저장 ⇒ 읽기/(쓰기-Optional) 권한

  • 힙 영역 : 읽기/쓰기 권한

  • 스택 영역 : 읽기/쓰기 권한

• 메모리 접근 권한 검사는 가상주소에서 물리주소로 변환될 때마다 일어난다.

  • 권한을 위반하는 경우 에러를 발생시킨다.

DAT(Dynamic Address Translation, 동적 주소 변환)

• 메모리 관리자가 물리 메모리와 스왑영역을 합쳐서 프로세스가 사용하는 가상주소를 물리주소로 변환하는 과정

• DAT를 거치면 프로세스는 마음대로 사용자 데이터를 물리 메모리에 배치할 수 있다.

Page Table Entry(PTE)

• 페이지 테이블을 이루고 있는 행

접근 비트

• 페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트

• 1 : 메모리에 읽기나 실행 작업을 수행한 경우

변경 비트

• 페이지가 메모리에 올라온 후 데이터에 변경이 있었는지 알려주는 비트

• 1 : 쓰기 작업을 수행한 경우

유효 비트

• 페이지가 물리 메모리에 있는지 알려주는 비트

• 1 : 페이지가 스왑영역에 위치

• 0 : 페이지가 물리 메모리에 위치

권한 비트

• 해당 메모리에 접근권한이 있는지 검사하는 비트

Page Fault

• 프로세스가 가상 메모리에 접근요청을 했을 때 MMU(메모리 관리자)는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아낸다.

  • 물리 메모리에 프레임이 없다면 MMU는 Page Fault라는 인터럽트를 발생시킨다.

• Page Fault가 발생하면 스왑영역에 접근하고 해당 프로세스는 대기 상태가 된다.
  → 스왑 영역의 데이터가 메모리로 올라가는 작업을 수행한다.
  → 데이터가 물리 메모리로 올라가는 경우 해당 프로세스가 실행 상태로 변경된다.

스레싱

• 프로세스들이 실제 실행되는 시간보다 페이지를 교체하는 데에 더 많은 시간을 사용하고 있는 현상
  ⇒ 페이지 부재(page fault)가 과도하게 발생하여 CPU 이용률이 급격히 떨어지는 현상

• 다중 프로그래밍의 정도가 높아져 각 프로세스에 할당된 메모리가 부족해지면서 발생

• CPU 이용률 저하 → 운영체제의 다중 프로그래밍 증가 → 페이지 부재 증가의 악순환이 반복

• 근본적인 원인 : 물리 메모리의 크기가 부족한 것
  → 메모리의 크기를 늘려서 해결(H/W 수준)할 수 있다.

S/W 수준의 해결 방법

• 프로세스가 실행되면 일정량의 페이지를 할당한다.
  → Page Fault가 빈번하게 발생하는 경우 : 더 많은 용량의 페이지를 할당한다.
  → Page Fault가 거의 없는 경우 : 적은 용량의 페이지를 할당한다.

File

데이터 집합 구성에 따른 분류

순차파일구조

• 파일의 내용이 연속적으로 이어진 형태
  ex) 카세트테이프

장점

• 모든 데이터가 순차적으로 기록되기 때문에 공간의 낭비가 없고, 구조가 단순하다.

단점

• 특정지점에 바로 이동이 어려워 데이터를 삽입하거나 삭제하려면 탐색하는데 시간이 오래 걸린다.

직접파일구조

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

• 자료구조에서 Hash Table이라고 불린다.
  ex) JSON

장점

• 해시 함수를 사용하기 때문에 데이터 접근이 굉장히 빠르다.

단점

• 해시함수의 선정이 굉장히 중요하다.

• 저장공간이 낭비될 수 있다.

인덱스 파일 구조

• 순차접근과 직접접근 방식의 장점을 취한 구조

•  <탐색키, 레코드 포인터> 쌍으로 구성

  • 데이터 파일과는 별도로 저장되며, 빠른 검색을 위해 사용된다.

File Descriptor(= File Control Block)

• OS가 파일을 제어하기 위한 정보를 보관하는 Block

• 파일마다 독립적으로 존재한다.

• 저장장치에 존재하다가 파일이 오픈되면 메모리로 이동한다.

• OS가 관리하고 사용자가 직접 참조할 수 없다.

• 사용자는 File Descriptor를 사용하여 File에 접근할 수 있다.

• 파일의 맨 앞에 위치해서 사용자가 쓰거나 읽기를 시작하면 처음부터 진행한다.

느낀점

• 회사에서 프로젝트와 병행하면서 '오늘 하루는 괜찮지 않을까...?'

  라는 안일한 생각을 했었지만 디스코드 커뮤니티에서 다들 열심히 일하는 모습을 보고 자극 받아 하루도 빠짐없이 완강하게 될 수 있었다.

• 스터디를 하는게 강제성이 부여되는 것 같아서 안일한 생각을 뿌리칠 수 있었다.

• 개발을 하다가 상사분들이 하는 얘기를 잘 따라가지 못했었는데 CS 강의를 듣고 나니 '아~ 이래서 그런 얘기를 하신거구나'라는 생각이 들게 되었다.

• 다음번에도 스터디가 있으면 적극적으로 참여해야겠다.