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

안녕하세요. 저는 3년차 Node.js 백엔드 개발자입니다. 벌써 1주차가 지나가고 있네요... 그동안 걸어온 발자국을 남겨보고자 글을 적게 되었습니다.클럽을 시작한 계기부끄럽지만 저는 기본기가 부족한 개발자였습니다. 연차가 쌓여가면서 현업의 다양한 문제를 해결할 때 마다 CS지식의 중요성을 뼈저리게 느끼게 되었고 최근에 동시성에 대해 공부하면서 단순히 구현만 할 수 있는 개발자를 넘어 그 안의 원리를 이해하는 것이 필요하다는 것을 절실하게 느끼게 되었습니다. 그러던 중 인프런에서 주최하는 워밍업 클럽이라는 좋은 프로그램을 접하게 되었고 고민없이 바로 신청하게 되었습니다.학습 회고제가 배운 지식들은 다음과 같습니다.자료구조와 알고리즘에서는 시간복잡도, 배열, 연결리스트, 스택, 큐, 덱, 해시테이블, 셋을 배우게 되었습니다. 자료구조와 알고리즘은 밀접한 관계를 가진다는 것을 알게 되었습니다. 그리고 추상적으로 개념만 알고 있던 내용들을 직접 구현하면서 원리를 이해할 수 있어서 자료구조를 선택할 때 더 나은 결정을 할 수 있게 될거 같습니다.운영체제에서는 운영체제의 역사, 구조, 하드웨어 구조, 부팅 과정, 인터럽트, 프로그램과 프로세스, 컴파일 과정, CPU 동작 과정, 유니프로그래밍, 멀티프로그래밍, 멀티태스킹, 멀티프로세서, 멀티프로세싱, PCB(Process Control Block), 컨텍스트 스위칭, 프로세스 생성과 종료, 쓰레드, CPU 스케줄링을 배우게 되었습니다. 사실 운영체제가 정말 저에게 필요한 과정이였습니다. 부분적으로 알고있거나 잘 모르고 지나가던 시스템의 내부 동작에 대해 명확하게 이해할 수 있었습니다.칭찬하고 싶은 점1주차의 강의와 과제를 밀리지 않고 해냈다는 점 자체를 칭찬하고 싶습니다. 또한 저는 눈으로 강의를 보면서 손으로 필기하고 귀로 목소리를 들으면서 좀 더 학습의 효율을 올리려고 하고 있습니다. 이해가 되지 않는 부분은 이해가 될 때 까지 추가적으로 AI로 자료를 찾아보면서 이해하려고 하였습니다.아쉬웠던 점아무래도 직장을 다니면서 남는 시간에 학습해야 했기 때문에 상대적으로 시간이 부족했습니다. 특히 이번주는 일정이 많아 시간을 내기 어려워서 한번에 들을 수 밖에 없었습니다. 일별로 들을 범위가 정해진 것은 복습을 통해 좀 더 내용을 이해할 수 있도록 가이드하는 것인데 그 부분을 챙기지 못했습니다. 그 부분이 아쉽습니다.보완하고 싶은 점이번 워밍업 클럽의 우선순위를 높여서 시간을 내서 강의를 들어야 할 거 같습니다. 다음주부터는 알고리즘과 프로세스 동기화, 데드락, 메모리에 대해서 학습하게 되는데 이 내용들이 다 난이도가 있어서 좀 더 시간을 내고자 해야할 것으로 보입니다.다음주 목표벌써 다음주가 기대가 됩니다...! 그냥 추상적으로만 알고 넘어갔던 동시성에 대한 문제를 다루는 것으로 보입니다. 단순히 구현만 할 수 있는 개발자를 넘어서 그 원리까지 이해할 수 있는 개발자가 되고자 좀 더 학습에 몰두하는 것이 목표입니다.미션 해결과정우선 운영체제의 경우 강의에 나온 내용들을 이해했다면 충분히 답을 할 수 있는 질문이였다고 생각합니다. 따라서 운영체제는 언급하지 않고 자료구조와 알고리즘의 미션에 대해서만 이야기 하도록 하겠습니다. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.우선 학생 정보가 어떤 특징을 가지고 있는지에 대해 고민하였습니다. 학생 정보는 출석번호를 통해 접근하고 그 안의 데이터는 읽기, 삽입 삭제의 성능이 어느정도 준수해야 한다고 생각했습니다. 다른 자료구조로 구현을 하게 되면 학생의 정보가 많아지게 되는 경우 전학을 가거나 오게 되는 경우 O(n)의 성능을 가지게 되고 이는 성능상 문제가 된다고 생각하였습니다. 따라서 공간을 많이 사용한다는 단점을 감수하고 해시테이블을 선택하게 되었습니다.여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.주문이 들어온 순서대로 처리가 된다는 부분에 좀 더 집중하였습니다. 그리고 이런 요구사항을 쉽게 구현할 수 있는 자료구조는 큐라고 생각하였습니다. 큐에 처리해야하는 주문 데이터가 들어오면 주문 순서에 따라 순차적으로 처리가 될 것으로 예상했습니다.우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.이 부분은 우리가 강의 시간에 배운 양방향 연결리스트를 통해 해결할 수 있다고 생각하였습니다. 맨 처음에 데이터를 입력하게 되는 경우 첫 데이터가 head가 되고 계속 데이터를 입력하게 되면 해당 부분이 tail이 되도록 수정하였습니다. 그렇게 수정을 하게 난 후 테스트 결과 정상 동작하는 것을 확인하였습니다.해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력문제의 힌트를 참고하여 구현하게 되었습니다. return name.charCodeAt(0) % 10; 이렇게 구현하였습니다. 문자열의 첫 문자의 유니코드를 가져와 그 값을 나눈 나머지를 사용해서 해시 테이블을 구현하는 방식입니다. 하지만 이 방식이 과연 데이터를 골고루 분산을 시키는 코드인지에 대한 의문이 있었습니다. 그래서 실제로는 어떻게 구현을 했을까에 대한 의문점이 생겼습니다. 저는 Node.js를 사용하는 개발자이기에 JS의 Map 자료구조의 특성에 대해 좀 더 조사하게 되었습니다.Node.js에서의 Map 자료구조의 해시함수 알고리즘Node.js는 V8 엔진을 기반으로 실행되므로, Node.js에서 Map 자료구조의 해시 함수는 V8 엔진 내부에서 관리되며, Map의 내부 해싱은 V8 엔진의 OrderedHashMap 구현을 따릅니다.이때 string인지 number인지 object인지에 따라 내부 처리가 다르게 동작합니다. 하나 하나씩 보도록 하겠습니다.string일 경우문자열을 키로 사용할 경우, V8은 OneByteStringHasher (ASCII) 또는 TwoByteStringHasher(유니코드) 를 사용하여 해시 값을 계산합니다.해싱 과정은 문자열을 특정 숫자로 변환(해싱)하고 해시 값을 버킷 인덱스로 변환하여 충돌이 발생하면 체이닝(chaining) 방식 사용합니다.V8 내부 코드에서 문자열 해싱은 MurmurHash2/3 기반으로 최적화된 버전을 사용합니다.uint32_t StringHasher::HashSequentialString(const uint8_t* chars, int length, uint32_t seed) { uint32_t hash = seed; for (int i = 0; i number인 경우이 경우는 크게 두가지로 나뉩니다.정수(int32 범위) 키는 그 자체로 해시 값으로 사용됩니다.64비트 부동소수점(double) 숫자는 비트 패턴을 XOR 연산하여 32비트 해시 값 생성합니다.uint32_t NumberToHash(double num) { if (num == 0) return 0; uint64_t bits = bit_cast(num); // 비트 변환 return static_cast(bits ^ (bits >> 32)); // 상위 비트와 XOR }object인 경우객체를 Map의 키로 사용할 경우, 객체의 메모리 주소를 기반으로 해싱이 이루어집니다. V8 엔진은 객체마다 숨겨진 ID(hidden identity hash) 를 생성하고 이 ID는 객체가 처음 Map의 키로 사용될 때 할당됩니다. 이때 객체가 이동(가비지 컬렉션 등)해도 변하지 않습니다.객체 해싱 과정은 객체가 처음으로 Map의 키로 사용될 때 V8은 객체에 Hidden Symbol을 할당합니다. 해당 심볼을 기반으로 해시 값을 생성하고 메모리 주소 기반으로 ID를 생성하지만, 가비지 컬렉션이 일어나도 유지되도록 관리합니다.uint32_t Object::GetOrCreateIdentityHash(Isolate* isolate) { if (!HasIdentityHash()) { uint32_t hash = GenerateRandomHash(); // 해시 값 생성 SetIdentityHash(hash); } return identity_hash_; }이상입니다. 지금까지 긴 글을 읽어주셔서 감사합니다.

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

1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.학생의 출석번호를 통해 관리를 하고 학생 정보를 저장할 수 있는 해시테이블을 사용할 것입니다. 학생의 정보는 수시로 바뀔 수 있다고 생각합니다. 전학생이 올 수도 있고 기존 학생이 전학을 갈 수 도 있다고 생각합니다. 배열의 경우 읽기 효율이 좋지만 삽입, 삭제 효율이 좋지 않습니다. 연결리스트의 경우 읽기 효율이 떨어져 요구사항에 부합하지 않습니다. 그에 따라 읽기, 삽입, 삭제의 효율이 좋은 해시 테이블을 사용할 것입니다.2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.들어온 순서대로 처리해야한다는 요구사항이 있어서 해당 주문 프로그램은 큐 자료구조를 선택할것입니다.3. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.export class MyStack2 { constructor() { this.list = new DoublyLinkedList(); } push(data) { this.list.insertAt(this.list.count, data); } pop() { try { return this.list.deleteAt(this.list.count - 1); } catch (e) { return null; } } peek() { return this.list.getNode(this.list.count - 1); } isEmpty() { return this.list.count === 0; } }4. 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요.힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력newHash(name) { return name.charCodeAt(0) % 10; }

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

while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }1. 위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?인터럽트를 사용하면 됩니다. 인터럽트의 동작 방식은 다음과 같습니다. CPU가 입출력 관리자에게 명령을 내리고 다른 작업을 합니다. 그런 다음 입출력 관리자는 입출력이 완료된 후 CPU에게 신호를 줍니다. CPU는 ISR(인터럽트 서비스 루틴)을 실행시켜 작업을 완료합니다. ISR이란 특정 인터럽트가 들어오면 그 인터럽트를 처리하는 함수입니다.인터럽트를 사용하게 되면 비동기적으로 동작해서 성능에 이점이 있음. 인터럽트는 하드웨어, 소프트웨어 두가지 방식이 있습니다. 첫번째로 하드웨어 방식인데 입출력이 발생하는 경우 인터럽트가 발생합니다. 소프트웨어에서 발생하는 경우도 있는데 사용자 프로그램에서 유효하지 않은 메모리 접근이나 0으로 나누기 같은 사례에서 발생하게 됩니다.2. 프로그램과 프로세스가 어떻게 다른가요?프로그램은 저장장치에 저장된 명령문의 집합체입니다. 저장장치에만 저장이 되어 있는 상태입니다.프로세스는 실행중인 프로그램이며 프로그램이 메모리에 올라간 경우입니다. 메모리도 사용, CPU 스케줄링 알고리즘에 따라서 CPU도 사용, 필요에 따라 입력과 출력을 합니다.3. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍은 메모리에 여러개의 프로세스가 올라가 처리하는 것입니다. CPU가 프로세스를 실행하다가 IO 작업을 만나면 기다리면서 다른 프로세스를 실행하게 됩니다. 멀티프로그래밍에서는 멀티태스킹을 하게 되는데 이는 각각의 프로세스를 짧게 실행시키면서 모든 프로세스를 동시에 실행시키는 것 처럼 느끼게 하는 기술입니다. 멀티프로세싱은 여러 CPU가 작업을 처리하는 것입니다. 실제로 여러 작업이 병렬적으로 돌아가게 됩니다. 요약하자면 멀티프로그래밍은 각각의 프로세스를 짧게 실행시키면서 모든 프로세스를 동시에 실행시키는 것 처럼 느끼게 하는 것이고 멀티프로세싱은 여러 CPU가 작업을 동시에 병렬적으로 처리하는 것을 말합니다.4. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?PCB(Process Control Block)를 사용합니다. 해당 프로세스의 정보를 가지고 있는 것입니다.PCB는 연결리스트라는 자료구조로 저장되며 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거합니다. PCB의 구조포인터: 부모와 자식 프로세스에 대한 포인터와 할당된 자원에 대한 포인터 등이 있고 프로세스의 한 상태에서 다른 상태로 전환될 때 저장하는 포인터를 가지고 있음. 효율적인 접근을 위해서 포인터를 사용함.프로세스 상태: 현재 프로세스의 다섯가지 상태(생성, 준비, 실행, 대기, 완료)를 나타냄프로세스 ID: 프로세스를 식별하기 위한 숫자가 저장됨.프로그램 카운터: 다음에 실행될 명령어의 주소를 포함하는 프로그램 카운터를 저장함. 다른 프로세스를 실행하다가 다시 돌아왔을 때 마저 명령을 실행해야해서 필수다.레지스터 정보: 프로세스가 실행될 때 사용했던 레지스터 값들이 저장됨. 다른 프로세스를 실행하다가 다시 돌아왔을 때 이전에 사용하는 값을 복구하기 위한 용도다.메모리 정보: 프로세스가 메모리에 있는 위치 정보, 메모리 침범을 막기 위한 경계레지스터 값등이 저장됩니다.CPU 스케줄링 정보: CPU 스케줄링에 필요한 우선순위, 최종 실행시간, CPU 점유시간등이 저장됩니다.5. 컨텍스트 스위칭이란 뭔가요?프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해서 실행중인 프로세스 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업입니다.컨텍스트 스위칭이 실행되면 PCB의 내용이 바뀌며 실행중인 프로세스의 작업내용을 PCB에 저장하고 실행될 기존 프로세스의 PCB의 내용대로 CPU가 다시 세팅됩니다.PCB에서 변경되는 값으로는 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 정보 등이 있습니다.한 프로세스가 CPU를 너무 오래 점유하는 경우 운영체제가 인터럽트를 발생시켜 컨텍스트 스위칭을 진행합니다. 컨텍스트 스위칭이 발생하는 경우는 CPU 점유시간이 만료되거나, IO요청이 있거나 다른 종류의 인터럽트가 있을 때 발생합니다.