인프런 워밍업 클럽 CS 2기 - 2주차 발자국
자료 구조 및 알고리즘
재귀함수
재귀란 어떤것을 정의할 때 자기 자신을 참조하는 것을 의미한다.
즉, 재귀함수란 함수를 정의할 때 자기 자신을 참조하는 함수를 의미한다.
재귀 함수는 자기 자신을 호출하므로 만약 기저 조건을 정의하지 않은경우 메모리를 다 사용할 때 까지 호출된다.
함수가 호출되면 메모리의 콜스택에 올라가고, 함수가 종료되면 메모리의 콜스택에서 제거된다.
그래서 재귀 함수의 기저조건을 작성하지 않거나 잘못 작성할 경우, 재귀함수가 종료되지 않아 재귀 함수가 메모리의 콜스택 영역에 존재하고 결국 메모리 공간을 가득 채워 스택 오버플로우가 발생해 프로그램이 강제 종료된다.
재귀적으로 생각하기
재귀 함수는 재귀적으로 함수를 호출하기 때문에 메모리를 차지하는 비효율적인 방법으로 보일 수 있다.
그러나 하위 문제 해결방법을 기반으로 문제를 해결하는 하향식 방식으로 효율적으로 문제를 해결할 수 있다.
팩토리얼
function factorial (number) {
if (number === 1) return 1;
if (number <= 0) return 0;
return number * factorial(number - 1)
}
console.log(factorial(5))
문자열 길이 확인
function strLength (str) {
if (str.length === 0) return 0;
return strLength(str.slice(0, -1)) + 1
}
console.log(strLength('string'))
지수함수
function power (x, n) {
if (n === 0) return 1;
return x * power(x, n - 1)
}
console.log(power(2, 5))
하노이의 탑
3개의 기둥에 3개의 원판을 옮기려고 할 때, 재귀적인 하향식 방법으로 문제를 해결할 수 있다.
원판을 count라고 정하고 아래의 접근방법을 따른다.
출발지 기둥에 있는 (count - 1)개의 원판을 임시 기둥에 옮긴다.
출발지 기둥에 있는 1개의 원판을 목적지 기둥에 옮긴다.
임시 기둥에 있는 (count - 1)개의 원판을 목적지 기둥에 옮긴다.
... 반복
그리고 옮기려는 원판이 없다면 함수를 종료하는 기저조건을 추가한다.
위의 하위 문제 해결방법으로 전체 문제를 해결할 수 있다.
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')
버블 정렬
정렬되지 않는 배열의 숫자 원소들을 정렬하는 알고리즘이다.
해당 알고리즘은 이중 for 반복문을 사용하므로 시간복잡도가 O(n²) 이다.
index 위치에 있는 숫자, index + 1 위치에 있는 숫자를 비교하여, index 위치에 있는 숫자가 더 크다면 원소 위치를 바꾼다.
function bubbleSort (arr) {
for (let i=0; i<arr.length; i++) {
for (let j=0; j<arr.length-i-1; j++) {
if (arr[j] > arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
}
return arr;
}
console.log(bubbleSort([3,1,2,4]))
선택 정렬
정렬되지 않는 배열의 숫자 원소들을 정렬하는 알고리즘이다.
해당 알고리즘은 이중 for 반복문을 사용하므로 시간복잡도가 O(n²) 이다.
배열의 원소들을 하나씩 확인하면서 가장 작은 값을 찾아 출발지의 index1, 가장 작은 원소의 index2 를 찾아 위치를 바꿔준다.
function selectionSort (arr) {
for (let i=0; i<arr.length-1; i++) {
let minIdx = i;
for (let j=i; j<arr.length; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
}
return arr;
}
console.log(selectionSort([3,1,2,4]))
미션1
재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?
함수가 호출되면 메모리의 콜스택 영역에 올라가고 함수가 종료되면 콜스택 영역에서 제거됩니다.
만약 기저조건을 만들지 않거나 잘못 설정할 경우, 함수가 메모리의 콜스택 영역에 존재하고 결국 메모리 공간을 가득 채워 스택 오버플로우가 발생해 프로그램이 강제 종료됩니다.
2. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.
function recursionOdd (n) {
if (n === 0) return 0;
return n % 2 === 1 ? n + recursionOdd(n - 1) : recursionOdd(n - 1);
}
console.log(recursionOdd(10)); // 25
자료 구조 및 알고리즘
SJF(Shortest Job First)
FIFO 스케줄링의 단점을 보안하기 위해 도입되어 Burst Time이 짧은 프로세스가 가장 먼저 실행된다.
문제는 Burst Time을 예측하기 어렵고, Burst Time이 긴 프로세스의 경우 무한정 대기할 수 있는 문제점이 있다.
RR(Round Robin)
CPU를 일정 시간만큼 할당하는 시간을 타임 슬라이스 또는 타임 퀀텀이라고 부른다.
기존의 FIFO 스케줄링의 평균대기시간을 보완하고자 CPU를 일정시간만큼 프로세스에 할당하여 평균대기시간을 낮춘다.
RR은 타임슬라이스에 따라 성능이 결정된다.
타임 슬라이스를 길게 잡으면 FIFO 스케줄링이 된다.
타임 슬라이스를 짧게 잡으면 프로세스간 컨텍스트 스위칭이 자주 발생해, 프로세스 처리량보다 컨텍스트 스위칭 처리량이 더 큰 문제점이 생깁니다.
MLFQ(Multi Level Feedback Queue)
RR 스케줄링을 보완한 방법으로 CPU Bound Process와 I/O Bound Process를 구분하여 우선순위 큐에 프로세스를 넣어 필요로하는 CPU 시간만큼 타임슬라이스를 정해 효율을 증가시켰다.
CPU Bound Process는 CPU 연산이 많이 필요한 프로세스이고, I/O Bound Process는 입출력 작업이 많이 필요한 프로세스이다.
운영체제가 구분하는 방법은 단순하게 타임 슬라이스로 구분한다.
만약, 타임 슬라이스만큼 CPU를 할당했을 때 운영체제에 의해 CPU를 빼앗기게 되면 상대적으로 CPU 연산이 많으므로 CPU Bound Process 이다.
만약, 타임 슬라이스보다 먼저 CPU를 반환하는 프로세스는 상대적으로 CPU 연산이 적으므로 I/O Bound Process 이다.
프로세스간 통신 방법
하나의 컴퓨터에서 프로세스간 통신
공유하고 있는 하나의 파일을 읽고 쓰기를 통해 프로세스간 통신한다.
운영체제가 생성한 파이프를 통해 프로세스간 통신한다.
외부 컴퓨터에 있는 프로세스간 통신
네트워크를 통해 운영체제가 제공하는 소켓 통신을 통해 프로세스간 통신한다.
RPC(원격 프로세스 호출)을 통해 프로세스간 통신한다.
🏷 프로세스 내부의 쓰레드는 Code 영역, Data 영역 그리고 Heap 영역을 공유하고 있으므로 이것은 쓰레드간 통신한다고 볼 수 있다.
공유자원과 임계구역
프로세스간 통신을 할 때 공유해서 사용하는 변수나 파일이다.
동시에 여러 프로세스가 사용하지 않는 영역을 임계구역이라고 한다.
그리고 공유 자원을 사용하기 위해 프로세스간 경쟁하는 조건을 경쟁조건이라고 한다.
만약 여러 프로세스가 사용할 경우 동기화 문제가 발생한다.
여러 프로세스가 사용하게되면 프로세스가 반환한 결과값을 사용하지 않고 상태에서 이전의 값을 사용하여 원하는 결과를 만들 수 없는 문제가 발생한다.
이 문제를 상호배제의 요구사항을 충족하는 방법으로 해결한다.
임계구역엔 하나의 프로세스만 접근한다.
여러 프로세스의 요청에도 단 하나의 프로세스만 접근가능하다.
공유자원을 다른 프로세스도 사용해야하므로, 임계구역에 접근한 프로세스는 최대한 빠르게 나와야한다.
상호배제의 요구사항을 충족하는 방법은 아래와 같다.
세마포어
모니터
세마포어
프로세스는 대기 큐에 대기하고, 운영체제가 세마포어를 프로세스에게 전해주어 자원을 사용하는 프로세스가 작업을 끝날 때 까지 다른 프로세스는 세마포어가 없기 때문에 공유자원에 접근하지 못한다.
세마포어는 정수형 변수이고, 여러개를 설정할 수 있다.
세마포어의 단점은 코드로 구현할 때 순서를 잘못 작성하면, 세마포어를 잘못 사용할 가능성이 존재한다.
모니터
프로그래밍 언어에서 지원해주는 것이로, 편리하고 안전하게 사용가능하다.
Java 프로그래밍 언어의 경우, synchronized 키워드를 함수 선언할 때 사용하여 synchronized 키워드가 선언된 함수들은 동시에 사용하지 못한다.
데드락
여러 프로세스가 서로 다른 프로세스의 작업이 끝나 해당 프로세스가 사용하던 자원을 사용하기 위해 끊임없이 기다리고 교착상태에 빠진 상태를 데드락이라고 한다.
교착상태의 필요조건 4가지
상호배제 : 하나의 프로세스가 자원을 사용하고 있다면 다른 프로세스는 해당 자원을 사용할 수 없다.
비선점 : 하나의 프로세스가 자원을 사용하고 있다면 다른 프로세스는 해당 자원을 빼앗을 수 없다.
점유와 대기 : 프로세스가 자원을 사용하면서 다른 자원을 원해야한다.
원형 대기 : 점유와 대기하는 프로세스들이 서로 원형 관계를 이루어야 한다.
데드락 해결 방법
교착상태 회피란, 운영체제가 교착상태에 빠지지 않을 만큼 프로세스에 자원을 할당한다.
교착상태 회피는 전체 자원의 수, 할당한 자원의 수에 따라 안정상태, 불안정상태로 나뉜다.
운영체제는 안정상태를 유지하기 위해 적절한 자원의 수를 프로세스에 할당해준다.
교착상태 회피
안정상태
프로세스는 자신이 요규하는 최대 자원의 수를 운영체제에게 알려주는데, 프로세스에 할당하고 사용가능한 자원의 수보다 프로세스가 요구하는 자원의 수가 많을 경우 운영체제는 거부한다.
만약 프로세스가 요구하는 자원의 수가 적을 경우 운영체제는 자원을 할당해주고, 할당해준 프로세스가 작업을 마친 후 자원을 반환하고 다른 프로세스에게 자원을 분배한다.
이처럼 프로세스의 최대 자원 요구량에 자원을 할당해줄 수 있을 만큼 사용가능한 자원 수를 갖고 있는 상태를 안정상태라고 한다.
불안정상태
프로세스에 할당하고 사용가능한 자원의 수보다 프로세스가 요구하는 자원의 수가 많을 경우 운영체제는 거부하는데, 사용 가능한 자원이 하나의 프로세스라도 최대 요구량에 미치지 못할 경우를 불안정상태라고 한다.
사람들은 교착상태를 회피하는 것 보다, 교착상태에 빠질 경우 해결하는 방식으로 넘어갔다.
교착상태를 해결하는 방법은 2가지가 있는데, 가벼운 교착상태 검출, 무거운 교착상태 검출이 있다.
교착상태 해결
가벼운 교착상태 검출
타이머를 이용하여 일정시간 프로세스가 작업을 진행하지 않을 경우 프로세스의 마지막 체크포인트로 롤백한다.
무거운 교착상태 검출
운영체제가 자원 할당 그래프를 이용하여 순환구조를 이루는 그래프를 확인하여 프로세스를 종료하고, 마지막 체크포인트로 롤백한다.
운영체제가 자원 할당 그래프를 운영하고, 검사해야하기 때문에 오버헤드가 발생하는 단점이 있지만, 타이머로 인해 억울하게 종료되는 프로세스가 없다는 장점이 있다.
메모리 종류
레지스터
CPU가 처리하기 위해 메인메모리에 있는 값을 레지스터로 가져와 계산을 하고, 결과값을 메인메모리에 저장한다.
CPU 구분시 32Bit, 64Bit는 레지스터의 크기를 뜻한다.
레지스터는 CPU에 존재한다.
전력이 끊기면 데이터가 사라지는 휘발성 메모리이다.
캐시
메인메모리의 있는 값을 레지스터로 가지고 올 때, 성능을 위해 미리 값을 가져온다.
캐시는 CPU에 L1, L2, L3... 등으로 존재한다.
전력이 끊기면 데이터가 사라지는 휘발성 메모리이다.
메인메모리(RAM)
운영체제나 프로세스가 올라가는 공간이다.
전력이 끊기면 데이터가 사라지는 휘발성 메모리이다.
보조저장장치(HDD, SDD)
전력이 끊겨도 데이터가 유지되는 비휘발성 메모리이다.
파일, 데이터를 저장하는 공간이다.
가격 : 레지스터 > 캐시 > 메인메모리 > 보조저장장치
용량 : 레지스터 < 캐시 < 메인메모리 < 보조저장장치
속도 : 레지스터 > 캐시 > 메인메모리 > 보조저장장치
메모리를 분리했기 때문에 속도가 빠르면서 저렴하게 컴퓨터를 사용할 수 있다.
메모리 주소
운영체제는 메모리를 관리하기 위해 1Byte(8bit) 크기로 구역을 나누고 숫자를 매긴 것을 메모리 주소라고 한다.
CPU의 레지스터의 크기가 클수록 사용가능한 메인메모리의 크기가 커지고, 처리가능한 양이 늘어 속도도 빠르다.
64Bit : 2^64 의 메인메모리 사용 가능
32Bit : 2^32 의 메인메모리 사용가능(4GB까지)
사용자의 프로세스가 운영체제가 실행되는 메모리 영역을 침범할 경우 악의적인 접근으로 문제가 발생할 소지가 있다.
그래서 운영체제가 실행되는 메모리 공간과 사용자가 실행하는 프로세스 공간을 물리적으로 구분하기 위해 경계 레지스터가 생겼다.
경계 레지스터는 CPU에 존재하고, 메모리 관리자가 사용자 프로세스가 침범했을 경우 해당 프로세스를 종료시킨다.
메모리 주소는 물리 주소, 논리 주소로 구분된다.
물리 주소란 컴퓨터 관점에서의 실제 메모리 주소이고, 논리 주소는 사용자 관점에서의 메모리 주소이다.
사용자가 개발한 프로그램은 0x0번 주소로 시작한다는 전재로 개발을 하고, 사용자가 메모리 주소(논리 주소)로 접근할 때 CPU는 메모리 관리자에게 주소를 요청하고 메모리 관리자는 실제 메모리 주소(물리 주소)를 반환해준다.
이를 통해 사용자는 저장될 메모리 주소를 고려하지 않고 편리하게 프로그램을 개발할 수 있다.
메모리 할당
하나의 프로세스가 메모리에 올라오는 유니 프로그래밍 환경에서 실제 메모리보다 더 큰 메모리를 요구하는 문제가 발생했다.
프로세스에서 실행에 필수적인 일부만 메모리에 올리고 나머지는 보조저장장치의 스왑 공간에 저장한다. 이 기법을 오버레이라고 한다.
오늘날과 같이 멀티 프로그래밍 환경에서는 메모리 크기를 나누었는데, 2가지 방법으로 나누어서 이 문제를 해소했다.
가변 분할 방식(세그멘테이션)
프로세스가 요구하는 메모리 공간 만큼 메모리를 나누어서 메모리를 할당한다.
프로세스가 순서대로 메모리에 할당되는데, 연속 메모리 할당이라고 한다.
장점은 낭비되는 메모리 공간이 없다.(내부 단편화 없음)
단점은 메모리 할당된 2개의 프로세스가 종료되고 2개의 프로세스의 요구하는 만큼 메모리 공간을 요구하는 프로세스가 발생할 경우, 실행중인 프로세스를 종료하고 메모리를 합쳐야하는 오버헤드가 발생한다.(외부 단편화)
고정 분할 방식(페이징)
고정된 메모리 크기로 메모리를 분할 하여 프로세스에 할당한다.
프로세스가 비연속적으로 메모리에 할당되는데, 비연속 메모로 할당이라고 한다.
장점은 구현이 단순하고, 오버헤드가 적다.
단점은 낭비되는 메모리 공간이 있다.(내부 단편화)
버디 시스템
세그멘테이션과 페이징을 혼합하여 단점을 최소화했다.
2의 승수로 메모리를 분할해 메모리를 할당한다.
예를 들어 메모리의 크기가 2048byte 이고 프로세스가 요구하는 메모리 공간이 500byte 인 경우 2의 승수로 요구되는 메모리 공간의 크기에 알맞는 크기로 메모리를 할당(512byte)한다.
이경우 낭비되는 메모리 공간을 최소한으로 줄이고, 프로세스가 종료되어도 메모리가 근접하므로 메모리를 합칠 때 발생하는 오버헤드를 최소화 하여 내부 단편화와 외부 단편화를 최소화했다.
미션2
FIFO 스케줄링의 장단점은 무엇인가요?
가장 먼저 들어온 프로세스가 먼저 실행되고, 늦게 들어온 프로세스는 나중에 실행되기 때문에 단순하고 직관적인게 장점입니다.
Burst Time이 긴 프로세스가 가장 먼저 들어왔고 Burst Time이 짧은 프로세스가 늦게 들어왔다면, 앞의 프로세스의 작업이 끝날 때 까지 뒤의 프로세스가 기다려야합니다. 또한, I/O 작업이 포함된 프로세스의 경우 CPU가 대기해야하는 시간이 있기 때문에 CPU 사용률이 떨어지는 단점이 있습니다.
SJF를 사용하기 여러운 이유가 뭔가요?
Burst Time이 가장 짧은 프로세스를 먼저 실행해야하는데 프로세스의 작업 시간을 예측하기가 어렵고, 만약 Burst Time이 긴 프로세스는 Burst Time이 짧은 프로세스로 인해 무한정 작업이 늦춰질 수도 있는 어려움이 있습니다.
RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?
여러개의 프로세스를 실행시키기 위해 컨텍스트 스위칭이 발생하는데, 만약 타임 슬라이스가 아주 작으면 프로세스 처리량보다 컨텍스트 스위칭 처리량이 더 커져셔 비효율적인 문제가 발생합니다.
4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?
프로세스가 CPU 연산을 많이하면 CPU Bound Process이고, 프로세스가 I/O 작업을 많이하면 I/O Bound Process입니다.
운영체제가 구분하는 방법은 단순하게 타임 슬라이스로 구분합니다.
타임 슬라이스만큼 CPU를 할당했을 때 운영체제에 의해 CPU를 빼앗기게 되면 상대적으로 CPU 연산이 많으므로 CPU Bound Process
타임 슬라이스보다 먼저 CPU를 반환하는 프로세스는 상대적으로 CPU 연산이 적으므로 I/O Bound Process
5. 공유자원이란무엇인가요?
프로세스간 통신을 할 때 공유해서 사용하는 변수나 파일입니다.
교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?
4가지 조건이 모두 충족되어야 교착상태에 빠질 수 있습니다.
상호배제 : 하나의 프로세스가 자원을 사용하고 있다면 다른 프로세스는 해당 자원을 사용할 수 없습니다.
비선점 : 하나의 프로세스가 자원을 사용하고 있다면 다른 프로세스는 해당 자원을 빼앗을 수 없습니다.
점유와 대기 : 프로세스가 자원을 사용하면서 다른 자원을 원해야합니다.
원형 대기 : 점유와 대기하는 프로세스들이 서로 원형 관계를 이루어야 합니다.
댓글을 작성해보세요.
