인프런 워밍업 클럽 - 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 강의를 듣고 나니 '아~ 이래서 그런 얘기를 하신거구나'라는 생각이 들게 되었다.다음번에도 스터디가 있으면 적극적으로 참여해야겠다.

인프런 워밍업 클럽 - CS 3주차 과제

운영체제1. 메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터가장 빠른 기억장소CPU 내에 존재휘발성 메모리CPU를 나타내는 값에서 32bit, 64bit가 레지스터의 크기를 의미한다.CPU는 계산을 수행할 때 메인 메모리에 있는 값을 레지스터로 가져와서 계산한다.캐시휘발성 메모리레지스터와 메인 메모리 사이의 속도 간극을 메우기 위한 저장소필요한 데이터를 미리 가져와 저장하는 저장소성능의 이유로 여러 개가 존재한다.ex) L1, L2, L3CPU가 값을 요청해 레지스터로 값을 옮겨야 하는 경우 빠른 캐시를 순차적으로 확인하고, 캐시에 데이터가 없으면 메인 메모리를 조회한다.메인메모리휘발성 메모리OS와 다른 프로세스들이 올라가는 공간데이터를 저장하기 보다는 실행중인 프로그램만 저장한다.2. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터H/W적으로 OS 공간과 사용자 공간을 나누는 레지스터CPU 내에 존재한다.메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났다면 검사하고, 벗어났다면 해당 프로세스를 종료시킨다.3. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식 장점메모리를 가변적으로 분할할 수 있다.코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있어 공유와 각 영역에 대한 메모리 접근보호가 편리하다.가변 분할 방식 단점외부 단편화가 발생한다.고정 분할 방식 장점메모리를 효율적으로 관리할 수 있다.고정 분할 방식 단점내부 단편화가 발생한다.But. 가변 분할 방식의 단점인 외부 단편화에 비해 많은 공간을 차지하지 않는다.4. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?쓰레싱5. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?필요하다고 생각한다.컴퓨터가 부팅될 때 ROM에 저장된 바이오스가 실행되고, 바이오스는 주요 하드웨어에 이상이 없는지 체크한다. 이 때 저장장치에 문제가 있다면 부팅이 정상적으로 이뤄지지 않는다.OS는 주로 HDD나 SSD에 설치되고 저장되고, 부팅시에 주요 장치에 이상이 없다면 HDD나 SSD의 마스터 부트 레코드에 저장된 부트로더를 메모리로 가져와서 실행시킨다.위의 2가지 이유 때문에 HDD와 SSD가 없어서는 안된다고 생각한다.6. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일시스템은 효율적인 공간 관리를 위해 Free Block List라는 목록을 관리한다.파일이 지워질 때 파일 시스템이 파일의 모든 정보를 지우는 것이 아니라 파일 테이블의 헤더를 삭제하고 Free Block List에 추가한다.→ 실제로 파일의 데이터를 지우는 것이 아니다.이러한 특성으로 인하여 포렌식으로 파일을 복구할 수 있는 것이다.자료구조와 알고리즘1. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬장점이해와 구현이 간단하다.단점성능이 좋지 않다.시간 복잡도O(n^2)선택 정렬장점이해와 구현이 간단하다.단점성능이 좋지 않다.시간 복잡도최악 : O(n^2) - 배열이 역순으로 정렬되어 있는 경우삽입 정렬장점구현이 간단하고 이해하기 쉽다.추가적인 메모리 소비가 적다.단점성능이 좋지 않다.데이터의 상태에 따라 성능 편차가 크다.최선 : O(n)최악 : O(n^2)시간 복잡도O(n^2)병합 정렬장점속도가 빠르다.단점병합 과정에서 임시 배열이 필요하기 때무넹 추가적인 메모리 공간을 사용한다.이해와 구현이 복잡하다.시간 복잡도O(n log n)퀵 정렬장점공간 효율성: 추가 메모리 공간을 거의 필요로 하지 않는 제자리 정렬 알고리즘캐시 친화적: 지역성이 좋아 캐시 성능이 우수병렬화 가능: 분할 정복 접근 방식으로 인해 병렬 처리에 적합단점불안정 정렬: 동일한 키 값을 가진 요소들의 상대적 순서가 보존되지 않을 수 있다.최악의 경우 성능: 피벗 선택이 잘못되면 O(n^2)의 시간 복잡도를 가질 수 있다.재귀적 특성: 재귀 호출로 인해 스택 오버플로우가 발생할 수 있다.시간 복잡도평균 케이스: O(n log n)최악의 케이스: O(n^2)최선의 케이스: O(n log n)2. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.타뷸레이션을 사용할 것 같다.메모이제이션의 경우 재귀호출이기 때문에 메모리를 많이 사용하기 때문에 메모리가 부족한 시스템에서 사용하는 것은 적합하지 않다.

