[인프런 워밍업 클럽 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 문을 통해 스택에 있는 데이터를 다시 출력하는 코드였다는 것을 파악하였고, 이를 재귀적으로 변경하기 위해서는 스택 자료구조를 사용하지 않고 하나의 함수에 하나의 폴더를 읽어오고 재귀적으로 함수를 다시 호출하면서 폴더 내부의 파일을 찾아가는 형식으로 수정할 수 있다는 것을 파악했다. 그렇게 하위조건을 설정하였고 기저조건을 만들어서 성공적으로 재귀함수로 코드를 수정할 수 있었다.이렇게 알고리즘을 응용하여 실전에서 사용할 수 있다는 것을 크게 깨달았고, 앞으로 알고리즘을 배울 때도 실전에서도 사용될 수 있는 다양한 사례를 함께 찾아보면서 공부하면 더 알고리즘 개념을 탄탄히 가져갈 수 있을 것 같다.