[인프런 워밍업 클럽 4기 - CS] - 1주차 미션 (컴퓨터 구조)

문제1. 4입력 AND, OR, NAND, NOR, XOR 연산의 진리표를 작성해보세요.(3입력 AND게이트의 예)| A | B | C | D | AND | OR | NAND | NOR | XOR | | --- | --- | --- | --- | --- | --- | ---- | --- | --- | | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |AND: 모든 값이 1일 경우에만 1OR: 하나의 값이라도 1이면 1NAND: AND 반대NOR: OR 반대XOR: (((A ⊕ B) ⊕ C) ⊕ D) > 두 입력이 같으면 0, 다르면 1 2.다음 불 방정식들을 여러 방법을 이용해 간략화 해보세요.1. A( (BB)’+ 0A) + (CC)' = (AB’) +C ㄴ A( (B)’+ 0A) + (C)' : 동일 법칙 ㄴ A(B’) + (C)' : 항등원 ㄴ AB’ + C’ 2. (B’B’) + (AD’ + (CA)’)D = B’ + (DC’) + (DA’) ㄴ (B’) + (AD’ + (CA)’)D : 동일 법칙 ㄴ (B’) + (AD’ + C’+ A’)D : 드모르간 법칙 ㄴ B’ + DC’+ DA’: 항등원 3. (A’B) + B(B1 + BC) = B ㄴ (A’B) + B(B + BC): 항등원 ㄴ (A’B) + B(B) : 흡수법칙 ㄴ (A’B) + B: 동일법칙 ㄴ B(A’ + 1): 결합법칙 ㄴ B(1): 항등원 ㄴ B 4. B’(1C + BD) + DB = (B’C) + (DB) ㄴ B’(C + BD) + DB = 항등원 ㄴ B’C + B’BD + DB = 분배법칙 ㄴ B’C + DB = 보완법칙다음 2진수를 10진수로 변환해보세요.1. 110111 = 1 + 2 + 4 + 16 + 32 = 55 2. 10000001 = 1 + 128 = 129 3. 11111100000 = 32 + 64 + 128 +256 + 512 + 1024 = 2016 4. 101010 = 2 + 8 + 32 = 42다음 10진수를 2진수로 변환해보세요.1. 10 = 1010(2) - 10/2 = 5 ...0 - 5/2 = 2...1 - 2/2 = 1...0 - 1/2 = 0...1 2. 27 = 11011(2) - 27/2 = 13...1 - 13/2 = 6...1 - 6/2 = 3...0 - 3/2 = 1...1 - 1/2 = 0...1 3. 86 = 1010110(2) - 86/2 = 43...0 - 43/2 = 21...1 - 21/2 = 10...1 - 10/2 = 5...0 - 5/2 = 2...1 - 2/2 = 1...0 - 1/2= 0...1 4. 516 = 100000100(2) - 516/2 =258...0 - 258/2 = 129...0 - 129/2 = 64...1 - 64/2 = 32...0 - 32/2 = 16...0 - 16/2 = 8...0 - 8/2 = 4...0 - 4/2 = 2...0 - 2/2 = 1...0 - 1/2 = 0...1다음 불 방정식을 logisim을 이용해 회로를 만들어보세요.(회로 이미지와 .circ파일 첨부)1. (B’C) + (DB) 2. (AB’) +C 3. B’ + (DC’) + (DA’) 1. (B’C) + (DB)2. (AB’) +C3. B’ + (DC’) + (DA’)후기불 대수나 불 연산에 대해서 개념을 공부할 때는 크게 와닿지 못하였고 외우기 바빴지만 직접 미션을 통해서 작업해보고 불 대수에서 나온 여러 법칙들이 왜 사용되게 되는지 흐름을 이해할 수 있었다. 또한 직접 프로그램을 통해 회로를 연결해보는 경험이 불 연산을 더 깊이 체감해볼 수 있는 경험이 되었다.

[인프런 워밍업 클럽 4기 - CS] - 1주차 미션 (자료구조와 알고리즘 심화)

문제Python, JavaScript, C# 같은 언어는 가비지 컬렉터를 이용해 메모리를 자동으로 정리하는 매니지드 언어(Managed Language)에 속합니다.매니지드 언어의 가비지 컬렉터는 개발자가 메모리를 요청하면 운영체제의 힙 영역에 할당하고, 더 이상 필요하지 않을 때 자동으로 해제하며 메모리를 관리합니다.여러분이 속한 회사에서 새로운 매니지드 언어를 개발 중이며, 여러분은 가비지 컬렉터 개발을 담당하게 되었습니다.특히 메모리 검색 부분을 맡게 되었는데, 사용자가 특정 크기(Byte)의 메모리를 요청하면 사용 가능한 메모리 중 가장 적절한 크기를 찾아 반환하는 GarbageCollector 클래스를 구현해보세요.(같은 크기의 메모리는 없다고 가정)import { AVLTree } from "./avlTree.mjs" class GabageCollector{ } const gc = new GabageCollector(); console.log("========== 빈 메모리 영역 초기화 =========="); gc.insertFreeMemory(64); // 빈 64바이트 삽입 gc.insertFreeMemory(48); // 빈 48바이트 삽입 gc.insertFreeMemory(87); // 빈 87바이트 삽입 gc.insertFreeMemory(13); // 빈 13바이트 삽입 gc.insertFreeMemory(102); // 빈 102바이트 삽입 gc.insertFreeMemory(34); // 빈 34바이트 삽입 gc.insertFreeMemory(61); // 빈 61바이트 삽입 gc.insertFreeMemory(40); // 빈 40바이트 삽입 gc.insertFreeMemory(6); // 빈 6바이트 삽입 let freeMemory1 = gc.searchFreeMemory(64); // 64바이트 메모리 console.log(freeMemory1); if(freeMemory1){ gc.releaseFreeMemory(freeMemory1.data); } let freeMemory2 = gc.searchFreeMemory(42); // 48바이트 메모리 획득 console.log(freeMemory2); if(freeMemory2){ gc.releaseFreeMemory(freeMemory2.data); } 풀이import { AVLTree } from "./avlTree.mjs"; class GabageCollector { constructor() { this.tree = new AVLTree(); } // 노드 추가 insertFreeMemory(data) { this.tree.root = this.tree.insert(this.tree.root, data); } // 가장 인근의 노드 찾기 searchFreeMemory(data) { if (this.tree.root === null) { return null; } let currentNode = this.tree.root; let parentNode = null; while (currentNode !== null) { // 현재 노드가 찾고자 하는 데이터보다 작을 경우 오른쪽 서브트리로 이동 if (currentNode.getData() 문제에서는 총 세 가지 메서드를 구현하여야 했다.insertFreeMemory: 빈 메모리를 삽입할 수 있는 기능searchFreeMemory: 데이터를 할당할 수 있는 최소의 메모리 공간을 검색하는 기능3. releaseFreeMemory: 해당 메모리를 삭제할 수 있는 기능우선적으로 GarbaceCollector에서 메모리 영역은 하나의 AVL 트리로 다뤄진다고 생각을 하여서 this.tree 속성으로 AVL 트리를 생성해주었다. insertFreeMemory의 경우, AVL Tree에서 제공해주는 insert 메서드를 통해 트리의 root를 설정해주고 그 하위에 적절한 위치를 찾아서 각 노드를 삽입해주었다. releaseFreeMemory의 경우, 동일하게 AVL Tree에서 제공하는 remove 메서드를 통해 데이터를 찾아가며 해당 노드를 삭제하고 각 노드의 height나 unbalance한 노드의 균형을 잡아주었다. searchFreeMemory는 새롭게 기능을 추가하여야 하였다. 처음에는 단순하게 매개변수의 데이터 값과 일치하는 노드만 반환하면 될 줄 알았지만 문제에서 '사용 가능한 메모리 중 가장 적절한 크기' 를 반환해야 한다고 적혀있듯 매개변수로 받는 데이터 이상의 노드들 중 최소값을 가진 노드를 반환해야 했다.메서드를 작성하기 전에 먼저 예외처리를 하였다.AVL Tree의 루트 노드가 없을 경우매개변수로 받는 데이터가 모든 노드의 값보다 클 경우두 가지 경우에는 null을 반환하고 "매모리를 추가할 수 없습니다."라고 로그를 찍어주었다.그 외의 경우에는 이제 while문을 통해 가장 인접한 값의 노드로 이동을 시켜주었다.만약 현재 위치한 노드의 값이 찾으려는 데이터보다 작다면 우측 서브트리로 이동해주고,데이터보다 큰 노드를 발견하게 된다면 부모 노드를 미리 저장해주고 좌측 서브트리로 이동해주었다.부모노드를 저장해주는 이유는 좌측 서브트리의 노드를 데이터보다 작을 수도 있기에 반환해줄 수 있는 노드 변수를 만들어주었다.그렇게 while 문을 반복하다보면 현재 위치의 노드가 null이 나오게 되고 기저 조건을 벗어나서 결국 부모 노드에 저장된 노드값이 사용 가능한 메모리 중 가장 적절한 크기가 되며 부모 노드가 null이라면 아까처리한 예외 조건에 의해 로그가 찍히게 된다. 저번 기수보다 더 어려운 문제를 미션으로 출제하신다는 코치님의 말씀에 겁을 먹었었지만 막상 이렇게 실용적인 예제와 직접 구현을 해보면서 미션을 진행하다보니 기존에 배웠던 AVL Tree에 대해 더 자세히 익히게 되고 동작 방식이나 해당 자료구조에 대한 특징을 몸소 체험해볼 수 있었던 것 같다.

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

