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

강의 내용 요약운영체제가상 메모리1. 가상 메모리가상 메모리는 물리적 메모리(RAM)의 크기가 부족한 경우에 대한 해결책가상 메모리의 크기는 물리 메모리의 크기와 CPU의 비트수에 따라 결정32bit CPU → 2^32(약 4GB)64bit CPU → 2^64 2. 가상 메모리를 이용한 여러 프로세스 실행물리 메모리 내용의 일부를 하드 디스크 내의 스왑 영역에 보관처리가 필요할 때 메인 메모리에 가져와서 실행 동적 주소 변환메모리 관리자는 물리 메모리(RAM)와 스왑 영역을 합쳐서 프로세스가 사용하는 가상주소를 물리주소로 변환이를 동적주소변환(Dynamic Address Translation)이라 부름동적 주소 변환을 거치면 사용자 데이터를 물리 메모리에 배치 가능메모리 관리자의 임무물리 메모리를 어떻게 나눌지프로세스를 메모리의 어디에 배치할지부족한 물리 메모리는 어떻게 처리할지가상 메모리 시스템에서 메모리를 관리하는 방식운영체제 영역을 제외한 나머지 영역을 일정한 크기로 나누어서 프로세스에게 할당메모리 분할 방식과 마찬가지로 가변 분할 방식(세그멘테이션)과 고정 분할 방식(페이징)을 사용각각 외부 단편화와 내부 단편화 문제가 있으므로 둘을 혼합한 방식인 세그멘테이션-페이징 혼용기법을 사용 가상주소와 물리주소의 매핑메모리 관리자는 가상주소와 물리주소를 일대일 매핑 테이블로 관리 3. 세그멘테이션 기법가변 분할 방식을 이용하는 기법프로그램(사용자) 관점의 메모리: 각 세그먼트는 인접할 필요가 없음프로세스 관점의 메모리: 각 세그먼트 영역이 서로 인접한 것처럼 바라봄 논리주소와 물리주소, 메모리 관리자논리주소 : 사용자, 프로세스, CPU 입장에서의 주소물리주소 : 실제 메모리 내의 주소논리주소와 물리주소의 변환은 메모리 관리자(MMU)가 처리 메모리 관리자는 세그멘테이션 테이블에 대한 정보를 가지고 있음세그멘테이션 테이블 자체는 메인 메모리에 저장세그멘테이션 테이블에는 Base Address와 Bound Address가 저장되고 이를 이용하여 물리 메모리 주소를 계산 세그멘테이션을 이용한 주소 변환 과정CPU에서 논리주소 전달 → 메모리 관리자는 해당 논리주소의 세그먼트 번호를 알아냄 → 메모리 관리자 내의 Segment Table Base Register(STBR)를 이용하여 물리 메모리 내에 있는 세그멘테이션 테이블을 찾음 → 세그먼트 번호를 인덱스로 Base Address와 Bound Address를 찾음 Bound Address는 세그먼트의 크기를 나타냄메모리 관리자는 CPU에서 받은 논리주소와 Bound Address를 비교하여 논리주소 를 구하고 논리주소 > Bound Adrress라면 메모리 침범으로 인식하여 해당 프로세스 종료 세그멘테이션의 장/단점장점메모리를 가변적으로 분할 가능코드, 데이터, 스택, 힙 영역을 모듈로 처리할 수 있어 공유 및 메모리 접근 보호가 편리단점가변 분할 방식의 단점인 “외부 단편화”가 발생 4. 페이징 기법고정 분할 방식을 이용하는 기법 논리주소공간사용자와 프로세스가 바라보는 주소공간페이지 → 논리주소공간을 일정한 크기로 나눈 것물리주소공간실제 메모리에서 사용되는 주소공간프레임 → 물리주소공간을 페이지의 크기와 동일하게 나눈 것 페이징을 이용한 주소변환 과정CPU에서 논리주소 전달 → 메모리 관리자는 이 논리주소의 페이지 번호, 오프셋을 알아냄 → 메모리 관리자 내의 Page Table Base Register(PTBR)를 이용하여 물리 메모리 내에 있는 페이지 테이블을 찾아냄 → 페이지 번호를 인덱스로 프레임 번호를 알아냄 → 오프셋을 이용해 물리주소로 변환(프레임이 invalid라면 스왑영역에 있음) 5. 세그멘테이션 vs 페이징세그멘테이션은 프로세스마다 크기가 달라 Bound Address를 가짐페이징은 모든 페이지의 크기가 동일하여 크기를 표현하는 Bound Address가 필요하지 않음세그멘테이션은 세그먼트마다 크기를 다르게 나눌 수 있기 때문에 논리적인 영역별로 세그먼트를 나눌 수 있는 반면, 페이징은 페이지의 크기가 고정되어 있어 논리적인 영역을 나눌 수 없음 페이지 테이블에서 가장 신경써야 하는 것은 페이지 테이블 크기프로세스가 많아질 수록 페이지 테이블의 개수도 많아짐메모리 관리자가 참조하는 페이지 테이블도 물리 메모리의 운영체제 영역에 저장되어 있음따라서 페이지 테이블의 크기가 너무 크면 사용자 영역이 부족해짐 6. 페이지드 세그멘테이션세그멘테이션과 페이징을 혼합하여 장점을 취한 방식 메모리 접근 권한메모리의 특정 번지에 부여된 권한읽기(Read),쓰기(Write),실행(Execute) 3가지 존재프로세스의 각 영역마다 접근 권한이 존재메모리 접근 권한에 대한 검사는 가상주소에서 물리주소로 변환될 때마다 발생 페이지드 세그멘테이션기존 세그먼테이션 테이블에서 변화한 점권한비트 추가Base address → 페이지 넘버Bound address → 페이지 개수페이지 넘버와 페이지 개수는 이름만 달라졌을 뿐 수행 역할은 거의 동일 페이지드 세그멘테이션 과정가상주소가 들어오면 가상주소를 이용해 세그먼트 번호를 알아냄 → 해당 세그먼트가 메모리 접근 권한을 위반하는 검사 (접근 권한 위반 시 프로세스를 종료시킴) → 페이지 넘버와 페이지 개수를 가져옴 (페이지 개수를 통해 메모리 침범 검사) → 페이지 넘버를 통해 페이지 테이블에 접근하여 프레임 번호를 가져옴 → 물리 메모리내의 해당 프레임에 접근하여 그 위치에서 페이지 개수를 더해 물리주소를 구함 (물리 메모리에 해당 프레임이 없다면 스왑 영역에서 물리 메모리로 가져옴) 페이지드 세그멘테이션의 단점물리 메모리 접근을 위해 메모리에 2번 접근해야 함세그멘테이션 테이블 참조 (1번) + 페이지 테이블 참조(1번) = 2번이러한 단점이 있어 현대 운영체제는 페이징과 페이지드 세그멘테이션 기법을 적절히 섞어서 사용함 7. 디멘드 페이징지역성 이론과 디멘드 페이징지역성 이론: 조만간 쓰일 데이터만 메모리에 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑 영역으로 보내 성능을 향상시킴공간의 지역성: 현재 위치와 가까운 데이터에 접근할 확률이 높음시간의 지역성: 최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높음 디멘드 페이징 ← 지역성 이론을 구현한 정책디멘드 페이징의 목적은 스왑 영역으로 데이터를 이동시키는 것을 최소화시키는 것스왑인 : 스왑영역에서 물리 메모리로 데이터를 가져오는 것스왑아웃: 물리 메모리에서 스왑영역으로 데이터를 보내는 것 페이지 테이블 엔트리페이지 테이블은 데이터가 물리 메모리, 스왑영역 중 어디에 위치해있는지 알아내기 위해 인덱스, 프레임 외에도 여러 비트가 존재페이지 테이블 엔트리(PTE) → 페이지 테이블을 이루는 하나의 행 접근 비트페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트메모리에 읽기나 실행 작업을 했다면 1로 바뀜 변경비트페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려주는 비트메모리에 쓰기 작업을 했다면 1로 바뀜 유효비트페이지가 물리 메모리에 있는지 알려주는 비트유효비트가 1 → 페이지가 스왑영역에 있음유효비트가 0 → 페이지가 물리메모리에 있음 읽기/쓰기/실행 비트권한비트해당 메모리에 접근권한이 있는지 검사하는 비트 디멘드 페이징 과정전체적인 과정프로세스가 가상 메모리에 접근요청→ 메모리 관리자는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아냄→ 만약, 물리 메모리에 없다면 Page Fault라는 인터럽트를 발생 시킴→ Page Fault가 발생 시 보조저장장치의 스왑영역에 접근, 해당 프로세스는 대기상태가 됨→ 스왑 영역의 데이터가 메모리로 올라감→ 메모리로 올라가면 대기상태의 프로세스가 다시 실행 8. 페이지 교체 정책Page Fault가 발생했을 때 메모리에 빈 공간이 없다면 메모리에 있는 페이지 중 어떤 페이지를 스왑영역으로 옮길 지 결정하는 방법 Random무작위로 선택해서 교체하는 방법지역성을 고려하지 않으므로 자주 사용되는 페이지가 선택될 수도 있어 성능이 좋지 않음 FIFO(First In First Out)가장 먼저 메모리에 들어온 페이지를 선택하는 방법자주 쓰이는 페이지가 먼저 들어왔다는 이유로 교체될 수도 있음구현이 간단하고 성능도 준수하기에 FIFO 정책을 변형하여 많이 사용 Optimum앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법사실상 구현이 불가능한 이론적 방법알고리즘 성능 비교 시 참조용으로 사용 LRU(Least Recently Used)최근 가장 사용이 적은 페이지를 선택하는 방법시간 지역성(최근 접근했던 데이터가 접근할 확률이 높음)에 근거한 방식Optimum 알고리즘에 근접한 성능을 보임프로그램이 지역성을 가지지 않을 때는 성능이 떨어짐페이지 테이블 엔트리에 시간 정보를 저장하기 위해서는 많은 비트가 필요실제 LRU를 구현할 때는 접근 비트를 이용하여 LRU에 근접하게 구현 빌레이디의 역설Page Fault를 줄이려고 프레임 수를 늘렸는데 오히려 Page Fault가 더 많이 발생하는 현상FIFO에서만 발생하고 LRU에서는 발생하지 않음 클락 알고리즘(Clock Algorithm)LRU와 유사하게 구현하는 방법클락 알고리즘은 접근비트 하나만 이용일정 시간 간격마다 모든 페이지의 접근비트를 0으로 초기화접근비트의 초기값은 0으로 설정되며 페이지 참조 시 1로 수정페이지를 원형으로 연결하고 스왑영역으로 옮길 페이지를 포인터로 가리키는데 이를 클락 핸드라고 부름클락 핸드는 시계 방향으로 돌며 Page Fault가 발생하여 스왑영역으로 보내야하는 상황이 나오면 클락 핸드는 현재 참조하고 있는 페이지의 접근비트를 봄접근비트가 1이면 0으로 바꾸고 다음 페이지를 가리킴접근비트가 0이면 해당 페이지를 스왑영역으로 보냄 향상된 클락 알고리즘(Enhanced Clock Algorithm)접근 비트와 변경 비트 모두 이용 스왑 영역으로 보내지는 순위접근 비트 0, 변경 비트 0 > 접근 비트 0, 변경 비트 1 > 접근 비트 1, 변경 비트 0 > 접근 비트 1, 변경 비트 1 2차 기회 페이지 교체 알고리즘FIFO 방식을 개선한 방식자주 사용되는 페이지에게 또 한번의 기회를 주는 방식Page Fault 없이 페이지 접근에 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시키는 방법FIFO 보다는 성능이 좋지만 LRU보다는 성능이 좋지 않음 스레싱(Thrashing)CPU 사용률을 올리기 위해 멀티프로그래밍의 정도를 올렸지만 CPU가 작업하는 시간보다 스왑작업의 시간이 더 길어져 CPU 사용률이 0%에 가까워 지는 것 스레싱의 해결책하드웨어적인 방법 → 물리 메모리의 크기를 늘리는 것소프트웨어적인 방법 → 워킹셋과 적절한 페이지 수 할당 적절한 페이지 수 할당프로세스가 실행되면 일정량의 페이지 할당Page Fault 발생 시 더 많은 페이지 할당해당 프로세스에서 Page Fault가 매우 적게 발생하면 메모리 낭비라 판단하여 페이지 회수이 절차를 반복하면 해당 프로세스에 맞는 적절한 페이지 수가 결정됨 워킹셋지역성 이론에 따라 현재 메모리에 올라온 페이지들을 하나의 셋트로 묶어서 실행하는 방법프로세스가 준비상태에서 실행상태가 되는 컨텍스트 스위칭을 할 때 사용됨 주변 장치1. 주변 장치 개요주변장치 내부 구조주변 장치들은 메인보드에 있는 버스로 연결됨하나의 버스는 Address 버스, Data 버스, Control 버스로 이루어져 있음 주변 장치들은 메인보드에 있는 버스로 연결됨하나의 버스는 Address 버스, Data 버스, Control 버스로 이루어져 있음 주변 장치의 구성 요소외부 인터페이스버스 인터페이스레지스터장치의 상태와 데이터를 보관입출력 작업 시 데이터를 저장하는 역할레지스터의 값들은 CPU가 사용하기 위해 메모리로 이동되기도 함컨트롤러로직주변 장치의 종류캐릭터 디바이스데이터 전송 단위가 캐릭터(글자)로 상대적으로 크기가 작음마우스, 키보드, 사운드카드, 직렬/병렬 포트 등이 포함블록 디바이스데이터 전송 단위가 블록(범위)로 상대적으로 크기가 큼SSD, HDD, 그래픽 카드 등이 포함 CPU와 주변 장치 간의 전체적 구조CPU는 I/O 명령을 만나면 입출력 제어기에게 입출력 작업을 맡기고 다른 작업을 수행입출력 제어기는 시스템 버스와 입출력 버스로 구분함시스템 버스 → 고속으로 작동하는 CPU와 메모리가 사용입출력 버스 → 주변장치가 사용느린 장치와 빠른 장치를 구분하여 속도 병목 현상을 해결하기 위해 고속 입출력 버스와 저속 입출력 버스로 나뉨그래픽 카드가 다루는 데이터는 매우 대용량이라 시스템 버스를 이용입출력 제어기가 메모리에 접근하기 위해서는 CPU가 필요한 문제가 있었음. 이를 해결하기 위해 DMA(Direct Memory Access) 제어기를 추가하였고 DMA 제어기를 통해 데이터를 직접 메모리에 저장 및 가져올 수 있음Memory Mapped I/O → CPU와 DMA가 사용하는 메모리가 겹치지 않도록 구분하게 하는 것 2. 마우스/키보드마우스DSP(Digital Signal Processor)가 마우스 움직임 혹은 클릭 같은 데이터 감지→ 디바이스 컨트롤러가 CPU에게 인터럽트를 보냄→ 마우스 드라이버가 동작하여 데이터를 읽어감→ 마우스 드라이버가 운영체제에게 이벤트 신호를 줌→ 운영체제는 이벤트를 Foreground 애플리케이션으로 전달→ 애플리케이션에서 받은 마우스 이벤트 처리 키보드키보드의 디바이스 컨트롤러가 어떤 키를 입력 받았는지 알아냄→ CPU에게 인터럽트→ 키보드 드라이버가 운영체제에게 이벤트를 보냄→ 운영체제는 Foreground 애플리케이션으로 이벤트 전달→ 애플리케이션에서 그에 맞는 키보드 이벤트 처리 3. 하드디스크와 플래쉬 메모리하드디스크스핀들: 하드디스크의 달린 막대플래터: 자기화된 원판으로 이루어짐디스크암: 읽기/쓰기 헤드로 플래터의 표면을 읽음플래터는 여러 개의 트랙으로 구성되어 있음플래터 표면에는 자성이 있기 때문에 N극을 띠면 0, S극을 띠면 1로 인식헤드는 디스크암에 고정되어 있으므로 모든 헤드는 항상 같이 움직임실린더: 여러 개의 플래터에 있는 같은 트랙의 집합섹터: 하드디스크의 가장 작은 단위, 여러 섹터가 모여 트랙을 이룸 하드 디스크에서 데이터를 읽어오는 예시실린더 C로 가서 트랙 B에 있는 섹터 D를 읽어라Seek: 헤드를 특정 실린더로 이동시키는 것Seek time: 헤드를 특정 실린더로 이동시키는 데 걸리는 시간 (ms 단위)실린더 C까지 이동했으면 트랙 B의 섹터 D가 헤드에 닿을 때까지 스핀들을 회전시킴헤드에 섹터 D가 읽히면 작업이 끝남 플래쉬 메모리장점크기가 HDD에 비해 작음Flash Memory는 전기적으로 읽기 때문에 굉장히 빠르고 조용자기성을 띄는 HDD에 비해 안전함충격에 강함단점데이터 덮어쓰기 불가능데이터를 지우기 가능한 횟수가 정해짐 파일시스템1. 파일시스템파일시스템 → 운영체제가 파일을 관리하기 위해 만든 관리자가상 메모리의 메모리 관리자와 하는 일이 비슷함파일시스템은 파일 테이블을 이용하여 파일을 관리 파일시스템의 기능파일과 디렉토리 생성파일과 디렉토리 수정/삭제파일 권한 관리무결성 보장백업과 복구암호화 저장장치의 전송단위는 블록이지만 사용자는 바이트 단위로 접근이 필요함. 이를 파일 관리자가 중간에서 관리해줌 파일의 구조파일은 헤더와 데이터로 구성헤더 → 파일의 속성(파일 이름, 식별자, 유형 등)들이 담겨져있음 파일 디스크립터File Descriptor (File Control Block)파일을 관리하기 위해 정보를 보관하는 곳파일 디스크립터는 파일마다 독립적으로 존재저장장치에 존재하다가 파일이 오픈되면 메모리로 이동파일시스템(운영체제)이 관리, 사용자가 직접 참조 불가능 파일의 종류순차파일구조파일의 내용이 연속적으로 이어진 형태모든 데이터가 순서대로 기록되기 때문에 공간의 낭비가 없고 구조가 단순특정 지점으로 바로 이동이 어려움(삽입/삭제 시 탐색 시간이 걸림) 직접파일구조저장하려는 데이터의 저장 위치를 해시 함수를 통해 결정하는 파일구조자료구조의 Hash Table 구조와 같음해시 함수를 이용하기 때문에 데이터 접근이 굉장히 빠름해시 함수의 선정이 굉장히 중요저장공간이 낭비될 수 있음 인덱스 파일구조순차접근과 직접접근 방식의 장점을 취한 방식으로 2가지 방식 모두 가능기본적인 접근은 순차적으로 접근특정 위치를 선택하면 인덱스 테이블의 인덱스에 접근해 블록 번호를 알아내고 순차 데이터의 해당 블록 번호로 이동하여 접근 가능 2. 디렉토리관련 있는 파일들을 하나로 모아둘 수 있는 구조디렉토리는 1개 이상의 파일을 가질 수 있고 자식 디렉토리도 가질 수 있음루트 디렉토리 → 가장 최상위에 있는 디렉토리 디렉토리와 파일은 다른 구조가 아님일반 파일에는 데이터가 저장되어 있음디렉토리에는 해당 디렉토리 내의 파일 정보가 저장되어 있음 디렉토리 구조초기 파일 시스템의 경우 루트 디렉토리에서만 하위 디렉토리를 생성할 수 있었고 그 외의 디렉토리에서는 생성할 수 없는 단순한 구조였음파일이 많아지며 관리의 불편함이 생겨 다단계 디렉토리 구조가 등장다단계 디렉토리어떠한 디렉토리에서도 하위 디렉토리를 만들 수 있는 트리구조현대의 운영체제는 트리구조에서 순환이 생김ex)윈도우/맥 의 바로가기 아이콘 3. 파일과 디스크파일 시스템은 메모리와 비슷함페이징과 같이 전체 디스크 공간을 일정한 크기로 나누고 그 공간에 주소를 할당하여 관리일정한 크기로 나눈 공간을 파일시스템에서는 블록이라 부름한 블록의 크기는 1~8KB정도 파일시스템은 파일정보를 파일테이블로 관리파일테이블에는 파일이 시작하는 블록의 위치정보가 담겨있음 하나의 파일은 여러 개의 블록으로 구성되어 있으며 연결하는 방식에 따라 연속할당, 불연속할당으로 나눌 수 있음 연속 할당파일을 구성하는 블록들을 디스크에 연속적으로 저장하는 방식파일의 시작 블록만 알면 파일 전체를 찾을 수 있음외부 단편화가 발생하기 때문에 실제로는 사용되지 않음 불연속 할당디스크의 비어있는 공간에 데이터를 분산해 저장하는 방식분산된 블록은 파일 시스템이 관리불연속 할당의 방식은 연결 할당, 인덱스 할당이 존재 연결 할당파일에 속한 데이터를 연결리스트로 관리파일테이블에는 시작 블록에 대한 정보만 저장하고 나머지는 연결리스트를 이용해 다른 블록에 접근하는 방식 인덱스 할당테이블의 블록 포인터가 데이터 블록에 직접 연결하는 것이 아닌 데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결인덱스 블록에 있는 참조하면 모든 데이터를 찾을 수 있음데이터가 많아 테이블이 꽉 찬 경우, 인덱스 블록을 더 만들어 연결하는 방식이기 때문에 테이블 공간을 확보할 수 있음 파일의 크기가 작음 → 블록 포인터를 이용파일의 크기가 큼 → 간접 포인터를 이용이 방식은 리눅스 및 유닉스에서 i-node라는 이름으로 사용되고 있음 파일 시스템에서 빈 공간을 관리하는 전략디스크에 파일을 저장할 때마다 빈 공간을 찾기 위해 모든 공간을 뒤지는 방식은 매우 비효율적파일시스템은 효율적인 관리를 위해 빈 공간을 모아둔 free block list를 가지고 있음특정 파일 삭제 시, 파일시스템은 모든 정보를 지우는 것이 아니라 파일의 헤더만을 삭제하고 free block list에 추가사용자는 파일이 삭제된 것처럼 느끼지만, 사용했던 블록의 데이터는 그대로 남아있기 때문에 포렌식을 통해 데이터 복구가 가능 자료구조1. 삽입 정렬(Insertion Sort)배열을 정렬된 영역과 정렬되지 않은 영역으로 나누고, 정렬되지 않은 값을 하나씩 정렬된 영역에 삽입하는 방식정렬 과정 예시: [4, 1, 5, 3, 6, 2]정렬된 영역: [4], 삽입할 값: 1 → [1, 4, 5, 3, 6, 2]다음 값 5는 4보다 크므로 그대로3은 5보다 작아, 5와 4를 오른쪽으로 밀고 → [1, 3, 4, 5, 6, 2]반복하여 최종 정렬 결과: [1, 2, 3, 4, 5, 6] 삽입 정렬의 성능시간 복잡도 : O(n^2) 장/단점장점: 구현이 간단, 데이터가 거의 정렬된 경우 최적의 성능을 보임단점: 역순 배열이면 최악의 성능을 보임, 큰 배열에서는 성능이 떨어짐 2. 병합 정렬(Merge Sort)재귀적으로 정렬하는 알고리즘분할 정복 알고리즘에 속함배열들의 데이터를 최소한을 쪼갠 후 각 단계 별로 병합을 하면서 정렬을 진행하는 방식 데이터를 반으로 나누어 분할.각각을 정렬한 후 병합하며 정렬.두 개의 데이터가 하나로 합쳐질 때 비교 연산이 두 번 발생.네 개의 데이터가 두 개로 병합될 때 비교 연산이 네 번 발생.단계마다 영역의 수가 반으로 줄어들기 때문에 O(log n)의 성능을 가짐.병합할 때 n개의 데이터를 비교하므로 전체 시간 복잡도는 O(n log n). 병합 정렬의 성능시간 복잡도 : O(n log n) 장/단점장점: 성능이 좋음단점: 이해와 구현이 어려움. 메모리 공간이 추가적으로 필요 3. 퀵 정렬(Quick Sort)분할 정복(Divide and Conquer) 알고리즘정렬 전에 배열에서 하나의 원소를 피벗(Pivot)으로 선택.피벗을 기준으로 작은 값과 큰 값으로 나누어 재귀적으로 정렬 수행. 퀵 정렬의 성능평균 : O(n log n)최악: O(n^2) -> 피벗이 한 쪽으로 지나치게 치우친 경우퀵 정렬은 최악의 피벗을 선택할 확률이 매우 낮아 병합 정렬에 비해 안정적인 성능을 보장병합 정렬에 비해 더 적은 비교와 더 적은 메모리 공간을 사용하기에 효율적 4. 동적 프로그래밍 - 메모이제이션(Memoization)재귀 사용 시 콜 스택 영역 차지 이외에도 같은 계산을 반복해서 수행하는 단점 존재이에 대한 해결책으로 동적 프로그래밍의 메모이제이션(Memoization)을 사용메모이제이션이미 계산된 값을 메모(캐싱)하여 재사용하는 방법.주로 재귀 함수에서 중복되는 연산을 방지하기 위해 많이 사용재귀를 이용하는 하향식(Top-down) 방식 메모이제이션을 통한 피보나치 수열 최적화시간 복잡도: 중복 계산을 방지하여 O(n^2) -> O(n)으로 줄일 수 있음장점재귀 함수 이용 시 성능 향상중복 계산 방지단점메모리 사용량 증가(계산한 값을 메모(캐싱)해야 하기 때문) 5. 동적 프로그래밍 - 타뷸레이션(Tabulation)하위 문제부터 해결하는 상향식 접근 방법. 반복문을 사용메모이제이션과 원리는 같음 (중복될 것 같은 값을 저장했다가 필요하면 계산이 아니라 값을 가져다 쓰기)장점재귀 호출을 이용하지 않아 과도한 콜 스택 호출로 인한 메모리 걱정이 없음단점가장 최하단의 하위 문제들에 대한 계산이 필요. 불필요한 계산이 발생할 수도 있음 메모이제이션과 타뷸레이션 중 어떤 것을 사용해야 할까?문제에 따라 다르지만눈에 보이는 재귀 or 분할 정복으로 풀기 쉬움 -> 메모이제이션(Memoization)복잡한 재귀 or 메모리 사용량이 중요함 -> 타뷸레이션(Tabulation) 일주일 간의 회고🍷칭찬하고 싶은 점강의를 1회독 완주한 점멘토님과 적극적으로 소통하려고 노력한 점😅아쉬웠던 점전공 시간에 이미 한 번 배웠던 것들인데 아직 완전한 내 것이 아닌 점이 아쉽네요... 좀 더 분발!🛠보완하고 싶은 점워밍업 클럽이 끝나고 운영체제, 자료구조와 알고리즘 강의를 개인 노션에 정리한 내용을 보면서 다시 정주행 돌릴 예정인데 그 때는 정리에 급급하기 보다는 차분하게 시간을 들여 내 것으로 만들도록 노력해야겠습니다.강의 재생 도중에 궁금한 점이 있으면 당장 찾아보는 것이 아니라 일단 다 듣고 찾아보기공부 흐름 끊어먹지 않고 온전히 집중하기

