블로그 모아보기 - 인프런

[인프런 워밍업클럽 CS 2기] 2주차 발자국

1. 전반적인 학습내용CPU 스케줄링 알고리즘(FIFO, SJF, RR, MLFQ), 프로세스 간 동기화(공유자원 등), 데드락과 메모리,그리고 알고리즘에서 재귀 내용과 정렬 등을 학습했다. 2. 일주일 간의 회고핑계를 대보자면 이번주는 좀 너무 정신없는 일이 많아서 강의를 날별로 규칙적으로 듣지는 못 했다.. 몰아서 듣다보니까 생각보다 이해할 때 더뎌지는 걸 느껴서 좀 놀랬다. 근데 운영체제랑 자료구조를 같이 공부하니까 몰아서 듣더라도 예전에 혼자 공부할 때보다, 처음 개발 공부를 시작할 때보다 이해가 더 수월하게 되는 것 같아서 너무 좋았다. 스터디가 끝나고 두 세번 더 각 강의를 돌려서 들어야 할 것 같다. 익숙해질 때까지 여러 번에 걸쳐서 복습이 필요할 듯 하다. 3. 다음주 목표2주동안 배운 내용 총정리 한번 하기, 알고리즘 연습 시작해 보기, 강의 밀리지 말자 .. ^00^

1

인프런 워밍업 클럽 스터디 2기 - CS 2주차 미션

운영체제1. FIFO 스케줄링의 장단점이 뭔가요?장점 : 단순하고 직관적단점 : 실행시간에 따라 프로세스 대기시간이 길어질 수 있고, I/O 작업으로 인해 CPU 사용률이 떨어짐 2. SJF를 사용하기 여러운 이유가 뭔가요?프로세스 종료시간을 예측하기 어려움Burst Time이 긴 프로세스는 오래 대기할 수 있음 3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?컨텍스트 스위칭이 많이 발생하게 되므로 오버헤드가 커짐 4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?타임 슬라이스 크기를 오버해서 강제로 CPU를 뺏기는지 아니면 시간 내에 끝나서 스스로 반납하는지를 보고 구분할 수 있음 CPU를 뺏긴다면 CPU Bound Process일 확률이 높고, 스스로 반납한다면 I/O Bound Process일 확률이 높음 5. 공유자원이란 무엇인가요?프로세스 간 공동으로 사용하는 자원 6. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호배제비선점점유와 대기원형 대기자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?콜스택이 가득 차서 종료될 수 있음 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ if(n <= 1) return n; // 재귀 로직 if(n % 2 == 1) { return sumOdd(n - 2) + n; } return sumOdd(n - 1); } console.log(sumOdd(10)) // 25

1

워밍업 클럽 CS 2주차 발자국 : 자료구조와 알고리즘