인프런 워밍업 클럽 - CS Day 14

Algorithm재귀가 성능에 영향을 미치는 경우Call Stack중복되는 연산→ 중복되는 연산을 저장하고, 같은 계산이 필요할 때 저장된 결과를 사용한다.→ 함수 호출 수가 줄어듦.→ 성능이 좋아진다.Memoization계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법단점속도를 위해서 메모리(저장 공간)를 사용한다.재귀 함수이기 때문에 Call Stack을 차지하는 단점은 변하지 않는다.Tabulation상향식 계산 방식계산에 필요하지 않을 수 있는 값도 미리 계산해 테이블에 저장하는 방식Memoization vs TabulationMemoization : 해결하기 힘든 문제를 하향식으로 접근하여 복잡한 문제를 쉽게 해결할 수 있다.분할 정복을 해결할 때 재귀가 더 직관적인 경우에 유리Tabulation재귀가 직관적이지 않은 경우에 유리OSFile저장장치에 저장된다.구조Header파일의 속성이 담겨있다.Data데이터의 집합데이터 집합 구성에 따른 분류순차파일구조파일의 내용이 연속적으로 이어진 형태ex) 카세트테이프장점모든 데이터가 순차적으로 기록되기 때문에 공간의 낭비가 없고, 구조가 단순하다.단점특정지점에 바로 이동이 어려워 데이터를 삽입하거나 삭제하려면 탐색하는데 시간이 오래 걸린다.직접파일구조저장하려는 데이터의 위치를 해시 함수를 통해 결정하는 구조자료구조에서 Hash Table이라고 불린다.ex) JSON장점해시 함수를 사용하기 때문에 데이터 접근이 굉장히 빠르다.단점해시함수의 선정이 굉장히 중요하다.저장공간이 낭비될 수 있다.인덱스 파일 구조순차접근과 직접접근 방식의 장점을 취한 구조 쌍으로 구성데이터 파일과는 별도로 저장되며, 빠른 검색을 위해 사용된다.File System파일을 관리하기 위해 OS가 둔 파일 관리자파일 테이블을 이용하여 파일을 관리한다.기능파일과 디렉토리 생성파일과 디렉토리 수정/삭제파일 권한 관리무결성 보장백업과 복구암호화동작블록 저장장치에 저장 → 전송 단위 : 블록사용자가 바이트 단위로 파일에 접근이 가능하도록 지원한다.File Descriptor(= File Control Block)OS가 파일을 제어하기 위한 정보를 보관하는 Block파일마다 독립적으로 존재한다.저장장치에 존재하다가 파일이 오픈되면 메모리로 이동한다.OS가 관리하고 사용자가 직접 참조할 수 없다.사용자는 File Descriptor를 사용하여 File에 접근할 수 있다.파일의 맨 앞에 위치해서 사용자가 쓰거나 읽기를 시작하면 처음부터 진행한다.Directory1개 이상의 파일과 자식 디렉토리를 가질 수 있다.운영체제 마다 가장 최상단의 디렉토리 명칭이 다르다.Windows : Partition Name(ex : C:)Unix, Linux : Root('/')디렉토리도 파일정보가 저장되어 있는 하나의 파일이다.구조디렉토리 헤더 : 디렉토리 정보가 시작하는 위치를 가리킨다.다단계 디렉토리어떠한 디렉토리에서도 하위 디렉토리를 만들 수 있는 트리 구조File & Disk전체 디스크 공간을 블록(일정한 크기를 갖는 공간)으로 나누고, 그 공간에 주소를 할당해 관리한다.- 일반적으로 한 블록의 크기는 1 ~ 8KB이다.- 하나의 파일은 여러개의 블록으로 이루어진다.파일시스템은 파일정보를 파일테이블로 관리한다.파일이 시작하는 블록의 위치정보가 담겨있다.블록 연결 방식에 따른 분류연속할당파일을 구성하는 블록들을 디스크에 연속적으로 저장하는 방식파일의 시작 블록만 알면 파일의 전체를 알 수 있다.외부 단편화가 발생하여 실제로 사용하지 않는다.불연속할당디스크의 비어있는 공간에 데이터를 분산하여 저장하는 방식- 분산된 블록은 파일시스템이 관리한다.연결 할당파일에 속한 데이터를 연결리스트를 사용하여 관리한다.파일테이블에는 시작 블록에 대한 정보만 저장하고 나머지는 연결리스트를 이용해 다른 블록에 접근한다.인덱스 할당테이블의 블록 포인터가데이터 블록에 직접 연결하는 것이 아니라 데이터들의 인덱스를 갖고 있는 인덱스 블록을 연결한다.데이터가 많아서 테이블이 꽉 찬경우 인덱스 블록을 더 만들어 연결하기 때문에 테이블 확장에 용이하다.파일 크기가 작다면 데이터를 바로 참조하는 블록 포인터를 이용한다.파일의 크기가 크다면 간접 포인터를 이용해 많은 데이터에 접근할 수 있다.i-node라는 방식으로 유닉스와 리눅스에서 많이 사용되고 있다.Free Block List파일시스템이 효율적인 공간 관리를 위해 빈 공간을 모아둔 목록파일 시스템은 파일의 모든 정보를 지우는 것이 아니라 파일 테이블의 헤더를 삭제하고 Free Block List에 추가한다.→ 포렌식을 통해 데이터를 복구할 수 있다.

