인프런 워밍업 클럽 CS 2기 - 3주차 발자국

자료 구조 및 알고리즘 삽입 정렬배열을 정렬된 부분, 정렬되지 않은 부분 총 두 영역으로 나누어, 정렬되지 않은 부분에서 데이터를 하나씩 꺼내어 정렬된 부분에 삽입하는 정렬 알고리즘이다.시간 복잡도는 O(n²)이다.function insertionSort (arr) { for (let i=1; i=0; j--) { if (arr[j] > memoried) arr[j+1] = arr[j]; else break; } arr[j+1] = memoried; } return arr; } console.log(insertionSort([4,1,3,5])) // [1,3,4,5] 병합 정렬병합 정렬은 분할 정복을 이용하여 재귀적으로 정렬하는 알고리즘이며, 배열을 반으로 분할하고 다시 병합한다.분할은 log n, 병합할 때 비교는 n이 걸리므로, 시간 복잡도는 O(n log n)이다.function mergeSort(arr) { if (arr.length 퀵 정렬병합 정렬은 분할 정복을 이용하여 재귀적으로 정렬하는 알고리즘이며, 배열에서 하나의 숫자를 '피벗'으로 선택한 뒤 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할 다시 병합한다.시간복잡도의 평균은 O(n log n)이지만, 피벗에 따라 O(n²) 일 수도 있다.퀵 정렬은 병합 정렬보다 더 적은 메모리와 비교하는 횟수가 더 적어서 효율적인 경우가 있다.function quickSort (arr, left = 0, right = arr.length - 1) { if (left 동적 프로그래밍 - 메모이제이션재귀 함수는 중복된 계산을 여러 번 수행하여 성능이 좋지 않다.메모이제이션은 계산된 값을 저장하고 이를 다시 사용하여 성능을 높일 수 있다.function fibonacci(n ,memo = {}) { if (n 동적 프로그래밍 - 타뷸레이션타뷸레이션은 상향식 접근 방식으로, 필요하지 않는 결과값도 계산하여 재귀를 사용하지 않기 때문에 메모제이션보다 더 빠를 수 있다.특히 재귀적이지 않기 때문에 메모리를 절약할 수 있다.function fibonacciTabulation(n) { const table = [0, 1] for (let i=2; i 미션1지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬장점: 구현이 간단하고, 이미 정렬된 경우 시간 복잡도가 O(n)이다.단점: 평균 및 최악의 경우 시간 복잡도가 O(n²)이다.시간 복잡도:최선: O(n)평균: O(n²)최악: O(n²)선택 정렬장점: 구현이 간단하다.단점: 항상 시간 복잡도가 O(n²)이다.시간 복잡도:최선: O(n²)평균: O(n²)최악: O(n²)삽입 정렬장점: 작은 데이터 집합에 대해 빠르게 동작하며, 안정적인 정렬 알고리즘이다.단점: 평균 및 최악의 경우 시간 복잡도가 O(n²)이다.시간 복잡도:최선: O(n)평균: O(n²)최악: O(n²)병합 정렬장점: 분할 병합 방식으로 시간 복잡도가 O(n log n)이다.단점: 추가적인 메모리 공간이 필요하여, 공간 복잡도가 O(n)이다.시간 복잡도:최선: O(n log n)평균: O(n log n)최악: O(n log n)퀵 정렬장점: 분할 병합 방식으로 O(n log n)의 시간 복잡도를 가지고, 메모리 사용이 효율적이다.단점: 최악의 경우 O(n²)이다.시간 복잡도:최선: O(n log n)평균: O(n log n)최악: O(n²)메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.타뷸레이션을 선택할거 같습니다.메모이제이션의 경우 재귀적으로 함수를 호출하기 때문에 함수를 생성하면 메모리를 차지하고, 함수가 종료되기 전까지 점유합니다. 반면에 타뷸레이션의 경우 재귀적으로 함수를 호출하지 않기 때문에 하나의 함수에 해당되는 메모리만 차지하기 때문에 메모리가 부족한 시스템에 더 적합합니다. 운영체제 및 CS 가상메모리물리메모리의 크기보다 프로세스가 요구하는 메모리 크기가 클 경우에 보조저장장치의 스왑 영역을 활용하여 메모리의 크기를 늘리는데, 물리메모리 + 스왑영역을 합쳐서 가상메모리라고 부른다.만약 CPU의 비트가 32bit인 경우, 가상메모리의 크기는 4GB까지 가능하다. 메모리 관리자는 프로세스가 메모리의 논리주소를 요구할 경우 물리 메모리의 물리주소를 전달해주는데, 이를 동적 주소 변환이라고 한다.메모리 관리자가 매핑 테이블을 이용하여 논리주소를 물리주소로 변환할 수 있다. 세그먼테이션(배치 정책)프로세스에 메모리를 할당해주는 배치 정책 중 가변적으로 메모리를 할당해준다고 해서 세그먼테이션이라고 한다. 메모리 관리자는 논리주소를 세그먼테이션 테이블에서 물리주소로 변환할 수 있는 정보를 가지고 물리주소로 변환한다.세그먼테이션 테이블에는 세그먼트 번호, Base Address, Bound Address 가 있다. 논리주소를 물리주소로 변환하는 과정프로세스가 논리주소를 요청할 때, 메모리관리자는 세그먼트 번호를 찾아낸다.메모리 관리자는 Segment Table Base Register를 이용해 물리메모리에 있는 세그먼테이션 테이블을 찾는다.세그먼테이션 테이블에서 세그먼테이션 번호와 일치되는 행의 정보를 얻는다.Bound Address보다 논리주소가 클 경우 메모리 침범 인터럽트를 발생시켜 프로그램을 종료시키고, 크지 않을 경우 Base Address + 논리 주소를 합쳐 물리주소를 변환하여 프로세스에게 전달한다. 세그멘테이션은 메모리를 가변적으로 분할 할 수 있고, 코드영역, 힙영역, 데이터영역, 스택 영역 등을 모듈로 관리할 수 있어 메모리 접근 보호가 편리한 장점이 있다.반면, 외부 단편화가 발생하기 때문에 분할되어 있는 메모리의 공간보다 큰 메모리를 요구하는 프로세스가 있는 경우, 메모리 공간을 합쳐여하는 오버헤드가 발생하는 단점이 있다. 페이징(배치 정책)프로세스에 메모리를 할당해주는 배치 정책 중 고정적으로 메모리를 할당해준다고 해서 페이징이라고 한다. 논리 주소 공간에서 페이징은 페이지라고 불리고, 물리 주소 공간에서 페이징은 프레임이라고 불린다. 메모리 관리자는 논리주소를 페이지 테이블에서 물리주소로 변환할 수 있는 정보를 가지고 물리주소로 변환한다.페이지 테이블에는 인덱스, 프레임이 있다. 논리주소를 물리주소로 변환하는 과정프로세스가 논리주소를 요청할 때, 메모리관리자는 인덱스와 오프셋을 구한다.인덱스는 (논리주소 / 페이지 크기)의 몫오프셋은 (논리주소 / 페이지 크기)의 나머지메모리 관리자는 Page Table Base Register를 이용해 물리메모리에 있는 페이지 테이블을 찾는다.세그먼테이션 테이블에서 세그먼테이션 번호와 일치되는 행의 정보를 얻어 프레임을 얻는다.프레임의 물리주소과 오프셋을 합산하여 실제 물리주소를 계산하여 프로세스에게 물리주소를 전달한다. 페이징은 메모리를 세그먼테이션보다 쉽게 구현할 수 있는 장점이 있다.반면, 내부단편화가 발생하기 때문에 낭비되는 메모리 공간이 발생하고, 코드영역, 힙영역, 데이터영역, 스택 영역 등을 메모리에 할당해야하기 때문에 논리적으로 분할 할 수 없고, 메모리 접근 보호가 어려우며, 프로세스가 많아지면 페이지 테이블이 많아지고 메모리 공간을 차지 하기 때문에 사용자 메모리 공간이 줄어드는 단점이 있다. 페이지드 세그멘테이션(배치 정책)세그멘테이션과 페이지의 혼합한 배치정책이다. 메모리 관리자는 논리주소를 페이지드 세그멘테이션 테이블에서 물리주소로 변환할 수 있는 정보를 가지고 물리주소로 변환한다.페이지드 세그멘테이션은 2개의 테이블을 가지는데, 세그멘테이션 테이블과 페이지 테이블이다.세그멘테이션 테이블은 세그먼트번호, 권한비트, 페이지넘버, Bound Address를 가진다.페이지 테이블은 인덱스, 프레임을 가진다. 메모리 접근권한은 읽기, 쓰기, 실행 권한이 있다.프로세스의 영역별 권한은 아래와 같다.코드 영역: 읽기와 실행 가능, 수정 불가데이터 영역: 읽기와 쓰기 가능, 실행 불가능스택 & 힙 영역: 읽기와 쓰기 가능, 실행 불가능 페이지드 세그멘테이션에서 논리주소를 물리주소로 변환할 때 권한도 확인한다. 논리주소를 물리주소로 변환하는 과정프로세스가 논리주소를 요청할 때, 메모리관리자는 세그멘테이션 번호를 찾아낸다.세그먼테이션 테이블에서 세그먼테이션 번호와 일치되는 행의 정보를 얻어 권한이 위반하면 인터럽트를 발생시켜 프로그램을 종료시키고, 위반하지 않으면 페이지넘버와 페이지 개수를 얻는다.페이지 테이블에서 접근한 페이지 넘버와 일치되는 행의 프레임을 얻는다.프레임과 페이지 개수를 합산한 물리 주소를 프로세스에 전달한다. 테이블을 확인하기 위해 메모리에 2번 접근해야하는 단점이 있어 현대에서는 페이징과 페이지드 세그멘테이션을 적절하게 사용하고 있다. 디멘드 페이징(가져오기 정책)메모리에 사용할것 같은 프로세스를 메모리에 올리고, 그렇지 않은 프로세스는 스왑영역에 위치시켜 메모리를 효율적으로 사용하는 정책이다. 지역성 이론시간적 지역성: 최근에 접근한 데이터는 다시 접근할 가능성이 높다.공간적 지역성: 현재 접근한 데이터와 가까운 위치에 있는 데이터가 곧 접근될 가능성이 높다. 스왑영역에서 메모리로 가져오는 것을 스왑인, 반대로 메모리에서 스왑영역으로 내보내는 것을 스왑아웃이라고 한다. 페이지 테이블의 한 행을 페이지 엔트리(PTE)라고 불리고, 여러 비트를 통해 물리메모리의 프레임 또는 스왑영역의 위치를 알 수 있다.접근 비트: 페이지가 메모리에 올라온 후 접근 유무변경 비트: 페이지 데이터의 변경 유무유효 비트: 페이지가 물리 메모리에 있는지 스왑 영역에 있는지 유무(1은 스왑영역에 있다는 뜻)읽기/쓰기/실행 비트: 페이지에 대한 접근 권한 Page Fault프로세스가 가상주소를 요청하고 메모리 관리자가 페이지 테이블을 통해 프레임이 물리 메모리에 없으면 Page Fault 인터럽트가 발생한다.그리고 프로세스는 대기 상태에 들어가고, 메모리 관리자는 스왑인을 통해 물리 메모리에 프레임을 옮기고 다시 재시작된다. 페이지 교체 정책메모리 공간이 부족할 때 어떤 페이지를 스왑 영역으로 보낼지 결정하는 중요한 알고리즘이다. 주요 페이지 교체 정책1. Random- 페이지를 랜덤으로 교체한다.- 지역성 이론을 고려하지 않고 자주 사용되는 페이지도 보낼 수 있기 때문에 거의 사용되지 않는다.2. FIFO(First In First Out)- 가장 먼저 메모리에 들어온 페이지 교체한다.- 구현이 간단하지만 자주 사용되는 페이지도 교체될 수 있다.3. Optimum- 앞으로 오랫동안 사용되지 않을 페이지 교체한다.- 이상적인 알고리즘이나 구현하기 어렵다.4. LRU(Least Recently Used)- 가장 최근에 사용되지 않은 페이지 교체한다.- 최근 사용된 페이지가 다시 사용될 확률이 높다는 가정에 따라 동작한다.LRU를 유사하게 구현하기 위한 알고리즘1. Clock Algorithm페이지 테이블의 접근 비트를 사용하여, 일정 시간 동안 참조된 페이지인지 아닌지 확인한다.클락 핸드가 시계 방향으로 움직이며, 접근 비트가 0인 페이지를 교체한다.Enhanced Clock Algorithm은 변경 비트까지 고려한다.2. Second Chance AlgorithmFIFO 방식의 문제점을 보완하여 맨 처음 페이지가 최근에 사용된 경우 큐의 맨 뒤로 이동시켜 수명 연장한다.스레싱과 워킹셋스레싱은 CPU 사용률이 떨어지는 현상이다.Page Falut가 발생하면 CPU 사용하는 것보다 스왑인, 스왑아웃 동작하는데 자원을 소모하여 CPU 사용률이 떨어지고, 그렇다고 메모리에 페이지를 많이 올리게 되면 프로세스가 사용해야할 페이지가 줄어들어 CPU 사용률이 떨어진다. 워킹셋(Working Set)현재 메모리에 올라와 있는 페이지는 자주 사용할 확률이 높기 때문에 하나의 세트로 묶는데 이를 워킹셋이라고 한다.프로세스가 준비상태에서 컨텍스트 스위칭을 통해 실행상태로 변경할 때 사용한다.주변장치(I/O, 디바이스, 저장장치)그래픽카드, 마우스, 키보드, 하드디스크 등을 주변장치라고 한다. 주변장치는 메인보드의 버스를 통해 연결되고, Address 버스, data 버스, control 버스가 있다.주변장치의 레지스터는 입출력 데이터를 저장하는 역할을 한다. 주변장치는 캐릭터 디바이스, 블록 디바이스로 나뉜다.캐릭터 디바이스는 적은 양의 데이터(문자)를 전송하는 장치로, 마우스나 키보드가 있다.블록 디바이스는 많은 양의 데이터를 전송하는 장치로, 하드디스크가 있다.초기에는 CPU가 I/O 요청을 대기해야해서 CPU 사용률이 떨어졌고, 이를 해결하기 위해 입출력 제어기가 도입되어 I/O 작업을 CPU 대신 관리한다.입출력 제어기는 CPU와 메모리를 연결하는 시스템 버스, 주변장치를 연결하는 입출력 버스로 구성되어 있다.그래픽카드는 빠른 속도를 위해 시스템 버스에 연결한다.입출력 버스는 고속과 저속으로 나뉘는데, 고속은 하드디스크과 연결하고 저속은 마우스, 키보드와 연결한다.입출력 데이터를 저장하기 위해서 CPU 도움이 필요한데, DMA 를 통해 CPU 도움없이 주변장치가 메모리에 접근가능하다.CPU로 접근하는 메모리와 DMA로 접근하는 메모리는 다른데, DMA로 접근하는 메모리는 Memory Mapped I/O 라고 한다.마우스, 키보드볼 마우스는 잔 고장이 많았다.광학 마우스는 마우스 아래에 달린 카메라를 통해 1500회 이상을 사진으로 촬영해 마우스 좌표값을 얻는다.마우스 이벤트 전달마우스의 디바이스 컨트롤러의 DSP를 통해 좌표값을 얻는다.마우스 드라이버가 DSP에서 좌표값을 가져간다.마우스 드라이버가 CPU에 인터럽트를 보내고, 좌표 데이터 또는 클릭 이벤트를 전달해준다.운영체제가 Foreground로 프로세스에게 이벤트를 전달해준다.키보드도 마우스와 유사하게 사용자가 입력한 키를 디바이스 컨트롤러가 감지해 CPU로 인터럽트를 보내고, 운영체제가 Foreground로 프로세스에게 이벤트를 전달해준다. 하드디스크하드디스크는 Spindle이 있고, 여러개의 Platter가 있다.Platter는 disk arm에 달린 read/write head를 통해 읽고 쓰며, 자성을 띄기 때문에 N극은 0 S극은 1이다.여러개의 Platter에 track이 같은 위치에 있는 것을 Cylinder라고 한다.Sector는 하드디스크의 가장 작은 단위이다.하드디스크는 헤드를 통해 읽고, 데이터를 읽는 시간을 Seek Time이라고 한다.헤드를 통해 데이터를 찾기 때문에 찾는 시간이 오래걸린다. SSD는 HDD와 달리 물리적으로 데이터를 읽는 것이 아니라 전기적으로 읽고 쓰기 때문에 빠르고, 조용하다. 파일과 파일시스템파일은 사용자가 운영체제에 관리를 요청하면, 운영체제는 파일시스템을 통해 파일을 관리한다. 파일 시스템은 아래의 기능을 제공한다.파일 및 디렉토리 생성,수정, 삭제파일 접근 권한 관리데이터 무결성 보장백업 및 복구암호화파일은 블록 디바이스인데, 사용자가 바이트 단위로 읽으려면 파일 시스템을 통해 읽을 수 있다.파일의 정보는 FCB가 있는데 FCB를 통해 사용자는 시스템 콜인 open(), close() 함수를 통해 파일을 열고 닫을 수 있다. 순차 파일 구조는 카세트 테이프처럼 데이터가 연속적으로 저장되는 구조이며 구조가 단순하여 공간 낭비가 적다. 만약 특정 위치로 이동하려면 lseek() 시스템 콜 함수를 통해 접근할 수 있고, 이는 단점으로 데이터 수정 및 삭제하는데 시간이 오래걸린다.직접 파일 구조는 해시 함수를 이용해 데이터를 저장하는 방식으로, 해시 함수에 따라 성능에 영향을 준다.인덱스 파일 구조: 순차 접근과 직접 접근의 장점을 결합한 방식으로, 인덱스 테이블을 이용해 빠른 접근이 가능하다. 디렉토리파일은 데이터를 갖고 있고, 디렉토리는 파일 정보를 갖고 있는 파일이다. 파일과 디스크파일이 저장될 때, 디스크는 일정 크기로 나뉜 블록으로 데이터를 저장한다.데이터 저장방식은 연속할당, 불연속할당이 있다.연속 할당은 연속적으로 데이터를 저장하며 외부 단편화가 발생한다.불연속 할당은 분산하여 데이터를 저장하며 내부 단편화가 발생한다.연결 할당은 연결 리스트 자료구조로 데이터를 연결하여 접근한다.인덱스 할당은 별도의 인덱스 블록을 통해 데이터에 접근한다. 파일시스템은 비어있는 블록을 별도로 관리하는데, 이를 free block list라고 한다.파일을 삭제할 때 실제 파일이 삭제되는 것이 아니라, 파일의 헤더만 삭제하고 사용했던 블록을 free block list에 추가한다.그래서 포렌식으로 데이터를 복구할 때 실제 데이터는 존재하기 때문에 복구가 가능하다. 미션2메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터CPU가 처리하기 위해 메인메모리에 있는 값을 레지스터로 가져와 계산을 하고, 결과값을 메인메모리에 저장한다. 레지스터는 CPU에 존재한다.전력이 끊기면 데이터가 사라지는 휘발성 메모리이다.캐시메인메모리의 있는 값을 레지스터로 가지고 올 때, 성능을 위해 미리 값을 가져온다.캐시는 CPU에 L1, L2, L3... 등으로 존재한다.전력이 끊기면 데이터가 사라지는 휘발성 메모리이다.메인메모리(RAM)운영체제나 프로세스가 올라가는 공간이다.전력이 끊기면 데이터가 사라지는 휘발성 메모리이다.보조저장장치(HDD, SDD)전력이 끊겨도 데이터가 유지되는 비휘발성 메모리이다.파일, 데이터를 저장하는 공간이다. 가격 : 레지스터 > 캐시 > 메인메모리 > 보조저장장치용량 : 레지스터 속도 : 레지스터 > 캐시 > 메인메모리 > 보조저장장치사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요? 가변 분할 방식 장점은 낭비되는 메모리 공간이 없다.(내부 단편화 없음)단점은 메모리 할당된 2개의 프로세스가 종료되고 2개의 프로세스의 요구하는 만큼 메모리 공간을 요구하는 프로세스가 발생할 경우, 실행중인 프로세스를 종료하고 메모리를 합쳐야하는 오버헤드가 발생한다.(외부 단편화)고정 분할 방식장점은 구현이 단순하고 오버헤드가 적다단점은 낭비되는 메모리 공간이 있다.(내부 단편화)CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱5. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요? 이유를 함께 적어주세요.초기의 컴퓨터는 필수적인 장치가 아니었습니다. 그러나 컴퓨터가 발전하면서 운영체제를 통해 컴퓨터를 효율적으로 관리하고, 개인 데이터를 저장하기 위해서 오늘날에는 거의 필수로 필요한 저장장치가 되었습니다.파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일 삭제시 파일의 헤더만 삭제하고 실제 데이터는 존재하기 때문에, 포렌식으로 파일을 복구할 수 있습니다.