알고리즘재귀 (Recursion)재귀란, 어떤 대상을 정의할 때 그 대상이 자기 자신을 참조하는 개념을 말합니다. 이를 함수로 구현한 것을 재귀 함수라고 합니다.재귀 함수: 자신을 재귀적으로 호출하는 함수.기저 조건(탈출 조건): 재귀 함수가 무한히 호출되지 않도록 종료 조건이 반드시 필요합니다.기저 조건이 없다면, 함수는 계속 호출되며, 결국 콜스택(Call Stack)이라는 메모리 공간이 꽉 차고 프로그램은 강제로 종료됩니다.*콜스택(Call Stack) : 함수 호출 시 해당 함수의 실행 정보를 저장하는 메모리 영역입니다. 스택(Stack) 구조로, 먼저 호출된 함수가 나중에 종료되는 후입선출(LIFO) 방식으로 동작합니다. 재귀적으로 문제 해결하기패턴단순한 반복 실행 단순 반복 작업은 재귀로 구현했을 때 성능 상의 이점이 없습니다. 오히려 반복문보다 더 많은 메모리를 차지하게 됩니다.반복 작업은 재귀보다는 반복문이 더 효율적입니다. 하위 문제를 기반으로 현재 문제 계산하향식 계산 방식으로 문제를 해결하는 경우 재귀가 더 유리합니다.예시: 팩토리얼 함수는 재귀를 이용한 하향식 계산이 가능합니다.같은 문제를 반복문으로 해결할 수도 있지만, 이때는 상향식 계산 방식이 주로 사용됩니다.재귀 함수는 특히 하향식 계산에서 강력한 성능을 발휘합니다. 이 방식은 재귀를 통해서만 구현할 수 있습니다. function hanoi(count = number, from = string, to = string, tmp = string) { if(count === 0) return; hanoi(count - 1, from, tmp, to); console.log(`원반 ${count}를 ${from}에서 ${to}로 이동`); hanoi(count - 1, tmp, to, from); } hanoi(3, 'A', 'C', 'B'); 버블 정렬 (Bubble Sort)버블 정렬은 인접한 두 원소를 비교하고, 크기에 따라 자리를 바꾸는 방식으로 정렬을 수행하는 알고리즘입니다.성능: 시간 복잡도는 최악의 경우 O(n2)O(n^2)O(n2).장점: 이해하기 쉽고 구현이 간단한 알고리즘입니다.단점: 효율이 좋지 않아, 실무에서 자주 사용되지 않습니다. function bubbleSort(arr) { for(let i = 0; i < arr.lenght - 1; i++) { for(let j = 0; j < (arr.length - i - 1); j++) { if(arr[j] > arr[j + 1]) { let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } 선택 정렬 (Selection Sort)선택 정렬은 정렬되지 않은 영역에서 가장 작은 값을 찾아 첫 번째 원소와 교체하는 방식으로 정렬하는 알고리즘입니다.성능: 시간 복잡도는 최악의 경우 O(n2)O(n^2)O(n2).장점: 구현이 단순하며 이해하기 쉽습니다.단점: 성능이 좋지 않아, 대규모 데이터에 적합하지 않습니다. function selectSort(arr) { for(let i = 0; i < arr.length; i++) { let minValueIndex = i; for(let j = i + 1; j < arr.length; j++) { if(arr[j] < arr[minValueIndex]) { minValueIndex = j; } } let temp = arr[i]; arr[i] = arr[minValueIndex]; arr[minValueIndex] = temp; } }

알고리즘 · 자료구조･CS･알고리즘･자료구조

1

[인프런 워밍업클럽 CS 2기] 2주차 미션

운영체제1. FIFO 스케줄링의 장단점이 뭔가요?스케줄링 큐에 들어온 순서대로 CPU 할당받기 때문에 장점은 단순하고 직관적이지만, 한 프로세스가 완전히 끝나야 다음 프로세스가 작업을 시작할 수 있기 때문에 긴 시간이 걸리는 작업 등을 기다려야 합니다. 게다가 I/O 작업이 있다면 CPU는 I/O 작업이 끝날 때까지 쉬고 있어서 CPU 사용률이 떨어집니다. 2. SJF를 사용하기 여러운 이유가 뭔가요?어떤 프로세스가 얼마나 실행될 지 예측 어렵습니다. BurstTime이 긴 프로세스는 또 아주 오랫동안 실행되지 않을 수 있습니다. 3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요? 컨텍스트 스위칭이 너무 자주 일어나서 타임 슬라이스에서 실행되는 프로세스의 처리량보다 컨텍스트 스위칭 처리하는 양이 더 커져버립니다. == "오버헤드가 너무 커집니다." 4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?프로세스가 실행 중에 스스로 CPU를 반납하면 CPU 사용이 적은 거니까 I/O Bound Process일 확률이 크고, 반대로 타임 슬라이스 크기를 오버해서 CPU 스케줄러에 의해 강제로 뺏기는 상황이면 CPU Bound Process일 확률이 크다. 5. 공유자원이란무엇인가요?프로세스 간 통신 시 공동으로 이용하는 변수, 파일 등을 말합니다. 6. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호배제비선점점유, 대기원형대기 자료구조와 알고리즘1. 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?콜 스택이라는 메모리 공간이 가득 차버려서 자동으로 종료되게 됩니다. 2. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요. function sumOdd(n){ // 재귀 로직 if (n <= 0) { return 0; } if (n % 2 !== 0) { return n + sumOdd(n - 2); } else { return sumOdd(n - 1); } } console.log(sumOdd(10)) // 25

1

[인프런 워밍업 클럽 2기 CS] 2주차 발자국

자료구조재귀 : 하향식 계산 방법이 재귀를 이해하는 확실한 설명이라고 느꼈습니다.버블 정렬 : 배열의 옆 자리 값과 비교하는 방법. 높은 숫자 부터 정렬이 진행됩니다.선택 정렬: 배열에서 값이 가장 작은 값을 머저 찾아서 정렬하는 방법. 작은 숫자 부터 정렬이 진행.지금까지 배운 정렬의 방식은 모두 O(n^2)으로 비효율적입니다. 메모리를 많이 사용하더라도 시간 복잡도를 낮추어야하는 필요가 있습니다. 알고리즘 cpu 스케줄링 : FIFO, SJF, RR, MLFQIPC : RPC, 공유자원 과 임계구역, 세마포어와 모니터데드락: 상호배제, 비선점, 점유와 대기, 원형식사하는 철학자 은행원 알고리즘메모리: 메모리의 종류상대 주소와 절대 주소가변 분할 방식, 고정 분할 방식, 버디 시스템 회고재귀에 대한 사고를 제 나름의 방식으로 명확히 이해할 수 있었습니다.CPU스케줄링에서 IPC, 데드락, 메모리로 이어지는 강의가 마치 이야기 같이 진행되어 큰 틀을 잡고 가기 좋았습니다. 나무 기둥을 세웠으니 가지와 잎을 더해 풍성하게 이야기를 채워야 함을 배웠습니다.

1

[인프런 워밍업 클럽 2기 CS] 1주차 발자국

[1주차 학습 내용]자료구조와 알고리즘배열, 연결리스트, 스택, 큐, 덱, 해시테이블, 셋자료구조 7가지의 개념과 시간복잡도에 대한 설명자료구조 7가지 코드로 구현해보기 운영체제운영체제에 대한 개념프로세스와 쓰레드에 대한 개념 및 관리 방법CPU 스케줄링에 대한 개념 및 동작방법[1주차 회고]지금까지 자료구조에 대한 개념 없이 무지성으로 매일 한 문제씩 알고리즘을 풀고 있었다.이제는 자료구조에 대한 개념이 필요한 상태였는데, 막상 공부를 하려고 하니 너무 어려웠고이해가 되지 않는 부분들이 너무 많았다. 근데 이번 강의는 그림으로 설명해주고 코드로 구현까지 하며 개념을 익히니정말 귀에 쏙쏙 들어왔다.반면 운영체제는 무작정 어렵다고만 생각해서 인지 강의 1번만으로는 제대로 개념을 익히지 못하였다.다음 2주차에는 1주차의 강의를 복습하면서 이해해보려고 노력해야겠다. 알고리즘 강의 링크 👉그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)운영체제 강의 링크 👉그림으로 쉽게 배우는 운영체제

알고리즘 · 자료구조･CS지식･인프런워밍업클럽･2기

1

[인프런 워밍업 클럽 2기 CS] 2주차 발자국

[2주차 학습 내용]자료구조와 알고리즘재귀: 어떠한 것을 정의 할 때 자기 자신을 참조하는 것프로그래밍에서 콜스택과 같다.FILO의 특징을 가지고 있다.버블정렬: 앞과 뒤의 값을 비교해서 자리를 비교하는 알고리즘가장 단순하지만 성능이 좋지 않다.O(n^2)의 시간복잡도를 가지고 있다.선택 정렬: 정렬되지 않은 첫번째 값을 시작으로 마지막 원소까지 비교하여 가장 작은 값과 자리를 바꾸는 알고리즘이해와 구현이 간단하지만 버블정렬과 마찬가지로 O(n^2)의 시간복잡도를 가지고 있다. 운영체제SJF, RR, MLFQ, 프로세스 간 통신, 공유자원과 임계구역, 세마포어, 모니터데드락, 데드락 해결, 메모리 종류, 메모리와 주소, 메모리 할당방식 [2주차 회고]처음 재귀에 대해 공부할때 이해하기 힘들었고, 당시에 완벽하게 이해를 하지 못하고 넘어갔었다. 하지만 이번 기회로 정확하게 재귀란 무엇인지 이해하게 되어 알고리즘에 한번 적용해보아야겠다.운영체제는 '이게 정말 무슨말이지..'할 정도로 멍하니 듣다가 끝낸 것 같다..지금은 이런게 있구나 정도로만 알고 넘어간 뒤 다시한번 강의를 들으면서 이해를 하는 것이 필요할 것 같다.알고리즘 강의 링크 👉그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)운영체제 강의 링크 👉그림으로 쉽게 배우는 운영체제

알고리즘 · 자료구조･CS지식･인프런워밍업클럽･2기

1

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) return 0; // n이 홀수면 n을 더하고, 짝수면 다음 홀수를 더하기 위해 n - 1을 호출 if (n % 2 !== 0) return n + sumOdd(n - 2); else return sumOdd(n - 1); } console.log(sumOdd(10)); // 25 답변:이 재귀 함수는 0부터 n까지의 홀수 합을 계산함. n이 홀수일 경우, 그 값을 더한 후 n-2에 대해 다시 재귀 호출을 하며, 짝수일 경우에는 다음 홀수를 계산하기 위해 n-1을 호출함.

1

[인프런 워밍업 클럽 2기 CS] 2주차 미션

[운영체제]FIFO 스케줄링의 장단점이 뭔가요?=> 선입선출의 구조로 단순하고 직관적이라는 장점이 있지만, 한 프로세스가 끝나야 그 다음 프로세스가 실행 되기 때문에 비효율적인 상황이 될 수 있습니다.SJF를 사용하기 여러운 이유가 뭔가요?=> 프로세스가 얼마나 실행될지 예측하기 어렵고, 실행시간이 너무 긴 프로세스는 뒤로 밀려나기 때문에 언제 실행될지 모른다는 단점이 있습니다.RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?=> 컨텍스트 스위칭이 너무 자주 일어나 실행되는 프로세스의 처리량보다 컨텍스트 스위칭을 처리하는 양이 더 커져 오버헤드가 커지는 상황이 발생합니다.운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?=> CPU 스케줄러에 의해 강제로 CPU를 뺐긴다면 CPU Bound Process이고, CPU를 사용하다가 스스로 반납하게 되면 I/O Bound Process입니다.공유자원이란무엇인가요?=> 프로세스들이 공동으로 사용하는 변수, 파일 등을 말합니다.교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?=> 상호배제, 비선점, 점유와 대기, 원형 대기가 모두 충족되어야 합니다. [자료구조와 알고리즘]재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?=> 코드가 끝나지 않게 되어 무한반복이 되거나, 잘못 반복이 되어 잘못된 결과가 나올 수 있습니다.0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ if(n <= 0) return 0; if(n %= 2 == 0){ return 0 + sumOdd(n - 1); }else { return n + sumOdd(n - 1); } } console.log(sumOdd(10)) // 25알고리즘 강의 링크 👉그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)운영체제 강의 링크 👉그림으로 쉽게 배우는 운영체제

알고리즘 · 자료구조･CS지식･인프런워밍업클럽･2기

1

운영체제

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

운영체제･워밍업클럽CS

1

[인프런 워밍업클럽 CS 2기] 2주차 발자국

