[인프런 워밍업클럽 CS 2기] 3주차 미션📒

운영체제메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.1. 레지스터레지스터는 CPU 내에 존재하는 가장 빠른 기억 장로, 계산 중간에 필요한 값들을 일시적으로 저장하기 위해 사용합니다.2. 캐시(Cache)레지스터는 굉장히 빠르고, 메인메모리는 너무 느리기 때문에 메인 메모리에 있는 값을 레지스터로 옮기려면 한참 걸리므로 필요할 것 같은 데이터를 미리 가져와서 캐시에 저장합니다. 성능 상의 이유로 여러개를 둡니다.3. 메인메모리(RAM)메인메모리는 실제 운영체제와 다른 프로세스들이 올라가는 공간입니다. 휘발성 메모리로, 전원이 공급되지 않으면 데이터가 지워집니다. 하드디스크나 SSD보다 속도는 빠르지만, 가격이 비싸므로 데이터를 저장하기 보다는 실행 중인 프로그램만 올립니다.4. 보조 저장 장치(HDD, SDD)사무용 프로그램, 게임, 작업한 파일 등을 저장할 필요가 있는데, 비싸고, 휘발성인 메모리에 저장할 순 없어서, 가격이 저렴하고 전원이 공급되지 않아도 데이터가 지워지지 않는 비휘발성 메모리인 HDD, SDD를 사용합니다.사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터입니다. 경계 레지스터는 프로세스가 사용할 수 있는 메모리의 범위를 저장하는 레지스터로, 사용자 프로세스가 경계 레지스터의 범위를 벗어났는지 검사하여 벗어났다면 해당 프로세스를 종료시키는 등의 조치로 메모리를 보호합니다.메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식은 프로세스의 크기에 맞게 메모리를 동적으로 할당하는 방식입니다. 따라서 프로세스의 크기에 딱 맞게 메모리를 할당하므로 내부 단편화 문제가 적고, 메모리를 효율적으로 사용할 수 있다는 장점이 있습니다. 하지만 프로세스가 종료되면서 중간중간 작은 빈 공간이 생기면 새로운 프로세스를 적절히 배치하기 어려운 외부 단편화 문제가 발생할 수 있다는 단점이 있습니다.고정 분할 방식은 메모리를 미리 여러 개의 고정 크기 블록으로 나누어 각 프로세스에 할당하는 방식입니다. 따라서 구현이 간단하고, 오버헤드가 적으며 외부 단편화 문제가 없다는 장점이 있습니다. 하지만 작은 프로세스도 큰 영역에 할당될 수 있어 공간이 낭비되는 내부 단편화 문제가 발생할 수 있는 단점이 있습니다.고정 분할 방식은 CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱입니다. 스래싱은 프로세스에 적절한 페이지 수를 할당하는 것으로 해결 할 수 있습니다. 이를 위해 자주 사용될 확률이 높은 현재 사용중 페이지를 통째로 메모리에 올리는 워킹셋 기법을 사용할 수 있습니다.HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?HDD나 SSD는 컴퓨터를 실행시키는데 반드시 필요하진 않다고 생각합니다. 그 이유는 HDD, SDD가 없다고 가정했을 때, 일반적으로 HDD,SDD에 저장되는 것들이 다른 곳에 저장될 수 있다고 생각했기 때문입니다. HDD, SDD는 비휘발성 메모리로, 여기에 운영체제와 사용자 데이터 등을 저장합니다. HDD, SDD가 없다면 USB 같은 다른 비휘발성 메모리에 운영 체제, 데이터 파일 등을 저장할 수 있을 것입니다.다만, USB와 같은 저장 장치를 사용할 경우 속도나 기능적 측면에서 HDD, SDD에 비해 제약이 따를 것이기 때문에, 속도와 성능을 고려하여 장기적으로 사용할 것이라면 HDD, SDD를 사용하는 것이 좋다고 생각합니다. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?삭제된 파일은 파일 테이블에서 헤더 정보가 지워지거나 비워지면서, 그 파일이 사용한 블록을 free block list로 추가합니다. 즉, 파일의 물리적인 데이터는 여전히 디스크에 남아 있지만, 운영체제는 이 블록들을 빈 공간으로 처리해 새로운 파일이 해당 블록을 사용할 수 있도록 표시합니다. 파일이 삭제되었을 때, 사용된 블록(파일이 저장된 물리적 위치)은 사실상 지워지지 않고 그대로 디스크에 남아 있는 상태입니다. 포렌식은 디스크에서 삭제된 파일이 사용한 블록을 찾아내어 헤더 정보가 없는 데이터를 복구합니다. 삭제된 파일이 사용한 블록이 새로운 데이터로 덮어쓰여지지 않았으면, 이 데이터를 복구할 수 있습니다.자료구조와 알고리즘지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.1. 버블 정렬- 시간 복잡도 : 평균 O(n^2)- 장점 : 구현이 매우 간단합니다.- 단점 : 시간 복잡도가 O(n^2)으로 성능이 낮습니다. 비교 및 교환을 많이 해야 하기 때문에, 큰 데이터셋에서 비효율적입니다.2. 선택 정렬- 시간 복잡도 : 평균 O(n^2)- 장점 : 구현이 간단합니다.- 단점 : 시간 복잡도가 O(n^2)으로 성능이 낮습니다. 비교 및 교환을 많이 해야 하기 때문에, 큰 데이터셋에서 비효율적입니다.3. 삽입 정렬- 시간 복잡도 : 평균 O(n^2)- 장점 : 구현이 간단합니다. - 단점 : 시간 복잡도가 O(n^2)으로 성능이 낮습니다. 비교 및 교환을 많이 해야 하기 때문에, 큰 데이터셋에서 비효율적입니다.4. 병합 정렬- 시간 복잡도 : 평균 O(nlogn)- 장점 : O(nlogn) 시간복잡도로 매우 빠릅니다. - 단점 : 추가적인 메모리 공간이 O(n)만큼 필요합니다.5. 퀵 정렬- 시간 복잡도 : 평균 O(n log n) / 최악 O(n^2)- 장점 : 평균적으로 매우 빠르고, 메모리 사용이 O(log n)로 적습니다.- 단점 : 피벗을 잘못 선택한다면, 최악의 경우 O(n^2)으로 좋지 못한 성능을 보입니다.메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.저라면 타뷸레이션을 사용할 것 같습니다. 메모이제이션은 동적으로 필요한 값만 캐시하고 계산을 추후에 하기 때문에, 재귀와 더 잘 맞물린다고 생각하지만, 재귀가 깊어지면 스택 오버플로우가 발생할 수 있다는 문제점이 있습니다. 또한, 메모이제이션은 메모리의 불필요한 사용이 있을 수 있기 때문에 메모리가 부족한 상황에서는 안정적인 메모리 사용이 가능한 타뷸레이션이 더 합리적인 선택이라고 생각합니다.

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

