운영체제

*이 내용은 인프런 그림으로 쉽게 배우는 운영체제를 수강하며 정리한 내용입니다. program과 process하드디스크등과 같은 저장장치에 저장된 명령문의 집합체를 말해.애플리케이션이나 앱이라고도 불리고 windows 운영체제에서는 .exe 의 모습을 하고있지.그럼 process는 뭘까?간단히 말하면 실행중인 프로그램이야.하드디스크에 저장된 프로그램이 메모리에 올라갔을 때 실행 중인 프로그램, 즉 프로세스라고 불려.프로그램은 수동적, 프로세스는 수동적인 존재라고 할 수 있어. process의 구조CodeDataHeap : 프로그래머가 동적으로 메모리를 할당하는데에 쓰인다. ( malloc, free )Stack컴파일 과정멀티프로그래밍과 멀티프로세싱유니프로그래밍 : 메모리에 오직 하나의 프로세스가 올라온 것 멀티프로그래밍 : 메모리에 여러 개의 프로세스가 올라온 것 멀티프로세싱 : CPU가 여러 개의 프로세스를 처리하는 것PCB (Process Control Block)프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 가지고있는 PCB를 만들고 저장해.PCB들은 연결리스트라는 자료구조로 저장돼.운영체제는 프로세스가 종료되면 해당 프로세스의 PCB를 연결리스트에서 제거해.프로세스 상태실행상태에 있는 프로세스의수는 CPU의 개수만큼 입니다.대기상태프로세스가 입출력 요청을 하면 입출력이 완료될 때까지 기다리는 상태야.CPU에 비해 입출력작업은 상당히 느려.특정 프로세스가 입출력 요청을 하면 입출력이 완료될 때까지 CPU를 기다리게 하는건 굉장히 비효율적이야.대신 입출력 요청을 한 프로세스를 "대기상태"로 두고 다른 프로세스에게 CPU를 할당해그러다가 시간이 지나서 입출력 작업이 완료되면 "대기상태"에 있던 프로세스에게 CPU 할당 기회를 줘 컨텍스트 스위칭프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 변경하는 작업이야.컨텍스트 스위칭이 일어날 때 PCB의 내용이 변경돼. 실행 중인 프로세스의 작업 내용을 PCB에 저장하고 실행될 기존 프로세스의 PCB의 내용대로 CPU가 다시 세팅돼.컨텍스트 스위칭이 일어날 때 PCB에 변경하는 값들로는 아래와 같아.운영체제에서 프로세스 A와 프로세스 B사 컨텍스트 스위칭을 하는 법을 알려줄게.먼저 CPU에서 프로세스 A를 실행해.시간이 지난 후 운영체제에서 CPU가 프로세스 A를 너무 오래 실행했다고 판단하면프로세스 A는 하던 일을 멈추고, 현재 CPU의 레지스터 값 등을 PCB A에 저장해.이제 PCB B를 참조해서 이전 프로세스 B의 상태로 CPU의 레지스터값을 설정해.여기에는 다음 실행할 명령어의 주소를 가지고있는 프로그램 카운터(PC)를 가지고있기 때문에 바로 프로세스 B의 명령어를 실행할 수 있어.프로세스 B가 점유시간동안 CPU를 사용하다가 점유시간이 다되면 운영체제는 다시 인터럽트를 발생시키는거지. 컨텍스트 스위칭은 CPU 점유시간이 다됐거나, I/O 요청이 발생하거나, 다른 종류의 인터럽트가 있을 때 등의 상황에서 발생해. 프로세스 생성과 종료일반적으로 프로세스가 생성될 때의 방법에 대해 설명할게..exe 파일을 더블클릭으로 실행하면 운영체제는 해당 프로그램의 코드영역과 데이터영역을 메모리에 로드하고 빈 스택과 빈 힙을 만들어 공간을 확보해.그리곤 이 프로세스를 관리하기 위한 PCB를 만들어서 값을 초기화해줘.지금 설명한 프로세스 생성과정은 운영체제가 부팅되고 0번 프로세스가 생성될 떄 딱 한번 실행돼.그리고나서 나머지 모든 프로세스는 새로 생성하지않고 0번 프로세스를 복사해서 사용하게 돼.이때 fork() 함수를 사용해.복사해서 사용하는 이유는 새로 생성하는 것보다 복사를 하는게 더 빠르기 때문이야.0번 프로세스를 복사해서 생성된 프로세스들을 자식 프로세스라고 해. 그럼 0번 프로세스는 부모 프로세스가 되겠지?자식 프로세스는 부모 프로세스의 코드영역, 데이터영역, 스택영역과 PCB의 내용을 전부 복사해.0번 프로세스의 코드와 데이터를 모두 복사해서 실행하면 0번 프로세스가 똑같이 실행되는거 아닌가?맞아...그럼 자기가 원하는 함수를 어떻게 실행시킬까? 바로 exec() 함수를 이용하면 돼.fork() 함수로 프로세스를 복사 후 exec() 함수를 실행시키면 자식 프로세스의 코드와 데이터 영역을 원하는 값으로 덮어쓰게 돼.그럼 이때부터 자식 프로세스는 부모 프로세스와 완전히 다르게 동작하게되는거지!쓰레드운영체제가 작업을 처리하는 단위는 프로세스야. 사용자가 운영체제에게 작업을 요구하는만큼! 프로세스의 수가 늘어나.프로세스를 생성하면 PCB가 생성되고, 메모리에 코드, 데이터, 스택, 힙영역을 만들어줘야해.프로세스가 생성된 만큼 PCB가 생성되고, 마찬가지로 메모리에 코드, 데이터, 스택, 힙영역이(휴;;)만들어지기때문에 너무 무거워지지.웹 브라우저를 실행시키면 프로세스가 실행되겠지?탭 하나를 추가하면 기존 프로세스를 복사해서 총 2개 프로세스가 존재하게 돼.이런식으로 탭을 많이 늘리면 웹브라우저가 메모리를 너무 많이 차지하게 돼.이 웹브라우저들의 탭들은 서로 통신을 하려면 IPC(Inter Process Communication)를 이용해야하는데 이는 통신의 비용이 상대적으로 많이 들어. 그래서 쓰레드라는 걸 고안하게 된거야!쓰레드는 프로세스 내에 존재하는 것으로 1개 이상이 있을 수 있어.한 프로세스 내의 쓰레드들은 그 프로세스의 PCB, 코드, 데이터, 힙영역을 공유해.스택은 공유하지 않고 쓰레드마다 하나씩 가지고있어.프로세스 내에 쓰레드가 여러개 있으니 이 쓰레드들을 구분해줘야겠지?그래서 쓰레드 ID도 부여하고 이 쓰레드를 관리하기위한 TCB(Thread Control Block)이 생겼어.이제 운영체제 관점에서 쓰레드도 구분이 가능해진거지. 이제 운영체제가 작업을 처리하는 단위는 프로세스 내의 쓰레드야~웹 브라우저를 실행하면 프로세스 하나가 생성되고 쓰레드도 하나 생성돼.탭을 하나 더 추가하면 쓰레드를 하나 더 생성하게되는거지. 각각의 장단점을 알아보자면안정성프로세스는 각각 독립적이기때문에 다른 프로세스가 영향을 받지 않아.반면 쓰레드는 해당 프로세스에 문제가 생기면 그 안의 모든 쓰레드에 문제가 생기게되지.그러므로 안정성 측면에서는 프로세스 방식이 쓰레드 방식보다 더 우수해.속도와 자원각각의 프로세스는 서로 고유한 자원을 가지고 있어. 코드, 데이터, 힙, 스택영역을 전부 따로두고있고 프로세스간의 통신을 하려면 IPC를 이용해야해서 오버헤드가 크고 속도가 느려.반면 쓰레드는 한 프로세스 내에서 스택영역을 제외하고 모두 공유하고있기때문에 오버헤드가 굉장히 작아. 쓰레드 간의 데이터 공유는 매우 쉽게할 수 있지만 공유되는 공간에서 문제가 생길 수 있어. (이 문제는 나중에 "프로세스 동기화"에서 알아보자.) 참조 : 그림으로 쉽게 배우는 운영체제 3주차 회고칭찬하고 싶은 점 : 기한을 지켰다 😅아쉬웠던 점 : 권장 커리큘럼을 지키지 못했다.