어느덧 2주차에 접어들었습니다.이번주도 너무 빠르게 지나간 것 같아 아쉬워요.그렇지만 많은 것을 했기에 나름 뿌듯함이 있는 주였습니다.가장 좋은 것은 이번주부터 발표스터디를 시작했다는 것입니다. (신청한 과거의 나 칭찬해...)발표를 해야하니 자동으로 빡세게 공부해야함+발표자료도 잘 만들어야 함+모르면 쪽팔림... 등등여러 요소들이 복합적으로 작용해서 원래 스터디에 참여한 제대로 공부한다는 목적을 잘 달성하고 있어서 좋습니다.단점은... 복습+준비+정리까지 시간이 좀 많이 걸린다는 것이 있습니다. - 이번주에 공부한 내용의 키워드 -운영체제CPU스케줄링 알고리즘: SJF, RR(Round Robin), MLFQ프로세스 간 통신공유자원과 임계구역. 임계구역 문제 해결을 위한 상호배제 메커니즘상호배제 메커니즘: 세마포어, 모니터(세마포어 단점 해결)교착상태(데드락) 문제와 해결방법은행원 알고리즘안정상태/불안정상태가벼운/무거운 교착 상태검출자료구조와 알고리즘재귀하노이탑버블정렬선택정렬- 이번주에 공부한 내용 요약 -운영체제CPU 스케줄링 알고리즘 중에서 FIFO는 작업 순서에 따라 평균 대기시간이 달라져요. 그렇다면 burst time이 짧은 프로세스 먼저 실행하는 알고리즘을 만들면 되는 것 아니냐!라는 아이디어로 Shortest Jop First(SJF) 알고리즘이 등장했습니다.SJF는 이론적으로 FIFO보다 성능이 좋지만 프로세스가 얼마나 실행될지 예측이 어렵고, burst time이 긴 프로세스는 계속 뒤로 밀린다는 불공평성 때문에 SJF는 쓰이지 않게 되었습니다.앞선 알고리즘들이 단점이 있자 이를 보완한 알고리즘은 Round Robin(RR)알고리즘이 등장했습니다.한 프로세스에게 일정시간(=타임슬라이스)만큼 CPU를 할당하고 할당시간이 지나면 강제로 뺏어서 다른 프로세스에게 일정시간만큼 CPU를 할당하는 방법을 의미합니다.RR의 성능은 타임슬라이스 값에 따라 달라져서 적절한 값을 주는 것이 가장 중요합니다.작업을 하다보면 손해보는 프로세스가 생기기도 하는데 이를 해결하기 위해 RR에서 업그레이드된 알고리즘인 MLFQ(Multi Level Feedback Queue)가 등장했어요. 이 방법이 오늘날 운영체제에서 가장 일반적으로 쓰이는 CPU스케줄링 기법입니다.프로세스는 다른 프로세스와 데이터를 주고받으며 통신하기도 해요. 프로세스 간 통신을 하다보면 공동으로 이용하는 변수나 파일들이 생기는데 이것을 '공유자원'이라 합니다.그런데 공유자원을 쓰다보면 자원에 여러 프로세스가 동시에 접근하는 것과 같은 문제가 생기기도 합니다. 이런 문제들을 '동기화 문제'라고 합니다.동기화 문제 해결을 위해 여러 프로세스가 동시에 사용하면 안되는 영역인 '임계구역'을 정의하게 되었습니다.임계구역 문제 해결을 위해 '상호배제 메커니즘'이 필요해요.상호배제 메커니즘으로는 '세마포어', '모니터'가 있어요세마포어는 동기화에서 가장 중요한 개념입니다. 공유자원을 지키는 열쇠같은 개념으로 이를 사용하면 여러 프로세스가 동시에 공유자원에 접근하지 못하게 할 수 있습니다.세마포어는 wait, signal 함수를 사용하는데 이 순서가 잘못 호출되면 세마포어를 잘못 사용할 가능성이 있어요. 그래서 등장한 것이 '모니터'입니다.모니터(컴퓨터 모니터 아님...)는 운영체제가 처리하는 것이 아니라 프로그래밍 언어차원에서 지원합니다. 대표적으로 자바에서 모니터를 지원해요.모니터 구현만 완벽하다면 세마포어처럼 wait, signal로 감싸지 않아도 되어서 편하고 안전하게 코드 작성이 가능합니다. 자료구조와 알고리즘재귀는 어떤 것을 정의할 때 자기 자신을 참고하는 것을 의미합니다.재귀함수를 정의해서 쓸 때는 탈출조건이 반드시 있어야합니다.콜스택은 함수가 호출되면서 올라가는 메모리 영역을 의미합니다.(=스택 자료구조)함수를 호출하면 콜스택에 올라가고 함수가 종료되면 콜스택에서 제거됩니다.재귀함수를 사용해서 해결하는 대표적인 문제로 '하노이 탑'이 있습니다.버블정렬은 가장 쉽게 생각할 수 있는 정렬방법 중 하나입니다.앞에서부터 바로 옆의 숫자와 크기를 비교하고 자리를 바꾸는데 이 과정을 끝까지 확인해가며 정렬하는 방법입니다.방법은 간단한데 성능이 좋지않다는 단점이 있습니다.버블정렬처럼 구현은 쉬운데 성능은 그닥 좋지 못한 알고리즘으로 '선택정렬'이 있습니다.선택정렬은 배열의 처음부터 마지막까지 쭉 확인한 다음 작은 값을 처음으로 가지고 옵니다. 정렬되지 않은 영역을 대상으로 정렬이 완료될 때까지 이 방법을 쭉 반복합니다.- 간단하게 이번 주 회고 -우여곡절 끝에 발표 스터디가 이번주부터 시작되었습니다. 다들 잘하는 분들로 모여서 나만 뒤쳐질 수는 없다!는 생각으로 따라가고 있습니다. 아마 이분들과 스터디를 하지 않았다면 강의 그냥 한번 보고 다음에 또 봐야지 했을 것 같아요. 스터디에서 발표도 해야하고 강의 내용으로 얘기도 해야 해서 정말 많이 복습했어요. 덕분에 이번 스터디 끝나면 배운 내용이 머리에서 떠나지는 않을 것 같습니다.(▲ 스터디에 사용한 발표자료 중 하나...) 어느덧 2주차가 마무리되었습니다. 주차가 거듭될수록 강의 내용이 더 많아지고 있는데 강의가 재미있어서 정말 다행입니다... 이제 3주차에 접어들게 되는데 계속 꾸준하게 강의 듣고 스터디를 해서 목표한 바를 이루도록 노력해야겠습니다.

운영체제･자료구조･알고리즘･스터디

1

[인프런 워밍업클럽 CS 2기] 2주차 미션

2주차 미션 시작합니다. 운영체제FIFO 스케줄링의 장단점이 뭔가요?FIFO 스케줄링은 스케줄링 큐에 들어온 순서대로 CPU를 할당받는 방식입니다.장점단순하고 직관적입니다.(들어온 순서대로 실행되고 나가면 끝!)단점실행시간이 짧은데 늦게 온 프로세스는 실행시간이 길고 먼저 온 프로세스를 기다려야 합니다. 순서대로 실행되어야 하기 때문이죠.만약에 입출력 작업이 먼저 와 있다면 입출력 작업이 끝날 때까지 CPU가 쉬어야해서 CPU 사용률이 감소한다는 단점이 있습니다. SJF를 사용하기 여러운 이유가 뭔가요?SJF(Shortest Job First)는 짧은 작업을 먼저 실행하는 알고리즘입니다.SJF에는 2개의 문제점이 있습니다.1) 어떤 프로세스가 얼마나 실행될지 예측하기 어렵다는 점2) Burst time이 짧은 프로세스가 중간에 계속 들어오면 긴 프로세스는 계속 뒤로 밀려 아주 오랫동안 실행되지 않을 수 있다는 점이런 문제점 때문에 SJF는 사용하기 어렵습니다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?RR스케줄링에서 타임슬라이스가 아주 작으면 앱이 동시에 동작하는 것처럼 느낄 수 있습니다.그러나 단점으로는 오버헤드가 너무 커진다는 것입니다. Context Switching 처리량이 실행되는 프로세스 처리량보다 많기 때문에 이런 일이 발생하게 됩니다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?CPU bound process는 대부분의 시간에 CPU연산을 하는 프로세스입니다.CPU를 많이 사용하기 때문에 CPU사용하는 프로세스가 실행하다가 CPU스케줄러에 강제로 CPU를 빼앗긴다면 운영체제는 CPU bound process로 판단합니다.I/O bound process는 대부분의 시간을 I/O작업으로 보내고 CPU연산을 조그맣게 합니다. CPU 사용이 적기 때문에 CPU사용하는 프로세스가 스스로 CPU를 반납한다면 운영체제는 CPU I/O process로 판단합니다. 공유자원이란무엇인가요?공유자원이란 프로세스 간 통신을 할 때 '공동으로 이용'하는 변수나 파일들을 의미합니다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?교착상태에 빠지기 위해서는 아래 4가지로 이 조건들을 모두 충족해야 합니다.1) 상호배제한 프로세스가 한 리소스를 점유했다면 그 리소스는 다른 프로세스에서 공유될 수 없습니다.2) 비선점한 프로세스가 리소스를 점유할 때 다른 프로세스가 리소스를 뺏을 수 없습니다.3) 점유와 대기어떤 프로세스가 한 리소스를 가지고 있는 상태에서 다른 리소스를 원하는 상태입니다.4) 원형대기점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있어야합니다. 자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?재귀함수에서 기저조건을 만들지 않거나 잘못 설정하면 재귀함수가 계속 호출되게 되고 메모리가 금방 가득 차서 프로그램 자동 종료되는 상황이 생길 수 있습니다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.def sumOdd(n): if n<=0: return 0 if n % 2 == 1: #홀수 return n + sumOdd(n-2) else: return sumOdd(n-1) print(sumOdd(10))

미션･운영체제･알고리즘･자료구조･cs

1

워밍업 클럽(CS) 두번째 미션📓

운영체제Q1. FIFO 스케줄링의 장단점이 뭔가요?장점 : 단순하고 직관적단점 : 한 프로세스가 완전히 끝나야 다음 프로세스 시작, I/O 작업 시 CPU가 기다려야 하므로 사용률이 떨어짐. Q2. SJF를 사용하기 여러운 이유가 뭔가요?어떤 프로세스가 얼마나 실행될 지 예측하기가 어렵고, Burst Time이 긴 프로세스는 오랫동안 실행되지 않을 수 있는 문제가 있다. Q3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?타임 슬라이스가 작으면 컨텍스트 스위칭이 너무 자주 일어나게 되어 오버헤드가 발생한다. Q4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?스스로 CPU를 반납하면 CPU 사용이 적은 I/O Bound Process로 판단, 타임 슬라이스 크기를 오버해서 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황이면 CPU Bound Process로 판단 Q5. 공유자원이란 무엇인가요?프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일들 Q6. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호배제/ 비선점/ 점유와 대기/ 원형 대기 자료구조와 알고리즘 Q1. 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?콜스택(메모리 공간)이 가득 차서 자동으로 종료됨 Q2. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ if(n <= 0) return 0; else if(n % 2 == 1){ return n + sumOdd(n - 2); } else{ return sumOdd(n - 1); } } console.log(sumOdd(10)) // 25

