[인프런 워밍업 클럽 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를 통해 여러 문제를 리스트업하고 최적의 자료구조나 알고리즘을 맞춰보기

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

💻 운영체제📌 프로세스 동기화프로세스는 다른 프로세스와 데이터를 주고 받으며 통신한다.여러 프로세스가 공유자원에 접근하여 데이터를 수정하고 읽을 경우, 동기화 문제가 발생할 수 있다.공유 자원 : 프로세스 간 공유되는 변수나 파일임계 구역: 여러 프로세스가 동시에 사용하면 안되는 구역경쟁 조건: 공유 자원을 서로 사용하기 위해 경쟁하는 것상호배제의 요구사항임계 구역에는 하나의 프로세스만 접근할 수 있다여러 요청에도 하나의 프로세스만 접근 가능하다임계 구역에 들어간 프로세스는 최대한 빠르게 나와야 한다.상호배제 메커니즘세마포어세마포어 변수를 갖고있는 프로세스가 먼저 실행되고 작업이 완료되면 signal()을 통해 변수 반환세마포어 변수가 없는 프로세스는 대기 wait()세마포어 변수를 할당받으면 프로세스 실행 가능공유 자원 수에 따라 세마포어의 수 증가모니터운영체제의 차원이 아닌 프로그래밍 언어에서 처리자바에서 synchronized가 붙은 함수가 실행되면 다른 프로세스가 접근 불가함수를 임계 구역에 감싸지 않아도 되어 편리하게 구현 가능 📌 데드락교착상태(데드락): 여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 아무도 작업을 진행하지 못하는 상태필요조건1. 상호배제: 한 프로세스가 리소스를 점유하였다면 다른 프로세스 접근 불가2. 비선점: 점유중인 프로세스의 리소스를 뺏어갈 수 없음3. 점유와 대기: 한 프로세스는 리소스를 점유하고 있는 상태에서 다른 프로세스의 리소스 점유를 대기해야 함4. 원형대기: 점유와 대기를 하는 프로세스들의 관계가 원형이어야 함.회피교착상태는 발생할 수 밖에 없다 > 발생의 원인을 줄이거나 빠르게 해결 안정상태 (시스템 총 자원이 14라 가정)현재 총 12개의 작업이 할당되었다.P1이 4개의 자원을 요청하면 사용 가능한 자원이 2(14-12)개 남아있기에 거절P2가 2개의 자원 요청하면 사용 가능한 자원 2개 할당P2의 작업이 마무리되면 사용 가능한 자원 6개로 증가나머지 프로세스들의 요청 예상 자원 커버 가능 불안정상태현재 사용 가능 자원은 1(14-13)개이다.모든 프로세스들의 요청 예상 자원을 할당해줄 수 없다.모든 프로세스들이 최대 자원을 요구하지 않는다면 교착 상태에 빠지지 않을 수 있지만가능성이 높다 가벼운 교착상태 검출 : 타이머 이용. 프로세스가 일정 시간동안 작업을 진행하지 않는다면 교착상태로 검출 일정시간마다 체크포인트 생성, 교착상태 예상 시에 롤백무거운 교착상태 검출: '자원 할당 그래프'를 통해 프로세스에 할당된 자원을 모니터링교착상태를 일으킨 프로세스 강제종료체크포인트로 롤백 📌 메모리1. 레지스터: 가장 빠른 기억 저장소이자 휘발성 메모리. 메인 메모리 데이터를 CPU레지스터를 가져와 연산 후 계산 결과를 다시 메인 메모리에 저장2. 캐시: 메인 메모리에서 필요할 것 같은 데이터를 미리 캐시에 저장3. 메인메모리(RAM): 실제 운영체제와 프로세스들이 저장되는 휘발성 메모리4. 보조저장장치: 비휘발성 메모리이며 프로그램, 파일을 저장 물리 주소(절대 주소): 메모리 공간의 실제 주소논리 주소(상대 주소): 사용자가 다루는 메모리 주소1. 사용자가 프로그램 실행 - 사용자 입장에서는 0x0000 메모리로 작업2. 프로세스는 실제 물리주소 0x4000 주소에 저장3. 사용자가 0x0100 주소의 데이터 요청 (논리 주소)4. 논리 주소(0x0100)와 재배치 레지스터(실행 중인 프로세스의 물리주소 - 0x4000)을 더해서 0x4100의 값을 전달 메모리 할당 방식❓ 유니 프로그래밍 환경에서는 하나의 프로세스만 메모리에서 동작이 가능하다. 만약 메모리의 용량을 초과한 프로그램을 실행시키려면?✅ 스왑 과정이 존재하기 때문에 실제 메모리에 전체 프로세스가 올라가있는 것에 비하면 속도가 느리다.메모리 오버레이: 실행시킬 프로세스를 분할시켜, 사용되는 부분을 메모리에 올리고 나머지는 하드디스크 스왑 영역에 저장 ❓ 멀티 프로그래밍 환경에서는 어떻게 동작?1. 가변 분할 방식(세그멘테이션): 프로세스가 크기에 따라 메모리를 분리- 연속된 메모리 공간에 할당되기에 내부 단편화 현상 없음- 외부 단편화 발생: 연속된 공간에 할당을 해야하니 5MB 프로그램을 3MB와 2MB 공간에 할당이 불가하다.2. 고정 분할 방식(페이징): 프로세스 크기 상관없이 메모리 분리 (만약 5MB 프로그램을 2MB 고정 분할 메모리에 저장시키려면 2 / 2 / 1로 분리) -> 비연속 메모리 할당- 구현이 간단하고 오버헤드가 적음- 내부 단편화 발생: 위 예시에서 2MB 분할 공간에 1MB만 사용3. 버디 시스템(가변 + 고정): 2의 승수로 메모리를 분할하여 할당- 전체 메모리 영역을 하나의 프로세스가 올라갈 수 있을 정도로 2의 승수로 나눠서 분할- 최소한의 내부 단편화, 간단한 메모리 합치기 조각 모음 : 외부 단편화에서 분리된 메모리 공간을 합치는 작업 - 실행 중인 프로세스를 일시적으로 멈춰야 해서 오버헤드 발생 📌 더 찾아본 점IPC(Interprocess Communication)란?프로세스 간 협업을 위해 데이터를 공유하기 위해서는 IPC 기술이 필요하다 공유 메모리(Shared Memory): 공유 메모리 지역을 지정하고 프로세스들은 공유 메모리에 접근하여 데이터를 공유한다. (producer-consumer problem)메세지 패싱(Message Passing): 협력하는 프로세스 간 메세지 전달을 통해 데이터 동기화(communication link)를 통해서 각 프로세스가 소통한다. race condition이란?다수의 프로세스(혹은 쓰레드)가 같은 데이터를 동시에 접근하거나 처리하면, 실행되는 순서에 따라서 결과가 달라진다.이를 해결하려면 특정 시간에 하나의 프로세스만 공유 자원을 다뤄야 한다. 즉, 프로세스는 동기적으로 실행되어야 한다.1. 상호배제(Mutual Exclusion)을 보장해주어야 한다.- 한 프로세스가 "임계영역(citical section)"을 실행 중일 때, 다른 프로세스는 임계 영역을 실행할 수 없다.2. 데드락(deadlock)을 회피(진행)- 임계 영역에 들어갈 프로세스를 정하는 건, 임계 영역에 들어가야하는 프로세스들만 참여할 수 있다. - 영역에 들어가는 과정이 무한정 지연되는 것을 방지3. 유한 대기(Bounded Waiting) (starving 기아 상태 방지)- 임계 영역에 들어가기를 요청한 프로세스는 무한정 기다리면 안된다. 상호배제 메커니즘Mutex Locks: 임계 영역에 진입하면 lock을 acquire()와 release()를 통해 주고 받음Semaphore: 공유자원 수용가능 수에 따라 정수형 변수 s 변수를 초기화. wait(s)와 signal(s)를 통해 각 작업에서 s값을 중가, 차감 자원할당 그래프(Resource0Allocation 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모든 쓰레드는 하나의 자원을 점유 중인 상태에서 다음 자원을 점유하기 위해 대기 상태에 있고, 이러한 상태가 원형을 이루어지고 있기 때문에 데드락에 빠질 확률이 높다고 판단한다. 메모리 주소 바인딩1. symbolic address: 소스 프로그램에 변수와 같이 메모리 주소를 상징적으로 저장2. relocatable address: 실제 메모리 주소가 결정될 수 있는 재배치 가능 주소3. absolute address: 컴파일 타임에 결정되는 메모리 주소 1. compile time: 컴파일 시점에 물리 주소가 결정 (`absolute address`로 결정)2. load time: 컴파일 시점에 메모리 위치가 확정나지 않았다면, relocatable code로 변환. 프로세스가 로드되어 메모리에 올라갈 때 물리 주소가 결정3. execution time: 프로그램 실행 도중에 메모리 주소가 변경될 수 있다면 런타임까지 바인딩 지연. MMU에 의해서 논리 주소를 물리 주소 결정 📌 백엔드 면접 질문해보기데드락과 라이브락의 차이점?데드락은 두 개 이상의 쓰레드가 자원을 점유하고 있지만 다른 자원을 점유하기 위해 대기 중인 교착 상태를 의미합니다. 라이브락이란 두 개 이상의 쓰레드가 충돌을 회피하기 위해 실패 작업을 반복하지만 진전이 없는 상태를 의미합니다.데드락은 교착 상태에서 모든 프로세스가 멈춰버리지만 라이브락은 실패 작업을 계속 시도하기 때문에 멈추지는 않습니다. 락 기반 동기화와 락 프리 알고리즘이란?락 기반 동기화란 하나의 프로세스만 공유자원을 사용하도록 강제하여 동기화시키는 방법입니다. 뮤텍스나 세마포어가 락 기반 동기화에 해당됩니다. 락 기반 기법은 두 개 이상의 스레드가 서로 상대방의 락의 해제를 기다린다면 데드락이 발생할 수 있으며, 낮은 우선순위의 스레드가 자원을 먼저 점유하면 높은 우선순위의 스레드가 대기를 해야하는 우선순위 역전 등의 문제가 있습니다.락 프리 알고리즘이란 락을 사용하지 않고도 동기화를 유지시킬 수 있는 알고리즘입니다. 해당 알고리즘은 CAS(Compare And Swap) 같은 원자적 연산을 통해 동기화를 보장하는데, 원자적 연산이란 연산이 중간에 중단없이 시작되지 않거나 완전히 수행되는 것(all or nothing)을 의미하며 CAS는 해당 원자적 연산을 기반으로 현재값을 읽고 예상했던 값과 일치할 경우에만 값을 변경하며 일치하지 않는다면(다른 쓰레드의 개입) 업데이트하지 않는 방식입니다. Node.js에서 데드락이 발생할 수 있을까? 공식 문서에 따르면 Node.js에는 락이 존재하지 않아서 데드락이 발생될 확률이 매우 적다고 적혀있습니다. 다만 libuv에서 제공하는 동기적인 메서드를 실행할 때, js파일에 대해 대기 상태가 발생할 수 있는데 이는 데드락이라기 보다는 Blocking에 해당합니다. 또한 이러한 동기 I/O 메서드에 대해서도 콜백을 포함한 비동기 처리 함수가 함께 제공됩니다. (readFileSync / readFile) V8 엔진 메모리 관리 방식은? V8 엔진은 node.js의 실행 엔진이며 컴파일과 GC를 포함하고 있다.V8 메모리 구조(Resident set)은 크게 Heap과 Stack 메모리로 구분된다.Heap에는 크게 New Space와 Old Space가 존재하며 New Space는 짧은 생명주기를 갖는 새로 생성된 객체들이 저장되며 2번의 minor GC에도 제거되지 않은 객체는 Old Space로 이동되어 저장된다. New Space는 minor GC, Old Space는 Major GC로 참조되지 않는 변수들을 가비지 컬렉팅 한다. Buffer와 Stream의 메모리 사용 방식 차이? Buffer: 데이터를 조각(chunk)내어 buffer에 다 차우면(buffering) 일괄로 데이터를 전송. - 메모리의 사용 비율이 크지만 데이터 처리 속도가 크게 향상Stream: 데이터 청크와 버퍼의 크기를 작게하여 지속적으로 데이터를 전달하는 방식 - 메모리 사용이 적지만 데이터 실시간 효율성이 높아짐 📔 회고🚀 최종 목표 : 더 효율적인 백엔드 개발을 위해 기본적인 운영체제 지식들을 확실히 잡아가기🚀 매주 규칙:각 섹션마다 하나의 .md 파일을 생성하고, 섹션 내 각 유닛은 헤더로 구분강의를 듣고 최대한 이쁘게 (?) 정리해놓기 매 강의를 듣고 궁금하거나 이해가 안가는 부분은 추가적으로 더 찾아서 정리해두기매 강의 내용을 백엔드 관점에서 고민해보고 GPT와 대화를 통해 정리첫 주차 발자국과 미션을 수행한 후에 이번 주에는 더 구체적이고 집중적으로 강의를 듣고 복습할 수 있게 방식을 수정하였다.규칙 3번에서 매 강의를 듣고 궁금하거나 이해가 안가는 부분에 대해서는 보통 검색을 통해 블로그를 찾아보고 정리하였었다. 하지만 블로그에 적혀있는 글마다 내용이 다르기도 하고 궁금증이 해소되지 않는 부분들이 있어, 더 찾아보던 도중 CS로 유명한 공룡책(Operating Systerm Concepts) 무료 영문 pdf파일을 발견하였고 그 날 강의에 해당하는 주제에 맞춰 공룡책을 공부하고 개념을 탄탄히 하는 것에 집중하였다. 추가적으로 인프런 강의 중에 무료로 공룡책에 대한 내용을 설명해주는 강의도 있어 함께 공부를 하니 더 깊이 있고 쉽게 개념을 잡아갈 수 있었던 것 같다.규칙 4번에서 처음에는 백엔드 관점으로 강의 내용을 살펴보려 하였는데, 생각보다 모호하고 막연하다고 생각하여 규칙을 조금 변경하였다. GPT에는 Node.js 전문가 프롬프트가 제공되어 있어서, 해당 프롬프트를 이용하여 오늘 배운 내용에 대해 이야기하고 백엔드 면접 질문을 리스트로 달라고 요청하면 기초부터 고급 그리고 node.js를 활용한 심화 질문까지 리스트업해준다. 해당 부분에 대해서 스스로 답변해보고 답변하지 못한 부분이나 설명이 부족한 부분은 다시 AI와 대화하면서 지식을 채울 수 있었던 것 같다.결과적으로 3. 매 강의 듣고 해당 내용 공룡책 & 강의 1회 정독 및 수강 / 4. 매 강의에 대한 내용 백엔드 면접 질문을 추려서 답변하고 개념 구체화하기 이렇게 수정하여 2주차를 진행하였다. 기존 독학으로 CS를 공부하였을 때는, 그 범위가 너무 넓어 어떤 부분을 공부하고 있는지도, 어디까지 공부해야할 지도 전혀 감을 잡을 수 없었는데 이렇게 강의를 수강하고 그 강의의 깊이있는 개념까지 찾아가며 공부하다보니 확실히 체계가 잡히고 개념도 탄탄히 공부해 볼 수 있는 것 같다. 해당 방식으로 공부하면 딱 몰입할 수 있을만큼 적당히 공부하는 것 같아서 다음 주에는 추가적인 규칙을 넣기보다 기존 규칙을 유지해보려고 한다.

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

💡 자료구조와 알고리즘 미션여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.✅ 해시 테이블을 이용하여 학생의 정보를 저장할 것 같다.해시 테이블은 해시 함수를 통해 입력값의 key를 받아 고유한 값 index로 변환을 시켜 테이블에 저장하는 자료구조이다.O(1)의 시간 복잡도로 데이터 삽입, 삭제, 조회가 가능하기 때문에 가장 효율적으로 학생의 정보를 관리할 수 있다.하지만 해시 함수에 의해 다른 데이터가 동일한 버킷에 할당되어 충돌이 발생한다면 O(n)의 시간 복잡도로 효율성이 줄어들 수 있다.이를 해결하기 위해, 각 버킷마다 연결리스트를 통해 충돌 데이터를 이어주는 분리 연결법, 또는 버킷에 하나의 데이터만 저장하고 충돌 시 다른 비어있는 버킷에 할당해주는 개방 주소법을 통해 충돌을 방지할 수 있다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.✅ "주문은 들어온 순서대로 처리됩니다"라는 의미는 FIFO(First In First Out)를 뜻하며, 해당 개념의 대표적인 자료구조는 큐(Queue) 가 있다.큐는양방향 리스트로 구현이 가능하며head와 tail 노드가 지정되어, 첫 노드가 처리 후 제거되어도 다음 tail을 O(1)의 시간복잡도로 조회가 가능하고각 노드가 prev와 next를 통해 앞, 뒤 노드의 주소를 저장하고 있어서 삽입, 삭제 또한 O(1)의 시간복잡도로 작업이 가능하다. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.✅기존: 1, 2, 3, 4 입력 시, (출구)[1,2,3,4](입구) , 4->3->2->1 로 출력변경: 1, 2, 3, 4 입력 시, 삽입 -> (출구)[4,3,2,1](입구) 후, 4->3->2->1 로 출력ReverseStack 클래스 작성class ReverseStack { constructor() { this.list = new LinkedList(); } push(data){ this.list.insertLast(data); } pop() { try { return this.list.deleteLast(); } catch (error) { return null; } } peek() { return this.list.getNodeAt(this.list.count-1) } isEmpty() { return this.list.count === 0; } printAll() { this.list.printAll() } }// 결과 출력 let reverseStack = new ReverseStack(); let stack = new Stack(); console.log("=======Stack input======="); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.printAll(); console.log(stack.pop().data); console.log(stack.pop().data); console.log(stack.pop().data); console.log(stack.pop().data); console.log("=======ReverseStack input======="); reverseStack.push(1); reverseStack.push(2); reverseStack.push(3); reverseStack.push(4); reverseStack.printAll(); console.log(reverseStack.pop().data); console.log(reverseStack.pop().data); console.log(reverseStack.pop().data); console.log(reverseStack.pop().data); =======Stack input======= [4, 3, 2, 1] 4 3 2 1 =======ReverseStack input======= [1, 2, 3, 4] 4 3 2 1사실 문제를 제대로 이해했는 지 맞나 모르겠다 ㅎㅎ..스택은 결국 FILO(First In Last Out)이니 입구와 출구가 동일하다고 볼 수 있지 않나..? 라고 생각했지만인덱스가 전환되는 것에 집중하여 기존에 삽입된 인덱스가 전환되는 형태로 스택을 수정하였다.즉, 연결리스트의 head부분으로 저장되는 것이 아닌 tail (여기서는 리스트의 count 인덱스)에 데이터를 연결하면 마지막 인덱스부터 저장되는 스택을 구현할 수 있었다. 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력✅hashFunction(name){ // 1. 이름 유니코드로만 설정 : 63.6% return name.charCodeAt(0) % 10; // 2. 이름의 각 유니코드를 더한 값 : 63.6% return [...name].reduce((acc, cur) => acc + cur.charCodeAt(0), 0) % 10; // 3. 첫 자의 유니코드의 각 숫자를 합친 값 : 54.5% return [...(name.charCodeAt(0) + '')].reduce((acc, cur) => acc + cur.charCodeAt(0), 0) % 10; }// 중복 비율 계산 getDuplicateFrequency(arr) { let array = arr.map((name) => this.hashNameFunction(name)); const frequency = array.reduce((acc, cur) => { acc[cur] = (acc[cur] || 0) + 1; return acc; }, {}); let duplicatedCount = 0; let totalCount = array.length; for (let key in frequency) { if (frequency[key] > 1) { duplicatedCount += frequency[key]; } } console.log(Math.round((duplicatedCount / totalCount) * 100 * 10) / 10); }좋은 해시 함수를 작성하는 것은 어려운 것 같다. 여러 방면에서 코드를 작성해봐도 생각보다 중복 비율이 줄어들지는 않는 것 같다. 📒 회고이번 주말은 여러 일정이 겹쳐있어서 미션을 수행할 시간이 많이 부족했뿐만 아니라, 생각보다 미션이 오래 걸렸던 것 같다. 다음 주 부터는 미리미리 강의 정리하면서 발자국도 함께 작성하는 것이 중요할 것 같고 미션도 올라오는 대로 바로 시작해야 안정적으로 미션을 제출할 수 있을 것 같다. 추가로 스터디에서 사람이랑 미션에 대해서도 얘기해보며 집단 지성을 이용해서 조금 더 획기적인 아이디어들을토론하고 고민해보는 것도 좋은 생각일 것 같다!

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

1주차 운영체제 미션 while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?✅ 폴링방식이란 CPU가 지속적으로 장치나 하드웨어의 상태를 확인하여 변화를 확인하는 방식이다. 예제 코드의 경우 while문을 통해 1초마다 반복적으로 isActivated의 상태를 확인해주고 있다.하나의 스킬만 확인한다면 큰 문제는 없을 수 있지만 점차 확인해야할 스킬의 수가 많아지거나, 스킬을 사용하는 객체의 수가 증가할수록 CPU는 다수의 장치를 지속적으로 확인해야 하기에 다른 중요한 작업의 처리 속도가 늦어질 수 있다. 또한 상태 확인 주기를 1초로 고정하였기 때문에 0.1초에 작업이 완료되어도 다음 다음 폴링 주기(0.9초 후)까지 사용자 응답이 지연된다는 단점이 있다. 해당 방식을 해결하기 위해서는 폴링 방식 대신 인터럽트로 변경해볼 수 있다. 인터럽트는 프로그램 실행 중, 특정 이벤트가 발생하면 즉시 실행은 중단하고 해당 작업을 먼저 수행하는 방식을 의미한다.// 스킬명, 쿨타임 const SKILL = { Q: { name: "Q", time: 1 }, W: { name: "W", time: 2 }, E: { name: "E", time: 3 }, R: { name: "R", time: 4 }, }; // 스킬 사용 상태 확인 const skillState = Object.values(SKILL).reduce((acc, skill) => { acc[skill.name] = { isActive: false, lastUsed: 0 }; return acc; }, {}); document.addEventListener("keydown", (event) => { const inputKey = event.key.toUpperCase(); const skill = skillState?.[inputKey]; const now = Date.now(); if (!skill) return; if (!checkSkillActivated(skill)) return; // 현재 - 마지막 스킬 사용 시간이 쿨타임보다 적다면 사용 가능 if (now - skill.lastUsed >= skill.time * 1000) { skill.isActive = true; skill.lastUsed = now; // 쿨타임 이후, 스킬 활성화 false setTimeout(() => { skill.isActive = false; }, SKILL[inputKey].time * 1000); } }); const checkSkillActivated = (skill) => { if (!skillState?.[skill]) return false; return skillState[skill].isActive; }; 기존에는 스킬을 1초마다 체크하게 확인 하였다면작성된 코드에서는 스킬을 사용할 때만 스킬을 체크하도록 수정하였다. 이벤트 리스너를 통해서 키 입력을 받으면해당 스킬이 존재하는지.스킬을 사용할 수 있는지 체크하여 스킬을 발동시키고 쿨타임과 스킬 사용 활성화를 true로 설정하였다.setTimeout을 통해 스킬의 쿨타임 뒤에 스킬 사용 활성화를 false로 변경해주었다. 프로그램과 프로세스가 어떻게 다른가요?✅ 프로그램이란 저장장치에 저장된 명령문의 집합체이며 프로세스는 실제 실행 중인 프로그램을 의미한다.프로그램은 실행하기 전까지 저장장치에 저장만 되어 있는 수동적인 존재이지만 프로세스는 실행되면 .exe 파일이 실행되어 메모리에 코드, 데이터, 스택, 힙 영역 등에 올라가며 CPU 연산과 I/O를 사용하는 능동적인 존재이다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?✅ 멀티프로그래밍이이란 메모리에 여러 개의 프로세스를 올려 하나의 CPU 작업을 수행하는 것을 의미한다. I/O 작업으로 해당 프로세스에서 CPU가 연산을 수행하지 못한다면 대기하지 않고 다른 프로세스에 할당되어 사용된다.멀티프로세싱이란 여러 개의 CPU로 다수의 프로세스 작업들을 동시에 수행하는 것을 의미한다. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?✅ PCB(Process Control Block)을 통해 프로세스를 관리한다. PCB에는 포인터 구조, 프로세스 상태, PID, 프로그램 카운터, 레지스터 정보 등 프로세스에 필요한 다양한 정보들을 담고 있으며 운영체제는 PCB를 통해 상태를 조회하고 컨텍스트 스위칭을 실행할 수 있다.PCB 정보포인터 구조 : 부모, 자식 프로세스에 대한 포인터(주소) 저장프로세스 상태: 프로세스의 현재 상태를 저장(생성, 준비, 대기, 실행, 완료)PID: 프로세스 식별 ID 저장프로그램 카운터: 다음에 실행되어야 할 명령어 위치 저장레지스터 정보: 프로세스 실행될 때, CPU에 저장되었던 레지스터 정보 저장 컨텍스트 스위칭이란 뭔가요?✅ 프로세스가 실행 중인 상태에서 다른 프로세스를 실행하기 위해 실행 중인 프로세스 상태를 저장하고 다른 프로세스로 교체하는 것을 의미한다. 운영체제에 의해 실행 중인 PCB의 내용이 수정되고, 교체될 PCB의 내용이 CPU에 세팅된다. 컨텍스트 스위칭 과정1. 프로세스 A의 CPU 점유 시간 초과2. 인터럽트 발생3. CPU의 레지스터 값 등을 PCB A에 저장4. PCB B를 참조해서 이전 프로세스 B의 작업을 이어감- 프로그램 카운터(다음에 실행될 명령어 주소)를 통해 이어서 명령어 실행 가능5. 프로세스 B의 CPU 점유 시간 초과6. 인터럽트 발생7. CPU의 레지스터 값 등을 PCB B에 저장 📒 회고이번 주말은 여러 일정이 겹쳐있어서 미션을 수행할 시간이 많이 부족했뿐만 아니라, 생각보다 미션이 오래 걸렸던 것 같다.다음 주 부터는 미리미리 강의 정리하면서 발자국도 함께 작성하는 것이 중요할 것 같고 미션도 올라오는 대로 바로 시작해야안정적으로 미션을 제출할 수 있을 것 같다. 추가로 스터디에서 사람이랑 미션에 대해서도 얘기해보며 집단 지성을 이용해서 조금 더 획기적인 아이디어들을토론하고 고민해보는 것도 좋은 생각일 것 같다!