인프런 워밍업 클럽 CS 3기 3주차 미션 (자료구조와 알고리즘)

자료구조 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬- 특징: 인접한 두 요소를 비교해서 큰 값을 뒤로 보내는 방식 - 시간복잡도: 최선: O(n) / 평균,최악: O(n²) - 장점: 구현이 아주 간단하고 직관적임 - 단점: 성능이 너무 안 좋음, 실전에서 거의 사용 하지 않음선택 정렬- 특징: 가장 작은 값을 찾아서 앞으로 하나씩 정렬해가는 방식 - 시간복잡도: 최선,평균,최악: O(n²)- 장점: 구현 쉬움, 자리 바꿈(Swap) 횟수가 적음-단점: 효율성 낮음, 데이터 크기 커지면 성능이 떨어짐삽입 정렬- 특징: 정렬된 부분에 새 값을 '삽입'하는 방식- 시간복잡도: 최선: O(n) / 평균,최악: O(n²)- 장점: 거의 정렬된 상태일 땐 빠름, 구현 쉽고 안정 정렬- 단점: 역순으로 정렬되어 있을 경우 성능이 크게 하락병합 정렬- 특징: 분할 → 정렬 → 병합하는 재귀 방식 (Divide & Conquer)- 시간복잡도: 항상 O(nlogn)- 장점: 성능이 좋음. 큰 데이터에도 효율적, 정렬 정확도 높음- 단점: 이해와 구현이 어려움. 메모리 공간을 많이 차지퀵 정렬- 특징: 분할 → 정렬 → 병합하는 재귀 방식 (Divide & Conquer)- 시간복잡도: 항상 O(nlogn)- 장점: 성능이 좋음. 큰 데이터에도 효율적, 정렬 정확도 높음- 단점: 이해와 구현이 어려움. 메모리 공간을 많이 차지 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요. 지금 당장으로서는 타뷸레이션을 사용할 것 같습니다. 일단 재귀의 경우, 하위 단계의 결과값을 상위 단계에서 사용할 수 있을 지를 판단해야 하는데 일단 여기서부터 재귀로 풀어야겠다는 생각을 도출하기까지 쉽지 않으며 메모리가 부족한 환경에서 콜 스택이 쌓이는 건 굉장히 치명적입니다. 재귀로 해결해야 한다면 최대 재귀 깊이를 설정하여 콜 스택이 무한정 쌓이지 않도록 방지하는 방법을 사용할 수 있을 것 같습니다.