인프런 워밍업 클럽 - CS Day 13

Algorithm한 번 정렬이 진행될 때마다 피벗이 정렬되고 정렬될 배열을 좌우로 나눠 재귀호출하여 모든 원소를 정렬한다.Quick Sort구현 방법피벗 선택배열에서 피벗으로 사용할 요소를 선택일반적으로 첫 번째, 마지막, 또는 중간 요소를 선택분할 (Partition)피벗을 기준으로 배열을 두 부분으로 나눈다.피벗보다 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 이동재귀 호출분할된 두 부분 배열에 대해 Quick Sort를 재귀적으로 적용한다.종료 조건부분 배열의 크기가 1 이하가 될 때까지 재귀를 반복한다.결합정렬된 부분 배열들이 자동으로 하나의 정렬된 배열로 합친다.시간 복잡도평균 케이스: O(n log n)최악의 케이스: O(n^2)최선의 케이스: O(n log n)장점공간 효율성: 추가 메모리 공간을 거의 필요로 하지 않는 제자리 정렬 알고리즘캐시 친화적: 지역성이 좋아 캐시 성능이 우수병렬화 가능: 분할 정복 접근 방식으로 인해 병렬 처리에 적합단점불안정 정렬: 동일한 키 값을 가진 요소들의 상대적 순서가 보존되지 않을 수 있다.최악의 경우 성능: 피벗 선택이 잘못되면 O(n^2)의 시간 복잡도를 가질 수 있다.재귀적 특성: 재귀 호출로 인해 스택 오버플로우가 발생할 수 있다.OS주변 장치여러 주변장치는 메인보드 내의 버스로 연결된다.- 기존에는 하나의 버스로 연결되었음→ CPU가 I/O 작업을 수행할 때 다른 작업을 할 수 없음→ I/O Controller(입출력 제어기)와 여러 개의 버스가 추가되었다.입출력 제어기입출력 버스에서 온 데이터를 메모리로 옮긴다.→ 메모리는 CPU의 명령으로 움직인다.→ 입출력 제어기가 메모리에 접근하기 위해선 CPU가 필요하다.→ 입출력 제어기가 CPU의 도움이 필요 없도록 DMA(Direct Memory Access) 제어기가 추가되었다.DMA 제어기를 통해 데이터를 직접 메모리에 저장하거나 가져올 수 있다.CPU와 DMA가 사용하는 메모리가 겹치지 않도록 구분한다.(=Memory Mapped I/O)입출력 버스세부적으로 느린장치와 빠른장치를 구분하기 위해 두개의 채널로 나뉜다.고속 입출력 버스저속 입출력 버스→ 속도 차이로 인한 병목현상을 해결한다.시스템 버스고속으로 작동하는 CPU와 메모리가 사용한다.입출력 버스주변장치가 사용한다.그래픽 카드매우 대용량의 데이터를 다룬다.→ 고속 입출력 버스도 감당할 수 없다.→ 시스템 버스에 바로 연결해 사용한다.내부 구조메인보드에 있는 버스로 연결된다.하나의 버스는 Address 버스, Data 버스, Control 버스로 구성되어 있다.→ I/O 디바이스는 세 세가지 버스를 따로 받을 수 있다.H/W에 맞게 외부 인터페이스가 존재한다.레지스터 : 입출력 작업을 할 때 데이터를 저장하는 역할을 수행CPU 작업을 위해 메모리로 값이 이동하기도 한다.데이터의 전송단위에 따른 분류캐릭터 디바이스상대적으로 적은 양의 데이터를 전송한다.마우스, 키보드, 사운드 카드, 직렬/병렬 포트, etc..블록 디바이스많은 양의 데이터를 전송한다.HDD, SSD, 그래픽 카드, etc...광학 마우스마우스 하단부의 작은 카메라가 초당 1500회 이상의 사진을 찍어 마우스의 디바이스 컨트롤러 내의 DSP(Digital Signal Processor)로 전송한다.DSP는 사진을 분석해 마우스의 x, y축 움직임을 캐치한다.DSP가 마우스의 움직임과 클릭같은 데이터를 감지하면 디바이스 컨트롤러는 CPU에게 인터럽트를 보내고 마우스 드라이버가 동작해서 데이터를 읽어간다.마우스 드라이버는 OS에게 이벤트를 주고, OS는 이벤트를 Foreground 애플리케이션으로 전달한다.키보드사용자가 키보드를 누르면 키보드의 디바이스 컨트롤러가 어떤 키를 입력받았는지 알아낸다.디바이스 컨트롤러가 CPU에게 인터럽트를 보낸다.키보드 드라이버는 OS에게 이벤트를 보낸다.OS는 이벤트를 Foreground 애플리케이션으로 전달한다.HDD블록 디바이스의 한 종류구조Spindle : 막대Platter : 자기화된 원판여러 개의 track으로 구성표면에 자성이 있다.N극 : 0S극 : 1→ 자석을 갖다대면 데이터가 손상된다.일반적으로 플래터 수는 2개 이상Read/Write Head : 플래터의 표면을 읽는다.Cylinder : 여러 개의 플래터에 있는 같은 트랙의 집합Track : Platter를 구성하고 있는 부분Sector : Track을 구성하는 부분HDD의 가장 작은 단위Disk Arm : Read/Write Head가 붙어 있는 장치데이터를 읽는 방법User Process가 HDD의 특정 섹터에 접근 요청실린더 C로 가서 트랙 B에 있는 섹터 D를 읽어들여라.Seek 동작 수행디스크 암은 헤드를 실린더 C로 이동시킨다.Seek Time 헤드를 실린더로 이동시키는 걸리는 시간→ HDD가 느린 이유트랙B의 섹터D가 Read/Write Head에 닿을 때 까지 스핀들을 회전시킨다.헤드에 섹터D가 읽히면 작업 완료Flash Memory(SSD)블록 디바이스의 종류전기적으로 데이터를 읽어들인다.특정한 지점에 데이터를 쓰면 덮어쓰기가 불가능하다.데이터를 지우기 가능한 횟수가 정해져있다.→ 같은 지점에 지우기를 자주 사용하면 망가져 사용할 수 없다.