미션 3

운영체제메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.RAM (Random Access Memory): 주기억장치로, 실행 중인 프로그램과 데이터를 일시적으로 저장하는 메모리입니다. 전원이 꺼지면 저장된 데이터가 사라지는 휘발성 메모리입니다.ROM (Read-Only Memory): 비휘발성 메모리로, 데이터를 읽을 수만 있고, 수정은 불가능합니다. 주로 컴퓨터 부팅에 필요한 기본적인 데이터를 저장합니다.캐시 메모리: CPU와 RAM 사이에 위치한 고속 메모리로, 자주 사용되는 데이터를 빠르게 접근할 수 있게 해줍니다. 속도가 빠르지만 용량이 작습니다.가상 메모리: 실제 물리 메모리보다 더 많은 메모리를 사용할 수 있도록 보조기억장치(HDD, SSD)의 일부를 메모리처럼 사용하는 기술입니다.2. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?베이스 레지스터(Base Register): 사용자 프로세스의 메모리 접근을 관리하며, 프로세스가 사용할 수 있는 메모리 영역의 시작 주소를 저장합니다.한계 레지스터(Limit Register): 사용자 프로세스가 사용할 수 있는 메모리 영역의 끝 주소를 저장하여, 프로세스가 할당된 영역을 넘지 못하게 방지합니다.메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?고정 분할 방식 (Fixed Partitioning)장점: 구현이 간단하며, 메모리 관리의 오버헤드가 적습니다.단점: 고정된 크기의 메모리 분할로 인해 내부 단편화(메모리 낭비)가 발생할 수 있습니다. 미리 분할된 크기가 비효율적일 수 있습니다.가변 분할 방식 (Dynamic Partitioning)장점: 프로세스의 크기에 맞춰 메모리를 동적으로 할당하므로 내부 단편화를 줄일 수 있습니다.단점: 외부 단편화가 발생할 수 있으며, 메모리 할당 및 해제 시 관리 비용이 증가합니다. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱(Thrashing): CPU 사용률을 높이기 위해 많은 프로그램을 동시에 실행하지만, 실제로 메모리 부족으로 인해 스왑이 과도하게 발생하고, CPU가 거의 사용되지 않는 현상을 말합니다. 이는 시스템 성능을 크게 저하시킵니다.HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?필요함: HDD나 SSD는 운영체제, 프로그램, 데이터가 저장되는 비휘발성 저장장치입니다. 컴퓨터를 실행하기 위해 운영체제와 필수 파일들을 읽어야 하므로, HDD나 SSD가 없으면 컴퓨터를 부팅하거나 정상적으로 작동할 수 없습니다.이유: RAM은 휘발성 메모리로 전원이 꺼지면 데이터가 사라지기 때문에, 비휘발성 메모리인 HDD나 SSD에 데이터를 영구적으로 저장할 수 있어야 컴퓨터가 데이터를 유지하고 부팅할 수 있습니다. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일을 삭제해도, 실제 데이터는 저장 장치에 그대로 남아있고, 파일 시스템에서는 해당 파일의 위치 정보만 지워집니다. 이 때문에 데이터가 덮어쓰기 되기 전까지는 복구 소프트웨어나 포렌식 기술로 파일을 복구할 수 있습니다.자료구조와 알고리즘지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬 (Bubble Sort)장점: 구현이 매우 쉽고, 적은 양의 데이터를 처리할 때는 효율적일 수 있습니다.단점: 모든 데이터에 대해 계속해서 비교하고 교환해야 하므로 매우 비효율적입니다.시간 복잡도: O(n²)삽입 정렬 (Insertion Sort)장점: 거의 정렬된 데이터에 대해서는 매우 효율적이며, 추가 메모리가 필요하지 않습니다.단점: 데이터의 양이 많을 경우 비효율적입니다.시간 복잡도: O(n²)병합 정렬 (Merge Sort)장점: 안정적인 정렬이며, 큰 데이터를 다룰 때도 효율적입니다. 분할 정복 기법을 사용합니다.단점: 추가적인 메모리 공간이 필요하며, 재귀적으로 호출하므로 스택 오버플로우 가능성이 있습니다.시간 복잡도: O(n log n)퀵 정렬 (Quick Sort)장점: 평균적으로 매우 빠른 정렬 알고리즘으로, 실무에서 가장 많이 사용됩니다.단점: 최악의 경우 시간 복잡도가 O(n²)가 될 수 있으며, 재귀 호출로 인한 스택 오버플로우가 발생할 수 있습니다.시간 복잡도: 평균 O(n log n), 최악 O(n²)선택 정렬 (Selection Sort)장점: 추가 메모리가 필요하지 않으며, 작은 데이터를 정렬할 때 적합합니다.단점: 비효율적이며, 데이터를 많이 교환해야 합니다.시간 복잡도: O(n²) 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.타뷸레이션(Tabulation): 메모리가 부족한 시스템에서는 일반적으로 타뷸레이션을 선택하는 것이 더 효율적입니다. 이유는 메모이제이션이 재귀를 사용하는 반면, 타뷸레이션은 반복을 사용하여 불필요한 재귀 호출을 방지하고, 추가적인 메모리 소비를 줄일 수 있기 때문입니다.