인프런 워밍업 클럽 CS 3기 3주차 미션 (운영체제)

운영체제메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터 - 가장 빠른 기억장소로 CPU내에 존재하며 전원이 공급되지 않으면 데이터가 사라지는 휘발성 메모리 - 레지스터의 크기에 따라 32bit CPU, 64bit CPU로 나뉨캐시 -레지스터와 메모리의 중간 다리 역할을 하는 메모리- 레지스터가 필요로 할 것 같은 데이터를 메인메모리에서 미리 가져와서 저장해두는 장소 - 휘발성 메모리 - 성능 상의 이유로 L1, L2, L3등 여러 개가 존재메인 메모리 - 실제 운영체제와 다른 프로세스들이 올라가는 공간 - 전원이 공급되지 않으면 데이터가 사라지는 휘발성 메모리 - 보조저장장치보다 가격이 비싸고 휘발성이기 때문에 실행 중인 프로그램만 올림보조기억장치 - 가격이 저렴하고 전원이 공급되지 않아도 데이터가 지워지지 않는 비휘발성 메모리사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요? 경계 레지스터메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 검사하고 만약 벗어났다면 그 프로세스를 종료시킵니다. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요? 가변 분할 방식은 프로세스의 크기에 딱 맞게 메모리가 할당되기 때문에 내부단편화 문제가 발생하지 않으나 메모리에 충분한 공간이 있음에도 연속된 빈 공간이 부족하여 메모리를 할당할 수 없는 외부단편화 문제가 발생할 수 있습니다.고정 분할 방식은 메모리를 같은 크기로 나누기 때문에 구현이 간단하고 오버헤드가 작으나 고정 크기가 프로세스가 필요한 크기보다 클 때 내부의 빈 공간이 사용되지 않고 낭비되는 문제인 내부단편화가 발생합니다.CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?CPU 사용률을 올리기 위해 멀티프로그래밍의 정도를 올렸지만 메모리 부족으로 인해 잦은 스왑이 일어나 CPU 사용률은 계속 떨어지게 되는 현상을 스레싱(Thrashing)이라고 합니다.HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?메인 메모리의 경우 휘발성 메모리로 전원이 끊기면 모든 데이터가 삭제됩니다. 따라서 전원이 끊겨도 운영체제나 다른 프로그램들을 안전하게 보관할 필요가 있으므로 보조기억장치는 반드시 필요합니다.파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일시스템은 빈 공간을 효율적으로 관리하기 위해 빈 공간을 모아둔 free block list를 가지고 있습니다. 파일을 삭제하면 데이터까지 삭제되는 것이 아니라 파일의 헤더만을 지우고 free block list에 추가하기 때문에 포렌식을 통해 파일의 데이터를 복구할 수 있습니다.

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

