두번째 발자국
알고리즘
재귀
재귀란 어떠한 것을 정의할 때 자기 자신을 참조하는 것
콜스텍이란 함수가 호출되면서 올라가는 메모리 영역으로 스택이라고도 부른다.
콜스택은 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 스케줄링
SJF
Shortest Job First
FIFO 에서 Burst Time이 짧은게 먼저 실행되면 평균 대기 시간이 짧아진다는 것을 발견하고
짧은 작업을 먼저 실행하면 된다는 발상에 의해 만들어짐.
문제점
프로세스 종료 시간 예측 불가능
Burst Time이 긴 프로세스는 실행이 안될 수도 있다.
RR
Round Robin
운영체제가 CPU 할당 시간을 지정해 현재 프로세스의 할당 시간이 지나면 다음 프로세스에게 CPU를 할당해주는 방법
이 CPU 할당 시간을 타임 슬라이스 or 타임 퀀텀이라고 부른다.
RR 알고리즘은 컨텍스트 스위칭이 있기에 비용이 더 발생할 수도 있다.
RR 알고리즘의 성능은 타임 슬라이스의 값에 따라 크게 달라진다.
타임 슬라이스를 너무 크게 설정하면 FIFO알고리즘과 같은 평균 대기 시간이 발생되고,
너무 작게 설정하면 실행되는 프로세스의 처리량보다 컨텍스트 스위칭의 비용이 더 커지게 된다.
그렇기에 사용자가 느끼기에 최적의 타임 슬라이스를 찾아야 한다.
Windows는 타임 슬라이스가 20ms, Unix는 100ms 정도이다.
MLFQ
Multi 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의 숭수로 동일하게 나눠서 반대로 조립만 하면 큰 공간이 만들어지기에 조각 모음보다 훨씬 간단하다.
이 방식의 장점은 가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라지고 외부 단편화를 방지하기 위헤 메모리 공간을 확보하는 것이 간단.
내부 단편화가 발생하기는 하지만 많은 공간의 낭비가 발생하지 않는다.
댓글을 작성해보세요.