알고리즘

*이 내용은 인프런 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)을 수강하며 정리한 내용입니다. 재귀(recursion)재귀는 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻해. 그러므로 재귀함수는 탈출 조건, 즉 기저 조건이 반드시 있어야 해.콜스택함수가 호출되면서 올라가는 메모리 영역으로 스택이라고도 불러. FILO의 특징을 띄고있어.상향식 계산 vs 하향식 계산재귀를 이용한 상향식 계산하지만 재귀는 하향식 계산일 때 위력을 발휘해!하노이 탑function hanoi(count, from, to, temp){ if(count == 0) return; hanoi(count - 1, from, temp, to); console.log(`${count} ${from} -> ${to}`); hanoi(count - 1, temp, to, from); } hanoi(3, "A", "C", "B"); 정렬버블정렬데이터를 옆 데이터와 비교하는 정렬이야.function BubbleSort(arr){ for(let i = 0; i arr[j + 1]){ // j, j+1 비교 let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }성능위와 같으므로 빅 오는 O(n**2)이 돼!성능이 중요한 시스템을 만드려면 버블 정렬은 어려울 수도 있어...장점 : 이해와 구현이 간단함단점 : 성능이 좋지 않음선택 정렬배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 뭔소로 가져오는 정렬이야.function SelectionSort(arr){ for(let i = 0; i 성능 버블정렬과 동일해! 즉 선택 정렬의 정렬도 O(n**2)이야.장점 : 이해와 구현이 간단함단점 : 성능이 좋지 않음 삽입정렬정렬되지 않은 영역의 데이터를 정렬된 영역에 끼워 넣는 정렬방식이야. 정렬된 영역을 뒤에서부터 역순으로 비교해.function InsertionSort(arr){ for(let i = 1; i = 0; j--){ if(arr[j] > insertingData){ arr[j + 1] = arr[j]; }else{ break; } } arr[j + 1] = insertingData; } } 성능 :위 정렬들과 마찬가지고 O(n**2)이야.장점 : 이해와 구현이 간단함단점 : 성능이 좋지 않음병합정렬분할 정복 알고리즘이야.숫자 하나가 들어있는 배열로 만들어주었으면 두 배열을 순서에 맞게 정렬한 후 두개의 숫자가 들어있는 배열 하나로 만들어 줘.이런식으로~같은 방식으로 이렇게 배열해주면 돼.function MergeSort(arr, leftIndex, rightIndex){ if(leftIndex midIndex){ for(let i = rightAreaIndex; i 성능하나의 데이터와 하나의 데이터가 하나로 합쳐질 때 비교 연산을 두 번 해.마찬가지로 두개의 데이터와 두개의 데이터가 하나로 합쳐질 때에는 비교가 네번 이루어져.각 단계를 거칠 때마다 영역의 수가 반으로 줄기 때문에 log(n)으로 말할 수 있어.분할된 배열을 병합할 때는 n개의 데이터를 n번 비교하므로n과 log(n)을 곱해서 O(nlogn)이야.장점 : 성능이 좋음단점 : 이해와 구현이 어려움퀵정렬병합정렬과 마찬가지고 분할 정복 알고리즘이야.우선 pivot을 랜덤으로 설정해.leftStartIndex는 오른쪽으로 이동하다가 피벗보다 큰 값을 만나면 멈춰.rightStartIndex는 왼쪽으로 이동하다가 피벗보다 작은 값을 만나면 멈춰.그리고 두 값을 swap 해.계속 반복하다가 서로 지나치게 되면 rightStartIndex와 pivot을 swap해줘.이렇게되면 pivot를 기준으로 왼쪽은 모두 pivot보다 작은 값이 위치하고, 오른쪽은 모두 pivot보다 큰 값이 위치하게 돼.이를 반복하면 되는거지!quickSortfunction quickSort(arr, left, right){ if(left dividefunction divide(arr, left, right){ // 정렬 let pivot = arr[left]; let leftStartIndex = left + 1; let rightStartIndex = right; while(leftStartIndex = arr[leftStartIndex]){ leftStartIndex++; } while(rightStartIndex >= (left + 1) && pivot swapfunction swap(arr, index1, index2){ let temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; } 성능데이터가 한 개가 될 떄까지 반으로 나누므로 log(n)!이 작업을 데이터 n개만큼 반복해야하므로 n을 곱함!보통 최악의 pivot을 선택하는 경우는 드물기때문에 평균 성능인 nlogn으로 표시해.퀵 정렬의 장단점은 병합 정렬과 동일해. 병합 정렬이 더 좋아보이지만 실제로 퀵 정렬이 더 좋게 평가돼. 동적 프로그래밍메모이제이션피보나치 수열을 구현할 때 재귀함수를 이용하게되면 위 사진처럼 중복되는 호출이 많아. 그럼 중복되는 계산 결과를 저장하고, 같은 계산이 필요할 때 저장도니 결과를 사용하면 더 좋겠지?그렇게되면 함수의 호출 수가 줄어들게되고 성능이 향상될거야.이를 메모이제이션이라고 해.그럼 어떤 자료구조를 사용하면 될까? 바로 해시 테이블이야.빠른 데이터 탐색, 삽입, 삭제가 가능하기 때문이지!해시 테이블의 key로 계산하려는 값을, value로 계산 결과를 저장하면 검색을 빠르게 할 수 있을거야.자바스크립트 객체 또한 해시테이블이므로 이를 이용하여 코드를 작성해볼게.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]; }이러면 실행 속도가 훨씬 빨라져.타뷸레이션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]; } 참조 : 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 3주차 회고칭찬하고 싶은 점 : 기한을 지켰다 😅아쉬웠던 점 : 권장 커리큘럼을 지키지 못했다.

자료구조

*이 내용은 인프런 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)을 수강하며 정리한 내용입니다. 덱데이터의 삽입과 제거를 head와 tail 두군데서 자유롭게 할 수 있어.덱의 추상자료형printAll - 모든 데이터 출력addFirst - head에 데이터 삽입removeFirst - head에서 데이터 제거addLast - tail에 데이터 삽입removeLast - tail에서 데이터 제거isEmpty - 리스트 비었는지 체크구현DoublyLinkedList.mjs를 import 해줘.class Deque{ constructor(){ this.list = new DoublyLinkedList(); } printAll(){ this.list.printAll(); } addFirst(data){ this.list.insertAt(0, data); } removeFirst(){ return this.list.deleteAt(0); } addLast(data){ this.list.insertAt(this.list.count, data); } removeLast(){ return this.list.deleteLast(); } isEmpty(){ return (this.list.count == 0); } }해시테이블해시(Hash), 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary)라고도 불려.해시 테이블은 이름에서도 알 수 있듯이 해시와 테이블이 합쳐진 자료구조야.해시 함수Key만 알면 Value에 O(1)의 성능으로 읽기가 가능하다!하지만 동일한 Key에 많은 Value를 집어넣는다면 많은 연결리스트를 뒤져야해.그러므로 데이터를 골고루 분배하는 것이 중요해!!장점 : 빠른 데이터 읽기, 삽입, 삭제단점 : 메모리를 많이 차지함, 좋은 해시 함수의 구현이 필수적!추상자료형set - 데이터 삽입get - 데이터 읽기remove - 데이터 제거 구현구현하기 전 hash 함수를 어떻게 만들거냐면~위와같은 형식으로 10으로 나눈 나머지의 인덱스에 값을 삽입할거야!HashDataclass HashData{ constructor(key, value){ this.key = key; this.value = value; } }HashTableclass HashTable{ constructor(){ this.arr = []; for(let i = 0; i Set데이터의 중복을 허용하지 않는 자료구조야. 셋은 해시 테이블을 이용해.해시 테이블의 value 값은 사용하지 않고 key만 사용해서 구현해!!추상자료형add(data) - 데이터 삽입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); // value는 쓰이지 않기때문에 그냥 -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 참조 : 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 3주차 회고칭찬하고 싶은 점 : 기한을 지켰다 😅아쉬웠던 점 : 권장 커리큘럼을 지키지 못했다.

CS 미션 2

1. FIFO 스케줄링의 장단점은 무엇인가요?답변:장점: 구현이 매우 간단하며, 프로세스가 도착한 순서대로 처리되므로 공정성이 보장됨.단점: 긴 작업이 먼저 도착하면 뒤에 있는 짧은 작업들이 오래 기다리는 Convoy Effect가 발생할 수 있으며, 대기 시간이 길어져 비효율적일 수 있음.2. SJF(Shortest Job First)를 사용하기 어려운 이유는 무엇인가요?답변:SJF는 프로세스의 실행 시간을 미리 알아야 하는데, 실제로 프로세스가 얼마나 걸릴지 정확히 예측하기 어렵기 때문에 사용이 까다로움. 또한, 선점형이 아닌 경우 긴 작업이 먼저 실행되면 짧은 작업이 뒤로 밀리게 되어 성능 저하가 발생할 수 있음.3. RR(Round Robin) 스케줄링에서 타임 슬라이스가 너무 작으면 어떤 문제가 발생하나요?답변:타임 슬라이스가 너무 작으면 Context Switching이 너무 자주 발생하여, CPU가 프로세스 교체에 많은 시간을 사용하게 됨. 이로 인해 실제 작업 처리보다 스위칭 비용이 커져서 성능이 저하되고 처리율이 낮아질 수 있음.4. MLFQ(Multi-Level Feedback Queue)에서 CPU Bound와 I/O Bound 프로세스를 어떻게 구분하나요?답변:MLFQ는 I/O Bound 프로세스가 CPU를 짧게 사용하고 자주 입출력을 요청하는 특성으로 인해 높은 우선순위를 부여하며, CPU Bound 프로세스는 CPU를 오래 사용하므로 점차 우선순위가 낮아져 더 낮은 큐로 이동함.5. 공유 자원이란 무엇인가요?답변:공유 자원은 여러 프로세스나 쓰레드가 동시에 접근하여 사용할 수 있는 자원으로, 대표적으로 메모리, 파일, 프린터 등이 있음. 여러 프로세스가 동시에 접근할 경우 자원 충돌 문제가 발생할 수 있어 동기화가 필요함.6. 교착 상태(Deadlock)에 빠질 수 있는 조건은 무엇인가요?답변:교착 상태가 발생하려면 다음 네 가지 조건을 모두 충족해야 함:상호 배제: 자원이 한번에 하나의 프로세스만 사용할 수 있음.점유와 대기: 자원을 점유한 상태에서 다른 자원을 기다림.비선점: 자원을 강제로 뺏을 수 없음.순환 대기: 자원이 순환적으로 대기 상태에 있음.자료구조와 알고리즘 문제7. 재귀 함수에서 기저 조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생하나요?답변:기저 조건이 없으면 재귀 함수가 끝없이 호출되어 무한 재귀가 발생함. 이로 인해 스택 메모리가 가득 차면서 Stack Overflow가 발생할 수 있고, 시스템이 비정상 종료될 수 있음.8. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 작성하세요.javascript코드 복사function sumOdd(n) { // 기저 조건: n이 0보다 작으면 0을 반환 if (n 답변:이 재귀 함수는 0부터 n까지의 홀수 합을 계산함. n이 홀수일 경우, 그 값을 더한 후 n-2에 대해 다시 재귀 호출을 하며, 짝수일 경우에는 다음 홀수를 계산하기 위해 n-1을 호출함.

운영체제

*이 내용은 인프런 그림으로 쉽게 배우는 운영체제를 수강하며 정리한 내용입니다. 인터럽트## 인터럽트- 정의: CPU가 현재 실행 중인 작업을 중단하고, 외부 또는 내부에서 발생한 중요한 이벤트를 처리하기 위해 호출되는 신호. 인터럽트는 현재 작업을 일시적으로 멈추고, 급한 작업을 먼저 처리한 후 다시 원래 작업으로 돌아오게 함.- 종류: - 하드웨어 인터럽트: 키보드 입력, 마우스 클릭, 타이머 등 하드웨어에서 발생하는 인터럽트. - 소프트웨어 인터럽트: 프로그램 내에서 오류가 발생하거나 시스템 호출 시 발생하는 인터럽트.- 역할: CPU가 매번 직접 확인하지 않아도 중요한 사건이 발생하면 즉시 대응할 수 있게 해줌. 멀티태스킹 환경에서 필수적임.## 프로세스- 정의: 실행 중인 프로그램의 인스턴스. CPU에서 독립적으로 실행되는 기본적인 실행 단위로, 운영체제가 프로세스를 관리하고 스케줄링함.- 특징: - 각각 고유의 메모리 공간(코드, 데이터, 스택 등)을 가지고 있으며, 다른 프로세스와 메모리를 공유하지 않음. - 운영체제는 프로세스 상태(생성, 준비, 실행, 대기, 종료)를 관리하며, CPU가 하나의 프로세스를 실행 중일 때 다른 프로세스는 대기 상태로 전환될 수 있음.- 프로세스 상태: - 생성: 프로세스가 생성되고 운영체제에 등록됨. - 준비: CPU가 할당되기를 기다리는 상태. - 실행: 프로세스가 CPU를 할당받아 명령을 실행하는 상태. - 대기: 입출력 등의 이유로 잠시 멈춰 있는 상태. - 종료: 프로세스가 실행을 마치고 종료된 상태.## 쓰레드- 정의: 프로세스 내에서 실행되는 가벼운 실행 단위. 하나의 프로세스는 여러 개의 쓰레드를 가질 수 있으며, 각 쓰레드는 독립적으로 실행됨.- 특징: - 같은 프로세스 내의 다른 쓰레드와 메모리를 공유하므로, 프로세스보다 가벼운 자원을 사용함. - 쓰레드는 CPU를 효율적으로 사용하여 병렬 처리(멀티스레딩)를 가능하게 함. - 그러나 메모리를 공유하기 때문에, 동기화 문제(공유 자원 접근 충돌)가 발생할 수 있음.- 장점: 메모리 공간을 적게 사용하면서 병렬 처리 성능을 높일 수 있음. 또한 쓰레드 간 통신이 빠름.- 단점: 공유 메모리를 사용할 때 동기화 문제를 해결하지 않으면 데이터 일관성 문제가 발생할 수 있음. 참조 : 그림으로 쉽게 배우는 운영체제 2주차 회고칭찬하고 싶은 점 : 기한을 지켰다 😅아쉬웠던 점 : 권장 커리큘럼을 지키지 못했다.다음 주에는 권장 커리큘럼을 지켜 수강하는 것이 목표입니다!

자료구조

*이 내용은 인프런 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)을 수강하며 정리한 내용입니다. Linked List 구현 (JS)추상자료형어떠한 데이터와 그 데이터에 대한 연산을 표기하는 것이야. 연결리스트의 추상자료형모든 데이터 출력 - printAll()모든 데이터 제거 - clear()인덱스 삽입 - insertAt(index, data); 마지막 삽입 - insertLast(data); 인덱스 삭제 - deleteAt(index);마지막 삭제 - deleteLast();인덱스 읽기 - getNodeAt(index); 구현이제 위 추상자료형을 바탕으로 구현을 해보자.연결리스트는 데이터를 담은 노드를 서로 연결하는 구조야. 이를 위해서 가장 먼저 만들어야하는 것은 노드겠지?노드 class Node{ // 생성자의 매개변수로 data, next를 만들어준다. // 매개변수 data는 필수이지만, // next는 입력하지 않는다면 null이 할당된다. constructor(data, next = null){ this.data = data; this.next = next; } } 아래와 같이 자기 참조 변수를 만들어준 후 추상자료형에서 나열한 함수들을 만들어볼게.class LinkedList{ constructor(){ this.head = null; // 연결리스트의 시작 노드 this.count = 0; // 총 저장된 노드의 수 }insertAt(index, data);insertAt(index, data){ // 예외 처리 if(index > this.count || index printAll()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()clear(){ this.head = null; this.count = 0; }insertLast(data); insertLast(data){ // insertAt(index, data) this.insertAt(this.count, data); }deleteAt(index);deleteAt(index){ // 예외 처리 if(index >= this.count || index deleteLast();deleteLast(){ return this.deleteAt(this.count - 1); }getNodeAt(index);getNodeAt(index){ // 예외 처리 if(index >= this.count || index 스택FILO의 리스트 형태야. ctrl+z를 구현할 때 스택이 사용되지!FILO의 조건만 충족한다면 어떤 자료구조로 구현하던지 상관없어.즉, 배열이나 연결리스트 각각으로 스택을 구현할 수 있어. 지금은 만들어놓은 연결리스트로 스택을 구현해볼게.새로 들어온 노드를 head로 지정해주면 돼. 스택의 추상자료형push - 데이터 삽입pop - 데이터 제거peek - 데이터 참조isEmpty - 비었는지 체크 구현class Stack{ constructor(){ this.list = new LinkedList(); } push(data){ // 0 인덱스에 data 삽입 this.list.insertAt(0, data); } pop(){ try{ return this.list.deleteAt(0); } catch(e){ // 빈 리스트 지울 경우 return null; } } peek(){ return this.list.getNodeAt(0); } isEmpty(){ return (this.list.count == 0); } }큐FIFO의 형태야. 마찬가지로 연결리스트로 구현해보자.이번에도 삽입하는 노드를 head로 지정하는 대신, 삭제하기 쉽도록 tail 이라는 변수를 하나 더 만들어서 가장 처음 삽입한 노드를 가리키도록 하자.이렇게했을때 처음 삽입한 노드를 삭제하게되면 tail은 전 노드를 가리켜야해.하지만 우리는 단방향 연결리스트를 구현했기 때문에 전 노드를 알 수 없어. 즉, 이중연결리스트로 수정해야해! 큐의 추상자료형enqueue - 데이터 삽입dequeue - 데이터 제거front - 데이터 참조isEmpty - 비었는지 확인DoublyLinkedList.mjsnode 수정 class Node{ constructor(data, next = null, prev = null){ this.data = data; this.next = next; this.prev = prev; // 이전 노드 추가 } }프로퍼티 추가class DoublyLinkedList{ constructor(){ this.head = null; this.tail = null; // tail 추가 this.count = 0; }insertAt(index, data) 수정데이터가 삽입될 때 이전 노드를 가리키는 코드를 추가하자.insertAt(index, data){ if(index > this.count || index deleteAt(index) 수정deleteAt(index){ if(index >= this.count || index Queue.mjsclass Queue{ constructor(){ this.list = new DoublyLinkedList(); } enqueue(data){ // 데이터 삽입 this.list.insertAt(0, data); } dequeue(){ // 데이터 제거 try{ return this.list.deleteLast(); } catch(e){ return null; } } front(){ // 데이터 참조 return this.list.tail; } isEmpty(){ // 비었는지 확인 return (this.list.count == 0); } } 참조 : 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 2주차 회고칭찬하고 싶은 점 : 기한을 지켰다 😅아쉬웠던 점 : 권장 커리큘럼을 지키지 못했다.다음 주에는 권장 커리큘럼을 지켜 수강하는 것이 목표입니다!

운영체제

*이 내용은 인프런 그림으로 쉽게 배우는 운영체제를 수강하며 정리한 내용입니다. 운영 체제의 구조운영 체제의 핵심은 커널이야.커널은 프로세스와 메모리, 저장장치를 관리하는 핵심적인 기능을 담당해.사용자는 운영 체제의 커널에 직접 접근할 수 없고, 인터페이스를 통해서 접근할 수 있어.인터페이스는 GUI, CLI로 나눌 수 있어. 이 두가지는 텍스트냐, 이미지냐의 차이이지 커널에 접근하기 위한 목적은 같아!GUI -> 이미지로 커널과 상호작용 ( ex. mac, window )CLI -> 텍스트로 커널과 상호작용 ( ex. 리눅스 )커널은 사용자로부터 자신을 보호하기 위한 시스템 콜이라는 인터페이스를 갖고있어.시스템 콜 없이 애플리케이션이 하드디스크에 접근하게되면 중요한 정보를 덮어쓸 수 있어...시스템 콜을 이용하면 자동으로 빈 공간에 저장하도록 해줘 ( 복잡하네😅 ) 사용자, 애플리케이션은 커널과의 인터페이스로 시스템 콜을 사용한다고 했는데,하드웨어와 커널과의 인터페이스로는 드라이버를 사용해...! 컴퓨터 하드웨어와 구조대부분이 폰 노이만 구조를 하고있어.CPU와 메모리를 두는 구조로, 배선을 바꾸는 대신 소프트웨어만 바꿔주면 되므로 편해졌어!CPU와 메모리를 연결하는 버스를 통해 명령어를 읽고, 데이터를 읽고 써. 컴퓨터 하드웨어에는 메인보드가 있어. 메인보드는 다른 하드웨어를 연결하는 장치야. 마우스 키보드 등등...장치 간에 데이터를 전송하는 건 메인보드의 버스가 담당해.CPU와 메모리를 메인보드에 꽂아줘. ( 폰 노이만 구조니까~ )하드디스크 연결 단자에는 하드디스크를 꽂아주면 돼. 마찬가지로 그래픽카드 연결 단자에는 그래픽 카드를 꽂아줘.출력 단자의 모니터 선을 꽂으면 모니터가 작동하게 돼. CPU 구조Central Processing Unit의 약자로, 중앙 처리 장치라고 불려.산술논리 연산장치 ( Arithmetic and Logic Unit, ALU ) : 데이터 연산 담당제어 장치 ( Control Unit ) : 모든 장치들의 동작을 지시하고 제어하는 장치레지스터 : 계산을 위해 임시로 보관하는 장치 메모리 종류RAM ( Random Access Memory )랜덤으로 데이터를 읽어도 저장된 위치와 상관없이 읽는 속도가 같아.전력이 끊기면 데이터를 읽어버리기 때문에 메인 메모리로 사용돼.ROM ( Read Only Memory )전력이 끊겨도 데이터를 보관할 수 있지만, 데이터를 한번 쓰면 수정할 수 없어.컴퓨터의 부팅과 관련된 바이오스를 저장하는데 주로 사용돼. 컴퓨터의 부팅과정컴퓨터의 전원을 누른다.ROM에 저장된 바이오스가 실행된다. ( 바이오스: 전원, CPU, 메모리, 키보드, 하드디스크 등 주요 하드웨어에 이상이 없는지 확인해. )이상이 없다면 하드디스크에 있는 마스터 부트 레코드에 저장된 부트로더를 메모리로 가져와서 바이오스가 실행한다.만약 윈도우즈 운영체제와 리눅스 운영체제가 둘 다 설치되어있는 컴퓨터라면 어떤 운영체제를 실행할지 선택하는 화면이 나온다.운영 체제를 메모리로 불러오고 모니터에 바탕화면이 보이게 된다.이제부터 실행되는 모든 응용 프로그램은 메모리에 올라와서 운영체제가 관리한다. 인터럽트CPU가 입출력 장치에 데이터를 읽거나 쓰려고 하는 상황을 생각해보자.CPU는 입출력 작업이 들어오면 입출력 관리자에게 입출력 명령을 내려.CPU 관점에서는 입출력 명령이 언제 완료될지 알 수 없기 때문에 주기적으로 확인해줘야해!!이러한 방식을 폴링(Polling) 방식이라고 해☺폴링 방식의 단점은 주기적으로 CPU가 확인해줘야하니 성능이 좋지 않다는 점이야. 인터럽트는 폴링 방식의 단점을 해결한 방식이야.CPU가 입출력 관리자에게 입출력 명령을 내리고 자기는 다른 일을 해.입출력 관리자는 입출력 명령이 완료되었을 때 CPU에게 신호를 주고, CPU는 그 신호를 받아서 ISR(Interrupt Service Routine)을 실행시켜 작업을 완료해.ISR은 특정 인터럽트가 들어오면 그 인터럽트를 처리하는 방식이야.인터럽트는 비동기적으로 작동하기 때문에 성능에 이점이 있어.하드웨어 인터럽트 ( ex. 입출력 )소프트웨어 인터럽트 ( ex. 유효하지 않은 메모리 접근 ) 참조 : 그림으로 쉽게 배우는 운영체제 1주차 회고칭찬하고 싶은 점 : 기한을 지켰다 😅아쉬웠던 점 : 권장 커리큘럼을 지키지 못했다.다음 주에는 권장 커리큘럼을 지켜 수강하는 것이 목표입니다!

CS 미션

운영체제1.while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?인터럽트 프로그램과 프로세스가 어떻게 다른가요?프로그램: 실행 가능한 코드, 즉 명령어들의 집합입니다. 디스크에 저장된 정적인 상태입니다.프로세스: 실행 중인 프로그램을 의미하며, 운영체제에 의해 관리되는 동적인 개체입니다. 프로그램이 메모리 상에서 실행되면 프로세스가 됩니다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍: 여러 프로그램이 메모리에 적재되어 있는 상태에서, CPU가 이들 프로그램을 번갈아가며 실행하는 방식입니다. CPU는 항상 바쁘게 작업을 처리하게 됩니다.멀티프로세싱: 여러 CPU를 사용하여 여러 프로그램을 동시에 실행하는 방식입니다. 여러 프로세서(혹은 코어)를 사용하여 작업을 병렬 처리할 수 있습니다. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?PCB 컨텍스트 스위칭이란 뭔가요? CPU가 현재 실행 중인 프로세스의 상태(레지스터, 프로그램 카운터, 스택 등)를 저장하고, 다음 프로세스를 실행하기 위해 해당 프로세스의 상태를 복원하는 작업 자료구조와 알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.해시맵(HashMap)을 선택할 수 있습니다. 해시맵은 키-값 쌍으로 데이터를 저장하며, 학생의 학번이나 이름을 키로 사용하고, 그에 대한 정보를 값으로 저장할 수 있습니다. 해시맵은 평균적으로 O(1)의 시간 복잡도로 빠르게 검색할 수 있어, 많은 학생 정보에 대한 접근이 효율적입니다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.큐(Queue)를 선택할 수 있습니다. 큐는 선입선출(FIFO, First In First Out) 방식으로 데이터를 처리하는 자료구조입니다. 주문은 들어온 순서대로 처리해야 하므로, 큐를 사용하면 가장 먼저 들어온 주문을 가장 먼저 처리할 수 있습니다.

자료구조

*이 내용은 인프런 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)을 수강하며 정리한 내용입니다. 프로그램자료구조와 알고리즘으로 이루어져있어.실력이 있는 사람은 적절한 자료구조를 선택해 적절한 알고리즘으로 원하는 결과를 얻지. 시간복잡도특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간이야.하지만 각자의 컴퓨터 성능에 따라 해결하는 시간이 달라지겠지?!그럼 코드에서 성능에 가장 많은 영향을 주는 부분은 어떤 것일까?바로 반복문이야. 따라서 해당 알고리즘의 반복문을 보고 성능을 평가해 😀예를 들어볼게!arr = [1, 4, 3, 6]위와 같은 배열이 있을 때, 3을 찾는 알고리즘을 구상한다고 해보자.그럼 반복문을 통해 배열을 전체 탐색해보면 되겠지?이렇게되면 3의 위치에따라 시간복잡도가 달라질거야...위와 같은 경우때문에 세가지 경우로 시간복잡도를 나눠.Big-Ω : 최선의 경우 한번에 찾음Big-O : 최악의 경우 배열의 길이만큼 걸림Big-Θ : 평균의 경우 배열의 길이 중간만큼 걸림 Big-O보통 Big-O를 사용해. 위와 같은 경우에는 Big-O가 배열의 길이인 4가 되겠지?즉 O(n) = n 이 되는 경우야.O(n)같은 경우는 입력이 많아질수록 계산량이 많아져. 이를 선형시간 알고리즘이라고 해.O(1)은 상수시간 알고리즘이라고 해. 입력의 크기와 상관없이 상수의 시간이 걸린다는 뜻이야.입력의 크기와 상관없이 100번의 시간이 걸린다고 해도 O(1)으로 표기해!그 외에도 여러 알고리즘이 있어.O( 1 ) > O( log(n) ) > O( n ) > O( nlog(n) ) > O( n**2 ) > O( 2**n ) > O( n! )오른쪽으로 갈수록 성능이 좋지 않아. 만약 n**2 + 2n + 100의 성능을 보이는 알고리즘이 있다면가장 영향을 많이 미치는 n**2만 남기면 돼. 즉 O(n**2)이야.3n**2 + 100이라면?O(3n**2)?맞아.하지만 상수는 큰 의미가 없으므로 O(n**2)으로 표기하면 돼. 배열배열은 값을 접근하고 읽는데에 O(1)만큼의 시간이 걸리므로 접근에는 용이하지만,데이터를 추가하고 제거하는데에는 내부적으로 필요한 단계가 많이 들기때문에, 성능이 좋지 않아.또한 미리 공간을 할당하기 때문에 낭비되는 공간이 존재할 수 있다는 단점이 있어!하지만 일반적인 배열과는 다르게 자바스크립트에서의 배열은 불연속적으로 값을 할당해. Linked List일반적인 배열의 단점을 보완하려면 어떻게 하면 좋을까?바로 저장하려는 데이터들을 메모리 공간에 분산해 할당하고, 이 데이터들을 연결하면 돼.위 행위는 노드(node)라는 것을 만들어 수행해.노드는 데이터를 담는 변수, 다음 노드를 가리키는 변수 하나를 갖고있어.첫 노드의 주소만 알고있다면, 모든 노드에 접근할 수 있어.이를 Linked list라고 해.장점으로는 배열처럼 초기 크기를 알아야한다는 단점이 없어!또한 중간에 데이터를 삽입하려면, 다음을 가리키는 변수만 바꿔주면되기때문에 간단하다는 장점도 있어.단점으로는 데이터 참조가 O(n)의 성능을 가진다는 거야. 배열 vs Linked List 참조 : 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 1주차 회고칭찬하고 싶은 점 : 기한을 지켰다 😅아쉬웠던 점 : 권장 커리큘럼을 지키지 못했다.다음 주에는 권장 커리큘럼을 지켜 수강하는 것이 목표입니다!