강의 내용 요약운영체제프로세스간 통신프로세스는 독립적으로 실행되는 경우도 있지만 다른 프로세스와 데이터를 주고 받으며 통신을 하는 경우도 있음프로세스는 한 컴퓨터 내에서 실행 중인 다른 프로세스와 통신하거나 네트워크로 연결된 다른 컴퓨터에 있는 프로세스와 통신할 수도 있음. 프로세스 간 통신의 종류한 컴퓨터 내에서 프로세스 간 통신 파일 : 파일을 이용해 데이터를 주고 받으며 통신파이프 : 운영체제가 제공한 파이프를 통해 데이터를 주고 받으며 통신 2. 하나의 프로세스 내에서 쓰레드를 이용한 통신쓰레드는 코드, 데이터, 힙영역을 공유하고 스택만 각자의 것을 가지고 있음데이터 영역의 전역 변수 or 힙을 이용하면 쓰레드 간 통신이 가능3. 원격의 컴퓨터의 프로세스 간 통신(네트워크 이용)운영체제가 제공하는 소켓통신4. 다른 컴퓨터에 있는 함수를 호출하는 RPC(Remote Procedure call : 원격 프로시저 호출) 공유자원과 임계구역1. 공유자원과 동기화 문제프로세스/쓰레드 간 통신을 할 때 여러 프로세스/쓰레드가 공동으로 이용하는 자원(메모리, 변수, 파일, 데이터 등…)을 공유자원이라함공유자원은 여러 프로세스/쓰레드가 공유하고 있기 때문에 프로세스/쓰레드가 공유자원에 접근하는 순서에 따라 실행 결과가 달라질 수 있음시분할처리, 멀티스레드 환경 등의 이유로 인해 프로세스/쓰레드의 실행 순서를 파악하기 어려움참고 사항운영체제는 프로세스의 실행 순서를 관리 및 결정하지만, 실행 결과에는 관여하지 않는다. → 실행만 하고 결과는 알 바가 아니다따라서 공유 자원에 대한 접근 순서가 올바르게 조정되지 않으면 예상치 못한 결과가 발생함이 문제를 동기화 문제 라 부름동기화 문제는 공유 자원에 대한 접근 순서가 잘못된 경우, 공유 자원에 동시 접근 등 공유 자원 사용과 관련된 모든 문제를 아우르는 개념 2. 동기화 문제의 예시// 물약을 먹는 코드 int currentHealth = getHealth(); health = currentHealth + 50; // 체력 50 회복 // 공격받는 코드 int currentHealth = getHealth(); health = currentHealth - 10; // 체력 10 감소 공격받는 코드가 먼저 실행된다고 가정공격받는 코드의 int currentHealth = getHealth(); 가 실행되어 currentHealth에 20이 저장컨텍스트 스위칭이 발생 → 물약먹는 코드가 실행int currentHealth = getHealth();가 실행되어 currentHealth에 20이 저장되고 health = currentHealth + 50; 가 실행되어 health를 70으로 변경다시 컨텍스트 스위칭이 발생 → 공격받는 코드가 실행health = currentHealth - 10; 가 실행되어 health를 10으로 변경물약먹는 코드가 먼저 실행된다고 가정물약먹는 코드의 int currentHealth = getHealth();가 실행되어 currentHealth에 20이 저장컨텍스트 스위칭이 발생 → 공격받는 코드가 실행int currentHealth = getHealth();가 실행되어 currentHealth에 20이 저장되고 health = currentHealth - 10;가 실행되어 health를 10으로 변경다시 컨텍스트 스위칭이 발생 → 물약먹는 코드가 실행health = currentHealth +50가 실행되어 health를 70으로 변경예상 결과값으로는 health가 60이지만 health라는 공유자원에 여러 프로세스가 잘못된 순서로 접근하여 엉뚱한 값이 되어버림 3. 임계구역(Critical Section)과 경쟁 조건(Race Conditon)여러 프로세스/쓰레드가 동시에 사용하면 안되는 영역을 임계 구역이라 함공유자원을 수정하는 코드 부분이며 한 번에 하나의 프로세스/쓰레드만 접근해야 하는 영역여러 프로세스/스레드가 동일한 공유 자원을 동시에 접근해 문제가 발생할 수 있는 상황을 경쟁 조건(Race Condition)이라고 부름경쟁 조건은 동기화 문제의 한 가지 경우에 해당 4. 상호 배제(Mutual Exclusion) 매커니즘임계 구역 문제를 해결하기 위한 원칙상호 배제의 요구사항임계구역에는 동시에 하나의 프로세스만 접근해야 한다여러 개의 요청에도 하나의 프로세스의 접근만 허용한다임계구역에 들어간 프로세스는 최대한 빠르게 나와야한다 세마포어(Semaphore)1. 세마포어의 개념직원 A와 직원 B가 프린터 이용을 하고 싶음프린터 이용 시 작업물이 섞이는 것을 방지하기 위해 프린터실을 따로 만들고 프린트 작업을 원할 때마다 프린터실 열쇠 관리자에게 단 하나의 열쇠를 받아서 프린터실을 이용해야 함한 직원이 프린터실에 들어가있는 동안에는 다른 직원은 절대 프린터실에 출입할 수 없으며 들어간 직원이 나올 때까지 대기해야 함직원 A가 프린터 작업을 마치고 프린터실에서 나와서 열쇠를 열쇠 관리자에게 반납함 프린터를 사용하려는 직원 : 프로세스프린터: 여러 프로세스/쓰레드가 같이 쓰고 있는 공유자원프린터를 쓰기 위해 대기하는 공간: 대기큐프린터실 열쇠 관리자: 운영체제열쇠: 세마포어 2. 세마포어를 코드에 적용하기// 세마포어 선언 int semaphore = 1; // 물약을 먹는 코드 wait(semaphore); //열쇠를 요청해서 열쇠를 받고 문을 잠금 int currentHealth = getHealth(); health = currentHealth + 50; // 체력 50 증가 signal(semaphore); // 방에서 나와 열쇠 관리자에게 열쇠 반납 // 공격받는 코드 wait(sempahore); //열쇠를 요청해서 열쇠를 받고 문을 잠금 int currentHealth = getHealth(); health = currentHealth - 10; // 체력 10 감소 signal(semaphore); // 방에서 나와 열쇠 관리자에게 열쇠 반납 물약을 먹는 코드가 먼저 실행세마포어 변수 semaphore를 가지고 wait() 함수 호출 → **wait()함수**는 세마포어(열쇠)를 획득할 때까지 기다렸다가 획득하면 방에 들어가 문을 잠구는 함수현재 세마포어(열쇠)가 있으니 받아서 문을 잠굼공격받는 코드로 컨텍스트 스위칭이 발생공격받는 코드에서 wait()함수를 호출했지만 세마포어(열쇠)가 없으므로 세마포어(열쇠)를 받을 때까지 대기 → 다음 코드가 실행되지 않고 멈춰있음시간이 지나 다시 물약을 먹는 코드로 컨텍스트 스위칭이 발생signal() 함수가 호출될 때까지 물약을 먹는 코드가 실행물약을 먹는 코드가 signal() 함수를 호출하여 세마포어(열쇠)를 반납하였고 그제서야 공격받는 코드의 wait()함수가 종료됨시간이 지나 다시 공격받는 코드로 컨텍스트 스위칭이 발생하면 health 값을 변경하고 signal() 함수로 세마포어(열쇠)를 반납함초기 health값을 20이라고 하면 health는 20 → 70 → 60으로 변화위 설명을 통해 세마포어를 이용하면 여러 프로세스/쓰레드가 공유자원에 동시에 접근하지 못하기 때문에 동기화 문제가 발생하지 않음세마포어는 여러 개의 값을 가질 수 있음공유자원의 개수에 따라 세마포어의 값을 다르게 조정 가능ex) 공유자원이 3개 → 세마포어의 값은 3 3. 세마포어의 단점wait(s); // 임계 구역 wait(s); wait(s); // 임계 구역 signal(s); signal(s); // 임계 구역 wait(s); 위 그림과 같이 wait()과 signal()의 순서를 이상하게 호출하여 세마포어를 잘못 사용할 가능성이 있음.반납을 안해서 다른 프로세스가 임계 구역에 접근이 불가능하다 등..위 문제는 모니터라는 기법을 통해 해결 가능 4. 모니터세마포어의 단점을 해결한 상호배제 메커니즘운영체제가 아닌 프로그래밍 언어 차원에서 지원하는 방법ex) 자바의 synchronizedpublic class Health{ private int health = 100; synchronized void increase(int amount){ health += amount } synchronized void decrease(int amount){ health -= amount } } // synchornized 키워드가 붙은 함수들은 동시에 여러 프로세스/쓰레드에서 실행 불가능 // ex)(동일한 객체에 속한) increase 함수가 프로세스/쓰레드 A에서 실행 중이면 // 프로세스/쓰레드 B에서는 increase, decrease 모두 실행 불가능 데드락(Deadlock)1. 교착상태(데드락)이란?여러 프로세스/쓰레드가 서로 다른 프로세스/쓰레드의 작업이 끝나기를 기다리다가 아무도 작업을 진행하지 못하는 상태일상생활 속 교착 상태 → 교차로에서의 교통 마비 상태교착 상태의 발생 이유는 공유자원 때문임어떤 자원을 여러 프로세스/쓰레드가 공유하지 않는다면 교착상태는 발생하지 않음 2. 식사하는 철학자원형으로 된 탁자에 음식이 준비되어 있고 철학자들은 각자 의자에 앉아서 음식을 먹는 상황각 철학자는 포크를 1개씩 가지고 있으며 음식을 먹기 위해서는 포크를 2개 사용해야 함철학자 3명이 동시에 자신의 오른쪽에 있는 포크를 집음모든 철학자가 포크가 1개 더 필요한 상황이지만 아무도 양보를 하지 않음아무도 식사가 불가능한 교착상태에 빠짐 3. 교착상태의 필요조건아래의 4가지 필요조건 중 하나라도 충족되지 않는다면 교착상태는 발생하지 않는다.상호 배제어떤 프로세스/쓰레드가 한 리소스를 점유했다면 그 리소스를 사용하는 동안 다른 프로세스에게 공유되면 안됨 식사하는 철학자에서 포크가 리소스에 해당먼저 포크를 집었다면 그 포크는 다른 사람이 사용할 수 없는 리소스 비선점프로세스/쓰레드 A가 리소스를 점유하고 있는데 프로세스/쓰레드 B가 그 리소스를 빼앗을 수 없어야 함식사하는 철학자에서 철학자 A가 들고 있는 포크를 철학자 B가 뺏을 수 없는 상황 점유와 대기어떤 프로세스/쓰레드가 리소스를 가지고 있는 상태에서 추가적인 리소스를 원하지만 추가 리소스를 사용할 수 없어 대기하는 상태식사하는 철학자에서 오른쪽 포크를 손에 쥔 채로 왼쪽 포크를 기다리는 상태 원형 대기점유와 대기를 하는 프로세스/쓰레들의 관계가 원형(순환 구조)을 이루며, 각 프로세스가 다음 프로세스가 보유한 리소스를 기다리는 상황. 식사하는 철학자에서 서로가 서로의 포크를 원하는 상황이 원형(순환구조)을 이룸 4. 교착상태의 예방(Prevention)아예 교착상태 자체가 일어나지 않도록 방지하는 방법운영체제 연구자들은 앞의 4가지 필요조건을 통해 교착상태를 예방하려고 했으나 제약이 많고 비효율적이기 때문에 예방이 아닌 교착상태를 해결하는 방법을 연구하기 시작함 5. 교착상태 회피(Avoidance)운영체제가 프로세스들에게 자원을 할당할 때 어느 정도의 자원을 할당해야 교착상태가 발생하는지 파악하여 교착상태가 발생하지 않는 수준의 자원을 할당하는 방식교착상태가 발생할 수 있지만 최대한 발생하지 않도록 미리 대비하는 방법교착상태 회피는 전체 자원의 수와 할당된 자원의 수를 기준으로 안정상태와 불안정 상태로 나눔운영체제는 최대한 안정 상태를 유지하는 방향으로 자원을 할당함불안정 상태에 있더라도 무조건 교착상태에 빠지는 것이 아니라 교착상태에 빠질 확률이 높아지는 것은행원 알고리즘(Banker’s Algorithm)은행(운영체제)이 사업가들(프로세스/쓰레드)에게 돈(리소스)을 빌려줄 때 은행의 여윳돈(시스템의 총 자원)과 사업가들에게 빌려준 돈들(현재 할당된 자원)을 보고 대출 가능한 상황(안전상태)인지 확인하고 빌려주는 원리의 알고리즘 안정 상태안정상태의 경우 P2 혹은 P3이 추가 자원을 요청할 경우 사용 가능한 자원 2개를 사용하여 할당해줄 수 있음.추가 자원이 할당된 P2 혹은 P3의 작업이 끝나면 자원을 반납받아 P1의 추가 자원 요청에도 대응할 수 있음 불안정 상태현재 운영체제가 사용 가능한 자원이 1개임이 자원으로는 P1, P2, P3가 요청할 수 있는 최대 요청인 2개를 충족하지 못함불안정 상태에 있더라도 프로세스가 추가로 최대 자원을 요청하지 않는다면 교착상태에 빠지지 않을 수도 있지만 안정 상태에 비해 확률이 높음은행원 알고리즘은 교착상태를 회피하는 좋은 방법이지만 비용이 비싸고 비효율적5. 교착상태 검출가벼운 교착 상태 검출타이머를 이용하는 방식 → 프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주하고 교착상태를 해결(프로세스 종료)일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장된 체크포인트로 롤백무거운 교착 상태 검출자원할당 그래프를 이용하는 방식 → 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생했다면 해결(프로세스 종료) 프로세스는 각자 자원을 차지하고 있고 화살표를 통해 추가로 다른 자원을 요청하고 있음왼쪽 그래프 : 순환 구조가 생기지 않음 → 교착상태가 없는 그래프오른쪽 그래프: 순환 구조가 발생 → 교착상태가 있는 그래프그래프를 통해 교착 상태를 검출했다면 교착상태를 일으킨 프로세스를 강제종료시키고 다시 실행될 때 체크포인트로 롤백시킴이 방식은 운영체제가 지속적으로 자원 할당 그래프를 유지하고 검사해야 하므로 큰 오버헤드가 발생하지만 가벼운 교착 상태보다 정확한 교착상태 검출 가능(타이머에 의한 강제 종료가 아니라 그래프를 근거로 판단하기 때문) 컴파일과 프로세스1. 프로그래밍 언어의 종류컴파일 언어작성한 코드를 컴파일이라는 과정을 거쳐 0과 1로 이루어진 기계어로 실행파일을 만드는 언어컴파일 과정에서 문법 오류를 검사하고 CPU에서 바로 처리 가능한 기계어로 실행파일을 만들어두기 때문에 속도가 빠름번역가가 원고를 읽고 통째로 번역한 다음 전달해주는 느낌C, C++, C# 등의 언어가 이에 해당인터프리터 언어작성한 코드를 미리 기계어로 만들지 않고 실행 시 코드를 1줄씩 해석해 실행하는 언어컴파일 과정이 없기 때문에 오류가 발생할 수 있고 컴파일 언어에 비해 속도도 느림동시통역사가 중간에서 즉석으로 통역해주는 느낌Javascript, Python, Ruby등의 언어가 이에 해당 2. 컴파일 과정가장 먼저 전처리기에서 전처리 과정이 진행됨전처리 구문이 처리됨전처리 구문: #으로 시작하는 구문#include, #define …코드에 있는 모든 주석은 제거됨printf()함수의 원형을 가져옴매크로 값인 MY_NUMBER가 100으로 치환 됨 컴파일러는 C언어 작성된 파일(.i)을 기계어에 가까운 어셈블리어로 변환시킴 어셈블리어로 변환된 파일은 어셈블러를 통해 오브젝트파일(.o)파일로 변환됨오브젝트 파일은 0과 1로 된 기계어로 구성되어 있기 때문에 일반적인 텍스트 에디터로는 내용을 확인할 수 없음오브젝트 파일은 코드 영역과 데이터 영역이 분리되어 있음 링커는 여러 개의 오브젝트 파일을 하나의 코드영역과 데이터영역으로 묶음실제로 실행될 주소를 매핑시켜줌링커까지 거치면 실행파일(.exe)파일이 생성됨 사용자가 프로그램을 실행시키면 운영체제가 프로세스를 생성운영체제는 exe파일에 있는 코드영역과 데이터영역을 가져와 프로세스의 코드영역과 데이터영역에 넣어주고 빈 상태의 스택과 힙을 할당PCB를 만들어 프로세스 관리가 가능하도록 만듦PCB의 프로그램 카운터를 생성한 프로세스의 코드영역의 첫번째 주소로 설정운영체제의 CPU 스케줄링에 따라 프로세스가 실행되다가 작업을 마치고 종료됨 메모리1. 메모리 종류레지스터가장 빠른 기억장소로 CPU내에 존재전원이 공급되지 않으면 데이터가 사라지는 휘발성 메모리32bit 크기의 레지스터를 가짐 → 32bit CPU64bit 크기의 레지스터를 가짐 → 64bit CPUcpu는 계산을 할 때 메인메모리에 있는 값을 레지스터로 가져와서 계산계산결과는 다시 메인메모리에 저장캐시레지스터와 메모리의 중간 다리 역할을 하는 메모리레지스터가 필요로 할 것 같은 데이터를 메인메모리에서 미리 가져와서 저장해두는 장소휘발성 메모리캐시는 성능의 이유로 L1, L2, L3등 여러 개가 존재CPU가 값을 요청해 레지스터로 값을 옮겨야 할 때 가장 속도가 빠른 L1 → L2 → L3 → 메인메모리의 순서대로 참조하여 값을 가져옴 (값이 없으면 하위 단계를 참조하는 방식)메인메모리실제 운영체제와 다른 프로세스들이 올라가는 공간전원이 공급되지 않으면 데이터가 사라지는 휘발성 메모리보조저장장치보다 가격이 비싸고 휘발성이기 때문에 실행중인 프로그램만 올림보조저장장치(HDD/SSD)가격이 저렴하고 전원이 공급되지 않아도 데이터가 지워지지 않는 비휘발성 메모리 2. 메모리와 주소유니프로그래밍 환경에서는 하나의 프로세스만 메모리에 올라오기 때문에 메모리 관리가 어렵지 않았음멀티프로그래밍 환경에서는 여러 프로세스가 메모리에 올라오기 때문에 메모리 복잡하고 어려워졌음주소 변환 필요프로세스 간 메모리 침범 방지 대책 필요동적 메모리 할당 및 해제가 복잡프로세스 간 메모리 공유 및 보호 문제32bit CPU와 64bit CPU32bit CPU레지스터 크기, ALU, 버스의 크기가 모두 32bit최대 메모리의 크기: 2^32 = 4GB64bit CPU레지스터 크기, ALU, 버스의 크기가 모두 64bit최대 메모리의 크기: 2^64 = 거의 무한대64bit CPU가 1번에 처리할 수 있는 양이 더 많으므로 속도가 더 빠름물리주소와 논리주소 물리 주소 공간: 메모리의 실제 주소공간논리 주소 공간: 사용자 관점에서 바라본 주소공간 경계 레지스터사용자 프로세스가 운영체제의 영역에 함부로 접근하지 못하도록 하드웨어적으로 운영체제 공간과 사용자 공간을 나누는 역할을 하는 레지스터CPU내에 존재하는 레지스터로 메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 검사하고 만약 벗어났다면 그 프로세스를 종료시킴 절대주소와 상대주소 실제 프로그램은 4000번지에서 시작되지만 컴파일러는 0번지에서 시작한다고 생각함절대 주소(물리 주소)메모리 내에서 프로세스가 실행되는 실제 주소 공간메모리 관리자 관점으로 바라본 주소그림에서는 실제 프로그램이 올라간 4000번지상대 주소(논리주소)사용자 관점으로 바라본 주소그림에서는 컴파일러가 생각한 0번지 CPU가 100번지의 값을 요청하면 재배치 레지스터 저장된 값인 4000번지의 값을 더한 4100번지의 값에 접근하여 데이터를 가져옴재배치 레지스터에는 프로그램의 시작주소가 저장되어 있음메모리 관리자는 사용자 접근 시마다 위의 방식대로 계산메모리 관리자 덕분에 주소에 대해 크게 신경쓰지 않아도 프로그램을 만들 수 있고 시작영역이 변경되더라도 재배치 레지스터의 값만 변경하면 되기에 굉장히 유연함 3. 메모리 할당방식메모리 오버레이메모리의 크기보다 더 큰 프로그램을 실행시키는 방법큰 프로그램을 작게 나누어 일부만 메모리에서 실행하고 나머지는 하드디스크의 스왑영역에 저장 하지만 스왑영역도 하드디스크의 일부 영역이고 스왑영역의 데이터와 메모리의 데이터를 교체하는 작업이 필요하므로 실제 메모리보다는 느리게 동작함가변 분할 방식과 고정 분할 방식 한 프로세스가 메모리의 연속된 공간에 할당되므로 연속 메모리 할당 이라고도 부름 한 프로세스가 메모리에 분산되어 할당되기 때문에 비연속 메모리 할당 이라고도 부름가변 분할 방식의 장/단점장점 단점 프로세스의 크기에 딱 맞게 할당됨 → 내부 단편화가 없음 외부 단편화가 발생고정 분할 방식의 장/단점장점 단점 같은 크기로 나누기 때문에 단순함 → 구현이 간단하고 오버헤드가 적음 작은 프로세스가 큰 공간에 할당되어 낭비되는 공간이 발생 → 내부 단편화가 발생외부 단편화충분한 메모리 공간이 있음에도, 연속된 빈 공간의 크기가 부족하여 프로세스를 메모리에 할당할 수 없는 상태 조각 모음을 통해 외부 단편화가 발생한 공간을 합칠 수 있지만 실행중인 프로세스들을 일시 중지해야하고 메모리 공간을 이동시키는 작업을 수행해야 하므로 오버헤드 발생내부 단편화분할 메모리의 크기가 프로세스가 필요한 크기보다 크게 할당되어 내부에 빈 공간이 생겨 낭비되는 현상 낭비되는 공간을 해결할 뚜렷한 방법은 없으나, 분할 메모리의 크기를 조절하여 내부단편화를 최소화하는 전략을 취함버디 시스템2의 제곱수로 메모리를 분할하여 메모리를 할당하는 방식 메모리를 2의 제곱수로 나누어 프로세스가 필요로 하는 크기보다 작을 때까지 나눔위 그림에서는 500이므로 256까지 메모리를 나눔나눴을 때 가장 작은 단위보다 한 단계 위의 공간에 프로세스를 할당256에는 할당할 수 없으므로 512에 할당여기서도 내부 단편화가 발생하지만 그 값을 최소화할 수 있음프로세스가 종료되어 메모리가 다시 확보되었을 때 비슷한 크기 혹은 같은 크기의 분할 공간이기에 메모리를 다시 합치기도 용이함 버디 시스템 방식가변 분할 방식처럼 프로세스의 크기에 따라 유동적으로 메모리를 할당 가능외부 단편화 방지를 위해 메모리 공간을 확보하는 것이 용이외부고정 분할 방식처럼 내부 단편화가 발생하지만 많은 공간 낭비가 발생하지 않음 자료구조재귀(Recursion)1. 재귀란?어떠한 것을 정의할 때 자기 자신을 참조하는 것재귀적으로 정의된 함수를 재귀함수라고 부름 2. 재귀 함수의 간단한 예시// 잘못된 방식의 재귀함수 function myFunction(number){ console.log(number); myFunction(number + 1); } myFunction(1); // 이 함수를 실행하면 정확한 종료 조건(기저 조건)이 없기 때문에 // 콜스택이 쌓여 계속 메모리 공간이 가득 차서 자동으로 종료됨 // 올바른 형식의 재귀함수 function myFunction(number){ if (number > 3) return; console.log(number); myFunction(number + 1); } myFunction(1); // 이 함수는 1 ~ 3까지는 재귀적으로 자신을 호출하다가 // 종료 조건(기저 조건)인 number > 3에 걸리게 되면 함수를 종료 3. 콜스택스택의 영역의 일부 중 함수가 호출되면서 올라가는 영역재귀 함수 호출 시 플로우 차트 위 그림처럼 함수를 호출할 때마다 위와 같이 콜스택에 쌓이게 됨재귀를 사용하는 이유 : 더 복잡한 문제를 쉽게 해결하기 위해팩토리얼, 피보나치 수열문제 등 4. 재귀적으로 생각하기 (재귀로 풀 수 있는 유형 알아보기)단순 반복 → 반복문을 재귀로 변경하기반복문을 재귀로 변경하면 성능 상 이점이 크게 없음 (메모리 문제 때문에 오히려 감소할 수도…)하위 문제의 결과를 상위 문제의 해결에 사용하는 경우 (하향식 계산) ⭐⭐⭐배열의 합, 문자열의 길이, power 함수 … 5. 하노이의 탑 ⭐⭐⭐하향식 접근을 통한 하노이의 탑 풀이하노이의 탑 코드 /** * @param {*} ringCount 원반 개수 * @param {*} from 출발지 기둥 * @param {*} to 임시 기둥 * @param {*} temp 목적지 기둥 * @returns */ function hanoi(ringCount, from, to, temp) { /* 종료(기저) 조건 */ if (ringCount == 0) return; /* 재귀 조건 */ // 기둥 A에 있는 원반 1,2를 B로 옮김 hanoi(ringCount - 1, from, temp, to); // 기둥 A에 있는 원반 3을 C로 옮김 console.log(`원반 ${ringCount}을(를) ${from}에서 ${to}로 이동`); // 기둥 B에 있는 원반 1,2을 C로 옮김 hanoi(ringCount - 1, temp, to, from); } hanoi(3, 'A', 'C', 'B'); 일주일 간의 회고🍷칭찬하고 싶은 점절대적 시간이 부족했지만 포기하지 않고 운영체제 강의는 끝까지 완주한 점배운 내용까지 최대한 디테일하게 정리한 점😅아쉬웠던 점자료구조 및 알고리즘의 재귀까지는 제대로 강의를 들었지만 정렬 부분은 아직 정리를 못했습니다. ㅠㅠㅠ예비군 2박3일 일정을 알고 있었는데도 시간 관리를 제대로 하지 못한 점이 아쉽습니다.🛠보완하고 싶은 점시간에 쫒겨서 제대로 정리하지 못한 부분을 제대로 정리하고 마지막 주차 잘 준비했으면 합니다.일단 이해가 가지 않더라도 중간에 끊지 않고 먼저 1번 듣고 그 다음에 정리하는 습관을 몸에 들여야겠습니다.