3주차 학습내용운영체제가상메모리가상 메모리를 사용하면 프로세스는 운영체제 영역이 어디 있는지, 물리 메모리의 크기가 얼마나 큰지 몰라도 됨프로그래머는 물리 메모리의 크기와 프로세스가 메모리의 어느 위치에 올라가는지 신경 쓰지 않고 0x0번지에서 시작된다고 생각하고 프로그래밍프로세스는 메모리 관리자를 통해 메모리에 접근 -> 물리 메모리에 직접 접근할 일이 없고 메모리 관리자(MMU)에게 요청만 하면 됨메모리 관리자는 물리 메모리와 스왑 영역을 합쳐 프로세스가 사용하는 가상 주소를 물리 주소로 변환 => 동적 주소 변환(Dynamic Address Translation)물리 메모리 내용의 일부를 하드 디스크의 스왑 영역으로 옮긴 뒤 처리가 필요할 때 물리 메모리로 가져와 실행세그멘테이션(배치정책)가변분할 방식으로, 프로세스의 메모리를 다양한 크기의 논리적 단위인 세그먼트로 나누어 관리하는 메모리 관리 전략Base Address와 Bound Address정보가 담긴 세그멘테이션 테이블을 가지고 있어 이를 통해 물리 메모리 주소를 계산Base Address: 세그먼트가 물리 메모리 내에서 시작하는 위치Bound Address: 세그먼트 크기논리 주소를 MMU에 전달 => MMU는 이 논리주소가 몇 번 세그먼트 인지 알아냄 => MMU 내의 Segment Table Base Register를 이용해 물리 메모리 내에 있는 세그먼트 테이블을 찾음 => 세그먼트 테이블 내 세그먼트 번호를 인덱스로 Base Address와 Bound Address를 찾음MMU는 논리주소와 Bound Address의 크기를 비교논리주소 논리주소 > Bound Address : 메모리 침범으로 간주하고 에러 발생장점메모리를 가변적으로 분할 가능코드, 데이터, 스택, 힙 영역을 모듈로 처리할 수 있어 메모리 보호 및 공유 기능 향상단점외부 단편화 발생페이징(배치정책)고정 분할 방식으로, 물리 메모리를 고정 크기의 블록(페이지 프레임)으로 나누고, 프로세스의 가상 메모리 역시 같은 크기의 페이지로 분할하여, 각 가상 페이지를 필요에 따라 물리 메모리의 페이지 프레임에 동적으로 매핑하는 방식페이지 : 논리 주소 공간에서 같은 크기로 나눈 블록프레임 : 물리 주소 공간에서 같은 크기로 나눈 블록CPU가 논리 주소를 전달 => MMU는 그 주소에 해당하는 페이지와 오프셋을 알아냄 => MMU 내의 PTBR(Page Table Base Register)를 이용해 물리 메모리에 있는 페이지 테이블을 찾음 => 페이지 번호를 인덱스로 해 프레임 번호를 알아낸 뒤 오프셋을 이용해 물리주소로 변환페이지 넘버 = 논리주소 / 페이지 크기오프셋 = 논리주소 % 페이지 크기물리주소 = 프레임값 + 오프셋장점외부 단편화 문제 해결논리 메모리는 물리 메모리에 저장될 때 연속되어 저장될 필요 없음단점내부 단편화 발생페이지 테이블의 크기를 적절히 유지해야 함페이지드 세그멘테이션(배치정책)메모리 관리의 두 가지 기본 접근 방식인 세그멘테이션과 페이징의 장점을 결합한 메모리 관리 전략프로그램의 메모리 공간을 논리적인 단위인 세그먼트로 나눈 다음, 각 세그먼트를 다시 고정 크기의 페이지로 분할하여 관리하는 방식메모리 접근 권한code 영역: 읽기, 실행data 영역: 읽기, (쓰기)heap 영역: 읽기, 쓰기stack: 읽기, 쓰기가상 주소에서 물리 주소로 변환될 때마다 메모리 접근 권한에 대한 검사 => 권한 위반 시 에러 발생시킴가상 주소가 들어오면 몇 번 세그먼트인지 알아냄 => 물리 메모리에 있는 페이지 테이블 찾음 => 그먼트 번호에 따라 인덱스를 참조하여 먼저 해당 세그먼트가 메모리 접근 권한을 위반하는지 검사 => 접근 권한 위반시 프로세스를 종료, 접근 권한에 부합할시 페이지 넘버와 페이지 개수를 가져옴 => 페이지 테이블에서 페이지 넘버에 따라 인덱스를 참조하여 프레임 알아냄장점각각의 세그먼트는 논리적 영역별로 나누어 독립적으로 관리 가능메모리를 효율적으로 관리단점물리 메모리에 접근하기 위해 메모리에 두 번 접근해야 디맨드 페이징(가져오기 정책)프로그램 실행 시 모든 코드와 데이터를 메모리에 적재하는 것이 아닌, 필요로 하는 데이터만을 메모리로 가져오고 쓰이지 않을 것 같은 데이터는 스왑 영역으로 이동 시키는 방식지역성 이론goto문을 사용하지 않는 이유가 되는 이론공간의 지역성 : 현재 위치와 가까운 데이터에 접근할 확률이 높다.시간의 지역성 : 최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높다.지역성 이론에 따라 조만간 쓰일 데이터만 메모리에 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑 영역으로 보내 성능 향상메모리 계층 구조레지스터: CPU 1 사이클캐시(L1, L2): CPU n~nn사이클메인 메모리: CPU nnn사이클보조 저장 장치: CPU nnnnnnn사이클메모리에 접근하는 시간은 보조 저장 장치로 갈수록 느려짐디맨드 페이징은 스왑 영역을 보조 저장 장치에 저장하는데, 성능 향상을 위해서는 스왑 영역으로 데이터 이동시키는 것을 최소화해야 함가상 메모리 크기 = 메인메모리 + 스왑 영역스왑 인 : 스왑 영역에서 물리 메모리로 데이터 가져오는 것스왑 아웃 : 물리 메모리에서 스왑영역으로 데이터 내보내는 것PTE : 페이지 테이블 엔트리, 페이지 테이블을 이루는 한 행페이지 교체정책 page fault가 생겼고, 현재 메모리가 가득 차있을 때 메모리에서 스왑 영역으로 페이지를 넣고 가져와야 하는데, 이 과정에서 어떤 페이지를 스왑영역으로 옮길지를 결정하는 것random무작위로 페이지를 선택해 교체하는 방식지역성을 고려하지 않아 성능이 좋지 않음FIFO(First In First Out)메모리에 가장 먼저 적재된 페이지를 선택해 교체하는 방식하드웨어적으로 접근비트를 지원하지 않는 시스템에서 사용장점구현이 간단함단점자주 사용되는 페이지도 교체되므로 낮은 성능Optimum앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택해 교체하는 방식가장 오랫동안 쓰이지 않을 페이지를 알 수 없으므로 이론적으로만 존재하는 방식이며 다른 정책과 성능을 비교하기 위한 참조용으로만 쓰임LRU(Least Recently Used)최근 가장 사용이 적은 페이지를 선택해 교체하는 방식지역성 이론의 시간 지역성에 따른 방식장점FIFO에 비해 효율적단점프로그램이 지역성을 띄지 않을 때 성능 저하시간을 기록하기 위한 많은 bit 필요하며 시간이 오래되면 오버플로우 발생접근 시간을 기록하기 위한 추가적 메커니즘 필요Clock AlgorithmLRU와 비슷모든 페이지에 접근 비트를 하나만 사용하여 일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화하며 페이지가 참조될 때 접근 비트를 1로 설정, 클락 핸드가 시계방향으로 페이지들을 순환하며 사용 비트가 0인 페이지를 선택해 교체하는 방식Enhanced Clock Algorithm접근 비트와 변경 비트를 동시에 두고 교체할 페이지를 선택하는 방식교체 1순위: 접근 비트 0 / 변경 비트 0교체 2순위: 접근 비트 0 / 변경 비트 1교체 3순위: 접근 비트 1 / 변경 비트 0교체 4순위: 접근 비트 1 / 변경 비트 12차 기회 페이지 교체 알고리즘하드웨어적으로 접근비트를 지원하지 않는 시스템에서 사용되어야 하는 FIFO의 단점이었던 자주 사용되는 페이지의 교체 문제를 개선한 방식먼저 들어왔지만 Page Fault 없이 페이지 접근에 성공한 경우 자주 사용되는 페이지이므로 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시키는 알고리즘성능 : FIFO 스레싱운영체제는 CPU사용량을 늘리려 함 => 사용량을 늘리려고 멀티프로그래밍 정도를 늘리려고 하는데 무작정 늘려버리면 오히려 스왑작업이 많아져서 사용량이 줄어들게 됨 => 해당 상황이 스레싱원인 : 물리메모리의 크기가 작은 것해결 방법메모리 크기 증가프로세스에 적절한 페이지의 수 할당 한 프로세스에 많은 페이지 할당시 다른 프로세스의 페이지가 줄어들어 낮은 효율한 프로세스에 적은 페이지 할당시 빈번한 Page Fault 발생으로 스래싱 발생프로세스에 맞게 유지할 페이지 결정워킹셋 : 현재 사용중인 페이지들은 자주 사용될 확률이 높기 때문에 이를 통째로 메모리에 올리는 것주변장치(I/O 디바이스, 저장장치)그래픽 카드, 하드디스크, SSD, 키보드, 마우스 등주변 장치 분류캐릭터 디바이스데이터 전송단위가 character로, 상대적으로 크기가 작다.마우스, 키보드, 사운드카드, 직렬/병렬 포트 블록 디바이스데이터 전송단위가 block으로, 상대적으로 크기가 작다.하드디스크, SSD, 그래픽카드 등입출력 버스 구조초기 : 버스 하나에 주변 장치를 모두 연결CPU가 작업을 진행하다가 입출력 명령을 만나면 직접 입출력장치에서 데이터를 가져오는 폴링 방식 이용 => CPU 사용률이 낮아짐현재 : 입출력 제어기(I/O Controller)와 여러개의 버스 추가CPU는 I/O 작업 발생 시 입출력 제어기에 이를 맡기고 다른 작업 진행메모리가 입출력 제어기에 직접 연결하기 위해 DMA(Direct Memory Access)를 추가하고 사용하는데 이를 Memory Mapped I/O라고 부름마우스/키보드광학 마우스 작동 원리마우스 밑면에 작은 카메라 탑재, 초당 1500회가 넘는 사진을 찍어 디바이스 컨트롤러 내 DSP로 보냄DSP는 사진을 분석해 마우스의 x축 좌표와 y축 좌표 움직임 분석디바이스 컨트롤러는 CPU에게 인터럽트를 보내고 마우스 드라이버가 동작해 데이터 읽음마우스 드라이버는 운영체제에게 이벤트 신호를 보내고 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달해당 애플리케이션은 받은 마우스 이벤트 처리, 해당 동작 수행키보드 작동 원리사용자가 키 입력디바이스 컨트롤러가 어떤 키를 입력 받았는지 알아냄CPU에게 인터럽트 보냄키보드 드라이버는 운영체제에 이벤트를 보내고 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달해당 애플리케이션은 받은 키보드 이벤트 처리, 해당 동작 수행 하드디스크/Flash Memory(SSD)블록 디바이스의 한 종류하드 디스크 구조spindle이라고 하는 막대가 있고 그곳에는 platter라는 원판들이 붙어 있음. disk arm이 platter의 값을 읽음. platter > track > sector구조하드 디스크 작동 원리유저 프로세스가 하드디스크의 특정 섹터에 접근 요청(실린더 C로 가서 트랙 B에 있는 섹터 D를 읽어라)seek: 디스크암은 헤드를 실린더 C로 이동.seek Time: 헤드를 실린더로 이동시키는 시간으로, 하드디스크가 느린 이유트랙 B의 섹터D가 헤드에 닿을때까지 스핀들 회전헤드에 섹터D가 읽히면 작업 종료단점속도 느리고 소음 발생자석을 대면 데이터 손상 충격에 약함Flash Memory장점전기적으로 데이터를 읽어 속도가 빠르고 조용하다 자석을 대도 데이터 보존 충격에 강함단점특정 부분에 데이터를 쓴 경우 덮어쓰기 불가 및 데이터 삭제 횟수가 정해져있어 같은 부분에 데이터 삽입과 삭제를 반복할 경우 망가져 사용 불가 파일과 파일시스템파일들은 하드디스크나 SSD같은 저장 장치에 저장되는데, 사용자가 직접 저장하면 손상시킬 수 있어 운영체제가 안전하게 저장파일 시스템 기능파일과 디렉토리 생성파일과 디렉토리 수정/삭제파일 권한 관리무결성 보장백업과 복구암호화파일 제어 블록 = 파일 디스크립터모든 파일마다 있고 오픈되면 메모리로 이동운영체제가 관리하고 사용자는 접근할 수 없음파일의 분류순차파일구조카세트테이프들어온 순서대로 작동하기에 공간의 낭비가 없고 구조가 단순특정지점으로 바로 이동이 어려움직접파일구조해시 함수를 통해 저장 위치를 정하는 방식(json도 이 방식 사용)데이터 접근이 매우 빠름해시함수를 잘 골라야 하며 저장공간이 낭비될 수 있음인덱스 파일구조앞선 두 가지 방식을 합친 것노래 재생목록디렉토리파일과 다른 디렉토리를 포함할 수 있는 컨테이너파일을 주제나 유형별로 그룹화하여 조직화할 수 있음디렉토리도 하나의 파일로, 파일이 데이터를 저장한다면 디렉토리는 파일 정보를 저장디렉토리 구조계층적 구조 : 최상위에 루트 디렉토리(/) 존재초기 : 루트 디렉토리에만 디렉토리가 존재할 수 있고 다른 디렉토리에서는 하위 디렉토리를 만들 수 없는 구조현재 : 다단계 디렉토리 구조로, 모든 디렉토리가 하위 디렉토리를 만들 수 있는 트리구조파일과 디스크디스크는 블록(1~8kB)으로 나뉘어있음. 파일시스템은 파일정보를 파일 테이블로 관리하고, 파일이 시작하는 블록 위치 정보도 기록되어있음.파일 할당 방식연속 할당블록들을 디스크에 연속적으로 저장하는 방식시작블록만 알면 나머지도 알 수 있으나 내부단편화가 발생 -> 그래서 사용하지 않음불연속 할당디스크의 비어있는 공간에 집어넣고 파일시스템이 두가지 방식으로 관리연결 할당파일에 속한 데이터를 연결리스트로 관리파일 테이블에는 시작 블록에 대한 정보만 저장하고 다른 블록은 연결리스트를 통해 접근인덱스 할당(i-node 방식)파일 테이블의 블록 포인터가 데이터 블록에 직접 연결하는것이 아닌, 데이터들의 인덱스를 가지고 있는 인덱스 블록에 연결데이터가 많아 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어 연결하기 때문에 테이블 확장 가능파일 크기가 작다면 데이터를 바로 참조하는 블록 포인터 이용, 파일 크기가 크다면 간접 포인터를 이용해 많은 데이터에 접근 가능디스크를 구성하는 블록의 크기가 너무 작으면 공간 낭비는 줄지만 관리해야 할 블록의 수가 많아지고, 블록의 크기가 너무 크면 관리해야하는 블록의 수는 적지만 내부단편화로 낭비되는 공간이 많아짐빈공간을 찾을 때 항상 모든 공간을 찾는것보다는 빈공간 리스트를 만들고 삭제한 후에 리스트에 빈 공간의 주소를 추가하는 방식이 좋음알고리즘정렬 - 삽입정렬장점 : 간단한 이해와 구현단점 : 낮은 성능A = [34, 58, 13, 94, 29] # 이미 정렬된 부분이라고 가정하는 0번째 요소를 제외한 나머지 부분 순회 for i in range(1, len(A)): # 이미 정렬된 부분(0번째~i-1번째)에서 자리 찾기 # 뒤에서부터 훑으면서 큰 원소들을 만날 때마다 교환 for j in range(i-1, 0, -1): if A[j+1] > A[j]: break A[j], A[j+1] = A[j+1], A[j]정렬 - 병합정렬정렬해야 할 것을 아주 잘게 나눈 다음 정렬하고 병합하는 것을 반복하는 정렬 방법장점 : O(nlogn)의 좋은 성능단점 : 이해와 구현 어려움, 시스템의 스택 크기가 큰 데이터를 정렬할 때 제한적def merge_sort(unsorted_list): # 리스트를 더 이상 나눌 수 없으면 해당 리스트를 그대로 리턴 if len(unsorted_list) left[left_idx]: merged.append(left[left_idx]) left_idx += 1 # 현재 가리키고 있는 오른쪽 값이 왼쪽 값보다 작으면 왼쪽 값을 병합리스트에 추가하고, 왼쪽 인덱스에 1 더하기 else: merged.append(right[right_idx]) right_idx += 1 # 왼쪽 리스트에 남은 값이 있으면 병합 리스트에 추가 while (left_idx 정렬 - 퀵정렬배열의 값 중 한가지를 피벗으로 설정 (피벗 설정 방법은 여러가지)맨 왼쪽, 맨 오른쪽, 양쪽 이동 값을 만든다장점 : O(nlogn)의 좋은 성능단점 : 이해와 구현 어려움, 최악의 경우 시간복잡도가 O(n^2)A = [34, 58, 13, 94, 29] def quick_sort(low, high): if low 동적 프로그래밍 - 메모이제이션계산 결과를 저장해서 여러번 계산하지 않도록 하는 기법계산 결과를 해시 테이블에 저장하고 재사용해 속도가 빠르다 .하향식 계산 방식으로 문제를 해결동적 프로그래밍 - 타뷸레이션계산에 필요한 모든 값을 전부 계산 후 테이블에 저장하는 기법상향식 계산 방식으로 문제를 해결회고3주간의 워밍업클럽 2기가 마무리되었다. 끝나고 회고를 작성하면서 드는 생각은 이것저것 챙기려고 하다보니, 3주간 약간은 쫓기면서 수업을 수강하진 않았는가 하는 아쉬움도 들고, 그럼에도 혼자 수강했다면 절대 완강하지 못했을 거란 생각이 들어서 참여하길 잘했다고 생각한다!알고리즘 공부는 개인적으로도 필요성을 많이 느껴서 블로그에 정리도 해보고, 따로 이런저런 글도 많이 읽어서 익숙했는데 운영체제는 사실 예전에 CS 면접 준비를 위해 잠깐 슥 겉핥기로 훑어본게 전부였고, 그때도 제대로 이해하진 못해서 좀 걱정되는 부분도 있었다. 다행히 친절한 난이도의 강의와 설명 덕분에 큰 무리없이 강의를 수강할 수 있었다. 기회가 된다면 다시 강의를 한바퀴 돌리면서 좀 더 개념을 확실히 익히고 추가적으로 궁금한 점이 생기는 부분을 더 깊게 파고들어보고 싶다. 일단은 기초 개념을 잡았다는 것에 만족:-)이제 워밍업 클럽은 끝났지만, 이걸로 공부를 완전히 끝내서는 당연히 안될 것이다. 인프런에 올린 발자국의 배운 내용 요약은 내가 강의를 들으면서 휘갈겼던(..) 노트를 그대로 옮긴거라, 추후엔 내 블로그에 이해한 내용을 나만의 방식으로 정리한 것과 강의를 들으면서 생겼던 의문, 그리고 그 의문에 대한 답 등등..을 정리하며 추가적으로 공부할 예정이다. (제발 하길...)워밍업 클럽 2기 안녕👋