인프런 워밍업 클럽 - CS Day 12

AlgorithmMerge Sort재귀로 구현하는 정렬 알고리즘Divide and Conquer복잡한 문제를 더 작고 관리하기 쉬운 하위 문제들로 나누어 해결하는 알고리즘 설계 기법구현 방법분할(Divide): 정렬할 배열을 거의 같은 크기의 두 부분 배열로 나눈다.정복(Conquer): 각 부분 배열을 재귀적으로 정렬한다.결합(Combine): 정렬된 부분 배열들을 하나의 정렬된 배열로 병합한다.1 ~ 3을 부분 배열의 크기가 1이 될 때까지 반복한다.시간 복잡도분할 과정: 배열을 반으로 나누는 과정이 log n번 일어납니다.병합 과정: 각 단계에서 n개의 요소를 비교하고 병합합니다.→ 전체 시간 복잡도 : O(n) * O(log n) = O(n log n)장점속도가 빠르다.시간 복잡도 : O(n log n)단점병합 과정에서 임시 배열이 필요하여 추가적인 메모리 공간을 사용한다.이해와 구현이 복잡하다.OS지역성 이론(90 : 10 법칙)프로그램이 실행될 때 90%의 시간이 10%의 코드에서 소요된다.조만간 쓸 데이터만 메모리로 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑영역으로 보내 성능을 향상시킨다.디맨드 페이징필요할 것 같은 데이터를 메모리로 가져오고, 쓰이지 않을 것 같은 데이터는 스왑영역으로 이동시키는 정책지역성 이론을 구현한 정책메모리에서 데이터를 가져오는 정책Swap in스왑 영역에서 물리 메모리로 데이터를 가져오는 과정Swap out물리 메모리에서 스왑 영역으로 데이터를 보내는 과정Page Table Entry(PTE)페이지 테이블을 이루고 있는 행접근 비트페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트메모리에 읽기나 실행 작업을 했다면 1로 변경된다.변경 비트페이지가 메모리에 올라온 후 데이터에 변경이 있었는지 알려주는 비트메모리에 쓰기 작업을 했다면 1로 변경된다.유효 비트페이지가 물리 메모리에 있는지 알려주는 비트유효비트 1 : 페이지가 스왑영역에 있음유효비트 0 : 페이지가 물리 메모리에 있음읽기/쓰기/실행 비트(권한 비트)해당 메모리에 접근권한이 있는지 검사하는 비트Page Fault프로세스가 가상 메모리에 접근요청을 했을 때 MMU(메모리 관리자)는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아낸다.물리 메모리에 프레임이 없다면 MMU는 Page Fault라는 인터럽트를 발생시킨다.Page Fault가 발생하면 스왑영역에 접근하고 해당 프로세스는 대기 상태가 된다.→ 스왑 영역의 데이터가 메모리로 올라가는 작업을 수행한다.→ 데이터가 물리 메모리로 올라가는 경우 해당 프로세스가 실행 상태로 변경된다.공간의 지역성현재 위치와 가까운 데이터에 접근할 확률이 높다.시간의 지역성최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높다.페이지 교체 정책메모리가 꽉찼을 때 어떤 페이지를 스왑영역으로 보낼지 결정하는 정책무작위로 교체하는 방법지역성을 고려하지 않는다.자주 사용되는 페이지가 선택될 수 있어 성능이 좋지 않다.→ 거의 사용되지 않는다.FIFO(First-In First-Out)메모리에 들어온지 가장 오래된 페이지를 교체한다.→ 자주 사용하는 페이지가 교체될 수 있다.구현이 간단하고 성능이 나쁘지 않아 변형해서 사용된다.H/W 적으로 접근비트를 지원하지 않는다면 FIFO를 사용해야 한다.Belady's AnomalyPage Fault를 줄이려고 메모리를 더 늘려서 프레임의 수를 늘렸는데 오히려 Page Fault가 더 많이 발생하는 현상FIFO에서만 발생한다.2차 기회 페이지 교체 알고리즘FIFO 방식에서 자주 사용하는 페이지에게는 또 한번의 기회를 준다.FIFO와 동일하게 동작하지만 Page Fault 없이 페이지 접근에 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시켜 준다.Optimum앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다.→ 이후에 어떤 요청이 들어올지 알고 있어야 한다.→ 사실상 구현이 불가능한 이론적인 방법다른 알고리즘과 성능 비교를 할 때 참고용으로 사용된다.LRU(Least Recently Used)시간의 지역성에 따르면 최근 사용한 데이터가 앞으로도 사용될 확률이 높기 때문에 최근에 가장 사용을 적게한 페이지가 앞으로도 사용될 확률이 적다.Optimum 알고리즘에 근접한 성능을 갖는다.프로그램이 지역성을 띄지 않을 때는 성능이 떨어진다.PTE에 시간을 기록하려면 비트가 많이 필요하다.→ 비트를 많이 사용하는 것은 어렵기 때문에 접근비트를 이용하여 LRU에 근접하게 구현한다.Clock Algorithm접근 비트 하나만을 사용하여 구현하는 알고리즘일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화한다.페이지가 참조되는 경우 1로 설정된다.⇒ 일정 시간 간격마다 페이지가 참조되었는지 참조되지 않았는지 알 수 있다.페이지를 원형으로 연결한다.Page Fault가 발생해서 스왑영역으로 보내야 하는 경우클락 핸드는 현재 참조하고 있는 접근 비트를 본다.해당 비트가 1인 경우 해당 비트를 0으로 변경하고 다음 비트를 바라본다.접근 비트가 0인 페이지를 발견하면 해당 페이지를 스왑 영역으로 보낸다.Clock Hand스왑영역으로 옮길 페이지를 가르키는 포인터시계 방향으로 돈다.Enhanced Clock Algorithm접근 비트만 이용하는 것이 아니라 변경 비트도 함께 사용하는 알고리즘스왑 영역으로 보내지는 가장 우선순위접근 비트 : 0, 변경 비트 : 0접근 비트 : 0, 변경 비트 : 1접근 비트 : 1, 변경 비트 : 0접근 비트 : 1, 변경 비트 : 1스레싱프로세스들이 실제 실행되는 시간보다 페이지를 교체하는 데에 더 많은 시간을 사용하고 있는 현상⇒ 페이지 부재(page fault)가 과도하게 발생하여 CPU 이용률이 급격히 떨어지는 현상다중 프로그래밍의 정도가 높아져 각 프로세스에 할당된 메모리가 부족해지면서 발생CPU 이용률 저하 → 운영체제의 다중 프로그래밍 증가 → 페이지 부재 증가의 악순환이 반복근본적인 원인 : 물리 메모리의 크기가 부족한 것→ 메모리의 크기를 늘려서 해결(H/W 수준)할 수 있다.S/W 수준의 해결 방법프로세스가 실행되면 일정량의 페이지를 할당한다.→ Page Fault가 빈번하게 발생하는 경우 : 더 많은 용량의 페이지를 할당한다.→ Page Fault가 거의 없는 경우 : 적은 용량의 페이지를 할당한다.워킹셋프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합프로그램의 지역성(Locality) 특성을 이용한 개념자주 참조되는 워킹셋을 주기억장치에 유지함으로써 페이지 부재와 교체를 줄인다.시간에 따라 자주 참조하는 페이지들의 집합이 변화하므로 워킹셋도 동적으로 변한다.컨텍스트 스위칭에서 사용된다.