인프런 워밍업 클럽 CS 3기 2주차 미션 (운영체제)

운영체제FIFO 스케줄링의 장단점이 뭔가요?장점: - 먼저 온 프로세스가 먼저 CPU를 사용하는 First In First Out의 구조를 가지기 때문에 단순하고 직관적입니다.단점: - 현재 실행 중인 프로세스가 완전히 끝나야 다음 프로세스가 실행되기 때문에 먼저 도착한 실행시간이 긴 프로세스가 완료될 때까지 기다려야 하는 Convoy effect(호위 효과)가 일어날 수 있습니다.- FIFO 스케줄링은 비선점의 특징을 가지기 때문에 실행 중인 프로세스가 CPU를 스스로 포기하지 않는 한 강제로 CPU를 뺏을 수 없습니다.- 만약 CPU를 사용하는 프로세스가 I/O 작업을 진행하고 있다면 CPU는 쉬고 있는 상태가 되기 때문에 CPU 사용률이 좋지 않습니다.SJF를 사용하기 여러운 이유가 뭔가요?- 프로세스의 종료시간을 예측하는 것은 거의 불가능하기 때문입니다.- Burst Time이 긴 프로세스는 실행 순위가 계속 뒤로 밀려 아주 오랫동안 실행되지 않을 수 있습니다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?- 타임 슬라이스를 너무 작게 설정하면 컨텍스트 스위칭이 너무 자주 일어나게 되어 오버헤드가 커지게 됩니다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?- CPU를 사용하는 프로세스가 타임 슬라이스 전에 CPU를 스스로 반납한다면 운영체제는 이 프로세스의 CPU 사용량이 적으므로 I/O Bound Process일 가능성이 높다고 판단합니다.- 반대로 CPU를 사용하는 프로세스가 타임 슬라이스를 오버하여 CPU 스케줄러에 의해 강제로 CPU를 뺏긴다면 운영체제는 이 프로세스의 CPU 사용량이 높으므로 CPU Bound Process일 가능성이 높다고 판단합니다. 공유자원이란무엇인가요?- 프로세스/쓰레드 간 통신을 할 때 여러 프로세스/쓰레드가 공동으로 이용하는 자원(메모리, 변수, 파일, 데이터 등…)을 ‘공유자원’이라고 합니다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?- 교착상태의 필요조건으로는 4가지가 있습니다.- 상호 배제어떤 프로세스/쓰레드가 한 리소스를 점유했다면 그 리소스를 사용하는 동안 다른 프로세스에게 공유되면 안됨식사하는 철학자에서 포크가 리소스에 해당합니다.- 비선점프로세스/쓰레드 A가 리소스를 점유하고 있는데 프로세스/쓰레드 B가 그 리소스를 빼앗을 수 없어야 함식사하는 철학자에서 철학자 A가 들고 있는 포크를 철학자 B가 뺏을 수 없는 상황에 해당합니다.- 점유와 대기어떤 프로세스/쓰레드가 리소스를 가지고 있는 상태에서 추가적인 리소스를 원하지만 추가 리소스를 사용할 수 없어 대기하는 상태식사하는 철학자에서 오른쪽 포크를 손에 쥔 채로 왼쪽 포크를 기다리는 상태를 의미합니다.- 원형 대기점유와 대기를 하는 프로세스/쓰레들의 관계가 원형(순환 구조)을 이루며, 각 프로세스가 다음 프로세스가 보유한 리소스를 기다리는 상황.식사하는 철학자에서 서로가 서로의 포크를 원하는 원형(순환 구조)를 이루는 상황에 해당합니다.

