수뼈님의 블로그 - 인프런

수뼈

@chatterbones

수강평 작성수

32

평균평점

4.9

블로그

전체 9

#카테고리

시스템 · 운영체제
알고리즘 · 자료구조

#태그

운영체제
알고리즘
자료구조

2025. 03. 22.
0
인프런 워밍업 클럽 스터디 3기 - CS 전공지식(운영체제) <셋째 주 미션>
1. 메모리의 종류는 어떤 것들이 있나요? 각 메모리의 특징도 함께 적어주세요.강의에서 배운 메모리에는 Register, Cache Memory, RAM, 보조저장장치(SSD/HDD)가 있습니다. 나열한 순서대로 처리 속도가 느려진다는 것이 공통된 특징입니다. 각 메모리의 고유 특징은 다음과 같습니다.Register는 명령어나 연산의 중간 결과값 등을 일시 저장하는 임시 기억장치로, 보통 CPU 내부에 위치합니다. CPU가 연산해야 할 데이터를 RAM에서 가져와 여기에 저장한 후에 연산을 시작합니다. 따라서, CPU의 연산이 이루어지는 곳이라는 점이 차별적 특징입니다.Cache Memory는 CPU와 메인 메모리 간 데이터 접근 속도의 차이를 최소화하기 위해 사용되는 고속 임시 저장소입니다. CPU가 자주 사용할 만한 데이터를 RAM에서 미리 가져와놓고(=Caching), CPU가 필요할 때 RAM보다 우선적으로 접근하도록 하는 용도로 쓰입니다. Cache Hit이 많으면 시스템의 성능이 올라가겠지만 Cache Miss가 많으면 추가 Latency가 발생해 오히려 Cache Memory가 없는 시스템보다도 시스템의 성능이 떨어질 수 있으므로 Cache Hit Ratio를 향상시키는 게 중요합니다.RAM(Random Access Memory)는 CPU가 즉각적으로 접근할 수 있으며, 프로그램 실행과 데이터 처리를 위해 일시적으로 명령어나 데이터를 저장하는 휘발성 메모리 장치입니다. CPU에서 직접 접근이 가능한 유일한 저장 장치라는 게 가장 큰 특징입니다.마지막으로 보조저장장치(SSD/HDD)는 데이터의 장기 저장을 목적으로 설계된 비휘발성(Non-volatile) 메모리입니다. 시스템에 전원이 들어오지 않아도 저장된 데이터가 지워지지 않는다는 고유 특징을 갖고 있습니다.2. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터(Boundary Register)입니다. 경계 레지스터에는 유저 및 응용프로그램이 접근하면 안 되는 OS 영역의 크기 정보가 들어 있습니다. MMU는 사용자의 요청 가상 주소가 Base Register의 값과 Boundary Register의 값을 더한 벗어나는지 검사하고, 만약 벗어났다면 OS 영역을 침범했다고 판단하고 그 프로세스를 종료시킵니다.3. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식은 외부 단편화로 인한 Overhead가 발생한다는 단점이 있지만, 각 논리 영역을 다른 프로세스와 공유하기 위한 추가 분할 작업을 할 필요 없고 각 영역에 대한 메모리 접근 보호에도 편의성이 높다는 장점이 있다. 한편 고정 분할 방식은 구현이 쉽고 오버헤드가 적다는 장점과 내부 단편화로 인한 Overhead라는 단점이 있습니다. 현대에는 이 두 방식을 혼합해 외부 단편화 문제를 없애고 내부 단편화 시 남는 메모리 공간을 최소화한 버디 시스템을 활용합니다.4. CPU 사용률을 올리기 위해 멀티프로그래밍을 했지만, 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워지는 것을 뭐라고 할까요?스레싱(Thrashing)입니다. 이 문제를 해결하려면 하드웨어적으로는 물리 메모리 증설로 해결할 수 있으며, 소프트웨어적으로는 Working Set Model을 활용해 완화할 수 있습니다.5. HDD나 SSD는 컴퓨터를 실행시키는 데 꼭 필요한 걸까요? 이유를 함께 적어주세요.컴퓨터를 '연산 장치'로 규정한다면 필요 없겠지만, 'Personal Virtual Workspace'로 본다면 꼭 필요하다고 생각합니다. 저는 몸이 불편해 현실에서 할 수 있는 작업이 매우 제한되어 있고, 따라서 이미 매우 범용적으로 컴퓨터를 활용하는 현대인들과 비교해서도 압도적으로 많은 작업에 컴퓨터를 활용하고 있습니다. 비휘발성 보조저장장치가 없다면 제가 작업한 것들을 유지하기 위해 컴퓨터를 24/7 켜놓거나 클라우드 공간에 업로드해야 합니다. 전자는 전기세 폭탄 문제와 정전 등 대처 불가능한 외부 문제를, 후자는 보안 문제가 있습니다. 이건 좀 비논리적이고 가벼운 설명이었고(한 번쯤 해 보고 싶었습니다 ㅋㅋ), Computer Architecture적 관점에서도 약 30GB 정도인 윈도우11 기준으로 OS 설치에만 30GB의 RAM이 필요하니 컴퓨터 부품값이 현격히 상승합니다.6. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일을 삭제하더라도 파일의 데이터는 지우지 않고 헤더 정보만 지우는 것이기 때문입니다. 유저가 파일을 삭제하면 파일 할당 테이블의 헤더 정보만 삭제한 뒤, 헤더가 없는 블록을 Free Block List에 따로 관리합니다.
시스템 · 운영체제
･
운영체제
2025. 03. 22.
0
인프런 워밍업 클럽 스터디 3기 - CS 전공지식(자료구조 & 알고리즘) <셋째 주 미션>
1. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬(Bubble Sort), 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort)은 모두 구현이 쉬운 편에 속하나 성능은 약 O(n^2)로 매우 낮습니다. 병합 정렬(Merge Sort)은 재귀적으로 구현해야 하므로 이해와 구현이 어려우나, 성능은 약 O(nlogn)으로 방금 언급한 세 정렬들보다 매우 높습니다. 퀵 정렬(Quick Sort) 또한 병합 정렬과 마찬가지로 Devide & Conquer 방식의 알고리즘으로 평균적으로 약 Θ(nlogn)의 성능을 보이나, 각 단계에서 Pivot이 배열의 요소 중 가장 작은 값 또는 가장 큰 값으로 선정되는 최악의 경우에는 약 O(n^2)로 성능이 결정됩니다. 그러나, 같은 배열을 퀵 정렬과 병합 정렬로 구현했을 때 같은 약 O(nlogn)의 시간 복잡도를 갖는 경우, 참조 지역성(Locality of Reference)의 원리에 의해 퀵 정렬이 병합 정렬보다 처리 속도가 더 빠릅니다.2. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.타뷸레이션(Tabulation)을 활용할 것 같습니다. 아니, 문제의 경우(메모리가 부족한 시스템)라면 타뷸레이션밖에 사용할 수 없습니다. 기본적으로 재귀로 쉽게 해결이 가능한 문제라면 일부 특수한 경우를 제외하면 메모이제이션과 타뷸레이션 모두 활용할 수 있습니다. 이 경우, 재귀 호출을 하지 않으므로 공간 복잡도도 낮고, Call Stack 생성/제거 과정에서의 Overhead가 없어 시간 효율성(Time Effeciency)도 높은 타뷸레이션을 사용하는 것이 더 좋습니다. 물론 재귀적 풀이 과정이 더 가독성이 좋을 때, 계산 가능한 경우의 수에 비해 실제 연산에 쓰이는 연산값은 매우 적을 때 등 메모이제이션이 더 좋을 때도 있을 것입니다. 하지만 메모리가 부족한 시스템이라면 메모이제이션으로 해결하려 할 시 Stack Overflow 에러로 인해 문제 해결 자체가 불가능해질 수 있으므로 타뷸레이션을 활용해야 합니다.
알고리즘 · 자료구조
･
알고리즘
2025. 03. 16.
1
인프런 워밍업 클럽 스터디 3기 - CS 전공지식 <셋째 주 발자국>
[Day 11~13]Algorithm정렬 알고리즘(Sorting Algorithm)개요데이터셋이 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘.참고: 정렬 알고리즘은 왜 배워야 할까?대표적인 정렬 알고리즘버블 정렬(Bubble Sort) (Day 09 참고)선택 정렬(Selection Sort) (Day 09 참고)삽입 정렬(Insertion Sort)개요 및 특징자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교해, 자신의 위치를 찾아 삽입하는 알고리즘(참고).구현이 쉬운 편에 속하나 성능은 O(n^2)로 매우 낮음.구현하기첫 번째 구현: 강의 보며 구현 (Done)두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현 (Done)세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현 (Done)네 번째 구현: 아무것도 안 보고 구현 (Done)마지막 구현: 익숙한 파이썬으로 구현(+리팩토링(비파괴적 연산, 예외처리)) (Done)병합 정렬(Merge Sort)개요 및 특징Array를 정렬의 최소 단위(=1개)로 쪼개 정렬한 결과를 병합하여 정렬하는 알고리즘.Devide and Conquer 기법과 재귀 함수를 이용해 정렬함(참고).참고: 여기서 설명하는 건 mergeSort()가 아니라 merge()다. 저걸 누가 헷갈리냐고? NADA재귀적으로 구현해야 하므로 이해와 구현이 어려우나, 성능(O(nlogn))이 매우 높음.구현하기첫 번째 구현: 강의 보며 구현 (Done)두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현 (Done)세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현 네 번째 구현: 아무것도 안 보고 구현 마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링) 퀵 정렬(Quick Sort)개요 및 특징피벗(Pivot)을 기준으로 작은 값과 큰 값을 분할하며 정렬하는 알고리즘.Devide and Conquer 기법과 재귀 함수를 이용해 정렬함(참고).pivot에 따라 Θ(nlogn), O(n^2)로, 안정적으로 O(nlogn)의 성능을 뽑아내는 병합 정렬이 더 좋음.하지만, 같은 O(nlogn)이라면 Locality of Reference 원리 때문에 더 빠름.구현하기첫 번째 구현: 강의 보며 구현 (Done)두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현 세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현 네 번째 구현: 아무것도 안 보고 구현 마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링) Operating System가상 메모리(Virtual Memory)개요실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술(혼공컴운 402p.)가상 메모리 시스템에서 MMU는 동적 주소 변환(Dynamic Address Translation; DAT)을 통해 RAM의 물리 주소와 스왑 영역을 하나의 가상 주소로 보고 관리함(참고).가상 주소-물리 주소쌍은 매핑 테이블로 관리됨(참고).프로세스 입장에서 관리 편의성 향상을 위해 생성된 가상의 공간이므로 이론상 크기는 ∞이자만, 실제로는 CPU 비트 수에 따라 OS에 의해 적정 크기로 결정됨(참고).하지만 사용자의 성향에 따라 수동 조정도 가능함(참고).OS가 실행할 프로세스 외 프로세스를 스와핑(Swapping)하는 방식으로 구현되어 있음.주소 공간 분할 방식세그멘테이션(Segmentation) 개요 및 특징프로세스를 세그멘트(Segment)로 잘라서 메모리에 배치하는 방법.MMU는 Segment Table을 통해 DAT하여 각 프로세스의 논리 주소를 물리 주소로 변환함(참고: 1, 2).Segmentation Table이 아님!메모리의 가변적 분할+프로세스 내 각 영역의 메모리 접근 보호 용이성 vs. 외부 단편화DAT 과정 (참고: 1, 2, 3)프로세스가 코드를 실행해 필요한 명령어와 데이터의 가상 주소를 CPU에 전달함.CPU가 MMU에게 특정 논리 주소의 물리 주소 정보를 요청함.MMU가 Segment Table의 Base Address와 Bound Address를 통해 해당 가상 주소와 연결된 물리 주소를 찾음.MMU가 가진 STBR을 통해 S.T.의 물리 메모리상 시작 위치를 찾음.S.T.상 해당 프로세스의 가상 주소가 몇 번째 세그먼트에 위치해 있는지 찾음.세그먼트 테이블의 해당 인덱스로부터 찾은 Base Address와 Bound Address 값을 참고해 진행.가상 주소 값 이라면 Base Address 값+가상 주소 값으로 물리 주소 값을 알아냄.가상 주소 값 > Bound Address 값이라면 프로세스를 종료시킴.페이징(Paging) (참고: 1, 2, 3, 4)개요 및 특징프로세스의 논리 주소 공간을 페이지(Page) 단위로, 물리 주소 공간을 프레임(Frame)으로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법(혼공컴운 403p.)페이지 테이블의 크기가 너무 커져서 메모리를 낭비하지 않도록 주의하는 것이 관건.메모리의 효율적 관리 vs. 내부 단편화DAT 과정 (참고: 1, 2, 3)프로세스 코드 실행 ... CPU의 특정 논리 주소의 물리 주소 정보 요청까지는 동일함.MMU가 Page Table을 통해 해당 가상 주소와 연결된 물리 주소를 찾음.해당 가상 주소의 Page Number 및 Offset을 통해 고유 Page Table에 접근함.Page Number = 가상 주소 / 페이지 크기, Offset = 가상 주소 % 페이지 크기PTBR을 통해 P.T.의 물리 메모리상 시작 위치를 찾음.S.T.상 페이지 번호로 프레임 번호를 찾고, 해당 프레임의 시작 주소에 Offset을 더해 변환함.페이지드 세그멘테이션(Paged Segmentation)개요 및 특징프로그램을 Segment로 나누고, 이를 Page들의 집합으로 구성하는 방식(참고).DAT 시 외부의 세그먼트 테이블과 내부의 페이지 테이블로 이루어진 두 단계 테이블을 이용함(참고).세그먼트 테이블 변경 사항보호 비트(Protection Bit) 추가(참고).Base Address -> Page NumberBound Address -> 해당 세그먼트의 페이지 개수Paging과 Segmentation의 장점 vs. 페이지 이중 참조로 인한 Overhead따라서, 현대 OS에서는 페이징과 페이지드 세그멘테이션을 혼용하여 사용함.DAT 과정 (참고: 1, 2, 3)프로세스 코드 실행 ... CPU의 특정 논리 주소의 물리 주소 정보 요청까지는 동일함.S.T.상 해당 프로세스의 가상 주소가 몇 번째 세그먼트에 위치해 있는지 찾음.영상에서 "0x12300 번지이니 1번 세그먼트구만!"이라는 설명은 예시일 뿐, 번지 수와 세그먼트 번호 간의 관계는 없음(참고).해당 세그먼트의 접근 권한 위반 여부 확인위반이라면 해당 요청을 한 프로세스를 Shutdown시킴.페이지 넘버를 통해 프레임 넘버를 가져 온 후, 해당 프레임으로 접근함.Invalid라면 Swap 영역에서 가져옴.해당 프레임의 시작 주소로부터 offset을 더해 원하는 데이터에 접근함(참고: 1, 2). [Day 14]Algorithm메모이제이션(Memoization) (참고: 1, 2, 3)정의 및 특징함수 호출의 결과를 캐싱하고 동일한 입력이 다시 발생할 때 캐싱된 결과를 반환하는 하향식 접근(참고).공간 복잡도-시간 효율성 간 Trade-off 관계에 있음.계산 결과를 저장하기 위한 추가 메모리가 필요하지만, 일반적으로 중복 계산 제거로 얻는 시간 효율성(Time Effeciency)이 훨씬 높으므로 자주 활용됨.메모이제이션 예제: 피보나치 수열(참고).메모이제이션 없이 구현메모이제이션 활용해 구현Operating System입출력 장치(I/O Device)개요새로운 데이터를 받아들여서 중앙 처리기로 보내고 다시 처리 결과를 받아 알아볼 수 있는 형태로 바꾸어 주는 장치(참고).CPU와 메모리 버스에 직접 연결되지 않고, 간접적으로 연결되면 전부 I/O Device!(참고)유저가 시스템과 소통할 수 있게 하는 장치로, 다른 장치에 비해 처리 속도(=전송률)가 매우 느림.이를 보완하는 기술로 Buffering과 Spooling이 존재함(참고: 1, 2, 3).각 장치는 각자의 Device Controller를 통해 데이터를 보내고, I/O Bus를 통해 CPU를 거쳐 RAM에 도달함.DMA(Direct Memory Access)를 추가해 CPU 없이 I/O Controller가 Event 등 데이터를 RAM에 직접 전달하는 입출력 방식, 즉 Memory Mapped I/O로 확장됨(참고).각 Device의 공통 내부 구조 (※ I/O Device는 종류별, 브랜드별, 제품별로 내부 구조가 천차만별임)Device Controller (참고: 1, 2, 3)System Bus와 장치 사이에서 데이터를 송수신할 수 있도록 Interface 역할을 하는 장치.'해당 I/O 장치를 전담으로 처리하는 작은 전용 CPU 같은 존재'라 이해하면 좋음!(참고)CPU와 I/O Device 간 통신 중개, 오류 검출, 데이터 버퍼링 등의 역할을 수행함.장치 종류에 따라 장치 내부에 있을 수도, 외부(본체)에 있을 수도, 둘 모두에 분산되어 있을 수도 있음.장치의 위치보다 장치의 기능을 위주로 기억하는 것이 핵심!Buffer입출력 장치와 응용 프로그램 사이의 데이터를 임시로 저장하는 메모리 공간.일반적으로 이중 버퍼링, 즉 입력 버퍼와 출력 버퍼를 사용하는 방식이 일반적임.RegistersCPU가 장치 상태를 확인하거나 명령을 보낼 때 사용하는 메모리 공간.데이터 레지스터, 상태 레지스터, 제어 레지스터로 이루어져 있음(참고).데이터 전송 단위에 따른 분류 (※ 한 장치에서도 기능별로 달리 작동하는 기기도 있음) (참고: 1, 2, 3)캐릭터 디바이스(Character Device)정의 및 특징Fixed Size Block로 정보를 기록하는 장치로, Event의 순서가 상관없는 장치에 사용함.B.D.에 비해 데이터 전송 단위가 작음종류마우스(Mouse)정의 및 특징2차원 평면에서의 움직임을 컴퓨터에 전송하는 포인팅 디바이스의 일종.일반적으로 2차원 평면상에서 위치 정보(x, y)와 버튼 클릭 정보, 스크롤 동작 등을 전달함.현대 GUI 기반 OS에서 가장 대중적인 입력장치로 쓰이고 있음.Event 처리 및 전달 과정 (※ 커서 이동 기준)Ball Mouse사용자로부터 Event 발생Optical Mouse 키보드(Keyboard)블록 디바이스(Block Device)개요 및 특징C.D.에 비해 데이터 전송 단위가 큼종류HDD(Hard Disk Drive)정의 및 특징비휘발성, 순차접근이 가능한 컴퓨터의 보조 기억 장치(참고).여러 개의 플래터(Platter)가 회전하며 데이터를 저장하고 읽는 자기식 저장장치임.Flash MemoryCPU와 I/O Device 간 통신 과정MMID (※ 강의에 소개된 방식) PMID [Day 15]Algorithm타뷸레이션(Tabulation) (참고: 1, 2, 3)정의 및 특징문제를 하위문제로 나눠 계산한 결과를 테이블에 저장한 후, 해당 테이블을 연산에 활용하는 상향식 접근(참고).메모이제이션은 계산 및 저장, 호출을 그때그때 하고, 타뷸레이션은 계산 및 저장을 먼저 해두고 나중에 한꺼번에 호출한다는 게 가장 큰 차이!재귀 호출을 하지 않으므로 공간 복잡도도 낮고, Call Stack 생성/제거 Overhead가 없어 T.E도 높음.반복문의 Overhead는 Loop Unrolling 등의 추가 최적화 여지가 있어 시간 효율성 측면에서는 반복문이 효율적임!단, 일부 상황(예: TSP)에서는 메모이제이션의 시간 효율성이 더 높을 수 있음.재귀적 풀이 과정이 더 가독성이 좋을 때, 계산 가능한 경우의 수에 비해 실제 연산에 쓰이는 연산값은 매우 적을 때 등구현하기타뷸레이션 예제: 피보나치 수열 Operating SystemFile System개요 및 특징 컴퓨터에서 파일이나 자료를 쉽게 발견 및 접근할 수 있도록 보관 또는 조직하는 체제(참고).파일 관리자가 Block 단위로 저장된 Block Device에 Byte 단위로 접근할 수 있도록 변환함. 파일 시스템의 기능파일 및 폴더 생성, 수정, 삭제파일 권한 관리무결성 보장백업 및 복구암호화(Encryption)File Descriptor개요 및 특징Process가 특정 파일에 접근할 때 사용하는 추상적인 값(참고). [Week Review]일주일 동안 공부하면서 배우고 느낀 점독학으로 CS 공부를 하는 나름의 습관에 감이 잡힌 것 같다.마지막 주 시작을 지난주에 미처 다 이해하지 못한 메모리 분할 방식에 대해 공부하면서 시작했다. 처음엔 정말 이해가 가지 않았지만, 강의를 계속 반복 학습하고, 관련 자료를 찾아보고, 이해가 안 되면 ChatGPT와 충분한 질답을 주고받으면서 공부했다.위 일련의 과정에서 파편화된 지식을 계층적으로 재구성해 정리하는 방법, Hallucination이라는 태생적 한계를 지닌 LLM을 공부에 활용할 때 어느 정도로 참고해야 하는지, 신용할 만한 정보는 어디에 많이 있는지 등에 관한 감이 잡혔다.어려웠던 점강약 조절이 너무 어렵다...감자님 강의를 보면 해당 주제에 대한 감은 오지만 지식이 체계적으로 쌓이는 느낌은 들지 않는다. 이건 감자님 강의가 입문자들을 위한 쉬운 설명에 주안점을 두고 있어서 그런 거지 단점이 아니다. 오히려 나 같은 비전공자들로 하여금 '뭘 공부해야 하지?'에 대한 가이드를 준다는 점에서 최고다.근데 내 성격과 몸이 문제다. 지식을 대충 말고 제대로 정리하다 보니 끝이 없다. 이러다간 이번 주는 발자국을 제때 완성 못하고 스터디도 준비 못할 것 같다.어찌저찌 마무리했다... 휴... 원래 내 방식은 노트 정리를 탑다운으로 틀만 잡고 그 후부터는 바텀업으로 디테일을 계속 파고드는 스타일이었는데, 탑다운으로 강의 내용을 어느 정도(한 60% 정도?) 머릿속에 집어넣기 전까진 정리라는 행위를 하지 않기로 했다. 그 후에 머릿속에 있는 내용을 최대한 있는 대로 정리한 후에 바텀업으로 디테일을 파고들었다. 시간상 정리하지 못한 부분도 있긴 하나 머릿속엔 있기 때문에 반쯤 성공이라고 자축해 본다.향후 목표나만의 CS 완전 정복 로드맵 마스터하기이번 워밍업 클럽은 내 첫 CS 공부였다. 이전까지는 주먹구구식으로 그때그때 필요한 정보만 공부하다 보니 지식이 계속 휘발되는 느낌이었다. 그런데 이번 CS 공부를 하면서 오직 CS 하나만을 집중적으로 공부했다 보니 왜 CS 공부를 해야 하는지 그 이유가 분명해졌다.나는 언젠가 창업을 하고자 한다. 창업해서 서비스를 운영하려면 모르긴 몰라도 아득히 높은 수준의 갖은 능력이 필요하리라 여겨진다. 그러나 요즘은 K-MOOC나 KOCW, edX 등을 통해 전공 강의조차도 무료로 들을 수 있는 시대이니 느리더라도 꾸준히 멈추지 않고 나아간다면 분명 승산이 있다고 생각한다.워밍업 클럽 마무리 관련 소감워밍업 클럽 전반 관련네트워킹이 제대로 이뤄지지 못하고 각자도생하는 느낌이어서 아쉬웠다. 워밍업 클럽이 '특정 목표를 가진 사람들을 모아놓자' 딱 거기에 의의가 있는 프로그램이라면 할 말 없지만, 운영 쪽에서 개별 스터디를 장려하는 유인(스터디 과정 제출 시 가산점, 놀러 와서 커피 쿠폰 뿌리고 가기 등)이 있었다면 훨씬 좋았을 것 같다.감자님 강의 관련 (※ 대문자 T 주의해 주세요 감자님 ㅠㅠㅠ 나쁜 마음은 없습니다ㅠㅠㅠㅠㅠㅠㅠ)자료구조 및 알고리즘 강의는 만점을 줘도 아깝지 않은 강의였다고 생각한다. 자료구조이나 알고리즘 모두 시각화가 정말 중요하다고 생각하는데, 단순히 달달 외우는 게 아니라 생각할 수 있는 힘을 기르게 해주신 훌륭한 강의였던 것 같다.운영체제 강의는 아쉬움이 남는다. (내게 이런 평가를 내릴 만큼의 지식이 있기는커녕 그 1%도 안 되지만) 내용상 잘못 설명하신 부분이나 실제로는 다르지만 같다고 퉁치고 넘어가는 내용들이 가끔 있었다. 나만 해도 지난 3주 동안 강의의 큰 오류를 2개나 찾았다. 강의 수강 대상자가 입문자라면 쉬운 설명만큼이나 내용의 정확성도 중요하다고 생각한다. 초보들은 처음 배운 지식을 수정하기가 매우 어렵기 때문이다.스터디 관련1주차부터 2주차, 그리고 오늘까지 CS 스터디를 모집해 운영해 왔다. 매주 일요일 2시에, 워밍업 클럽 일정대로 공부한 내용을 공유하는 스터디였는데 이탈률도 높고 남은 사람들의 참여율도 저조했다. 더 이상 말은 안 하겠지만... 많이 실망스러웠다.그래도 공유해야 할 내용이 있는 만큼 내가 이해한 내용을 하나라도 더 매끄럽게 설명할 수 있게 노력한다든지, 정확한 내용이 맞는지 더블, 트리플, 쿼드러플 체크를 반복했던 점은 좋았다. 혼자 공부할 때도 늘 그렇게 하고 있었다는 게 문제지만.나 자신 관련우선 나 자신에게 고생했다고 말하고 싶다. 어찌 됐건 수료를 했으니까. 얻은 것들도 무수히 많고. 무엇보다 막연하기만 했던 'CS란 뭘까?'에 대한 해답과 '비전공자인 내가 CS를 감히 도전해도 될까?'에 대한 해답을 얻은 게 긍정적이다.하지만, 개인적으로 내가 나에게 느꼈으면 하는 감정은 답답함과 공포였다. 근데 둘 모두 전혀 없다. '비전공자여도 전공자들을 찍어누를 만큼의 지식과 경험, 능력을 갖고 싶다'는 다소 허황된 꿈이 여기서 현실로 다가왔어야 했는데... 아쉽다.
알고리즘 · 자료구조
･
알고리즘
･
운영체제
2025. 03. 15.
0
인프런 워밍업 클럽 스터디 3기 - CS 전공지식(자료구조 & 알고리즘) <둘째 주 미션>
1. 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?스택 오버플로우(Stack Overflow)가 발생합니다. 일반적으로 코드가 실행되면 Call Stack이 생성되어 함수가 호출될 때마다 그와 관련된 정보가 Stack Frame 형태로 메모리에 저장됩니다. 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했다면 함수가 무제한으로 호출되며, 그에 따라 Stack Frame도 무제한으로 쌓이게 됩니다. 이렇게 늘어난 용량이 프로세스에 할당된 Call Stack 메모리의 잉여 용량을 초과하면 프로세스가 OS에 의해 강제 종료되는데, 이것이 스택 오버플로우(Stack Overflow)입니다.2. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n) { if (n 3. 다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.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 traverseDirectory(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); traverseDirectory2(filePath); // 재귀 호출 } else { console.log('파일:', filePath); } } } traverseDirectory("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력
알고리즘 · 자료구조
･
자료구조
･
알고리즘
2025. 03. 15.
0
인프런 워밍업 클럽 스터디 3기 - CS 전공지식(운영체제) <둘째 주 미션>
1. FIFO 스케줄링의 장단점이 뭔가요?장점은 쉬운 구현과 실행 결과 예측의 용이성이고, 단점은 호위 효과와 사용성 저하입니다. FCFS(First Comes, First Served) Algorithm이라고도 하는 FIFO Scheduling은 이름대로 모든 프로세스를 단일 Ready Queue에 넣고 순차 실행합니다. Time Slice, Timeout Interrupt 등을 통한 Context Switching도 구현되지 않은 때의 비선점 알고리즘인 만큼 구현이 쉽고 실행 결과 예측이 용이합니다. 그러나 Burst Time이 긴 게 먼저 오느냐, 짧은 게 먼저 오느냐에 따라 평균 대기 시간 차이가 크게 벌어지는 Convoy Effect가 발생하며, 멀티 프로세싱이 불가능하므로 사용성이 크게 저하됩니다.2. SJF를 사용하기 어러운 이유가 뭔가요?각 프로세스의 Burst Time 예측 불가능성, Burst Time이 긴 프로세스의 Starvation 때문입니다. SJF(Shortest Job First) Scheduling은 Burst Time이 짧은 프로세스를 우선 실행하는 알고리즘입니다. 따라서 각 프로세스의 Burst Time을 정확히 예측하고, 그걸 바탕으로 Ready Queue에 줄세워야 하는데 이것은 외부 환경 등에 의해 큰 영향을 받는 Burst Time 특성상 현실적으로 줄세우기가 불가능하단 것이 첫 번째 이유입니다. 두 번째로, 어찌어찌 모든 프로세스를 잘 줄세웠다고 해도 Burst Time이 아주 긴 프로세스는 최악의 경우, 컴퓨터가 종료될 때까지 단 한 번도 실행되지 못할 수도 있습니다.3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?매우 큰 Context Switching Overhead가 발생해 시스템 성능을 크게 저하됩니다. 컨텍스트 스위칭 작업에는 CPU 레지스터나 프로그램 카운터 같은 상태 정보 저장 및 복원, 메모리 캐시 무효화 등의 오버헤드 요소가 산재해 있습니다. 만약 타임 슬라이스가 극단적으로 짧다면 CPU가 연산보다 컨텍스트 스위칭에 더 많은 리소스와 시간을 소모하게 되어 전체 시스템 처리량을 크게 낮추고 응답 시간도 늘어나게 됩니다.4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?OS는 Timeout Interrupt가 일어난 프로세스는 CPU Bound Process로, I/O Burst가 일어난 I/O Bound Process는 I/O Bound Process로 판단합니다. 어떤 프로세스가 할당된 시간 동안 작업을 완수하지 못한 채 타임아웃 인터럽트가 발생하면, 이는 프로세스가 긴 CPU burst를 수행하고 있다는 신호이므로 CPU Bound Process로 간주되어 낮은 우선순위 큐로 이동할 가능성이 큽니다. 반면 Timeout Interrupt 전에 I/O Burst을 발생시키면 CPU를 별로 안 쓴다는 뜻이므로 I/O Bound Process로 판단되어 높은 우선순위 큐에 배치되어 빠른 응답성을 유지합니다.5. 공유자원이란 무엇인가요?여러 프로세스나 스레드가 동시에 접근하고 사용할 수 있는 하드웨어나 소프트웨어 자원을 의미합니다. CPU, 메모리, 파일, 프린터, 네트워크 등이 모든 HW 자원이 여기에 해당할 수 있습니다. 동기화 문제가 발생하지 않도록 주의해야 합니다.6. 교착상태에 빠질 수 있는 조건에는 어떤 것들이 있을까요?상호 배제(Mutual Exclusion), 비선점(No Pre-emption), 점유와 대기(Hold and Wait), 원형 대기(Circular Wait)이 있습니다. 상호 배제는 하나의 프로세스가 자원을 사용 중일 때 다른 프로세스는 해당 자원을 사용할 수 없는 조건입니다. 비선점은 한 프로세스가 자원을 할당받으면, 그 프로세스가 자원을 자발적으로 해제할 때까지 다른 프로세스가 강제로 빼앗을 수 없는 조건입니다. 점유와 대기는 프로세스가 최소한 하나의 자원을 보유한 상태에서, 추가 자원을 요청해 대기하는 상황입니다. 마지막으로 원형 대기 (Circular Wait)란 프로세스들이 점유와 대기 상태로 원형으로 대기하는 것입니다. 예를 들어, 프로세스 A가 프로세스 B가 보유한 자원을 기다리고, 프로세스 B는 프로세스 C의 자원을, 그리고 마지막으로 프로세스 C는 다시 프로세스 A의 자원을 기다리는 형태입니다.
시스템 · 운영체제
･
운영체제
2025. 03. 10.
1
인프런 워밍업 클럽 스터디 3기 - CS 전공지식 <둘째 주 발자국>
[Day 06]Algorithm재귀(Recursion): 어떠한 것을 정의하는 과정에서 자기 자신을 참조하는 것.재귀함수(Recursive Function)을 구현할 때 탈출 조건(기저 조건)을 정의해놓지 않으면 콜 스택(Call Stack)에 스택 프레임(Stack Frame)이 무제한으로 쌓이게 되어 사용이 불가능함.Stack Overflow: Call Stack이 메모리의 잉여 용량을 초과하여 프로세스가 OS에 의해 강제 종료되는 현상.재귀함수를 사용할 때 쉽게 해결 가능한 문제: Factorial(n)재귀함수를 사용할 때 쉽게 해결 가능한 문제: 깊이 우선 탐색(Depth-First Search; DFS)(참고: 1, 2, 3)Operating System 프로세스 간 / 프로세스 내 통신프로세스 간 통신(Inter-process Communication; IPC) (참고: 1, 2, 3)개요운영체제가 주체가 되어 프로세스 간 통신 프로세스들끼리 서로 데이터를 주고받는 것.기본적으로 각 프로세스는 독립적이기에 명시적으로 통신 매개체를 만들어주지 않으면 통신이 불가능함.파일, 파이프, 메세지, 네트워크 등 다양한 매개체를 통해 통신하는 다양한 방식이 있음.여러 프로세스가 공유 자원에 접근한다면 동기화 문제가 생길 수 있으므로 해결이 필요함.정보 공유,계산 가속화,모듈성,편의성 등을 도모하기 위해 활용되는 기술임.통신 방식에 따른 분류공유 메모리(Shared Memory) 방식 (참고: 1, 2, 3)개요여러 프로세스가 공동으로 사용할 수 있는 가상 메모리 영역을 활용해 통신하는 방식.모든 IPC 방식 중 가장 통신 속도가 빠르다는 장점과 동기화 문제가 생기기 쉽다는 단점이 있음.대표적인 활용 예시로 복붙이 있음(예: 워드의 텍스트를 인터넷 창에 가져오기).일반적인 순서UNIX 계열부모 프로세스 생성 및 가상메모리 영역 할당.부모 프로세스가 자신에게 할당된 메모리 영역 중 일부를 공유 메모리로 사용하겠다고 커널에 요청.커널이 프로세스가 접근 가능한 고정 길이의 공유 메모리 영역을 생성 및 할당해 줌.고정 길이라는 점을 왜 강조하신 걸까? -> 왜 용량 할당 기준이 다른 걸까?(참고) 메모리 할당 방식과 동기화 문제 발생 가능성의 차이 때문임.fork() 함수로 자식 프로세스 복제(이때 공유 메모리 주소도 복사됨).프로세스 동기화(Process Synchronization) (※ 병형 제어(Concurrency Control)라고 부르기도 함) (참고: 1, 2, 3)정의 및 특징프로세스 접근 순서 및 방식을 OS의 동기화 메커니즘을 사용하여 조정하는 것.각 프로세스가 공유 자원에 접근하는 순서는 시분할 CPU 스케줄링을 하는 OS만 알고 있으므로, OS 단위로 해결할 수밖에 없음.대부분의 프로세스 동기화 방법은 상호 배제(Mutual Exclusion) 메커니즘의 일부 또는 전부에 기반함.공유 메모리 방식에서 가장 발생하기 쉬운 문제지만, 다른 방식에서도 얼마든지 발생할 수 있는 문제.동기화 문제 해결 방법 (Deadlock 해결 방법은 Day 07 참조)Race Condition 해결 방법뮤텍스(Mutex) (참고: 1, 2, 3)추가 예정.세마포어(Semaphore) (참고: 1, 2, 3)개요 및 특징멀티프로그래밍 환경에서 Critical Section에 동시에 접근할 수 있는 프로세스의 최대 개수를 제한하기 위해 사용되는 정수형 변수(링크 내 정의를 참고해 보강함).뮤텍스와 달리 Critical Section에 접근 가능한 프로세스 개수를 2개 이상으로 지정할 수 있다는 게 차이점!뮤텍스=열쇠(잠긴 동안 누구도 못 감), 세마포어=미리 발급된 n개의 출입증(다 떨어진 순간 못 들어감)이 더 좋은 비유라고 생각함.사용법 자체는 쉽지만 wait() 함수와 signal() 함수를 잘못 사용하면 꼬일 수 있음(참고).활용 방법wait() 함수로 세마포어의 수를 1 줄여 프로세스 하나가 Critical Section에 들어갔음을 OS에 전달함.이때 이미 세마포어가 0이라면 이후 코드는 실행되지 않음.코드를 진행하다 signal() 함수를 만나면 세마포어의 수를 1 늘려 프로세스 하나가 Critical Section에서 나갔음을 OS에 전달함.모니터(Monitor) (참고: 1, 2, 3)개요 및 특징공유 자원에 대한 동시 접근을 안전하게 제어하기 위해 상호 배제와 조건 변수를 결합한 고수준의 동기화 기법(by ChatGPT o3-mini-high)프로그래밍 언어 차원에서 여러 프로세스에서 동시에 실행될 수 없는 함수를 만드는 방식으로 구현함.파이프(Pipe) 방식개요OS가 각 프로세스와 연결된 단방향 통신용 메모리 공간(=Circular Buffer)을 생성해 데이터를 전달함.기본적으로는 바이트스트림(Bytestream) 데이터만 전달 가능하며(참고: 1, 2, 3), 다른 데이터타입을 전달하려면 직렬화(Serialization)해야 함. Anonymous Pipe부모-자식, 형제 등 통신 대상이 정해진 두 프로세스가 단방향 통신(Half Duplex)할 때 사용함(예: fork()).양방향 통신(Full duplex)을 위해선 익명 파이프가 두 개 필요한데, 이는 구현이 복잡함.Named PipeAnonymous Pipe가 확장된 형태로, 파일 시스템에 이름이 부여된 파이프를 말함.FIFO라는 통신을 위한 파일을 만들고, 그걸 통해 양방향 통신(Full duplex)이 가능함.메세지 큐(Message Queue)네트워크 방식소켓RPC스레드 간 통신(Inter-thread Communication; ITC)데이터 영역에 있는 전역 변수(=공유 메모리)나 힙을 이용해 통신함."전역 변수보단 공유 메모리라는 명칭을 선호한다." - 곰책으로 쉽게 배우는 최소한의 운영체제론 [Day 07]Algorithm Recursive Thinking재귀라는 테크닉을 제대로 활용하려면 하향식(Top-down) 계산식으로 문제를 변형할 수 있어야 함.하향식 계산 활용 1: 배열 각 원소의 총합 구하기하위 문제: arr.length === n-1인 배열 각 원소의 총합 구하기 + 마지막 원소하향식 계산 활용 2: 문자열 길이 계산하기하위 문제: str.length === n-1인 문자열의 갯수 구하기 + 1하향식 계산 활용 3: 지수함수 계산하기하위 문제: n^m-1 * nOperating System교착 상태 제어(Deadlock Control)Deadlock: 두 개 이상의 프로세스가 서로가 가진 자원의 해제를 기다리며 무한 대기하는 상태.Deadlock의 필요조건 (넷 중 하나라도 빠지면 Deadlock이 발생·유지되지 못함)상호 배제(Mutual Exclusion), 비선점(No Pre-emption),점유와 대기(Hold and Wait),원형 대기(Circular Wait)Deadlock 해결 방안 (참고: 1, 2, 3)Deadlock Prevention (참고: 1, 2, 3)교착상태가 애초에 일어나지 않도록 Deadlock 필요조건 중 하나를 제거하는 것.이론적으로만 가능하고 현실적으로 불가능하거나(상호 배제 및 비선점), 유저 사용성과 시스템 유연성을 해치게 되므로(점유와 대기,원형 대기) 현실적으로 적용 불가함.Deadlock AvoidenceOS가 시스템 자원과 프로세스들의 현재 할당 자원 및 최대 요구 자원을 종합적으로 고려해 시스템이 되도록 안정 상태(Safe State)를 유지할 수 있는 만큼만 시스템 자원을 할당하는 것.각 메모리의 최대 요구 CPU 리소스는 어떻게 아는 걸까?(참고) 추정치가 아니라 상한선이다!비용이 비싸고, 비효율적이라는 단점교착상태 검출가벼운 교착상태 검출프로세스가 정해진 시간 동안 작업을 진행하지 않는다면 OS가 이를 교착상태로 판단함.교착상태가 되면 가장 최근의 Checkpoint로 프로세스 상태를 되돌림.오버헤드가 적지만 멀쩡한 프로세스를 롤백해버릴 수 있음.무거운 교착상태 검출OS가 자원 할당 그래프를 지속적으로 관찰하다가 원형 대기 상태를 발견하면 이를 교착상태로 판단함.교착상태가 되면 가장 최근의 Checkpoint로 프로세스 상태를 되돌림.멀쩡한 프로세스를 롤백할 일이 없지만 오버헤드가 큼. [Day 08]Algorithm 하노이의 탑(The Tower of Hanoi) 1883년 프랑스의 수학자 Édouard Lucas가 처음으로 발표한 게임으로, 재귀함수 예제로 활용됨.하향식(Top-down) 접근가장 큰 원반을 기둥 3으로 옮기기 -> 나머지 원반을 기둥 2로 옮겨야 함그보다 작은 원반을 기둥 3으로 옮기기 -> 더 작은 나머지 원반을 기둥 2로 옮겨야 함 (이게 하위문제!)구현하기첫 번째 구현: 강의 보며 구현 (Done) 두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현 (Done) 세 번째 구현: 리팩토링 (원반 이동 횟수 출력, 원반 이동 On/Off 기능 추가) (Done) 마지막 구현: 익숙한 파이썬으로 구현(+리팩토링) (Done) Operating System컴파일과 프로세스Compile: 소스코드가 실행파일(=프로그램)이 되는 과정 (※ 아래 과정은 C 기준) (참고: 1, 2)Preprocessing,Compile, Assembly, Linking 순으로 진행하여 .exe 파일, 즉 실행 파일이 생성됨.코드 영역과 데이터 영역으로 이루어진 .exe 파일 실행 시 프로세스 생성됨. [Day 09]Algorithm정렬 알고리즘(Sorting Algorithm)개요데이터셋이 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘.참고: 정렬 알고리즘은 왜 배워야 할까?대표적인 정렬 알고리즘버블 정렬(Bubble Sort) (※ Sinking Sort라고도 함)배열의 정렬되지 않은 영역에서 서로 인접한 두 원소 크기가 순서대로 되어 있지 않으면 서로 교환하는 방식으로 모든 원소를 정렬하는 알고리즘.최악의 경우, O(n^2)의 시간복잡도를 가짐.구현하기첫 번째 구현: 강의 보며 구현 (Done)두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현 세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현 네 번째 구현: 아무것도 안 보고 구현 마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링) 선택 정렬(Selection Sort)배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져오는 알고리즘.최악의 경우, O(n^2)의 시간복잡도를 가짐.구현하기첫 번째 구현: 강의 보며 구현 (Done)두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현 세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현 네 번째 구현: 아무것도 안 보고 구현 마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링) Operating System메모리의 종류휘발성 메모리(Volatile Memory)종류 및 특징Register (참고: 1, 2, 3)개요 및 특징CPU 내부에서 처리할 명령어나 연산의 중간 결과값 등을 일시 저장하는 임시 기억장치.CPU 내부에는 다양한 종류의 레지스터가 있음(각 레지스터의 종류와 특징은 후술).CPU가 연산해야 할 데이터를 RAM에서 가져와 여기에 저장한 후에 연산을 시작함.Register의 크기가 32bit인지 64bit인지에 따라 CPU 종류가 달라짐.종류와 특징재배치 레지스터(Relocation Register)논리 주소를 물리 주소로 변환하는 데 사용되는 레지스터.프로그램을 다른 메모리 위치로 이동해도 주소 수정 없이 실행 가능함.Cache Memory (참고: 1, 2, 3)CPU와 메인 메모리 간 데이터 접근 속도의 차이를 최소화하기 위해 사용되는 CPU 내 고속 임시 저장소(by ChatGPT-o3-mini-high).속도와 용량에 따라 Level 1, Level 2, Level 3 Cache로 세분화되어 탑재되어 있음(시스템마다 다름).CPU가 자주 사용할 만한 데이터를 RAM에서 미리 가져와놓고(=Caching), CPU가 필요할 때 RAM보다 우선적으로 접근함.Cache Hit이 많으면 시스템의 성능이 올라가겠지만 Cache Miss가 많으면 추가 Latency가 발생해 오히려 Cache Memory가 없는 시스템보다도 시스템의 성능이 떨어질 수 있음.따라서 Cache Hit Ratio를 향상시키는 게 중요함(향상 기법 설명).RAM(Random Access Memory) (참고: 1, 2, 3, 4)개요 및 특징CPU가 즉각적으로 접근할 수 있으며, 프로그램 실행과 데이터 처리를 위해 일시적으로 명령어나 데이터를 저장하는 휘발성 메모리 장치(by ChatGPT 4.5).Stack, Heap, Code, Data 영역으로 구성되어 있어 각 영역이 가상 메모리(Virtual Memory)를 통해 각 프로세스에 할당됨.CPU에서 직접 접근이 가능한 유일한 저장 장치임.RAM의 종류RAM의 구성요소OS의 RAM 관리 방법메모리의 주소 공간(Address Space) (참고: 1, 2, 3, 4)관리의 최소 단위를 주소(Address)라 하며, 1 byte(8 bits)의 크기를 가짐.1 byte 단위마다 지정된 각 주소는 편의상 0x??????(16진수)로 표시됨(참고).RAM에서는 논리(가상) 주소와 물리(절대) 주소로 주소 공간을 분리하여 관리함.왜 이렇게 구분? OS 영역 침범 방지 + 메모리 관리의 편의성물리 주소(Physical Address) (※ 절대 주소(Absolute Address)라고도 함) (참고)CPU 관점에서 바라 본 실제 HW상 주소 공간으로, CPU 속 MMU가 논리 주소를 물리 주소로 변환하여 접근함(참고).경계 레지스터(Boundary Register)가 유저 프로세스가 RAM의 커널 영역을 침범하는지 감시하다가, 침범했다면 강제 Shutdown시킴(참고).논리 주소(Logical Address) (※ 가상 주소(Virtual Address)라고도 함)각 유저 프로세스 관점에서 바라 본 주소 공간으로, 각 주소마다 0x0부터 시작함.각 프로세스마다 새로 할당되므로 시스템 전체(OS) 관점에서 보면 같은 주소가 여러 개 존재할 수 있음.OS 영역과 유저 영역으로 구분되어 있음.OS는 프로세스 생성 및 메모리 할당 시 가상 주소-물리 주소쌍이 담긴 페이지 테이블(Page Table)을 만들어 RAM에 저장함(참고).프로세스 실행 시 CPU는 P.T의 맵핑 정보를 참고하여 명령어나 데이터를 참조함.상대 주소(Relative Address)는 프로세스 내에서 특정 주소 기준으로 얼마 떨어진 주소를 가리킬 때 사용하는 개념으로, 강의에서의 설명과는 소폭 다름(참고).메모리 할당 방식 (참고: 1, 2, 3)개요RAM의 빈 물리 주소 공간에 각 프로세스의 가상 주소 공간을 할당·관리하는 방법.연속적인 Swapping, Context Switching 상황에서도 최소한의 빈 공간과 Overhead를 유지하는 것이 메모리 할당 방식 연구의 목표.메모리 오버레이(Memory Overlay) (참고: 혼공컴운 391p., 2, 3, 4, 5)프로그램을 여러 개의 독립된 모듈로 나누고, 한 번에 필요한 모듈만 메모리에 적재하여 실행하는 방식(참고).Manual Overlay에서 Dynamic Loading과 Dynamic Linking으로 발전함.위 기술들은종류가변 분할각 프로세스에 메모리를 프로세스 크기만큼 연속 할당하는 방식.외부 단편화로 인한 Overhead 발생고정 분할각 프로세스에 메모리를 특정 크기만큼 연속 할당하는 방식.구현이 쉽고 오버헤드가 적다 vs. 내부 단편화 발생버디 시스템짬뽕비휘발성 메모리(Non-volatile Memory)Secondary Memory (참고: 1, 2, 3) [Day 10]데이터 지향 설계(Data-Oriented Design) (참고: 1, 2, 3)소프트웨어를 설계할 때 데이터 자체와 그 흐름에 초점을 맞추어, 프로그램의 성능과 메모리 사용 효율을 극대화하는 방법론(by ChatGPT-o3-mini-high).프로세서 캐시(cache) 효율을 높이고, 불필요한 메모리 접근 오버헤드를 줄이며, 데이터 처리 속도를 극대화하는 것이 목표.데이터를 배열에 담아 특정 인덱스 데이터를 호출하면 Cache Locality에 따라 해당 인덱스와 인접한 데이터들이 캐시 메모리에 올라감.CS를 공부하면 새로운 라이브러리/프레임워크를 배우기 쉽다.https://dev.epicgames.com/community/fortnite/getting-started/uefn [Week Review]일주일 동안 공부하면서 배우고 느낀 점감자님의 운영체제 강의는 너무 좋다. 눈에 쏙 들어오고 이해도 잘 된다. 하지만 엉성하게 감이 잡힌 상태에서 그 이상을 궁금해하기 시작하면 지옥이 펼쳐진다....예를 들어 (이후에 나오는지는 모르겠지만) IPC는 강의에서 주로 다룬 공유 메모리 방식 말고도 파이프 방식도 있는데, 이에 대해 검색하니 뭐 데이터스트림이라느니 Message Passing 방식이라느니 알 수 없는 내용들이 쏟아진다.이 강의(워밍업 클럽)로 큰 줄기를 그린 다음 오랜 기간에 걸쳐 꾸준히 학습하며 디테일을 채워 나가야겠다. 나는 비전공자인데다, 머리도 나쁘고, 근육병에, 기초수급자에다, 남들은 당분간 알아주지 않을 길을 오래 걸어가야 하니까.자료구조 및 알고리즘을 공부하니 프로그램 설계 능력 향상에도 도움이 되는 것 같다.잡식으로 필요한 것 혹은 필요해 보이는 기술 같은 것들만 공부하며 버텨온 시간들을 뒤로 하고 내실을 다지고자 별 기대 없이 시작한 워밍업 클럽인데, 의외로 소프트웨어 설계에 큰 도움이 되는 듯하다.이번 주 중간점검 때는 질문할 게 별로 없었다. 궁금한 게 없어서가 아니라 뭐부터 질문해야 할지 모를 정도로 머릿속이 혼란스러운 게 첫째, 궁금한 것들이 대부분 감자님 강의에 없는 내용들이라는 점이다.어제 중간점검 때 감자님께서 "강의 내용 정도면 컴공 전공자들이 배우는 지식과 크게 다르지 않다."고 말씀하셨는데, 내가 전공자가 되어보진 않았어도 "그건 아니다."라고 단언할 수 있다. 내 목표가 전공ㅈ어려웠던 점(참고) IPC 부분을 조금 깊이 파고들다 보니 강의에 설명되지 않은 부분이 정말 많아서 혼란이 심했다.특히 Process Synchronization 문제와 그 해결 방식들에 대해 공부한 후에, "그래서 저 수많은 IPC 방법들 중 Process Synchronization 문제는 어떤 방법을 쓸 때 발생하는 거지?"가 헷갈렸다.감자님 답변으로 "어떤 방법을 쓰는가보다는 공유자원의 존재 유무로 동기화 이슈가 발생할 수 있다"는 걸로 대강 이해했다.(참고) 동기화 부분을 정리하면서 강사님께서 말씀하시는 동기화 문제가 공유 메모리 방식에서 주로 발생하는 것 같다고 이해했다. 근데 다른 강사님의 강의에서 "파일 기반 IPC는 OS가 필요한 용량을 할당해줄 때 기준이 느슨한데, 메모리 기반 IPC는 OS가 필요한 용량을 할당해줄 때 기준이 엄청 깐깐하다."는 말이 나왔고, 왜 그런 차이가 나는지 궁금해져서 질문을 올렸다.답변에 틀린 부분은 없었지만 뭔가 명쾌한 느낌도 아니었다. 그래서 챗지피티에게 물어보니 메모리 할당 방식과 동기화 문제 발생 가능성을 이유로 설명했다. 이 답변을 바탕으로 정리에 두었더니 훨씬 명확해졌다.IPC를 공부할 때 통신 과정을 순서대로 정리해두니 확 이해도 되고 머릿속에 남는 것 같다!앞으로 개선할 점아무리 열심히 공부하기 위한 목적이라지만... 이거 공부 및 정리에 너무 많은 시간을 쓰고 있다. 기본적인 걸 무조건 끝내놓고 남는 시간에 내용 보충을 해야겠다. 기타 잡담강의 보면서 웃겼던 부분ㅋㅋㅋㅋㅋㅋ 빌린 돈도 안 갚아놓고 더 빌려 달라니 뭔 심보여
알고리즘 · 자료구조
･
알고리즘
･
운영체제
2025. 03. 09.
0
인프런 워밍업 클럽 스터디 3기 - CS 전공지식(자료구조 & 알고리즘) <첫째 주 미션>
1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.저라면 해시 테이블(Hash Table)을 사용하겠습니다. 교실의 학생들은 번호가 있기 때문에 해당 번호를 키로 빠르게 삽입/탐색/삭제가 모두 가능하기 때문입니다. 아래는 직접 구현해 본 코드입니다. 2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.기본적으로는 FIFO로 작동하는 큐(Queue)가 적절할 것 같습니다. 하지만 중간에 주문이 취소되거나 고객이 배달 요청 시간을 늦춰달라는 등 현실에는 여러 변수가 있을 수 있으므로 이중 연결 리스트(Doubly Linked List)를 활용해 변수에 빠르게 대처할 수 있을 것 같습니다.3. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요. 4. 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요.
알고리즘 · 자료구조
･
알고리즘
･
자료구조
2025. 03. 09.
0
인프런 워밍업 클럽 스터디 3기 - CS 전공지식(운영체제) <첫째 주 미션>
1. 아래 코드는 1초마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링 방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?while(true) { wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }인터럽트(Interrupt) 방식을 이용하면 성능을 개선하여 문제를 해결할 수 있을 것 같습니다. 인터럽트(Interrupt) 방식이란 I/O Device의 I/O 인터럽트 신호가 발생하면 CPU의 인터럽트 컨트롤러가 이를 받아 콜백 함수를 실행시킴으로써 이벤트를 처리하는 방식을 말합니다. 문제에 이 방식을 적용한다면 다음과 같이 구현할 수 있을 것 같습니다.function onSkillActivated(callback) { console.log('스킬 활성화를 기다리는 중...'); setTimeout(() => { callback(); }, 5000); } function handleSkillActivation() { console.log('스킬 활성화'); } onSkillActivated(handleSkillActivation);2. 프로그램과 프로세스가 어떻게 다른가요?둘의 차이는 메모리에 할당되어 있는지 여부에 있습니다. 프로그램은 코드 및 데이터가 저장장치(HDD, SSD)에 들어 있는 경우로, 자기 코드가 실행되기를 기다립니다. 사용자가 exe 파일을 실행하는 등 프로그램을 실행하면 프로세스가 생성되어 메모리 할당, PCB 설정 등의 작업을 거쳐 대기 상태로 들어가고, 이후 Ready Queue에 있다가 CPU 스케줄러에 의해 CPU 리소스를 할당받게 됩니다. 이렇게 Running 상태에 들어가면 연산, 시스템 콜 호출 등 하드웨어 자원에 대한 일시 통제권을 갖고 필요한 처리를 할 수 있게 됩니다.3. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?둘의 차이는 메모리 관점에서 보느냐, CPU 관점에서 보느냐에 따라 달라집니다. 멀티프로그래밍(Multi-programming)은 메모리 위에 여러 프로세스가 동시에 올라간 상태(=Running 상태)로 동작하는 방식이며, 멀티프로세싱(Multi-processing)은 단일 CPU 코어가 특정 프로세스를 정해진 Time Slice만큼 처리하는 시분할(Time-Sharing) 처리 방식을 말합니다. 현대 OS는 두 방식을 동시에 지원하므로 둘은 상호배반적인 개념이 아닙니다.4. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요? (질문이 다소 불분명하게 생각되어 두 가지로 답변하겠습니다.)1. '프로세스 관리'를 특정 프로세스에 대한 CPU 리소스의 할당 및 제거로 볼 때CPU Scheduling을 사용합니다. CPU Scheduling이란 Context Switching을 통해 적절한 스케줄링 알고리즘에 따라 Ready Queue 또는 Device Queue에 있는 PCB를 꺼내 Dispathing하는 것입니다. 리소스 사용률 향상, 오버헤드 최소화, 공평성 극대화, 처리량 증대, 대기시간 및 응답시간 최소화 등 다양한 목표를 만족하는 스케줄링 알고리즘을 환경에 맞게 적절히 활용하는 것이 핵심입니다.2. '프로세스 관리'를 컨텍스트 스위칭의 관점에서 볼 때PCB(Process Control Block)를 활용합니다. PCB(Process Control Block)란 특정 프로세스의 여러 정보를 포함하는 자료구조입니다. OS는 생성된 프로세스를 연결 리스트 형태인 PCB로 저장합니다. PCB에는 포인터, 프로세스 상태 정보, 프로세스 ID 등 Context Switching 시 멀티태스킹 처리의 안정성을 담보하는 데 도움이 되는 정보가 들어 있습니다.5. 컨텍스트 스위칭이란 뭔가요?컨텍스트 스위칭(Context Switching)이란 프로세스 전환(=멀티태스킹)을 위해 프로세스 상태값(=CPU 레지스터 값)을 PCB 형태로 Ready Queue 또는 Device Queue에 저장 및 불러오기하는 과정을 말합니다. Time Slice가 너무 짧아 Context Switching이 너무 자주 일어나면 Context Switching Overhead가 발생할 수 있으므로, 적절한 CPU Scheduling 알고리즘을 통해 적절한 Time Slice를 설정하거나, Thread Context Switching, Lazy Context Switching 등을 통해 오버헤드를 완화·개선할 수 있습니다.
시스템 · 운영체제
･
운영체제
2025. 03. 04.
0
인프런 워밍업 클럽 스터디 3기 - CS 전공지식 <첫째 주 발자국>
[Day 01]Data Structure자료구조란 데이터가 어떤 구조로 저장되고, 어떻게 사용되는지 나타낸 것.실행 속도가 빠르고, 메모리 차지가 적으며, 유지보수가 쉬워야 좋은 자료구조.시간복잡도(Time Complexity)컴퓨터 프로그램의 입력값과 연산 수행 횟수의 상관관계를 나타내는 추상적 성능 척도.알고리즘의 대략적 성능 증가/감소 경향성을 판단을 목표로 하므로 부가 사항은 배제함.배제 요소: 시스템 연산 성능 및 연산 1회당 연산량, 최고차항 외 항 등.점근적 표기법(Asymptotic Notation)함수를 단순화하여 함수의 증가율을 다른 함수와의 비교로 표현하는 방법으로, 다음 세 가지 표기법이 존재함.종류Big-O Notation알고리즘의 점근적 상한(Asymptotic Upper Bound)을 표시하는 표기법."이 표기법은 최악의 경우를 고려할 때만 사용한다." -> X알고리즘 성능 평가의 목적 및 프로젝트 실행 환경에 따라 적합한 표기법을 취사 선택하는 것이 중요!무슨 일이 벌어질지 모를 현실 세계에서 가장 많이 고려되는 표기법임.Big-Θ Notation알고리즘의 점근적 상한/하한(Asymptotic Tight Bound)을 동시에 표시할 수 있는 표기법.어떤 케이스에도 상한과 하한이 동일할 때 사용할 수 있음.ex) 순차 탐색(Linear Search), 이진 탐색(Binary Search) 등Big-Ω Notation알고리즘의 점근적 하한(Asymptotic Lower Bound)을 표시하는 표기법.현실의 문제 해결적 목적보다는 알고리즘 이론과 성능의 본질적 한계 분석 및 입증, 즉 개선 한계 분석의 중요한 근거가 된다는 데 의의가 있음. (by ChatGPT 4.5)Algorithm알고리즘이란 어떤 문제를 해결하기 위한 확실한 방법.데이터의 개수나 반복 횟수 등이 달라져도 같은 조건이면 동일하게 적용되는 것이 좋은 알고리즘.Operating SystemOS는 프로세스(Process), 메모리(Memory), 하드웨어(Hardware), 파일 시스템(File System)을 관리함.겁나 비싼 CPU를 최대한 뽑아먹기(?) 위해 Single-stream Batch System -> 시분할(Time Sharing)로 발전함(참고).응용 프로그램은 (보통의 경우) 표준 API를 통해 시스템 콜에 접근함(안전성, 편의성 Up)(참고:1, 2)우리가 흔히 보는 플러그 앤 플레이는 커널에 연결한 장치의 드라이버가 내장되어 있어서임.컴퓨터 구조 관련대표적인 컴퓨터 설계폰 노이만 구조(von Neumann Architecture) (참고: 1, 2) (여담: 1, 2)John von Neumann이 1945년에 설계한 프로그램 내장(Stored Program) 방식 컴퓨터 아키텍쳐로, 더 이상 물리 회로 변경 없이 CPU 명령어를 전환할 수 있게 됨.von Neumann Model, Princeton Architecture라고도 함.CPU, Bus, Memory, I/O Device로 이루어져 있음.메모리 내부에 명령어와 데이터를 동시에 저장하므로 병목현상(Bottleneck)(=메모리 속박 문제)이 발생할 수 있음.명령어 병렬 처리 방식(SMP, MPP 등)을 쓰거나 아예 새로운 하버드 구조로 해결 가능함.하버드 구조(Harvard Architecture) (참고: 1, 2, 3)폰 노이만 구조에서의 단일 Bus를 명령어용/데이터용 Bus로 물리적으로 분리하여 명령어와 데이터에 동시에 접근할 수 있도록 설계된 컴퓨터 아키텍처.ARM9, Xscale, RISC 마이크로 프로세서, DSP 등이 여기 속함.초기 하버드 구조는 명령어용 메모리와 데이터용 메모리를 분리했으나, MHA에서는 CPU와 RAM 사이에 캐시 메모리를 두어 병목을 개선함.컴퓨터 발전에 따라 CPU와 I/O 장치 간 처리 속도 차가 심해졌고, 그 간극을 메우고자 CPU에 인터럽트 컨트롤러를 추가해 I/O 장치의 인터럽트 신호를 받아 비동기적으로 처리할 수 있게 됨.참고1: 인터럽트 컨트롤러가 최초로 추가된 컴퓨터 UNIVAC 1103A(위키피디아, 사진).참고2: Polling vs. Interrupt in Super Mario참고3: CPU는 어떻게 작동할까?참고4: 인터럽트 서비스 루틴(ISR, Interrupt Service Routine) [Day 02]Data Structure배열(Array): 메모리의 특정 크기의 연속된 공간을 미리 할당받는 자료구조.특징은? 위 내용 보고 생각해 보기!JS의 배열은 정확히는 배열이 아니라, 객체(Object)의 한 형태(idx가 키!).Python의 List는 동적 배열(Dynamic Array)로, 새 배열 생성 없이 데이터 추가 O.연결 리스트(Linked List): 각 노드(Node)에 각 데이터를, 불연속적인 메모리 위치에 저장하고 이들을 포인터(Pointer)로 연결한 자료구조.특징은? 위 내용 보고 생각해 보기!자료구조 구현 시 추상 자료형(Abstract Data Type) 구현 후 그걸 코드화한다고 생각하면 쉬움.이거 완전 Pseudocode랑 비슷하지 않나?구현하기첫 번째 구현: 강의 보며 구현 (Done)두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현 (Done) 세 번째 구현: 아무것도 안 보고 구현 마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링) Operating System프로그램은 수동적(=자기 코드가 실행되기를 기다림), 프로세스가 되면 능동적(=리소스를 주도적으로 활용함)임!프로그램이 실행되어 메모리에 올라가 프로세스로 바뀌는 과정을 인스턴스화(Instantiation)라고도 함.프로세스는 Code, Data, Heap, Stack 영역으로 이루어져 있음(참고: 1, 2).메모리 용량이 작던 과거엔 유니프로그래밍을 활용할 수밖에 없었는데, 이때 스와핑(Swapping)을 통해 멀티프로세싱을 간접적으로 활용했음.스와핑을 통한 멀티프로세싱은 동시에 여러 개를 처리하는 것처럼 보일 뿐이지, 멀티프로세싱이라 할 수 없지 않나?강의가 틀렸었다! 강의에서 설명한 건 멀티태스킹(Multitasking)이었다.발전 순서: 멀티프로그래밍 -> 멀티태스킹 -> 멀티프로세싱임(참고: 1, 2).OS는 멀티태스킹 처리의 안정성을 담보하기 위해 생성된 프로세스를 연결 리스트 형태인 PCB(Process Control Block)로 커널 영역(Kernel Space)에 저장함(참고: 1, 2).프로세스 상태(Process State)프로세스는 시분할(Time-Sharing) 처리를 위해 New(생성), Ready(준비), Waiting(대기), Running(실행), Terminated(완료) 상태를 가짐. [Day 03]Data Structure 스택(Stack): FILO 원칙을 따르는 자료구조로, 후입선출이기만 하면 자료 형태는 상관 없음.ex) Undo 기능, Syntax Checker, 재귀 알고리즘 등Redo는 어떻게 구현하는 걸까? -> Undo한 작업을 Redo 스택에 저장해두었다가 다시 실행할 수 있도록 함. 구현하기첫 번째 구현: 강의 보며 구현 (Done)두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현 세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현 네 번째 구현: 아무것도 안 보고 구현 마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링) 큐(Queue): FIFO 원칙을 따르는 자료구조로, 선입선출이기만 하면 자료 형태는 상관 없음. ex) 메세지 큐(Message Queue), FIFO 스케줄링, 프린터 스풀러(Printer Spooler)등큐를 Linked List 기반으로 구현할 때는 양방향 연결 리스트 기반으로 구현해야 빠름!참고: 오늘의 영어단어 - queue 구현하기첫 번째 구현: 강의 보며 구현 (Done)Line 72~74를 왜 Line 56 조건에 넣지 않고 뺀 걸까? 새 노드를 테일 노드 뒤에 넣으면 무조건 새 노드를 테일로 만들어야 하는데.여기서 답변을 주셨지만 사실 저걸 봐도 이해가 안 된다...ㅎ 변수 할당할 땐 뒤에서부터 앞으로 생각하는 게 편한 것 같다!ex) this.tail.next = newNode; --> newNode를 테일 다음 노드에!두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현 세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현 네 번째 구현: 아무것도 안 보고 구현 마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링) 덱(Deque): FILO / FIFO를 자유자재로 선택 가능한 자료구조로, Double-ended queue의 약자임.ex) 토마토, 웹 브라우저 히스토리, A-Steal(Job-Steal) 알고리즘 등구현하기첫 번째 구현: 강의 보며 구현 두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현 세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현 네 번째 구현: 아무것도 안 보고 구현 마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링) Operating SystemContext Switching: 프로세스 전환을 위해 프로세스 상태값 저장, 불러오기하는 것.시분할(Time-Sharing) 시스템에서 멀티태스킹을 안정적으로 수행하기 위해 필요한 필수 과정.인터럽트 -> CPU 레지스터 PCB A에 저장 -> PCB B의 레지스터 값 CPU에 적용 -> 프로세스 B 상태 전환 순서로 진행됨.Time Slice가 너무 짧아 C.S이 너무 자주 일어나면 Context Switching Overhead가 발생할 수 있음(참고: 1, 2).프로세스 생성 및 종료부팅 후 첫 프로그램 실행 시 부모 프로세스가 생성되며, 자식 프로세스는 이를 복제(fork)하여 생성됨.프로그램의 코드 영역과 데이터 영역을 메모리에 로드 -> 빈 힙과 스택 생성 -> PCB init강의에서 나온 fork()는 UNIX 계열(Linux)의 생성 방식이며, Windows 환경에서는 부모 프로세스 복사 없이 CreateProcess() 함수를 통해 독립적으로 생성함.exec() 함수로 자식 프로세스의 코드/데이터 영역을 덮어씀으로써 독립된 프로세스로 동작함.부모 프로세스는 자식 프로세스가 exit() 신호를 보내기 전에는 C.S이 일어나도 CPU를 할당받지 않음.부모 프로세스가 자식 프로세스의 종료 상태(exit status)를 확인할 수 없어(예: 부모의 조기 종료, 부모의 wait() 누락 등) 메모리에서 제거되지 않은 프로세스를 좀비 프로세스(Zombie Process)라고 함.(일반적으로는) Windows 환경에선 부모와 자식이 독립적이므로, 부모 프로세스가 자식 프로세스의 종료 상태(exit status)를 확인할 수 없어도 커널이 해당 프로세스를 완전히 제거함.쓰레드(Thread) (참고: 1, 2)프로세스 내의 단일 시퀀스 스트림(A single sequence stream)으로, 코드/데이터 영역과 힙을 공유함(스택은 독립 할당).쓰레드에게 할당된 독립 공간은 스택도 있지만 TLS(Thread Local Storage)도 있음.OS는 TCB(Thread Control Block) 내 각 쓰레드의 ID를 통해 각 쓰레드를 개별적으로 관리함.메모리 소모가 적고, 쓰레드 간 통신 속도가 빠르다는 장점과 안정성이 낮다는 단점이 있음. [Day 04]Data Structure해시 테이블(Hash Table): 해시 함수(Hash Function)를 통해 데이터를 Key, Value 형태로 저장하는 자료구조.해시 충돌(Hash Collision)이 나면 Chaining, Open Addressing 등을 통해 해결할 수 있음.해시 함수를 통과한 데이터는 특정 범위에 속한 정수(=해시)로 변환하며, 이를 키(=인덱스)로 데이터를 할당함.하지만, 해시 테이블 이외 상황에서는 해시 함수 통과 시(=해싱) 고정된 길이의 데이터로 변환됨.구현하기첫 번째 구현: 강의 보며 구현 (Done)두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현 세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현 네 번째 구현: 아무것도 안 보고 구현 마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링) Operating SystemCPU 스케줄링(CPU Scheduling)개요특정 프로세스에게 CPU 리소스를 할당/제거하는 OS(=스케줄러)의 역할.리소스 사용률 향상, 오버헤드 최소화, 공평성 극대화, 처리량 증대, 대기·응답시간 최소화 등을 목표로 함.모든 목표를 동시에 달성할 순 없으므로, 현대 컴퓨팅 환경에서는 OS의 지향점에 따라 여러 스케줄링 알고리즘을 바꿔가면서, 또는 복합적으로 사용함(예).프로세스 상태 전이(Process State Transition) (참고: 1, 2, 3, 4)승인(Admit)인스턴스화된 프로그램, 즉 프로세스가 New 상태에서 Ready 상태로 전환되는 것.빈 Code, Data, Heap, Stack 영역과 Thread 1개, 그리고 PCB가 생성되어 커널에 저장됨.디스패칭(Dispatching)Ready 상태 프로세스의 PCB가 Ready Queue에 있다가 우선순위에 따라 CPU 스케줄러(=OS)에 의해 실행 상태로 전환되는 것.Deadlock Avoidence의 은행원 알고리즘(Banker's Algorithm)이 여기서 작동함(Day 07 참고).깨우기(Wake-up)Waiting 상태의 프로세스가 Ready 상태가 되고, 해당 PCB도 커널의 Ready Queue로 이동함.Device Queue 내 I/O 작업 종류별로 우선순위가 결정됨.대표적인 CPU 스케줄링 알고리즘FIFO Scheduling (※ FCFS(First Comes, First Served) Algorithm이라고도 함)스케줄링 큐에 들어온 순서대로(FIFO), 프로세스를 하나씩 실행하는 최악의 알고리즘.프로세스 간 우선순위에 따라(Burst Time이 긴 게 먼저 vs. 짧은 게 먼저) 평균 대기 시간 차이가 확 남.FIFO Scheduling은 비선점형 스케줄링(Non-preemptive / Cooperative Scheduling)에 해당하므로,Convoy Effect(호위 효과)가 발생할 수 있음. [Day 05]Data Structure셋(Set): 데이터의 중복을 허용하지 않는 자료구조.구현하기첫 번째 구현: 강의 보며 구현 (Done)두 번째 구현: 강의 안 보고 구현하다 기억 안 나면 강의 확인하며 구현 세 번째 구현: 강의 안 보고 구현하다 기억 안 나면 과거에 내가 짠 코드 확인하며 구현 네 번째 구현: 아무것도 안 보고 구현 마지막 구현: 익숙한 파이썬으로 구현(+ 리팩토링) Operating SystemSJF(Shortest Job First) Scheduling: Burst Time이 짧은 프로세스를 우선 실행하는 알고리즘.각 프로세스의 Burst Time 예측 불가능성, Burst Time이 긴 프로세스는 영영 실행되지 못할 수도 있는 점(=Starvation) 때문에 RR로 빠르게 대체됨.RR(Round Robin): FIFO 스케줄링에 Time Slice(Time Quantum)를 추가한 알고리즘.FIFO랑 다름 없거나, C.S에 의한 오버헤드가 너무 크지 않도록 최적의 TS(TQ)를 찾는 것이 매우 중요함!참고: Scheduling Algorithms - Round Robin Scheduling MLFQ(Multi Level Feedback Queue): 프로세스마다 최적의 TS(TQ)를 할당해 최적의 리소스 사용률 및 응답 속도를 보장하는 알고리즘.인터럽트가 일어난 프로세스의 TS는 낮추고, 스케줄링이 일어난 프로세스의 TS는 높임.
알고리즘 · 자료구조
･
자료구조
･
알고리즘
･
운영체제