[인프런 워밍업클럽 CS 2기] 2주차 미션📒

운영체제1. FIFO 스케줄링의 장단점이 뭔가요?FIFO 알고리즘은 단순하게 프로세스가 큐에 들어온 순서대로 CPU를 할당받기 때문에, 알고리즘이 단순하고 직관적이라는 장점이 있습니다.다만, 먼저 들어온 프로세스가 완전히 끝나야만 다음 프로세스가 실행되기 때문에, 실행 시간이 짧고 늦게 도착한 프로세스가 실행 시간이 길고 빨리 도착한 프로세스의 작업을 한참 다려야해서 비효율적입니다. 또한 I/O 작업이 들어오면 CPU는 해당 I/O 작업이 끝날 때까지 쉬고 있게 되기 때문에 CPU 사용률이 떨어진다는 단점이 있습니다. 2. SJF를 사용하기 여러운 이유가 뭔가요?SJF는 Shortest Job First로, Burst Time이 짧은 프로세스를 먼저 실행시키는 알고리즘입니다. 만약 그러한 알고리즘을 사용한다면, 어떤 프로세스가 얼마나 오래동안 실행될지 예측이 어렵고, Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수 있기 때문에 사용하기 어렵습니다. 3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?RR는 Round Robin으로, 특정한 타임 슬라이스만큼 프로세스에게 CPU를 할당했다가, 해당 시간이 지나면 다른 프로세스에게 CPU를 할당하는 방식으로 동작하는 알고리즘입니다. 만약 RR 스케줄링에서 타임 슬라이스가 아주 작으면 그 짧은 시간마다 계속해서 실행되던 프로세스에게서 CPU를 뺏어서 다른 프로세스에게 CPU를 할당해야하고, 그만큼 컨텍스트 스위칭이 자주 일어나게 됩니다. 결국 프로세스의 처리량보다 컨텍스트 스위칭을 처리하는 비용이 더 커져서 오버헤드가 커집니다. 4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?MLFQ는 Multi Level Feedback Queue로, 우선순위 큐를 여러개 두어 우선순위가 높으면 타임 슬라이스 크기가 작고, 우선순위가 낮으면 타임 슬라이스 크기가 커지는 방식의 알고리즘입니다. 기본적으로 CPU Bound Process에게는 타임 슬라이스를 크게 주고, I/O Bound Process에게는 타임 슬라이스를 작게 줍니다. 이때, CPU를 사용하는 프로세스가 스스로 CPU를 반납하면 I/O Bound Process일 확률이 높고, 실행 도중에 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황이 발생하면 CPU Bound Process일 확률이 높으므로 이를 이용해 두 프로세스를 구분합니다. 5. 공유자원이란무엇인가요?공유자원이란 프로세스가 통신할 때 공동으로 이용하는 변수, 파일 등으로 한 마디로 여러 프로세스가 함께 공유하고 있는 자원을 의미합니다.공유자원은 각 프로세스의 접근 순서에 따라 결과가 달라지는데, 시분할 처리로 인해 어떤 프로세스가 먼저 실행되고 나중에 실행되는지 예측하기 어려워 연산 결과를 예측하기 힘듭니다. 6. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?교착 상태에 빠질 수 있는 조건으로는 상호배제, 비선점, 점유와 대기, 원형 대기의 4가지가 있습니다. 이 중 하나라도 만족하지 못하면 교착상태는 발생하지 않습니다.상호배제 - 어떤 프로세스가 한 프로세스를 점유하면, 그 리소스는 다른 프로세스에게 공유되면 안됩니다.비선점 - 프로세스 A가 리소스를 점유하고 있으면 다른 프로세스는 그 리소스를 뺏을 수 없습니다.점유와 대기 - 어떤 프로세스가 리소스A를 갖고 있는 상태에서 다른 리소스B를 원하고 있는 상황이어야 합니다.원형 대기 - 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있어야 합니다.자료구조와 알고리즘1. 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?기저조건을 만들지 않거나 잘못 설정하면 무한히 재귀함수가 호출되어 콜스택 메모리 공간이 가득 차게 되고, 자동으로 종료되는 등 예기치 못하게 프로그램이 동작할 수 있습니다. 2. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ if (n

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

2주차 학습 내용운영체제CPU 스케줄링 알고리즘 - SJF(Shortest Job First)Burst Time이 짧은 프로세스를 먼저 실행하는 알고리즘이론적으론 FIFO보다 성능이 좋지만, 구현에 문제가 발생할 수 있음어떤 프로세스가 얼마나 실행될지 예측 어려움Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수도 있음CPU 스케줄링 알고리즘 - Round Robin한 프로세스에게 일정 시간만큼 CPU를 할당하고, 할당 시간이 지나면 강제로 다른 프로세스에게 일정 시만큼 CPU를 할당하는 알고리즘프로세스에게 할당하는 일정 시간 => 타임 슬라이스, 타임 퀀텀타임 슬라이스의 값에 따라 RR 알고리즘의 성능이 크게 바뀜타임 슬라이스가 큰 경우(무한대라고 가정)먼저 들어온 프로세스의 작업이 종료될 때까지 실행 => FIFO 알고리즘이 됨타임 슬라이스가 작은 경우(1ms라고 가정)컨텍스트 스위칭이 너무 자주 일어남프로세스 처리량보다 컨텍스트 스위칭을 처리하는 양이 더 커짐 => 오버헤드가 너무 큼최적의 타임 슬라이스 : 사용자가 느끼기에 여러 프로세스가 버벅거리지 않고, 동시에 실행되는 것처럼 느껴지면서 오버헤드가 너무 크지 않는 값Windows는 20ms, Unix는 100ms 정도 CPU 스케줄링 알고리즘 - MLFQ(Multi Level Feedback Queue)오늘날 운영체제에서 가장 일반적으로 쓰이는 CPU 스케줄링 기법기본적으로 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임 슬라이스를 선택하되, CPU Bound Process들에게는 타임 슬라이스를 크게 줌CPU를 사용하는 프로세스가 스스로 CPU를 반납하면 I/O Bound Process일 확률이 높고, 실행 도중 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황이 발생하면 CPU Bound Process일 확률이 높음우선순위 큐를 여러 개 준비하여, 우선순위가 높으면 타임 슬라이스 크기가 작고, 우선순위가 낮으면 타임 슬라이스 크기가 커짐처음엔 타임 슬라이스가 작게 할당되어있다가, CPU가 강제로 뺏기면 좀 더 큰 타임 슬라이스를 할당받게 됨프로세스 간 통신프로세스는 독립적으로 실행되기도 하지만, 다른 프로세스와 데이터를 주고받으며 통신을 하는 경우도 있음한 컴퓨터 내에서 프로세스 간 통신하는 방법파일을 이용하는 방법통신하려는 프로세스들이 하나의 파일을 이용해 읽고 쓰는 방법파이프를 이용하는 방법운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰는 방법한 프로세스 내에서 쓰레드 간 통신하는 방법데이터 영역의 전역 변수나 힙을 이용해 통신네트워크를 이용한 방법운영체제가 제공하는 소켓통신이나 다른 컴퓨터에 있는 함수를 호출하는 RPC(원격 프로시저 호출)를 이용해 통신공유자원과 임계구역공유자원프로세스가 통신할 때 공동으로 이용하는 변수, 파일 등여러 프로세스가 공유하고 있기 때문에 각 프로세스의 접근 순서에 따라 결과가 달라질 수 있음임계 구역(Critical Section)여러 프로세스가 동시에 사용하면 안되는 영역경쟁 조건(Race Condition) : 공유 자원을 서로 사용하기 위해 경쟁하는 것임계 구역 문제를 해결하기 위한 조건상호 배제(Mutual Exclusion) 메커니즘 필요임계 구역엔 주어진 시간에 항상 하나의 프로세스만 접근할 수 있어야 한다동시에 여러 개의 요청이 있더라도 하나의 프로세스의 접근만 허용한다.임계 구역에 들어간 프로세스는 빠르게 나와야 한다.세마포어프로세스들은 대기 큐에서 공유 자원을 사용하기 위해 대기하고, 운영 체제가 관리하는 열쇠를 가진 프로세스만 공유 자원을 사용할 수 있음 => 이때 이 열쇠를 세마포어(정수형 변수)라고 함공유 자원의 개수에 따라 세마포어의 값 또한 달라짐wait() : 열쇠를 요청해서 열쇠를 받고 문을 잠금. 열쇠가 없으면 기다림signal() : 방에서 나와 문지키는 직원에게 열쇠 반납단점 : wait() 함수, signal() 함수의 순서를 이상하게 호출해서 세마포어를 잘 못 사용할 가능성이 있음 => 모니터로 해결!모니터운영체제가 처리하는 것이 아닌, 프로그래밍 언어 차원에서 지원하는 방법Java에서 synchronized라는 키워드가 붙으면, 이 키워드가 붙은 함수들은 동시에 여러 프로세스에서 실행시킬 수 없음 = 상호배제가 완벽하게 이루어짐만약 프로세스 A에서 increase() 함수를 실행하면, 프로세스 B는 synchronized 키워드가 붙은 decrease() 함수도 실행할 수 없음교착상태(데드락)여러 프로세스가 서로 다른 프로세스의 작업이 끝나길 기다리다가 아무도 작업을 진행하지 못하는 상태교착상태의 필요 조건 (한가지라도 충족하지 않으면 교착상태 발생 X)상호배제 : 어떤 프로세스가 한 리소스를 점유했다면, 그 리소스는 다른 프로세스에게 공유되면 안됨 비선점 : 프로세스 A가 리소스를 점유하고 있는데 프로세스 B가 리소스를 빼앗을 수 없어야 함 점유와 대기 : 어떤 프로세스가 리소스A를 가지고 있는 상태에서 리소스 B를 원하는 상태여야 함 원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있어야 함 교착 상태의 네가지 조건을 이용해서 교착상태를 예방하는 방법을 연구해보고자 했으나, 제약이 많고 비효율적이라 해결하는 방법을 연구함교착상태 회피(Deadlock avoidance)프로세스들에게 자원을 할당할 때 어느정도 자원을 할당해야 교착상태가 발생하는지 파악해서 교착상태가 발생하지 않는 수준의 자원 할당을 함전체 자원의 수와 할당된 자원의 수를 기준으로 안정 상태, 불안정 상태로 나눔운영체제는 최대한 안정 상태를 유지하려고 자원할당 함불안정 상태에 있더라도 무조건 교착 상태에 빠지는 것이 아닌, 교착 상태에 빠질 확률이 높아짐운영체제에서 은행원 알고리즘 구현하기안정상태은행원 알고리즘은 각 프로세스가 현재 요구할 수 있는 요청이 예상되는 자원을 구함 P1에서 4개를 요청하면 현재 사용 가능 자원이 2개뿐이므로 거절P2에서 2개를 요청하면 2개 모두 P2에 할당, P2는 작업을 마치고 6개를 반납사용 가능한 자원이 6개가 되어, P1, P3 모두에 필요한 만큼 할당 가능불안정 상태사용 가능한 자원이 1개현재 사용 가능한 자원 개수로는 P1, P2, P3가 요청할 수 있는 최대 요청인 2개를 충족하지 못함 => 불안정 상태모든 프로세스가 최대 자원을 요청하지 않는다면 교착 상태에 빠지지 않을 수도 있지만, 불안정상태에 빠지지 않도록 유지하는게 좋음교착상태의 검출 방식가벼운 교착 상태 검출프로세스가 일정 시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주해결 방법 : 일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착 상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백무거운 교착 상태 검출자원 할당 그래프 이용현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착 상태가 발생했다면 해결그래프에 순환 구조가 생긴다면 교착 상태가 생긴 그래프교착 상태를 검출하면 교착 상태를 일으킨 프로세스를 강제 종료시키고, 다시 실행시킬 때 체크포인트로 롤백단점 : 운영체제가 지속적으로 자원할당그래프를 유지하고 검사해야하므로 오버헤드가 발생장점 : 가벼운 교착상태에서 발생하는 억울하게 종료되는 프로세스는 발생하지 않음메모리 종류레지스터가장 빠른 기억장소, CPU 내에 존재휘발성 메모리 - 컴퓨터의 전원이 꺼지면 데이터가 사라짐CPU를 구분할 때 말하는 32bit, 64bit는 레지스터의 크기를 말함CPU는 계산을 할 때, 메인메모리에 있는 값을 레지스터로 가져와 계산하고, 결과는 메인메모리에 저장캐시휘발성 메모리레지스터는 굉장히 빠르고, 메인메모리는 너무 느림 => 메인 메모리에 있는 값을 레지스터로 옮기려면 한참 걸리므로 필요할 것 같은 데이터를 미리 가져와서 캐시에 저장성능의 이유로 여러개를 둠메인메모리(RAM)실제 운영체제와 다른 프로세스들이 올라가는 공간전원이 공급되지 않으면 데이터가 지워지므로 휘발성 메모리하드디스크나 SSD보다 속도는 빠르지만, 가격이 비싸므로 데이터를 저장하기 보다는 실행 중인 프로그램만 올림 보조저장장치(HDD, SSD)사무용 프로그램, 게임, 작업한 파일 등을 저장할 필요가 있는데, 비싸고, 휘발성인 메모리에 저장할 순 없음가격이 저렴하고 전원이 공급되지 않아도 데이터가 지워지지 않는 비휘발성 메모리를 만듦 메인메모리오늘날의 컴퓨터 구조인 폰 노이만 구조는 모든 프로그램을 메모리에 올려 실행시킴운영체제는 메모리를 관리하기 위해 1바이트 크기로 구역을 나누고 숫자를 매김 => 이 숫자는 "주소"라고 부름물리 주소와 논리 주소물리 주소 : 메모리를 컴퓨터에 연결하면 0x0번지부터 시작하는 주소 공간논리 주소 : 사용자 관점에서 바라본 주소 공간사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근할 수 있음경계 레지스터메모리에는 수많은 프로세스가 올라오는데, 운영체제를 위한 공간은 따로 마련해둠. 이때,하드웨어적으로 운영체제 공간과 사용자 공간을 나누는 경계 레지스터를 만듦메모리 할당 방식유니 프로그래밍메모리 오버레이유니프로그램 방식에서 메모리보다 더 큰 프로그램을 실행시키는 방법큰 프로그램을 메모리에 올릴 수 있도록 잘라서 당장 실행시켜야 할 부분만 메모리에 올리고 나머지는 용량이 큰 하드디스크의 스왑 영역에 저장하는 기법멀티프로그래밍가변 분할 방식(세그멘테이션)프로세스의 크기에 따라 메모리를 나누는 방식장점 : 내부 단편화 없음단점 : 외부 단편화 발생고정 분할 방식(페이징)프로세스의 크기와 상관 없이 메모리를 정해진 크기로 나누는 방식 장점 : 구현이 간단하며 오버헤드가 적음단점 : 작은 프로세스도 큰 영역에 할당돼서 공간이 낭비되는 내부 단편화 발생버디 시스템오늘날 가변 분할 방식과 고정 분할 방식을 혼합하여 단점을 줄인 방식2의 승수로 메모리를 분할해 메모리를 할당하는 방식가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라지고, 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단함고정 분할 방식처럼 내부 단편화가 발생하긴 하지만 많은 낭비가 발생하진 않음알고리즘재귀(recursion)어떠한 것을 정의할 때 자기 자신을 참조하는 것재귀 함수탈출 조건이 없으면 콜스택이라는 메모리 공간이 가득차서 자동으로 종료언제 종료될지 예측할 수 있게 하기 위해 탈출 조건, 즉 기저 조건이 반드시 필콜스택함수가 호출되면서 올라가는 메모리 영역, 스택이라고도 부름FILO(먼저 들어온 데이터가 나중에 나감) 특성을 가짐함수를 호출하면 함수는 콜스택에 올라가고, 종료되면 콜스택에서 제거됨버블 정렬(Bubble Sort)앞에 있는 숫자와 뒤에 있는 숫자를 비교해서 자리를 바꾸는 알고리즘데이터를 옆 데이터와 비교하면서 자리를 바꾸는게 버블이 일어나는 것 같아서 붙여진 이름시간복잡도 : O(n^2)장점 : 이해와 구현이 쉽다단점 : 성능이 좋지 않다.function BubbleSort(arr){ for(let i = 0; i arr[j + 1]){ let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }선택 정렬 (Sellection Sort)배열의 정렬되지 않은 영역을 순회하며 가장 작은 값을 탐색 후 교체하는 방법시간복잡도 : O(n^2)장점 : 이해와 구현이 쉽다단점 : 성능이 좋지 않다function SelectionSort(arr){ for(let i = 0; i 회고칭찬하고 싶은 점이번 주부터 알고리즘 스터디를 시작하고, 또 매일 출근도 하면서 오늘 있었던 코딩테스트까지 일주일 간 이것저것 할일이 많았는데 포기하지 않고 이번주차 진도를 따라잡았다. CS 중에서도 운영체제는 개념이 잘 잡혀있지 않았는데, 공부를 하면서 운영체제에서 가장 중요한 개념인 프로세스와 CPU 스케줄링에 대해 어느정도 개념을 이해할 수 있는 일주일이었다.아쉬웠던 점이번주에도 역시나 매일매일 정해진 분량을 학습하기보다는 시간이 남는 타임에 몰아들은 경우가 더 많았던 것 같다.보완해야할 점남은 일주일도 바쁠 예정이기 때문에..현실적으로 매일매일 정해진 분량을 지켜서 노트까지 정리해가며 학습하기엔 벅차더라도, 지난 주처럼 너무 한번에 몰아서 하지 말고 출퇴근 시간을 이용해서 강의를 가볍게 보고 추후에 다시 복습하는 개념으로 노트를 정리하면 좋을 것 같다.

[인프런 워밍업클럽 CS 2기] 1주차 미션📒

운영체제 1. while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 } 위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요? 폴링 방식의 성능 문제를 해결하기 위해서는 인터럽트를 사용할 수 있습니다. 인터럽트란, CPU가 주기적으로 실행이 완료되었는지 상태를 체크하는 대신, 그 시간에 다른 작업을 수행할 수 있도록 하는 메커니즘입니다. 즉, CPU가 계속해서 상태를 확인하지 않아도 특정 조건이 충족되면 원래의 작업을 즉시 처리할 수 있게 하는 알림 같은 개념이다.코드 수정해보기스킬 사용 여부를 계속 체크하는 대신, 다른 작업을 수행하면서도 플레이어가 스킬을 사용했을 때를 감지해서 특정한 반응이 일어날 수 있도록 코드를 수정했습니다.void onSkillActivated() { // 스킬이 활성화 되면 실행되는 코드 activateSkill(); } int main() { // 스킬 사용 이벤트에 인터럽트 핸들러 등록 registerInterruptHandler("SkillActivated", onSkillActivated); while (true) { // 기타 게임 로직 처리 } return 0; } 2. 프로그램과 프로세스가 어떻게 다른가요?프로그램은 코드, 즉 명령어의 집합으로 .exe와 같은 파일 형태로 존재합니다. 실행되지 않으면 CPU, 메모리 등의 시스템 자원을 사용할 수 없습니다. 이제 이러한 프로그램을 더블 클릭 등으로 실행을 시키면 메모리에 적재되어 CPU에서 실제로 실행되고, 바로 그것을 프로세스라고 부릅니다. 프로세스는 실행 중일 때 시스템 자원을 사용합니다. 또한 준비 상태, 실행 상태, 대기 상태 등 다양한 상태를 가집니다.한 마디로 프로그램은 실행 중이 아닌 상태의 코드이고, 프로세스는 실행 중인 상태의 프로그램입니다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍은 메모리 상에 여러 프로세스가 존재하고, CPU가 이 프로세스들을 번갈아 가며 실행하는 방식입니다. 멀티프로세싱은 CPU가 여러개의 프로세스를 처리하는 방식입니다. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요? 운영체제는 PCB(Process Control Block)를 사용하여 프로세스를 관리합니다. PCB에는 각 프로세스에 대한 정보가 저장되어 있습니다. 포인터, 프로세스 상태, 프로세스 ID, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보, CPU 스케줄링 정보 등 프로세스에 효율적으로 접근하고, CPU가 뺏겼다가 프로세스가 다시 실행될 때와 같은 상황에 필요한 정보들이 PCB에 담겨있습니다. 컨텍스트 스위칭이란 뭔가요?운영체제가 프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행 중인 프로세스의 상태를 PCB에 저장하고, 다른 프로세스의 상태값으로 CPU의 세팅을 변경하는 작업을 말합니다. CPU의 점유 시간이 다 된 경우, I/O 요청이 있는 경우, 다른 종류의 인터럽트가 있는 경우에 컨텍스트 스위칭이 발생합니다. 예를 들어 프로세스 A의 CPU 점유 시간이 다 된 경우, 현재 CPU 레지스터 값을 PCB A에 저장하고, 다음에 실행될 프로세스의 PCB를 참조해서 해당 프로세스의 마지막 상태로 CPU의 레지스터 값을 세팅합니다. 자료구조와 알고리즘 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요. 학생 정보를 저장하기 위해 해시 테이블을 사용하면 좋을 것 같습니다. 일반적으로 학생들은 고유한 학번(학생 id)을 갖고 있기 때문에 이러한 학번을 key로 사용하면, 특정 학생의 id만 알고있으면 학생의 정보에 빠르게(O(1)) 접근할 수 있어 유용할 것이라고 생각합니다. 또한 한 교실의 학생 인원에 변동(전학 등)이 생길 경우 해시 테이블을 사용한다면 학생 데이터의 삽입, 삭제도 빠르게 할 수 있습니다. 다만, 해시함수에서 충돌이 발생할 수 있기 때문에 이 점에 유의해서 프로그램을 작성해야할 것입니다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.주어진 조건에 가장 적합한 자료구조는 큐라고 생각합니다.큐는 FIFO(First In First Out), 가장 먼저 들어온 것이 가장 먼저 나가는 방식으로 동작합니다. 따라서 큐를 사용하면 주문이 들어온 순서대로 처리할 수 있습니다. 또한 새로운 주문을 큐의 끝에 추가하는 삽입 연산, 가장 먼저 들어온 주문을 큐의 맨 앞에서 제거하는 삭제 연산 등의 간단한 연산만으로 주문 프로그램을 구현할수 있습니다.

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

1주차 학습 내용운영체제운영체제의 구조커널프로세스, 메모리, 저장 장치 등을 관리사용자가 직접 접근하지 못하고, 인터페이스로만 접근 가능인터페이스GUI(Graphic User Interface)GLI(Command Line Interface)시스템콜어플리케이션은 시스템콜을 활용해 커널에 접근드라이버하드웨어와 커널의 인터페이스 컴퓨터 하드웨어와 구조메인보드 : 다른 하드웨어를 연결하는 장치로, 장치 간 데이터 전송은 메인보드의 버스가 담당CPU(Central Processing Unit, 중앙 처리 장치)산술논리 연산 장치(ALU) : 실제 데이터 연산 담당제어 장치(Control Unit) : 모든 장치들의 동작을 지시, 제어레지스터: CPU 내에서 계산을 위해 임시로 보관메모리RAM(Random Acess Memory) : 전원을 끄면 데이터가 날아감, 메인 메모리로 사용, 랜덤한 위치의 어떤 데이터를 읽든 속도가 동일ROM(Read Only Memory) : 전원을 꺼도 데이터 보관 가능, 컴퓨터 부팅 관련 바이오스 저장부팅과정컴퓨터 전원 누름 -> ROM에 저장된 BIOS 실행 -> 주요 하드웨어 이상 여부 체크 -> 이상이 없으면 부트 로더 실행 -> 운영체제를 메모리로 불러오기 -> 바탕화면이 보임인터럽트CPU 입출력 명령이 들어왔을 때 언제 완료되는지 계속 확인해야하는 폴링 방식의 단점을 해결한 것CPU가 입출력 관리자에게 명령을 내리고 자기는 다른 작업함 -> 입출력이 완료되면 CPU에게 신호를 주고 CPU는 신호를 받아서 ISR 실행시켜 작업 완료 프로그램과 프로세스프로그램하드디스크와 같은 저장장치에 저장된 명령문의 집합저장 장치만 사용하므로 수동적인 존재프로세스하드디스크에 저장된 프로그램이 메모리에 올라갔을 때, 즉 실행 중인 프로그램메모리, CPU 사용 및 입/출력 등 능동적인 존재code, data, stack, heap 영역으로 구성멀티프로그래밍과 멀티프로세싱멀티프로그래밍 : 메모리에 여러 개의 프로세스가 올라온 것멀티프로세싱 : CPU가 여러 개의 프로세스를 처리하는 것PCB(Process Control Block)프로세스의 정보를 가지고 있는 것으로, 연결리스트 자료구조로 저장됨.포인터, 프로세스 상태, 프로세스 ID, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보, CPU 스케줄링 정보 등을 저장프로세스 상태생성 -> 준비 -> 실행 -> *(대기 -> 준비 -> 실행 ->) 완료대기 상태: 입출력 요청이 들어오면 입출력이 완료될때까지 기다리는 상태컨텍스트 스위칭프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업컨텍스트 스위칭이 일어날 때 PCB의 내용이 변경됨쓰레드요구하는 작업의 수가 늘어나면 프로세스의 수가 늘어나고, 프로세스의 수만큼 PCB, 코드, 데이터, 스택, 힙 영역을 만들어줘야해서 무거워짐 => 이를 해결하기 위해 쓰레드 고안프로세스 내에 1개 이상 존재하며, PCB, 코드, 데이터, 힙 영역을 공유함CPU 스케줄링운영체제가 모든 프로세스에게 CPU를 할당하거나 해제하는 작업어떤 프로세스에게 CPU 리소스를 줄지, 얼마의 시간동안 CPU를 할당할지를 고려함Burst : 한 작업을 연속적으로 처리하는 것으로, 보통 작업 처리에 필요한 시간을 의미 (CPU Burst, I/O Burst)스케줄링 목표리소스 사용률 높이기, 오버헤드 최소화, 공평성, 처리량, 대기 시간, 응답 시간서로 상반되는 상황이 있기 때문에 사용하는 시스템에 따라서 목표를 다르게 설정CPU 스케줄링 알고리즘 - FIFOFirst In First Out, 먼저 들어온 작업이 먼저 나간다프로세스의 Burst Time에 따라 성능차이가 심하게 나므로 현대 운영체제에서 잘 쓰이지 않고 일괄처리 시스템에서 쓰임알고리즘자료구조와 알고리즘자료구조 : 데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냄알고리즘 : 어떤 문제를 해결하기 위한 확실한 방법자료구조에 따라 알고리즘이 달라지므로, 상황에 맞는 적절한 자료구조를 선택하고 이에 맞는 알고리즘을 적용할 줄 알아야함시간복잡도최선 : 빅-오메가, 평균 : 빅-세타, 최악 : 빅-오주로 빅-오 표기법을 많이 사용함성능 : O(1) 표기법계산에 가장 많은 영향을 미치는 항만 표기상수는 큰 의미 없음배열일반적인 배열크기가 정해져있고, 정해진 크기만큼 연속적인 메모리 공간에 값을 할당운영체제는 가장 첫번째 주소만 기억함참조 성능은 O(1), 삭제, 삽입 성능은 좋지 않음자바스크립트의 배열 상황에 따라서 연속적, 불연속적으로 메모리 할당하는데 대부분 불연속적으로 할당(내부적으로 연결)장점읽기, 쓰기와 같은 참조에는 O(1)의 성능을 가짐단점크기 예측이 힘들기 때문에 메모리 낭비가 발생할 수 있음데이터의 삽입, 삭제가 비효율적임연결리스트배열의 단점을 해결하기 위해 저장하려는 데이터를 메모리 공간에 분산해 할당하고, 데이터를 서로 연결해주면 됨 => Node를 만들어 수행Node의 구조 : data를 담는 변수, 다음 노드를 가리키는 변수장점배열에서 초기 크기를 알아야하는 단점이 없음중간에 데이터를 삽입 혹은 삭제하려면, 특정 노드의 다음 가리키는 노드만 바꿔주면 됨단점데이터들이 전부 떨어져있기 때문에 바로 접근하기 힘듦 => O(n)의 성능스택(Stack)First In Last Out(FILO)으로, 먼저 들어간 데이터가 가장 나중에 나오는 규칙이 있음Redo, Undo 기능, 괄호짝 검사 등에 사용큐(Queue)First In First Out(FIFO)로, 먼저 들어간 데이터가 먼저 나오는 규칙이 있음계산대에 줄을 서는 경우, 맛집 대기줄 등 일렬로 기다리는 줄을 생각하면 됨덱(Deque)데이터의 삽입과 제거를 head와 tail 두 군데서 자유롭게 할 수 있는 자료구조해시테이블(Hash Table)해시(Hash), 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary)라고도 불림해시와 테이블이 합쳐진 자료구조테이블을 그냥 배열에 저장하면, 낭비되는 공간이 발생할 수 있음테이블의 기존 인덱스를 순차적인 인덱스로 만들기 위해 어떤 계산을 하는 함수를 해시라고 함key만 알면 value에 O(1)의 성능으로 읽기가 가능삽입, 삭제, 수정도 O(1)장점빠른 데이터 탐색, 삽입, 삭제를 할 수 있음단점공간의 효율성이 좋지 않음좋은 해시 함수의 구현이 필수적임셋(Set)데이터의 중복을 허용하지 않는 자료구조해시 테이블을 이용하므로 쉽게 구현 가능해시 테이블을 사용한다고 해서 Hash Set이라고도 불림value 값은 사용하지 않고 key만 사용해서 구현함(key가 데이터)회고칭찬하고 싶은 점강의를 허투루 듣지 않기 위해서 강의 노트를 작성하면서, 좀 더 궁금한 점이 생기면 의문점을 작성해두고 추가로 찾아보는 등 디테일한 이해를 위해 노력했다. 아쉬웠던 점휴일이나 주말 등 강의를 들을 시간이 넉넉한 때를 생각하면서 당일에 들어야하는 분량을 미루는 일이 잦았다.보완해야할 점퇴근 후 피곤하더라도 완전히 그날 강의를 안듣기 보다는, 한 강의라도 들으면서 꾸준히 강의를 수강하는 습관을 들이도록 노력하자!