인프런 워밍업 클럽 - 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를 거치면 프로세스는 마음대로 사용자 데이터를 물리 메모리에 배치할 수 있다.

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

AlgorithmRecursion(재귀)어떠한 것을 정의할 때 자기 자신을 참조하는 것을 의미한다.재귀함수 : 재귀적으로 정의된 함수재귀함수는 콜스택이라는 메모리 가득차게 되는 경우 자동으로 종료된다.기저 조건 : 재귀함수가 종료될 수 있는 탈출 조건기저 조건이 반드시 있어야 정상적으로 수행할 수 있다.재귀함수는 함수를 호출할 때마다 Call Stack이라는 메모리 공간에 호출정보가 저장된다.→ 재귀함수는 Loop문보다 더 많은 메모리 공간을 차지한다.Call Stack(= Stack)함수가 호출되면서 올라가는 메모리 영역함수가 종료되면 콜스택에서 제거된다.FILO(First-In Last-Out)재귀함수를 사용하는 이유Loop를 대신한다기 보다는 더 복잡한 문제를 쉽게 해결하기 위해 사용된다.ex) Factorial재귀함수를 쉽게 작성하는 방법재귀함수 내에서 자기 자신을 호출할 때 해당 함수가 벌써 구현이 되어있다고 가정한다.재귀 사용하는 패턴단순 반복문반복문으로 구현했을 때보다 이점이 되는 부분이 없음Call Stack에 공간을 많이 차지해 성능이 반복문보다 좋지 않다.하향식 계산하향식 계산 : 하위문제의 결과를 기반으로 현재 문제를 계산하는 방식재귀가 반복문보다 성능이 좋은 경우큰 문제를 해결하기 위해 작은 재귀 함수를 호출한다.재귀를 사용해서만 구현이 가능하다.상향식 계산 : 하위 문제를 모아서 현재 문제를 계산하는 방식반복문으로 구현한 것보다 성능이 좋지 않음반복문이나 재귀를 사용해서 구현할 수 있다.하노이의 탑하향식 계산 방식의 좋은 예시→ 재귀함수의 좋은 예시제약 조건한 번에 하나의 원반을 움직일 수 있다.가장 위에 있는 원반만 옮길 수 있다.아래에 작은 원반이 올 수 없다. Bubble Sort인접한 두 원소를 비교하여 두 원소의 위치를 교환한다.과정배열을 처음부터 끝까지 순회하며 인접한 두 원소를 비교한다.왼쪽 원소가 오른쪽 원소보다 크면 두 원소를 교환한다.이 과정을 배열이 정렬될 때까지 반복한다.시간 복잡도O(n^2)장점이해와 구현이 간단한다.단점성능이 좋지 않다.Selection Sort배열에서 최솟값을 찾아 맨 앞으로 이동시킨다.과정정렬되지 않은 부분에서 최솟값을 찾는다.찾은 최솟값을 정렬되지 않은 부분의 첫 번째 원소와 교환한다.정렬된 부분을 한 칸 늘리고, 정렬되지 않은 부분에서 위 과정을 반복한다.시간 복잡도O(n^2)장점이해와 구현이 간단하다.단점성능이 좋지 않다.참고 : https://visualgo.net/en/sortingCPU Scheduling AlgorithmSJF(Shortest Job First)Burst Time이 짧은 작업부터 CPU를 할당한다.문제점어떤 프로세스가 얼마나 실행될지 예측하기 힘들다.→ 예측하는 것이 거의 불가능하다.Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수 있다.→ Burst Time이 긴 프로세스는 Burst Time이 짧은 프로세스에게 계속해서 우선순위가 밀린다.⇒ 사용되지 않는다.RR(Round Robin)하나의 프로세스에게 일정 시간만 CPU를 할당하고 할당된 시간이 지나면 강제로 다른 프로세스에게 일정시간만큼 CPU를 할당하는 방식→ 강제로 CPU를 뺏긴 프로세스는 Queue의 가장 마지막으로 밀려난다.Time Slice(=Time Quantum) : 프로세스에게 할당하는 일정 시간Time Slice에 따라서 RR의 성능이 좌지우지된다.Time Slice를 작게 만드는 경우 Context Switching이 빈번하게 발생된다.→ Context Switching이 빈번하게 발생함에 따라 성능이 떨어진다.Time Slice가 큰 경우 FIFO와 동일하게 동작한다.Time Slice 예시Window Time Slice : 20msUnix Time Slice : 100ms단점Context Switching이 존재한다.→ 평균 대기시간이 FIFO와 동일하다면 FIFO가 더 성능이 좋다.MLFQ(Multi Level Feedback Queue)RR의 업그레이드 버전주로 사용되는 CPU 스케줄링 알고리즘CPU Bound Process : CPU를 할당받은 시간을 대부분 CPU 연산을 수행하는 프로세스CPU 사용률과 처리량이 중요I/O Bound Process : 대부분의 시간을 I/O 작업에 수행하고 적은 시간만 CPU 연산을 하는 프로세스- 응답시간이 중요MLFQ는 기본적으로 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 Time Slice를 사용한다.CPU Bound Process에게는 CPU 사용률을 높이기 위해 Time Slice를 높게 할당한다.I/O Bound Process에게는 I/O 사용률을 높이기 위해 Time Slice를 낮게 할당한다.OS는 어떻게 CPU Bound Process와 I/O Bound Process를 구분할까?CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하는 경우 CPU 사용률이 낮음→ I/O Bound Process일 확률이 높음CPU를 사용하는 프로세스가 실행하다가 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황인 경우 CPU 사용률이 높음→ CPU Bound Process일 확률이 높음구현 방법우선순위를 갖는 큐를 여러개 준비한다.우선순위가 높으면 Time Slice가 작다.우선순위가 낮아질수록 Time Slice가 커진다.Process간 통신하나의 컴퓨터 내에서 프로세스간 통신하는 방법Pipe운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰는 방법File통신을 하려는 프로세스들이 하나의 파일을 이용해 읽고 쓰는 방법Thread를 이용한 통신하나의 프로세스 내에서 쓰레드간 통신하는 방법쓰레드는 코드, 데이터, 힙 영역을 공유한다.(스택 영역만 별도로 갖는다.)데이터 영역의 전역 변수나 힙 영역을 이용하여 통신할 수 있다.NetworkOS가 제공하는 Socket 통신RPC(Remote Procedure Call)다른 컴퓨터의 함수를 호출하는 방법공유자원과 임계구역공유자원 : 프로세스간 통신을 할 때 공용으로 이용하는 변수나 파일여러 프로세스가 공유하기 때문에 각 프로세스의 접근 순서에 따라서 결과가 달라질 수 있다.컨텍스트 스위칭으로 시분할 처리를 하기 때문에 프로세스간의 실행 순서를 예측하기 어렵다.⇒ 동기화 문제가 발생할 수 있다.임계규역 : 여러 프로세스가 동시에 사용하면 안되는 영역상호배제 메커니즘을 통해 해결할 수 있다.경쟁조건 : 공유자원을 사용하기 위해 서로 경쟁하는 것상호배제 요구사항임계영역엔 동시에 하나의 프로세스만 접근한다.여러 요청에도 하나의 프로세스의 접근만 허용한다.임계구역에 들어간 프로세스는 빠르게 나와야한다.Semaphore상호배제 메커니즘의 한 종류Semaphore : 정수 값을 가지는 변수로, 공유 자원에 접근할 수 있는 프로세스/스레드의 수를 나타낸다.세마포어를 갖고 있는 프로세스가 실행되고 세마포어를 반납한다.기본 연산wait(S): 세마포어 값을 감소시킨다.값이 0이면 프로세스/스레드를 대기 상태로 만든다.signal(S): 세마포어 값을 증가시킵니다.대기 중인 프로세스/스레드가 있다면 깨운다.종류이진 세마포어: 0과 1 두 가지 값만 갖는다.(뮤텍스와 유사하게 사용한다.)카운팅 세마포어: 0 이상의 정수 값을 갖는다.(여러 자원을 관리할 때 사용된다.)장단점장점: 여러 프로세스/스레드 간의 복잡한 동기화 문제를 해결할 수 있다.단점잘못 사용하면 교착 상태나 기아 상태를 유발할 수 있다.ex) 세마포어를 획득하는 함수와 세마포어를 반납하는 함수의 위치 잘못 사용Mutex(MUTual EXclusion)뮤텍스는 이진 세마포어의 특수한 경우여러 스레드가 공유 자원에 동시에 접근하는 것을 방지하는 기술기본 연산Lock: 스레드가 임계 영역에 진입할 권한을 획득Unlock: 임계 영역 사용을 마치고 다른 스레드가 진입할 수 있게 한다.뮤텍스와의 차이세마포어는 여러 프로세스/스레드의 접근을 허용할 수 있지만, 뮤텍스는 하나의 프로세스/스레드만 접근을 허용한다.Monitor세마포어의 단점을 보완한 상호배제 메커니즘OS가 처리하는 것이 아니라 프로그래밍 언어단에서 지원하는 기능ex) Java : synchronized 키워드한 번에 하나의 프로세스/스레드만 실행할 수 있다.교착상태여러 프로세스가 서로 다른 프로세스의 작업이 끝나길 기다리다가 아무 작업도 수행되지 않는 상태발생 원인상호 배제 : 공유 자원은 한 번에 하나의 프로세스만 사용할 수 있다.비선점 : 다른 프로세스가 사용 중인 자원을 강제로 빼앗을 수 없다.점유와 대기 : 프로세스가 이미 자원을 보유한 상태에서 다른 자원을 요청하며 대기한다.원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형이다.하나라도 충족하지 않으면 교착상태가 발생하지 않는다.→ 교착 상태를 예방하는 것을 구현하기는 매우 어려워서 교착 상태를 해결하는 방향으로 발전됐다.해결방법교착상태 회피프로세스들에게 자원을 할당할 대 어느 정도 자원을 할당해야 교착상태가 발생하는지 파악해서 교착상태가 발생하지 않는 수준의 자원을 할당한다.전체 자원의 수와 할당된 자원의 수를 기준으로 안정상태와 불안정 상태로 나뉜다.OS는 안정상태를 유지하려 한다.안전 상태: 모든 프로세스가 요구한 최대 자원을 할당받아 실행을 완료할 수 있는 상태불안정상태에 있더라도 무조건 교착상태에 들어가는 것이 아니라 교착상태에 빠질 확률이 높아지는 것이다.은행원 알고리즘작동 원리프로세스가 자원을 요청할 때, 그 요청이 시스템을 안전 상태로 유지할 수 있는지 확인한다.안전 상태를 유지할 수 있는 요청만 수락하고, 불안정한 상태를 초래할 수 있는 요청은 거절한다.주요 개념최대 요구량(Max Need): 프로세스가 실행을 완료하기 위해 필요한 최대 자원 양할당량(Allocation): 현재 프로세스에 할당된 자원 양필요량(Need): 최대 요구량에서 현재 할당량을 뺀 값가용량(= 시스템 총 자원, Available): 시스템에서 현재 사용 가능한 자원 양단점비용이 비싸고 비효율적이다.교착상태 검출가벼운 교착 상태 검출타이머를 이용하는 방식프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주하고 교착상태를 해결한다.교착상태 해결 방법일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백한다.무거운 교착 상태 검출자원 할당 그래프를 이용하는 방식OS가 자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드가 발생한다.But. 가벼운 교착 상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스가 발생하지 않는다.OS에서 프로세스가 어떤 작업을 사용하는지 지켜보고 교착상태가 발생했다면 해결한다.Programming LanguageCompile Language개발자가 코드를 작성하고 컴파일을 수행하여 0과 1로된 기계어로 실행파일을 만든다.→ 기계어로 되어 있어 실행 속도가 인터프리터 언어에 비해 빠르다.컴파일 과정에서 개발자의 문법오류를 체크한다.ex) C, C++, C#Interpreter Language개발자가 작성한 코드를 미리 기계어로 만들어 놓지 않고 실행시 코드를 한줄씩 해석해 실행하는 언어→ 미리 검사를 하지 않기 때문에 실행할 때 오류가 발생할 수 있고, 컴파일 언어보다 느리다.ex) Javascript, Python, Ruby프로세스의 영역코드 영역실행해야 할 코드가 들어간다.데이터 영역전역 변수나 배열이 들어가는 영역스택 / 힙프로세스가 실행될 때 할당되는 메모리스택 : 지역변수와 함수 관련 값들이 저장힙 : 실행 중에 메모리 공간을 할당할 수 있는 유동적인 공간Compile 언어가 Process가 되는 방법개발자가 코드 작성전처리 단계 실행개발자가 작성한 코드를 확인하고 전처리 구문을 처리한다.C에서는 #이라는 키워드로 선언된다.ex) #include, #define MY_NUMBER 100코드에 있는 모든 주석은 삭제된다.결과물로 .i 파일이 생성된다.전처리기에서 나온 결과파일을 컴파일러가 처리한다.컴파일러는 .i 파일을 기계어에 가까운 어셈블리어로 변환시킨다.결과물로 .s 파일이 생성된다.어셈블러 작업이 수행된다.오브젝트 파일.o로 변환된다.오브젝트 파일은 0과 1로 구성되어 있다.코드영역과 데이터 영역이 나뉘어져 있다.링커 작업이 수행된다.모든 오브젝트 파일을 하나의 코드 영역과 데이터 영역으로 묶어준다.실제로 실행될 주소를 매핑시켜준다.결과물로 .exe 파일이 생성된다.사용자가 .exe파일을 실행시키면 OS가 프로세스를 생성한다.OS는 파일에 있는 코드 영역과 데이터 영역을 가져와 프로세스의 코드 영역과 데이터 영역에 넣어주고, 빈 상태의 스택과 힙을 할당한다.PCB를 만들어 프로세스를 관리가 가능하게 한다.PC(프로그램 카운터)에 다음 실행할 명령어의 주소를 생성한 프로세스의 코드영역의 첫번째 주소로 설정한다.→ OS의 CPU 스케줄링에 따라서 프로세스가 실행되다가 작업을 마친다.메모리 종류레지스터가장 빠른 기억장소, CPU 내에 존재한다.휘발성 메모리CPU를 나타내는 값에서 32bit, 64bit를 의미하는 것이 레지스터의 크기이다.CPU는 계산을 수행할 때 메인 메모리에 있는 값을 레지스터로 가져와서 계산한다.계산 결과는 메인 메모리에 저장한다.캐시휘발성 메모리속도가 매우 빠른 레지스터와 레지스터에 비해 상대적으로 느린 메인 메모리 사이의 속도 간극을 메우기 위해 필요한 데이터를 미리 가져와 저장하는 저장소성능의 이유로 여러 개가 존재한다.L1, L2, L3→ 숫자가 커질 수록 느린 캐시CPU가 값을 요청해 레지스터로 값을 옮겨야 한다면 빠른 캐시를 순차적으로 확인하고, 캐시에 데이터가 없으면 메인 메모리를 조회한다.ex) L1 → L2 → L3 → 메인 메모리보조 저장장치(HDD, SSD)비휘발성 메모리메인 메모리실제 운영체제와 다른 프로세스들이 올라가는 공간휘발성 메모리데이터를 저장하기 보다는 실행중인 프로그램만 저장한다.OS는 메모리를 관리하기 위해서 1Byte 크기로 구역을 나누고 숫자(주소)를 매긴다.32bit CPU, 64bit CPU32bit CPU레지스터, ALU, Data Bus : 32bit메모리 : 2^32 = 4GB64bit CPU레지스터, ALU, Data Bus : 64bit메모리 : 2^64 = 16384PiB64bit CPU가 32bit CPU 보다 한번에 처리할 수 있는 양이 많기 때문에 속도가 더 빠르다.물리 주소 & 논리 주소물리 주소 공간 : 0x0부터 시작하는 주소 공간논리 주소 : 사용자 관점에서 바라 본 주소 공간사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근할 수 있다.OS를 위한 공간은 따로 확보한다.경계 레지스터H/W적으로 OS 공간과 사용자 공간을 나누는 레지스터CPU 내에 존재하는 레지스터메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났다면 검사하고, 벗어났다면 해당 프로세스를 종료시킨다.절대 주소 & 상대 주소개발자가 프로그램이 실행될 주소를 신경쓰지 않고 개발할 수 있는 이유→ 컴파일러가 컴파일을 할 때 메모리 0번지에서 실행한다고 가정하기 때문절대 주소 : 메모리 관리자가 바라본 프로세스가 올라간 물리 주소상대 주소 : 사용자가 바라보는 논리 주소재배치 레지스터프로그램의 시작 주소가 저장되어 있다.사용자가 요청한 논리 주소의 데이터를 물리 주소로 치환해준다.사용자가 메모리에 접근할 때마다 논리 주소를 물리 주소로 치환해준다.메모리 할당 방식메모리 오버레이메모리보다 용량이 큰 프로그램을 실행시키는 방법큰 프로그램을 메모리에 올릴 수 있을 정도로 분할하여 일부만 실행하고, 실행되지 않은 프로그램은 HDD의 스왑 영역에 저장하는 방식Swap스왑영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 옮기는 것가변 분할 방식(= Segmentation, 세그멘테이션)프로세스의 크기에 따라 메모리를 나누는 방식하나의 프로세스가 메모리에 연속된 공간에 할당된다.→ 연속 메모리 할당이라고 한다.장점메모리에 연속된 공간에 할당된다.→ 내부 단편화가 없다.단점외부 단편화가 발생한다.고정 분할 방식(= Paging, 페이징)프로세스의 크기와는 상관없이 정해진 크기로 나누는 방식하나의 프로세스가 메모리에 분산되어 할단된다.→ 비연속 메모리 할당이라고 한다.장점구현이 간단하고 오버헤드가 적다.단점작은 프로세스도 큰 영역에 할당되어 내부 단편화가 발생한다.내부 단편화프로세스에 필요한 메모리보다 더 큰 고정 크기의 메모리 블록이 할당될 때 발생한다.할당된 메모리와 실제 사용된 메모리 사이의 차이로 인해 메모리 공간이 낭비된다.고정 크기 분할 방식에서 주로 발생한다.해결 방법은 딱히 없고, 분할되는 크기를 조절하여 내부 단편화를 최소화한다.외부 단편화메모리 할당과 해제를 반복하면서 작은 빈 공간들이 메모리 곳곳에 흩어져 생기는 현상전체 가용 메모리는 충분하지만, 연속된 큰 블록을 할당할 수 없는 상황을 만든다.가변 분할 방식에서 주로 발생한다.조각모음외부 단편화가 발생한 공간을 합쳐주는 작업현재 메모리에서 실행되고 있는 프로세스들의 작업을 일시 주징하고, 메모리 공간을 이동시켜야 한다.→ 오버헤드가 발생한다.버디 시스템가변 분할 방식 + 고정 분할 방식오늘날의 OS가 채택한 메모리 할당 방식2의 제곱으로 메모리를 분할하여 할당하는 방식→ 근접한 메모리 공간을 합치기 쉽다.→ 조각 모음보다 훨씬 간단하다.장점가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라지고, 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단하다.내부 단편화가 발생할 수 있지만 고정 분할 방식에 비해 많은 공간이 낭비되지는 않는다.Retrospect잘한 점매일매일 빠지지 않고 강의를 들은 점매일 들은 강의 내용을 요약/정리하고 그 주차의 내용들을 하나의 게시글로 정리한 것

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