📕 자료구조와 알고리즘(심화)✅ P-NP문제가 어려운 지, 쉬운 지 혹은 해결이 가능한 지 불가한 지 판단하는 것.결정 문제: 참 혹은 거짓을 대답할 수 있는 문제최적화 문제: 최적의 해를 찾을 수 있는 문제 (대부분의 최적화 문제는 결정 문제가 된다)결정론적 튜링 머신: 다음 상태가 유일한(오직 하나의) 상태로 결정되는 것비결정론적 튜링 머신: 현재 상태와 기호에 대해 여러 개의 가능한 다음 상태가 존재할 수 있는 것 (현실에는 존재 X 가정으로 상상)다항 시간: 어떤 문제의 해결 시간을 다항식으로 표현이 가능한 것다항 시간 내 1. 상수 시간: O(1) 2. 로그 시간: O(log n) 3. 선형 시간: O(n) 4. 로그-선형 시간: O(nlog n) 5. 다항 시간: O(n^k) 다항 시간 외 1. 지수 시간: O(k^n) 2. 팩토리얼 시간: O(n!) P 문제: 결정문제에 대해 결정론적 튜링 머신을 통해 다항 시간 내에 답을 구할 수 있는 문제NP 문제: 결정문제에 대해 비결정론적 튜링 머신을 사용하여 다항 시간 내에 답을 구할 수 있는 문제NP Hard: 모든 NP문제들을 다항 시간 내에 어떤 문제 A로 환원이 가능한 것NP Complete: NP-Hard이면서 NP에 포함되는 문제결정론적 / 비결정론적 문제ex) 완전 이진 트리 형태로 되어 있고 깊이가 k인 갈림길에 하나의 리프에만 보물이 있다고 가정결정론적: 한 번씩 모든 길을 거쳐서 보물을 확인 > 최악의 경우 2^k의 시간이 걸린다.비결정론적: 갈림길을 마주할 때마다 분신술을 사용하여 동시에 모든 리프 확인 > k의 시간이 걸린다.어떠한 힌트가 주어지게 된다면 비결정론적 문제들은 결정론적 문제로 검증이 가능모든 결정론적 문제들은 비결정론적 문제들에 속함 (P⊆NP) ✅ 트리와 이진 트리트리: 하나의 노드에서 점차 내려가는 자료구조Edge: 각 노드를 연결하는 선루트 노드: 트리에서 최상위 노드터미널 노드: 자식 노드가 없는 노드인터널 노드: 터미널 노드를 제외한 노드서브 트리: 트리 구조 내에 작은 트리 (터미널 노드 또한 루트 노드만 있는 트리라고 판단)레벨: 각트리의 높이이진 트리: 각 노드는 최대 2개의 자식 노드를 갖는 트리포화 이진 트리: 트리의 최대 레벨에 있는 모든 터미널 노드가 꽉 찬 트리완전 이진 트리: 최대 레벨을 제외한 나머지 레벨에는 모두 노드가 존재하고 최대 레벨의 노드는 왼쪽부터 채워진 트리순회: 트리의 노드들을 순회전위: 루트 노드 먼저 순회중위: 루트 노드를 중간에 순회후위: 루트 노드를 마지막에 순회 ✅ 이진 탐색 트리이진 탐색 알고리즘: 정렬되어 있는 배열에서 반씩 나눠 탐색을 해가며 범위를 줄여나가는 알고리즘이진 탐색 트리이진 탐색은 정렬된 상태에서만 가능하며 배열의 경우 데이터 삽입, 삭제가 비효율적이다.해시 테이블은 데이터 조회, 삽입, 제거가 빠르지만 해시 함수에 따라 성능이 달라지고 데이터를 저장할 메모리가 필요하다.이진 탐색 테이블은 데이터 조회, 삽입, 제거가 빠르고 해시 테이블에 비해 메모리 사용량이 적다규칙자식 노드는 모두 이진 트리여야 한다.중복된 노드의 데이터는 없어야 한다.A 노드의 왼쪽 자식 노드값은 A 노드값보다 작아야 한다.A 노드의 오른쪽 자식 노드값은 A 노드값보다 커야 한다.자식 트리도 상위 규칙을 따라야 한다.평가:트리가 만들어졌을 때 : O(logn)트리가 잘 만들어지지 않을 때 : O(n)이진 트리는 균형을 유지하는 것이 성능에 중요삽입, 삭제 시 트리의 균형이 깨질 가능성이 크다.✅ AVL 트리이진 트리에서는 균형을 유지하는 것이 중요하다.규칙:왼쪽과 오른쪽 자식트리의 높이가 최대 1까지만 차이가 날 수 있다.균형이 맞지 않는 트리는 회전을 통해 균형을 다시 맞출 수 있다.(못 맞추는 경우도 존재)회전LL회전: 오른쪽으로 뻗은 트리에 대해 적용 가능RR회전: 왼쪽으로 뻗은 트리에 대해 적용 가능LR회전: 왼쪽으로 꺾였다가 안쪽으로 꺾인 트리 적용 가능RL회전: 오른쪽으로 꺾였다가 안쪽으로 꺾인 트리 적용 가능📕 컴퓨터 구조✅ 컴퓨터 구조블랙박스: 내부 작동 원리는 모르더라도 입력에 따라 출력이 예측 가능한 것들모듈화: 큰 문제를 작은 문제로 분할하여 복잡함을 단순화 시키는 방법역사:수동식 계산기- 주판기계식 계산기- 계산봉, 파스칼린, 라이프니츠 휠자동 계산기- 차분 기관(톱니바퀴로 계산 결과 활용), 해석 기관(프로그래밍 가능)디지털 계산기- ENIAC- 폰노이만 구조(중앙 처리 장치, 메모리, 입출력 장치)- 트랜지스터 (진공관 대체)- 집척 회로- ,,, 동작방식컴퓨터는 0,1로 이루어진 명령어만 해석이 가능하다.기계어: 0,1로 이루어진 명령어컴파일러: 정적 코드를 기계어로 변환하는 과정에서 에러 발견 가능하고 실행속도가 매우 빠름 (c, C++) / 변환 과정이 오래 걸림인터프리터: 한 줄씩 기계어로 변환하기에 프로그램 실행 도중 문법 오류 발생 가능, 실행 속도가 느림✅ 컴퓨터 구성 요소CPU:프로그램 카운터: 다음 실행할 명령어 저장제어 유닛: 명령어 해석 및 실행산술 논리 연산장치: 산술, 논리 연산을 수행레지스터: 용량은 적지만 속도가 빠른 CPU 내장 메모리버스: 데이터 전송 통로Memory:RAM(Random Access Memory): 어떤 메모리에 접근하여도 접근 시간이 동일하며 휘발성ROM(Read Only Memory): 쓰기가 불가하며 비휘발성이기 때문에 컴퓨터 동작을 위한 BIOS가 저장 1. CPU가 프로그램 실행 시, 코드와 데이터를 RAM에서 가져온다. 2. 연산에 필요한 데이터 레지스터 저장 3. 연산 이후 결과를 RAM에 저장 4. 자주 사용되는 데이터 CPU 내부에 캐시 메모리 저장 ( RAM) 주변 장치:입출력 장치1. 키보드 / 마우스2. 모니터 / 스피커 / 프린터보조기억 장치1. HDD / SSD32, 64bit 컴퓨터:1bit (0,1 표현) = 21byte = 8bit = 2564byte = 32bit = 약 42억8byte = 64bit = 약 18경플리플롭: 1비트를 저장할 수 있는 회로컴퓨터 비트에 맞춰서 레지스터와 버스의 비트 수가 맞춰짐- 64비트 -> 64비트 레지스터 / 64개의 버스비트 수에 따라 저장할 수 있는, 계산할 수 있는 한계가 정해짐RAM이 여러개를 갖고 있더라도 CPU에서 처리할 수 있는 한계가 있음컴퓨터의 성능은 클럭, 명령어 최적화, 메모리, 레지스터 속도가 중요✅ 불 대수디지털 장치들은 불 대수 기반으로 작동한다.true: 1false: 0 불 연산:NOT: 입력값의 반대AND: A와 B가 같을 때만 1 (논리곱)OR: A와 B중 하나만 1이면 1 (논리합)NAND: AND 연산의 반대NOR: 하나라도 1이면 1XOR: 하나만 1일 경우에만 1 (두 입력이 다를 때)불 대수의 성질과 법칙항등원:원산 결과가 자기 자신이 되는 수AND (⋅) / A ⋅ 1 = AOR (+) / A + 0 = A교환법칙: 피연산자의 순서를 바꿔도 결과는 동일하다A ⋅ B = B ⋅ A결합법칙: 괄호의 위치를 바꿔도 결과 동일(A ⋅ B) ⋅ C = A ⋅ (B ⋅ C)분배법칙A ⋅ (B + C) = A⋅B + A⋅C동일법칙: 동일한 값을 두 번 연산해도 원래 값A ⋅ A = A이중 부정법칙: 두 번 부정하면 원래 값으로 돌아감흡수법칙A(A + B)= AA + AB ← 분배법칙= A + AB ← AA = A (동일법칙)= A(1 + B). ← A로 묶음 (결합법칙의 역)= A(1) ← 1 + B = 1 (항등원)= A 드모르간 법칙AND = NOT A OR NOT BA NOR B = NOT A AND NOT B불 함수함수: 입력 값에 따라 출력 값이 변하는 것불함수: 입력 값과 출력 값 모두 boolean 진리표 변환결과가 0인 행은 제외(Don't care 행)모든 행을 AND 연산으로 만들고결과값에 맞춰서 수정✅ 비트10진법과 2진법1개의 비트로 표현할 수 있는 수의 개수 = 2^1개2개의 비트로 표현할 수 있는 수의 개수 = 2^2개3개의 비트로 표현할 수 있는 수의 개수 = 2^3개,,, 10진법 > 2진법 변환10진수를 2로 나눌 수 있을 때까지 나누는 것ex) 9 > 9/2 = 4...1 > 4/2 > 2...0 > 2/2 > 1...09(10) = 1001(2) 16진법0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F16진법을 사용하는 이유는 2진수를 10진법으로 표현하는 것보다 더 간단하기 때문16은 2^4이기 때문에 간단히 변환 가능11111111(2) = FF(16)Ox1001 => 16진수 표기법 빅 엔디안과 리틀 엔디안MSB: 가장 왼쪽 비트LSB: 가장 오른쪽 비트 빅 엔디안: MSB를 가장 낮은 주소부터 채우는 방식리틀 엔디안: LSB를 가장 낮은 주소부터 채우는 방식하나의 방식으로 통일해서 사용해야 함. 오버플로우와 인터럽트오버플로우: 값이 데이터 타입(또는 레지스터)이 표현할 수 있는 범위를 초과했을 때 발생하는 현상인터럽트: CPU가 실행 중인 작업을 중단하고 인터럽트 서비스를 실행 음수- 부호없는 정수 (양수만 표현 가능)0000 ~ 1111 = 0 ~ 15까지 16개 값 표현- 부호있는 정수 (양수, 음수 표현 가능)0000 ~ 1111 = -8 ~ 7까지 16개 값 표현MSB가 부호를 표현(0이면 양수, 1이면 음수) > 나머지 3비트로만 값 표현 가능예: +5 → 00000101 (8비트 기준)음수 표현 만들기 (예: -5)① 비트를 반전 (1의 보수): 11111010② +1 더함: 11111010 + 1 = 11111011 00000101 ( +5 ) + 11111011 ( -5 ) ----------- 00000000 → 결과: 0 후기직접 프로그램을 통해 불 연산을 시각화해볼 수 있다는 것이 가장 인상깊었다. 기존에는 논리 연산을 통해서 조건문을 작성할 때를 제외하고는 생각해본 적이 없었는데, 더 하위 레벨에서 불대수, 불함수, 그리고 불 연산에서 자주 사용되는 수학적인 법칙까지 직접 공부해보고 이를 통해 간단한 프로그램을 만들어 보는 경험이 어렵지 않으면서 가장 크게 체감을 할 수 있었던 것 같다. 자료구조와 알고리즘 또한 트리가 나오게된 배경부터 AVL 트리가 탄생하게 된 계기까지 그 흐름을 잘 따라갈 수 있었고 AVL 트리만의 특징과 균형을 잡기 위한 여러 회전 원리에 대해서도 탄탄히 공부해볼 수 있었다.

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

지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블정렬인접한 두 수를 비교하여 차례대로 자리를 바꿔나가며 정렬하는 방식시간복잡도: O(n^2)선택정렬선택된 정렬 영역에 정렬되지 않은 영역의 최솟값을 삽입시간복잡도: O(n^2)삽입정렬정렬되지 않은 영역의 첫 원소를 정렬된 원소들과 비교하여 올바른 위치에 삽입시간복잡도: O(n^2)병합정렬배열을 더 이상 나눌 수 없을 때까지 쪼개고(분할)다시 정렬된 상태로 병합(정복)재귀를 통해서 구현이 가능시간 복잡도 O(nlogn)퀵정렬배열 중 하나를 pivot으로 설정하고배열의 시작과 끝에서부터 pivot과 비교해가며 좌, 우로 정렬하고두 인덱스가 교차되면 pivot을 교차점이랑 교체재귀를 통해서 반복시간 복잡도 O(nlogn) - 최악의 경우 O(n^2)하지만 최악의 경우가 나올 확률이 거의 없고, 병합정렬보다 메모리 사용이 적기 때문에 더 좋은 알고리즘이라고 판단메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.메모리제이션이란 알고리즘 계산 과정에서 동일한 계산이 반복되어 실행되는 경우, 함수를 실행해가며 계산 값을 저장해두고 동일한 계산 실행 시 저장된 결과 값을 불러오며 계산하는 방식을 의미한다. 이 방법은 하향식 계산을 하며 중복되는 계산을 제거할 수 있기에 연산 속도는 빠르고 하향식 접근 문제에 대해 빠르게 풀이할 수 있다는 장점이 있지만 계산에 필요한 결과를 저장해두어야 함으로 메모리의 사용량이 크다는 단점이 있다.타뷸레이션은 상향식 계산 방식으로 모든 값을 자료구조에 저장해두고 계산에 필요한 결과 값을 불러오며 계산하는 방식을 의미한다. 반복적인 함수 호출이 없기 때문에 메모리에 큰 부담이 없으며 상향식 접근이 필요한 문제에 사용될 수 있다는 장점이 있지만 미리 모든 연산을 진행하여 저장해야 하기 때문에 불필요한 연산이 발생할 수 있다는 단점이 있다.'메모리가 부족한' 시스템에서 '재귀로 쉽게' 구현이 가능한 상황에서 문제를 해결하기 위해서는 타뷸레이션을 사용할 것 같다. 메모이제이션은 재귀로 쉽게 구현이 가능한 문제에 대해 이점을 발휘하지만 메모리의 사용이 크다는 단점으로 인해, 결국 메모리가 부족한 시스템에서 구현이 완료되어도 실행이 안된다면 의미가 없다고 판단하였다. 반면 타뷸레이션은 재귀로 문제를 푸는 것에 이점은 없지만 쉽지 않더라도 재귀가 아닌 상향식으로 문제를 접근하여 풀이할 수 있을 것이라고 생각한다. 📒 회고 미션을 통해서 강의를 통해서 공부했던 내용들을 전체적으로 복습해볼 수 있었으며 이번에도 실무적인 환경에서 실제로 고민해볼만한 주제를 받고 이에 대해 생각해볼 수 있는 시간을 가져서 좋았다. 아직 기초 수준의 자료구조와 알고리즘에 대해서 공부를 하였지만 꾸준히 문제를 풀어가면서 심화 알고리즘에 접근하며 실력을 키워나가고 싶다.

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

메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요. 레지스터CPU 내에 존재하며 가장 빠른 기억장치휘발성 메모리(컴퓨터가 종료되면 데이터가 사라짐)적은 용량, 높은 가격캐시레지스터와 메인 메모리의 속도 차이를 줄이기 위해 메인 메모리에서 미리 필요할 것 같은 데이터를 미리 저장휘발성 메모리L1 ~ L3 여러 개의 캐시로 구분메인메모리실제 운영체제와 프로세스가 저장되는 공간휘발성 메모라보조저장장치비휘발성 메모리(컴퓨터가 종료되어도 데이터가 사라지지 않음)프로그램, 파일 등을 저장 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?메모리의 운영체제 영역에 사용자 프로세스가 침범하게 되면 운영체제가 동작하지 않을 수도 있기 때문에, 경계 레지스터는 사용자 프로세스가 접근할 수 있는 메모리 영역을 제한하여 운영체제의 메모리에 침범하지 못하도록 보호하는 역할을 한다. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식은 프로세스의 크기에 따라 메모리를 분할하여 동적으로 할당하는 방식을 의미한다. 필요한 크기만큼 할당하기에 메모리의 활용도나 다양한 크기의 프로세스를 한 번에 저장할 수 있다는 장점이 있다. 단점으로는 분할된 공간이 일정하지 않아, 외부 단편화가 발생하고 비어있는 메모리가 많아진다면 조각 모음이 필요해진다는 단점이 있다. 세그멘테이션 또한 가변 분할 방식이며, 프로세스의 모듈을 세그먼트로 구분하여 필요한 모듈을 분리하여 메모리에 올려 관리할 수 있다는 장점이 있다. 고정 분할 방식은 메모리를 정해진 크기의 파티션으로 나누어 프로세스를 할당하는 방식을 의미한다. 정해진 크기에 맞춰 프로세스가 분할되어 저장되기에 구현이 빠르고 오버헤드가 적으며 외부 단편화가 발생하지 않는다는 장점이 있다. 하지만 파티션의 크기보다 작은 프로세스가 저장되면 내부 단편화가 발생한다는 단점이 있다. 페이징은 고정 분할 방식이며 프로세스를 일정한 페이지로 분할하여 프로세스를 나누고 메인 메모리는 프레임으로 나누어 페이지 테이블을 통해 논리 주소를 물리 주소로 변환시킬 수 있다. 고정 분할 방식은 고정된 크기에 따라서 메모리를 분할하는 기법을 의미한다. 페이징이라고도 하며,CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?멀티 프로그래밍이란 CPU가 한 번에 여러 개의 프로세스를 실행하는 방식을 의미한다. 메모리에 여러 프로세스를 올려 스케쥴링 기법에 따라서 효율적으로 CPU 사용률을 높이는 방식이다. 하지만 메인 메모리의 공간에는 물리적으로 한계가 있기 때문에 여러 프로세스가 실행될 수록 메인 메모리에 저장할 수 있는 공간이 부족해져 필요하지 않은 페이지는 스왑 영역에 저장되게 된다. 이 때, 계속되는 컨텍스트 스위칭으로 찾으려는 데이터가 메인 메모리에 없으면 page fault 를 발생시키는데, page fault는 운영체제 trap을 발동시켜 실행 중인 프로세스를 대기 상태로 만들고 스왑 영역에서 데이터를 찾아 다시 메인 메모리에 올리고 페이지 테이블을 수정시킨 뒤 프로세스를 재실행 시키게 된다. 이런 page fault로 인한 자원 소요가 멀티 프로그래밍으로 인해 점차 늘어나게 되고 결국, CPU의 사용률이 떨어지는 것을 스레싱(Thrashing)이라고 한다. 이를 해결하기 위해서 워킹셋(Working set)을 설정할 수 있는데, 워킹셋은 지역성 이론에 따라 최근 가장 많이 조회된 페이지들의 집합을 저장하는 기법이다. 워킹셋은 현재 진행 중인 페이지들에 따라 계속해서 변화하며 운영체제는 워킹셋을 모니터링하며 충분한 프레임이 남으면 프로세스를 더 실행시키고, 워킹셋의 총합보다 프레임의 수가 초과되면 프로세스를 중지시키며 적절한 수의 프로세스를 조절할 수 있다. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요? '컴퓨터를 실행' 시키기 위해서는 HDD나 SDD가 꼭 필요하진 않다. 컴퓨터 전원 버튼을 누르면 ROM에 저장되어 있는 BIOS가 실행되면서 CPU, RAM, 하드웨어 등에 이상이 있는지 확인하고 이상이 없다면 하드 디스크에 저장되어 있는 마스터 부트 레코드를 메모리에 올려 운영체제를 실행시킨다. 하지만 하드 디스크가 없기 때문에 운영체제는 실행하지 못하고 단순히 컴퓨터의 기본적인 부팅만 가능하다. 즉, 컴퓨터는 실행 시킬 수 있지만 운영체제가 없기 때문에 컴퓨터를 통해서 어떠한 작업을 진행할 수는 없다. 그렇다면 운영체제를 HDD나 SSD가 아닌 곳에 저장을 시켜서 컴퓨터를 실행시킬 수 있나? 휘발성 메모리는 전기가 통하지 않으면 데이터가 사라지니, 비휘발성 메모리에 저장을 시켜야 하고 과거, 윈도우를 구매할 때 USB나 CD에 담아서 판매하는 것을 봤던 기억이 있다. BIOS는 우선적으로 HDD나 SSD에서 부팅 장치를 찾지만 이 후, USB 드라이브 혹은 CD 등에서 부팅 가능한 장치를 찾아서 부트 로더를 실행 시킬 수 있을 것 같다. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?디스크의 공간을 일정한 크기로 나눈 블록에 파일을 분할하여 저장된다. 파일의 헤더에는 파일명, 크기, 생성 시간 등 메타 데이터가 저장되어 있는데, 파일을 삭제하면 디스크에서 해당 데이터를 제거하는 것이 아닌 파일의 헤더만 제거하게 된다. 파일의 헤더가 제거되면 더 이상 파일을 참조할 수 없어, 읽고 쓰는 것이 불가하게 된다. 파일이 저장되어 있던 블록은 free block list로 연결되게 되고 새로운 파일이 해당 블록을 덮어쓰기 전까지는 혹은 해당 블록에 쓰여져 있던 데이터보다 작은 데이터가 덮어 씌어진 다면 남은 부분에 대해서는 이전 데이터를 포렌식으로 복구할 수 있게 된다. 즉, 덮어씌어진 부분을 제외하면 파일 데이터는 물리적으로 계속 남아있다. 📒 회고이번에도 미션을 진행하면서 단순히 강의 이론에 대한 내용을 회고할 뿐만 아니라 강의에서 배운 내용을 응용해볼 수 있는 질문에 답변해볼 수 있어서 인상 깊었던 것 같다. 강의 초반에 배웠었던 BIOS 부터 복습해보면서 컴퓨터를 실행하였을 때, 어느 순서대로 동작이 되는지 다시 한 번 찾아보기도 하였으며 답변을 하며 스스로 떠오르는 질문에 대해서도 자료를 찾아보며 '이렇게 동작하지 않을까?' 라는 생각을 이어나가볼 수 있었다. 다만 조금 아쉬운 것은 이론적으로 컴퓨터의 동작을 추측해본 것에만 그치고 '실제로 그렇게 동작하는 가?' 라는 것에 대해서는 확신이 없없다는 것이고, 미션에 대한 답이 나오면 다시 해당 내용을 찾아볼 생각이다.

[인프런 워밍업 클럽 3기 - CS] - 3주차 발자국(자료구조와 알고리즘)

💻 알고리즘 📌 삽입 정렬- 정렬된 영역과 정렬되지 않은 영역을 나누어, 정렬되지 않은 영역의 첫 원소를 정렬된 원소와 비교하여 올바른 위치에 삽입- 성능이 아쉬움(O(n^2))📌 병합 정렬분할 정복(divide and conquer): 해결하기 쉬울 정도로 문제를 쪼갠 후 하나씩 해결- 재귀를 통해 정렬- 배열을 더 이상 나눌 수 없을 때까지 쪼개고 병합하면서 정렬- 시간 복잡도 (O(nlogn))📌 퀵 정렬- 분할 정복 알고리즘 중 하나- 재귀를 사용- 배열 중 하나를 '피봇(pivot)'으로 설정- 배열의 시작: left / 끝: right index값 저장- 값 비교 인덱스: leftStartIndex / rightStartIndex- leftStartIndex > pivot && rightStartIndex - 인덱스가 만나면 멈추고 피봇을 rightStartIndex랑 변경- 재귀- 시간 복잡도 (O(nlogn)) / 최악의 경우 (O(n^2))- 병합 정렬보다 더 적은 메모리 사용으로 더 좋은 알고리즘이라고 판단📌 동적 프로그래밍 - 메모이제이션피보나치 수열- 이전 두 수를 무한하게 더하는 수재귀 함수를 실행하면서 중복되는 부분이 무수히 발생한다.- 계산 결과를 저장하고, 중복되는 계산은 저장된 값을 불러온다.- 속도가 빠른 대신, 메모리 공간 차지가 많아진다.function fibonacci(n) { if (n == 0 || n == 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); } function fibonacci2(n, memo) { if (n == 0 || n == 1) return n; if (memo[n] == null) { memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo); } return memo[n]; } console.time("first fibonacci"); console.log(fibonacci(40)); console.timeEnd("first fibonacci"); console.time("second fibonacci"); console.log(fibonacci2(40, {})); console.timeEnd("second fibonacci"); //102334155 //first fibonacci: 867.412ms //102334155 //second fibonacci: 0.073ms 📌 동적 프로그래밍 - 타뷸레이션상향식 계산 방식으로 계산에 필요한 모든 값을 전부 계산 후 테이블에 저장- 적은 메모리 사용 + 빠른 시간- 해결하기 힘든 문제를 하향식으로 접근하여 메모리를 이용하여 빠르게 문제 풀이: 메모이제이션- 직관적이지 못한 재귀, 상향식 접근이 필요: 타뷸레이션 📔 회고🚀 최종 목표 : 로드맵을 마무리하고 알고리즘 문제들을 제대로 이해할 수 있을 정도의 수준이 되기.🚀 매주 규칙:각 섹션마다 하나의 .md 파일을 생성하고, 섹션 내 각 유닛은 헤더로 구분강의를 듣고 최대한 이쁘게 (?) 정리해놓기매 강의를 듣고 궁금하거나 이해가 안가는 부분은 추가적으로 더 찾아서 정리해두기강의에 관련된 알고리즘 최소 1문제씩 풀어 습관화 GPT를 통해 여러 문제를 리스트업하고 최적의 자료구조나 알고리즘을 맞춰보기 이번 인프런 워밍업 클럽을 진행하면서 커리큘럼에 맞춰 매일 강의를 듣고 지키려고 하였던 나의 목표 및 규칙이다.규칙부터 살펴보자면,각 섹션마다 하나의 .md 파일을 생성하고, 섹션 내 각 유닛은 헤더로 구분 : 10 / 10강의를 듣고 최대한 이쁘게 (?) 정리해놓기 : 8 / 10매 강의를 듣고 궁금하거나 이해가 안가는 부분은 추가적으로 더 찾아서 정리해두기: 6 / 10강의에 관련된 알고리즘 최소 1문제씩 풀어 습관화 : 9 / 10GPT를 통해 여러 문제를 리스트업하고 최적의 자료구조나 알고리즘을 맞춰보기 : 7 / 10매 강의를 듣고 섹션별, 유닛별로 모든 내용을 정리하여 저장하였으니 10점을 주었다.강의를 듣고 최대한 이쁘게 정리를 하려고 노력하였지만 2점이 감점된 이유는 시간이 지날 수록 점점 이모지 사용이 줄고 글간, 행간과 같은 사소한 부분을 신경쓰지 않게 된 것같다,, 그래도 이 노력을 통해서 일관된 템플릿을 형성할 수 있었다는 점, md파일로 매일 정리해보며 파일 정리에 조금 익숙해진 것 같다.자료구조 강의는 이론적인 부분이 많아, 찾아볼 자료 혹은 더 공부해 볼 부분이 많이 존재하였지만 알고리즘은 이론보다 실전이 더 중요한 부분이라 궁금한 점 보다는 이해가 안가는 부분을 반복해보며 익숙해지려 노력하였다. 결국, 강의를 들으면서 궁금한 점이 많지 않아서 직접 찾아보려고 한 노력들은 적었기에 6점을 주었다. 스스로 피드백을 주자면, 배운 알고리즘이 어느 문제들에서 유용한 지, 혹은 더 개선된 버전의 알고리즘이 있는지 찾아봤으면 더 좋지 않았을까,, 라는 생각이 든다.강의를 듣고 강의에 관련된 알고리즘 문제를 쉬운 문제라도 최소 하나는 매일 풀어봤던 것 같다. leetcode를 통해서 문제를 찾았고 첫 번째는 효율성을 따지지 않고 스스로 풀어보고, 두 번째는 효율성을 개선할 부분을 찾아 수정하였고 마지막은 더 효율적인 코드가 있는지 다른 코드를 찾아보며 알고리즘 문제에 익숙해지려 하였다. 1점이 감점된 이유는 대부분 하루에 한 문제씩만 풀었다는 아쉬움과 게으름의 후회,,이 부분이 진행하기 가장 어려웠던 것 같다. 아직 기본적인 수준의 자료구조와 알고리즘만 배운 상태이기 때문에 제대로된 답변을 하지 못하는 경우가 많았고 설명을 들어도 잘 이해가 가지 않는 경우가 많았다. 이게 오히려 투지를 불태우긴 하였지만 아직까지는 아쉬운 부분이 커서 7점을 주었다. 하지만 계속해서 반복하다보면 새로운 개념들에 점차 익숙해질 수 있고 알고리즘 공부와 꾸준히 이어서 하면 큰 시너지를 낼 수 있을 것 같다.그래서 최종 목표는로드맵을 마무리하고 알고리즘 문제들을 제대로 이해할 수 있을 정도의 수준이 되기 : 6 / 10알고리즘 문제를 풀거나, GPT를 통해 여러 문제에 대한 효율적인 자료구조를 대답해봐도 아직 내가 어느정도 성장했다고 느끼지는 못하였다. 자료구조와 알고리즘은 확실히 이론을 공부하는 것보다는 반복적인 연습과 실습이 중요하다라는 것을 다시 한 번 더 깨달은 것 같다. 알고리즘 공부 또한 꾸준히 해나갈 것이고 매일 최소 한 문제씩 풀어가면서 성장을 위해 필요한 최소의 연습양을 채우면서 점차 내가 원하는 수준의 알고리즘 문제 풀이 실력까지 높여가고 싶다.