인프런 워밍업 클럽 CS 2기 - 2주차 발자국

자료 구조 및 알고리즘 재귀함수재귀란 어떤것을 정의할 때 자기 자신을 참조하는 것을 의미한다.즉, 재귀함수란 함수를 정의할 때 자기 자신을 참조하는 함수를 의미한다. 재귀 함수는 자기 자신을 호출하므로 만약 기저 조건을 정의하지 않은경우 메모리를 다 사용할 때 까지 호출된다.함수가 호출되면 메모리의 콜스택에 올라가고, 함수가 종료되면 메모리의 콜스택에서 제거된다. 그래서 재귀 함수의 기저조건을 작성하지 않거나 잘못 작성할 경우, 재귀함수가 종료되지 않아 재귀 함수가 메모리의 콜스택 영역에 존재하고 결국 메모리 공간을 가득 채워 스택 오버플로우가 발생해 프로그램이 강제 종료된다. 재귀적으로 생각하기재귀 함수는 재귀적으로 함수를 호출하기 때문에 메모리를 차지하는 비효율적인 방법으로 보일 수 있다.그러나 하위 문제 해결방법을 기반으로 문제를 해결하는 하향식 방식으로 효율적으로 문제를 해결할 수 있다. 팩토리얼function factorial (number) { if (number === 1) return 1; if (number 문자열 길이 확인function strLength (str) { if (str.length === 0) return 0; return strLength(str.slice(0, -1)) + 1 } console.log(strLength('string')) 지수함수function power (x, n) { if (n === 0) return 1; return x * power(x, n - 1) } console.log(power(2, 5)) 하노이의 탑3개의 기둥에 3개의 원판을 옮기려고 할 때, 재귀적인 하향식 방법으로 문제를 해결할 수 있다. 원판을 count라고 정하고 아래의 접근방법을 따른다.출발지 기둥에 있는 (count - 1)개의 원판을 임시 기둥에 옮긴다.출발지 기둥에 있는 1개의 원판을 목적지 기둥에 옮긴다.임시 기둥에 있는 (count - 1)개의 원판을 목적지 기둥에 옮긴다.... 반복 그리고 옮기려는 원판이 없다면 함수를 종료하는 기저조건을 추가한다. 위의 하위 문제 해결방법으로 전체 문제를 해결할 수 있다. function hanoi(count, from, to, temp) { if (count === 0) return; hanoi(count - 1, from, temp, to); console.log(`${count} => ${from}에서 ${to}`); hanoi(count - 1 , temp, to, from); } hanoi(3, 'A', 'C', 'B') 버블 정렬정렬되지 않는 배열의 숫자 원소들을 정렬하는 알고리즘이다.해당 알고리즘은 이중 for 반복문을 사용하므로 시간복잡도가 O(n²) 이다. index 위치에 있는 숫자, index + 1 위치에 있는 숫자를 비교하여, index 위치에 있는 숫자가 더 크다면 원소 위치를 바꾼다.function bubbleSort (arr) { for (let i=0; i arr[j+1]) { [arr[j], arr[j+1]] = [arr[j+1], arr[j]] } } } return arr; } console.log(bubbleSort([3,1,2,4])) 선택 정렬정렬되지 않는 배열의 숫자 원소들을 정렬하는 알고리즘이다.해당 알고리즘은 이중 for 반복문을 사용하므로 시간복잡도가 O(n²) 이다. 배열의 원소들을 하나씩 확인하면서 가장 작은 값을 찾아 출발지의 index1, 가장 작은 원소의 index2 를 찾아 위치를 바꿔준다.function selectionSort (arr) { for (let i=0; i 미션1재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?함수가 호출되면 메모리의 콜스택 영역에 올라가고 함수가 종료되면 콜스택 영역에서 제거됩니다.만약 기저조건을 만들지 않거나 잘못 설정할 경우, 함수가 메모리의 콜스택 영역에 존재하고 결국 메모리 공간을 가득 채워 스택 오버플로우가 발생해 프로그램이 강제 종료됩니다.2. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function recursionOdd (n) { if (n === 0) return 0; return n % 2 === 1 ? n + recursionOdd(n - 1) : recursionOdd(n - 1); } console.log(recursionOdd(10)); // 25 자료 구조 및 알고리즘 SJF(Shortest Job First)FIFO 스케줄링의 단점을 보안하기 위해 도입되어 Burst Time이 짧은 프로세스가 가장 먼저 실행된다.문제는 Burst Time을 예측하기 어렵고, Burst Time이 긴 프로세스의 경우 무한정 대기할 수 있는 문제점이 있다. RR(Round Robin)CPU를 일정 시간만큼 할당하는 시간을 타임 슬라이스 또는 타임 퀀텀이라고 부른다.기존의 FIFO 스케줄링의 평균대기시간을 보완하고자 CPU를 일정시간만큼 프로세스에 할당하여 평균대기시간을 낮춘다. RR은 타임슬라이스에 따라 성능이 결정된다.타임 슬라이스를 길게 잡으면 FIFO 스케줄링이 된다.타임 슬라이스를 짧게 잡으면 프로세스간 컨텍스트 스위칭이 자주 발생해, 프로세스 처리량보다 컨텍스트 스위칭 처리량이 더 큰 문제점이 생깁니다. MLFQ(Multi Level Feedback Queue)RR 스케줄링을 보완한 방법으로 CPU Bound Process와 I/O Bound Process를 구분하여 우선순위 큐에 프로세스를 넣어 필요로하는 CPU 시간만큼 타임슬라이스를 정해 효율을 증가시켰다. CPU Bound Process는 CPU 연산이 많이 필요한 프로세스이고, I/O Bound Process는 입출력 작업이 많이 필요한 프로세스이다. 운영체제가 구분하는 방법은 단순하게 타임 슬라이스로 구분한다.만약, 타임 슬라이스만큼 CPU를 할당했을 때 운영체제에 의해 CPU를 빼앗기게 되면 상대적으로 CPU 연산이 많으므로 CPU Bound Process 이다.만약, 타임 슬라이스보다 먼저 CPU를 반환하는 프로세스는 상대적으로 CPU 연산이 적으므로 I/O Bound Process 이다. 프로세스간 통신 방법하나의 컴퓨터에서 프로세스간 통신공유하고 있는 하나의 파일을 읽고 쓰기를 통해 프로세스간 통신한다.운영체제가 생성한 파이프를 통해 프로세스간 통신한다. 외부 컴퓨터에 있는 프로세스간 통신네트워크를 통해 운영체제가 제공하는 소켓 통신을 통해 프로세스간 통신한다.RPC(원격 프로세스 호출)을 통해 프로세스간 통신한다. 🏷 프로세스 내부의 쓰레드는 Code 영역, Data 영역 그리고 Heap 영역을 공유하고 있으므로 이것은 쓰레드간 통신한다고 볼 수 있다. 공유자원과 임계구역프로세스간 통신을 할 때 공유해서 사용하는 변수나 파일이다. 동시에 여러 프로세스가 사용하지 않는 영역을 임계구역이라고 한다.그리고 공유 자원을 사용하기 위해 프로세스간 경쟁하는 조건을 경쟁조건이라고 한다. 만약 여러 프로세스가 사용할 경우 동기화 문제가 발생한다.여러 프로세스가 사용하게되면 프로세스가 반환한 결과값을 사용하지 않고 상태에서 이전의 값을 사용하여 원하는 결과를 만들 수 없는 문제가 발생한다. 이 문제를 상호배제의 요구사항을 충족하는 방법으로 해결한다.임계구역엔 하나의 프로세스만 접근한다.여러 프로세스의 요청에도 단 하나의 프로세스만 접근가능하다.공유자원을 다른 프로세스도 사용해야하므로, 임계구역에 접근한 프로세스는 최대한 빠르게 나와야한다. 상호배제의 요구사항을 충족하는 방법은 아래와 같다.세마포어모니터 세마포어프로세스는 대기 큐에 대기하고, 운영체제가 세마포어를 프로세스에게 전해주어 자원을 사용하는 프로세스가 작업을 끝날 때 까지 다른 프로세스는 세마포어가 없기 때문에 공유자원에 접근하지 못한다.세마포어는 정수형 변수이고, 여러개를 설정할 수 있다.세마포어의 단점은 코드로 구현할 때 순서를 잘못 작성하면, 세마포어를 잘못 사용할 가능성이 존재한다.모니터프로그래밍 언어에서 지원해주는 것이로, 편리하고 안전하게 사용가능하다. Java 프로그래밍 언어의 경우, synchronized 키워드를 함수 선언할 때 사용하여 synchronized 키워드가 선언된 함수들은 동시에 사용하지 못한다.데드락여러 프로세스가 서로 다른 프로세스의 작업이 끝나 해당 프로세스가 사용하던 자원을 사용하기 위해 끊임없이 기다리고 교착상태에 빠진 상태를 데드락이라고 한다. 교착상태의 필요조건 4가지상호배제 : 하나의 프로세스가 자원을 사용하고 있다면 다른 프로세스는 해당 자원을 사용할 수 없다.비선점 : 하나의 프로세스가 자원을 사용하고 있다면 다른 프로세스는 해당 자원을 빼앗을 수 없다.점유와 대기 : 프로세스가 자원을 사용하면서 다른 자원을 원해야한다.원형 대기 : 점유와 대기하는 프로세스들이 서로 원형 관계를 이루어야 한다. 데드락 해결 방법교착상태 회피란, 운영체제가 교착상태에 빠지지 않을 만큼 프로세스에 자원을 할당한다.교착상태 회피는 전체 자원의 수, 할당한 자원의 수에 따라 안정상태, 불안정상태로 나뉜다.운영체제는 안정상태를 유지하기 위해 적절한 자원의 수를 프로세스에 할당해준다.교착상태 회피안정상태프로세스는 자신이 요규하는 최대 자원의 수를 운영체제에게 알려주는데, 프로세스에 할당하고 사용가능한 자원의 수보다 프로세스가 요구하는 자원의 수가 많을 경우 운영체제는 거부한다.만약 프로세스가 요구하는 자원의 수가 적을 경우 운영체제는 자원을 할당해주고, 할당해준 프로세스가 작업을 마친 후 자원을 반환하고 다른 프로세스에게 자원을 분배한다.이처럼 프로세스의 최대 자원 요구량에 자원을 할당해줄 수 있을 만큼 사용가능한 자원 수를 갖고 있는 상태를 안정상태라고 한다.불안정상태프로세스에 할당하고 사용가능한 자원의 수보다 프로세스가 요구하는 자원의 수가 많을 경우 운영체제는 거부하는데, 사용 가능한 자원이 하나의 프로세스라도 최대 요구량에 미치지 못할 경우를 불안정상태라고 한다.사람들은 교착상태를 회피하는 것 보다, 교착상태에 빠질 경우 해결하는 방식으로 넘어갔다.교착상태를 해결하는 방법은 2가지가 있는데, 가벼운 교착상태 검출, 무거운 교착상태 검출이 있다.교착상태 해결가벼운 교착상태 검출타이머를 이용하여 일정시간 프로세스가 작업을 진행하지 않을 경우 프로세스의 마지막 체크포인트로 롤백한다.무거운 교착상태 검출운영체제가 자원 할당 그래프를 이용하여 순환구조를 이루는 그래프를 확인하여 프로세스를 종료하고, 마지막 체크포인트로 롤백한다.운영체제가 자원 할당 그래프를 운영하고, 검사해야하기 때문에 오버헤드가 발생하는 단점이 있지만, 타이머로 인해 억울하게 종료되는 프로세스가 없다는 장점이 있다. 메모리 종류레지스터CPU가 처리하기 위해 메인메모리에 있는 값을 레지스터로 가져와 계산을 하고, 결과값을 메인메모리에 저장한다.CPU 구분시 32Bit, 64Bit는 레지스터의 크기를 뜻한다.레지스터는 CPU에 존재한다.전력이 끊기면 데이터가 사라지는 휘발성 메모리이다.캐시메인메모리의 있는 값을 레지스터로 가지고 올 때, 성능을 위해 미리 값을 가져온다.캐시는 CPU에 L1, L2, L3... 등으로 존재한다.전력이 끊기면 데이터가 사라지는 휘발성 메모리이다.메인메모리(RAM)운영체제나 프로세스가 올라가는 공간이다.전력이 끊기면 데이터가 사라지는 휘발성 메모리이다.보조저장장치(HDD, SDD)전력이 끊겨도 데이터가 유지되는 비휘발성 메모리이다.파일, 데이터를 저장하는 공간이다. 가격 : 레지스터 > 캐시 > 메인메모리 > 보조저장장치용량 : 레지스터 속도 : 레지스터 > 캐시 > 메인메모리 > 보조저장장치 메모리를 분리했기 때문에 속도가 빠르면서 저렴하게 컴퓨터를 사용할 수 있다. 메모리 주소운영체제는 메모리를 관리하기 위해 1Byte(8bit) 크기로 구역을 나누고 숫자를 매긴 것을 메모리 주소라고 한다.CPU의 레지스터의 크기가 클수록 사용가능한 메인메모리의 크기가 커지고, 처리가능한 양이 늘어 속도도 빠르다.64Bit : 2^64 의 메인메모리 사용 가능32Bit : 2^32 의 메인메모리 사용가능(4GB까지) 사용자의 프로세스가 운영체제가 실행되는 메모리 영역을 침범할 경우 악의적인 접근으로 문제가 발생할 소지가 있다.그래서 운영체제가 실행되는 메모리 공간과 사용자가 실행하는 프로세스 공간을 물리적으로 구분하기 위해 경계 레지스터가 생겼다.경계 레지스터는 CPU에 존재하고, 메모리 관리자가 사용자 프로세스가 침범했을 경우 해당 프로세스를 종료시킨다. 메모리 주소는 물리 주소, 논리 주소로 구분된다.물리 주소란 컴퓨터 관점에서의 실제 메모리 주소이고, 논리 주소는 사용자 관점에서의 메모리 주소이다. 사용자가 개발한 프로그램은 0x0번 주소로 시작한다는 전재로 개발을 하고, 사용자가 메모리 주소(논리 주소)로 접근할 때 CPU는 메모리 관리자에게 주소를 요청하고 메모리 관리자는 실제 메모리 주소(물리 주소)를 반환해준다.이를 통해 사용자는 저장될 메모리 주소를 고려하지 않고 편리하게 프로그램을 개발할 수 있다.메모리 할당하나의 프로세스가 메모리에 올라오는 유니 프로그래밍 환경에서 실제 메모리보다 더 큰 메모리를 요구하는 문제가 발생했다.프로세스에서 실행에 필수적인 일부만 메모리에 올리고 나머지는 보조저장장치의 스왑 공간에 저장한다. 이 기법을 오버레이라고 한다. 오늘날과 같이 멀티 프로그래밍 환경에서는 메모리 크기를 나누었는데, 2가지 방법으로 나누어서 이 문제를 해소했다.가변 분할 방식(세그멘테이션)프로세스가 요구하는 메모리 공간 만큼 메모리를 나누어서 메모리를 할당한다.프로세스가 순서대로 메모리에 할당되는데, 연속 메모리 할당이라고 한다.장점은 낭비되는 메모리 공간이 없다.(내부 단편화 없음)단점은 메모리 할당된 2개의 프로세스가 종료되고 2개의 프로세스의 요구하는 만큼 메모리 공간을 요구하는 프로세스가 발생할 경우, 실행중인 프로세스를 종료하고 메모리를 합쳐야하는 오버헤드가 발생한다.(외부 단편화) 고정 분할 방식(페이징)고정된 메모리 크기로 메모리를 분할 하여 프로세스에 할당한다.프로세스가 비연속적으로 메모리에 할당되는데, 비연속 메모로 할당이라고 한다.장점은 구현이 단순하고, 오버헤드가 적다.단점은 낭비되는 메모리 공간이 있다.(내부 단편화) 버디 시스템세그멘테이션과 페이징을 혼합하여 단점을 최소화했다. 2의 승수로 메모리를 분할해 메모리를 할당한다.예를 들어 메모리의 크기가 2048byte 이고 프로세스가 요구하는 메모리 공간이 500byte 인 경우 2의 승수로 요구되는 메모리 공간의 크기에 알맞는 크기로 메모리를 할당(512byte)한다.이경우 낭비되는 메모리 공간을 최소한으로 줄이고, 프로세스가 종료되어도 메모리가 근접하므로 메모리를 합칠 때 발생하는 오버헤드를 최소화 하여 내부 단편화와 외부 단편화를 최소화했다. 미션2FIFO 스케줄링의 장단점은 무엇인가요?가장 먼저 들어온 프로세스가 먼저 실행되고, 늦게 들어온 프로세스는 나중에 실행되기 때문에 단순하고 직관적인게 장점입니다.Burst Time이 긴 프로세스가 가장 먼저 들어왔고 Burst Time이 짧은 프로세스가 늦게 들어왔다면, 앞의 프로세스의 작업이 끝날 때 까지 뒤의 프로세스가 기다려야합니다. 또한, I/O 작업이 포함된 프로세스의 경우 CPU가 대기해야하는 시간이 있기 때문에 CPU 사용률이 떨어지는 단점이 있습니다.SJF를 사용하기 여러운 이유가 뭔가요?Burst Time이 가장 짧은 프로세스를 먼저 실행해야하는데 프로세스의 작업 시간을 예측하기가 어렵고, 만약 Burst Time이 긴 프로세스는 Burst Time이 짧은 프로세스로 인해 무한정 작업이 늦춰질 수도 있는 어려움이 있습니다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?여러개의 프로세스를 실행시키기 위해 컨텍스트 스위칭이 발생하는데, 만약 타임 슬라이스가 아주 작으면 프로세스 처리량보다 컨텍스트 스위칭 처리량이 더 커져셔 비효율적인 문제가 발생합니다. 4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?프로세스가 CPU 연산을 많이하면 CPU Bound Process이고, 프로세스가 I/O 작업을 많이하면 I/O Bound Process입니다.운영체제가 구분하는 방법은 단순하게 타임 슬라이스로 구분합니다.타임 슬라이스만큼 CPU를 할당했을 때 운영체제에 의해 CPU를 빼앗기게 되면 상대적으로 CPU 연산이 많으므로 CPU Bound Process타임 슬라이스보다 먼저 CPU를 반환하는 프로세스는 상대적으로 CPU 연산이 적으므로 I/O Bound Process 5. 공유자원이란무엇인가요?프로세스간 통신을 할 때 공유해서 사용하는 변수나 파일입니다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?4가지 조건이 모두 충족되어야 교착상태에 빠질 수 있습니다.상호배제 : 하나의 프로세스가 자원을 사용하고 있다면 다른 프로세스는 해당 자원을 사용할 수 없습니다.비선점 : 하나의 프로세스가 자원을 사용하고 있다면 다른 프로세스는 해당 자원을 빼앗을 수 없습니다.점유와 대기 : 프로세스가 자원을 사용하면서 다른 자원을 원해야합니다.원형 대기 : 점유와 대기하는 프로세스들이 서로 원형 관계를 이루어야 합니다.

인프런 워밍업 클럽 CS 2기 - 1주차 발자국

자료 구조 및 알고리즘 배열다른 프로그래밍 언어 vs 자바스크립트 특징다른 프로그래밍 언어의 경우는 배열의 크기를 정하고 연속적인 공간을 차지한다. 반면 자바스크립트 언어의 경우에는 배열의 크기를 정하지 않고 비연속적인 공간을 차지한다.다른 프로그래밍 언어의 배열은 배열의 크기를 늘릴경우 연속적인 공간을 새로 찾아서 기존의 내용을 복사붙여넣기 하기 때문에 성능이 좋지 않다. 반면 자바스크립트 언어의 경우에는 배열의 크기를 정하지 않기 때문에 비연속적인 공간에 값을 넣어 성능이 상대적으로 좋다.다른 프로그래밍 언어의 배열은 배열의 크기를 할당해야하기 때문에 불필요한 공간을 차지할 수 있다. 반면 자바스크립트 언어의 배열은 배열의 크기를 정하지 않고 동적으로 크기가 정해지기 때문에 불필요한 공간을 줄일 수 있다. 공통 특징배열의 시작주소 + 인덱스를 이용하여 참조를 하고, 참조의 경우 O(1) 의 성능을 보여준다. 🏷 자바스크립트 언어의 경우 비연속적인 공간을 차지하는데, 연결리스트로 노드가 연결되어 있어 인덱스로 접근할 수 있어 다른 프로그래밍언어에서 사용되는 배열과 유사하게 연속적인 공간을 차지하는 것 처럼 보여진다. 단방향 연결리스트특징연결리스트는 다른 노드를 가르키는 포인터가 있고, 하나의 노드가 다른 하나의 노드를 가르키며 서로 연결되어 있지 않아 단방향 연결리스트라고 불린다. 데이터 추가시, 인덱스의 위치에 따라 성능이 달라지는데 맨 앞에 데이터 추가시 O(1)의 성능을 가지는 반면, 맨 뒤에 데이터를 추가시 마지막 노드를 확인하고 추가해야하므로 O(n)의 성능을 가진다.데이터 삭제와 조회도 마찬가지이다. 연관된 자료구조스택 스택(Stack)특징First In Last Out (FILO) 방식이며, 가장 첫번째로 들어간 노드가 가장 마지막으로 나오는 순서를 따른다. 예시로 설거지를 한 접시를 탑을 쌓는다면 가장 위의 접시부터 빼는 것을 생각하면 이해가 쉽다. 구현단방향 연결리스트를 이용하여 위에서 부터 값을 넣는 push, 가장 위에서 제거하는 pop, 가장 위에 위치한 값을 확인하는 peek, 스택이 비어있는지 확인하는 isEmpty 메서드를 구현했다. 양방향 연결리스트특징양방향 연결리스트의 경우 하나의 노드가 다른 하나의 노드를 가리키고 있는데, 서로간에 참고하는 경우를 양방향에서 알 수 있다고 해서 양방향 연결리스트라고 한다. 연관된 자료구조큐, 덱, 셋 큐(Queue)특징First In First Out (FIFO) 방식이며, 가장 첫번째로 들어간 노드가 가장 첫번째로 나오는 순서를 따른다. 예시로 마트 계산대에서 가장 먼저 줄을 선 사람부터 계산을 진행하는 것을 생각하면 이해가 쉽다. 구현양방향 연결리스트를 이용하여 값을 넣는 enqueue, 값을 제거하는 dequeue, 가장 첫번째로 위치한 값을 확인하는 front, 큐가 비어있는지 확인하는 isEmpty 메서드를 구현했다. 데크(Deque)특징스택과 큐를 특징이 혼합된 자료구조로, 데이터를 첫번째와 마지막에 데이터를 추가, 삭제, 조회를 할 수 있다. 구현양방향 연결리스트를 이용하여 맨 앞의 값을 넣는 addFirst, 맨 앞의 값을 제거하는 removeFirst, 맨 뒤의 값을 넣는 addLast, 맨 뒤의 값을 제거하는 removeLast, 데크가 비어있는지 확인하는 isEmpty 메서드를 구현했다. 해시테이블특징해시 함수 + 테이블을 합친 개념으로 프로그래밍 언어마다 용어의 차이가 있다. 자바스크립트의 경우 해시 테이블이라고 한다.테이블을 배열로 만드는 방식의 경우 테이블의 키(숫자)를 인덱스로 하여 값을 저장했다. 이 방법은 사용되지 않는 인덱스의 경우 낭비되는 공간이기 때문에 메모리 낭비를 초래한다. 그래서 해시 함수를 사용하여 낭비되는 공간을 줄이는 방식이 해시 테이블이라고 한다.해시테이블의 경우 해시 함수에 따라 성능이 좋고 나쁨이 결정되기 때문에 좋은 해시 함수를 만드는 것이 가장 중요하다. 구현배열을 만들고, 양방향 연결리스트를 배열의 원소로 넣어 하나의 배열에 여러개의 양방향 연결리스트를 가진다. 연관된 자료구조셋 셋(Set)특징중복된 자료를 허용하지 않는다. 구현해시테이블을 이용하여 값을 넣는 add, 값을 제거하는 remove, 맨 뒤의 값을 넣는 addLast, 값을 초기화하는 clear, 저장된 값들을 출력하는 printAll, 셋이 비어있는지 확인하는 isEmpty 메서드를 구현했다. 미션1여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.배열 또는 해시테이블을 선택할 거 같습니다.만약 학생을 나누는 키 값이 연속적인 경우 배열을 선택해도 메모리 낭비 공간이 없겠지만, 만약 키값이 불연속적인 경우 배열로 저장할 경우 낭비되는 공간이 생길 수 있으므로, 해시 함수를 이용하여 낭비되는 메모리 공간을 줄이는 해시테이블을 사용합니다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.큐 자료구조를 선택할 거 같습니다.큐 자료구조의 특징이 첫번째 들어온 데이터가 가장 첫번째로 나가는 FiFO 방식이기 대문에 들어온 순서대로 처리하기에 적합한 자료구조입니다. 자료 구조 및 알고리즘 인터럽트입출력 장치의 데이터를 읽거나 쓰려고 할 때 기존의 폴링 방식의 단점을 해결하려고 나온 방식이다.기존의 폴링방식은 입출력 장치의 데이터를 지속적으로 확인해야하기 때문에 성능이 좋지 않았고, 인터럽트를 통해 입출력 장치가 CPU에게 신호를 주면 CPU는 그때 처리하는 방식이어서 성능상에 이점이 있다. 인터럽트입출력 장치의 데이터를 읽거나 쓰려고 할 때 기존의 폴링 방식의 단점을 해결하려고 나온 방식이다.기존의 폴링방식은 입출력 장치의 데이터를 지속적으로 확인해야하기 때문에 성능이 좋지 않았고, 인터럽트를 통해 입출력 장치가 CPU에게 신호를 주면 CPU는 그때 처리하는 방식이어서 성능상에 이점이 있다. 프로그램과 프로세스프로그램은 저장장치에 저장된 명령문의 집합체이다. 프로세스는 프로그램이 메모리에 적재되어 실행중인 상태, 즉 실행중인 프로그램을 뜻한다. 멀티프로그래밍과 멀티프로세싱유니프로그래밍은 메모리에 하나의 프로그램이 올라갔으며, 즉 하나의 프로세스가 있다.멀티프로그래밍은 메모리에 여러개의 프로그램이 올라갔으며, 즉 여러개의 프로세스가 있다.멀티프로세싱은 CPU가 여러개의 프로세스를 처리하는 것이다. PCB운영체제가 CPU가 프로세스를 효과적으로 관리하기 위해 PCB를 사용한다.PCB에는 프로세스에 대한 정보가 있어 시분할 시스템에서 CPU를 이용하여 여러개의 프로세스를 관리할 때 사용한다. 프로세스 상태시분할 시스템으로 여러 프로세스를 돌아가며 실행하여, 동시에 실행되는 것 처럼 보인다.생성 : PCB생성 후 메모리에 프로그램 적재 요청준비 : CPU에 의해 사용을 기다리고 있음, CPU 스케줄러에 의해 할당실행 : 준비 상태에 있는 프로세스가 CPU를 할당받아 실행되는 상태대기 : 프로세스가 입출력 요청을 하면 입출력이 완료까지 대기완료 : 프로세스 종료 및 PCB제거컨텍스트 스위칭프로세서를 실행 중에 다른 프로세스를 실행하기 위해 현재 프로세서의 상태 값을 저장하고, 다른 프로세스의 상태 값으로 교체하는 것을 뜻합니다.PCB의 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경된다.프로세스 생성과 종료초기 컴퓨터 부팅 후 부모 프로세스가 생성된다.이후 모든 다른 프로세스는 부모 프로세스를 복사하여 생성되며, 이는 프로세스를 새로 생성하는 것보다 성능에 이점이 있다.내부의 코드는 자식 프로세스가 exec() 함수가 실행되면 덮어쓰게된다. 쓰레드하나의 프로세스에 하나 이상의 쓰레드가 존재한다.프로세스가 많아질 수록 PCB, 코드, 데이터, 스택, 힙 영역을 만들어 줘야하기 때문에 메모리를 많이 차지하는 이슈가 있었다. 그리고 브라우저의 탭들은 프로세스마다 통신을 하기 위해 IPC를 이용해야하는데 IPC의 비용이 많은 이슈가 있었다.쓰레드는 이러한 문제를 해소하기 위해 Code, data, heap을 공유하며, stack은 쓰레드마다 하나씩 가지고, IPC 비용을 줄일 수 있었다.쓰레드를 이용하면 IPC 비용을 줄일 수 있고 메모리 공간을 절약할 수 있다. 그러나 하나의 프로세스에 문제가 생기면 프로세스에 있는 쓰레드가 모두 문제가 생기는 단점이 있다. CPU 스케줄링프로세스를 실행하기 위해 CPU 스케줄링은 고려해야할 사항이 2가지 있다.어떤 프로세스에게 CPU를 할당할 것인가.어떤 프로세스에게 얼만큼의 CPU 할당 시간을 줄것인가. 다중큐준비 상태에 있는 프로세스는 실행 상태로 변환된다.준비 상태에 있는 프로세스의 PCB는 준비 상태의 다중 큐에 존재하며 CPU 스케줄러에 의해 실행이 결정된다.대기 상태에 있는 I/O 작업의 프로세스의 PCB가 대기 상태의 다중큐에 존재하며, CPU스케줄러에 의해 실행이 결정된다.스케줄링 목표리소스 사용률오버헤드 최소화공평성처리량대기시간응답시간FIFO스케줄링 큐에 들어온 순서대로 할당하며, 먼저 들어온 프로세스가 종료되어야 다음 프로세스가 실행된다.만약 Burst Time이 오래 걸리는 프로세스의 위치에 따라 평균 대기시간이 크게 차이가 난다.현대에서는 사용되지 않으나, 일괄처리시스템에서 주로 사용된다. 미션2 while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?인터럽트 프로그램과 프로세스가 어떻게 다른가요? 프로그램은 저장장치에 저장된 명령문의 집합체입니다.프로세스는 메모리 상에 적재되어 실행중인 프로그램입니다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요? 멀티프로그래밍은 메모리 관점에서 메모리에 여러개의 프로세스가 존재하는 것을 뜻합니다.멀티프로세싱은 CPU 관점에서 여러개의 프로세스를 처리하는 것을 뜻합니다. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?운영체제는 PCB를 사용하여 프로세서를 관리합니다.예를 들어 시분할 시스템으로 여러개의 프로세스를 번갈아가며 프로세스를 실행해야할 때, CPU에서 특정 프로세스 실행 후 레지스터를 해당 프로세서의 PCB에 저장하고 다른 프로세스의 PCB의 레지스터 정보를 불러와서 실행하는 것을 반복하여 마치 여러개의 프로세스가 동시에 실행되는 것처럼 관리할 수 있습니다. 컨텍스트 스위칭이란 뭔가요?프로세서를 실행 중에 다른 프로세스를 실행하기 위해 현재 프로세서의 상태 값을 저장하고, 다른 프로세스의 상태 값으로 교체하는 것을 뜻합니다. PCB의 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경됩니다.