알고리즘 · 자료구조･워밍업클럽･자료구조･알고리즘･운영체제･감자

1

두번째 발자국

알고리즘재귀재귀란 어떠한 것을 정의할 때 자기 자신을 참조하는 것 콜스텍이란 함수가 호출되면서 올라가는 메모리 영역으로 스택이라고도 부른다.콜스택은 FIFO 특성을 가지고 있다.콜스택은 스택 자료구조를 잘 활용한 대표적인 사례이다. 재귀함수는 자기자신을 호출하는 함수이며, 기저 조건(탈출 조건)이 필요함기저 조건을 만날 때까지 콜스택에 함수가 쌓인다. 재귀함수는 for문을 대신하려고 쓰는게 아닌 더 복잡한 문제를 쉽게 해결하기 위함대표적인 예시로 팩토리얼이 있다.int Factorial(int value) { if(value == 1) return 1; return value * Factorial(value - 1); } 하노이탑재귀함수의 대표적인 예시void Hanoi(int cnt, string from, string to, string temp) { if(cnt == 0) return; Hanoi(cnt - 1, from, temp, to); cout << "원반" << cnt << "를 " << from << "에서 " << to << "로 이동" << "\\n"; Hanoi(cnt - 1, temp, to, from); } 버블 정렬 (Bubble Sort)가장 쉽게 생각할 수 있는 정렬 중 하나이기에 구현은 쉽지만, 성능은 나쁘다.앞에 있는 숫자와 뒤에 있는 숫자를 비교해서 자리를 바꾸는 알고리즘버블 정렬은 데이터를 옆 데이터와 비교하면서 자리를 바꾸는 게 버블이 일어나는 것 같다 해서 버블 정렬이라는 이름이 붙음.버블 정렬의 성능시간 복잡도 : O(n²)장점이해와 구현이 쉽다.단점성능이 좋지 않다 O(n²)void BubbleSort(int* arr, int size) { for(int i = 0; i < size - 1; i++) { for(int j = 1; j < size - i - 1; j++) { if(arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } 선택 정렬 (Sellection Sort)선택 정렬도 이해와 구현이 쉽지만, 성능이 나쁘다.배열의 정렬 되지 않은 영역을 순회하며 가장 작은 값을 탐색 후 교체다음 원소부터 다시 해당 작업 반복선택 정렬의 성능시간 복잡도 : O(n²)장점이해와 구현이 쉽다.단점성능이 좋지 않음void SelectionSort(int* arr, int size) { for(int i = 0; i < size - 1; i++) { int minIndex = i; for(int j = i + 1; j < size; j++) { if(arr[minIndex] > arr[j]) { minIndex = j; } } if(minIndex != i) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } } CPU 스케줄링SJFShortest Job FirstFIFO 에서 Burst Time이 짧은게 먼저 실행되면 평균 대기 시간이 짧아진다는 것을 발견하고짧은 작업을 먼저 실행하면 된다는 발상에 의해 만들어짐.문제점프로세스 종료 시간 예측 불가능Burst Time이 긴 프로세스는 실행이 안될 수도 있다.RRRound Robin운영체제가 CPU 할당 시간을 지정해 현재 프로세스의 할당 시간이 지나면 다음 프로세스에게 CPU를 할당해주는 방법이 CPU 할당 시간을 타임 슬라이스 or 타임 퀀텀이라고 부른다.RR 알고리즘은 컨텍스트 스위칭이 있기에 비용이 더 발생할 수도 있다.RR 알고리즘의 성능은 타임 슬라이스의 값에 따라 크게 달라진다.타임 슬라이스를 너무 크게 설정하면 FIFO알고리즘과 같은 평균 대기 시간이 발생되고,너무 작게 설정하면 실행되는 프로세스의 처리량보다 컨텍스트 스위칭의 비용이 더 커지게 된다.그렇기에 사용자가 느끼기에 최적의 타임 슬라이스를 찾아야 한다.Windows는 타임 슬라이스가 20ms, Unix는 100ms 정도이다.MLFQMulti Level Feedback Queue현대 운영체제에서 가장 일반적으로 사용되는 CPU 스케줄링 기법이다.MLFQ 는 RR의 업그레이드된 알고리즘이다.CPU Bound Process는 I/O 작업 없이 CPU 연산만 하는 프로세스이다.CPU 사용률과 처리량이 중요I/O Bound Process는 CPU작업은 조금만 하고 대부분의 시간은 I/O 작업에 사용된다.응답 속도가 중요RR 알고리즘으로는 CPU Bound Process 와 I/O Bound Process 둘 다 이득을 보는 구조로 만드려면타임 슬라이스를 작게 설정해야 한다. 이렇게 할 시 I/O Bound Process 는 무조건 이득인 구조이지만,CPU Bound Process에서 같은 프로세스를 계속 실행하지만 컨텍스트 스위칭을 계속해서 해당 비용이 발생하는 문제가 생김.이러한 손해를 해결하기 위해 만들어진 알고리즘이 MLFQ 알고리즘이다.MLFQ의 핵심 로직은 프로세스의 CPU 점유 시간이 지나 강제로 뺏기는지, 스스로 CPU 사용을 반납하는지이다.우선순위를 가진 큐를 여러 개 준비하고, 해당 큐는 우선순위가 낮을 수록 타임 슬라이스 시간을 길게 설정한다.CPU 에게 강제로 뺏긴다면 현재 큐보다 우선순위가 낮은 큐로 이동시킨다. 프로세스 동기화프로세스 간 통신프로세스는 독립적으로도 실행하지만 다른 프로세스와 데이터를 주고 받으며 통신을 하는 경우도 있다.통신은 한 PC 내에 다른 프로세스와 할 수도 있고네트워크로 연결된 다른 프로세스와 할 수도 있다.통신 방법한 PC 내에 프로세스 간 통신 하는 방법파일 : 통신을 하려는 프로세스들이 하나의 파일을 이용해 읽고 쓰는 방법파이프 : 운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰는 방법네트워크를 이용한 방법운영체제가 제공하는 소켓통신이나 다른 컴퓨터에 있는 함수를 호출하는 RPC(Remote Procedure Call, 원격 프로시저 호출)를 이용해 통신하는 방법한 프로세스 내에 쓰레드 간 통신 하는 방법데이터에 있는 전역변수나 힙을 이용하여 통신이 가능하다.공유자원과 임계구역공유 자원 : 프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일들공유자원은 여러 프로세스가 공유하고 있기에 각 프로세스의 접근 순서에 따라 결과가 달라질 수 있다.또한 컨텍스트 스위칭으로 시분할 처리를 하기에 프로세스 실행 순서 예측이 힘들며 연산 결과를 예측하기 힘들고 여기서 발생한 문제를 ‘동기화 문제’ 라고 부른다.임계 구역(Critical Section) : 여러 프로세스가 동시에 사용하면 안되는 영역경쟁 조건(Race Condition) : 공유 자원을 서로 사용하기 위해서 경쟁하는 것.임계 구역 문제를 해결하기 위해서는 상호 배제(Mutual Exclusion) 메커니즘이 필요상호 배제의 요구 사항임계 영역엔 동시에 하나의 프로세스만 접근한다.여러 요청에도 하나의 프로세스의 접근만 허용한다.임계 영역에 들어간 프로세스는 최대한 빠르게 나와야한다.세마포어상호 배제 메커니즘의 한 가지세마포어는 운영체제가 관리하는 int형 정수이다.프로세스가 공유 자원을 사용할 때 접근 권한을 얻고 해당 접근 권한을 다시 반납하기 전 까지다른 프로세스가 해당 공유 자원에 접근하지 못하게 하는 것.단점순서를 기다리는 wait()함수와 순서를 반납하는 signal()함수의 순서를 잘못 사용할 가능성이 있음.모니터세마포어의 단점을 해결한 상호 배제 매커니즘이다.모니터는 운영체제가 처리하는 것이 아닌 프로그래밍 언어 차원에서 지원하는 방법이다.키워드가 붙은 함수를 사용중인 프로세스가 있다면 같은 키워드가 붙은 함수를 다른 프로세스에서 실행하지 못함. 자바에서는 synchronized키워드를 사용. 완벽한 상호 배제가 일어남.C++ 에서는 mutex를 사용C#(유니티) 에서는 lock 키워드를 사용데드락데드락이란?데드락(교착상태) : 여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 아무도 작업을 진행하지 못하는 상태교착상태가 발생하는 이유는 공유자원 때문이다.공유자원을 서로 차지하려다가 교착상태가 발생한 것.교착상태의 필요조건 : 한가지라도 충족되지 않으면 교착상태가 발생하지 않는다.상호배제 : 공유자원에 대한 접근 권한을 부여하여 하나의 프로세스만 이용 가능비선점 : 프로세스가 점유하고 있는 리소스를 다른 프로세스가 빼앗지 못해야 한다.점유와 대기 : 어떤 프로세스가 리소스A를 가지고 있는 상태에서 리소스 B를 원하는 상태여야 한다.원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있다.데드락 해결교착상태 예방은 힘들고 해결하는 방안으로 발전교착상태 회피(Deadlock avoidance) : 운영체제가 가지는 총자원의 수와 프로세스들이 요구하는 최대 요구 자원, 현재 할당된 자원, 요청이 예상되는 자원을 통해 안정상태, 불안정상태를 나눈다.가벼운 교착 상태 검출 : 타이머를 이용한 방식. 프로세스가 일정시간 동안 작업을 진행하지 않으면 교착상태가 일어났다고 간주하고 해결하는 방식. / 일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백.무거운 교착 상태 검출 : 자원 할당 그래프를 이용. 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생했다면 해결. / 프로세스들의 자원 요청이 순환인지 아닌지 확인 후 교착상태를 파악한다. 교착상태를 일으킨 프로세스는 강제 종료시킨다. 다시 실행시킬 때 체크포인트로 롤백 시킨다.이 방식은 운영체제가 지속적으로 자원 할당 그래프를 유지고 검사하기에 오버헤드가 발생한다. 하지만 가벼운 교착 상태 검출에서 발생하는 억울하게 종료되는 프로세스가 만들어지지 않는다.메모리레지스터가장 빠른 기억장소로 CPU 내에 존재휘발성 메모리CPU 구분할 때 32bit, 64bit 가 레지스터의 크기를 의미CPU는 계산을 할 때 메인메모리에 있는 값을 레지스터로 가져와 계산을 한다.계산 결과는 다시 메인메모리에 저장시킨다.캐시레지스터는 작업 속도가 매우 빠르고, 메인 메모리는 작업 속도가 느리다.메인 메모리에 있는 값을 레지스터로 옮기려면 한참 걸리기에 미리 필요할 것 같은 데이터를미리 가져오기로 하는데 이 데이터를 저장하는 곳이 캐시이다.휘발성 메모리캐시는 성능의 이유로 여러 개를 둔다.만약 CPU가 값을 요청해 레지스터로 값을 옮겨야 한다면단계에 따라 가장 속도가 빠른 L1 캐시를 보고 여기에 데이터가 없다면 L2 ~ L3 캐시를 확인해보고여기에도 없다면 메인 메모리에서 값을 가져온다.메인 메모리(RAM)메인 메모리는 실제 운영체제와 다른 프로세스들이 올라가는 공간이다.휘발성 메모리실행중인 프로그램만 올리는 용도이다.보조저장장치 (SSD, HDD)비휘발성 메모리사무용 프로그램이나 게임, 작업한 파일등의 데이터를 저장하는데 사용메모리와 주소메모리운영체제는 메모리를 관리하기 위해 1바이트 크기로 구역을 나누고 숫자를 메긴다. 이 숫자가 주소를 의미한다.CPU의 레지스터 크기에 따라 ALU(산술 논리 연산 장치)의 크기와, 데이터가 이동하는 버스의 크기, CPU가 다룰 수 있는 메모리의 크기도 같다.32bit, 64bit레지스터 크기가 클수록 한번에 처리할 수 있는 양이 많기에 속도도 빠르다.물리 주소(절대 주소)와 논리 주소(상대 주소)물리 주소 공간 : 메모리를 컴퓨터에 연결하면 0x0번지부터 시작하는 주소 공간논리 주소 공간 : 사용자 관점에서 바라본 주소 공간사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근 가능하다.운영체제는 특별하기에 운영체제를 위한 공간은 따로 마련한다.사용자가 악의적인 프로그램을 만들어 운영체제를 침범하면 굉장히 위험할 수도 있기 때문그래서 하드웨어적으로 운영체제 공간과 사용자 공간을 나누는 경계 레지스터를 만든다.경계 레지스터 : CPU 내에 존재하는 레지스터로 메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 검사하고 만약 벗어났다면 해당 프로세스를 종료시킨다.컴파일러 / 모든 사용자 프로세스가 컴파일을 할 때 메모리 0번지에서 실행한다고 가정.사용자 관점으로 바라보는 주소는 상대 주소는 논리 주소 공간을 의미.메모리 관리자 관점으로 보는 주소는 절대 주소이다.사용자가 100번지의 주소를 요청했을때 CPU가 메모리 관리자에게 100번지의 데이터를 메모리 관리자에게 요청하고 메모리 관리자는 CPU가 요청한 주소와 재배치 레지스터에 있는 4000번지(프로그램의 실제 물리 주소) 값을 더한 4100번지에 접근해 데이터를 가져온다.재배치 레지스터 : 프로그램의 시작 주소가 저장되어 있다.메모리 할당 방식예전에는 유니 프로그래밍 환경에서 메모리보다 더 큰 프로그램을 실행시키는 방법으로메모리 오버 레이 (Memory Overlay) : 큰 프로그램을 메모리에 올릴 수 있도록 잘라서 당장 실행시켜야 할 부분만 메모리에 올리고 나머지는 용량이 큰 하드디스크의 스왑영역에 저장하는 기법스왑 : 스왑영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 옮기는 것메모리 할방 방식가변 분할 방식(세그멘테이션)프로세스의 크기에 따라 메모리를 나누는 방식한 프로세스가 메모리에 연속된 공간에 할당되기에 연속 메모리 할당이라고 한다.장점크기에 맞게 할당되기에 더 크게 할당되어서 낭비되는 공간인 내부 단편화가 없다. 단점외부 단편화가 발생 세그멘테이션에서 발생하는 외부 단편화는 연속된 공간에 할당되어야 하기에만약에 50MB와 10MB의 빈 공간이 있지만, 데이터 상으로는 60MB도 실행시킬 수 있지만,떨어져있기에 실행이 안되는 현상을 외부 단편화라고 부른다.이 현상을 해결하기 위해서는 운영체제가 조각 모음을 실행해줘야 하는데, 이 작업을 실행하면 모든 프로세스의 작업이 일시 중지되고, 메모리 공간을 이동시키는 작업을 해야 하기에 오버헤드가 발생.고정 분할 방식(페이징)프로세스의 크기와는 상관없이 메모리를 정해진 크기로 나누는 방식한 프로세스가 메모리에 분산되어 할당되기에 비연속 메모리 할당이라고 한다. 장점구현이 간단하고 오버헤드가 적다. 단점공간이 낭비되는 내부 단편화가 발생 내부 단편화 : 분할된 크기보다 작기에 내부에 빈 공간이 생겨 낭비된다.이를 해결하는 방법은 없고 분할되는 크기를 조절해서 내부 단편화를 최소화한다.오늘날의 운영체제는 가변 분할 방식과 고정 분할 방식을 혼합하여 단점을 줄였다.버디 시스템2의 승수로 메모리를 분할해 메모리를 할당하는 방식이다.프로세스가 요청하는 메모리 공간보다 작은 값이 나올 때까지 메모리 공간을 나눈다.그리고 그보다 큰 공간을 프로세스에게 할당해준다.해당 프로세스가 사용을 마치고 메모리에서 나가도 근접한 메모리 공간을 합치기 쉽다.2의 숭수로 동일하게 나눠서 반대로 조립만 하면 큰 공간이 만들어지기에 조각 모음보다 훨씬 간단하다.이 방식의 장점은 가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라지고 외부 단편화를 방지하기 위헤 메모리 공간을 확보하는 것이 간단.내부 단편화가 발생하기는 하지만 많은 공간의 낭비가 발생하지 않는다.

1

[인프런 워밍업 스터디 클럽] 2기 - 두 번째 발자국

시간 가는 줄 모른다. 벌써 워밍업 클럽 2주 차가 끝났다. 강의지난주에 개념을 잡았다면, 이번 주는 실습이 많았다. 2가지를 중점으로 들었다.어떻게 활용할 수 있을까?사고를 어떻게 하실까?실습을 하다 보니, 부족한 점을 많이 느꼈다. 객체지향이 부족하다고 느꼈는데 역시 맞았다. 개념도 중요하지만 어떻게 사용해야 할지 이어지지 않았다. 잠시 풀이 죽었다. 그런데 다시 생각해 보니 기회였다.'섹션 7. 리팩토링 연습'이 가장 인상 깊다. 준비한 개념을 전부 활용하는 섹션이었다. 섹션 7을 막힘없이 설명할 수 있다면 강의를 제대로 수강했다고 생각한다. 섹션 7에 계시는 우빈 님께 여러 번 인사드릴 예정이다. 늘 그랬듯, 해결할 것이다. 미션미션 1개였지만 어려웠다. '막막하다'라는 표현이 적절하다. 도저히 '객체지향'에 다가갈 수 없었다. 다른 분의 방식을 참고해서 미션을 해결할 수 있었다. 하지만 '내가 무엇을 모르고 부족한가?'를 알아보기 위해서는 알고 있는 부분에서 최선으로 해결했다.만족스럽지 않았다. 아쉬웠다. 문제에 부딪혔을 때 지식 공유자 님을 추상화하고 다가가려고 시도하는 편이다. '섹션 8. 기억하면 좋은 조언들'에 도움을 많이 받았다. 우빈 님께서 어떻게 사고에 다가갈 수 있는지 상세하게 이야기해 주셔서 힘을 얻었다. 지금도 재밌는데, '의도를 전달할 수 있다면 얼마나 재밌을까?'라는 생각이 들었다. 적용하기 어려웠던 부분을 반복해서 체득시킬 생각이다. 마치며클린 코드 과정이 끝났다. 중간 점검에서 우빈 님께서 하신 말씀이 기억에 남았다."강의에 전하고 싶은 내용을 모두 담았습니다"앞으로 이어지는 테스트에서도 어떻게 실천하고 계신지 함께 지켜보며 들을 생각이다. 절반 왔다. 강의에서 끝나지 않고 연습이 중요하다고 느꼈다. 3주 차도 무리 없이 헤쳐나갔으면 좋겠다. <참고 자료>인프런 워밍업 클럽 스터디 - BE 클린 코드 & 테스트 과정

백엔드･인프런워밍업클럽

1

[인프런 워밍업클럽 CS 2기] 2주차 발자국

운영체제프로세스 간 통신:프로세스는 같은 컴퓨터 내에서는 파이프나 쓰레드를 사용하고, 다른 컴퓨터 간에는 네트워크를 통해 통신한다.소켓 통신과 원격 프로시저 호출(RPC)을 사용하여 원격 통신을 처리한다.공유 자원과 임계 구역:여러 프로세스가 동시에 접근해서는 안 되는 영역을 임계구역이라 하며, 상호 배제 메커니즘을 통해 하나의 프로세스만 접근할 수 있도록 관리한다. 경쟁 상태를 방지하기 위해 세마포어와 모니터 등의 기법을 사용한다.세마포어:세마포어는 대기 큐와 열쇠 관리자를 통해 프로세스 간의 자원 접근을 관리한다. 그러나 세마포어는 잘못 사용할 경우 문제가 발생할 수 있으며, 이를 보완하기 위해 모니터와 같은 상호배제 메커니즘이 사용된다.데드락:교착 상태는 프로세스들이 자원을 점유하고 다른 프로세스의 작업이 완료되기를 기다리는 상황에서 발생한다. 이를 방지하기 위해 은행원 알고리즘과 같은 회피 기법을 사용한다.메모리 관리:메모리 할당 방식은 고정분할방식(페이징), 가변분할방식(세그멘테이션), 버디 시스템으로 나뉜다. 각 방식은 내부 단편화와 외부 단편화 문제를 해결하며, 효율적인 메모리 관리를 위해 사용된다. 알고리즘재귀:재귀는 함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 기법이다. 이를 통해 반복되는 문제를 하위 문제로 나누어 해결한다. 대표적인 예시로 팩토리얼 계산, 배열의 합, 문자열의 길이 계산, 지수 함수 계산, 하노이 탑 문제를 재귀적으로 풀어낸다. 재귀의 핵심은 기저조건 설정이며, 이를 통해 무한 호출을 방지할 수 있다. 콜스택(FILO 구조)을 사용하여 함수 호출과 종료를 처리한다.재귀 패턴:하위 문제를 해결한 뒤 상위 문제로 확장하는 하향식 계산 방식.반복적인 문제 해결보다는 하위 문제의 결과를 기반으로 상위 문제를 개선하는 방식이 효율적임.재귀 함수 예시:팩토리얼 계산: 하위 문제에서 구한 값을 상위 문제로 연결.배열의 합: 배열을 분할하고 합을 구하는 방식.문자열의 길이: 문자열을 하나씩 제거하면서 길이를 계산.지수 함수: 지수 계산을 재귀적으로 처리.하노이 탑: 문제를 나누어 하향식으로 접근하는 방법을 학습.회고이번 학습을 통해 운영체제의 핵심 원리와 알고리즘의 재귀적 사고 방식을 체계적으로 이해할 수 있었다. 특히, 알고리즘에서는 재귀적 사고를 통한 문제 분할이 얼마나 유용한지 체감할 수 있었으며 간단해 보이지만 재귀 함수 설계 시 기저 조건 설정과 스택 사용이 중요한 부분이라는 점을 깨달았다. 또한, 운영체제에서는 프로세스 간의 자원 공유와 통신이 어떻게 관리되는지, 그리고 자원 경쟁으로 인해 발생할 수 있는 교착 상태를 회피하고 해결하는 다양한 방법을 학습하면서 시스템의 안정성과 성능을 유지하는 것이 매우 중요한 문제임을 알게 되었다!☺

알고리즘 · 자료구조･워밍업클럽･CS

1

[인프런 워밍업 클럽 2기 - CS] 2주차 미션

운영체제FIFO 스케줄링의 장단점이 뭔가요?:장점:구현이 간단하며 요청된 순서대로 처리(선입선출).CPU 점유가 긴 프로세스가 없다면 응답 속도가 빠를 수 있다.단점:긴 작업이 앞에 있을 경우 짧은 작업이 오래 기다려야 한다. SJF를 사용하기 여러운 이유가 뭔가요?:각 프로세스의 실행 시간을 미리 예측하기 어렵다.실행시간이 너무 긴 프로세스는 너무 늦게 실행된다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?:컨텍스트 스위칭 비용이 증가하여 CPU 시간이 많이 소모된다.실제로 작업 처리 시간이 감소하여 성능 저하 발생 가능하다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?:PU 사용량이 많다 보니 타임 슬라이스를 넘어 CPU가 뺏기게 된다.I/O Bound Process의 경우 CPU 사용량이 적다 보니 타임 슬라이스 내에 CPU를 반납한다. 공유자원이란무엇인가요?:여러 프로세스가 동시에 접근할 수 있는 자원을 말한다(예: 프린터, 파일, 데이터베이스 등). 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?:상호 배제: 자원을 프로세스가 가져갔다면 다른 프로세스에게 공유되면 안된다.비선점: 다른 프로세스가 자원을 강제로 뺏을 수 없어야 한다.점유 및 대기: 자원을 점유한 채 다른 프로세스는 이 리소스를 원하면서 기다리고 있어야 한다. 원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있어야 한다. 위에 조건이 하나라도 충족되지 않으면 교착상태가 일어나지 않는다.자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?:무한 루프: 기저 조건이 없거나 잘못 설정되면 함수가 종료되지 않고 계속 호출되면서 무한 루프가 발생한다.Stack Overflow: 재귀 호출이 무한정 계속되면 스택 메모리가 가득 차서 Stack Overflow 에러가 발생하게 된다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요. :function sumOdd(n){ // 재귀 로직 if (n <= 0) return 0; n % 2 !== 0 ? n + sumOdd(n - 2) : sumOdd(n - 1); } console.log(sumOdd(10)) // 25

알고리즘 · 자료구조･워밍업클럽･CS

1

[발자국] 인프런 워밍업클럽 CS 2기 2주차 발자국

학습 했던 내용 요약자료구조 및 알고리즘 재귀 : 자기 자신을 참조하는 것, 탈출 조건 필수! (하노이탑)버블 정렬 : 앞에 있는 숫자와 옆에 있는 숫자를 비교해서 자리를 바꾸는 알고리즘.구현하기 쉽지만 성능O(n²)은 좋지 않음.선택 정렬 : 배열에 정렬되지 않은 영역에서 가장 작은 원소를 가장 첫번째로 가져온다. 완료된 영역은 더이상 참조하지않고, 정렬되지 않은 영역만 이 과정을 반복해 정렬하는 알고리즘.이해와 구현이 간단하지만, 성능O(n²)은 좋지 않음. 운영체제 프로그램을 실행시키면 메모리에 프로세스가 생성되고 각 프로세스에는 1개 이상의 스레드가 있다. 운영체제는 모든 프로세스에게 CPU를 할당, 해제하는데 이를 CPU 스케줄링이라 한다. 스케줄링 알고리즘에는 FIFO,SJF,RR, MLFQ 가 있다. FIFO (First In First Out) : 스케줄링 큐에 먼저 들어온 순서대로 CPU를 할당하는 방식이다. SJF (Shortest Job First) : Burst Time(작업시간)이 짧은 프로세스 먼저 실행되는 방식이다. RR (Round Robin) : 한 프로세스에게 일정 시간만큼 CPU를 할당하고, 할당 시간이 지나면 강제로 다른 프로세스에게 CPU 가 할당된다. 강제로 CPU를 뺏긴 프로세스는 큐의 가장 뒷부분으로 밀려나는 방식이다. MLFQ (Multi Level Feedback Queue) : 기본적으로 작은 크기의 타임 슬라이스를 선택하고, CPU 스케줄러에 의해 CPU가 뺏긴 상황이라면 , CPU Bound Process일 확률이 높으니 더 큰 타임 슬라이스를 할당 해주는 방식이다.공유된 자원에서 동기화 문제가 발생했고,이를 해결하기 위한 방법인 세마포어와 모니터방식이 있다. 공유자원 : 프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일1. 세마포어 : 운영체제가 가지고 있는 열쇠로, 공유자원을 한 프로세스만 이용하게끔 관리2. 모니터 방식 : 따로 운영체제가 처리하는 것이 아니라, 프로그래밍 언어 차원에서 지원하는 것.동기화 문제를 해결하기 위해 공유된 자원을 한 프로세스가 점유하게 만들었는데 교착상태(데드락) 발생교착상태 (데드락) : 여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 작업을 진행하지 못하는 상태교착상태가 발생하는 원인 : 공유자원해결방법 : 1. 가벼운 교착 상태 검출: 타이머 사용체크포인트를 만들어 저장하고, 타임 아웃시 마지막에 저장된 체크 포인트로 롤백2. 무거운 교착 상태 검출: 자원 할당 그래프 이용현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보다가, 교착상태가 발생 시 해결순환 구조가 생긴 그래프를 통해 확인하고, 교착 상태를 일으킨 프로세스를 강제 종료시킨다. 회고일주일 동안 스스로 칭찬하고 싶은 점일중일치 진도대로 인강을 다 수강하고, 미션과 발자국도 기한내에 진행한 점.(인강을 수강하면서 정리한 내용)복습을 함께 진행한 점 아쉬웠던 점토요일까지로 미션과 발자국을 미리 완수하고 싶었는데, 그렇지 못한 점. 보완하고 싶은 점 이해가 어려웠던 부분들은 더 찾아보면서 이해해보기 다음주 학습 목표미션과 발자국을 마감기한보다 하루 일찍 완수하기 출처 : 그림으로 쉽게 배우는 운영체제 - 감자 , 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)- 감자

알고리즘 · 자료구조･워밍업클럽･알고리즘･CS･발자국･운영체제･자료구조

1

인프런 워밍업 클럽 2기 - 발자국 2주차

회고이번주는 기간 맞춰서 들은 걸 넘어서, 중간에 휴일이 껴있어서 먼저 듣기도 했다. 그리고, 남는 시간에 다른 공부를 하는 100점에 110점!👏👏👏 다음주도 100점 만점에 105점을 하고 싶다.마지막 주도 화이팅! 강의 수강운영체제cpu 스케줄링, 프로세스 동기화, 데드락, 메모리에 대해 학습하였다. 공유자원과 데드락이 정말 재밌었다. 공유자원에 다양한 만약? 이런 경우라면 하고 생각해볼 수 있는 경우가 많았다.세마포어의 해결 하는 부분에서 모니터락에 대해서 설명해주셨는데만약, 인스턴스 단위 락을 걸고싶다면? 이런석으로도 사용할 수 있다는걸 배웠다. public class Health { private int health = 100; synchronized void increase(int amount) { health += amount; } synchronized void decrease(int amount) { health -= amount; } }이외에도 해당 모니터락은 범위 별로 다양하게 사용할 수 있는데, 이런 락을 많이 걸게되면, 성능상 문제가 생길 요지가 있으니 적잘한 락을 거는게 매우 중요할 것 같다. 알고리즘알고리즘에 대해 본격적으로 학습하였다.특히 재귀적으로 생각하기가 도움이 많이 되었다. 사실 알고리즘을 공부하면서, 재귀 함수를 사용하는 경우가 많은데 이해가기 좀 어려웠다 ㅠㅠ 이번에 강의를 들으면서 어떤 상황에는 재귀적으로 사용하면 좋을지 도움이 되었다.

워밍업클럽cs

1

워밍업 클럽 2주차 발자국🐾

그림으로 쉽게 배우는 자료구조와 알고리즘재귀(recursion) : 어떠한 것을 정의할 때 자기 자신을 참조하는 것콜스택함수가 호출되면서 올라가는 메모리 영역, 스택이라고도 부름First In Last Out(그림을 보면 기억이 더 잘 날 것 같아서 캡쳐! FILO를 시각적으로 이해할 수 있어서 좋다💕)재귀함수 예시 : 팩토리얼 함수function factorial(number){ if(number == 1 || number == 0){ return 1; } else{ return number * factorial(number - 1); } }(이게 어떻게 구현이 가능한 것인지 완벽히 이해되지는 않지만, 이렇게 간단히 표현 할 수 있다는 것이 놀랍다.)재귀적으로 생각하기하위 문제의 결과를 기반으로 현재 문제를 계산 -> 하향식 계산재귀함수의 위력은 하향식 계산에서 발휘 배열의 합 function sumArray(arr){ if(arr.length == 1) return arr[0]; return sumArray(arr.slice(0, -1)) + arr[arr.length -1]; }문자열의 길이를 계산function strLength(arr){ if(arr[0] == null) return 0; return strLength(arr.slice(0, -1)) + 1; }지수함수(밑 x, 지수 n)function power(x, n){ if(n == 0) return 1; retrun power(x, n-1) * x; }하노이 탑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"); 정렬 - 버블 정렬(Bubble Sort)데이터를 옆 데이터와 비교하면서 자리를 바꿈function BubbleSort(arr){ for(let i = 0; i < arr.length - 1; i++){ for(let j = 0; j < (arr.length - i - 1); j++){ if(arr[j] > arr[j + 1]){ let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }버블정렬의 성능 : Ο(n²)장점 : 이해와 구현이 간단함단점 : 성능이 좋지 않음 정렬 - 선택 정렬(Selection Sort)배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫번째 원소로 가져옴function SelectionSort(arr){ for(let i = 0; i < arr.length - 1; i++){ let minValueIndex = i; for(let j = i + 1; i < arr.length; j++){ if(arr[j] < arr[minValueIndex]){ minValueIndex = j; } } let temp = arr[i]; arr[i] = arr[minValueIndex]; arr[minValueIndex] = temp; } } 선택 정렬의 성능 : Ο(n²)장점 : 이해와 구현이 간단함단점 : 성능이 좋지 않음 그림으로 쉽게 배우는 운영체제CPU 스케줄링운영체제는 모든 프로세스에게 CPU를 할당/해제하는데 이를 CPU 스케줄링이라고 한다.CPU 스케줄링에서 스케줄러(운영체제)가 고려해야 할 사항 첫번째, 어떤 프로세스에게 CPU 리소스를 줘야하는가?두번째, CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야하는가?스케줄링 목표 리소스 사용률오버헤드 최소화공평성 처리량대기시간응답시간스케줄링 알고리즘 FIFO(First In First Out) Burst Time이 짧은게 먼저 실행되면 평균 대기 시간이 짧아진다.SJF(Shortest Job First) 문제1 : 어떤 프로세스가 얼마나 실행될지 예측 어려움문제2 : Burst Time이 긴 프로세스는 오랫동안 실행되지 않을 수도 있다RR(Round Robin) 한 프로세스에 일정 시간만큼 CPU 할당(타임 슬라이스)타임 슬라이스가 작을 경우 컨텍스트 스위칭이 너무 자주 일어나게 되어 오버헤드 발생여러 프로세스가 동시에 실행되는 것처럼 느껴지면서 오버헤드가 너무 크지 않은 값을 찾아야 함Windows는 20ms, Unix는 100msMLFQ(Multi Level Feedback Queue) 오늘날 운영체제에서 가장 일반적으로 사용RR의 업그레이드 버전CPU Bound Process들에게는 타임 슬라이스를 크게 준다. 프로세스 동기화 프로세스 간 통신의 종류한 컴퓨터 내에서 프로세스 간 통신 파일과 파이프 이용쓰레드 이용(한 프로세스 내에서 쓰레드 간 통신)네트워크 이용(소켓통신, RPC(원격 프로시저 호출))공유자원과 임계구역공유자원 여러 프로세스가 공유하고 있기 때문에 각 프로세스의 접근 순서에 따라 결과가 달라질 수 있음"동기화 문제" 발생임계구역 여러 프로세스가 동시에 사용하면 안되는 영역상호 배제 메커니즘 필요 임계영역엔 동시에 하나의 프로세스만 접근한다.여러 요청에도 하나의 프로세스의 접근만 허용한다.임계구역에 들어간 프로세스는 빠르게 나와야한다.세마포어(상호베제 메커니즘의 한 가지)프린터실(공유자원) 열쇠관리자(운영체제) 예시 -> "열쇠 = 세마포어"단점 : wait()함수와 signal()함수의 순서를 이상하게 호출해서 세마포어를 잘못 사용할 가능성이 있음모니터세마포어의 단점을 해결한 상호배제 메커니즘프로그래밍 언어 차원에서 지원하는 방법자바 : synchronized교착상태(데드락)교착상태의 필요조건상호배제비선점점유와 대기원형 대기교착상태 해결 방법교착상태 회피 교착상태가 발생하지 않는 수준의 자원 할당전체 자원과 할당된 자원의 수를 기준으로 안정상태와 불안정상태 구분은행원 알고리즘 교착상태 검출 가벼운 교착 상태 검출 타이머 이용프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착상태 발생 간주일정 시점마다 체크포인트를 만들어 작업 저장, 교착상태 발생했다면 마지막으로 저장했던 체크포인트로 롤백무거운 교착 상태 검출 자원 할당 그래프 이용프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생했다면 해결교착상태를 일으킨 프로세스 강제 종료, 다시 실행할 때 체크포인트로 롤백자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드 발생 메모리메모리 종류레지스터 가장 빠른 기억장소, CPU 내에 존재휘발성 메모리32bit 64bit캐시 메인메모리에 있는 값을 레지스터로 옮기려면 한참 걸리기 때문에 필요할 것 같은 데이터 미리 가져와 저장메인메모리(RAM) 운영체제와 프로세스들이 올라가는 공간휘발성 메모리보조저장장치(HDD, SSD) 비휘발성 메모리 메모리와 주소 메모리 = 메인메모리(RAM)물리주소와 논리주소 - 사용자절대주소와 상대주소 - 메모리 관리자메모리 할당 방식 메모리 오버레이(memory overlay) 프로그램을 잘라서 실행시켜야 할 부분만 메모리에 올리고 나머지는 하드디스크(스왑영역)에 저장가변 분할 방식(세그멘테이션) 프로세스의 크기에 따라 메모리를 나누는 방식연속 메모리 할당장점 : 낭비되는 공간인 '내부 단편화'가 없음단점 : 외부 단편화 발생(조각모음으로 해결, but 실행되고 있는 프로세스 중지해야 함 오버헤드 발생)고정 분할 방식(페이징) 프로세스 크기와 상관없이 메모리를 할당비연속 메모리 할당장점 : 구현이 간단, 오버헤드가 적음단점 : 내부 단편화 발생버디 시스템(가변 + 고정 혼합) 2의 승수로 메모리 분할각 단점 최소화

알고리즘 · 자료구조･워밍업･알고리즘･자료구조･운영체제･감자

1

인프런 워밍업 클럽 스터디 2기 CS 2주차 과제

운영체제FIFO 스케줄링의 장단점이 뭔가요?선입선출로 구현이 쉽고 오버헤드가 적다. 단, 매우 긴 CPU 연산 시간이 필요한 프로세스가 먼저 실행된다면, CPU 평균 실행 시간이 높아져 다른 프로세스 작업 시간에 악영향을 끼친다.SJF를 사용하기 여러운 이유가 뭔가요?Short Job First는 CPU 작업 시간이 짧은 프로세스를 먼저 실행시키지만, 프로세스의 CPU 작업 시간을 예측할 수 없기 때문에 현실적으로 불가능에 가깝다.RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?CPU가 실행중인 프로세스를 교체하는 작업인 컨텍스트 스위칭 비용이 빈번하게 발생하여 오버헤드가 크다.운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?주어진 타입 슬라이스보다 프로세스의 버스트 타임이 많다면 CPU 사용률과 처리량이 중요한 프로세스이다. 반대로 버스트 타임이 짧다면 I/O 응답속도가 중요한 프로세스이다.공유자원이란 무엇인가요?같은 컴퓨터에서 프로세스가 통신할 때 사용하는 파일 또는 파이프, 그 밖에 여러 작업들이 공유하여 사용하는 모든 것들은 공유 자원이라고 부른다.교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?임계구역에 하나의 프로세스만 접근한다.프로세스의 공유자원을 강제로 다른 프로세스가 선점할 수 없다.공유자원을 선점한 프로세스와 이를 기다리는 프로세스가 있다.서로에 작업을 기다리는 구조가 순환 구조를 이룬다. 자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?재귀적 호출을 탈출하지 못한다. 때문에 완료하지 못한 실행중인 함수를 메모리 콜스택에 추가되기만 한다. (사용 가능한 메모리를 초과)0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ if (n === 0) return 0; while (n % 2 === 0) { n -= 1; } return sumOdd(n - 1) + n; }

1

[인프런 워밍업 클럽 2기 - CS] 2주차 발자국

학습 내용스케쥴링의 목표와 FIFO부터 MLFQ에 이르기까지 어떤 시행착오를 거쳐서 스케쥴링 방식을 진화시켜 왔는지 확인햇습니다.공유자원가 임계구역 ,세마포어 모니터 와 같이 프로세스 동기화 에 관해 공부했습니다.재귀의 기본과 하노이탑 , 버블/선택 정렬에 대해서 공부했습니다.회고강의를 들었다 해도 미션에 대해서는 다시 생각하고 강의를 들어서 답을 작성해야 했는데 복습의 중요성을 역시 느꼇습니다.미션미션은 강의를 복습하며 작성했습니다.회고질문에 대한 답을 생각하면서 강의를 다시 보고 답변을 작성하는 것에서 복습의 효과를 본 것 같습니다.

1

[인프런 워밍업 클럽 2기 - CS] 2주차 미션

운영체재FIFO 스케쥴링의 장단점?장점First In First Out으로 직관적이고 알기쉽다. 단점먼저 들어온 시간이 오랜 작업시간을 소요하는 경우 평균 대기시간이 길어진다.I/O 작업 같은 것도 다른 작업이 끝날 때 까지 다른 작업을 못하게 되어 사용률이 떨어진다.SJF를 사용하기 여러운 이유가 뭔가요?어떤 스케쥴이 먼저 실행되는지 예측하기 어렵다.소요시간이 긴 프로세스가 뒤로 밀려나는 현상이 생긴다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?타임슬라이스가 아주 작으면 컨텍스트 스위칭이 너무 자주 일어나서 오버헤드가 발생할 수 있다.운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?타임슬라이스를 조금씩 늘려서 프로세스를 실행시키는데 금방 종료된다면 I/O , 실행도중 타임슬라이스를 초과해 강제로 CPU를 뺏긴다면 CPU이다.공유자원이란무엇인가요?각 프로세스가 통신을 할 때 공동으로 사용하는 변수나 파일들을 말한다.교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호배제 : 어떤 프로세스가 리소스 점유시 그 리소스는 다른 프로세스 사용하지 못해야 한다. (리소를 점유하는 상황)비선점 : 프로세스가 점유한 리소스를 다른 프로세스가 빼앗을 수 없다. (사용중인 리소스를 빼앗을 수 없는 상황)점유와 대기 : 프로세스가 이미 리소스를 점유한 상태에서 추가적인 리소스를 요청해야 한다. (다른 리소스를 기다리는 상황)원형 대기 : 점유와 대기 관계가 원형으로 형성되어야 한다. (서로가 기다리는 상황)해야할까요? 자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요? 함수가 무한히 실행되거나 의도치 않게 종료될 수 있음0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n) { if(n%2 == 0) { return sumOdd(n-1) } else { if(n==1) return 1; else return sumOdd(n-2)+n } } console.log(sumOdd(10))

1

인프런 워밍업 클럽 스터디 2기 - CS 미션 2

운영체제1. FIFO 스케줄링의 장단점이 뭔가요?장점 : 단순하고 직관적입니다.단점한 프로세스가 끝나야 다음 프로세스가 시작할 수 있기 때문에 실행시간이 짤은 프로세스가 실행시간이 긴 프로세스의 작업이 끝날 때까지 기다려야 합니다.I/O 작업이 있다면 I/O 작업이 끝날 떄까지 CPU가 쉬어야 하기 때문에 CPU 사용률이 감소합니다. 2. SJF를 사용하기 여러운 이유가 뭔가요?어떤 프로세스가 얼마나 걸릴지 예측하기 힘듭니다.Burst Time이 긴 프로세스는 오랫동안 실행되지 않을 수도 있습니다. 3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?프로세스 처리량보다 컨텍스트 스위칭 비용이 더 커질 수 있습니다. 오버헤드가 너무 커집니다. 4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?CPU를 사용하는 프로세스가 타임 슬라이스 크기를 초과해서 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황이면 CPU Bound Process라고 간주합니다.CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하면 CPU 사용이 적은 것 I/O Bound Process라고 간주합니다. 5. 공유자원이란 무엇인가요?프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일을 말합니다.공동으로 이용하기 때문에 연산결과 예측이 힘들어서 동기화 문제가 있을 수 있습니다. 6. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야 할까요?상호배제 : 어떤 프로세스가 한 리소스를 점유했다면 그 리소스는 다른 프로세스에게 공유가 되면 안 됩니다.비선점 : 프로세스 A가 리소스를 점유하고 있는데 프로세스 B가 리소스를 뺏을 수 없어야 합니다.점유와 대기 : 한 프로세스가 리소스 A를 가지고 있는 상태에서 리소스 B를 원하는 상태여야 합니다. 원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있어야 합니다. 자료구조와 알고리즘1. 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?콜스택 메모리 공간이 가득 차서 비정상적으로 함수가 종료될 수 있습니다. 2. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n) { if (n <= 0) { return 0; } if (n == 1) { return 1; } if (n % 2 == 0) { return sumOdd(n - 1); } return n + sumOdd(n - 2); } console.log(sumOdd(10)) // 25

1