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

지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블정렬,선택정렬,삽입정렬,병합정렬,퀵정렬이 있습니다.. 버블정렬성능 : O(n²)의 성능을 가집니다장점 : 구현이 쉽고 단순합니다.단점 : 성능이 좋지않아 대규모 데이터 처리에 좋지않습니다. 선택정렬성능 : O(n²)의 성능을 가집니다장점 : 구현이 쉽고 단순합니다. (버블정렬과 동일)단점 : 성능이 좋지않아 대규모 데이터 처리에 좋지않습니다. (버블정렬과 동일) 삽입정렬성능 : O(n²)의 성능을 가집니다장점 : 구현이 쉽고 단순합니다. (버블정렬과 동일)단점 : 성능이 좋지않아 대규모 데이터 처리에 좋지않습니다. (버블정렬과 동일) 병합정렬성능 : O(n log n)의 성능을 가집니다.장점 : 안정적인 성능을 보여줌단점 : 구현과 이해가 어렵고 메모리 공간을 많이 차지 퀵정렬성능 : 평균적으로 O(n log n)의 성능을 가지고 최악의 경우 피벗이 한쪽으로 치우쳐 O(n²)를 가지지만 보통 최악의경우가 나올 확률은 극히 낮아 좋은 피벗을 선택해 평균적인 성능으로 말해 O(n log n)의 성능을 가집니다.장점 : 속도가 빠르고 추가 메모리 사용이 거의 없음단점 : 최악의 경우 O(n²)의 성능을 가짐 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.재귀로 쉽게 구현할 수 있는 문제라면 메모이제이션을 사용하는 것이 좋습니다메모이제이션은 재귀 기반 방식이라 코드가 직관적이고 분할하여 해결하기도 쉬워 구현이 간단합니다.반면 타뷸레이션은 반복문 기반으로 계산을 순서대로 처리해 안정적이지만 코드가 길어질 수 있습니다. 타뷸레이션과 메모이제이션을 실행했을때 public static int fibonacci1(int n){ // 타뷸레이션 if(n memo){ // 메모이제이션 if(n == 0 || n == 1){ return n; } if (!memo.containsKey(n)) { memo.put(n, fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo)); } return memo.get(n); } public static void main(String[] args) { HashMap memo = new HashMap(); System.out.println("메모이제이션 : " + fibonacci2(5,memo)); System.out.println("타뷸레이션 : " + fibonacci1(5)); }

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

메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터 : 가장 빠른 기억 장소 이고 컴퓨터의 전원이 꺼지면 데이터가 사라져 휘발성 메모리입니다.캐시 : 레지스터와 메인 메모리 사이에 위치해 데이터 접근 속도를 향상시켜주고 cpu가 메인메모리의 데이터를 가져오기전에 L1 -> L2 -> L3 순으로 확인을하고 캐시에 데이터가 없으면 메인 메모리에서 데이터를 가져옴메인메모리 : 운영체제와 프로세스가 사용하는 공간으로 역시 전원이 꺼지면 데이터가 사라지는 휘발성 메모리입니다하드디스크 : 전원이 종료되도 데이터가 유지되는 비휘발성 메모리에 비용이 저렴하지만 속도가느려 보통 실행할 프로그램을 저장하는데 쓰임 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?base address와 bound address 입니다. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식장점 : 코드, 데이터, 스택, 힙 등의 영역을 논리적으로 구분하여 모듈 단위로 관리할 수 있어 영역간 접근 권한 설정이 쉬움단점 : 외부 단편화 발생 고정 분할 방식장점 : 외부 단편화가 발생하지 않고 메모리 관리가 단순함단점 : 내부 단편화 발생 CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱 입니다물리메모리 용량이 적어서 발생하는거라 메모리 크기를 늘리면 해결되지만 무작정 메모리 크기를 늘려도 현재 프로세스가 동작하는데 문제가없어 스레싱이 발생하지 않으면 크기를 늘려도 문제가 발생하지 않음 HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?꼭 필요합니다.보통 컴퓨터 운영체제를 hdd나sdd에 저장하기 떄문에 필요합니다.ram에도 설치가 가능은 하겠지만 ram은 휘발성 메모리이기 때문에 전원이 종료되면 전부 사라져 비휘발성 메모리인 hdd/ssd에 저장을 하는게 비용적인 면이나 안전성면에서 좋습니다 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일의 데이터가 완전히 지워지지 않기 떄문입니다.파일시스템은 빈 블록 정보를 모은 Free Block List이 존재하는데 파일 삭제시 파일전부를 지우는게아닌 파일의 헤더만 삭제하고 나머지 블록은 Free Block List에 저장해 두기 떄문입니다.

[인프런 워밍업 클럽 3기 CS전공지식] 3주차 발자국

1일차가상 메모리 개요 가상 메모리란?프로세스는 물리 메모리의 크기나 운영체제 영역이 어디에 위치하는지를 몰라도 된다. 프로세스는 메모리 관리자(MMU, Memory Management Unit)를 통해 메모리에 접근하며, 가상 메모리를 통해 자신만의 독립적인 주소 공간을 가진다.가상 메모리의 크기는 이론적으로 무한하지만 실제로는 물리 메모리 크기와 CPU 비트 수에 따라 결정된다. 예를 들어, 32비트 CPU에서는 2의 32승(약 4GB) 크기의 가상 주소 공간을 제공할 수 있다.만약 4GB 크기의 프로세스 5개가 실행되면 총 20GB가 필요한데, 이는 실제 물리 메모리보다 훨씬 크다. 이를 가능하게 하려면 물리 메모리의 일부만을 사용하고 나머지는 하드디스크의 스왑 영역에 저장했다가 필요할 때 가져오는 방식이 필요하다. 이 방식을 가상 메모리라고 한다.가상 메모리를 통해 실행 중인 프로세스의 일부만 물리 메모리에 적재하고, 나머지는 스왑 공간에 두어 메모리를 효율적으로 사용할 수 있다. 주소 변환과 메모리 관리 전략메모리 관리자는 가상 주소를 물리 주소로 변환하기 위해 동적 주소 변환(Dynamic Address Translation) 을 수행한다. 프로세스는 논리 주소를 사용하고, 실제 주소 변환은 MMU가 수행한다. 이때 물리 메모리와 스왑 영역을 포함한 공간을 관리해야 하므로 메모리 관리자는 복잡한 구조를 가진다.물리 메모리에서 0x0 주소는 운영체제가 사용하는 공간이므로 일반 사용자 프로세스는 사용할 수 없으며, 나머지 영역은 고정 분할 방식 또는 가변 분할 방식으로 나눠진다.세그멘테이션: 가변 분할 방식 (외부 단편화 발생)페이징: 고정 분할 방식 (내부 단편화 발생)혼합 방식: 세그멘테이션 + 페이징가상 메모리 시스템에서는 가상 주소가 물리 메모리나 스왑 영역의 어느 위치에 있는지를 일대일 매핑 테이블(페이지 테이블 등) 을 통해 관리한다. 세그멘테이션(Segmentation)세그멘테이션은 프로그램을 논리적 단위(코드, 데이터, 힙, 스택 등)로 분리하여 각 영역을 세그먼트로 나누는 방식이다.세그먼트는 물리 메모리상에서 인접할 필요가 없고, 독립적으로 배치될 수 있다.논리 주소는 (세그먼트 번호, 오프셋) 형태로 구성된다.물리 주소 변환은 세그먼트 테이블의 base address와 bound address를 사용한다.실제 물리주소로 변환은 중간에서 메모리 관리자(MMU)가 해줌변환 예시:CPU가 세그먼트 1번의 주소 0x632에 접근 요청해당 세그먼트의 base address = 5200, bound address = 1000오프셋 0x632 오프셋 0x632 물리주소 5832로 접근논리주소가 더 클 경우CPU가 세그먼트 3번의 주소 0x750에 접근 요청해당 세그먼트의 bound address = 500논리 주소 0x750은 500보다 크므로 접근 불가메모리 관리자는 메모리 침범(잘못된 접근)으로 판단하고 인터럽트를 발생시켜 프로세스를 종료시킴장점:코드, 데이터, 스택, 힙 등의 영역을 논리적으로 구분하여 모듈 단위로 관리할 수 있음이로 인해 영역 간 공유와 접근 권한 설정이 쉬움가변 분할 가능단점:외부 단편화 발생 (공간 낭비)페이징(Paging) 페이징은 논리 주소와 물리 주소를 동일한 크기의 단위로 나누어 사용하는 방식이라 외부 단편화가 발생하지 않음.논리 주소 공간과 물리 주소 공간은 각각의 역할이 있다.논리 주소 공간: 사용자와 프로세스가 바라보는 주소 공간물리 주소 공간: 실제 메모리 하드웨어에서 사용되는 주소 공간논리 주소 공간은 페이지(Page) 단위로 나뉘고 물리 주소 공간은 프레임(Frame) 단위로 나뉨 주소 변환 과정:메모리 관리자는 테이블을 가지고 있는데 이를 페이지 테이블(Page Table)이라 부른다. CPU에서 논리 주소를 전달하면, 메모리 관리자는 이 논리 주소가 몇 번 페이지에 해당하는지와 오프셋(offset)을 계산한다.메모리 관리자 내부에는 PTBR(Page Table Base Register) 이 있어, 이를 통해 해당 프로세스의 페이지 테이블이 물리 메모리의 어디에 위치하는지를 알아낸다.페이지 번호는 페이지 테이블의 인덱스가 되고, 해당 인덱스의 값은 실제 물리 메모리 내의 프레임 번호가 된다.오프셋은 프레임 시작 주소에 더해져 최종 물리 주소가 계산된다.만약 페이지 테이블 항목이 invalid(유효하지 않음)로 표시되어 있다면 해당 페이지는 스왑 영역(하드디스크)에 있으며, 필요한 경우 물리 메모리로 로드된다.세그멘테이션과 마찬가지로 PTBR은 컨텍스트 스위칭 시마다 해당 프로세스의 값으로 업데이트된다.논리 주소는 (페이지 번호, 오프셋)으로 나뉨페이지 번호 → 페이지 테이블에서 대응되는 프레임 번호 찾음물리 주소 = 프레임 시작 주소 + 오프셋 32bit cpu가 주소변환하는 과정 :32비트 CPU 기준 주소 공간은 4GB페이지 크기를 16MB(2^24)로 설정하면 32비트 중 상위 8비트가 페이지 번호, 하위 24비트가 오프셋이 됨총 페이지 수는 2^8 = 256개로, 각 페이지가 16MB물리 메모리는 프레임이 128개라고 가정할 경우 약 2GB 크기부족한 메모리는 스왑 처리를 통해 해결 가능메모리 관리자 내 페이지 테이블은 1차원 배열 형태이며, 페이지 번호는 배열의 인덱스로 사용되어 해당 인덱스에서 프레임 번호를 참조CPU가 논리 주소 0x1000에 접근할 때:페이지 번호 = 0x1000 ÷ 16MB = 0 (페이지 크기 기준 몫)오프셋 = 0x1000 (페이지 크기 기준 나머지)페이지 테이블에서 0번 인덱스의 값이 프레임 3이라면, 물리 주소 = 프레임 3의 시작 주소 + 0x1000CPU가 논리 주소 0x1000에 접근할 때: - 0x1000 = 4096 (10진수) - 페이지 크기: 16MB = 16,777,216 bytes - 페이지 번호 = 4096 ÷ 16,777,216 = 0 (페이지 크기 기준 몫) - 오프셋 = 4096 % 16,777,216 = 4096 (또는 0x1000) - 페이지 테이블에서 0번 인덱스의 값이 프레임 3이라면, - 프레임 3의 시작 주소 = 3 × 16MB = 50,331,648 (또는 0x3000000) - 물리 주소 = 프레임 시작 주소 + 오프셋 = 0x3000000 + 0x1000 = 0x3001000 최종 물리 주소 = 0x3001000 장점:외부 단편화 없음관리가 단순함단점:내부 단편화 발생 가능성페이지 테이블의 크기가 커질 수 있으며 이를 해결하기 위해 다단계 페이지 테이블(Multi-level Paging)과 페이지 테이블 압축 기법이 존재함 세그멘테이션 vs 페이징메모리 분할 방식: 세그멘테이션은 가변 크기의 세그먼트를 사용하고, 페이징은 고정 크기의 페이지로 나눈다.주소 구성 방식: 세그멘테이션은 (세그먼트 번호, 오프셋), 페이징은 (페이지 번호, 오프셋)으로 주소를 구성한다.단편화: 세그멘테이션은 외부 단편화가 발생하고, 페이징은 내부 단편화가 발생할 수 있다.메모리 보호 및 공유: 세그멘테이션은 영역별 권한 설정과 공유가 쉬우며, 페이징은 논리 영역 구분이 어려워 공유/권한 제어가 어렵다.메모리 관리 비용: 페이징은 모든 프로세스가 개별 페이지 테이블을 가지므로 테이블이 많아질수록 관리 비용이 증가하고, 프로세스가 실제 사용할 수 있는 메모리 공간이 줄어들 수 있다.이처럼 세그멘테이션은 논리적 구조에 맞는 유연한 관리가 가능하지만 외부 단편화가 단점페이징은 메모리 관리가 간편하지만 내부 단편화와 테이블 크기 문제가 단점 페이지드 세그멘테이션 (Paged Segmentation)페이지드 세그멘테이션은 세그멘테이션과 페이징을 결합한 메모리 관리 기법으로, 두 방식의 장점을 결합하여 메모리를 효율적으로 관리하면서도 공유 및 접근 보호 기능을 강화할 수 있다. 세그멘테이션과 페이징의 역할세그멘테이션:프로그램을 코드, 데이터, 힙, 스택 등 의미 있는 단위(세그먼트)로 나누어 관리프로세스 간 공유 및 메모리 접근 보호가 용이페이징:메모리를 고정된 크기의 페이지 단위로 나누어 관리외부 단편화를 방지하여 메모리를 효율적으로 사용페이지드 세그멘테이션에서는 세그먼트 내부에서 다시 페이징을 적용하여, 세그먼트의 크기가 가변적이지만, 내부 단위는 고정된 크기(페이지)로 관리된다.세그먼트 내부를 다시 페이지 단위로 나누어 관리함세그먼트 테이블에는 권한 비트, 페이지 테이블 정보 포함 주소 변환 방식:세그먼트 테이블은 base address와 bound address로 구성되며, 여기서 base address는 해당 세그먼트의 페이지 테이블이 시작하는 위치(프레임 번호 또는 인덱스)를 의미하고, bound address는 해당 세그먼트에 할당된 페이지 수를 나타낸다권한 비트를 통해 해당 세그먼트의 접근 권한을 검사가상 주소가 주어지면 해당 세그먼트를 찾고, 권한을 확인한 뒤 페이지 번호와 페이지 개수를 확인함페이지 번호를 이용해 페이지 테이블에 접근하고, 해당 프레임 번호를 찾은 후 프레임 시작 주소에 오프셋을 더해 물리 주소를 계산함물리 메모리에 프레임이 존재하지 않으면 스왑 영역에서 메모리로 데이터를 가져옴요약1. 가상 주소에서 세그먼트 번호를 추출2. 세그먼트의 권한을 검사3. 해당 세그먼트의 페이지 테이블에서 프레임 번호 추출4. 프레임 시작 주소 + 오프셋 → 물리 주소 계산 페이지드 세그멘테이션의 장점과 단점장점논리적 관리 + 메모리 효율성: 세그멘테이션을 사용하여 코드, 데이터, 힙, 스택을 논리적으로 구분하면서도, 내부적으로 페이징을 적용하여 메모리 단편화를 줄일 수 있음공유 및 보호 기능 강화: 세그먼트 단위로 다른 프로세스와 특정 영역을 공유하거나, 접근 권한을 제어할 수 있음단점메모리 접근 시 2번 참조가 필요하여 성능 저하첫 번째 참조: 세그먼트 테이블 조회두 번째 참조: 페이지 테이블 조회총 2번의 메모리 접근이 필요하므로 속도가 느려질 수 있음추가적인 하드웨어 지원 필요성능 최적화를 위해 TLB(Translation Lookaside Buffer) 같은 캐시 기법이 필요 현대 운영체제에서의 활용현대 운영체제는 대부분 "페이징 기반 메모리 관리"를 사용하지만, 일부 시스템에서는 페이지드 세그멘테이션 기법을 혼합하여 사용특히 프로세스 간 코드 공유, 메모리 접근 보호가 중요한 경우 페이지드 세그멘테이션 기법이 활용됨성능 최적화를 위해 다단계 페이지 테이블, TLB 캐싱 기법을 함께 사용 메모리 접근 권한메모리 영역별로 접근 권한을 다르게 설정함:코드 영역: 프로그램의 실행 파일이 저장되는 공간 → 읽기 + 실행 가능, 수정(쓰기) 불가데이터 영역: 전역 변수, 상수 등이 저장되는 공간 → 읽기 가능, 쓰기는 선택적, 실행 불가힙, 스택: 동적 메모리 할당 → 영역 읽기, 쓰기 (실행 불가)운영체제는 가상 주소를 물리 주소로 변환할 때 해당 주소에 대한 접근 권한을 검사하며, 위반 시 예외(Exception) 또는 인터럽트를 발생시켜 프로세스를 종료한다. 삽입 정렬 (Insertion Sort)삽입 정렬은 배열을 정렬된 영역과 정렬되지 않은 영역으로 나누고, 정렬되지 않은 값을 하나씩 정렬된 영역에 삽입하는 방식이다.정렬 과정 예시: [4, 1, 5, 3, 6, 2]정렬된 영역: [4], 삽입할 값: 1 → [1, 4, 5, 3, 6, 2]다음 값 5는 4보다 크므로 그대로3은 5보다 작아, 5와 4를 오른쪽으로 밀고 → [1, 3, 4, 5, 6, 2]반복하여 최종 정렬 결과: [1, 2, 3, 4, 5, 6]시간 복잡도: O(n²)장점: 구현이 간단하고, 데이터가 거의 정렬된 경우 빠름단점: 큰 배열에서는 성능이 떨어짐 자바 코드 예시public static void insertion(int[] arr) { for(int i = 1; i = 0; j--){ // 현재 삽입할 데이터(insertingData)와 정렬된 영역 비교 if(arr[j] > insertingData){ // 삽입할 값보다 크면 한 칸 오른쪽으로 이동 arr[j + 1] = arr[j]; } else { break; // 삽입할 위치를 찾으면 루프 종료 } } arr[j + 1] = insertingData; // 찾은 위치에 삽입할 값 저장 } } public static void main(String[] args) { int[] arr = {1, 6, 4, 3, 2, 5}; System.out.println("정렬 전: " + Arrays.toString(arr)); insertion(arr); System.out.println("정렬 후: " + Arrays.toString(arr)); } 2일차 디맨드 페이징(Demand Paging)(가져오기 정책)프로그램이 메모리에 올라와 프로세스로 실행될 때, 코드(Code), 데이터(Data), 힙(Heap), 스택(Stack) 등의 모듈이 모두 메모리에 올라와 실행되는 것처럼 보이지만, 실제로는 필요할 때만 필요한 부분이 메모리에 올라와 실행된다.지역성(Locality) 이론90:10 법칙에 따르면 프로그램이 실행될 때 전체 코드의 10%에서 90%의 시간이 소비된다고 하고 이는 지역성(Locality) 이론과 관련이 있으며, 지역성에는 두 가지 유형이 있다.공간적 지역성(Spatial Locality): 현재 위치와 가까운 데이터에 접근할 확률이 높음.시간적 지역성(Temporal Locality): 현재 기준으로 가까운 시간에 접근한 데이터가 먼 시간에 접근했던 데이터보다 다시 접근될 확률이 높음.운영체제는 이러한 지역성 이론을 활용하여 자주 사용될 데이터만 메모리에 올리고, 필요하지 않은 데이터는 스왑 영역으로 보내 성능을 향상시킨다. 디맨드 페이징(Demand Paging)은 조만간 필요할 것 같은 데이터를 메모리로 가져오고, 사용되지 않을 것 같은 데이터는 스왑 영역으로 이동시키는 정책이다.디맨드 페이징을 사용하는 예가상 메모리를 사용하는 운영체제현대적인 운영체제의 메모리 관리 기법페이지 교체가 필요한 경우 메모리 계층 구조메모리는 속도에 따라 여러 계층으로 나눌 수 있다.레지스터(Register): CPU 내에 존재하며 한 사이클만에 접근 가능하여 가장 빠름.캐시(Cache): CPU에서 수 사이클~수십 사이클에 접근 가능.메인 메모리(Main Memory, RAM): 수백 사이클이 걸림.보조 저장 장치(Storage, HDD/SSD): 수백만 사이클이 걸려 매우 느림.디맨드 페이징에서는 스왑 영역을 보조 저장 장치에 저장하는데, 성능 향상을 위해 스왑 영역으로 데이터를 이동시키는 횟수를 최소화해야 한다. 가상 메모리와 페이지 테이블가상 메모리 크기는 물리 메모리 크기 + 스왑 영역 크기로 정의된다.스왑인(Swap In): 스왑 영역에서 물리 메모리로 데이터를 가져오는 과정.스왑아웃(Swap Out): 물리 메모리에서 스왑 영역으로 데이터를 보내는 과정.가상 주소가 주어지면 운영체제는 **페이지 테이블(Page Table)**을 참조하여 물리 메모리 내의 프레임(Frame) 위치를 찾거나, 스왑 영역 내의 위치를 확인한다.페이지 테이블 엔트리(Page Table Entry, PTE)는 여러 비트 정보를 포함한다.접근 비트: 페이지가 메모리에 올라온 후 접근이 있었는지 나타냄. (읽기 또는 실행 시 1로 변경)변경 비트: 페이지가 메모리에 올라온 후 데이터 변경이 있었는지 나타냄. (쓰기 작업 시 1로 변경)유효 비트: 해당 페이지가 물리 메모리에 있는지 여부를 나타냄. (1이면 물리 메모리에 있음, 0이면 스왑 영역에 있음)읽기/쓰기/실행 비트: 접근 권한을 검사하는 비트.프로세스가 요청하면 운영체제는 페이지 테이블을 참조하여 물리 메모리에 프레임이 존재하는지 확인한다. 만약 페이지가 물리 메모리에 없다면 Page Fault(페이지 폴트) 예외가 발생한다.Page Fault 발생 시 처리 과정운영체제는 페이지 테이블을 참조하여 해당 페이지가 스왑 영역에 있는지 확인.스왑 영역에서 데이터를 메모리로 가져옴 (스왑인).해당 프로세스는 대기 상태가 됨.데이터가 메모리에 올라간 후 프로세스가 다시 실행 상태가 됨. 물리 메모리에서 데이터 참조 과정예제 1: 페이지가 물리 메모리에 있는 경우프로세스가 페이지 0을 요청.페이지 테이블에서 페이지 0의 유효 비트(Valid Bit) = 0, 프레임 넘버 = 1 일떄페이지가 물리 메모리 1번 프레임에 존재하므로 해당 프레임에서 데이터를 참조.예제 2: 페이지가 스왑 영역에 있는 경우프로세스가 페이지 2를 요청.페이지 테이블에서 페이지 2의 유효 비트 = 1, 프레임 넘버 = 2 일때페이지가 스왑 영역 2번에 있음을 의미.물리 메모리에 적절한 공간이 필요하므로 빈 공간(예: 3번 프레임)에 데이터를 올림.페이지 테이블을 업데이트하여 유효 비트 = 0, 프레임 넘버 = 3으로 수정 후 프로세스가 해당 데이터를 참조하게 함. 페이지 교체 알고리즘운영체제는 스왑아웃과 스왑인 시 어떤 페이지를 교체할지 판단해야 하며, 이를페이지 교체 알고리즘(Page Replacement Algorithm)이라 한다.대표적인 알고리즘:FIFO(First In First Out): 가장 먼저 올라온 페이지를 제거.LRU(Least Recently Used): 가장 오랫동안 사용되지 않은 페이지를 제거.LFU(Least Frequently Used): 가장 적게 사용된 페이지를 제거. 병합 정렬(Merge Sort)병합 정렬은 재귀적으로 정렬하는 알고리즘이다.데이터를 반으로 나누어 분할.각각을 정렬한 후 병합하며 정렬.두 개의 데이터가 하나로 합쳐질 때 비교 연산이 두 번 발생.네 개의 데이터가 두 개로 병합될 때 비교 연산이 네 번 발생.단계마다 영역의 수가 반으로 줄어들기 때문에 **O(log n)**의 성능을 가짐.병합할 때 n개의 데이터를 비교하므로 전체 시간 복잡도는 O(n log n).장점O(n log n)의 성능으로 퀵 정렬보다 안정적인 성능을 제공.단점이해와 구현이 어렵고 추가적인 메모리 공간이 필요함. 자바 코드 예시 public static void MergeSort(int[] arr, int leftIndex, int rightIndex) { if(leftIndex midIndex){ // 왼쪽 영역이 먼저 끝났을 경우, 오른쪽 나머지 요소 복사 for(int i = rightAreaIndex; i 3일차 페이지 교체 정책프로세스는 데이터를 접근하기 위해 메모리를 참조하는데, 해당 데이터가 메모리에 없으면 페이지 폴트(Page Fault)가 발생한다. 이 경우, 운영체제는 해당 페이지를 스왑 영역에서 물리 메모리로 불러와야 한다. 하지만 메모리가 가득 차서 공간이 없다면, 기존에 메모리에 있는 페이지 중 하나를 선택하여 스왑 영역으로 옮겨야 하는데 이때 어떤 페이지를 교체할지 결정하는 것이 페이지 교체 정책(Page Replacement Policy)이다. 페이지 교체 정책의 종류랜덤(Random) 교체 알고리즘무작위로 페이지를 선택하여 교체하는 방법.지역성을 고려하지 않아 성능이 낮아 실제로 거의 사용되지 않음. FIFO(First-In First-Out) 교체 알고리즘가장 먼저 메모리에 들어온 페이지를 제거하는 방식.단순하고 구현이 쉬우나, 자주 사용되는 페이지도 오래되었다는 이유로 교체될 수 있어 성능 저하 발생 가능.빌레이디의 역설(Bélády's Anomaly):프레임 수를 증가시켜도 오히려 페이지 폴트가 증가하는 현상이 발생할 수 있음. 최적(Optimal, OPT) 교체 알고리즘앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식.이론적으로 최적이지만, 미래의 메모리 접근 패턴을 예측해야 하므로 실제 구현이 불가능.다른 알고리즘의 성능을 평가할 때 비교 기준으로 사용됨. LRU(Least Recently Used) 교체 알고리즘가장 오랫동안 사용되지 않은 페이지를 교체하는 방식.시간적 지역성(Temporal Locality)을 고려하여 자주 사용된 페이지를 유지함.하지만 모든 페이지의 사용 시간을 기록해야 하므로 구현이 어려움.하드웨어적으로 접근 비트(Access Bit)를 지원하지 않는 경우 구현이 불가능하여 다른 대체 기법을 사용해야 함. FIFO의 문제점과 해결책FIFO의 가장 큰 문제는 빌레이디의 역설로 인해 프레임 수를 늘려도 페이지 폴트가 증가하는 경우가 발생할 수 있음.하지만 LRU에서는 빌레이디의 역설이 발생하지 않음.LRU에선 접근비트를 이용하는데 하드웨어적으로 접근비트를 지원하지않으면 FIFO를 쓸수밖에없음FIFO 개선 방법: 2차 기회 알고리즘(Second-Chance Algorithm)FIFO 방식과 유사하지만, 자주 사용되는 페이지는 한 번 더 기회를 부여하는 방식.만약 페이지가 참조되었다면 큐의 맨 뒤로 이동시켜 수명을 연장함.LRU보다는 성능이 낮지만, FIFO보다는 성능이 향상됨。 LRU의 한계와 클락(Clock) 알고리즘LRU 구현 문제모든 페이지의 사용 시간을 기록하려면 많은 비트가 필요함.오랜 시간이 지나면 오버플로우 문제가 발생하여 시간을 정확히 기록하기 어려움.따라서 LRU를 근사적으로 구현하는 방식으로 클락(Clock) 알고리즘을 사용함.클락(Clock) 알고리즘접근 비트(Access Bit)를 이용하여 최근 참조 여부를 추적.페이지들을 원형으로 연결하고, 각 페이지를 가리키는 포인터(Clock Hand)를 시계방향으로 회전시키며 검사.이 포인터를 클락 핸드(Clock Hand)라고 부른다.클락 핸드는 페이지 교체가 필요할 때 순차적으로 각 페이지의 접근 비트를 검사한다.접근 비트가 1인 경우, 접근 비트를 0으로 초기화하고 클락 핸드는 다음 페이지로 이동한다.접근 비트가 0인 경우, 해당 페이지를 교체 대상으로 선택한다.FIFO보다 성능이 뛰어나며, LRU에 근접한 성능을 보임.향상된 클락 알고리즘(Enhanced Clock Algorithm)접근 비트 + 변경 비트를 함께 고려.교체 우선순위:접근 비트 = 0, 변경 비트 = 0 (가장 먼저 교체)접근 비트 = 0, 변경 비트 = 1접근 비트 = 1, 변경 비트 = 0접근 비트 = 1, 변경 비트 = 1 (가장 나중에 교체) 스레싱(Thrashing)과 워킹셋(Working Set)스레싱(Thrashing)운영체제가 CPU 사용률을 높이기 위해 멀티프로그래밍 정도를 증가시키면서, 페이지 폴트가 빈번하게 발생하여 CPU가 대부분 스왑 작업에 소비되는 현상.즉, CPU가 실제 작업보다 페이지 교체에 더 많은 시간을 소비하여 성능이 급격히 저하됨.해결 방법: 물리 메모리 크기를 증가시키거나, 적절한 프로세스 수 조절.하지만 무작정 크기를 늘린다고 해결되지는 않는데 현재 메모리가 프로세스들이 작업하는데 충분한 크기라 스레싱이 발생하지않는다면 크기를 늘려도 별 문제가 발생하지않기떄문임워킹셋(Working Set)프로세스가 일정 시간 동안 참조하는 페이지 집합을 워킹셋으로 스레싱을 예방하는 역할을 함페이지 폴트가 발생하면 워킹셋 크기를 증가시켜 추가 페이지를 할당.반대로 페이지 폴트가 거의 발생하지 않으면 워킹셋 크기를 줄여 불필요한 페이지를 회수.지역성(Locality) 원리를 활용하여 성능을 최적화워킹셋은 프로세스가 준비상태에서 실행상태가 되는 컨텍스트스위칭을 할때 사용 퀵 정렬(Quick Sort)병합 정렬(Merge Sort)과 마찬가지로 분할 정복(Divide and Conquer) 알고리즘.정렬 전에 배열에서 하나의 원소를 피벗(Pivot)으로 선택.피벗을 기준으로 작은 값과 큰 값으로 나누어 재귀적으로 정렬 수행.퀵 정렬의 성능평균적인 경우: O(n log n)최악의 경우: O(n²) (피벗이 한쪽으로 치우친 경우)퀵정렬은 대부분 좋은 피벗을 선택하고 최악의 확률이 극히낮아 평균적인 성능을말함적은 비교 연산과 메모리 사용량 덕분에 병합 정렬보다 효율적퀵 정렬이 병합 정렬보다 선호되는 이유병합 정렬은 추가적인 메모리 공간이 필요하지만, 퀵 정렬은 제자리 정렬(in-place sorting)이 가능.대부분의 경우, 퀵 정렬이 더 적은 비교 연산을 수행하여 속도가 빠름 자바 코드 예시 public static void quickSort(int[] arr, int left, int right) { if(left = arr[leftStartIndex]){ // 피벗보다 작거나 같은 값은 이미 왼쪽에 있어야 하니 다음 인덱스로 이동 leftStartIndex++; } while(rightStartIndex >= (left + 1) && pivot 4일차입출력 장치 주변장치 개요주변장치는 그래픽카드, 하드디스크, SSD, 키보드, 마우스 등 다양한 장치들이 있으며, 이들은 메인보드의 버스를 통해 연결된다. 버스는 주소 버스(Address Bus), 데이터 버스(Data Bus), 제어 버스(Control Bus)로 구성되어 있으며, I/O 디바이스는 이를 통해 데이터를 송수신한다.각 주변장치에는 외부 인터페이스와 함께 상태나 데이터를 보관하는 레지스터들이 존재하며, 이 레지스터에 저장된 데이터는 CPU가 사용하기 위해 메모리로 이동되기도 한다.주변장치는 캐릭터 디바이스와 블록 디바이스로 구분된다. 이는 데이터를 전송하는 단위에 따라 나뉘며, 캐릭터 단위인지 블록 단위인지를 기준으로 한다.캐릭터 디바이스: 마우스, 키보드, 사운드 카드, 직렬/병렬 포트 등. 상대적으로 적은 양의 데이터를 전송한다.블록 디바이스: 하드디스크, SSD, 그래픽카드 등. 대용량 데이터를 전송한다. 입출력 구조와 제어 방식예전 시스템에서는 모든 주변장치를 하나의 버스로 연결했으며, CPU가 직접 I/O 장치에 접근하여 데이터를 처리했다. 이 방식은 입출력 중 CPU가 다른 작업을 하지 못해 CPU 사용률이 낮아지는 문제가 있었다.이를 개선하기 위해 **입출력 제어기(I/O Controller)**와 입출력 버스가 도입되었다. CPU는 I/O 명령을 만나면 입출력 제어기에 명령을 위임하고 다른 작업을 수행할 수 있게 되었다.입출력 제어기는 두 채널로 구분된다:시스템 버스: CPU와 메모리가 사용하는 고속 버스입출력 버스: 주변장치가 사용하는 저속 또는 고속 버스입출력 버스는 다시 고속 I/O 버스와 저속 I/O 버스로 나뉘며, 장치 속도에 따라 병목 현상을 방지한다. 예를 들어, 그래픽카드는 매우 빠른 대역폭이 필요하기 때문에 시스템 버스에 직접 연결되기도 한다.하지만 입출력 제어기만으로는 데이터를 메모리에 쓰기 위해 여전히 CPU의 개입이 필요했다. 이를 해결하기 위해 DMA(Direct Memory Access) 제어기가 도입되었다. DMA는 입출력 장치가 CPU를 거치지 않고 직접 메모리에 접근할 수 있게 하여 성능을 향상시킨다.DMA와 CPU가 메모리 충돌 없이 사용할 수 있도록, 메모리를 나눠 관리하는 방식을 Memory Mapped I/O라고 한다. 마우스와 키보드 동작 방식마우스예전에는 볼 마우스를 사용했으며, 내부의 볼이 회전하며 움직임을 감지했다.현재는 광학 마우스를 주로 사용한다. 하단에 있는 카메라가 초당 수천 회 표면을 촬영하고, 내장 DSP가 이미지 변화를 분석하여 X, Y축 좌표를 계산한다.마우스의 동작이나 클릭 등의 이벤트가 발생하면, 디바이스 컨트롤러가 CPU에 인터럽트를 보내고, 마우스 드라이버가 데이터를 읽어 운영체제에 이벤트로 전달한다.운영체제는 이 이벤트를 포그라운드 애플리케이션에 전달하여 동작을 수행하게 한다.키보드사용자가 키를 누르면 키보드 컨트롤러가 어떤 키인지 판단하여 CPU에 인터럽트를 발생시킨다.이후 키보드 드라이버가 운영체제에 이벤트를 전달하고, OS는 해당 이벤트를 포그라운드 애플리케이션에 전달한다.애플리케이션은 해당 키에 맞는 동작을 수행한다. 하드디스크와 플래시 메모리하드디스크 구조하드디스크에는 중심축인 스핀들이 있으며, 여기에 여러 개의 원판(플래터)이 장착되어 있다. 플래터는 자기화된 원판으로, 디스크 암에 고정된 읽기/쓰기 헤드가 데이터를 읽거나 쓴다.플래터는 여러 개의 트랙(원형 경로)으로 구성되며, 각 트랙은 다시 섹터로 나뉜다. 섹터는 하드디스크의 가장 작은 저장 단위이다. 플래터가 여러 개인 경우 같은 위치의 트랙들을 묶은 것을 실린더(Cylinder)라고 한다.플래터 표면에는 자성이 있으며, N극으로 자화된 부분은 0, S극으로 자화된 부분은 1로 인식된다. 이러한 방식으로 디지털 데이터를 저장한다.일반적으로 하드디스크는 2개 이상의 플래터를 사용하고, 각 플래터의 양면에 헤드가 위치해 데이터를 읽는다.헤드는 디스크 암에 고정되어 있으며, 하나의 디스크 암이 여러 헤드를 동시에 움직이기 때문에 모든 헤드는 함께 이동하게 된다.데이터를 읽는 과정 예시:명령: 실린더 C, 트랙 B, 섹터 D를 읽어라디스크 암이 실린더 C로 이동 (이 과정: 시크(Seek))이때 걸리는 시간: 시크 타임(Seek Time)이후 스핀들을 회전시켜 플래터를 돌리고, 섹터 D가 헤드에 닿을떄 까지 기다림섹터 D를 읽은 뒤 작업 완료하드디스크는 이처럼 기계적인 이동이 많기 때문에 느리고, 충격에 약하며, 소음이 발생하는 단점이 있다. 플래시 메모리(SSD)플래시 메모리는 전기적으로 데이터를 처리하기 때문에 빠르고 조용하며, 충격에도 강하다. 또한 자성을 띠지 않으므로 외부 자기장에 영향을 받지 않는다.하지만 플래시 메모리는 특정 영역에 데이터를 다시 쓰기 위해서는 먼저 해당 영역을 지워야 하며, 이 지우기 작업에는 횟수 제한이 존재한다. 같은 지점을 반복해서 지우고 쓰는 작업이 누적되면 해당 셀의 수명이 다해 결국 플래시 메모리가 손상되어 사용할 수 없게 되는 문제가 발생할 수 있다. 또한 자성을 띠지 않으므로 외부 자기장에 영향을 받지 않는다. 동적 프로그래밍과 메모이제이션동적 프로그래밍(Dynamic Programming)은 큰 문제를 작은 문제로 나누어 해결하는 방식으로, 특히 중복 계산을 피하는 데 효과적이다.예를 들어, 피보나치 수열을 재귀로 구현하면 같은 계산을 반복하게 되어 O(n²)의 성능을 가지게 되지만, 메모이제이션(Memoization)을 사용하면 계산 결과를 저장해 중복 연산을 제거하여 O(n)의 성능을 달성할 수 있다.단점으로는, 속도 향상을 위해 메모리를 추가로 사용하게 된다는 점이 있다. 자바코드 예제 public static int fibonacci1(int n) { if(n == 0 || n == 1){ return n; } return fibonacci1(n - 2) + fibonacci1(n - 1); } public static int fibonacci2(int n, HashMap memo){ if(n == 0 || n == 1){ return n; } if (!memo.containsKey(n)) { memo.put(n, fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo)); } return memo.get(n); } public static void main(String[] args) { System.out.println("fibonacci1 : " + fibonacci1(5)); HashMap memo = new HashMap(); System.out.println("fibonacci2 : " + fibonacci2(5,memo)); } 5일차파일과 파일시스템 파일시스템의 역할과 구조메모리처럼 직접 접근이 가능한 장치와는 달리, 하드디스크나 SSD 같은 저장장치는 사용자가 직접 데이터를 저장하거나 수정하게 되면 중요한 정보가 손상될 수 있다. 그래서 사용자는 운영체제를 통해 파일 저장을 요청하고, 운영체제가 이를 안전하게 처리한다.운영체제는 이러한 파일 관리를 위해 파일 관리자를 두며, 이를 파일시스템(File System)이라 부릅니다. 이는 메모리 관리에서 페이지 테이블을 통해 가상 주소를 물리 주소로 변환하듯, 파일 테이블을 통해 파일의 정보와 위치 등을 관리한다. 파일시스템의 주요 기능파일과 디렉토리 생성: 새 파일 및 폴더를 만들 수 있도록 지원함파일과 디렉토리 수정 및 삭제: 기존 데이터를 변경하거나 제거할 수 있음파일 권한 관리: 사용자별 접근 권한을 설정하고 제어함무결성 보장: 파일 손상 없이 안전하게 유지되도록 함백업 및 복구: 데이터 유실에 대비해 저장 및 복원 기능 제공암호화: 파일 내용을 보호하기 위한 암호화 기능 제공 파일시스템과 저장장치의 관계파일시스템은 하드디스크나 플래시 메모리(SSD) 같은 저장장치에 설치된다. 이러한 장치는 데이터를 블록 단위로 전송하지만, 사용자는 바이트 단위로 데이터를 읽고 쓰기 때문에 파일시스템은 중간에서 블록을 바이트 단위로 관리해주는 역할을 한다.주변장치의 관점에서 보면, 하드디스크와 플래시 메모리는 블록 디바이스에 해당하며, 키보드나 마우스처럼 캐릭터 단위로 처리되지 않는다. 파일과 파일 디스크립터파일은 헤더(Header)와 데이터(Data)로 구성되어 있으며, 헤더에는 파일의 속성 정보가 담겨 있다. 운영체제는 파일 정보를 관리하기 위해 파일 제어 블록(File Control Block) 을 유지하며, 사용자가 파일을 열면 파일 디스크립터(File Descriptor) 라는 참조 번호를 통해 파일 제어 블록에 간접적으로 접근할 수 있도록 한다.파일 디스크립터는 파일이 열릴 때 메모리로 로드되며, 사용자는 직접 접근할 수 없다.사용자는 운영체제를 통해 전달받은 디스크립터를 통해 파일에 접근하게 된다. 파일 구조의 종류순차 파일 구조 (Sequential File Structure)데이터가 파일 내에 순서대로 저장됨.C 언어에서는 open() 함수로 파일을 열고, 파일 디스크립터는 파일의 맨 앞을 가리킨다.읽기/쓰기 작업은 처음부터 진행되며, 특정 위치로 이동하려면 lseek() 함수를 사용해야 함.장점: 구조가 단순하고 공간 낭비가 적음.단점: 중간 삽입/삭제가 느림.직접 파일 구조 (Direct File Structure)데이터를 저장할 위치를 해시 함수를 이용해 결정.해시테이블, JSON 등의 구조와 유사.장점: 매우 빠른 접근 속도.단점: 해시 함수 선정이 중요하며, 충돌 및 공간 낭비 가능성 존재.인덱스 파일 구조 (Indexed File Structure)순차 접근과 직접 접근의 장점을 결합.인덱스를 통해 빠른 접근이 가능하고, 순차 처리도 지원함. 디렉토리 구조디렉토리는 파일을 포함할 수 있으며, 하위 디렉토리를 포함할 수도 있다. 디렉토리 구조는 계층형 트리 구조로 발전해 왔으며, 최상위 디렉토리를 루트 디렉토리(Root Directory)라고 부른다.리눅스/유닉스: 루트 디렉토리는 /로 표기되며, 디렉토리 구분자도 / 사용.윈도우: 루트 디렉토리는 보통 파티션 이름(C:\)로 표기되며, 디렉토리 구분자로 \ (역슬래시) 사용.디렉토리는 일반 파일과 동일한 구조를 가지지만, 일반 파일은 데이터를 저장하고 디렉토리는 파일 목록 정보를 저장한다. 디렉토리의 발전초기: 루트 디렉토리만 존재 (단일 디렉토리 구조)이후: 파일이 많아지면서 불편함이 생겨 다단계 디렉토리 구조로 발전 → 모든 디렉토리에서 하위 디렉토리 생성 가능 (트리 구조)순환 참조 문제: 바로가기(Shortcut) 기능으로 인해 트리 구조 내에 사이클이 생길 수 있음 파일과 디스크 할당 방식파일시스템은 파일 정보를 파일 테이블로 관리하고, 이 테이블에는 파일이 저장된 블록의 시작 위치가 기록된다.파일은 여러 블록으로 나뉘어 저장되며, 블록 연결 방식에 따라 아래와 같이 분류된다:연속 할당 (Contiguous Allocation)파일을 연속된 블록에 저장.시작 블록만 알면 전체 파일에 접근 가능 → 매우 빠름.단점: 외부 단편화 발생, 파일 크기 예측 어려움, 실제로는 사용하지않는 방식불연속 할당 (Non-contiguous Allocation)디스크의 빈 블록에 데이터를 분산 저장.연결할당과 인덱스할당으로 나눠짐연결 할당 (Linked Allocation)각 데이터 블록이 다음 블록의 위치를 가리킴 (연결 리스트 방식)파일 테이블에는 시작 블록만 저장됨인덱스 할당 (Indexed Allocation)파일마다 인덱스 블록을 두고, 그 안에 데이터 블록의 포인터를 저장인덱스 블록이 꽉 차면 다른 인덱스 블록을 추가 연결 (확장 가능)파일의 크기가 작다면 데이터를 바로 참조하는 블록 포인터를 이용크다면 간접 포인터를 이용해 많은데이터를 참조유닉스/리눅스에서는 이 구조를 i-node라고 함 디스크 블록과 공간 관리디스크는 일정한 크기의 블록 단위로 나뉘며, 보통 1KB ~ 8KB 사이블록이 작으면 공간 낭비는 적지만, 관리할 블록 수가 많아짐블록이 크면 블록 수는 줄지만 내부 단편화로 인해 일부 공간 낭비 발생 Free Block List매번 빈 블록을 전체 검색하면 비효율적이므로, 파일시스템은 빈 블록 정보를 모은 Free Block List를 유지한다파일 삭제 시, 파일 전체를 지우는 것이 아니라 헤더만 삭제하고 블록은 Free Block List에 추가해 재사용함 동적 프로그래밍 - 타뷸레이션(Tabulation)타뷸레이션은 상향식 계산 방식이다. 문제를 해결하는 데 필요한 값을 미리 계산하여 테이블에 저장하고, 이후 필요한 값은 테이블에서 꺼내 사용하는 방식이다.장점: 재귀 호출을 사용하지 않기 때문에 스택 오버플로우 위험 없음단점: 필요하지 않은 값까지 계산할 수 있음 (메모리 낭비 가능성)메모이제이션 vs 타뷸레이션메모이제이션(Memoization): 하향식(Top-down), 재귀 기반 → 코드가 직관적이고 문제 분할이 쉬움타뷸레이션(Tabulation): 상향식(Bottom-up), 반복문 기반 → 메모리 사용이 예측 가능하고 빠름문제가 분할 정복적으로 풀기 쉬우면 메모이제이션, 재귀가 복잡하거나 메모리 최적화가 중요하면 타뷸레이션이 더 적합하다. 자바 코드 예시 public static int fibonacci3(int n){ if(n 3주차 회고이번주 역시 매일 스케쥴에 맞춰 강의를 듣고 발자국 정리 하는건 빼먹지않았습니다.3주차 강의내용은 생각보다 정말 어려워 아직 이해했다 하기는 힘든상태라 발자국에 정리를 해두고 다시 3주차 처음부터 공부를 다시 해볼 계획입니다. 이번 인프런 워밍업 클럽 후기인프런 강의를 사두고 강의를 완강하는건 쉽지않아 완강할 수있는 계기가 필요해 이번 인프런 워밍업 클럽에 신청해 그중 cs지식이 필요해 감자님의 강의를 수강했습니다.국비과정을 수료해 코드만 칠줄알았었는데 cs 공부를 처음해보니 이해하기 정말 힘들었어서 이번 워밍업 클럽이 아니였으면 사실 손도 안댔을거같습니다.강의는 cs지식이 0에 가까운 저에게 강의제목처럼 그림으로 이해하기 쉽게 알려주셔서 cs지식이 필요한데 뭘 공부할지 모르시는 분들께 정말 추천드리고 강의를 듣다가 질문을 작성하면 답변을 새벽에 올려도 금방금방 답변해주셔서 정말 좋았습니다. 만약 4기 워밍업 클럽도 진행한다면 강력추천합니다.강의 영상도 좋고 질문답변해주시는 것도 빠르고 좋습니다.특히 난 강의를 구매하고 완강을 하기 힘드신분은 강력 추천드립니다.매일 어느파트의 강의를 들어야하는 시간표를 건내줘서 본인이 해당 시간표에 맞춰 행동하겠다 마음만 먹으면 충분히 하실수 있습니다.

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

재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?기저 조건이 없으면 무한으로 반복해 콜스택이 가득차 스택 오버플로우가 발생하여 프로그램이 비정상적으로 종료됩니다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.자바 코드 예시 public static int sum(int n) { if (n == 1) return 1; // 탈출 조건 if(n % 2 == 1){ return n + sum(n - 1); } return sum(n - 1); } public static void main(String[] args) { System.out.println("홀수합 = " + sum(10)); // 120 출력 } 자바스크립트 예제function sumOdd(n){ if(n == 1) return 1; if(n % 2 == 1){ return n + sumOdd(n-1); } return sumOdd(n-1); } console.log(sumOdd(10)) // 25다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.const fs = require("fs"); // 파일을 이용하는 모듈 const path = require("path"); // 폴더와 파일의 경로를 지정해주는 모듈 function traverseDirectory1(directory){ const stack = [directory]; // 순회해야 할 디렉토리를 저장할 스택 while (stack.length > 0) { // 스택이 빌 때까지 반복 const currentDir = stack.pop(); // 현재 디렉토리 const files = fs.readdirSync(currentDir); // 인자로 주어진 경로의 디렉토리에 있는 파일or디렉토리들 for (const file of files) { // 현재 디렉토리의 모든 파일or디렉토리 순회 const filePath = path.join(currentDir, file); //directory와 file을 하나의 경로로 합쳐줌 const fileStatus= fs.statSync(filePath); // 파일정보 얻기 if (fileStatus.isDirectory()) { // 해당 파일이 디렉토리라면 console.log('디렉토리:', filePath); stack.push(filePath); } else { // 해당 파일이 파일이라면 console.log('파일:', filePath); } } } } traverseDirectory1("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력 자바 코드 예시public static void directory(String directory) { if(directory == null){ return; } File dir = new File(directory); // 디렉토리값을 기반으로 파일 객체 생성 File[] files = dir.listFiles(); // 파일 및 하위 디렉토리 정보 저장 배열 if (files != null) { for (File file : files) { if (file.isDirectory()) { System.out.println("디렉토리 : " + file.getAbsolutePath()); // 경로를 출력 directory(file.getAbsolutePath()); // 재귀로 하위 디렉토리 탐색 } else { System.out.println("파일 : " + file.getAbsolutePath()); } } }else{ return; } } public static void main(String[] args) { directory("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력 }

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

운영체제FIFO 스케줄링의 장단점이 뭔가요? 장점 : 선입선출 방식의 알고리즘이라 프로세스가 들어온 순서대로 처리할수 있어 단순하고 직관적임단점 : 먼저 온 프로세스가 실행 시간이 길면 실행 시간이 짧은 프로세스들은 그 뒤에서 작업이 끝날떄 까지 기다려야하는 호위효과가 발생하게됨 SJF를 사용하기 여러운 이유가 뭔가요?burst Time의 예측이 어렵고 burst Time이 짧은 작업이 계속 들어올경우 상대적으로 작업시간이 긴 프로세스는 계속 대기해야하는 기아현상이 발생합니다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?CPU의 프로세스 간에 전환이 너무 자주 일어면 컨텍스트 스위칭이 자주 발생해 오버헤드가 커져 효율성이 떨어집니다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요? CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하면 I/O Bound Process이고CPU를 사용하는 프로세스가 타임 슬라이스를 오버해서 스케줄러에 의해 강제로 CPU를 뺏기는 상황이면 CPU Bound Process 입니다. 공유자원이란무엇인가요?프로세스 간 통신에서 공동으로 사용하는 변수나 파일이고 여러 프로세스가 동시에 접근하면 순서에 따라 결과가 달라질 수 있습니다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호 배제, 비선점, 점유와 대기, 원형 대기가 모두 충족이 되어야 하고 이 중 하나라도 충족하지 못하면 교착상태에 빠지지 않습니다.

[인프런 워밍업 클럽 3기 CS전공지식] 2주차 발자국

1일차프로세스 동기화와 통신,재귀 프로세스 간 통신프로세스는 독립적으로 실행될 수도 있지만 다른 프로세스와 데이터를 주고받으며 통신하기도 합니다.통신 방식은 한 컴퓨터 내의 프로세스 간 통신과 네트워크를 통해 다른 컴퓨터의 프로세스와 통신하는 방법으로 나눌 수 있습니다. 프로세스 간 통신 방법파일(File) 이용통신하려는 프로세스들이 공통된 파일을 이용하여 데이터를 읽고 씁니다.파이프(Pipe) 이용운영체제가 생성한 파이프를 통해 데이터를 읽고 쓰는 방식입니다. 한 프로세스가 파이프에 데이터를 쓰면, 다른 프로세스가 이를 읽습니다. 쓰레드를 이용한 통신한 프로세스 내에서 쓰레드 간 통신 방법입니다.쓰레드는 코드, 데이터, 힙 영역을 공유하고, 각 쓰레드는 독립적인 스택을 가집니다. 따라서 공유된 데이터나 힙 영역을 통해 쓰레드 간 데이터를 주고받을 수 있습니다.네트워크를 이용한 통신소켓(Socket): 운영체제가 제공하는 소켓을 사용하여 네트워크 상의 다른 컴퓨터와 통신합니다.RPC(Remote Procedure Call, 원격 프로시저 호출): 네트워크를 통해 다른 컴퓨터의 프로세스에 있는 함수를 호출하는 방식입니다. 공유 자원과 임계 구역공유 자원프로세스 간 통신에서 공동으로 사용하는 변수나 파일 등을 공유 자원(Shared Resource) 이라고 합니다.공유 자원은 여러 프로세스가 동시에 접근할 경우, 접근 순서에 따라 결과가 달라질 수 있습니다.경쟁 조건 (Race Condition)여러 프로세스가 동시에 공유 자원에 접근하려고 경쟁하는 상황을 경쟁 조건이라 합니다.컨텍스트 스위칭(Context Switching)으로 인해 어떤 프로세스가 먼저 실행될지 예측하기 어렵습니다.따라서 여러 프로세스가 동시에 사용하면 안되는 영역을 정의했는데 이를 **임계구역이라 함**임계 구역 (Critical Section)여러 프로세스가 동시에 접근하면 안 되는 코드 영역을 임계 구역이라 합니다. 임계 구역 문제 해결 - 상호 배제 매커니즘(Mutual Exclusion)임계 구역 문제를 해결하려면 상호 배제 매커니즘이 필요합니다.주요 상호 배제 메커니즘뮤텍스(Mutex):상호 배제를 위한 동기화 도구로, 한 번에 하나의 프로세스 또는 스레드만 접근할 수 있도록 합니다.세마포어(Semaphore):공유 자원에 여러 프로세스가 동시에 접근하는 것을 방지하기 위한 동기화 도구입니다.모니터(Monitor):공유 자원과 해당 자원에 대한 연산을 묶어서 관리하는 동기화 도구입니다.상호 배제를 만족하기 위한 요구사항:상호 배제: 어떤 시점에도 하나의 프로세스만 임계 구역에 접근해야 합니다.진행 조건: 여러 프로세스가 임계 구역에 들어가기를 원하면, 하나의 프로세스만 선택되어야 합니다.유한 대기: 임계 구역에 들어간 프로세스는 최대한 빨리 종료해야 하며, 다른 프로세스가 무한정 기다리는 것을 방지해야 합니다. 프로세스 동기화 기법세마포어 (Semaphore)공유 자원에 여러 프로세스가 동시에 접근하는 것을 방지하기 위한 동기화 도구입니다.wait() 함수와 signal() 함수를 사용하여 자원 접근을 조절합니다.문제점: wait()와 signal()을 잘못 사용하면 **교착 상태(Deadlock)나 **경쟁 상태가 발생할 수 있습니다.**교착 상태 : 여러 프로세스가 서로 필요한 자원을 기다리면서 무한정 대기하는 상태입니다. 세마포어의 wait() 함수를 잘못 사용하면 교착 상태가 발생할 수 있습니다.**경쟁 상태 : 세마포어의 signal() 함수를 잘못 사용하면 여러 프로세스가 동시에 임계 구역에 접근하여 데이터 불일치 등의 문제가 발생할 수 있습니다. 세마포어의 사용 코드 예제(JAVA) public static void main(String[] args) throws InterruptedException { Semaphore semaphore = new Semaphore(1); semaphore.acquire(); // acqurie()는 wait()과 같은 역할을 담당 System.out.println("wait 실행"); semaphore.release(); // release()는 signal()과 같은 역할을 담당 System.out.println("signal 실행"); } 모니터 (Monitor)세마포어의 문제점을 보완한 상호 배제 매커니즘입니다.운영체제가 아닌 프로그래밍 언어 차원에서 제공하며, Java의 synchronized 키워드가 대표적입니다.synchronized 키워드가 붙은 메서드는 한 번에 하나의 쓰레드만 접근할 수 있습니다. 그럼 세마포어의 문제점을 보완한게 모니터니까 모니터를 사용하는게 가장 좋은건가??세마포어와 모니터: 세마포어는 개발자가 직접 'wait'과 'signal'을 조작해야 하기 떄문에 세밀한 관리가 가능하지만 호출 순서 및 위치를 잘못 설정하면 교착상태,경쟁조건이 생길 수 있어 복잡하고 세밀한 동기화를 사용하기 좋음모니터는 공유 자원에 접근하는 코드를 '모니터'라는 방 안에 넣으면 알아서 한 번에 한 명씩만 들어가도록 관리를 해줘 개발자는 안전하게 코드가 작성이 가능해 안전한 동기화에 좋지만 세마포어보다 오버헤드가 클 수 가있음모니터의 사용 코드 예제(JAVA) public static void main(String[] args) { Object lock = new Object(); // 락으로 사용할 객체 synchronized (lock) { // 락이 있을경우 해당 메서드에 진입해 실행 System.out.println("Inside synchronized block."); //실행문 종료 후 별다른 명령어 없이 자동으로 lock 반납 } } 뮤텍스 (Mutex)세마포어와 유사하지만, 뮤텍스는 오직 하나의 프로세스/스레드만 공유 자원에 접근하도록 제한합니다.잠금(lock)과 해제(unlock) 연산을 통해 임계 영역을 보호합니다.주로 하나의 공유 자원에 대한 접근을 순차적으로 처리해야 할 때 사용됩니다.뮤텍스는 잠금을 소유한 스레드만이 잠금을 해제할 수 있다는 특징이 있습니다.뮤텍스의 사용 코드 예제(JAVA) public static void main(String[] args) { ReentrantLock lock = new ReentrantLock(); lock.lock(); // lock 활성화 System.out.println("Lock acquired."); lock.unlock(); // lock 반납 System.out.println("Lock released."); }재귀 (Recursion)재귀란?어떤 것을 정의할 때 자기 자신을 참조하는 방식입니다.함수가 자기 자신을 호출하는 재귀 함수가 대표적인 예입니다.재귀 함수의 종료 조건재귀 함수에는 반드시 탈출 조건이 필요합니다.탈출 조건이 없으면 무한 재귀가 발생하며, **콜 스택(Call Stack)이 가득 차 프로그램이 비정상 종료됩니다.함수를 호출하면 해당 함수는 콜스택 위에 올라가고 함수가 종료되면 콜스택에서 제거됨**콜 스택 (Call Stack)함수 호출 기록을 저장하는 메모리 영역입니다.FILO(First In Last Out) 구조를 가지며, 마지막에 호출된 함수가 가장 먼저 종료됩니다. 재귀, 반복문반복문(for, while)으로 해결 가능한 문제를 재귀 함수로 구현하면 비효율적일 수 있습니다.재귀 함수는 함수를 호출할 때마다 새로운 **스택 프레임을 생성합니다. 이 스택 프레임에는 함수의 매개 변수지역 변수,반환 주소 등의 정보가 저장되어 코드만 실행하면 되는 반복문에 비해 함수 호출 및 스택 관리에 더 많은시간과 메모리를 소비해야함** 스택 프레임??프로그램 실행 중에 함수가 호출될 때 생성되는 메모리 블록으로 함수에 호출된 정보를 저장그러나 팩토리얼 계산등 문제의 구조 자체가 재귀적인 경우 재귀 함수가 유리합니다.// 반복문 int sum = 0; for (int i = 1; i 팩토리얼 예제(JAVA)public class FactorialExample { public static int factorial(int n) { if (n == 1) return 1; // 탈출 조건 return n * factorial(n - 1); } public static void main(String[] args) { System.out.println("5! = " + factorial(5)); // 120 출력 } }2일차프로세스 동기화와 통신,재귀 교착상태 (Deadlock)교착상태란?교착상태(Deadlock)는 여러 프로세스가 서로 다른 프로세스가 보유한 자원을 기다리며 무한히 대기하는 상태를 의미합니다. 이 상태에 빠지면 어떤 프로세스도 작업을 진행하지 못하게 됩니다.공유 자원: 프로세스들이 서로 공유하는 자원(예: 프린터, 메모리 등)이 있을 때 발생할 수 있음.독립 자원: 반대로, 공유하지 않는 자원만 사용한다면 교착상태는 발생하지 않음. 교착상태의 필요조건교착상태가 발생하기 위한 4가지 필요조건이 있으며, 이 중 하나라도 충족되지 않으면 교착상태가 발생하지 않습니다.상호 배제 (Mutual Exclusion)어떤 자원이 한 프로세스에 의해 점유되었다면, 그 자원은 다른 프로세스와 공유되지 않아야 함.비선점 (No Preemption)다른 프로세스가 점유한 자원을 강제로 빼앗을 수 없어야 함.점유와 대기 (Hold and Wait)어떤 프로세스가 자원을 점유한 상태에서 추가 자원을 기다려야 함.즉, 이미 할당된 자원을 보유하면서 다른 자원을 요청하고 대기하는 상태여야 합니다.원형 대기 (Circular Wait)점유와 대기 상태의 프로세스들이 원형으로 연결되어 있어야 함.예를 들어, 프로세스 A는 프로세스 B가 가진 자원을 기다리고, 프로세스 B는 프로세스 C가 가진 자원을 기다리고, 프로세스 C는 프로세스 A가 가진 자원을 기다리는 식입니다. 교착상태 해결 방법교착 상태는 여러 프로세스가 서로 필요한 자원을 기다리며 무한히 대기하는 상황을 의미합니다. 이러한 교착 상태를 해결하기 위한 다양한 방법 중 하나가 바로 **교착 상태 회피입니다.**교착 상태 회피란?시스템이 자원을 할당하기 전에 교착상태 가능성을 검사하고, 교착상태가 발생하지 않도록 자원을 할당.대표 알고리즘: **은행가 알고리즘 (Banker's Algorithm)** 은행가 알고리즘의 특징시스템은 프로세스들의 최대 요구 자원을 미리 알고 있어야 함.자원 할당 전에 시스템의 상태를 안정 상태(Safe State)와 불안정 상태(Unsafe State)로 구분안정 상태(Safe State): 교착상태에 빠지지 않을 수 있는 상태.불안정 상태(Unsafe State): 교착상태에 빠질 가능성이 있는 상태. (불안정 상태가 반드시 교착상태를 의미하진 않음)안정 상태의 예시시스템의 총 자원 14개P1: 최대 9개, 현재 5개 점유 → 추가로 4개 필요P2: 최대 6개, 현재 4개 점유 → 추가로 2개 필요P3: 최대 4개, 현재 3개 점유 → 추가로 1개 필요사용 가능한 자원: 2개자원 할당 순서P1은 4개를 요청하므로 거절.P2는 2개 요청 가능 → 작업 완료 후 6개 반납.P1은 이제 4개 요청 가능 → 작업 완료 후 자원 반납.불안정 상태의 예시시스템의 총 자원 10개P1: 최대 7개, 현재 5개 점유 → 추가로 2개 필요P2: 최대 5개, 현재 3개 점유 → 추가로 2개 필요P3: 최대 4개, 현재 2개 점유 → 추가로 2개 필요사용 가능한 자원: 1개자원 할당 상태P1, P2, P3 모두 추가 자원을 받기 위해 대기.사용 가능한 자원이 1개뿐이라 어느 프로세스도 필요한 자원을 다 받지 못함.세 프로세스가 서로 자원을 기다리며 무한 대기 상태 → 교착상태 발생 교착상태가 발생한지 알아내는 방법가벼운 교착상태 검출:타이머를 설정해 특정 시간 동안 프로세스가 작업을 하지 않으면 교착상태라고 판단.해결 방법 : 체크포인트를 통해 주기적으로 상태를 저장하고, 교착상태 발생 시 마지막 체크포인트로 롤백.간단하지만, 오탐지 가능성이 있고 롤백에 따른 오버헤드가 발생할 수 있습니다무거운 교착상태 검출:**자원 할당 그래프(Resource Allocation Graph, RAG)를 사용.프로세스-자원 관계를 그래프로 표현하고 사이클이 발견되면 교착상태로 간주.정확도가 높지만, 자원 할당 그래프를 관리하고 순환을 탐지하는 데 오버헤드가 발생합니다.오버헤드가 발생하지만, 프로세스를 강제로 종료하지 않고 교착상태를 해결 가능. **자원 할당 그래프자원할당 그래프의 사이클이 존재하는 지 그림으로 확인해당 그림처럼 프로세스와 자원 간의 사이클이 존재한다면 교착상태이고 해당 그림처럼 프로세스와 자원간의 사이클이 없으면 교착상태가 아니다하지만 사이클이 있어도 교착상태에 안걸리는 경우도 존재하는데P2와 P4가 작업을 완료하고 자원을 반납하면R1과 R2의 자원을 반납P1과 P3가 필요한 자원을 얻을 수 있음.원형 대기 상태가 깨지므로 교착상태가 해소됨. 재귀적으로 생각하기 패턴 1: 단순 반복의 재귀적 구현 (비효율적)반복문으로 간단하게 해결할 수 있는 문제를 재귀 함수로 구현하는 것은 일반적으로 비효율적입니다. 재귀 호출은 콜 스택 공간 사용을 발생시키므로 단순 반복 작업은 for 문을 사용하는 것이 좋습니다.// 반복문 (효율적) public static int sum1(int n) { int total = 0; for (int i = 1; i 패턴 2: 하위 문제 기반 문제 해결 (하향식 vs. 상향식)재귀는 하위 문제의 결과를 기반으로 현재 문제를 해결하는 데 특히 유용합니다. 대표적인 예가 팩토리얼 계산입니다.재귀함수를 이용한 팩토리얼 자바코드 예시public static int factorial(int n) { if (n == 0) { return 1; } return n * factorial(n - 1); }for문을 이용한 팩토리얼 자바코드 예시public static int factorial(int n) { int result = 1; for (int i = 1; i 재귀와 반복문재귀 함수는 상향식 계산도 가능하지만, 반복문으로 구현하는 것보다 성능이 좋지 않습니다.재귀 함수는 하향식 계산에서 위력을 발휘합니다. 특히 문제의 구조 자체가 재귀적인 경우 재귀 함수를 사용하면 코드를 간결하고 이해하기 쉽게 만들 수 있습니다. 재귀와 for문을 이용해 배열의 합 구현// 재귀 함수 public static int arraySum(int[] arr, int n) { if (n == 0) { return 0; } return arr[n - 1] + arraySum(arr, n - 1); } // 반복문 public static int arraySum(int[] arr) { int total = 0; for (int num : arr) { total += num; } return total; } 문자열 길이 계산 public static int strLength(String arr) { if (arr == null || arr.isEmpty()) { return 0; } return strLength(arr.substring(1)) + 1; } 지수 함수 하향식 구현public static int power(int x, int y) { if (y == 0) { return 1; } return x * power(x, y - 1); } 3일차컴파일과 프로세스, 재귀 - 하노이 탑 컴파일과 프로세스프로그래밍 언어의 종류프로그래밍 언어는 컴파일 언어와 인터프리터 언어로 구분할 수 있습니다.컴파일 언어개발자가 코드를 작성하고 컴파일이라는 과정을 거쳐 기계어(0과 1) 로 된 실행 파일을 생성합니다.컴파일 과정에서 문법 오류가 있는지 검사하고, CPU에서 실행할 수 있는 기계어로 변환합니다.미리 실행 파일을 만들어 놓으므로 실행 속도가 빠릅니다.예시: C, C++, C# 등인터프리터 언어개발자가 작성한 코드를 미리 기계어로 변환하지 않고, 실행 시점에 한 줄씩 해석하며 실행합니다.실행 전에 오류 검사를 하지 않기 때문에 실행 중 오류가 발생할 수 있으며, 속도도 컴파일 언어보다 느립니다.예시: JavaScript, Python 등 컴파일 언어로 작성된 파일이 프로세스가 되기까지C 언어로 작성된 test.c 파일이 실행 파일이 되고, 최종적으로 프로세스가 되는 과정1. 컴파일 과정전처리컴파일러가 실행되면 가장 먼저 전처리기가 동작합니다.전처리기는 #include, #define 등 전처리 구문을 처리합니다.주석 제거를 수행한 후 전처리된 코드를 .i 파일로 저장합니다.컴파일전처리된 코드를 기계어에 가까운 어셈블리어로 변환합니다.이 과정에서 문법 오류 체크도 함께 이루어집니다.결과물은 어셈블리 코드가 담긴 .s 파일입니다.어셈블어셈블리어를 기계어 코드(오브젝트 코드)로 변환합니다.생성된 오브젝트 파일은 .o 확장자를 가집니다.이 오브젝트 파일에는 코드 영역과 데이터 영역이 나눠져 있습니다.링커오브젝트 파일은 실행 파일이 되기 위해 링커(Linker) 를 거칩니다.링커는 여러 오브젝트 파일을 하나로 합치고, 코드 영역과 데이터 영역을 하나로 묶습니다. 결과물은 실행 파일(.exe)입니다. 2. 프로세스 생성 과정실행 파일이 프로세스가 되려면 다음 과정을 거칩니다프로그램 실행사용자가 .exe 파일을 실행합니다.운영체제가 프로세스를 생성합니다.메모리 할당운영체제는 실행 파일에 있는 코드 영역과 데이터 영역을 가져와 프로세스의 코드 영역과 데이터 영역에 로드합니다.그리고 빈 스택(Stack)과 힙(Heap) 영역도 할당합니다.PCB 생성운영체제는 PCB를 생성하여 프로세스를 관리합니다.PCB에는 프로세스 상태, 프로그램 카운터(PC), CPU 레지스터, 메모리 정보 등이 저장됩니다.프로그램 카운터 설정프로그램 카운터(PC) 는 다음 실행할 명령어의 주소를 가리킵니다.처음에는 코드 영역의 첫 번째 명령어의 주소를 가리킵니다.CPU 스케줄링운영체제의 CPU 스케줄러가 프로세스를 준비 상태에 놓고, CPU를 할당받으면 실행 상태로 전환되어 명령어가 실행됩니다. 재귀-하노이탑자바 코드 사용 예시 public static void hanoi(int count, String from, String to, String temp) { if (count == 0) { return; } hanoi(count - 1, from, temp, to); System.out.println(count + "를 " + from + "에서 " + to + "로 이동"); hanoi(count - 1, temp, to, from); } public static void main(String[] args) { hanoi(3, "A", "C", "B"); // 3은 옮겨야할 갯수 A는 시작위치 C는 도착해야할 위치 B는 거쳐갈 위치 }결과창4일차메모리 관리,버블정렬과 선택정렬 메모리의 종류레지스터가장 빠른 기억 장소로 CPU 내부에 존재합니다.컴퓨터의 전원이 꺼지면 데이터가 사라지므로 휘발성 메모리입니다.CPU의 32비트, 64비트는 레지스터 크기를 의미합니다.CPU는 연산 시 메인 메모리(RAM)에 있는 데이터를 레지스터로 가져와 계산하고, 결과를 다시 메인 메모리에 저장합니다. 캐시(Cache)레지스터와 메인 메모리 사이에 위치하여, 데이터 접근 속도를 향상시키는 역할을 합니다.CPU는 필요한 데이터를 메인 메모리에서 가져오기 전에 L1 캐시 → L2 캐시 → L3 캐시 순으로 확인합니다.캐시에 가져올 데이터가 없으면 메인 메모리에서 데이터를 가져옵니다. 메인 메모리(RAM) 실제 운영체제와 프로세스가 로드되는 공간입니다.휘발성 메모리로, 전원이 꺼지면 데이터가 사라집니다.속도는 HDD/SSD보다 빠르지만, 가격이 비싸기 때문에 실행 중인 프로그램만 저장합니다. HDD/SSD비휘발성 메모리로, 전원이 꺼져도 데이터가 보존됩니다.속도는 메인 메모리보다 느리지만, 가격이 저렴하여 데이터 저장 용도로 사용됩니다. 메모리 할당 방식메모리 오버레이:프로그램을 분할하여 필요한 부분만 메모리에 로드하고, 나머지는 스왑 영역에 저장합니다.스왑(Swap): 스왑영역에 있는 데이터를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 옮기는것을 말합니다.가변 분할 방식(Variable Partitioning)프로세스 크기에 따라 메모리를 연속된 공간에 동적으로 할당합니다.장점: 연속된 공간으로 할당하기 때문에 내부 단편화가 발생하지 않습니다.단점: 외부 단편화가 발생합니다.예시: 프로세스 A(50MB), B(30MB), C(15MB), D(10MB)가 메모리에 차례로 로드이후 A와 D가 종료되어 빈 공간(50MB + 10MB)이 생기고 새로운 프로세스 E(60MB)를 로드하려고 할 때 이 공간들은 연속되어 있지 않아 할당할 수 없는데 이를 외부 단편화라고 하며, 조각 모음을 통해 빈 공간들을 하나로 합쳐야 합니다. 이 과정은 메모리에 있는 프로세스를 일시 중지하고 공간을 이동시키는 작업이므로 오버헤드가 발생합니다. 고정 분할 방식(Fixed Partitioning)메모리를 고정 크기 블록으로 나눠 프로세스를 할당합니다.장점: 구현이 간단하고 오버헤드가 적습니다.단점: 프로세스 크기와 상관없이 고정된 크기로 메모리를 할당하므로 내부 단편화가 발생합니다.예시: 메모리를 2MB로 나눈다 가정할 때 프로세스 A(1MB), B(2MB), C(5MB)를 할당할 경우,A는 2MB 블록에 할당되어 1MB의 내부 단편화가 발생합니다. B는 2MB 블록에 할당되고 B는 2MB이기 때문에 정확히 떨어짐. C는 총 5MB이기 때문에 2MB 블록을 3개의 구역에 나눠서 저장해 1MB의 내부 단편화가 발생. 버디 시스템(Buddy System)가변 분할 방식과 고정 분할 방식을 혼합하여 단점을 보완합니다.메모리를 2의 제곱수 크기로 나누고, 필요할 때마다 나눠 프로세스를 할당합니다.장점: 외부 단편화를 방지하고, 메모리 합병(병합)이 간단합니다.단점: 약간의 내부 단편화가 발생할 수 있습니다. 그럼 메모리 할당 방식은 둘의 단점을 최소화한 버디 시스템이 최고인가??버디 시스템의 내부 단편화와 작은 크기의 블럭을 지나치게 나누면 생기는 메모리 관리 오버헤드가 커질수있어 최신 운영체제는 페이징 기법을 활용하거나, 세그멘테이션과 조합해서 사용페이징 기법 (Paging)정의:메인 메모리를 고정된 크기의 블록인**페이지 프레임(Page Frame)으로 나누고, 프로세스의 가상 메모리 공간도 동일한 크기의 **페이지(Page)로 나눕니다.프로세스의 페이지들은 메모리의 페이지 프레임에 비연속적으로 할당됩니다.페이지 프레임과 페이지란???페이지는 프로세스를 나눈 조각페이지 프레임은 메모리를 나눈 조각장점:외부 단편화가 발생하지 않습니다.메모리 관리가 단순해집니다.단점:내부 단편화가 발생할 수 있습니다. (마지막 페이지가 완전히 채워지지 않는 경우)예시:프로세스 A가 5KB이고, 페이지 크기가 2KB라면, A는 3개의 페이지로 나뉩니다.마지막 페이지는 1KB만 사용되고 1KB는 낭비되므로 내부 단편화가 발생합니다.추가 설명: 페이지 테이블을 사용하여 가상 주소를 물리 주소로 변환합니다.고정 분할 방식과 페이징 기법은 비슷하지만 고정 분할 방식은 메모리를 나눈 후 프로세스를 맞춰 넣는 방식이고,페이징은 프로세스를 나눈 후 메모리에 퍼즐처럼 넣는 방식 세그멘테이션 (Segmentation)정의:프로세스를 논리적인 의미 단위인 세그먼트(Segment)로 나누어 메모리에 로드합니다.세그먼트의 크기는 가변적입니다.장점:논리적으로 관련된 코드나 데이터가 한 곳에 모이므로 효율적입니다.프로그램의 구조를 반영하여 메모리를 관리할 수 있습니다.단점:외부 단편화가 발생할 수 있습니다.예시:프로그램이 코드(10KB), 데이터(5KB), 스택(8KB)으로 나뉜 경우, 각 부분이 독립적인 세그먼트로 관리됩니다.추가 설명:세그먼테이션은 프로그램의 논리적인 구조를 반영하여 메모리를 관리하는 데 유용합니다.최근에는 페이징과 함께 사용되어 메모리 보호 및 공유 기능을 강화합니다.요약:페이징은 메모리를 고정 크기로 나누어 관리하고, 세그멘테이션은 논리적인 단위로 나누어 관리합니다.페이징은 외부 단편화를 해결하고, 세그멘테이션은 프로그램의 논리적인 구조를 반영합니다.. 페이징 + 세그먼테이션을 사용하면 내부/외부 단편화가 완전히 사라지는 것은 아니지만, 각각의 단점을 최소화할 수 있습니다. 버블 정렬과 선택 정렬정렬 알고리즘은 데이터를 특정 순서로 나열하는 방법을 정의버블 정렬과 선택 정렬은 가장 기본적인 정렬 알고리즘으로 이해와 구현이 쉽지만 성능은 다소 아쉬움1. 버블 정렬 (Bubble Sort)원리:인접한 두 원소를 비교하여 순서가 맞지 않으면 교환하는 과정을 반복합니다. 예시:[4, 2, 3, 1] 배열을 정렬하는 과정:[2, 4, 3, 1] (4와 2 교환)[2, 3, 4, 1] (4와 3 교환)[2, 3, 1, 4] (4와 1 교환)위 과정을 반복하여 [1, 2, 3, 4] 완성성능:시간 복잡도: O(n²) - 데이터가 많아질수록 비교 횟수가 제곱으로 증가합니다.장단점:장점: 이해와 구현이 매우 쉽습니다.단점: 성능이 좋지 않아 대규모 데이터 처리에는 부적합합니다. 자바코드로 예시 구현 public static void bubble(int[] arr) { int n = arr.length; for (int i = 0; i arr[j + 1]) { // arr[j]번쨰 값이 arr[j]다음의 값보다 크다면 int temp = arr[j]; // 현재 arr[j]번째의 값을 저장해두고 arr[j] = arr[j + 1]; // arr[j]의 값을 arr[j] 다음의값으로 변경 arr[j + 1] = temp;// arr[j] 다음의값을 이전에 temp에 저장해둔 arr[j]값으로 변경 } } } } public static void main(String[] args) { int[] arr = {4, 2, 3, 1}; bubble(arr); for (int num : arr) { System.out.print(num + " "); } } 2. 선택 정렬 (Selection Sort)원리:배열에서 가장 작은 원소를 찾아 첫 번째 위치로 이동시키고, 다음으로 작은 원소를 찾아 두 번째 위치로 이동시키는 과정을 반복합니다.정렬되지 않은 부분에서 최소값을 선택하여 정렬된 부분의 마지막 위치로 이동시킵니다.예시:[4, 2, 1, 3] 배열을 정렬하는 과정:[1, 2, 4, 3] (최소값 1을 첫 번째 위치로 이동 기존에 있던 4는 1이있던 자리로 이동)[1, 2, 4, 3] (다음 최소값 2는 이미 정렬된 위치)[1, 2, 3, 4] (다음 최소값 3을 세 번째 위치로 이동)성능:시간 복잡도: O(n²) - 버블 정렬과 마찬가지로 성능이 좋지 않습니다.장단점:장점: 버블 정렬과 마찬가지로 이해와 구현이 쉽습니다.단점: 성능이 좋지 않아 대규모 데이터 처리에는 부적합합니다. 자바코드로 예시 구현 public static void selection(int[] arr) { for (int i = 0; i 정리버블 정렬과 선택 정렬은 기본적이지만 비효율적인 정렬 알고리즘입니다. 2주차 회고 잘한 점저번주에 다짐했던 그날그날 강의를 듣고 정리하는건 잘지켰고 확실히 그날 배운 내용을 바로바로 정리하니 저번주보다 죽은지식이 덜했습니다.저번주는 몰아서 정리하다보니 아 이거 뭐였지 하며 다시 찾아보고 하는 경우가 많았는데 현저히 줄어든게 느껴졌습니다. 아쉬운 점운영체제는 역시 여전히 어려웠습니다.아무래도 강의가 기본으로 쉽게 이해하려는데 초점이 맞춰져있다보니 아주 쉽게 동작원리를 알려주다보니 하나의 내용을 던져주고 궁금해서 그걸 가지고 파다보면 끝도없는 용어와 또 다른 내용이 튀어나와 역시 쉽지않았습니다.자료구조와 알고리즘은 재귀 버블정렬 등 해당 알고리즘의 개념을 이해만 한다면 코드로 녹여내는건 생각보다 어렵지않았고 오히려 정말 재밌게 공부했었습니다.이무래도 코드를 작성하면 시각적으로 결과가 바로바로 보여지다보니 좀더 흥미를 느꼈던거같습니다. 개선할 점이제 다음주가 마지막 주차인데 이번주 보다 공부 시간을 좀 더 늘리겠습니다. 목표이번주 역시 로드맵에 맞게 해당 강의 영상을 듣고 바로바로 발자국으로 내용 정리하기2주차에 투자한 공부시간보다 더 늘리기질문 더 많이하기

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

여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요. 학생의 정보는 보통 학번,이름,반,성적 등이 저장 될텐데 해당 정보들은 해시테이블을 활용하면 좋을거 같습니다.반에서 학번은 중복되는 경우는 없기때문에 학번을 키(key)값으로 저장하여 빠른 탐색이 가능하게 할거같습니다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요. 주문은 항상 먼저 들어온 주문을 처리해야해 FIFO(First in First Out)성질을 가져 큐(Queue)를 활용하는에 맞습니다.큐는 선입선출 방식의 알고리즘을 가져 먼저 들어온 데이터의 정보는 가장 먼저 나와야 합니다. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.class Stack{ constructor(){ this.list = new LinkedList(); } push(data){ this.list.insertAt(this.list.count, data); // 현재 count의 인덱스에 해당 데이터를 삽입 } pop(){ try{ return this.list.deleteLast(); // 마지막 인덱스를 삭제 }catch{ return null; } } 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력 hashFunction(name){ return name.charCodeAt(0) % 10; }

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

1. while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?메인 작업을 진행 중 특정 상황이 발생 시 해당 작업을 먼저 실행하는 인터럽트 방식을 사용합니다. JAVA를 활용한 코드public class InterruptTest extends Thread { @Override public void run() { try { while(true) { Thread.sleep(1); System.out.println("실행중"); } } catch (InterruptedException e) { System.out.println("InterruptedException 발생"); } System.out.println("종료"); } public static void main(String[] args) throws InterruptedException { InterruptTest t = new InterruptTest(); t.start(); // 쓰레드 시작 // 메인 쓰레드에서 잠시 대기 후 인터럽트 발생 Thread.sleep(5); t.interrupt(); // 인터럽트 발생 System.out.println("Main Thread 종료..."); } } 프로그램과 프로세스가 어떻게 다른가요?프로그램은 컴퓨터에서 수행할 작업을 정의한 명령문의 집합으로 해당 명령들은 하드디스크(HDD), SSD 등 저장장치에 저장프로세스는 저장장치에 있던 프로그램이 메모리에 올라가게되면 프로세스라 불림프로그램과 프로세스의 차이로는 프로그램은 저장장치만 사용하기 대문에 수동적이지만 프로세스는 메모리와 운영체제의 CPU 스케줄링에 의해 필요에 따라 입출력을 수행하기때문에 능동적임 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍은 하나의 CPU에서 여러개의 프로세스가 동작하는 방식이고 멀티프로세싱은 CPU 코어가 여러개있을시 동시에 프로세스를 작동하는 방식둘의 큰 차이로는 멀티프로그래밍은 시분할 방식으로 진행하고 멀티프로세싱은 여러 프로세스를 동시에 실행할수있음 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?PCB를 사용합니다PCB는 각 프로세스마다 하나의 PCB가 생성되고 프로세스의 상태와 정보를 연결리스트 형태로 저장되며 프로세스 종료시 PCB는 제거됩니다. 컨텍스트 스위칭이란 뭔가요?컨텍스트 스위칭은 실행 중인 프로세스를 저장하고 다른 프로세스를 실행하기 위해 상태 값을 교체하는 작업으로 컨텍스트 스위칭이 발생할 때 PCB의 내용이 변경됩니다.변경되는 내용은 프로세스의 상태와 각종 레지스터 값등이 있습니다.

[인프런 워밍업 클럽 3기 CS전공지식] 1주차 발자국

1일차운영체제 및 자료구조와 알고리즘 운영체제가 하는일프로세스 관리프로세스 관리는 운영체제의 핵심 기능 중 하나입니다. 여러 프로그램(예: 여러 브라우저 창)을 동시에 실행할 수 있는 이유는 운영체제가 각 프로세스를 효율적으로 관리해주기 때문입니다.역할 : CPU의 자원을 여러 프로세스가 공평하게 사용할 수 있도록 스케줄링하고, 각 프로세스의 실행 상태를 관리합니다.중요성 : 만약 운영체제가 프로세스를 관리하지 않으면, 특정 프로그램이 CPU를 독차지해 다른 프로그램이 실행되지 않을 수도 있습니다. 메모리 관리운영체제는 시스템 메모리(RAM)를 효율적으로 관리합니다. 모든 프로그램은 메모리에 로드된 후 실행되기 때문에 메모리 관리는 필수적인 기능입니다.역할 : 각 프로그램이 필요한 메모리 공간을 할당하고, 사용이 끝난 메모리를 해제합니다.중요성 : 효율적인 메모리 관리를 통해 여러 프로그램이 원활하게 실행되며, 메모리 부족으로 인한 시스템 오류를 방지할 수 있습니다. 하드웨어 관리운영체제는 사용자가 하드웨어에 직접 접근하는 것을 제한하고, 안정적이고 안전한 하드웨어 사용 환경을 제공합니다.역할 : 키보드, 마우스, 디스크 드라이브, 프린터 등의 하드웨어 장치와 소프트웨어 사이의 중재자 역할을 합니다.중요성 : 사용자가 하드웨어에 직접 접근하면, 하드디스크의 중요한 데이터를 훼손하거나 악의적인 공격을 가할 가능성이 있습니다. 운영체제가 이를 방지하고 보호합니다. 파일 시스템 관리운영체제는 하드디스크에 저장된 파일들을 효율적으로 관리하고, 사용자가 쉽게 접근할 수 있도록 합니다.역할 : 파일 생성, 수정, 삭제, 검색 등 파일 관련 작업을 담당합니다.중요성 : 체계적인 파일 관리 덕분에 사용자는 원하는 데이터를 빠르게 찾고, 데이터를 안전하게 보관할 수 있습니다. 운영체제 구조운영체제의 구조에서 가장 핵심적인 부분은 커널(Kernel)입니다.커널은 운영체제의 중심이 되는 프로그램으로, 프로세스와 메모리, 저장 장치를 관리하는 핵심적인 기능을 담당합니다.커널과 사용자 인터페이스커널에 사용자가 직접 접근하는 것은 불가능하며, 인터페이스를 통해 간접적으로 접근합니다. 대표적인 인터페이스 방식은 GUI와 CLI로 나뉩니다.GUI (Graphical User Interface): 그래픽 기반의 인터페이스로, 윈도우(Windows)나 맥OS(macOS) 같은 운영체제가 대표적입니다.CLI (Command Line Interface): 텍스트 기반의 인터페이스로, 유닉스(Unix)나 리눅스(Linux)에서 제공하는 터미널 환경이 대표적입니다. 운영체제에서 어플리케이션은 시스템 콜(System Call)을 통해 커널에 접근합니다.시스템 콜의 역할: 프로그램이 하드웨어 자원(CPU, 메모리, 디스크 등)에 안전하게 접근할 수 있도록 중간 역할을 합니다.시스템 콜이 필요한 이유??만약 시스템 콜 없이 프로그램이 하드디스크에 직접 접근할 수 있다면, 중요 데이터를 덮어쓰거나 다른 어플리케이션의 데이터를 훼손할 위험이 있습니다.컴퓨터 하드웨어와 구조오늘날 대부분의 컴퓨터는 **폰 노이만 구조(Von Neumann Architecture)를 기반으로 합니다.* 폰 노이만 구조란?컴퓨터 시스템에서 데이터와 프로그램을 같은 메모리 공간에 저장하고 CPU가 이를 처리하는 방식CPU의 구조CPU(중앙처리장치)는 컴퓨터에서 명령을 처리하는 핵심 장치입니다.산술논리 연산장치(ALU): 데이터의 연산을 수행합니다.제어장치: 모든 장치의 동작을 지시하고 제어합니다.레지스터: 연산 중 데이터를 임시로 저장하는 고속 메모리입니다. 메모리의 종류RAM(랜덤 액세스 메모리): 저장 위치와 상관없이 동일한 속도로 데이터를 읽습니다. 전원이 끊기면 데이터를 잃어버리기 때문에 주 메모리(Main Memory)로 사용됩니다.ROM(읽기 전용 메모리): 전원이 끊겨도 데이터를 유지하지만, 한 번 저장된 데이터는 수정이 불가능합니다.BIOS(기본 입출력 시스템) 등을 저장하는 데 사용됩니다. 컴퓨터의 부팅 과정ROM에 저장된 BIOS가 실행됩니다.BIOS가 CPU, RAM, 키보드 등 주요 하드웨어의 이상 여부를 점검합니다.이상이 없으면 하드디스크의 **MBR(마스터 부트 레코드)에 저장된 **부트로더(bootloader)를 메모리로 로드하고 실행합니다.부트 후 모든 응용 프로그램은 메모리에 올라와 운영체제가 관리합니다.** MBR과 부트로더란???MBR은 하드디스크의 첫 번째 섹터에 위치한 영역으로 하드디스크가 BIOS에 의해 처음 읽힐때MBR을 읽어 부팅을 시작하게되는데 주요 역할로는 부트로더 위치 정보를 저장하고 디스크 파티션 정보를 저장함부트로더는 운영체제를 메모리로 로드하고 실행하는 역할주요 역할로는 운영체제를 로딩과 다중 부팅이 가능함인터럽트(Interrupt)인터럽트는 CPU와 입출력 장치 간 효율적인 작업 처리를 가능하게 합니다.폴링 방식 : CPU가 주기적으로 입출력 장치의 상태를 확인하는 방식입니다. 비효율적입니다.인터럽트 방식 : CPU가 다른 작업을 수행하는 동안 입출력 장치가 작업 완료 신호를 보냅니다. CPU는 **인터럽트 서비스 루틴(ISR)을 실행해 해당 작업을 처리합니다.** 인터럽트 서비스 루틴(ISR)이란?인터럽트가 발생했을때 호출되는 특정 목적을 처리하는 함수예를 들면평소에는 책 읽는 중(=메인 작업)도중에 전화가 오면(=인터럽트 발생) 책을 잠시 덮고 전화를 받음(=ISR 실행)문 열고 나서 다시 책 읽기(=메인 작업 복귀)이런 느낌이다.자료구조와 알고리즘자료구조자료구조(Data Structure)는 데이터를 어떤 구조로 저장하고 어떻게 사용될지를 나타냅니다. 다양한 자료구조가 존재하며, 각 구조마다 장단점과 사용 목적이 다릅니다.대표적으로변수: 가장 단순한 형태의 자료구조로, 하나의 데이터를 저장합니다.배열: 같은 종류의 데이터를 순서대로 저장하는 자료구조입니다.연결 리스트, 스택, 큐, 해시 테이블, 트리, 그래프: 보다 복잡한 구조로, 다양한 상황에서 데이터를 효율적으로 저장하고 처리합니다.시간 복잡도시간 복잡도는 특정 알고리즘이 문제를 해결하는 데 걸리는 시간을 나타내는데 여기서 걸리는 시간은 실제로 걸리는 시간이 아닌 입력크기(n의값)이 커졌을떄 연산횟수가 어떻게 변하는지 기준으로함하지만 컴퓨터의 성능에 따라 실행 시간이 달라지기 때문에, 코드에서 성능에 영향을 주는 부분을 찾아 실행 시간을 예측합니다.두 가지의 예)반복문 사용public class SumExample { public static void main(String[] args) { int n = 1000; // 입력 크기 int sum = 0; for (int i = 1; i 수학 공식 이용public class SumExample { public static void main(String[] args) { int n = 1000; // 입력 크기 int sum = n * (n + 1) / 2; // 항상 3번 연산 System.out.println(sum); } } 위 방법을 비교했을때 방법1은 n번을 기준으로 반복하지만 방법2는 3번을 연산n이 1000일 경우 방법1은 1000번을 반복해 1초가 걸리고 방법2는 3번을 연산을해 0.1초가 나왔다 가정을 했을때만약 cpu가 고성능일 경우 두 방법 모두 0.1초가 나올 경우도 있기때문에 처리하는 실제 시간이 아닌 연산횟수를 기준으로 하게됨위 방법을 기준으로 했을때 2번쨰 방법이 좋은 알고리즘 방법임시간 복잡도를 평가하는 방법반복문은 알고리즘의 성능에 가장 큰 영향을 미칩니다. 반복문의 중첩 정도와 실행 횟수에 따라 시간 복잡도가 결정됩니다.예시: 배열 [1, 2, 3, 4]에서 숫자 1을 찾는 경우는 첫 번째에 바로 찾을 수 있지만, 4를 찾으려면 배열 전체를 순회해야 합니다. 이런 상황에 따라 성능이 달라지므로 시간 복잡도는 최선, 최악, 평균의 경우로 나눕니다.Big-Ω (오메가): 최선의 경우 시간 복잡도.public class BigOmegaExample { public static boolean findNumber(int[] arr, int target) { for (int num : arr) { if (num == target) { return true; // 최선의 경우: 첫 번째 요소에서 찾음 } } return false; } public static void main(String[] args) { int[] numbers = {1, 2, 3, 4, 5}; System.out.println(findNumber(numbers, 1)); // 최선의 경우 } }Big-Θ (세타): 평균의 경우 시간 복잡도. public class BigThetaExample { public static boolean findNumber(int[] arr, int target) { for (int num : arr) { if (num == target) { return true; // 평균적으로 배열의 절반을 탐색 } } return false; } public static void main(String[] args) { int[] numbers = {1, 2, 3, 4, 5}; System.out.println(findNumber(numbers, 3)); // 평균적인 경우 } }Big-O: 최악의 경우 시간 복잡도.public class BigOExample { public static boolean findNumber(int[] arr, int target) { for (int num : arr) { if (num == target) { return true; } } return false; // 최악의 경우: 배열 끝까지 탐색 } public static void main(String[] args) { int[] numbers = {1, 2, 3, 4, 5}; System.out.println(findNumber(numbers, 5)); // 최악의 경우 } }이중 Big-O 표기법이 가장 널리 사용되는데 주로 알고리즘의 성능을 평가할 때 최악의 경우를 기준으로 설명하므로 많이 사용되기 때문입니다. 알고리즘의 성능을 평가할때 최악을 경우를 기준으로 설명하는 이유알고리즘 성능을 최악의 경우로 평가하는 이유는, 최악의 상황에서도 최소한 그 정도 시간 이상은 걸리지 않기 때문입니다. 이렇게 평가하면 평균적인 성능도 예측할 수 있고, 예기치 않은 상황에서도 안전하게 동작한다고 보장할 수 있습니다. 일상을 예로 들면평균적인 경우: 집에서 학교까지 보통 30분 걸림최악의 경우: 비가 오고, 차가 막히고, 사고가 나면 1시간 걸림학교에 늦지 않으려면?평균 30분만 보고 출발하면, 최악의 경우에 지각할 수 있습니다.최악 1시간을 기준으로 준비하면 어떤 일이 생겨도 늦지 않게됨 Big-O 표기법의 특징입력 크기에 따른 계산량: 빅오 표기법은 입력 크기 n이 커질 때 계산량이 어떻게 증가하는지를 나타냅니다. 이는 알고리즘의 성능을 추상적으로 표현하는 방법입니다.상수와 낮은 차수 항을 무시함: 빅오 표기법에서는 상수나 낮은 차수 항을 무시합니다.예를 들어, n² +2n +100n처럼 복잡한 식이 있을 때, 가장 영향을 많이 주는 항만 표기해 해당 예에선 n² 이 가장 영향을 많이 미쳐 상수 항인 100과 낮은 차수 항인 2n은 성능에 큰 영향을 미치지 않으므로 빅오 표기법에서는 이들을 생략해 O(n²) 으로 표현함 2일차프로세스와 배열,연결리스트 프로그램과 프로세스 개념프로그램이란?하드디스크(HDD), SSD와 같은 저장장치에 저장된 명령문의 집합체애플리케이션(앱)이라고도 불리며, 윈도우에서는 보통 .exe 확장자를 가짐 프로세스란?실행 중인 프로그램을 의미하드디스크에 저장된 프로그램이 메모리에 올라가 실행될 때 프로세스가 됨 프로그램과 프로세스의 차이프로그램: 저장장치만 사용하기 때문에 → 수동적프로세스: 메모리와 운영체제의 CPU 스케줄링 알고리즘에 따라 CPU 사용, 필요에 따라 입출력을 수행 → 능동적 프로세스의 구조Code 영역: 프로그램의 실행 코드가 저장되는 영역으로, 읽기 전용이다.Data 영역: 전역 변수와 static 변수가 저장되며, 프로그램 종료까지 유지된다.Stack 영역: 함수 호출 시 생성되는 지역 변수와 매개변수가 저장되며, 함수 종료 시 제거된다.Heap 영역: 프로그래머가 동적으로 메모리를 할당하는 영역 CPU가 프로세스를 실행하는 순서데이터를 메모리에 저장 (예: 숫자 5와 7)데이터를 레지스터(**EDX, **EAX)로 로드제어 장치가 연산 명령 실행 → ALU(산술 논리 연산 장치)가 연산 수행연산 결과를 EAX 레지스터에 저장 후 메모리에 다시 저장** ALU : 데이터의 연산을 담당하는 장치** EAX : 범용 레지스터 중 하나로, 보통 연산의 결과를 저장하는 데 사용 특히 산술 및 논리 연산에서 많이 쓰임** EDX : 보조적인 역할을 하는 레지스터로. 곱셈, 나눗셈 같은 연산에서 EAX와 함께 사용돼서 큰 숫자를 처리하거나 나머지 값을 저장하는 데 쓰임 멀티프로그래밍과 멀티프로세싱유니프로그래밍과 멀티프로그래밍유니프로그래밍: 메모리에 하나의 프로세스만 존재하나의 작업이 끝나야 다음 작업 시작 → CPU가 쉬는 시간(입출력 대기 시간)이 많아 비효율적 멀티프로그래밍: 메모리에 여러 프로세스가 존재한 프로세스가 입출력 작업 중이면, 다른 프로세스가 CPU 사용 -> CPU사용 극대화 하지만 CPU가 어떤 작업을 먼저 할지(=스케줄링이 필요) 멀티프로세싱병렬 처리를 통해 성능을 높이고 안정성을 강화하며, 빠른 응답과 확장성을 제공합니다여러 개의 CPU가 동시에 여러 프로세스를 실행하는 방식으로 시분할 형식과는 살짝 다름시분할 방식은 싱글코어에서 여러 프로세스를 빠르게 번갈아 실행하는 방식.멀티프로세싱은 멀티코어에서 실제로 동시에 실행 멀티코어는 시분할과 멀티프로세싱이 동시에 가능 PCB란?PCB는 운영체제가 프로세스를 관리하기 위해 사용하는 데이터 구조입니다.각 프로세스마다 하나의 PCB가 생성되며 프로세스의 상태와 정보를 담고 있습니다.연결리스트 형태로 저장되며 프로세스 종료시 PCB는 제거됩니다. PCB 구성 요소포인터: 부모/자식 프로세스와 자원 포인터, 상태 전환 시 저장 포인터프로세스 상태: 생성, 준비, 실행, 대기, 완료 상태프로세스 ID: 프로세스를 식별하는 고유 번호프로그램 카운터: 다음 실행 명령어의 주소레지스터 정보: 실행 중 사용한 레지스터 값메모리 정보: 메모리 위치와 경계 레지스터 값CPU 스케줄링 정보: 우선순위, 최종 실행 시간, CPU 점유 시간 등 프로세스의 상태생성 상태: 프로세스 생성 요청 시 운영체제가 PCB 생성준비 상태: CPU 할당 대기실행 상태: CPU를 할당받아 실행 중 (CPU 수만큼 프로세스 실행 가능)대기 상태: 입출력 요청 시 대기 (입출력 완료 후 준비 상태로 전환)완료 상태: 프로세스 종료 및 메모리와 PCB 제거 배열,연결리스트배열장점: 빠른 데이터 참조(O(1)의 성능을 가짐)단점: 고정된 크기, 중간 삽입/삭제 시 비효율적(O(n)의 성능을 가짐)연결 리스트 (Linked List)장점: 동적 메모리 할당, 삽입/삭제 시 효율적단점: 느린 데이터 참조(O(n)의 성능을 가짐) 비연속적인 메모리 할당사용 상황배열: 데이터 변화가 적고 참조가 빈번할 때 유리연결 리스트: 삽입/삭제가 자주 발생할 때 유리빠른 조회가 필요한 상황이면 배열이 유리하고 데이터 추가,삭제가 자주 일어나면 연결 리스트가 유리함 연결리스트 구현 예제class Node{ constructor(data, next = null){ this.data = data; // 현재 데이터 정보 this.next = next; // 다음 데이터의 정보 } } class LinkedList{ constructor(){ this.head = null; // 연결리스트의 head 부분 this.count = 0; // 인덱스 카운트 } printAll(){ // 현재 연결리스트의 정보 모두 출력 let currentNode = this.head; let text = "["; while(currentNode != null){ // 현재 노드가 널일경우 반복문을 벗어남 text += currentNode.data; currentNode = currentNode.next; if(currentNode != null){ text += ", "; } } text += "]"; console.log(text); } clear(){ // 연결리스트의 데이터를 전부 제거 this.head = null; this.count = 0; } insertAt(index,data){ // 특정 위치에 데이터를 하나씩 삽입 if(index > this.count || index = this.count || index = this.count || index 3일차컨텍스트 스위칭와 쓰레드, 큐 스택컨텍스트 스위칭컨텍스트 스위칭(Context Switching)은 실행 중인 프로세스를 저장하고 다른 프로세스를 실행하기 위해 상태 값을 교체하는 작업입니다. 컨텍스트 스위칭이 발생할 때, PCB(Process Control Block)의 내용이 변경됩니다.실행 중인 프로세스의 작업 내용을 PCB에 저장하고, 실행될 프로세스의 PCB 내용을 기반으로 CPU가 다시 세팅됩니다.컨텍스트 스위칭 시 PCB에 저장 및 변경되는 값은 다음과 같습니다:프로세스 상태프로그램 카운터 : 현재 실행 중인 프로그램에서 다음에 실행될 명령어의 메모리 주소를 나타내는 레지스터각종 레지스터 값 컨텍스트 스위칭 과정운영체제(OS)가 프로세스 A가 CPU를 오래 사용했다고 판단하고 인터럽트(Interrupt)를 발생시킴.프로세스 A가 하던 일을 멈추고 현재 상태에서 나중에 재개할 수 있도록 CPU 레지스터 값을 PCB A에 저장.PCB B를 참조하여 이전 프로세스 B의 상태로 CPU 레지스터 값을 복원.프로그램 카운터의 값에 따라 프로세스 B의 명령어 실행.프로세스 B가 CPU 점유 시간이 끝나면 인터럽트를 발생시켜 PCB B에 현재 상태 저장.다시 PCB A의 내용을 불러와 프로세스 A 실행.메모리에 있는 모든 프로세스들은 컨텍스트 스위칭을 함 컨텍스트 스위칭 발생 이유CPU 점유 시간 만료 (타임 슬라이스 종료)I/O(입출력) 요청인터럽트 발생 (시스템 콜, 예외 처리 등) 프로세스 생성 과정.exe 파일 실행 시 운영체제는 해당 프로그램의 코드 영역과 데이터 영역을 메모리에 로드.메모리에 빈 스택(Stack)과 힙(Heap) 공간 생성.프로세스를 관리하기 위한 PCB 생성 및 초기화..exe 파일을 실행했을때 운영체제는 해당 프로그램의 코드영역과 데이터영역을 메모리에 저장하고메모리에 빈 스택과 빈 힙을 만들어 공간을 확보 후 이 프로세스를 관리하기위한 PCB를 만들어값을 초기화 해줌 부모-자식 프로세스 관계0번 프로세스(부모): 부팅 시 한 번만 실행.fork() 함수를 사용해 기존 프로세스를 복사하여 새로운 자식 프로세스 생성.자식 프로세스는 부모 프로세스의 코드, 데이터, 스택, PCB 내용 복사하지만 이렇게 되면 자식 프로세스를 실행하면 결국 부모 프로세스가 실행되는것과 다를게 없어 **exec() 함수를 사용**exec() 함수 사용자식 프로세스가 부모 프로세스와 완전히 다른 동작을 하도록 fork() 함수로 프로세스를 복사후 exec()함수를 실행시키면 부모를 복사한 자식 프로세스의 코드와 데이터 영역을 원하는 값으로 덮어쓰게됨 좀비 프로세스부모 프로세스가 자식보다 먼저 종료되거나 자식이 비정상 종료 시 발생.자식 프로세스가 exit() 신호를 받지 못해 Exit Status 미수신 시 메모리 점유 지속보통 컴퓨터를 오래 켜두면 해당 현상 발생 쓰레드(Thread)하나의 프로세스 내에서 여러 개의 쓰레드를 생성할 수 있습니다.쓰레드는 프로세스 내의 코드, 데이터, 힙 영역을 공유하지만 각 쓰레드는 독립적인 스택을 가집니다.쓰레드 간 통신은 데이터를 공유할 수 있기 때문에 빠르지만 공유 자원에서 문제가 발생할 수 있습니다. 쓰레드의 장점프로세스 내 존재, 1개 이상의 쓰레드 보유 가능.PCB, 코드, 데이터, 힙 영역 공유.스택은 독립적, 각 쓰레드마다 개별 보유.**TCB(Thread Control Block) 생성으로 쓰레드 구분 가능. ** TCB란?쓰레드 제어 블록으로, 각 쓰레드의 상태를 관리하는 데이터 구조입니다TCB가 필요한 이유쓰레드는 프로세스 내에서 실행되는 독립적인 작업이기 때문에 각 쓰레드의 상태와 정보를 독립적으로 관리할 필요가 있습니다.이를 위해 TCB를 사용하여 각 쓰레드의 실행 상태를 효율적으로 관리합니다. 쓰레드 사용 예시 (웹브라우저)기존 방식: 탭 추가 시 새로운 프로세스 복사 -> 메모리 사용 증가.쓰레드 방식: 프로세스 내에 새로운 쓰레드 추가 -> 메모리 효율 향상. 프로세스와 쓰레드의 장단점안정성프로세스: 독립적, 하나의 프로세스 문제가 다른 프로세스에 영향 없음.쓰레드: 동일 프로세스 내 문제 발생 시 모든 쓰레드 영향.안전성은 프로세스가 우수 속도 및 자원 효율성프로세스: 고유 자원 보유(코드,데이터,힙,스택영역을 따로 둠), IPC 필요 -> **오버헤드 크고 속도 느림.쓰레드: 스택을 제외한 영역 공유 -> 오버헤드 적고 통신 속도 빠름.** 오버헤드란?어떤 작업을 수행하는 데 필요한 추가적인 비용이나 시간 스택(Stack)First In Last Out(FILO): 먼저 들어간 데이터가 나중에 나옴.스택은 먼저 들어간 데이터가 나중에 나오기만 하면 어떤 자료구조로 구현하던 상관이 없음 연결리스트 기반 스택 동작 예시삽입(Push): 1 -> 2 -> 3 -> 4 순서로 삽입 시 4, 3, 2, 1 순서로 저장.제거(Pop): 가장 마지막에 삽입된 데이터부터 제거. 사용 사례Undo(Ctrl + Z): 그림판에서 그림을 그리다 잘못그리면 crtl+z를 사용하게되는데 컴퓨터가작업을 스택에 저장을 하고있어 crtl+z를 누르게 되면 가장 최근에 들어온 작업을 버려버림 스택의 주요 연산push(): 데이터 삽입.pop(): 데이터 제거.peek(): 데이터 참조.isEmpty(): 비어있는지 확인. 스택 구현 예제class Stack{ constructor(){ this.list = new LinkedList(); } push(data){ // 스택의 맨 뒤에 데이터 삽입 this.list.insertAt(0, data); } pop(){ // 스택의 맨 뒤 데이터 제거 try{ // 스택이 비어있을 경우 오류 방지 return this.list.deleteAt(0); }catch{ return null; } } peek(){ // 스택의 맨 앞 데이터 참조 return this.list.getNodeAt(0); } isEmpty(){ // 스택이 비어있는지 체크 return (this.list.count == 0); } } 큐(Queue)큐는 데이터를 한쪽 끝에서 삽입하고, 다른 쪽 끝에서 제거하는 자료구조로 FIFO(First In First Out) 방식으로 동작합니다. 즉, 가장 먼저 들어간 데이터가 가장 먼저 나옵니다. 큐의 동작 방식노드가 뒤의 노드를 가리키는 단방향 연결리스트인데 이런 구조면 맨뒤에있는 데이터를 삭제하기 힘들어지게됩니다.삽입의 경우 head를 사용해서 간단한데 제거의 경우 가장 뒤의 노드를 제거해야하기 때문에해당 노드에 접근하기 위해서 가장 앞 노드 부터 순서대로 접근을 해야해 O(n)의 성능을 가져 느림이를 위해 tail이라는 변수하나를 만들어 head는 가장 앞의 노드를 가르키고 tail은 가장 뒷 노드를 가르켜 O(1)의 성능으로 제거할수있음** 하지만 변수를 추가한다고 항상 O(1)의 성능을 가지는건 아닌데 변수를 이용해 마지막 노드를 삭제하면 삭제된 이전 노드를 다시 변수를 설정해줘야함 단방향 연결리스트라 tail로 이전 노드를 참조하는건 불가능해 현재 노드가 이전 노드로 가리킬 수 있는 이중 연결리스트를 사용해야함 큐의 주요 연산enqueue(): 데이터 삽입.dequeue(): 데이터 제거.front(): 데이터 참조.isEmpty(): 비어있는지 확인. class Queue{ constructor(){ this.list = new DoublyLinkedList(); } enqueue(data){ // 큐의 tail에 데이터 삽입 this.list.insertAt(0,data); } dequeue(){ // 큐의 head 부분 데이터 제거 try{ return this.list.deleteLast(); }catch(e){ return null; } } front(){ // 큐의 head 데이터 참조 return this.list.tail; } isEmpty(){ // 큐가 비었는지 확인 return (this.list.count == 0); } } 덱(Deque)덱(Deque, Double-ended Queue)은 데이터를 양쪽 끝에서 자유롭게 삽입하거나 제거할 수 있는 자료구조입니다. 덱은 큐와 스택의 특성을 모두 갖고 있습니다. 덱의 주요 연산printAll(): 모든 데이터 출력.addFirst(): head에 데이터 삽입.removeFirst(): head에서 데이터 제거.addLast(): tail에 데이터 삽입.removeLast(): tail에서 데이터 제거.isEmpty(): 비어있는지 확인. 덱 구현 예제 class Deque{ constructor(){ this.list = new DoublyLinkedList(); } printAll(){ // 덱 정보 모두 출력 this.list.printAll(); } addFirst(data){ // 덱의 head부분에 데이터 삽입 this.list.insertAt(0, data); } removeFirst(){ // 덱의 head 부분 데이터 제거 return this.list.deleteAt(0); } addLast(data){ // 덱의 tail에 데이터 삽입 this.list.insertAt(this.list.count,data); } removeLast(){ // 덱의 tail 부분 데이터 제거 return this.list.deleteLast(); } isEmpty(){ // 덱이 비어있는지 확인 return (this.list.count == 0); } }4일차 CPU 스케줄링과 FIFO, 해시테이블 CPU 스케줄링프로그램을 실행시키면 메모리에 프로세스가 생성되고, 프로세스에는 1개 이상의 스레드가 존재합니다. 프로세스들은 CPU를 차지하기 위해 운영체제의 명령을 기다리고 있으며, 운영체제는 모든 프로세스에게 CPU를 할당 및 해제하는 역할을 수행합니다. 이를 CPU 스케줄링이라 합니다.CPU 스케줄러가 고려해야 할 사항어떤 프로세스에게 CPU를 할당할 것인가?메모리에는 수많은 프로세스가 존재합니다. 이 중 어떤 프로세스에게 CPU 사용권을 줄 것인지를 결정해야 합니다.CPU를 할당받은 프로세스가 얼마나 오랫동안 CPU를 사용할 것인가?현대 운영체제는 시분할 방식(Time-sharing) 을 사용하여 여러 프로세스에게 짧은 시간 동안 번갈아 가며 CPU를 할당합니다.CPU Burst: 프로세스가 CPU를 할당받아 작업하는 시간I/O Burst: 프로세스가 입출력 작업을 수행하는 시간 다중 큐(Multi-Queue)프로세스 정보를 담고 있는 PCB(Process Control Block) 는 준비 상태의 다중 큐에 들어가 실행되기를 기다립니다.CPU 스케줄러는 준비 상태 큐를 참조하여 어떤 프로세스를 실행시킬지 결정합니다.다중 큐(Multi-Queue) 는 우선순위를 기반으로 여러 개의 큐로 나누어져 있으며 각 큐는 서로 다른 우선순위를 가질 수 있습니다.프로세스는 자신의 우선순위에 따라 해당 큐에 배치되며, 상위 우선순위 큐가 먼저 스케줄링됩니다.I/O 작업이 발생하면 실행 중인 프로세스는 해당 I/O 작업에 따라 분류된 큐에 들어가고, CPU 스케줄러는 이를 참조하여 스케줄링합니다. 스케줄링 목표리소스 사용률(Resource Utilization)CPU 사용률과 I/O 디바이스 사용률을 최대화하는 것이 목표입니다.오버헤드 최소화(Minimizing Overhead)스케줄링 계산이 지나치게 복잡하거나 컨텍스트 스위칭(Context Switching) 이 잦아지면 오히려 성능이 저하될 수 있으므로, 이러한 오버헤드를 최소화합니다.공평성(Fairness)모든 프로세스가 공평하게 CPU를 할당받아야 합니다.처리량(Throughput)주어진 시간 내에 최대한 많은 작업을 처리하는 것을 목표로 합니다.대기 시간(Waiting Time)작업을 요청한 후 실제 작업이 시작되기 전까지의 시간을 줄입니다.응답 시간(Response Time)대화형 시스템에서는 사용자의 요청에 빠르게 반응하는 것이 중요합니다.위 목표들은 서로 상반되는 경우가 많습니다.처리량을 높이기 위해서는 하나의 프로세스에 CPU를 오래 할당해야 하지만,응답 시간을 줄이려면 여러 프로세스에 CPU를 골고루 할당해야 합니다.예를 들어:터치스크린 기반 시스템 → 응답 시간 단축이 중요복잡한 계산 작업 → 처리량 극대화가 중요 FIFO(First In First Out)FIFO는 선입선출 방식의 스케줄링 알고리즘입니다.(Queue(큐)와 같음)먼저 도착한 프로세스가 완전히 끝나야 다음 프로세스가 실행됩니다.장점: 단순하고 직관적단점: 실행 시간이 긴 프로세스가 먼저 도착하면, 짧은 작업이 뒤에서 기다려야 하므로 **Convoy Effect(호위 효과) 발생** 호위 효과 : 긴 프로세스가 CPU를 점유하고 있을 때 짧은 프로세스들이 기다리는 상황 스케줄링의 성능은 평균 대기시간으로 평가 평균 대기 시간 계산 예시프로세스1: Burst Time 25초프로세스2: Burst Time 5초프로세스3: Burst Time 4초실행 순서: 1 → 2 → 3프로세스1: 대기 시간 0초프로세스2: 대기 시간 25초프로세스3: 대기 시간 30초평균 대기 시간: (0 + 25 + 30) ÷ 3 = 18.3초실행 순서: 3 → 2 → 1프로세스3: 대기 시간 0초프로세스2: 대기 시간 4초프로세스1: 대기 시간 9초평균 대기 시간: (0 + 4 + 9) ÷ 3 = 4.3초이처럼 실행 순서만 바꾸어도 평균 대기 시간이 크게 차이 납니다. 따라서 FIFO 알고리즘은 Burst Time에 따라 성능 편차가 심하여, 현대 운영체제에서는 거의 사용되지 않습니다.대신 **일괄 처리 시스템(Batch System)에서 주로 활용됩니다. ** 일괄 처리 시스템 : 사용자와의 상호작용 없이 데이터나 작업을 일정한 묶음으로 처리하는 시스템을 의미 주로 자동화된 작업이나 대량의 데이터 처리가 필요한 상황에서 사용예시 ) 월 급여를 계산하고 지급하는 작업을 일괄적으로 처리 혹은 정해진 시간마다 데이터를 백업하고 처리 해시 테이블(Hash Table)해시 테이블은 해시 함수를 사용하여 데이터를 키(Key) 와 값(Value) 쌍으로 저장하는 자료구조입니다.장점빠른 검색, 삽입, 삭제가 가능합니다.단점공간 효율성이 떨어집니다.미리 많은 메모리 공간을 할당해야 하며, 해시 함수에 따라 공간 낭비가 심할 수 있습니다.해시 테이블의 추상 자료형set(Key, Value): 데이터 삽입get(Key): 데이터 조회remove(Key): 데이터 삭제 해시 테이블 구현 예제 class HashTable{ constructor(){ this.arr = []; for(let i = 0; i 5일차SJF와 RR MLFQ, 셋(set) SJF(Shortest Job First)SJF는 Burst Time이 짧은 프로세스가 먼저 실행되는 알고리즘입니다.이론적으로 FIFO보다 성능이 좋지만 몇 가지 문제점이 있습니다.문제점Burst Time 예측 어려움 : 어떤 프로세스가 얼마나 실행될지 미리 예측하기 어렵습니다.Starvation(기아 현상) : 긴 Burst Time을 가진 프로세스는 짧은 작업이 계속 들어오면 무한히 대기할 수 있습니다.이러한 문제 때문에 SJF는 실질적으로 운영체제에서 잘 사용되지 않습니다. RR(Round Robin)RR은 시분할 방식(Time-sharing) 을 통해 FIFO의 단점을 보완한 알고리즘입니다.프로세스는 타임 슬라이스(Time Slice) 또는 타임 퀀텀(Time Quantum) 이라는 일정 시간 동안만 CPU를 사용합니다.타임 슬라이스가 지나면 강제로 CPU를 반납하고, 큐의 마지막으로 이동합니다.예시타임 슬라이스: 10초프로세스1(P1): Burst Time 25초프로세스2(P2): Burst Time 4초프로세스3(P3): Burst Time 10초실행 순서P1: 10초 실행 → 큐 뒤로 이동P2: 4초 실행 → 종료P3: 10초 실행 → 종료P1: 남은 15초 중 10초 실행 → 큐 뒤로 이동P1: 남은 5초 실행 → 종료대기 시간 계산P1: (0 + 10 + 14 + 14 + 0) ÷ 3 = 12.67초FIFO 방식일 경우 약 18초 RR 알고리즘은 타임 슬라이스 크기에 따라 성능이 크게 달라집니다.타임 슬라이스 크기의 영향너무 큰 경우 → FIFO 방식과 다를 바 없어짐.뮤직플레이어도 5초 실행하다 멈춰 굉장히 끊기게됨만약 타임슬라이스가 5초인 시스템에서 웹브라우저와 뮤직플레이어를 실행시키면 웹브라우저가 5초 실행하다멈추고너무 작은 경우 → 컨텍스트 스위칭이 자주 일어나 오버헤드 증가.왜 컨텍스트 스위칭이 자주 일어나면 오버헤드가 증가할까?컨텍스트 스위칭이 자주 일어나면 CPU가 실제 작업을 수행하는 시간을 줄이고 컨텍스트 스위칭 오버헤드가 커지기 때문에 시스템 효율성이 저하 결국 최적의 타임 슬라이스는 여러 프로세스가 동시에 실행되는 것처럼 보이면서 오버헤드가 크지 않은 값입니다.MLFQ(Multi Level Feedback Queue)MLFQ는 RR 알고리즘의 단점을 보완한 방식입니다.CPU Bound Process(CPU 사용 위주)와 I/O Bound Process(입출력 위주)를 구분하여 각각 적절한 시간 배분을 수행합니다.동작 방식우선순위 큐 사용높은 우선순위 큐: 짧은 타임 슬라이스 → 빠른 응답낮은 우선순위 큐: 긴 타임 슬라이스 → 효율적 처리큐 이동CPU를 오래 사용하는 프로세스 → 낮은 우선순위 큐로 이동 (Burst Time이 긴 프로세스)짧은 시간만 CPU 사용 후 반납 → 높은 우선순위 큐 유지 (I/O 작업 많은 프로세스)타임 슬라이스 조절프로세스가 타임 슬라이스를 초과하여 강제로 CPU를 반납하면, 낮은 우선순위 큐로 이동낮은 우선순위 큐로 이동할수록 타임 슬라이스 크기 증가프로세스가 계속 CPU를 점유할 경우 점점 더 긴 타임 슬라이스가 할당됨 타임 슬라이스 크기에 따른 차이점(P1은 연산만하는 프로세스 P2는 1초 연산 후 10초동안 I/O작업)타임 슬라이스가 100초일 경우(P2 먼저 실행의 경우)P2가 먼저 1초 실행 후 I/O 작업 대기P1이 100초 실행 중 10초 시점에서 P2의 I/O 완료 인터럽트 발생 → P2 다시 큐에 들어감100초 경과 후 P2가 다시 1초 실행 후 I/O 작업 요청반복CPU 사용률 100% / I/O 사용률 약 10%타임 슬라이스가 1초일 경우(P2 먼저 실행의 경우)P2가 1초 실행 후 I/O 작업 대기P1이 1초 실행 → 큐가 비어 바로 재실행 반복P2가 10번 실행되면 I/O 완료 인터럽트 → P2 다시 큐에 들어간 후 1초 실행반복CPU 사용률 100% / I/O 사용률 약 90%결론: 타임 슬라이스가 작을수록 CPU와 I/O 사용률이 고르게 유지되며, 자원 낭비가 줄어듭니다.해시 테이블(Hash Table)해시 테이블은 해시 함수(Hash Function) 를 사용하여 데이터를 키(Key) 와 값(Value) 쌍으로 저장하는 자료구조입니다.장점빠른 검색, 삽입, 삭제가 가능합니다.단점공간 효율성이 떨어집니다.미리 많은 메모리 공간을 할당해야 하며, 해시 함수에 따라 공간 낭비가 심할 수 있습니다.해시 테이블의 추상 자료형set(Key, Value): 데이터 삽입get(Key): 데이터 조회remove(Key): 데이터 삭제 셋(Set)셋(Set) 은 데이터의 중복을 허용하지 않는 자료구조이고 유일한 값만을 추구함add : 데이터 삽입isContain(data): 데이터 체크remove(data): 데이터 제거clear() : 셋 비우기isEmpty() : 셋이 비었는지 체크printAll() : 모든 데이터 출력 셋 구현 예제class HashSet{ constructor(){ this.hashTable = new HashTable(); } add(data){ // 셋 데이터 삽입 if(this.hashTable.get(data) == null){ // 만약 데이터가 존재하면 추가하지 않음 this.hashTable.set(data, -1); } } isContain(data){ // 셋 데이터 체크 return this.hashTable.get(data) != null; } remove(data){ // 셋 데이터 제거 this.hashTable.remove(data); } clear(){ // 셋 비우기 for(let i = 0; i 0){ empty = false; break; } } return empty; } printAll(){ // 셋의 모든 데이터 출력 for(let i = 0; i 1 주차 회고국비과정을 수료 후 기술면접을 준비하다 CS지식이 너무 부족하다 느껴 이번 인프런 워밍업 클럽을 신청하게 되었습니다.매주 해당 요일마다 들어야할 강의를 로드맵으로 정해 듣고 매주 해당 주차 강의내용을 바탕으로 미션을 수행한다는 점에 평소 공부를 할때 강제성이 좀 필요했던 저로서는 이번 기회가 반가웠습니다.처음 공부할때 강의 시간이 3분 5분 정도밖에 되지않아 금방 공부가 끝날줄 알았지만 하면 할수록 알아야 할 항목들이 많고 생소한 용어들이 많아 하나하나 찾아보고 정리하는 시간이 생각보다 만만찮았습니다.이번주는 중간에 2틀정도 강의를 못듣게 됬었는데 나중에 몰아서 듣다보니 많은 양을 이해하려하니 힘들었습니다.2주차 부터는 최대한 로드맵에 맞게 강의를 듣고 발자국 정리도 몰아서 정리가 아닌 해당 일차마다 바로바로 작성해서 정리할 예정입니다.