인프런 워밍업 클럽 - CS Day 11

Algorithm영역을 2개로 나누어서 정렬을 수행하는 알고리즘정렬된 영역정렬되지 않은 영역정렬되지 않은 영역에서 데이터를 하나씩 꺼내서 정렬된 영역 내의 적절한 위치에 삽입하여 정렬하는 알고리즘시간 복잡도O(n^2) : 배열이 역순으로 정렬되어 있는 경우장점구현이 간단하고 이해하기 쉽다.추가적인 메모리 소비가 적다.단점시간 복잡도가 O(n^2)로 느리다.데이터의 상태에 따라 성능 편차가 크다.최선의 경우 : O(n)최악의 경우 : O(n^2)OS가상 메모리프로세스는 OS 영역이 어디있는지, 물리 메모리의 크기가 얼마나 큰지 몰라도 된다.→ 프로그래머는 물리 메모리의 크기와 프로세스가 메모리에 어느위치에 신경쓰지 않고 0x0번지에서 시작한다고 가정하고 프로그래밍을 한다.프로세스는 메모리 관리자를 통해서 메모리에 접근한다.직접 메모리에 붙지 않는다.가상 메모리의 크기이론적 무한대실제 : 물리 메모리 크기 + CPU 비트 수ex) 32bit → 표현 가능한 주소값 : 2^32 = 4GB가상 메모리 시스템은 물리 메모리가 처리할 수 없는 용량을 프로세스들이 요구할 때 물리 메모리 내용의 일부를 하드 디스크에 있는 스왑 영역으로 옮기고 처리가 필요할 때 물리 메모리로 가져와서 처리한다.→ 물리 메모리가 처리할 수 없는 용량의 작업들을 처리할 수 있게 한다.메모리 관리자는 가상주소와 물리 주소를 1 : 1 매핑 테이블로 관리한다.가상 메모리의 프로세스 할당 방법가상 메모리 시스템에서는 OS 영역을 제외한 나머지 영역을 일정한 크기로 나누어서 프로세스에게 할당한다.가변 분할 방식(Segmentation)프로그램은 함수나 모듈 등으로 세그먼트를 구성한다.각 세그먼트들이 인접해 위치할 필요는 없다.But. 프로세스 입장에서는 코드 영역, 데이터 영역, 힙 영역, 스택 영역을 서로 인접한 것 처럼 바라본다.MMU(메모리 관리자)가 논리주소로 물리주소로 변환해주는 방법세그멘테이션 테이블이라는 테이블이 존재Base AddressBound Address⇒ 두 주소를 사용하여 물리 메모리 주소를 계산한다.AddressBase Address프로세스나 세그먼트의 물리 메모리 상 시작 주소를 나타낸다.MMU의 base register에 저장되어 주소 변환에 사용Bound Address (또는 Limit)프로세스나 세그먼트의 크기를 나타낸다.MMU의 bound/limit register에 저장되어 메모리 보호에 사용된다.논리주소 → 물리주소CPU에서 논리 주소 전달MMU는 해당 논리 주소가 몇 번 세그먼트 인지 확인MMU내의 Segment Table Base Register 내에 있는 세그멘테이션 테이블을 찾는다.세그먼트 번호를 인덱스로 Base Address와 Bound Address를 찾는다.MMU는 CPU에서 받은 논리주소와 Bound Address의 크기를 비교한다.논리주소가 Bound Address보다 작은 경우논리주소와 Base Address를 더해 물리 주소를 더한다.논리주소가 Bound Address보다 큰 경우메모리를 침범했다고 간주하고 에러를 발생시킨다.STBR(Segment Table Base Register)OS는 컨텍스트 스위칭을 할 때마다 메모리 관리자내의 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야 한다.→ Context Switching이 고비용 작업인 이유장점메모리를 가변적으로 분할할 수 있다.코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있어 공유와 각 영역에 대한 메모리 접근보호가 편리하다.단점외부 단편화 발생고정 분할 방식(Paging)세그멘테이션 기법의 외부 단편화를 해결하기 위해 고안된 배치 정책페이징은 메모리를 할당할 때 정해진 크기의 페이지로 나눈다.→ 외부 단편화가 발생되지 않는다.Page : 일정한 크기로 균일하게 나뉘어진 논리주소공간Frame : 일정한 크기로 균일하게 나뉘어진 물리주소공간가장 신경써야 하는 점페이지 테이블의 크기각 프로세스마다 테이블을 갖는다.→ 프로세스가 많아질 수록 페이지 테이블도 많아진다.→ 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어든다.페이지 테이블 크기가 너무 큰 경우 : 사용자 영역이 부족하다.Page Table가상 주소를 물리 주소로 변환하는데 사용하는 테이블각 프로세스의 가상 페이지 번호(VPN)을 물리 프레임 번호(PFN)로 매핑한다.각 프로세스마다 독립적인 Page Table을 갖는다.페이지 테이블에 Invalid로 되어 있으면 스왑영역에 저장되어 있는 상태Page Table Entry(PTE)페이지 기본 주소 (Page base address)유효 비트 (Valid bit): 페이지가 메모리에 있는지 여부보호 비트 (Protection bit): 읽기/쓰기/실행 권한참조 비트 (Reference bit): 페이지 접근 여부수정 비트 (Dirty bit): 페이지 내용 변경 여부Page Table Base Register(PTER)각 프로세스의 PCB에 위치하며, 해당 프로세스의 Page Table의 시작 주소를 가리킨다.OS는 컨텍스트 스위칭을 할 때마다 메모리 관리자내의 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야 한다.논리주소 → 물리주소CPU에서 논리주소 전달MMU는 논리주소가 몇번 페이지인지 오프셋은 어떻게 되는지 확인MMU에서 Page Table Base Register를 이용하여 물리 메모리에 있는 페이지 테이블을 찾는다.페이지 번호를 인덱스로 프레임 번호를 알아낸다.오프셋을 사용하여 물리 주소로 변환한다.장점메모리를 효율적으로 관리할 수 있다.단점내부 단편화 발생세그멘테이션의 외부 단편화와 비교하면 많은 공간을 비교하지 않는다.Segmentation vs Paging차이점페이지의 크기세그멘테이션은 프로세스마다 크기가 달라 Bound Address를 갖는다.페이징은 모든 페이지의 크기가 동일해서 크기를 표현하는 Bound Address가 필요없다.세그멘테이션은 논리적인 영역별로 세그먼트를 나눈다.→ 세그먼트 마다 크기를 다르게 나눌 수 있다.→ 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 나눌 수 있다.페이징은 페이지의 크기가 고정되어 있어 논리적인 영역을 나눌 수 없다.→ 특정 영역만 떼어내서 공유하거나 권한을 부여하기 어렵다.Paged Segmentation세그멘테이션 - 페이징 혼용 기법각각의 장점을 혼합한 기법세그멘테이션 테이블과 페이지 테이블을 결합하여 사용한다.메모리 접근 권한메모리의 특정 번지에 부여된 권한상태값 : Read, Write, Execute각 프로세스는 코드 영역, 데이터 영역, 힙 영역, 스택 영역이 존재한다.→ 각 영역마다 접근 권한이 있다.코드 영역 : 프로그램 자체 ⇒ 읽기/실행 권한데이터 영역 : 일반변수, 전역변수, 상수로 선언한 변수 저장 ⇒ 읽기/(쓰기-Optional) 권한힙 영역 : 읽기/쓰기 권한스택 영역 : 읽기/쓰기 권한메모리 접근 권한 검사는 가상주소에서 물리주소로 변환될 때마다 일어난다.권한을 위반하는 경우 에러를 발생시킨다.주소 변환 과정세그먼트 번호로 세그먼트 테이블에 접근하여 세그먼트 길이와 해당 세그먼트의 페이지 테이블 시작 주소를 얻는다.해당 세그먼트가 메모리 접근 권한을 위반하는지 검사한다.접근 권한 위반 시 프로세스 종료세그먼트의 페이지 테이블 시작 주소에 세그먼트 내 페이지 번호를 더해 페이지 테이블 항목에 접근한다.페이지 테이블에서 프레임 번호를 얻는다.프레임 번호에 페이지 내 오프셋을 더해 최종 물리 주소를 얻는다.단점물리 메모리에 접근하기 위해 메모리에 두 번 접근해야 한다.세그멘테이션 테이블 참조페이지 테이블 참조→ 페이징과 페이지드 세그멘테이션 기법을 적절히 섞어서 사용한다.DAT(Dynamic Address Translation, 동적 주소 변환)메모리 관리자가 물리 메모리와 스왑영역을 합쳐서 프로세스가 사용하는 가상주소를 물리주소로 변환하는 과정DAT를 거치면 프로세스는 마음대로 사용자 데이터를 물리 메모리에 배치할 수 있다.