운영체제FIFO 스케줄링의 장단점이 뭔가요?장점구현이 간단하고 이해하기 쉽다공정성이 보장된다 - 모든 프로세스가 동등하게 처리된다.기아 현상이 발생하지 않는다.기아 현상 : 특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태단점긴 대기 시간을 초래할 수 있다.CPU 사용률이 낮아질 수 있다Burst Time이 짧은 프로세스가 Burst Time이 긴 프로세스 보다 늦게 들어온 경우에 Busrt Time이 짧은 프로세스가 오래 기다려야 한다. SJF를 사용하기 여러운 이유가 뭔가요?어떤 프로세스가 얼마나 실행될지 예측하기 힘들다.→ 예측하는 것이 거의 불가능하다.Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수 있다.→ Burst Time이 긴 프로세스는 Burst Time이 짧은 프로세스에게 계속해서 우선순위가 밀린다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?Time Slice를 작게 만드는 경우 Context Switching이 빈번하게 발생된다.→ CPU에서 프로세스가 실행되는 것보다 Context Switching이 빈번하게 발생함에 따라 성능이 떨어진다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하는 경우 CPU 사용률이 낮음→ I/O Bound Process일 확률이 높음CPU를 사용하는 프로세스가 실행하다가 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황인 경우 CPU 사용률이 높음→ CPU Bound Process일 확률이 높음 공유자원이란 무엇인가요?공유자원 : 여러 프로세스나 스레드가 동시에 접근하고 사용할 수 있는 컴퓨터 자원여러 프로세스가 공유하기 때문에 각 프로세스의 접근 순서에 따라서 결과가 달라질 수 있다.컨텍스트 스위칭으로 시분할 처리를 하기 때문에 프로세스간의 실행 순서를 예측하기 어렵다.⇒ 동기화 문제가 발생할 수 있다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호 배제 : 공유 자원은 한 번에 하나의 프로세스만 사용할 수 있다.비선점 : 다른 프로세스가 사용 중인 자원을 강제로 빼앗을 수 없다.점유와 대기 : 프로세스가 이미 자원을 보유한 상태에서 다른 자원을 요청하며 대기한다.원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형이다.자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?무한 재귀가 발생하여 스택 오버플로우 오류가 발생할 수 있다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ if (n

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

Algorithm참고 : https://visualgo.net/en/sortingBubble Sort인접한 두 원소를 비교하여 두 원소의 위치를 교환한다.과정배열을 처음부터 끝까지 순회하며 인접한 두 원소를 비교한다.왼쪽 원소가 오른쪽 원소보다 크면 두 원소를 교환한다.이 과정을 배열이 정렬될 때까지 반복한다.시간 복잡도O(n^2)장점이해와 구현이 간단한다.단점성능이 좋지 않다.Selection Sort배열에서 최솟값을 찾아 맨 앞으로 이동시킨다.과정정렬되지 않은 부분에서 최솟값을 찾는다.찾은 최솟값을 정렬되지 않은 부분의 첫 번째 원소와 교환한다.정렬된 부분을 한 칸 늘리고, 정렬되지 않은 부분에서 위 과정을 반복한다.시간 복잡도O(n^2)장점이해와 구현이 간단하다.단점성능이 좋지 않다.OSProgramming LanguageCompile Language개발자가 코드를 작성하고 컴파일을 수행하여 0과 1로된 기계어로 실행파일을 만든다.→ 기계어로 되어 있어 실행 속도가 인터프리터 언어에 비해 빠르다.컴파일 과정에서 개발자의 문법오류를 체크한다.ex) C, C++, C#Interpreter Language개발자가 작성한 코드를 미리 기계어로 만들어 놓지 않고 실행시 코드를 한줄씩 해석해 실행하는 언어→ 미리 검사를 하지 않기 때문에 실행할 때 오류가 발생할 수 있고, 컴파일 언어보다 느리다.ex) Javascript, Python, Ruby프로세스의 영역코드 영역실행해야 할 코드가 들어간다.데이터 영역전역 변수나 배열이 들어가는 영역스택 / 힙프로세스가 실행될 때 할당되는 메모리스택 : 지역변수와 함수 관련 값들이 저장힙 : 실행 중에 메모리 공간을 할당할 수 있는 유동적인 공간Compile 언어가 Process가 되는 방법개발자가 코드 작성전처리 단계 실행개발자가 작성한 코드를 확인하고 전처리 구문을 처리한다.C에서는 #이라는 키워드로 선언된다.ex) #include, #define MY_NUMBER 100코드에 있는 모든 주석은 삭제된다.결과물로 .i 파일이 생성된다.전처리기에서 나온 결과파일을 컴파일러가 처리한다.컴파일러는 .i 파일을 기계어에 가까운 어셈블리어로 변환시킨다.결과물로 .s 파일이 생성된다.어셈블러 작업이 수행된다.오브젝트 파일.o로 변환된다.오브젝트 파일은 0과 1로 구성되어 있다.코드영역과 데이터 영역이 나뉘어져 있다.링커 작업이 수행된다.모든 오브젝트 파일을 하나의 코드 영역과 데이터 영역으로 묶어준다.실제로 실행될 주소를 매핑시켜준다.결과물로 .exe 파일이 생성된다.사용자가 .exe파일을 실행시키면 OS가 프로세스를 생성한다.OS는 파일에 있는 코드 영역과 데이터 영역을 가져와 프로세스의 코드 영역과 데이터 영역에 넣어주고, 빈 상태의 스택과 힙을 할당한다.PCB를 만들어 프로세스를 관리가 가능하게 한다.PC(프로그램 카운터)에 다음 실행할 명령어의 주소를 생성한 프로세스의 코드영역의 첫번째 주소로 설정한다.→ OS의 CPU 스케줄링에 따라서 프로세스가 실행되다가 작업을 마친다.메모리 종류레지스터가장 빠른 기억장소, CPU 내에 존재한다.휘발성 메모리CPU를 나타내는 값에서 32bit, 64bit를 의미하는 것이 레지스터의 크기이다.CPU는 계산을 수행할 때 메인 메모리에 있는 값을 레지스터로 가져와서 계산한다.계산 결과는 메인 메모리에 저장한다.캐시휘발성 메모리속도가 매우 빠른 레지스터와 레지스터에 비해 상대적으로 느린 메인 메모리 사이의 속도 간극을 메우기 위해 필요한 데이터를 미리 가져와 저장하는 저장소성능의 이유로 여러 개가 존재한다.L1, L2, L3→ 숫자가 커질 수록 느린 캐시CPU가 값을 요청해 레지스터로 값을 옮겨야 한다면 빠른 캐시를 순차적으로 확인하고, 캐시에 데이터가 없으면 메인 메모리를 조회한다.ex) L1 → L2 → L3 → 메인 메모리보조 저장장치(HDD, SSD)비휘발성 메모리메인 메모리실제 운영체제와 다른 프로세스들이 올라가는 공간휘발성 메모리데이터를 저장하기 보다는 실행중인 프로그램만 저장한다.OS는 메모리를 관리하기 위해서 1Byte 크기로 구역을 나누고 숫자(주소)를 매긴다.32bit CPU, 64bit CPU32bit CPU레지스터, ALU, Data Bus : 32bit메모리 : 2^32 = 4GB64bit CPU레지스터, ALU, Data Bus : 64bit메모리 : 2^64 = 16384PiB64bit CPU가 32bit CPU 보다 한번에 처리할 수 있는 양이 많기 때문에 속도가 더 빠르다.물리 주소 & 논리 주소물리 주소 공간 : 0x0부터 시작하는 주소 공간논리 주소 : 사용자 관점에서 바라 본 주소 공간사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근할 수 있다.OS를 위한 공간은 따로 확보한다.경계 레지스터H/W적으로 OS 공간과 사용자 공간을 나누는 레지스터CPU 내에 존재하는 레지스터메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났다면 검사하고, 벗어났다면 해당 프로세스를 종료시킨다.절대 주소 & 상대 주소개발자가 프로그램이 실행될 주소를 신경쓰지 않고 개발할 수 있는 이유→ 컴파일러가 컴파일을 할 때 메모리 0번지에서 실행한다고 가정하기 때문절대 주소 : 메모리 관리자가 바라본 프로세스가 올라간 물리 주소상대 주소 : 사용자가 바라보는 논리 주소재배치 레지스터프로그램의 시작 주소가 저장되어 있다.사용자가 요청한 논리 주소의 데이터를 물리 주소로 치환해준다.사용자가 메모리에 접근할 때마다 논리 주소를 물리 주소로 치환해준다.메모리 할당 방식메모리 오버레이메모리보다 용량이 큰 프로그램을 실행시키는 방법큰 프로그램을 메모리에 올릴 수 있을 정도로 분할하여 일부만 실행하고, 실행되지 않은 프로그램은 HDD의 스왑 영역에 저장하는 방식Swap스왑영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 옮기는 것가변 분할 방식(= Segmentation, 세그멘테이션)프로세스의 크기에 따라 메모리를 나누는 방식하나의 프로세스가 메모리에 연속된 공간에 할당된다.→ 연속 메모리 할당이라고 한다.장점메모리에 연속된 공간에 할당된다.→ 내부 단편화가 없다.단점외부 단편화가 발생한다.고정 분할 방식(= Paging, 페이징)프로세스의 크기와는 상관없이 정해진 크기로 나누는 방식하나의 프로세스가 메모리에 분산되어 할단된다.→ 비연속 메모리 할당이라고 한다.장점구현이 간단하고 오버헤드가 적다.단점작은 프로세스도 큰 영역에 할당되어 내부 단편화가 발생한다.내부 단편화프로세스에 필요한 메모리보다 더 큰 고정 크기의 메모리 블록이 할당될 때 발생한다.할당된 메모리와 실제 사용된 메모리 사이의 차이로 인해 메모리 공간이 낭비된다.고정 크기 분할 방식에서 주로 발생한다.해결 방법은 딱히 없고, 분할되는 크기를 조절하여 내부 단편화를 최소화한다.외부 단편화메모리 할당과 해제를 반복하면서 작은 빈 공간들이 메모리 곳곳에 흩어져 생기는 현상전체 가용 메모리는 충분하지만, 연속된 큰 블록을 할당할 수 없는 상황을 만든다.가변 분할 방식에서 주로 발생한다.조각모음외부 단편화가 발생한 공간을 합쳐주는 작업현재 메모리에서 실행되고 있는 프로세스들의 작업을 일시 주징하고, 메모리 공간을 이동시켜야 한다.→ 오버헤드가 발생한다.버디 시스템가변 분할 방식 + 고정 분할 방식오늘날의 OS가 채택한 메모리 할당 방식2의 제곱으로 메모리를 분할하여 할당하는 방식→ 근접한 메모리 공간을 합치기 쉽다.→ 조각 모음보다 훨씬 간단하다.장점가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라지고, 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단하다.내부 단편화가 발생할 수 있지만 고정 분할 방식에 비해 많은 공간이 낭비되지는 않는다.

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

Algorithm하노이의 탑하향식 계산 방식의 좋은 예시→ 재귀함수의 좋은 예시제약 조건한 번에 하나의 원반을 움직일 수 있다.가장 위에 있는 원반만 옮길 수 있다.아래에 작은 원반이 올 수 없다.OS교착상태여러 프로세스가 서로 다른 프로세스의 작업이 끝나길 기다리다가 아무 작업도 수행되지 않는 상태발생 원인상호 배제 : 공유 자원은 한 번에 하나의 프로세스만 사용할 수 있다.비선점 : 다른 프로세스가 사용 중인 자원을 강제로 빼앗을 수 없다.점유와 대기 : 프로세스가 이미 자원을 보유한 상태에서 다른 자원을 요청하며 대기한다.원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형이다.하나라도 충족하지 않으면 교착상태가 발생하지 않는다.→ 교착 상태를 예방하는 것을 구현하기는 매우 어려워서 교착 상태를 해결하는 방향으로 발전됐다.해결방법교착상태 회피프로세스들에게 자원을 할당할 대 어느 정도 자원을 할당해야 교착상태가 발생하는지 파악해서 교착상태가 발생하지 않는 수준의 자원을 할당한다.전체 자원의 수와 할당된 자원의 수를 기준으로 안정상태와 불안정 상태로 나뉜다.OS는 안정상태를 유지하려 한다.안전 상태: 모든 프로세스가 요구한 최대 자원을 할당받아 실행을 완료할 수 있는 상태불안정상태에 있더라도 무조건 교착상태에 들어가는 것이 아니라 교착상태에 빠질 확률이 높아지는 것이다.은행원 알고리즘작동 원리프로세스가 자원을 요청할 때, 그 요청이 시스템을 안전 상태로 유지할 수 있는지 확인한다.안전 상태를 유지할 수 있는 요청만 수락하고, 불안정한 상태를 초래할 수 있는 요청은 거절한다.주요 개념최대 요구량(Max Need): 프로세스가 실행을 완료하기 위해 필요한 최대 자원 양할당량(Allocation): 현재 프로세스에 할당된 자원 양필요량(Need): 최대 요구량에서 현재 할당량을 뺀 값가용량(= 시스템 총 자원, Available): 시스템에서 현재 사용 가능한 자원 양단점비용이 비싸고 비효율적이다.교착상태 검출가벼운 교착 상태 검출타이머를 이용하는 방식프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주하고 교착상태를 해결한다.교착상태 해결 방법일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백한다.무거운 교착 상태 검출자원 할당 그래프를 이용하는 방식OS가 자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드가 발생한다.But. 가벼운 교착 상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스가 발생하지 않는다.OS에서 프로세스가 어떤 작업을 사용하는지 지켜보고 교착상태가 발생했다면 해결한다.