인프런 워밍업 클럽 CS 3기 2주차 미션 (자료구조와 알고리즘)

자료구조재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?종료 조건을 설정하지 않거나 잘못 설정했을 경우 콜스택의 누적으로 인한 메모리 부족으로 강제 종료되거나 혹은 의도하지 않은 결과값을 얻을 수 있습니다.0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ // 탈출(기저) 조건 : n이 1일 때 if (n == 1){ return 1; } // 재귀 조건 : n이 1보다 큰 홀수일 때 if (n%2 == 1){ return sumOdd(n-2) + n; } else{ return sumOdd(n-1); } } console.log(sumOdd(10)) // 25다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.변경 이전const fs = require("fs"); // 파일을 이용하는 모듈 const path = require("path"); // 폴더와 파일의 경로를 지정해주는 모듈 function traverseDirectory1(directory){ const stack = [directory]; // 순회해야 할 디렉토리를 저장할 스택 while (stack.length > 0) { // 스택이 빌 때까지 반복 const currentDir = stack.pop(); // 현재 디렉토리 const files = fs.readdirSync(currentDir); // 인자로 주어진 경로의 디렉토리에 있는 파일or디렉토리들 for (const file of files) { // 현재 디렉토리의 모든 파일or디렉토리 순회 const filePath = path.join(currentDir, file); //directory와 file을 하나의 경로로 합쳐줌 const fileStatus= fs.statSync(filePath); // 파일정보 얻기 if (fileStatus.isDirectory()) { // 해당 파일이 디렉토리라면 console.log('디렉토리:', filePath); stack.push(filePath); } else { // 해당 파일이 파일이라면 console.log('파일:', filePath); } } } } traverseDirectory1("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력 변경 이후const fs = require("fs"); // 파일을 이용하는 모듈 const path = require("path"); // 폴더와 파일의 경로를 지정해주는 모듈 function traverseDirectory2(directory){ const files = fs.readdirSync(directory); for (const file of files) { // 모든 파일 및 디렉토리를 순회 const filePath = path.join(directory, file); // 현재 디렉토리와 파일/디렉토리 이름을 결합하여 전체 경로 생성 const fileStatus = fs.statSync(filePath); // 파일/디렉토리 정보를 가져옴 /* 재귀조건: 해당 경로가 디렉토리인 경우 */ if (fileStatus.isDirectory()) { console.log('디렉토리:', filePath); traverseDirectoryRecursive(filePath); // 재귀 호출 } /* 탈출조건: 해당 경로가 파일인 경우 */ else { console.log('파일:', filePath); } } } traverseDirectory2("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력

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

