인프런 워밍업 클럽 - CS Week 3
AlgorithmInsertion Sort영역을 2개로 나누어서 정렬을 수행하는 알고리즘정렬된 영역정렬되지 않은 영역정렬되지 않은 영역에서 데이터를 하나씩 꺼내서 정렬된 영역 내의 적절한 위치에 삽입하여 정렬하는 알고리즘시간 복잡도 : O(n^2) 장점구현이 간단하고 이해하기 쉬움추가적인 메모리 소비가 적다.단점데이터의 상태에 따라 성능 편차가 크다.최선 : O(n)최악 : O(n^2)Merge Sort재귀로 구현하는 정렬 알고리즘시간 복잡도 : O(n log n)Divide & Conquer복잡한 문제를 더 작고 관리하기 쉬운 하위 문제들로 나누어 해결하는 알고리즘 설계 기법구현 방법분할(Divide): 정렬할 배열을 거의 같은 크기의 두 부분 배열로 나눈다.정복(Conquer): 각 부분 배열을 재귀적으로 정렬한다.결합(Combine): 정렬된 부분 배열들을 하나의 정렬된 배열로 병합한다.장점속도가 빠르다.단점병합 과정에서 임시 배열이 필요하여 추가적인 메모리 공간을 사용한다.이해와 구현이 어렵다.Quick SortPivot을 사용하여 정렬하는 알고리즘시간 복잡도평균 케이스: O(n log n)최악의 케이스: O(n^2)최선의 케이스: O(n log n)구현 방법피벗 선택배열에서 피벗으로 사용할 요소를 선택일반적으로 첫 번째, 마지막, 또는 중간 요소를 선택분할 (Partition)피벗을 기준으로 배열을 두 부분으로 나눈다.피벗보다 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 이동재귀 호출분할된 두 부분 배열에 대해 Quick Sort를 재귀적으로 적용한다.종료 조건부분 배열의 크기가 1 이하가 될 때까지 재귀를 반복한다.결합정렬된 부분 배열들이 자동으로 하나의 정렬된 배열로 합친다.장점공간 효율성: 추가 메모리 공간을 거의 필요로 하지 않는 제자리 정렬 알고리즘캐시 친화적: 지역성이 좋아 캐시 성능이 우수병렬화 가능: 분할 정복 접근 방식으로 인해 병렬 처리에 적합단점불안정 정렬: 동일한 키 값을 가진 요소들의 상대적 순서가 보존되지 않을 수 있다.최악의 경우 성능: 피벗 선택이 잘못되면 O(n^2)의 시간 복잡도를 가질 수 있다.재귀적 특성: 재귀 호출로 인해 스택 오버플로우가 발생할 수 있다.Memoization중복되는 연산을 저장하고, 같은 계산이 필요할 때 저장된 결과를 사용한다.재귀 호출로 구현한다.재귀 함수에 비해 함수 호출 수가 줄어들어 성능이 비교적 우수하다.분할 정복을 해결할 때 재귀가 더 직관적인 경우에 사용한다.Tabulation상향식 계산 방식계산에 필요하지 않을 수 있는 값도 미리 계산해 테이블에 저장하는 방식재귀가 직관적이지 않은 경우에 사용한다.OS가상 메모리물리 메모리가 처리할 수 없는 용량을 프로세스들이 요구할 때 물리 메모리 내용의 일부를 하드 디스크에 있는 스왑 영역으로 옮기고 처리가 필요할 때 물리 메모리로 가져와서 처리한다.→ 물리 메모리가 처리할 수 없는 용량의 작업들을 처리할 수 있게 한다.메모리 관리자는 가상주소와 물리 주소를 1: 1 매핑 테이블로 관리한다.가상 메모리 시스템에서는 OS 영역을 제외한 나머지 영역을 일정한 크기로 나누어서 프로세스에게 할당한다.Segmentation(가변 분할 방식)세그멘테이션 테이블이라는 테이블이 존재Base AddressBound Address⇒ 두 주소를 사용하여 물리 메모리 주소를 계산한다.AddressBase 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 SegmentationSegmentation + PagingSegmentation 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 강의를 듣고 나니 '아~ 이래서 그런 얘기를 하신거구나'라는 생각이 들게 되었다.다음번에도 스터디가 있으면 적극적으로 참여해야겠다.