[인프런 워밍업 클럽 3기 - CS] - 3주차 발자국(운영체제)

💻 가상메모리📌 개요32bit CPU 를 사용한다면 약 4GB(2^32)의 메모리, 가상 메모리를 가진다. ❓그러면 가상 메모리의 용량을 뛰어넘는 프로세스들을 어떻게 실행되는 것인가?✅ 물리 메모리 내용의 일부를 스왑 영역에 저장하고 필요 시에만 물리 메모리로 스왑 메모리 관리자(MMU Memory Management Unit)은 물리 메모리 + 스왑 영역을 전체 메모리 공간으로 보고 가상 주소를 물리 주소로 변환시킨다 (동적 주소 변환 DAT) ❓메모리 관리자는 어떻게 메모리 공간을 관리하나?✅ 물리 메모리의 0번지는 운영체제의 영역이며 나머지 영역에 대해 "가변 분할 방식(세그멘테이션)"과 "고정 분할 방식(페이징)"으로 구분하여 나눈다. 또한 매핑 테이블을 관리하여 가상주소를 물리주소로 전환이 가능하다. 📌 세그멘테이션(배치정책)세그멘테이션(Segmentation): 함수, 모듈 등으로 세그먼트를 분할(코드, 힙, 데이테, 스택,,)프로그램 입장에서는 각 세그먼트는 모듈 별로 분리되어 있다고 판단프로세스 입장에서는 각 세그먼트는 인접하게 판단각 세그멘테이션이 모듈로 처리되어 역할에 맞게 분할되어 관리가 가능하다외부 단편화가 발생할 수 있다. 세그멘테이션 테이블 : 세그멘테이션에서 사용되는 매핑 테이블Base Address : 세그멘테이션 메모리 시작 주소Bound Address: 세그멘테이션 크기, 접근 가능 최대 범위 물리 주소 변환 과정1. CPU가 논리주소, 세그멘트 번호 전달2. 메모리 관리자는 Segment Table Base Register 를 통해 물리 메모리 n 번지에 저장된 세그먼테이션 테이블 로드3. 세그멘트 번호를 인덱스로 테이블에서 Base Address, Bound Address 조회4. Bound Address(메모리 크기)와 논리 주소를 비교1. Bound Address > 논리 주소 = Base Address + 논리 주소 = 물리 주소2. Bound Address 에러 발생- 컨텍스트 스위칭마다 해당 세그멘테이션 테이블에 프로세스의 데이터를 수정해야 함으로 비용이 큰 작업이다. 📌 페이징(배치정책)고정 분할 방식: 메모리를 정해진 크기의 페이지로 나누어 관리프로세스는 같은 크기의 페이지로 분할되며, 메인 메모리는 같은 크기의 프레임으로 분할된다. 페이지 테이블page number: 조회할 페이지 번호frame number: 물리메모리 프레임 번호물리 주소 변환 과정1. CPU 논리주소 전달2. 메모리 관리자는 Page Table Base Register을 통해 물리메모리 n번지에서 페이지 테이블 로드3. 페이지 번호 = 논리주소 / 페이지 크기4. 오프셋은 논리주소 % 페이지 크기5. 페이지 테이블에서 페이지 번호를 인덱스로 프레임, 오프셋를 알아냄6. 만약 프레임에 invalid로 저장되면 스왑영역에 저장 세그멘테이션 VS 페이징1. 세그멘테이션은 Base Address가 필요하지만 페이징은 각 페이지 영역이 동일하여 필요 없음2. 세그멘테이션 외부 단편화 발생, 페이징 내부 단편화 발생3. 세그멘테이션 논리적 영역별로 구분, 페이징은 고정된 페이지에 저장하여야 하니 논리적으로 구분 불가4. 각 프로세스마다 페이지 테이블을 갖고 있기에, 페이지 테이블의 크기 관리가 중요하다. 📌 페이지드 세그멘테이션페이지 + 세그멘테이션 프로세스 접근 권한- 코드: RE- 데이터: RW(o)- 힙: RW- 스택: RW세그멘테이션 테이블권한 비트Page Number페이지 개수물리 주소 변환 과정CPU가 0x12300번지 접근 요청메모리 관리자가 메모리에서 세그멘테이션 테이블이랑 페이지 테이블 로드세그먼트 번호를 통해 인덱스를 확인 후, 접근 권한 위반 여부를 파악페이지 크기와 비교하여 메모리 침범 여부를 확인페이지 넘버를 통해 페이지 테이블의 프레임 확인물리 메모리의 프레임 번호 + 접근 요청된 메모리 오프셋 = 물리 주소단점1. 물리메모리에서 데이터를 가져오기 위해서는 메모리 접근 두 번 해야함 (세그멘테이션 테이블, 페이지 테이블) 📌 디멘드 페이징(가져오기 정책)지역성 이론1. 공간의 지역성: 현재 위치에서 가까운 데이터에 접근 확률이 높음2. 시간의 지역성: 현재 시간에서 가까운 데이터에 접근 확률이 높음(최근) 디멘드 페이징: 필요한 데이터만 메모리에 올리고 사용하지 않는 데이터는 스왑 영역으로 이동보조저장장치에서 데이터를 가져오는 것은 레지스터보다 몇 배는 더 많은 시간이 소요스왑영역이 보조저장장치에 있기에, 스왑영역에 데이터를 저장하는 것을 최소화해야 함. 스왑 인(swap in): 스왑 영역 -> 물리 메모리스왑 아웃(swap out): 물리 메모리 -> 스왑 영역 페이지 테이블 엔트리(PTE)1. 접근 비트: 데이터 접근 여부(읽기, 실행 작업 시, 1)2. 변경 비트: 데이터 쓰기 여부(쓰기 작업 시, 1)3. 유효 비트: 페이지가 물리 메모리에 있는지(있음 0)4. WRE 비트: 접근 권한 비트5. 프레임: 프레임 번호 저장 디멘드 페이징 과정1. 페이지 테이블에서 유효비트와 프레임 번호를 확인2. 유효비트가 0일 경우, 물리 메모리에서 해당 프레임 번호로 데이터 반환3. 1일 경우, 스왑영역에서 프레임 번호로 데이터 추출4. 물리 메모리에서 빈 프레임을 확인5. 빈 프레임이 있으면 물리 메모리로 데이터를 적재하고 페이지 테이블 수정6. 빈 프레임이 없으면 물리 메모리에서 필요하지 않은 데이터를 스왑 영역으로 이동 후, 빈 프레임으로 이동 📌 페이지 교체정책페이지 교체정책: 가득찬 메모리에서 스왑영역으로 보낼 페이지를 고르는 기법1. 무작위 선택(Random): 지역성을 고려하지 않아, 자주 사용되는 페이지가 교체될 수 있음2. 가장 오래된 페이지 교체(FIFO): 가장 오래된 페이지가 자주 사용될 수도 있음3. 가장 오랫동안 사용하지 않을 페이지 교체(Optimum): 사실상 구현이 불가(이론상)4. 최근 사용이 가장 적은 페이지 교체(Least Recently Used)1. 지역성 이론에 따라, 최근 사용이 적은 페이지는 앞으로도 사용이 적을 것이다는 추정2. optimum 알고리즘과 근접한 성능을 갖지만, 지역성 이론에 따르지 않는다면 성능이 안좋아짐3. 시간을 기록하는 비트 수가 많아짐 Belady의 역설: 페이지 폴트를 줄이기 위해 메모리를 늘려 프레임을 늘렸더니 페이지 폴트가 더 많이 발생(FIFO에서 발생) LRU 알고리즘의 성능은 좋지만 구현이 어렵고 시간을 기록할 비트가 많이 필요하며 시간이 오래 지나면 오버 플로우가 발생한다. 클락 알고리즘(clokc algorithm)접근 비트를 하나만 이용일정시간마다 접근 비트를 0으로 초기화페이지 조회 시, 접근 비트 1로 수정페이지를 원형으로 연결페이지 폴트 발생 시, 클락 핸드(원형 페이지를 순회하는 포인터)를 시계방향으로 돌려접근 비트가 1이면 0으로 수정하고접근 비트가 0이면 교체할 페이지로 선택향상된 클락 알고리즘접근 비트와 변경 비트 모두 확인접근 비트 0 / 변경 비트 0접근 비트 0 / 변경 비트 1접근 비트 1 / 변경 비트 0접근 비트 1 / 변경 비트 1순서대로 페이지 교체 우선 순위 선정 하드웨어적으로 접근비트를 지원하지 않는 시스템에서 FIFO를 사용해야 함.(FIFO 최적화 필요)2차 기회 페이지 교체 알고리즘- FIFO와 동일하게 동작- 만약 페이지 폴트없이 페이지 접근이 성공하면, 가장 첫 체이지를 큐의 가장 뒤로 이동 📌 스레싱과 워킹셋스레싱: CPU 사용률을 높이기 위해 더 많은 프로세스를 실행하지만 물리 메모리의 공간 초과로 스왑에 더 많은 시간이 할당되어 CPU 사용률이 낮아지는 것- 물리메모리의 크기가 부족하여 스레싱 발생- 물리적으로 메모리의 성능을 늘리는 것은 한계가 있음(스레싱이 발생하지 않는다면 업그레이드에 대한 효율이 없음)- 페이지를 적게 할당하면 page fault가 많이 발생 / 페이지를 많이 할당하면 다른 프로세스가 사용할 페이지가 적음- 프로세스를 실행하며 page fault가 많이 발생하면 페이지를 더 할당- page fault가 적게 발생하면 페이지를 조금 할당- 적절한 페이지 수가 결정되어 지역성 이론에 따라 유지할 페이지들을 골라야 함. 워킹셋: 현재 메모리에 올라온 페이지는 다시 사용할 확률이 높기 때문에 하나의 세트로 묶어서 메모리에 저장- 프로세스 준비 -> 실행 상태로 컨텍스트 스위칭할 때 사용된다. 💻 입출력장치📌 주변장치(I/O 디바이스, 저장장치)I/O Device하드웨어완 연결할 수 있는 외부 인터페이스I/O 데이터 전달을 위한 버스 인터페이스(address, data, control 버스 3개)장치 상태 및 데이터 저장을 위한 레지스터(C메모리로 전달되기도 함)컨트롤러, 로직I/O 처리 과정CPU는 I/O 작업을 입출력 제어기에게 맡기고 다른 작업CPU, 메모리, 그래픽 카드(입출력 장치지만 대용량 데이터를 다룸)는 시스템 버스를 이용하고 (고속으로 이용)입출력 제어기는 고속 입출력 버스를 통해 빠른 장치(HDD 등)데이터 전송과 저속 입출력 버스를 통해 느린 장치(마우스 키보드 등)입출력 제어기는 입출력 두 개의 버스에서 온 데이터를 시스템 버스를 통해 메모리로 옮김입출력 제어기가 메모리에 접근하려면 CPU가 필요한데, 효율성이 떨어지니 DMA(Direct Meomry Access)를 통해 메모리에 저장CPU와 DMA 메모리 공간을 분리 - Memory Mapped I/O 📌 마우스 / 키보드마우스과거는 볼을 사용하여 마우스 움직임 계산현재는 카메라로 초당 1500회의 사진을 찍어 DPS를 통해 마우스 좌표를 계산DPS 입력 감지 시, 디바이스 컨트롤러가 인터럽트 발생마우스 드라이버가 데이터를 운영체제에 이벤트 전달 > Foreground 애플리케이션 전달 > 애플리케이션 데이터 처리키보드디바이스 컨트롤러 입력 감지 및 인터럽트 발생키보드 드라이버 이벤트 전달 > 운영체제 Foreground 애플리케이션 전달 > 애플리케이션 데이터 처리📌 하드디스크/Flash Memory(SSD) 하드디스크의 구조sector: track에서 여러개의 sector로 나뉘고 하드디스크의 가장 작은 단위 track: platter에 여러개의 track이 존재하고 표면의 자성으로 N극은 0, S극은 1platter: 원판 형태로 데이터 저장cylinder: 모든 헤드는 같이 움직이고 여러개의 헤드가 가리키는 트랙의 집합spindle: platter를 지지하는 막대read/write head: disk arm에 달려있어, platter의 표면을 읽음 과정cylinder C로 가서 track B에 있는 sector D를 읽어라disk arm은 헤드를 cylinder C로 이동시키고(seek, seek time track B에 Sector D가 head에 닿을때까지 spindle을 회전Flash Memory하드디스크기계적으로 움직여 소음도 일어나고 속도가 느림자기적으로 처리 -> 고장 가능성이 높음충격에 약함flash memory전기적으로 데이터를 읽기 때문에 조용하고 속도가 빠름안전함덮어쓰기가 불가능지우기 가능한 횟수가 정해져있어서, 지우고 쓰기가 여러번 쓰일 수 없음 💻 파일시스템📌 파일과 파일 시스템파일 시스템 기능파일, 디렉토리 생성, 수정, 삭제접근 권한 관리무결성 보장백업과 복구암호화파일 -> 블록 단위로 저장 -> 메모리 관리자가 바이트로 변환 -> 사용자가 접근운영체제는 File Descriptor를 갖고 있으며 파일마다 독립적인 File Descriptor가 존재하여 파일이 오픈되면 메모리에 올라간다. 사용자가 파일을 실행하면 운영체제가 file descriptor를 전달하여 파일을 찾아온다. 파일 구조순차파일구조: 파일 내용이 연속적으로 이어져있음직접파일구조: 해시 함수를 통해 해시 테이블에 데이터 저장인덱스파일구조: 순차 + 직접 파일구조 📌 디렉토리Root Directory: 최상위 디렉토리디렉토리 헤더는 디렉토리 정보가 시작하는 위치를 가리킨다.다단계 디렉토리: 하나의 디렉토리에 하위의 디렉토리를 만들 수 있는 트리 구조 📌 파일과 디스크블록: 디스크 공간을 일정한 크기로 나누고 주소를 할당(1 ~ 8KB)연속할당: 파일 구성 블록들을 디스크에 연속적으로 할당시작주소만 알면 파일을 읽을 수 있음내부 단편화 발생불연속할당: 데이터를 분산하여 저장연결할당: 시작 블록 주소만 알고 있으며, 연결리스트를 통해 블록 저장인덱스할당: 인덱스 블록의 주소를 저장하고, 인덱스 블록에 저장된 데이터 블록 인덱스들로 데이터 블록을 읽어옴 📌 더 찾아본 점 ❓ 페이징, 세그멘테이션, 페이지드 세그멘테이션페이징 테이블 구성: 페이지 번호 / 프레임 번호 / 유효/무효 비트페이징 테이블 엔트리: 페이지 테이블에서 페이지에 대한 위치 정보를 담은 각 행CPU가 (p, d) 전달페이징 테이블에서 p에 대한 f를 찾고 반환물리 주소에서 f 번 프레임의 d 번째 위치 (페이지 크기 * f + d)세그멘테이션 테이블 구성: 세그멘테이션 번호 / Base Address / Bound AddressCPU가 (s,d) 논리주소 전달세그먼트 테이블에서 s에 대한 base address와 limit 확인d가 limit 보다 크면 에러물리 주소 = base address + d페이지드 세그멘테이션: 프로세스를 각 세그멘테이션으로 구분하고 세그멘테이션을 고정 크기의 페이지로 분할CPU는 (s,p,d) 논리주소 전달세그먼트 번호를 통해 p를 확인하고 d와 페이지 개수를 비교하여 메모리 침범인지 확인p를 통해 페이지 테이블에서 인덱스를 확인하고 프레임 번호를 확인물리 주소: 프레임 번호 시작 주소 + d = f \* 페이지 크기 + d ❓ 메모리에 없는(invalid)데이터를 어떻게 저장장치에서 가져올까?Demand Paging: 프로그램 실행 중에 필요한 페이지만 물리 메모리에 저장하고, 실행 중에 요구되는 페이지에 대해서는 저장장치에서 로드Page Fault: 페이지 테이블에서 가져오려는 데이터가 invalid 한 상황. 운영체제에게 trap을 발동시키고 이를 통해 요구되는 페이지를 메모리로 로드 1. 페이지 테이블에서 찾으려난 데이터가 valid인지 invalid인지 확인2. invalid일 경우, page fault가 발생되고 운영체제의 trap에 걸림(프로세스 대기).3. 물리 메모리에서 비어있는 frame 주소를 찾음4. 제 2 저장장치에서 요구되는 페이지를 찾고 해당 프레임에 할당5. 물리 주소 프레임 위치를 페이지 테이블에 매핑6. 인터럽트가 끝나고 프로세스 중단된 명령어부터 다시 실행 ❓ Second-Chance Algorithm?FIFO 알고리즘에 접근 비트(reference bit)를 추가하여 접근 여부를 파악0이면 해당 페이지를 교체, 1이면 0으로 수정한 후 다음 FIFO page로 이동향상된 Second-Change Algorithm(clock algorithm)원형 큐로 생성포인터가 각 큐를 순회하며 접근 비트가 0인 것을 발견.최악의 경우(모든 접근 비트가 1), 모든 접근 비트를 0으로 수정하고 FIFO와 동일하게 가장 앞에 페이지를 교체 ❓ Thrashing, Working set?프로세스가 page in, page out으로 너무 많은 swapping을 하는 현상많은 프로세스를 메모리에 올려(멀티 프로그래밍) 실행 시키면, 어느 순간 CPU 효율성이 떨어지는 현상프로세스 실행 > page fault > process wait queue > page in > next page > page fault ...Working Set지역성 이론에 따라서 최근에 가장 많이 조회된 페이지들의 집합working set안에 있다 - 자주 참조되는 페이지 / 없다 - 교체 대상 페이지t1 시간에는 {1,2,5,6,7} 로 워킹셋 생성, t2에 {3,4} 로 워킹셋 수정Δ (델타) 를 통해 working set window를 생성하고 그 사이즈를 적절히 정하는게 중요운영체제는 각 프로세스의 working set을 모니터링하면서 사이즈에 맞게 frame을 할당충분한 프레임이 남는다면 프로세스를 더 실행 / 각 프로세스의 워킹셋 총합이 사용가능한 프레임의 수가 초과되면 프로세스 중지이를 통해 멀티 프로그래밍 정도를 높이면서 CPU 효율성을 유지❓ 입출력 장치의 I/O 인터럽트가 발생해도 끊김이 없는 이유?interrupt-request line을 통해 CPU는 명령어를 실행한 후 인터럽트가 발생하였는지 감지현재 실행 중인 프로세스의 데이터, 상태를 저장인터럽트 핸들러를 실행인터럽트의 원인을 확인하고 필요한 작업을 수행수행 후, 상태값을 복원하여 이전 작업으로 복귀아무런 작업이 없는 컴퓨터에서 10초 동안 23,000개의 인터럽트가 발생 - 초당 수백개의 인터럽트를 처리해야 함. 현재 운영체제에서는 조금 더 정교한 interrupt handling 특징들이 있음1. 중요한 프로세스 작업 중 인터럽트 핸들링을 지연시킬 능력이 필요하다2. polling을 통한 인터럽트 발생 확인이 아닌, 적절한 인터럽트 핸들러를 통해 효율적으로 인터럽트 관리3. multilevel interrupt를 통해 상위 - 하위 우선순위의 인터럽트를 구분하고 여러 인터럽트 동발생 시, 긴급성에 따라 응답4. 운영체제의 attention을 바로 받을 수 있을 만한 명령어가 필요 (page fault는 trap) 📌 백엔드 면접 질문✏ 페이지 폴트(Page Fault)는 언제 발생하며, 운영체제는 이를 어떻게 처리하는가??✅ 페이지 폴트란 프로세스가 논리 주소로 데이터를 요청할 때, 메인 메모리에 데이터가 없는 경우 발생하는 인터럽트이다.스왑 영역에 저장되어 있는 페이지를 가져오기 위해 프로세스를 대기 상태로 변경 시켜, 운영체제에 트랩을 발생시키고스왑 영억에서 데이터를 가져와 메인 메모리에 저장하고 페이지 테이블을 다시 변경해서 프로세스를 이어서 실행시킵니다. ✏ Node.js에서 가상메모리는 어떻게 관리되는가?V8 엔진은 JS코드가 저장되는 Code segment, 함수 호출과 실행 컨텍스트를 저장하는 Call Stack, 객체와 데이터를 저장하는 Heap Memory로 구분된다. V8에서는 페이징 기법을 통해 힙 영역을 가상 메모리로 관리한다. 힙 영역에 각각의 space(new space, old space, large object space,,)들은 페이지로 구성되어 있으며 각 페이지는 large object space를 제외하고는 1MB정도이다. 또한 가비지 컬렉터를 통해 단편화가 많이 일어난 페이지에 대해 메모리 압축을 진행한다. - 살아있는 객체들을 한 곳으로 이동시키고 포인터 갱신 ✏ Node.js에서 파일을 읽는 방법은?- Node.js는 싱글스레드에서 동작하지만 내부적으로 멀티 쓰레드(Worker Pool)에서 작업을 한 후에 이벤트 루프를 통해 결과를 반환한다. 이벤트 루프는 비동기 작업에 대해 작업이 완료되면 콜백함수를 task queue에 저장하고 콜스택이 비어있으면 task queue에서 콜백함수 실행. readFile 메서드는 비동기로 실행되며 콜백 함수를 통해 파일 읽기 작업이 마무리되면 콜백이 실행되며 readFileSync는 동기적으로 실행되고 blocking 상태가 되어, 파일을 읽을 때까지 작업이 대기된다. 📔 회고🚀 최종 목표 : 더 효율적인 백엔드 개발을 위해 기본적인 운영체제 지식들을 확실히 잡아가기🚀 매주 규칙:각 섹션마다 하나의 .md 파일을 생성하고, 섹션 내 각 유닛은 헤더로 구분강의를 듣고 최대한 이쁘게 (?) 정리해놓기 매 강의 듣고 해당 내용 공룡책 & 강의 1회 정독 및 수강매 강의에 대한 내용 백엔드 면접 질문을 추려서 답변하고 개념 구체화하기이번 인프런 워밍업 클럽을 진행하면서 커리큘럼에 맞춰 매일 강의를 듣고 지키려고 하였던 나의 목표 및 규칙이다.규칙부터 살펴보자면,각 섹션마다 하나의 .md 파일을 생성하고, 섹션 내 각 유닛은 헤더로 구분 : 10 / 10강의를 듣고 최대한 이쁘게 (?) 정리해놓기 : 8 / 10매 강의 듣고 해당 내용 공룡책 & 강의 1회 정독 및 수강 : 7 / 10매 강의에 대한 내용 백엔드 면접 질문을 추려서 답변하고 개념 구체화하기 : 7 / 10매 강의를 듣고 섹션별, 유닛별로 모든 내용을 정리하여 저장하였으니 10점을 주었다.강의를 듣고 최대한 이쁘게 정리를 하려고 노력하였지만 2점이 감점된 이유는 시간이 지날 수록 점점 이모지 사용이 줄고 글간, 행간과 같은 사소한 부분을 신경쓰지 않게 된 것같다,, 그래도 이 노력을 통해서 일관된 템플릿을 형성할 수 있었다는 점, md파일로 매일 정리해보며 파일 정리에 조금 익숙해진 것 같다.매 강의를 듣고 관련된 내용을 공룡책에서 찾아서 읽어보고 어려운 내용에 대해서는 공룡책 관련 강의와 함께 수강하려고 노력하였다. 2주차까지는 강의에서 나온 내용과 공룡책이 챕터 별로 일치하여 찾아보기가 편하여 공룡책에 나온 내용을 읽어보고 스스로 정리해보며 부족한 부분을 기록하였다면, 이번 주차부터는 공룡책에 안나오는 내용들이 점차 등장하여 미리 궁금한 내용들은 정리해두고 다른 블로그나 공식문서들을 참고하여 지식을 채워갔다. 7점을 준 이유는 아무래도 공룡책 챕터 별로 범위가 넓고 깊이 있게 다루기 때문에 정독의 수준에는 미치지 못한 것 같다. 또한 이해가지 않은 부분은 쉽게 넘어가고 전체적인 흐름만 파악하려 하였기에 아쉬운 점이 조금 남은 것 같다.매 강의를 듣고 GPT를 이용하여 관련된 강의 내용에 관련된 백엔드 면접 질문들을 추려서 스스로 답변하면서 정리해보았다. 관심이 많던 Node.js 를 기반으로 더 깊이있게 공부해봤던 것 같고 CS 지식들을 실무에 적용시켜서 생각해보려고 노력하였다. 하지만 Node.js 프롬프트를 이용한 질문은 유료라 한도가 항상 잡혀서 아쉬운 점이 컸던 것 같다. 무료 프롬프트는 어딘가 의심이 드는 답변들이 많아 두번 세번 더 찾아봐야하는 문제점이 있어, 한정된 질문들에 대해 소중하게 답변했던 것 같다. 7점을 주었던 이유는 면접 질문을 정리하고 스스로 공부해봤던 개념들을 따로 정리해놓지는 않아서 부족하게 진행되었던 것 같고 이번 기회에 매일 면접 질문들을 답변해보면서 공부를 한 것들을 기록하여 정리해보려 한다.그래서 최종적으로 내가 설정하였던 목표에 대해서는더 효율적인 백엔드 개발을 위해 기본적인 운영체제 지식들을 확실히 잡아가기 : 8/10나름 높은 점수를 주었지만 이 점수는 나의 과정에 대한 점수이지 결과에 대한 점수는 아닌 것 같다. CS에 대해서는 아직 부족한 부분이 많지만 이번 로드맵을 통해 CS가 더 흥미로워졌고 더 깊이 공부해보고 싶은 생각이 들었다.무엇보다 가장 좋았던 부분은 CS에 대한 전반적인 틀을 잡을 수 있었고 공부 해야할 방향성이 조금씩 잡혀나가는 것 같다는 느낌이 들었다. 이를 기반으로 더 깊이 있게 공부하면서 실무적으로 계속 연결하여 생각해보고 백엔드 개발에서 더 효율적이고 올바른 판단을 하기 위해 꾸준히 노력해 볼 생각이다.

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

FIFO 스케줄링의 장단점이 뭔가요?FIFO(First In First Out) 스케줄링이란 대기 큐에 들어온 작업 순서대로 실행하는 스케줄링을 의미한다. 비선점형 스케줄링으로, 하나의 프로세스가 CPU에 할당받아 작업이 시작되면 해당 프로세스의 작업이 마무리되기 전까지 중단되지 않는다.✅ 장점 스케줄링 구현이 단순하다들어온 작업 순서대로 모든 작업이 실행되기 때문에 기아(Starvation)현상에 빠지지 않는다.컨텍스트 스위칭이 자주 발생하지 않아,오버헤드가 적다✅ 단점들어온 작업 순서에 따라, 작업의 시간이 긴 프로세스가 먼저 실행될 경우 작업의 시간이 짧은 프로세스들은 오래 대기해야 하며 응답시간 또한 길어진다. (Convoy Effect, 호위효과)I/O작업을 대기하는 동안 CPU는 다른 작업으로 전환할 수 없기 때문에(비선점형), CPU 사용률이 저하된다.✅ 평균대기시간case 1: 프로세스_1 (Burst Time: 25초) - 대기 시간: 0초프로세스_2 (5초) - 대기 시간: 25초프로세스_3 (4초) - 대기 시간: 30초평균 대기 시간: 55 / 3 = 18.3초case2:프로세스_3 (4초) - 대기 시간: 0초프로세스_2 (5초) - 대기 시간: 4초프로세스_1 (Burst Time: 25초) - 대기 시간: 9초평균 대기 시간: 13 / 3 = 4.3초프로세스의 실행 순서에 따라 평균대기시간의 편차가 커지기 때문에 현대 운영체제에서는 잘 사용하지 않는다.먼저 들어온 작업 순서대로 처리를 해주는 작업 혹은 성능의 저하없이 모든 작업을 순서대로 처리하는 일괄 처리 시스템에서 효율적이다. SJF를 사용하기 여러운 이유가 뭔가요?SJF (Shortest Job First) 스케줄링은 Burst Time이 가장 짧은 작업부터 우선 실행하는 스케줄링이다. FIFO의 단점이었던 '실행 순서에 따른 평균 대기시간 편차'를 극복하기 위해 설계되어 실행 시간이 짧은 프로세스 먼저 작업하는 기법이다. 하지만 두 가지 큰 단점이 존재한다. 첫 번째는 Starvation(기아) 현상이 발생할 수 있다. 짧은 작업을 우선적으로 처리하기 때문에, 긴 작업의 프로세스는 계속 대기를 하게 되어 실행의 순서가 보장되지 않는다. 두 번째는 실제 Burst Time을 예측하기 힘들다는 것이다. 짧은 실행 순서를 먼저 실행시키는 SJF 스케줄링에서, 실제 작업이 얼마나 CPU를 사용할 것인지 혹은 I/O 작업이 언제 응답 받을 수 있는지 예측될 수 없기 때문에 실 Burst Time을 예측하여 짧은 프로세스 먼저 실행시키기 어렵다. SJF는 결론적으로 실행 시간이 예측 가능하며 짧은 작업이 많은 환경에서 평균 대기 시간을 효율적으로 줄일 수 있는 스케줄링 기법이다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?RR(Round Robin) 스케줄링이란 타임 슬라이스만큼 프로세스를 실행하고 다음 프로세스를 실행하는 스케줄링이며 타임 슬라이스는 CPU가 할당되는 일정한 시간을 의미한다.타임 슬라이스가 아주 작게 실행되면 여러 프로세스가 동일한 시간에 실행되는 것처럼 보일 수 있지만 짧은 시간을 주기로 Context Switching이 많아져 오버헤드가 증가한다. 타임 슬라이스가 너무 크게 실행되면 FIFO 스케줄링과 유사하게 동작하여 효율성이 떨어지게 된다. 즉, RR 스케줄링은 최적의 타임 슬라이스를 설정하는 것이 중요하며 최적의 타임 슬라이스는 여러 프로세스가 버벅이지 않으면서 동시에 실행시키는 효과를 줌과 동시에 오버헤드가 너무 크지 않은 정도의 할당 시간을 의미한다. 윈도우에서는 20ms, 유닉스에선 100ms정도로 설정된다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?MLFQ(Multi Level Feedback Queue)란 프로세스를 여러 개의 우선순위 큐로 분류하고, 실행 시간에 따라 큐 간 이동이 가능한 스케줄링 알고리즘이다. 처음 프로세스가 실행되면 높은 우선순위의 큐에서 실행되며, 실행되는 시간에 따라 우선순위가 변동되어 점차 다른 큐에 할당된다. 주어진 타임 슬라이스 내에 작업이 완료된다면 I/O Bound Process로 간주하여 높은 우선순위를 유지하고,해당 타임 슬라이스를 초과하면 CPU Bound Process로 간주되어 낮은 우선순위 큐로 이동하게 된다. 실행 순서는 우선순위가 높은 큐부터 순차적으로 실행되며, 낮은 우선순위의 큐는 오래 동안 실행되지 않는 상태인 기아(Starvation) 현상을 겪을 수도 있기 때문에 Aging을 통해 문제를 해결할 수 있다. Aging은 낮은 우선순위 큐에서 오랫동안 기다린 프로세스들을 점진적으로 다시 우선순위를 높여주는 기법이다. I/O Bound Process가 우선순위가 높은 이유처음에는 I/O 작업은 요청을 한 뒤에 응답까지 기다려야 하니, 작업 시간이 예측하기 힘들고 오래걸리지 않나? 라고 생각하였고타임 슬라이스 안에 작업이 보통 완료하지 못하지 않을까라는 생각에 우선순위가 높은 이유가 궁금하여 다시 해당 부분을 찾아보았다. I/O 작업은 CPU를 거의 사용하지 않고 보통 외부 장치를 통해 응답을 기다리는 작업들이다. CPU의 점유를 가로채지 못하는 비선점형 스케줄링 기법에서는 I/O작업이 실행되면 응답까지 기다려야 하니(대표적으로 FIFO 같은 기법) 작업이 빠르다고 말할 수는 없지만, 선점형 스케줄링 기법에서는 I/O 작업이 요청되면 해당 프로세스는 대기 상태로 상태값이 변경되고 응답이 오기 전까지(인터럽트) 다른 프로세스의 작업을 실행할 수 있기 때문에 작업이 빠르다고 얘기할 수 있으며 우선순위 또한 높게 가져갈 수 있는 것이다. 공유자원이란무엇인가요?공유자원이란 여러 프로세스 간 공유되는 자원(변수나 파일 등)을 의미한다. 여러 프로세스는 서로 통신을 하며 한 가지 작업을 동시에 수행할 수도 있는데, 이 과정에서 공유자원을 여러 프로세스가 접근하게 되면 경쟁 조건이 발생하면서 동기화 문제가 생긴다. 경쟁 조건이란 다수의 프로세스(혹은 쓰레드)가 같은 데이터(공유자원)에 동시에 접근 혹은 조작의 순서에 따라 결과의 일관성을 해칠 수 있는 상태를 의미하며 이를 해결하기 위해서는 상호 배제가 필요히다. 상호배제는 하나의 프로세스만 접근할 수 있는 구역인 임계구역을 설정하여 데이터의 동기화를 유지시키는 것을 의미한다. 상호배제 요구사항임계영역엔 하나의 프로세스만 접근 가능하다여러 요청에도 하나의 프로세스만 접근을 허용한다임계구역에 들어간 프로세스는 최대한 빠르게 나와야 한다. 상호배제의 매커니즘Mutex임계 구역에 진입하면 lock을 획득하고 acquire()와 release()를 통해 획득 및 반납프로세스가 임계구역에 진입하기 위해 무한 루프가 돌며 이를 spinlock이라고도 부른다Semaphore공유자원 수용 가능 수에 따라 정수의 변수 s를 선언wait(s) signal(s) 를 통해 s값을 증가 차감한다함수 호출 순서를 잘못하면 문제가 발생한다.Monitor세마포어의 단점을 해결한 상호배제 메커니즘운영체제의 차원이 아닌 프로그래밍 언어에서 처리한다자바에서 synchronized 붙은 함수가 실행되면 다른 프로세스가 접근 할 수 없음함수를 임계 영역을 감싸지 않아도 되어 편리함. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?교착상태(Deadlock)란 여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 아무도 작업을 진행하지 못하는 상태를 의미한다. 교착상테 필요조건상호배제: 한 프로세스가 리소스를 점유하였다면 다른 프로세스 접근 불가비선점: 점유중인 프로세스의 리소스를 뺏어갈 수 없음점유와 대기: 한 프로세스는 리소스를 점유하고 있는 상태에서 다른 프로세스의 리소스 점유를 대기해야 함원형대기: 점유와 대기를 하는 프로세스들의 관계가 원형이어야 함.데드락의 발생은 막을 수 없으니, 발생 후의 해결 방법을 고민해본다. 1. 가벼운 교착상태 검출: 타이머 이용. 프로세스가 일정 시간동안 작업을 진행하지 않는다면 교착상태로 검출 - 일정시간마다 체크포인트 생성, 교착상태 예상 시에 롤백2. 무거운 교착상태 검출: '자원 할당 그래프'를 통해 프로세스에 할당된 자원을 모니터링 - 교착상태를 일으킨 프로세스 강제종료 - 체크포인트로 롤백 자원할당 그래프(Resource Allocation Graph)란 무엇일까?운영체제에서 자원이 할당되어 있는 상태를 그래프로 그려, 시각적으로 데드락의 여부를 판단- T = {T1, T2, ..., Tn}: 실행 중인 쓰레드- R = {R1, R2, ..., Rm}: 할당될 자원 타입- T_i → R_j: i 쓰레드가 j 자원을 요청한다- R_j → T_i: j 자원을 i 쓰레드에 할당되어 있다.위 예제에서는 3개의 쓰레드와 4개의 자원이 있으며 2개의 순환 구조를 갖고 있다.T1 → R1 → T2 → R3 → T3 → R2 → T1T2 → R3 → T3 → R2 → T2모든 쓰레드는 하나의 자원을 점유 중인 상태에서 다음 자원을 점유하기 위해 대기 상태에 있고, 이러한 상태가 원형을 이루어지고 있기 때문에 데드락에 빠질 확률이 높다고 판단한다. 📔 회고미션을 수행하면서도 강의를 들었을 때 고민하지 못했던 부분에 대해서 더 찾아보고 전체적인 흐름을 다시 정리해볼 수 있었다.MLFQ 스케줄링에서 I/O Boud Process를 정리하면서 우선순위가 높은 이유에 대해서 생각해보진 못했던 것 같은데,선점형과 비선점형의 특징을 알고, 선점형에서 I/O 작업이 응답 대기를 통해 다른 프로세스로 전환될 경우 CPU 작업 처리 비중은 적으니 빠른 작업 실행과 높은 우선순위를 가져갈 수 있다라는 것을 다시 한 번 전체적인 흐름과 다른 개념과의 연관을 통해 정리해볼 수 있었다.또한 질문의 답변을 통해서 강의를 듣고 추가로 공부해봤던 것들에 대해서 한 번 더 정리해볼 수 있는 시간을 가졌는데, 뮤텍스와 같은 상호배제 메커니즘이나 처음에 이해하지 못했던 자원 할당 그래프를 직접 다시 확인해보고 개념들을 이해해볼 수 있었던 것 같다.

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

재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?재귀함수는 함수 내부에서 자기 자신을 다시 호출하여 작업을 수행하는 함수를 의미한다. 즉, 자기 자신을 무한대로 호출하여 작업하기 때문에 함수 종료 조건인 기저조건을 설정하지 않는다면, 해당 함수가 실행됨에 따라 무한대로 콜스택에 메모리가 얹히게 되고 스택 오버플로우가 발생하여 프로그램이 강제 종료된다.// 기저 조건 없는 경우 function factorial(n){ return n * factorial(n - 1) } // RangeError : Maxmum call stack size exceeded // 기저 조건 설정 function factorial(n) { if (n == 0) return 1; return n * factorial(n - 1); }0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.하위조건 : n - 1이 홀수인지 확인하고 홀수일 경우 n을 더하고 짝수일 경우 0을 더함기저조건: n이 0 이하일 경우 0을 반환하고 함수 종료function sumOdd(n){ // 재귀 로직 if (n 다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.const fs = require('fs'); // 파일을 이용하는 모듈 const path = require('path'); // 폴더와 파일의 경로를 지정해주는 모듈 function traverseDirectoryRecursive(directory) { const files = fs.readdirSync(directory); // 1. 인자로 받은 폴더 내부 파일들 추출 for (const file of files) { const filePath = path.join(directory, file); // 2. 파일 경로 합치기 const fileStatus = fs.statSync(filePath); // 2. 파일 정보 얻기 if (fileStatus.isDirectory()) { // 3-1. 폴더일 경우 재귀 console.log('디렉토리:', filePath); traverseDirectoryRecursive(filePath); } else { // 3-2. 파일일 경우 출력 console.log('파일:', filePath); } } } traverseDirectoryRecursive('.'); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력하위 조건:인자로 받은 Directory의 파일과 폴더를 읽어온다파일 경로를 합치고 파일 정보를 얻어온다폴더일 경우, 재귀함수를 통해 내부 폴더의 파일과 폴더를 읽는다파일일 경우, 파일을 출력한다.기저조건:현재 폴더 내부 모든 파일 수만큼 반복📔 회고알고리즘 문제가 아닌 실전에서 사용할 수 있는 재귀 함수로 응용을 해보니 생각보다 하위조건을 파악하고 기저조건을 설정하는 것이 쉽지 않다는 것을 깨달았다. 처음에는 계속해서 코드를 읽어보면서 익숙하지 않은 fs모듈에 대해서 먼저 파악해보고, 제공되는 메서드들을 익혀보았다. 그렇게 코드의 흐름을 익혀가면서 반복되는 부분을 구분하였고, 재귀적으로 해결할 수 있는 부분은 while 문이라는 것을 파악했다. 기존에 스택을 통해서 파일들을 가져오고 데이터를 쌓아오면서 while 문을 통해 스택에 있는 데이터를 다시 출력하는 코드였다는 것을 파악하였고, 이를 재귀적으로 변경하기 위해서는 스택 자료구조를 사용하지 않고 하나의 함수에 하나의 폴더를 읽어오고 재귀적으로 함수를 다시 호출하면서 폴더 내부의 파일을 찾아가는 형식으로 수정할 수 있다는 것을 파악했다. 그렇게 하위조건을 설정하였고 기저조건을 만들어서 성공적으로 재귀함수로 코드를 수정할 수 있었다.이렇게 알고리즘을 응용하여 실전에서 사용할 수 있다는 것을 크게 깨달았고, 앞으로 알고리즘을 배울 때도 실전에서도 사용될 수 있는 다양한 사례를 함께 찾아보면서 공부하면 더 알고리즘 개념을 탄탄히 가져갈 수 있을 것 같다.

[인프런 워밍업 클럽 3기 - CS] - 2주차 발자국(자료구조와 알고리즘)

💻 알고리즘📌 재귀✅ 재귀 : 어떠한 것을 정의할 때 자기 자신을 참조하는 것✅ 콜스택 : 함수가 호출되면서 올라가는 메모리 영역 (메모리 스택 영역) - FILO(First In Last Out)함수를 호출하면 콜스택에 올라가고 종료되면 콜스택에서 종료된다. 1. 다른 함수 2개를 호출하는 상황1. A가 실행되고 콜스택에 올라간다2. A가 종료되고 콜스택에서 제거된다3. B가 실행되고 콜스택에 올라간다4. B가 종료되고 콜스택에서 제거된다2. 하나의 함수에서 다른 함수를 호출하는 상황1. A가 실행되고 콜스택에 올라간다.2. A 실행 중, B를 실행하고 콜스택에 올라간다.3. B가 종료되고 콜스택에서 제거된다.4. A가 종료되고 콜스택에서 제거된다.3. 재귀함수1. A-1이 실행되고 콜스택에 올라간다.2. 내부에서 기저 조건을 확인하고 거짓이라면 다음 문장을 실행시킨다.3. 재귀에 의해 A-2가 실행하고 콜스택에 올라간다.4. ...5. 기저 조건에 의해 함수가 종료된다.6. 가장 상위 함수부터 콜스택에서 제거된다.7. 만약 기저조건이 없었다면 무한으로 콜스택에 올라가 메모리 부족 현상 발생 📌 재귀적으로 생각하기1. 반복문을 재귀함수로 대체하는 것은 더 나쁜 효율성을 갖는다. (콜스택 메모리 차지)2. 하위 문제를 기반으로 현재 문제를 계산한다.3. 하향식 계산은 재귀함수만 할 수 있다. 📌 버블 정렬- 앞에 있는 데이터와 옆 데이터를 비교하여 자리를 바꾸고 정렬하는 방식- 성능이 아쉬움(O(n^2)) 📌 선택 정렬- 정렬되지 않은 영역의 첫 원소를 마지막 원소까지 비교하여 정렬하는 방식- 성능이 아쉬움(O(n^2)) 📌 더 찾아본 점❓ 하노이 탑✅ 재귀적으로 생각해봐야할 부분1. 마지막 원판(count) 위의 모든 원판은 temp로 가야한다. (to -> temp)2. 마지막 원판은 to 로 간다3. temp에 있는 모든 원판은 to로 가야한다.(from -> temp, temp -> from) ❓ 하노이 탑 (count: 4) 진행과정{ 4 A C B { 3 A B C { 2 A C B { 1 A B C console.log(1 block from A to B) } console.log(2 block from A to C) { 1 B C A console.log(1 block from B to C) } } console.log(3 block from A to B) { 2 C B A { 1 C A B console.log(1 block from C to A) } console.log(2 block from C to B) { 1 A B C console.log(1 block from A to B) } } } console.log(4 block from A to C) { 3 B C A { 2 B A C { 1 B C A console.log(1 block from B to C) } console.log(2 block from B to A) { 1 C A B console.log(1 block from C to A) } } console.log(3 block from B to C) { 2 A C B { 1 A B C console.log(1 block from A to B) } console.log(2 block from A to C) { 1 B C A console.log(1 block from B to C) } } } } 📔 회고🚀 최종 목표 : 로드맵을 마무리하고 알고리즘 문제들을 제대로 이해할 수 있을 정도의 수준이 되기.🚀 매주 규칙:각 섹션마다 하나의 .md 파일을 생성하고, 섹션 내 각 유닛은 헤더로 구분강의를 듣고 최대한 이쁘게 (?) 정리해놓기매 강의를 듣고 궁금하거나 이해가 안가는 부분은 추가적으로 더 찾아서 정리해두기강의에 관련된 알고리즘 최소 1문제씩 풀어 습관화 이번 주차에는 알고리즘에 대한 이론과 정의보다는 실제 코드를 작성해보면서 동작 원리를 익히는 게 주된 주차였다. 그에 맞춰서 알고리즘에 대한 이론보다 동작되는 과정을 익히고 코드로 어떻게 풀어나가는 지 이해하기 위해 직접 코드를 작성해보고 어떻게 진행되는 지 생각해보고 직접 작성해보았다.재귀함수의 대표적인 문제인 하노이 탑의 경우, 강의를 직접 듣고 원리와 코드를 한 번에 이해하기가 힘들어서 검색해보고 애니메이션도 확인하면서 이해하려 노력하였다. 여러 방식을 익혀봤지만 역시 동작되는 과정을 직접 타이핑해보는 것이 가장 이해가 빨랐던 것 같다.(하노이 탑 진행과정 코드) 이 뿐만 아니라 하노이 탑 시뮬레이터(라고 말하고 게임)도 있길래, 미리 동작 과정을 예상해서 코드로 타이핑을 하고 시뮬레이터에 그 코드 과정을 그대로 따라가면서 학습했던 것 같다.이번 주 목표 중 하나였던 알고리즘 최소 1문제 습관화 또한 달성하였다. 기존에는 백준이나 프로그래머스를 통해 문제를 풀어봤었는데 이번에는 영어 공부도 할 겸 leet 코드를 통해서 매일 알고리즘 문제를 풀어보았다. 매일 강의를 듣고 그 강의에서 배웠던 알고리즘 방식과 관련된 문제들을 찾아보고 최소 1문제씩 풀었다. 문제를 풀면서 AI 혹은 discussions에 나와있는 해설들을 절대 보지 않으려고 노력하였고 뭐가되든 첫 문제 풀이는 내 스스로 하는 것에 최대한 집중하였다. 그렇게 문제를 풀고 틀리게 되면 한 번 더 고민해보고 주변 도움을 구하였고, 만약 맞췄다면 그 이후 성능을 더 빠르게 문제를 풀 수 있는 방법이 있는지 찾아보기도 하였다.알고리즘 문제를 풀면서 다음 주에 해보고 싶은 규칙이 하나 생겼다. 현재는 내가 알고 있는 방식으로만 문제를 해결하고 있지만 직접 문제를 해결하지 않더라도 문제에 대해 알맞는 자료구조를 선택할 수 있는 능력을 기르는 것은 어떨까? 그래서 이 또한 GPT를 이용해서 여러 문제들에 대해 나열을 시키고, 그 문제를 해결할 수 있는 최적의 자료구조와 알고리즘을 답변하여 점점 더 개념을 탄탄히 하고 최적의 문제해결능력을 사고하는 능력을 길러보고 싶다. GPT를 통해 여러 문제를 리스트업하고 최적의 자료구조나 알고리즘을 맞춰보기