강의 내용 요약운영체제운영체제의 기본 개념운영체제의 필요성과 역할컴퓨터 동작에 있어서 운영체제는 반드시 필요한가?✔ 정답은 No 다.❗하지만 운영체제가 없으면 컴퓨터는 처음 설계한 대로 동작할 뿐 다른 기능을 수행할 수 없다.운영체제의 역할프로세스 관리메모리 관리하드웨어 관리파일 시스템 관리 운영체제의 구조 커널 ⭐⭐⭐프로세서, 메모리, 저장장치를 관리하는 핵심 기능을 담당사용자는 운영체제의 커널에 직접 접근할 수 없으며 인터페이스(CLI, GUI)를 통해 접근 가능어플리케이션(게임, 인터넷, MS office, 멜론 뮤직….)은 시스템 콜을 통해 커널에 접근 가능 인터페이스(GUI/CLI)는 쉘(Shell)이나 API를 통해 간접적으로 시스템 콜을 이용(인터페이스(GUI/CLI) → 쉘 또는 API → 시스템 콜 → 커널)시스템 콜은 응용 프로그램이 직접 커널을 호출하는 방식 컴퓨터 하드웨어폰 노이만 구조CPU와 메모리를 버스(데이터를 전달하는 통로)로 연결하는 방식프로그램을 메모리에 올려서 실행시킴(프로그램 내장 방식)CPU 구조산술논리 연산장치(ALU, Arithmetic and Logical Unit)CPU 내에서 실제로 데이터 연산을 담당제어 장치(Control Unit)모든 장치들의 동작을 지시하고 제어레지스터(Register)CPU 내에서 계산을 위해 임시로 보관하는 장치 3. 메모리 종류RAM(Random Access Memory)무작위 위치의 데이터를 읽어도 저장된 위치와 상관없이 데이터를 읽는 속도가 같음전력이 끊기면 데이터가 소실됨(휘발성)메인 메모리로 사용ROM(Read Only Memory)전력이 끊겨도 계속 데이터를 보관할 수 있음(비휘발성)데이터를 한 번 쓰면 수정이 불가능함부팅과 관련된 BIOS를 저장하는 용도로 사용 4. 인터럽트와 폴링CPU가 입출력 작업을 처리한다고 가정폴링 방식CPU가 주기적으로 입출력 명령을 확인하여 명령을 처리하는 방식CPU의 성능 저하가 발생인터럽트 방식CPU가 프로그램을 실행하고 있을 때, 입출력 처리가 필요한 경우 CPU에게 이를 알려주는 방식CPU는 인터럽트가 발생했을 때만 입출력을 처리하므로 그 외의 경우에는 다른 작업을 수행할 수 있음 → 비동기적으로 동작하기 때문에 성능 이점하드웨어 인터럽트: 입출력 인터럽트, 외부 신호 인터럽트 등등소프트웨어 인터럽트: 프로그램 오류로 인한 인터럽트(Exception, Underflow/Overflow, Divison by Zero 등등) 프로그램과 프로세스프로그램이란?하드디스크나 SSD와 같은 저장장치에 저장된 명령문의 집합체애플리케이션 혹은 앱이라고도 불리며 windows 운영체제 기준 .exe 확장자를 가짐컴퓨터 관점에서 저장장치만 사용하는 수동적인 형태 2. 프로세스란?실행중인 프로그램 → 저장장치에 저장된 프로그램이 메모리에 올라가서 실행중인 상태컴퓨터 관점에서 메모리를 사용하고 운영체제의 CPU 스케줄링 알고리즘에 따라서 CPU도 사용하고 필요에 따라 입출력도 수행하는 능동적인 형태프로세스 구조(메모리 구조와 같음)code(text) : 실행할 소스코드가 저장되어 있는 영역data : 전역 변수와 정적(static) 변수가 할당되는 영역stack : 지역 변수와 함수 호출 시 필요한 정보(매개변수 등)가 저장되는 영역heap : 프로그래머에 의해 동적으로 할당/해제되는 메모리 영역C언어의 malloc(), free()가 대표적인 heap 영역을 동적 할당하는 함수 멀티프로그래밍과 멀티프로세싱유니프로그래밍 메모리에 하나의 프로세스가 올라온 것 멀티프로그래밍 메모리에 여러 개의 프로세스가 올라온 것 멀티프로세싱 CPU가 여러 개의 프로세스를 처리하는 것메모리 관점이 아닌 CPU 관점 현대의 멀티프로그래밍과 멀티프로세싱현대의 OS(운영체제)에는 멀티프로그래밍과 멀티프로세싱이 공존함메모리에는 여러 개의 프로세스가 동시에 올라올 수 있고(멀티프로그래밍), CPU는 시분할처리를 이용하여 각각의 프로세스를 짧은 시간 동안 교대로 실행함(멀티프로세싱) PCB(Process Control Block)PCB란?프로세스에 대한 정보를 가지고 있는 커널의 자료구조PCB는 특정 프로세스에 관한 모든 정보를 가지고 있음PCB들은 연결 리스트 방식으로 저장됨. PCB의 구조포인터 : 부모/자식 프로세스에 대한 포인터, 프로세스의 현재 위치에 대한 포인터, 할당된 자원에 대한 포인터 정보프로세스 상태 : 프로세스의 상태(생성, 준비, 실행, 대기, 종료)에 대한 정보를 저장프로세스 ID : 프로세스를 식별하기 위한 고유한 숫자값이 저장프로그램 카운터 : 다음에 실행될 명령어의 주소를 저장레지스터 정보 : 프로세스가 실행될 때 사용했던 레지스터 값들이 저장됨(CPU를 뺏기고 다시 시작할 때 이전에 사용하던 값을 복구하기 위한 용도)메모리 관련 정보 : 프로세스가 메모리에 있는 위치 정보, 메모리 침범을 막기 위한 경계 레지스터 값 등이 저장됨CPU 스케줄링 정보: CPU 스케줄링에 필요한 우선순위, 최종 실행시간, CPU 점유시간 등이 저장됨 프로세스 상태프로세스 상태가 왜 존재하는가?시분할 시스템을 사용하는 운영체제는 여러 개의 프로세스를 돌아가면서 실행함속도가 매우 빨라 동시에 실행하는 것처럼 보이지만, CPU는 한 순간에는 하나의 프로세스밖에 처리하지 못함시분할 시스템에 대응하기 위해 프로세스는 5가지의 상태를 가짐프로세스 상태의 종류생성(New)메모리에 프로그램 적재를 요청한 상태메모리에 프로그램 적재가 승인되면 그 때 PCB가 생성되고 준비 상태로 넘어간다.준비(Ready)프로세스가 CPU 사용을 위해 기다리고 있는 상태준비 상태의 프로세스는 CPU 스케줄러에 의해 CPU가 할당됨대부분의 프로세스는 준비 상태에서 CPU 사용을 기다리고 있음실행(Running)프로세스가 CPU 스케줄러에 의해 CPU를 할당받아 실행되는 상태준비 → 실행 (Dispatch)실행 상태에 있는 프로세스의 수는 CPU의 개수(CPU의 코어 개수)만큼임실행 상태에 있는 프로세스는 CPU 스케줄러가 부여한 시간 만큼만 CPU를 사용할 수 있음프로세스가 할당된 시간을 초과하면 CPU 스케줄러는 CPU를 강제로 빼앗기며 준비 상태로 돌아감 (Timeout)실행 → 준비 (Timeout)대기(Waiting)프로세스가 입출력 요청을 하면 입출력이 완료될 때까지 기다리는 상태실행 중인 프로세스가 입출력 요청을 하면 해당 프로세스를 대기 상태로 두고 다른 프로세스에게 CPU를 할당함실행 → 대기 (Block)입출력 작업이 끝나면 대기 상태에 있던 프로세스는 다시 CPU 할당을 위해 준비 상태로 이동대기 → 준비 (Wakeup)완료(Terminated)프로세스가 종료된 상태프로세스가 사용했던 데이터를 메모리에서 제거하고 PCB도 제거 프로세스 상태 전이 다이어그램 컨텍스트 스위칭(Context Switching)컨텍스트 스위칭이란?프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행 중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업 컨텍스트 스위칭이 발생할 때 PCB의 내용이 변경됨프로세스 상태프로그램 카운터레지스터 정보메모리 관련 정보 실행 중인 프로세스의 작업내용을 해당 프로세스의 PCB에 저장 → 다음에 실행될 프로세스의 PCB의 내용대로 CPU를 세팅 프로세스 생성과 종료프로세스의 생성 (0번 프로세스) 운영체제는 프로그램의 코드영역과 데이터 영역을 메모리에 로드빈 스택과 힙을 만들어 메모리 공간을 확보프로세스를 관리하기 위한 PCB 생성하여 값을 초기화 위의 과정은 운영체제가 부팅되고 0번 프로세스가 생성될 때 딱 1번만 실행 프로세스의 복사 (나머지 프로세스)나머지 모든 프로세스는 새로 생성이 아닌 0번 프로세스를 복사해서 사용프로세스 복사는 fork() 함수를 이용부모 프로세스를 복사해서 자식 프로세스를 생성리턴값으로 부모 프로세스에는 자식 프로세스의 PID, 자식 프로세스에는 0을 반환 프로세스 복사를 통해 생성되는 프로세스는 자식 프로세스복사의 원본이 되는 프로세스는 부모 프로세스 자식 프로세스는 부모 프로세스의 코드,데이터, 스택 영역과 PCB의 모든 내용을 복사 → 부모 프로세스와 완전 동일자식 프로세스가 부모와 완전히 같으면 자신이 원하는 코드는 어떻게 실행할까?exec() 함수 이용fork() 함수로 프로세스 복사 → exec() 함수로 코드와 데이터 영역을 원하는 값으로 덮어쓰기exec() 함수가 완료된 시점부터 부모 프로세스와는 완전히 다른 방식으로 작동 (부모-자식 관계는 계속 유지) 좀비 프로세스?부모 프로세스가 자식 프로세스보다 먼저 종료되거나 자식 프로세스가 비정상적으로 종료돼 exit() 신호를 주지 못해서 부모가 Exit status를 읽지 못해 메모리에 계속 살아있는 상태 쓰레드(Thread)쓰레드는 왜 필요한가? 운영체제가 기본적으로 작업을 처리하는 단위는 프로세스프로세스의 수가 많아지면 각각의 프로세스에 대해서 PCB를 생성하고 메모리에 코드, 데이터, 스택, 힙영역을 모두 할당해줘야 하므로 너무 무거워짐 크롬 브라우저의 경우 탭 1개 당 프로세스 1개로 동작탭을 많이 띄울 수록 크롬 브라우저가 가지는 프로세스의 수가 늘어남크롬 브라우저가 메모리를 너무 많이 차지하게 됨크롬 브라우저의 탭들은 통신을 위해 IPC(Inter Process Communication)을 이용하는데 IPC는 상대적으로 통신의 비용이 비쌈 프로세스가 컴퓨터 자원을 많이 차지하는 문제점을 해결하기 위해 쓰레드 라는 개념을 도입 2. 쓰레드란? 쓰레드는 프로세스 내에 존재하는 것으로 하나의 프로세스는 1개 이상의 쓰레드를 가질 수 있음.한 프로세스 내의 쓰레드들은 그 프로세스의 PCB, 코드, 데이터, 힙영역을 공유하며 스택은 쓰레드마다 각자 가지고 있음쓰레드는 스택을 제외한 나머지 영역을 공유해서 사용하기 때문에 프로세스 대비 메모리 절약이 많이 됨한 프로세스의 내의 여러 쓰레드를 구분하기 위해 쓰레드 ID를 부여하고 쓰레드 관리를 위한 TCB(Thread Control Block)도 생성운영체제는 프로세스 내의 쓰레드를 구분할 수 있으며 작업을 처리하는 단위는 쓰레드가 되었음크롬 브라우저와 달리 파이어폭스 브라우저는 처음 4개의 탭만 프로세스를 생성하고 추가적인 탭은 생성된 프로세스 내에 쓰레드를 추가하는 방식으로 동작3. 프로세스 vs 쓰레드CPU 스케줄링CPU 스케줄링이란?운영체제가 특정 규칙에 따라 프로세스에게 CPU를 할당/해제하는 것CPU 스케줄러(운영체제 내부에 존재)가 CPU 스케줄링에서 고려해야 할 사항어떤 프로세스에게 CPU 리소스를 줘야 하는가?CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야 하는가?CPU Burst : 프로세스가 CPU를 할당받아 작업을 수행하는 것I/O Burst : 프로세스가 입출력(I/O) 장치를 사용하여 데이터를 처리하는 것 다중 큐와 프로세스 스케줄링 프로세스의 상태 중 준비 상태와 대기 상태는 다중 큐에 의해 관리됨프로세스가 실행 상태에서 준비 상태로 돌아갈 때 운영체제는 해당 프로세스의 우선순위를 보고 그에 맞는 준비 큐에 넣음 CPU 스케줄러는 준비 상태의 다중 큐에 들어있는 프로세스들 중에 우선순위가 높은 프로세스를 선택하여 실행 상태로 전환시킴 프로세스가 실행 상태에서 I/O 요청을 받아 대기 상태로 오게 되면 I/O 작업 종류에 따라 분류된 큐에 들어가게 됨 정확히는 큐에는 프로세스 자체가 아닌 프로세스의 정보를 가지고 있는 PCB가 들어감 CPU 스케줄링의 핵심 목표리소스 사용률 (CPU, I/O 디바이스 등의 사용률을 높이는 것을 목표)오버헤드 최소화 (복잡하지 않은 스케줄링 방식 채택, 컨텍스트 스위칭 최소화가 목적)공평성 (모든 프로세스에서 공평하게 CPU가 할당되는 것을 목표)공평성의 의미는 사용하는 시스템의 환경에 따라 달라질 수 있음ex) 자율주행 자동차의 운영체제는 다른 프로세스보다 자율주행 프로세스에 CPU를 더 많이 할당위와 같은 특수한 시스템이 아닌 일반 시스템의 경우, 모든 프로세스에게 CPU가 골고루 할당되는 것이 공평처리량 (단위시간당 더 많은 처리하는 것을 목표)대기시간 (작업을 요청하고 실제 작업이 이루어지기 전까지 대기시간이 짧은 것을 목표)응답시간 (사용자의 요청에 빠르게 반응하는 것을 목표) 목표 간의 서로 상충하는 부분이 있기 때문에 사용하는 시스템에 따라서 목표를 다르게 설정해야 함 일반적인 시스템의 경우 밸런스를 유지하는 것이 중요 4. CPU 스케줄링 알고리즘FIFO(First In First Out)SJF(Shortest Job First)RR(Round Robin)MLFQ(Multi Level Feedback Queue) 자료구조자료구조와 알고리즘자료구조란?데이터가 저장, 사용되는 방법 및 형식자료구조에 따라서 처리 방법이 달라질 뿐만 아니라 코드가 더 단순해질 수도 있음.// 일반 변수를 이용해 평균을 구하는 경우 let a = 87; let b = 70; let c = 100; // 데이터를 1개 추가하는 경우 let d = 55; let average = (a+b+c)/3; average = (a+b+c)/4;// 배열을 이용해 평균을 구하는 경우 let arr = [87,70,100]; // 데이터를 1개 추가하는 경우 arr.push(55); let average = 0; for (let i = 0; i 알고리즘이란?어떤 문제를 해결하기 위한 방법사용하는 자료구조에 따라서 알고리즘이 달라짐같은 자료구조에 대해서도 알고리즘은 여러가지가 존재할 수 있음 시간복잡도시간복잡도란?일반적으로 알고리즘의 속도를 성능의 척도로 사용함특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간컴퓨터의 사양이 사용자에 따라 다르기 때문에 절대적인 시간 측정이 아닌 코드에서 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측함코드에서 성능을 많은 영향을 주는 부분 → 반복문(loop)최선의 경우 : Big-Ω (Big-Omega)최악의 경우 : Big-O (Big-Oh)평균의 경우 : Big-θ ****(Big-theta)Big-O와 Big-θ를 주로 사용하며 가장 많이 사용하는 것은 Big-O 대표적인 시간 복잡도 그래프O(n) : 선형시간 알고리즘입력 데이터 수에 비례하여 계산량이 증가함O(1) : 상수시간 알고리즘입력 데이터 수와 상관없이 상수(1,2,3,4…)의 계산량을 가짐 Big-O 표기법의 특징계산에 가장 많은 영향을 미치는 항만을 표기Big-O 표기법으로 표시할 때는 상수는 큰 의미가 없으므로 제거ex) n^2 + 2n +100 → O(n^2)ex) 3n + 60 → O(n) 배열배열의 특징배열의 생김새일반적으로 프로그래밍 언어에서는 배열 선언 시 배열의 크기를 입력해야 함운영체제는 메모리에서 연속된 빈 공간을 찾아서 순서대로 값을 할당함할당하지 않는 부분은 쓰레기 값이 저장됨운영체제는 배열의 시작 주소(arr[0]의 주소)만을 기억함. 배열은 0번째 인덱스부터 시작!값에 접근 시 배열의 인덱스(arr[2], arr[4], arr[1]…)를 이용하여 접근함 배열은 인덱스 참조를 통해 길이에 상관없이 한번에 값에 접근할 수 있기 때문에 참조에서는 O(1)의 성능을 가짐. → 참조(읽기/쓰기)에서는 매우 훌륭한 성능을 지님 But, 데이터의 삽입,삭제의 성능은 좋지 않음. Why?운영체제로부터 할당받은 배열의 길이를 넘어서는 메모리 공간에는 다른 중요한 데이터가 있을 수도 있음. → 함부로 접근 불가배열의 크기가 부족하다면?다른 메모리 공간에서 기존 배열보다 더 큰 연속된 크기의 공간을 찾아야 함.찾은 뒤 그 공간에 값을 복사한 뒤에 값을 삽입해야 함따라서 매우 비효율적이다.아예 배열의 크기를 엄청 크게 해놓으면?언제 삽입될지 모르는 데이터를 위해 큰 공간을 미리 할당하는 것은 엄청난 메모리 낭비임.배열 중간에 데이터 삽입/삭제는?넣으려는 위치의 값을 덮어씌우거나 혹은 모두 한 칸씩 뒤로 밀어야 한다. → 많은 연산 발생(오버헤드가 큼)삭제하려는 값을 지우고 그 뒤의 값을 모두 한 칸씩 앞으로 당겨야 한다. → 많은 연산 발생(오버헤드가 큼) 2. 자바스크립트의 배열자바스크립트의 배열은 일반적인 배열과는 조금 다르게 동작한다.자바스크립트의 경우 상황에 따라서 연속적, 불연속적으로 메모리를 할당불연속적으로 할당된 메모리는 내부적으로 연결해서 사용하여 사용자에게는 배열인 것처럼 보임자료구조의 기능적인 부분은 일반적인 배열과 동일하므로 배열이라 부른다. 연결리스트(Linked List)연결리스트배열의 단점인 메모리 낭비와 데이터 삽입/삭제를 해결하기 위해 탄생한 자료구조저장하려는 데이터를 메모리 공간에 분산해 할당 + 데이터들을 서로 연결연결리스트의 노드 구조데이터를 담는 변수(DATA) + 다음 노드를 가리키는 변수(NEXT)로 구성 연결리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근 할 수 있음.장점데이터 삽입 시 빈 메모리 공간 아무 곳에 데이터를 생성하고 연결만 하면 되기 때문에 초기 크기를 알 필요가 없음삭제도 삽입과 마찬가지로 연결만 끊어주면 됨따라서 삽입/삭제가 수월함단점연결리스트의 경우 데이터들이 모두 분산되어 있기 때문에 배열처럼 바로 접근할 수 없음.ex) 5번째 노드의 데이터에 접근하고 싶어!1번째 노드의 next로 2번째 노드 접근 → 2번째 노드의 next로 3번째 노드 접근 → 3번째 노드의 next로 4번째 노드 접근 → 4번째 노드의 next로 5번째 노드 접근 → 5번째 노드 데이터 찾았다! → O(n)의 성능 배열 vs 연결리스트 스택(Stack)스택이란?FILO(First In Last Out)의 규칙을 가지는 자료구조사용 사례Ctrl+Z(되돌리기), 인터넷의 뒤로 가기, 문법 검사기 연결 리스트를 이용한 스택의 구현 방법삽입(Push)데이터 삽입을 무조건 첫번째 인덱스(head)에 하는 방식제거(Pop)무조건 첫번째 인덱스(head)만 제거하는 방식 큐(Queue)큐란?FIFO(First In, First Out)의 규칙을 가지는 자료구조큐는 운영체제에서도 사용됨(FIFO 스케줄링)head와 tail을 이용하는 큐를 구현할 때, 단방향 연결리스트는 이전 노드를 가리켜야 하는 삭제 작업을 수행하기 어렵기 때문에 양방향 연결리스트로 구현해야 함 덱(Deque)덱이란? 데이터의 삽입과 제거를 head와 tail 두 군데서 자유롭게 할 수 있는 구조 (Double Ended Queue)덱은 이러한 특징을 가지고 있기 때문에 덱을 이용하면 스택과 큐를 모두 구현할 수 있음스택 → (head에 데이터 삽입 + head에서 데이터 제거) or (tail에 데이터 삽입 + tail에서 데이터 제거)큐 → (head에 데이터 삽입 + tail에서 데이터 제거) or (tail에 데이터 삽입 + head에서 데이터 제거) 해시 테이블(Hash Table)해시 테이블이란?해시와 테이블이 합쳐진 자료구조프로그래밍 언어에 따라 조금씩 다른 내용을 가지고 있음 (Hash, Map, HashMap, Dictionary)왼쪽과 같은 데이터 형식을 테이블이라 부르며 이를 저장하기 가장 간단한 방법은 배열에 저장하는 것테이블을 오른쪽 배열과 같은 형식으로 저장했을 때 중간중간 빈 공간이 많이 발생하게 되어 메모리 낭비가 심하게 됨이를 보완하기 위하여 기존의 인덱스를 어떠한 계산을 통해 정해진 범위 내로 한정하는 방법을 고안해냄 → 해시 함수오른쪽의 배열은 해시 함수를 통해 테이블의 인덱스를 새로 만들기 때문에 해시 테이블이라 불림해시 테이블의 인덱스는 key, 데이터는 value라고 불림해시 테이블은 데이터 접근, 삽입, 삭제, 수정 모두 O(1)의 성능을 가짐 다만 해시 테이블은 collision(충돌)이 발생할 가능성이 있음충돌 : 같은 key를 가지는 데이터가 여러 개인 경우해시 함수를 등번호를 10으로 나눈 나머지라고 가정할 때, “이운재”와 “박지성”, “최진철”과 “이천수”는 같은 key값(1과 4)을 가져 충돌이 발생충돌을 해결하기 위해 해당 key의 value를 연결리스트 형태로 구성하여 데이터를 연결 → O(n)의 성능을 가짐하나의 key에 value들이 집중되는 충돌 현상을 최소화하기 위해 해시 함수의 선정이 굉장히 중요함좋은 해시 함수 : 데이터를 각 key에 골고루 분배시켜주는 함수해시 테이블의 장/단점 정리 셋(set)셋이란? 데이터의 중복을 허용하지 않는 자료구조셋은 해시 테이블을 이용하기 때문에 해시 셋(Hash Set)이라고도 불림셋은 해시 테이블의 value값은 사용하지 않고 key만을 사용하여 구현위 테이블에서 “리오넬 메시”와 “크리스티아누 호날두”는 key가 중복되기 때문에 셋에서는 허용되지 않는다. 일주일 간의 회고🍷칭찬하고 싶은 점전공시간에 한번 배웠던 내용들이라서 생소하지는 않았지만 감자님이 강의하시는 내용을 뼈대로 제가 알고 있는 지식, 구글링을 통해 알게 된 지식 등을 살을 붙여 개인 노션 및 velog에 업로드하였습니다.자료구조의 추상 자료형 이해를 위해 그림을 그려가며 이해하도록 노력하였고 강의 내의 질문 및 답변에서 스스로 답을 도출하거나 혹은 질문을 통해 모르는 부분을 해소하였습니다.😅아쉬웠던 점정리를 위해서 강의를 여러 번 돌려보다 보니 생각보다 많은 시간이 소요되었습니다.강의 하나의 템포가 길어지니 생각보다 정신적으로 피로가 빨리 찾아왔습니다.🛠보완하고 싶은 점다음 주에 예비군 훈련이 있어서 평일에 시간을 내기가 더 어려울 것이라 예상되므로 시간 관리를 더 잘하도록 노력해야겠습니다.미리 예습을 하는 방식으로 진도표에 적힌 진도는 반드시 맞출 수 있도록 해야겠습니다.강의를 보면서 정리하는 것이 아니라 일단 한 번 정독한 후에 다시 한 번 돌려보면서 정리를 하는 것이 시간 절약 측면에서 도움이 될 지 한 번 시험해보는 1주를 보내야겠습니다.

인프런 워밍업 클럽 CS 3기 1주차 미션 (자료구조와 알고리즘)

자료구조여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요. 해시 테이블을 이용할 것 같습니다. 해시 테이블의 경우 데이터의 삽입, 삭제, 접근, 수정이 O(1)의 성능을 가지기 때문에 매우 빠르지만 좋은 해시함수를 선정할 필요가 있으며 공간 효율성이 낮습니다. 하지만 교실의 학생 수는 많아봐야 40명이기에 메모리 공간을 크게 걱정하지 않아도 되며 학생번호를 순서대로 부여받기 때문에 간단한 해시 함수를 사용해도 해시 테이블 내의 key에 value가 고르게 분배될 것입니다. 또한 앞서 적었듯이 해시 테이블은 데이터 접근, 삽입, 삭제가 굉장히 빠르기 때문에 전학같은 이슈 발생 시에도 유연하게 대처가 가능합니다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요. FIFO의 특징을 가지는 Queue를 사용할 것입니다. DoublyLinkedList를 이용하면 Stack, Queue, Deque, hashTable을 비교적 쉽게 적용할 수 있으므로 구현은 DoublyLinkedList를 기반으로 하는 것이 좋을 것 같습니다. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.import { LinkedList } from '../LinkedList/linked_list.mjs'; class Stack { constructor() { this.LinkedList = new LinkedList(); } /** * 스택에 데이터 삽입 * @param {number} data */ push(data) { this.LinkedList.insertLast(data); } /** * 스택에서 데이터를 삭제하고 반환 * @returns {Node} */ pop() { try { return this.LinkedList.deleteLast(); } catch (error) { return null; } } /** * 스택의 맨 위 데이터를 반환 * @returns {Node} */ peek() { return this.LinkedList.getNodeAt(0); } /** * 스택이 비어있는지 확인 * @returns {boolean} */ isEmpty() { return this.LinkedList.count == 0 ? true : false; } } export { Stack }; 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력hashFunction(input){ let changed = input.charCodeAt(0) + input.charCodeAt(1); return changed % 5; } /* 결과값 4 0 2 3 2 0 4 2 3 0 1 */

인프런 워밍업 클럽 CS 3기 1주차 미션 (운영체제)

운영체제아래의 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요? while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 } 위의 while 문과 같이 일정 주기/시간 마다 체크하는 폴링 방식이 아니라 이벤트 리스너 등을 이용하여 호출했을 때만 실행하는 인터럽트 방식을 사용하는 것이 오버헤드가 더 적을 것이라 생각합니다.const onSkillActivated = function(){ console.log('스킬이 활성화되었습니다'); } const skillActivateEvent = function(callback) { document.addEventListener("skillActivated", callback); callback(); } // 이벤트 리스너가 포함된 함수 실행시 실행 skillActivateEvent(onSkillActivated); 프로그램과 프로세스가 어떻게 다른가요? 프로그램은 저장장치에 저장된 명령문들의 형태이고 프로세스는 프로그램이 메모리에 올라가서 실행중인 상태입니다. 프로세스는 메모리 적재가 승인이 되면 PCB가 생성됨과 동시에 실제 메모리 영역을 차지합니다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요? 멀티프로그래밍은 메모리에 여러 개의 프로세스가 올라온 상태입니다. 반면 멀티프로세싱은 CPU가 여러 개의 프로세스를 처리하는 것입니다. 둘의 차이를 말해보자면 멀티프로그래밍은 메모리의 관점의 접근이고 멀티프로세싱은 CPU 관점의 접근입니다. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요? 운영체제는 프로세스를 관리하기 위해 여러 가지 기법을 사용합니다. 먼저 운영체제의 커널단에서는 PCB라는 자료구조를 통해 프로세스의 모든 정보를 관리합니다. 그 다음으로 컨텍스트 스위칭과 여러 스케줄링 기법(FIFO,SJF,RR,MLFQ …)을 통해 정해진 규칙에 따라 프로세스들이 공평하게 CPU 자원을 할당받을 수 있도록 조정합니다. 컨텍스트 스위칭이란 뭔가요? 컨텍스트 스위칭이란 프로세스를 실행하는 도중에 다른 프로세스를 실행하기 위해서 현재 실행하고 있는 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업입니다. 컨텍스트 스위칭이 일어나면 PCB에 현재 상태값을 저장하기 때문에 PCB의 값(프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보…)이 변경됩니다.