Tech Log 🛠️

CISC란?

CISC(Complex Instruction Set Computer)란 많은 수의 다양하고 중복되는 명령어 집합이다.

*명령어 집합:CPU가 이해할 수 있는 명령어들의 모음

사용자가 이해할 수 있는(고급 언어) 하나에 각기 다른 기계 명령어를 대입 시킴으로써 명령어수가 많고 가변 길이를 가진다.

명령어 수가 많고 상대적으로 적은 수의 명령어로도 프로그램을 실행할 수 있다. (메모리 사용이 적다.)

CISC의 명령이의 길이가 고정되어 있지 않은 이유는 각각의 명령어가 프로세싱 성능을 극대화하도 록 설계되었기 때문이다.

하지만 명령어의 수가 많다고 하더라고 실제로는 쓰이는 명령어들만 주로 쓰이고 명령어를 사용해서 메모리 파이프라이닝이 불리하다는 단점이 있다. 또한 상대적으로 많은 전력을 소모한다.

특징

1. 강력한 기능을 수행하는 다양한 명령어들이 있다.

2. 상대적으로 메모리를 적게 소비한다.

4. 가변 길이 명령어를 사용한다.

5. 명령어가 실행되는 데 하나 이상의 클럭 주기를 가진다.

6. 다양한 주소 지정 방식을 사용한다.

7. 컴파일 과정이 쉽고 호한성이 좋다.

단점

1. 명령어 실행 시간이 파이프라인을 만들기에 불리하다.

2. 상대적으로 많은 전력을 소비한다.

RISC란?

RISC(Reduced Instruction Set Computer)란 축소된 명령어의 집합이다.

CISC와는 여러 차이점이 있는데 대표적으로 명령어의 수가 100개 미만으로 줄어들었다. 인식 가능한 명령어의 수를 줄임으로써 속도를 향상시키지만 프로그램을 실행 시키는데 더 많은 명령어가 필요하다.

RISC는 신속한 프로세싱을 달성하기 위한 파이프라인 프로세싱의 일환으로서 고정길이 명령어를 사용하며,CISC와 달리 클럭 주기당 하나의 명령어를 실행한다. 단일 사이클의 명령어를 실행함으로써 명령어 실행 과정을 파이프라인으로 구현할 수 있다. 

특징

1. 모든 데이터 처리는 레지스터에서 수행되며 load-store 구조를 사용하여 메모리 접근을 최소화하였다.

2. 단순한 고정 길이 방식의 명령어를 사용한다.

3. 적은 주소 지정 방식을 사용한다.

단점 

1. 컴파일러의 최적화 과정이 복잡하다.

2. 명령어가 고정되어 있어서 코드 효율이 낮다.

3. 파이프라인 해저드에 대한 조치가 필요하다.

결론

둘 다 장단점을 보유하고 있어서 어느 쪽이 성능 면에서 우세하다고 볼 수는 없다. 

또한 오늘날의 몇몇 CISC MCU는 RISC의 장점을 일 부 공유하고 있으며, 몇몇 RISC MCU는 CISC의 장점 을 일부 공유하고 있기 때문에 각자의 상황에 맞는 선택이 필요하다.

커널이란?

커널이란 운영체제 내부에서 자원들을 관리하고 추상화 해준다. 이 덕분에 사용자는 내부 하드웨어에 직접 접근하지 않고도 간편하게 프로그램을 실행할 수 있다. 여기서 자원은 CPU, 메모리 , 입출력 장치 같은 것들을 나타낸다.

또한 커널은 자원을 관리하기 위한 여러 관리자들이 있다.

1. 테스트 관리자 : 물리적 자원인 CPU를 추상 자원인 테스크로 제공한다.
2. 메모리 관리자 : 물리적 자원인 메모리를 추상 자원인 페이지나 세그먼트로 제공한다.
3. 파일 시스템 관리자 : 물리적 자원인 디스크를 추상 자원인 파일로 제공한다.
4. 네트워크 관리자 : 물리적 자원인 네트워크 장치를 추상 자원인 소켓으로 제공한다.
5. 디바이스 드라이버 관리자 : 각종 외부 장치(프린터, GPU 등)에 대한 접근을 제공한다.

커널의 동작 방식

커널은 Memory Resident 한 프로그램이다. 일반적으로 프로그램들은 디스크에 상주해있는데, 커널은 메모리에서 여러 명령들을 처리한다. 

하지만 커널은 사용자의 명령을 직접적으로 받지 않고 쉘이란 프로그램을 통해서 명령을 전달받는다. 즉 쉘을 통해서 커널에게 명령을 내릴 수 있는 것이다.

쉘의 역할

프로그램들이 언제 메모리에 로딩되고 해제되는지 관리해주는 프로그램이다. 여러 프로그램들의 메모리를 관리해주며 커널의 중간다리 역할을 수행하기도 한다.

일반적으로 운영체제가 부팅되면 Memory Resident한 특성을 가지는 커널이 먼저 메모리에 올라온다.

그 후 유저가 터미널을 실행하면 쉘이 메모리에 올라오고 유저가 입력한 커맨드에 맞는 잡(job)을 메모리에 올린다.

이런 과정으로 유저는 프로그램을 내부적인 구조를 신경쓰지 않고 실행시킬 수 있는 것이다.

하지만 이런 리눅스 환경은 신경써야 할 점이 하나 있다. 바로 멀티유저 시스템이라는 점이다.

윈도우는 개인pc용 운영체제여서 보안에 대한 부담이 리눅스에 비해 적을 수 있지만, 여러 사용자가 이용하는 리눅스는 보안을 특별히 더 신경써야한다.

만약 유저A가 유저B의 파일에 맘대로 접근할 수 있다면 어떨까? 이는 심각한 문제를 초래할 수 있다. 

따라서 운영체제는 커널모드와 유저모드를 나누어서 입출력 작업 같이 자원에 접근하는 일들은 커널에서 담당하도록 하였다.

이때 커널에게 해당 작업을 요청하는 것을 시스템 콜이라고 한다.

유저 모드에서 시스템 콜이나 인터럽트가 발생하게 되면 커널 모드로 진입한다.

시스템 콜의 종류는 다음과 같은 역할들을 수행한다.

프로세스/스레드 관련 처리

파일 I/O 관련 처리

소켓 관련 처리

디바이스 관련 처리

프로세스 통신 관련 처리

물론 모든 커맨드에 대해서 시스템 콜이 커널로 명령을 전달해주면 이는 무용지물일 것이다. 그래서 해당 명령이 적합한 명령인지를 판단하는 바이너리 비트를 CPU에 두는데, 이를 mode bit라고 한다. 1이면 커널모드 0이면 유저모드라고 알려져있다.

커널모드에서는 모든 자원에 대한 접근이 가능한데 이때 I/O 같은 작업들을 수행하고 시스템 콜의 리턴값으로 해당 작업에 대한 결과를 받는다. 그리고 해당 작업이 종료되면 다시 유저모드로 돌아가서 프로그램을 실행한다. 이 작업이 한번만 진행되는 건 아니고 프로그램이 실행되면서 수없이 커널모드와 유저모드를 왔다갔다한다.

인터럽트란

앞서 인터럽트가 발생하였을 때 커널 모드로 진입한다고 하였다. 이 때 인터럽트는 무엇이고 왜 발생할까? 

인터럽트는 시스템에서 발생한 다양한 종류의 이벤트 혹은 그런 이벤트들이 발생했을 때 알려주는 메커니즘이다.

인터럽트들이 발생하면 CPU에서는 인터럽트 처리를 위해 커널 모드로 진입한다.

하드웨어 혹은 프로그램이 인터럽트 라인에 인터럽트를 세팅하면 인터럽트가 발생한다. 이때 인터럽트 벡터를 통해 인터럽트 서비스 루틴을 실행해서 인터럽트를 처리한다.

인터럽트 벡터

인터럽트 서비스 루틴(핸들러)의 주소를 담고 있는 테이블

인터럽트 서비스 루틴

실제 인터럽트를 처리하기 위한 루틴

참고로 프로그램 레벨에서 발생하는 인터럽트는 트랩이라고 불리며 하드웨어 인터럽트보다 우선 순위가 높다.

외부 인터럽트

전원에 문제가 생겼을 때

I/O 작업이 완료되었을 때

타이머 시간이 끝났을 때

내부 인터럽트

0으로 나눴을 때

잘못된 메모리 공간에 접근을 시도할 때

소프트웨어 인터럽트

프로그램 처리 중 명령의 요청에 의해 발생하는 데, 대표적으로 SVC에 의한 call이 있다.

인터럽트는 다음과 같은 우선 순위를 가진다.

1. 전원 이상(Power fail)
2. 기계 착오(Machine Check)
3. 외부 신호(External)
4. 입출력(I/O)
5. 명령어 잘못
6. 프로그램 검사(Program Check)
7. SVC(SuperVisor Call)

시스템 콜 & 인터럽트의 동작 과정(예시)

싱글 코어 환경에서 쓰레드1(t1)과 쓰레드2(t2)가 있다고 가정해보자

t1에서 file read 요청이 들어왔다.

이때 file read에 해당하는 시스템 콜이 호출되며 기존 t1의 상태를 저장하고 커널 모드로 진입한다.

커널모드에 진입한 t1은 해당 file이 read 가능한 상태가 될때까지 waiting 하게 되며 다시 유저 모드로 진입 후 t2가 실행되게 된다.

t1에서 요청한 file이 read 요청을 처리할 준비가 되었다.

이때는 아까와 다르게 시스템 콜이 아닌 인터럽트가 호출된다. 다시 CPU는 t2의 상태를 저장하고 t1을 waiting에서 ready(runnable)로 상태를 바꾼다. 그런 다음 유저모드로 진입 후에 t2를 실행한다.

모종의 이유로 t2의 CPU 점유가 중단되는 일이 생길 것이다.

CPU는 다시 커널 모드로 진입 후에 t2를 ready 상태로 바꾼다. 이제는 t1을 실행 상태로 바꾸고 작업들을 처리하면 된다.

하지만 사용자는 직접적으로 시스템 콜을 호출할 일이 없는데 이는 하이(high) 레벨 언어가 시스템 콜을 호출할 수 있도록 래핑(wrapping)을 통해 제공하기 때문이다. 대표적으로 스레드를 start 할 때 native 코드를 통해서 JNI(Java Native Interface)가 해당 운영체제에 맞는 시스템 콜을 호출해준다.

private native void start0();

0. 만약 인덱스가 없었다면

인덱스 없이 테이블에 대한 탐색을 한다고 가정해보자

num의 값이 27인 행을 찾는 다고 가정했을 때 인덱스가 없다면 , 정렬 되지 않은 데이터를 처음부터 찾아야한다.

이럴 경우 하나의 데이터를 찾기 위해서 최악의 경우 모든 값을 탐색하는 풀 스캔을 해야할 수도있다.

이는 매우 비효율적인 방법이다.

인덱스가 없는 경우 어떤 현상이 일어나는 지 알아보았으니, 그럼 이제 인덱스가 적용 된 경우를 살펴보자

처음 예시와의 차이점은 데이터가 정렬되어 있고 무작정 처음부터 조회하지 않는다.

이 경우 정렬된 데이터들로부터 인덱스를 통해 탐색하므로 효율적인 탐색이 가능해진다.

이제 우리는 인덱스를 통해 효율적인 탐색이 가능해진다는 것을 알았다.

바로 이 인덱스가 오늘 배워볼 주제이다.

어떻게 인덱스를 통해 효율적인 탐색이 가능하고, 어떻게 하면 효율적으로 인덱스를 사용할 수 있을 지 알아보자

1. 인덱스가 필요한 이유

테이블의 검색 성능을 높여주는 자료구조이다.

인덱스를 쓰게 되면 추가적인 쓰기 작업과 저장 공간을 활용하므로 탐색 속도를 높일 수 있다.

예시를 포함해서 지금까지의 설명으로 인덱스의 특징을 정리해볼 수 있다.

• 인덱스의 데이터는 정렬되어 있다.
• 인덱스는 추가적인 저장 공간을 필요로 한다.
• 인덱스를 사용해서 효율적인 탐색이 가능해진다.

여기까지만 들어도 인덱스가 무엇이고 어떤 장점이 있는 지 대략 파악되었을 것이다.

데이터베이스 쪽으로 좀 더 들어가서 구체적으로 왜 필요한 지 알아보자

2. 인덱스의 동작 방식

mySQL의 공식 문서를 보면 다음과 같이 나와있다.

Indexes are used to find rows with specific column values quickly. Without an index, MySQL must begin with the first row and then read through the entire table to find the relevant rows.

크게 두 가지로 요약할 수 있다.

1. 조건에 맞는 데이터를 빠르게 검색하기 위헤
2. 데이터를 빠르게 정렬하거나 그룹핑 하기 위해

예를 들어,

SELECT * FROM team WHERE name = ‘sehan’;

DELETE FROM logs WHERE datetime < ‘2023-06-16’;

UPDATE employee SET salary = salary * 1.5 WHERE id = 100;

SELECT * FROM team T JOIN department D ON [T.id](<http://T.id>) = D.id;

각각의 쿼리에는 조건들이 포함되어 있다.

따라서 해당 쿼리들이 실행되면 조건에 맞는 데이터들을 찾아야한다.

하지만 이 경우 테이블의 데이터가 중간이나 끝에 있다면 풀스캔을 해야하는 상황이 된다.

이를 보완하기 위해 인덱스는 별도의 자료구조 및 작업을 실행하여 테이블 탐색 성능을 향상시켜준다.

즉 테이블의 데이터, 조건들을 빠르게 찾기 위해 필요한 것이 인덱스이다.

또한 인덱스는 조인을 할 때 조인을 하기 위한 조건을 빠르게 찾기 위해 사용되기도 한다.

무조건 Select 에서만 필요한 것이 아닌 조건 탐색을 위해서든 단순 데이터 탐색을 위해서든 인덱스는 사용될 수 있다.

3. 인덱스의 종류

그렇다면 인덱스는 어떻게 동작할까?

인덱스의 자료구조

인덱스를 구현하기 위한 자료구조로는 크게 두가지가 있지만 , 대표적으로 B-tree 와 B+tree 가 있다.

마지막엔 추가로 해시에 대해서도 알아볼 것이다.

B-tree,B+tree 에서 ‘B’의 의미는 정확히 밝혀진 바는 없지만 균형을 맞춘다는 의미에서 Balanced 라는 의미로 통한다.

균형을 맞춤으로써 좀 더 빠른 인덱싱이 가능해진다.

만약 자식노드들이 Balanced 하지 않다면 어떻게 될까?

트리가 편향되어 있는 BST(이진 탐색 트리)모습을 상상해보자

BST는 균형을 맞추지 않기 때문에 위와 같은 모습이 나올 수 있다. 

최악의 경우에는 O(n)의 시간 복잡도가 나오는데 B tree는 트리의 균형을 맞춤으로써 시간 복잡도를 줄여준다.

이는 BST는 최대 2개의 자녀 노드를 가지지만 B tree는 여러개의 자녀노드를 가질 수 있기 때문에 가능하다.

B-Tree

B-tree 는 항상 데이터가 정렬되어 있다는 특징이 있다.

때문에 어떤 데이터를 탐색하더라도 O(logN)의 시간 복잡도를 가진다.

그리고 모든 리프 노드들은 같은 레벨에 있으며 따라서 Balanced 되었다 라고 할 수 있다.

B-tree의 구성을 살펴보자, 노드는 키값과 리프 노드에 대한 포인터로 구성되어 있다.

각 key들의 왼쪽 자식들은 key보다 작은 값 ,오른쪽 값은 key보다 큰 값으로 되어있다.

B-tree 구조의 데이터 탐색 과정을 알아보자

현재 데이터에서 정수 27 데이터를 찾아보려고 한다.

먼저 27은 31보다 작으므로 왼쪽 자식노드로 이동한다.

그 다음 11, 29와 데이터를 비교하게 되는데 이 중간값이라는 것을 알 수 있다.

따라서 가운데에 있는 자식 노드로 탐색을 하게되고 27을 발견하게 되면서 탐색이 끝난다.

이렇게 균형 있는 트리 구조를 통해 특정 데이터를 효율적으로 찾을 수 있다.

하지만 모든 경우에서 베스트인것은 아니다.

선형 탐색(Full scan)의 경우 모든 데이터를 다 탐색하므로 O(n)의 시간 복잡도를 가진다.

이 경우 뒤에서 살펴볼 B+tree 라는 것을 통해서 Full scan시 효율을 개선할 수 있다.

삽입

삽입의 경우 조회 방식과 통일하게 Leaf Node들을 탐색하고 노드 자리가 비어있다면 해당 자리에 노드를 삽입 , 꽉 차 있다면 노드를 분할해서 삽입한다.

예제를 통해 13 데이터를 넣을려고 한다고 가정해보자

탐색의 결과, 12와 14 사이의 값에 배정되었다. 하지만 해당 Leaf Node는 노드가 꽉 찬 상태이다.

따라서 부모 노드에 데이터를 넣어주었다.

이렇게 되면 부모 노드도 꽉 찬 상태가 되므로 중앙값인 11로 데이터를 분할해준다.

부모 노드에 11을 넣으니 또 노드가 꽉 찬 상태가 된다.

그러므로 다시 중앙값인 11로 데이터를 분할해준다.

이렇게 함으로써 삽입 과정이 완료되었다.

B-tree의 특징

1. 모든 자식 들을 같은 레벨에 존재한다.
2. 노드의 key의 수가 k개라면, 자식노드는 k+1 이다.
3. Key들은 항상 정렬된 상태이다.

여기까지가 B- Tree 에 대한 작동 과정이다.

이제 B+ Tree에 대해 알아보자

B + Tree

B- tree와의 가장 큰 차이점은 리프 노드들만 데이터를 가질 수 있다는 점이다.

이는 Full scan 시에 가장 명확한 장점을 가진다.

다시 B-tree 의 Full scan 과정을 생각해보자

B-tree에서는 Full scan을 하기 위해서 모든 브랜치 노드 및 자식 노드들을 탐색했어야했다.

하지만 B+tree에서의 Full scan 은 다르다.

그 이유는 Leaf Node 에만 데이터가 존재하고 이들은 연결 리스트로 연결되어 있기 때문이다.

덕분에 한번의 선형 탐색으로도 Full scan을 완료할 수 있다.

B+tree의 특징

1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다.
2. 풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 효율적인 탐색이 가능하다.

해시

해시가 인덱스에서 사용되는 것을 알기전에 해시테이블에 대해 알 필요가 있다.

해시 테이블은 key값을 인자로 하는 해시 함수의 결과를 통해 인덱스를 만듦으로써 데이터를 저장하는 자료구조이다.

이 경우 찾고자 하는 데이터의 key값을 해시함수 한번으로 조회할 수 있으므로 O(1)의 시간 복잡도를 가진다.

하지만 해시 자료구조는 인덱스에서 거의 쓰이지 않는데, 그 이유는 등호 방식에만 최적화 되어있기 때문이다.

즉 DB 탐색 시에 주로 사용되는 범위검색이나 정렬에는 취약하다.

이러한 단점 때문에 인덱스에서는 많이 사용되지 않는다.

인덱스의 종류

클러스터 인덱스

클러스터 인덱스는 실제 데이터를 정렬하여 인덱스를 만드는 것이다.

따라서 테이블당 단 하나의 클러스터 인덱스만을 만들 수 있다.

실제 데이터를 통해서 인덱스를 만드는 것이므로 조회 과정에서 매우 빠른 속도를 가진다.

하지만 그 외 삽입 , 삭제 , 수정 같은 경우 클러스터 인덱스의 사용이 적합하지 않다.

(DML이 일어나는 경우 매번 정렬을 유지하기 때문)

따라서 클러스터 인덱스는 테이블의 수정이 빈번하지 않고 조회 위주의 작업을 하게 될 경우 좋은 효율을 가질 수 있다.

실생활에 비유해보면, 영어 단어 책을 예시로 들 수 있다.

영어 단어 책은 항상 A~Z 까지 정렬되있는 데 책 자체가 정렬되어 있는 이것을 클러스터 인덱스로 볼 수 있다 !

논클러스터 인덱스

실제 데이터 테이블을 정렬하지 않고 별도의 공간에 인덱스 페이지를 생성해서 저장하는 방식이다.

따라서 인덱스 페이지를 저장하기 위한 추가적인 메모리 공간이 필요하다.

DB에서 데이터를 저장하는 단위이다.

하나의 페이지는 16kb의 크기를 가진다.

MySQL :: MySQL 8.0 Reference Manual :: 15.11.2 File Space Management

논클러스터 인덱스는 데이터의 조회보다 수정,삭제,삽입 시에 더 좋은 효율을 가진다.

실생활에 비유해보면 ,

책 앞에 색인(인덱스)를 보고 해당 내용이 있는 페이지로 이동하는 것이다 !

따라서 데이터의 조회보단 수시로 데이터의 변경이 일어나는 테이블에서의 사용하는 것이 적합하다.

4. 인덱스 만드는 법

SQL 문을 통해 인덱스를 만들 수가 있다.

이 중에서는 우리가 흔히 쓰는 프라이머리 키를 통한 인덱스 생성도 포함되어있다.

위에서 두가지의 인덱스를 배웠는데 각각 어떻게 만드는 지를 알아보자

클러스터 인덱스

1. 프라이머리 키를 선언하는 경우
2. not null + 유니크 제약 조건을 선언하는 경우

ALTER TABLE member ADD CONSTRAINT id PRIMARY KEY(id); → 클러스터링

ALTER TABLE member ADD CONSTRAINT id UNIQUE NOT NULL; → 클러스터링

논 클러스터 인덱스

1. 유니크 제약 조건을 선언하는 경우
2. 직접 (유니크)인덱스를 생성하는 경우

ALTER TABLE member ADD CONSTRAINT name UNIQUE(name); → 논클러스터링

CREATE INDEX name ON member (name); → 논클러스터링

아니면 테이블을 생성할 때 인덱스를 생성할 수도 있다.

CREATE TABLE member(
id INT PRIMARY KEY,
name varchar(20) not null,
INDEX name_idx (name)
)

이처럼 여러가지 방식으로 DB 인덱스를 생성할 수 있다.

5. 적절한 인덱스 사용

인덱스를 쓰면 빠른 조회가 가능하다는 장점이 있지만 인덱스를 사용하게 될 경우 추가적인 작업이 발생하므로 상황에 따라 사용하는 것이 좋다. 그렇다면 인덱스가 굳이 필요없는 상황은 언제일까?

1. 인덱스의 범위가 너무 넓은 경우이다. 넓다는 것의 기준은 전체 데이터의 15%이상을 조회해야한다는 의미로 보면 적합하다.
2. 이 경우 인덱스를 통한 효과가 미미하기 때문에 인덱스의 사용을 지양한다.
3. 조회보다 삽입,삭제 등 수정 작업이 많을 경우이다. 이 경우도 마찬가지로 인덱스로 인한 효과가 미미하다.(수정 작업 시 where 로 조회하는 경우 제외)
4. 데이터 자체가 적은 경우는 배보다 배꼽이 더 큰 상황이 올 수 있기 때문에 사용을 지양하는 것이 좋다.

6. 언제 쓰면 좋을까?

카디널리티가 높은 데이터를 인덱스로 하면 효과적이다.

여기서 카디너리티란 사전적 의미로 그룹 내 요소의 개수를 의미한다.

그렇다면 카디널리티가 높다는 것은 어떤 걸 의미할까?

정해진 데이터 내에서 그룹 내 요소 개수가 많다는 것은 중복이 적다는 것이다.

중복이 적다는 것은 인덱스로 사용 시 매우 좋은 효율을 낼 수 있다.

예를 들어 중복된 데이터가 많은 성별 , 학년은 카디널리티가 낮으므로(중복이 높음) 인덱스에 적합하지 않다.

반대로 학번 , 고유 ID 등은 카디널리티가 높으므로(중복이 낮음) 인덱스 사용에 적합하다.

7. 결론

인덱스의 동작 방식과 인덱스의 사용 효과에 대해 알아보았다.

인덱스는 적절하게 사용하면 좋은 효율을 낼 수 있지만 상황에 맞지 않는 인덱스 사용은 오히려 역효과를 불러올 수 있다.

때문에 인덱스가 필요한 상황인 지를 잘 판단해 효율적으로 사용할 수 있어야한다.

참고 자료

DB Index 동작원리를 알아보자

클러스터 인덱스 vs 넌클러스터 인덱스 | zinirun

[자료구조] 그림으로 알아보는 B-Tree

배경지식 : 함수 종속

두 튜플의 X값이 같다면 Y값도 같은 경우가 있다. 즉 X 값에 따라서 Y의 값이 결정되는 것인데, X와 Y를을 함수 종속 관계라고 한다.

관점에 따라서 X가 Y를 함수적으로 결정한다. 라고 할수도 있고 Y가 X에 함수적으로 의존한다. 라고 표현할 수도 있다.

이러한 관계를 함수 종속 혹은 Funtional Dependency(FD)라고 한다.

예를 들어 아래 테이블에서는 회원이름과 프로그램이 primary key이며 이는 가격을 결정한다.

(회원 번호가 좀 더 자연스럽지만 설명을 위해 다른 키를 예시로 든다.)

이 둘을 FD 관계라고 할 수 있으며 기호로는 {회원이름,프로그램} -> 가격 으로 표시한다.

여기서 주의할 점은 FD를 파악할때는 스키마의 의미를 보고 파악해야하며 테이블의 데이터들을 보고 추론해서는 안된다.

왜냐하면 회원 이름과 가격 데이터가 FD처럼 보인다고 생각해도 동명이인이라는 변수가 있을 수 있고 여러 예외 상황들이 있기 때문이다.

이렇게 구축하려는 데이터베이스의 속성(애트리뷰트)가 관계적으로 어떤 의미를 지닐지에 따라서 FD들이 달라진다.

따라서 데이터(or state)만 보고 판단하기보단 스키마를 보고 의미적으로 존재하는 지 파악해야한다.

또 한가지 중요한 점은 FD는 역관계가 성립하지 않는다는 것이다.

X -> Y 관계라고 해서 Y->X가 성립하지는 않는다. 예를 들어보면 프로그램이 가격을 결정짓는 다고 해서 가격이 프로그램을 결정하는 것은 아니다!

{프로그램} -> 가격 (O)
{가격} -> 프로그램 (X)

*{}-> Y 는 "Y은 언제나 하나의 값만을 가진다"는 의미이다.

Trivial Funtional Dependcy

X -> Y의 관계에서 Y가 X의 부분 집합이라면 이 관계를 Trivial Funtional Dependcy라고 한다.

예를 들어, {a,b,c} -> {c} 같이 c가 a,b,c의 부분집합인 경우가 있다. 

반대의 경우로는 당연히 non-Trivial Funtional Dependcy (아예 안겹치면 completely-non) 같은 관계가 있다.

Partial Functional Dependency

X->Y의 관계에서 X의 부분집합(전체를 제외한)만으로 Y를 결정지을 수 있다면 이를 Partial Functional Dependency라고 한다.

예를 들어, {a,b,c} -> {c} 에서 {a} -> {c}가 성립하는 경우가 있다. 반대의 경우는 Full Funtional Dependcy가 있다.

DB 정규화란

데이터 중복과 insertion , update , deletion anomaly를 최소화하기 위해 함수의 종속성을 이용해서 relational DB를 구성하는 과정이다.

삽입이상 : 자료를 삽입할 때 의도치 않은 자료까지 삽입해야한다. (ex. null)

갱신이상 : 중복된 데이터 중 일부만 수정되어 모순이 발생하는 것이다.

삭제이상 : 어떤 정보를 삭제하면 의도치 않은 다른 정보까지 삭제된다.

정규화를 진행하게 되면 데이터 수정 시에 여러 이상 현상들을 줄일 수 있고, 확장에 용이하여 데이터 구조가 변경되어도 어플리케이션에 최소한의 영향만을 미친다.

정규형에는 몇 단계의 nf(normal forms)가 있는데 처음 단계부터 순차적으로 진행하며 앞 단계를 만족해야 다음 단계를 진행할 수 있다.

보통 실무에서 3nf까지 하면 정규화되었다라고 말한다.

제 1 정규형(1NF)

모든 attribute의 value는 더 이상 나눠질 수 없는 값이어야한다. -> 여러 값을 가지고 있으면 안된다.

(예시 참고: 코딩애플)

영희에 해당하는 프로그램 데이터가 두 개를 가지고 있으므로 이는 제 1 정규형을 위반한다.

제 2 정규형(2NF)

모든 non-prime attribute는 모든 key에 대해 full funtional dependent해야한다.
(현재 테이블과 상관없는 컬럼들을 분리한다.)

제 1 정규형을 적용하였으면 이제 제 2 정규형을 진행할 차례이다.

현재 테이블에서는 회원 정보와 프로그램 정보가 혼재해있다. 이런 테이블 구조는 데이터를 변경해야할 시에 매우 번거로울 수 있다.

(예시 참고: 코딩애플)

예시에서는 가격 컬럼이 프로그램에 partial funtional dependent하다.

{회원이름,프로그램} -> 가격

{프로그램} -> 가격

primary key가 회원번호,프로그램이지만 가격은 프로그램 하나만으로 결정될 수 있다. -> 현재 테이블에 상관 없는 데이터가 들어간 것이다!

이 상황에서 가격이 변경됨에 되면 컬럼을 일일이 수정해주어야 하기 때문에 매우 비효율적이다. 따라서 다음과 같이 분리할 수 있다.

이제 가격은 프로그램에 full functional dependency하며 프로그램 테이블에 연관있는 컬럼들만 들어가 있다.

만약 가격이 수정된다고 하더라도 이 테이블의 값만 수정하면 되기 때문에 효율적이라고 할 수 있다.

제 3 정규형 (3NF)

모든 non-prime attribute(키를 제외한)는 어떤 key에도 transitive FD(이행적 함수 종속) 하면 안된다.

transitive FD(이행적 함수 종속) 이란, X -> Y 이고 Y -> Z이면 X -> Z 인 경우이다.

이 경우에는 프로그램을 통해 강사가 결정되는데 동시에 강사가 전화번호 또한 결정할 수 있다.

프로그램 -> 강사 

강사  -> 전화번호

=> 프로그램 -> 전화번호 같은 이행적 함수 종속이 발생한다.

다음과 같은 문제가 발생할 수 있다. 예를 들어 강사가 여러 개의 과목을 담당한다고 가정하였을 때 중복된 강사는 여러 개일 것이다.

그렇다면 만약 해당 강사가 전화번호를 변경하였을 경우 일일이 변경해주어야 하며 이는 갱신 이상이 발생할 수 있다.

따라서 다음과 같이 해당 컬럼을 분리해줌으로써 문제를 해결할 수 있다.

보통 여기까지 오면 정규화 되었다고 말할 수 있지만 BCNF까지만 더 알아보려고 한다.

BCNF

모든 유효한 non-trivial FD X -> Y 는 X가 슈퍼키여야한다.

만약 테이블에 강의실 정보까지 추가되었다고 가정해보자 

이제 강의실을 통해 해당 강사의 정보를 알 수 있다. 하지만 굳이 중복된 강사의 데이터들을 가지고 있어야할까? 라는 의문이 드는데 이와 관련된 개념이 BCNF이다.

테이블을 보면 강의실을 통해 현재 어떤 강사가 배정되었는 지 알 수 있으므로 강의실 -> 강사는 non-trivial FD 라고 할 수 있다.

하지만 강의실은 슈퍼키가 아니므로 BCNF를 위반한다.

테이블을 분리한 결과 강의실은 슈퍼키가 되었고 더 이상 원래 테이블에 중복된 강사 데이터를 넣지 않아도 된다.

이렇게 해두면 BCNF를 지키면서 중복된 데이터들을 최소화 할 수 있다.

가상메모리란?

프로그램을 시작하기 위해서는 프로그램이 메모리에 올라와야 하는데, 모든 프로그램을 올리기에는 메모리의 용량이 턱 없이 부족하다. 이때 필요한 것이 가상 메모리이다. 

가상 메모리는 컴퓨터가 이용 가능한 메모리 자원들을 추상화하는 것이라고 하는데, 이게 무슨 말일까?

CPU는 프로세스를 실행할 때 논리 주소(logical memory)를 바라본다.

이때 실제로 메모리에 있는 지 없는 지 상관없이, 가상 메모리를 통해서 논리 주소를 모두 프로세스에게 할당하여준다. 

이렇게 해주면 CPU 입장에서는 "모든 프로세스들이 메모리에 올라와 있네?" 라는 착각을 하게 되고 이를 메모리의 추상화라고 볼 수 있다.

(실제 메모리에 있는 없든 CPU 입장에선 알 필요 없다.)

가상 메모리가 필요한 이유

가상 메모리의 핵심은 프로세스의 일부분만 메모리에 올릴 수 있다는 것이다.

기존에는 프로세스를 실행시키기 위해서 메모리에 프로세스 전체를 올려야했다. 하지만 이러한 방식은 메모리의 용량이 부족하거나 다른 프로세스가 실행될 경우 빈번하게 스왑(swap) 요청이 반복된다는 문제가 있었으며, 메모리의 비효율성을 초래했다.

그렇기 때문에 가상 메모리에서는 요구페이징 기법을 사용하여 가상 메모리 공간을 페이지로 나누고 꼭 필요한 페이지들만 물리 메모리에 가져온다.

요구 페이징 기법이란

모든 프로세스를 메모리에 올려놓으면 메모리 관리가 힘들어지고 응답 시간이 느려진다는 단점이 있었다.

요구 페이징 기법은 이런 문제를 해결하기 위해 나온 것인데, 요구되는 프로세스의 일부만 메모리에 적재함으로써 기존 문제들을 완화시킬 수 있다.

만약 가상 메모리에서 4번 페이지를 요청했는데 page fault가 발생한 경우를 살펴보자.

현재 4번 페이지의 유효비트는 1(invalid)이다. 그렇다면 스왑 영역에서 가져와야하는데 이때 스와핑이 발생한다.

일단, 임의로 4번에 있는 페이지를 스왑 영역으로 방출(스왑 아웃)한다. 그러면 유효비트는 1에서 0이 되고 스왑 영역 내의 주소(6)가 들어가게 된다.

그 다음 스왑 영역의 1번에 해당하는 프로세스(E)가 물리메모리의 3번 프레임으로 올라가고 유효 비트는 1에서 0으로 바뀐다.

이처럼 유효비트가 1(메모리에 없음)일때는 주소 필드에 프레임 번호가 들어가고 0(메모리에 있음)일때는 메모리 주소가 들어간다.

그리고 예시에서는 임의로 페이지를 방출했지만, 실제로는 페이지가 꽉 찼을 경우 지역성을 고려해서 페이징 알고리즘을 설계한다.

가상 메모리의 동작 방식

필요성을 알았다면 기본적인 동작 방식을 다뤄보려고한다.

먼저 처음에는 CPU가 프로세스 요청을 하는 것부터 시작한다.

이때 바로 페이지 테이블로 가는 것이 아닌 캐싱 계층인 TLB를 방문한다. -> 여기에도 없으면 페이지 테이블로 간다.

하지만 물리 메모리 자체에 적제가 되어있지 않다면 페이지 폴트 현상이 발생한다.

메모리에 없는 프로세스마저 논리 주소를 할당하기 때문에 이 현상은 불가피하다. 

중요한 것은 페이지 폴트가 일어난 다음인데, 바로 스와핑을 통해 페이지 폴트를 대처할 수 있다.

스와핑이란 메모리에 없는 프로세스를 바로 디스크의 스왑 영역에서 가져옴으로써 빨리 메모리에 적재시키는 것이다.

스와핑이 자주 일어난다는 것은 좋은 현상이 아니다. 대표적인 문제가 *스레싱이다.

스와핑이 동시 다발적으로 발생하면 CPU 처리의 공백이 발생한다.

근데 운영체제는 이를 CPU가 놀고있다고 인식하고 더 많은 프로세스를 메모리에 올리는데 이러한 악순환의 반복으로 성능이 떨어지게된다.

스레싱 : 페이지 부재율(Page fault)이 증가하여 CPU 이용율이 급격하게 떨어지는 현상

스레싱 현상의 대표적인 해결법으로는 PFF(page fault frequency)를 사용하여 페이지 폴트의 상한선과 하한선을 정해줌으로써 최소한의 페이지 프레임 할당을 보장해주는 방식이 있다.

이 방식을 통해 페이지 폴트 빈도를 계산하여 페이지 폴트가 상한선보다 높으면 더 많은 프레임을 할당해주고 낮으면 할당한 프레임을 회수해줄 수 있다.

아니면 작업 집합 모델(Working Set)을 만들어서 가장 최근에 참조된 페이지들을 집합으로 관리할 수 있다.

이는 최근에 참조된 프레임들이 이후에도 또 참조될 것이라는 지역성에 기반한다.

가상 메모리의 장단점

장점

메모리 관리를 효율적으로 할 수 있다.

기존에는 프로세스 전체가 올라와야 했다면 페이지 테이블을 통해 꼭 필요한 페이지만 메모리에 올릴 수 있다.

또한 램+스왑 영역을 통해 비교적 넓은 영역에 메모리를 저장할 수 있어서 메모리 충돌 위험이 적고 메모리 관리가 비교적 단순해진다.

단점

페이지 폴트 현상이 빈번할 시 스레싱으로 인한 성능 저하가 발생하는 데 이를 완화하기 위한 추가 작업이 필요하다. ex) 페이징 알고리즘

결론

가상 메모리를 사용함으로써 꼭 필요한 프로세스들만 페이지 단위로 메모리에 올릴 수 있으며, 이를 통해 효과적으로 메모리를 관리할 수 있다.

CPU 입장에서는 이런 메모리의 추상화를 통해 모든 프로세스들을 자유롭게 요청할 수 있고 만약 메모리에 없더라도 스왑을 통해 바로 요청할 수 있다.

하지만 잦은 페이지 폴트로 인한 스레싱을 방지하기 위해 어떤 프로세스를 올리고 내릴 지에 대한 추가적인 페이징 알고리즘이 필요하다.

연속 메모리 할당이란

프로세스에 연속적으로 메모리를 할당하는 것이다. 매 시점 프로그램의 크기에 맞게 동적으로 메모리를 할당한다.

연속 메모리 할당의 종류로는 고정 분할 방식과 가변 분할 방식이 있다.

연속 메모리 할당의 원리

연속 메모리 할당에서는 메모리를 여러 분할로 나누어서 프로세스를 할당한다.

프로세스들을 할당할 때 적재될 공간을 찾아야하는데 이를 구현한 방법이 대표적으로 3가지가 있다.

 
최초 적합
메모리를 탐색하다가 프로세스를 적재할 수 있는 공간(hole)이 나오면 그 자리에 바로 배치하는 것이다.
 
최적 적합
빈 자리가 있다고 무조건 적재하는 것이 아니라 적재 가능한 가장 작은 공간에 프로세스를 할당한다.
 
최악 적합
촤적 적합과는 반대로 적재할 수 있는 가장 큰 공간에 프로세스를 적재하는 것이다.
 

연속 메모리 할당으로 인한 문제점

근데 문제는 위처럼 빈 공간에 메모리를 할당하는 것은 그렇게 효율적인 방법이 아니다.
그 이유는 외부 단편화, 내부 단편화 때문인데 두 개의 문제가 꽤 치명적이다.

먼저 고정 분할 방식에서 생기는 문제점은 외부 단편화 , 내부 단편화가 있다.

고정 분할 방식은 분할의 크기보다 프로세스의 크기가 커서 실행되지 못하는 문제가 발생하는데 이를 외부 단편화 라고한다.

또한 프로세스에 비해 큰 분할에 적재될 경우 해당 분할의 남은 메모리가 낭비되는 내부 단편화 문제도 발생한다. 이는 하나의 분할에는 하나의 프로세스만 들어가야 하기때문에 발생하는 문제이다.

이처럼 고정 분할 방식은 메모리를 고정시켜 놓고 시작하기 때문에 가변 분할 방식에 비해 융통성이 떨어진다.

하지만 가변 분할 방식도 문제가 없는 것은 아니다. 가변 분할 방식도 외부 단편화 문제를 가지고 있다.
메모리에 빈 공간이 20MB , 30MB가 있더라도 50MB는 할당이 불가능하다. 이 두개의 메모리는 나뉘어져 있기 때문이다.
이렇게 메모리가 할당되면서 생기는 애매하게 작은 빈공간들은 계륵같은 존재여서 결국엔 빈공간으로 남게 된다. 이 문제를 외부 단편화라고 한다.
 

 
단순한 해결 방법으로는 메모리 압축 방식이 있다. 하지만 이 방법은 좀 비효율적이다.
메모리를 압축하면서 오버헤드를 피할 수 없으며 그리고 메모리를 어떻게 압축할건지에 대한 효율적인 설계도 부담해야하기 때문에
현대에는 페이징이 대표적으로 사용되고 있다.
 

대표적인 해결 방법 - 페이징

지금까지 연속 메모리 할당은 여러 문제가 있다는 것을 살펴보았다.
그래서 운영체제가 선택한 방법은 가상 메모리를 이용한 페이징인데 페이징에 집중해서 알아볼 것이다.
https://cb036133.tistory.com/175

 
페이징은 근원적인 문제를 해결한다.
결국 외부 단편화가 발생하는 이유는 프로세스의 크기가 모두 달라서인데 그렇다면 프로세스의 크기를 일정하게 자르고 필요한 부분만 할당한다면 어떨까?
이렇게하면 낭비되는 메모리도 줄일수 있고 크기 큰 프로세스도 일정 부분만 올려서 실행시킬 수 있다.
 
이렇게 일정한 크기로 자른 단위를 페이지라고하며 메인 메모리에서는 프레임이라고 한다.
그리고 안쓰는 페이지들은 다시 스왑 영역으로 swap out 시킬 수 있다. 즉 모든 메모리가 메모리에 적재되어 있을 필요가 없다.
 
근데 페이지는 연속 메모리 할당과는 다르게 불연속적으로 할당된다. 그렇기 때문에 CPU는 페이지 테이블을 이용하여 페이지와 테이블을 매핑시킨다.(약간 네트워크의 라우팅 테이블과 같은 역할이다)
프로세스마다 있는 페이지 테이블을 이용해서 순차적으로 프레임에 접근할 수 있으며 CPU는 불연속 적으로 할당되었다는 것을 고려할 필요가 없다.

근데 프로세스마다 테이블이 있다면 CPU는 어떻게 이 테이블을 찾아갈 수 있는 걸까? 이 역할을 하는게 PTBR이다.

하지만 페이지 테이블이 따로 있다면 불필요하게 메모리에 두번 접근하게 된다. (페이지 테이블 1번 + 페이지 참조 1번)

따라서 TLB를 통해 페이지 테이블의 일부를 가져와서 저장하는 캐시이다. 이를 통해 불필요한 메모리 접근을 줄일 수 있다.
 
페이징 방식이 좋다고 한들 계속 스왑을 하게 되면 성능적으로 떨어질 수 밖에 없다. 이제 관건은 어떤 프로세스를 메모리에 올리느냐인데, 이것을 고민한 결과들이 페이지 교체 알고리즘이다.
 
페이지 교체 알고리즘의 종류
 
오프라인 알고리즘(LFD)
가장 먼 미래에 참조되는 페이지와 현재 할당하는 페이지를 바꾸는 것이다.
오프라인 알고리즘은 가장 이상적인 알고리즘이지만 실현 가능성이 거의 없다. 유저의 미래 행동을 예측할 수 없기 때문이다.
하지만 현재 페이지 테이블에서 나올 수 있는 성능의 이상적인 척도(상한선)를 제공해준다. 
 
직관적으로 생각하면 가장 나중에 사용되는 페이지를 버린다고 볼 수 있다.

FIFO
먼저 온 페이지를 가장 먼저 교체한다.

특이하게도 FIFO의 경우 페이지의 수를 늘리게 되면 페이지 폴트가 더 자주 발생한다.(벨레이디의 모순)

 
LRU
참조가 가장 오래돤 페이지를 바꾼다. 이 방식을 구현하기 위해서는 각 페이지마다 카운터와 스택을 두어야한다.
 

LFU
가장 참조 횟수가 적은 페이지를 교체한다.

NUR (클럭 알고리즘)
0과 1을 가진 비트를 두고 시계 방향으로 돌면서 0을 찾은 순간 프로세스를 교체하는 것이다. 여기서 0은 참조되지 않았다는 뜻이다.

하지만 참조 시점이 가장 오래되었다는 것을 보장하지는 않는다. 프로세스를 교체하면 해당 부분은 1로 바꾼다.

1. 데드락이란?

데드락이란 두개 이상의 프로세스 혹은 스레드가 서로가 가진 리소스를 기다리는 상태이다.

이런 상태가 발생하면 서로가 원하는 자원을 얻지 못해서 처리 상태가 마비되는 현상이 발생한다.

멀티 프로세스/스레드 환경 , 레이스 컨디션 환경에서 발생하며 여러 조건이 복합적으로 작용해서 데드락이 발생한다.

2. 데드락이 발생하는 이유

앞서 데드락은 여러 조건이 복합적으로 작용해야한다고 하였다. 그 조건은 크게 4가지가 있다.

1. 상호배제(Mutual Exclusion)

레이스 컨디션 환경에서 공유 자원들을 공유해서 사용할 수 없기 때문에 발생한다.

예를 들어, 차량들이 차선들을 공유해서 사용하게 된다면 이는 곧 교통사고로 이루어진다.

이 조건은 당연히 보장되어야되는 것이다.

2. 점유 대기 (Hold and Wait)

프로세스가 이미 하나 이상의 리소스를 취득한 상태에서 다른 프로세스가 사용하고 있는 리소스를 추가로 기다리는 것이다.

점유(Hold)한 상태로 다른 리소스를 대기(wait) 한다는 개념이다.

차량이 1차선을 점유하고 있는 상황에서 2차선까지 점유해야한다면, 그 동안은 다른 차량들이 1차선을 점유하지 못할 것이다.

하지만 어떤 차량이 꼭 1차선에 가야한다면 이는 곧 처리가 마비되는 데드락을 유발할 수 있다.

3. 비선점

다른 프로세스나 스레드나 CPU 자원을 임의로 가져올 수 있다. 즉 현재 자원(리소스)을 점유하고 있는 자만이 리소스를 반환할 수 있다.

2차선에 있는 차량이 1차선에 있는 차량을 억지로 끌어내려서 점유할 수 없는 것과 같은 개념이다.

4. 순환 대기

말 그대로 서로가 서로의 자원을 기다리고 있는 것이다.

이 4가지 조건이 충족되어야 데드락이 발생한다고 할 수 있다!

3. 데드락 해결 전략

데드락 방지

4가지 조건으로 인해 데드락이 발생한다면, 역발상으로 4가지 상황이 충족되지 않게 시스템을 디자인하는 것이다.

첫번째로 리소스를 공유 가능하게 하는 방법이 있다.

하지만 이 방법은 애초에 현실 가능성이 없다. 왜냐하면 레이스 컨디션 환경에서 자원을 공유한다는 거는 매우 위험하기 때문이다.

또한 IO 관련 리소스들은 애초에 동시에 실행될 수가 없기 때문에 현실 가능성이 없다고 할 수 있다.

두번째로는 점유 대기 상태를 만들지 않는 것이다.

자원을 점유한 상태에서 다른 자원을 대기하면서 문제가 되는 것이라면, 애초에 모든 자원을 점유한 상태에서만 실행하게끔 하여서

해당 상태를 만들지 않으면 된다. 즉 "hold(점유)한 채로 wait(대기)하지마!" 방식의 해결 방법이다.

세번째는 대기 상태에서 자원을 양보하도록 하는 것이다.

만약 어떤 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리고 있는 상태라면, 현재 점유하고 있는 자원을 다른 프로세스에게 양보할 수 있다.

이는 락을 자발적으로 반환하는 모니터 방식과 유사하다.

https://cb036133.tistory.com/178

네번째는 모든 리소스에 순서체계를 부여해서 오름차순으로 리소스를 요청하는 것이다.

만약 4번 리소스를 점유했다면 다음 리소스는 4번 리소스보다 큰 리소스를 점유해야한다.

이렇게 함으로써 순환 참조를 없앨 수 있다.

데드락 회피

데드락이 발생할 것 같은 상황 자체를 회피하는 것이다. 이를 위한 대표적인 알고리즘으로 은행원 알고리즘이 있다.

은행원 알고리즘이란, 총 자원의 양과 현재 할당한 자원의 양을 기준으로 안정 또는 불안정 상태로 나누고 안정 상태를 유지하도록 자원을 할당하는 알고리즘이다.

안정 상태: 데드락이 발생하지 않았고 프로세스의 최대 자원 요구량을 운영체제가 충족시킬 수 있는 상태

데드락 감지와 복구

우선 데드락을 허용해주고 데드락이 발생한다면 복구한다.

복구 전략은 크게 2가지이다.

먼저 데드락이 걸린 프로세스들을 종료시키는 것이다.

이때 프로세스들을 하나씩 종료시키거나, 모두 한꺼번에 종료시킬 수도 있지만 이 방법은 최후의 방법이다. 

이렇게 강제 종료를 하게 되면 그동안의 진행 상황을 잃게 되는 리스크를 감내해야 하기 때문이다.

그리고 다른 방법은 일시적으로 선점을 허용해주는 것이다.

이렇게 함으로써 꽁꽁 묶여있던 프로세스/스레드 들이 그나마 진행될 수 있다.

데드락 무시

말 그대로 데드락이 일어나던 말건 신경 안쓰는 것이다. 꽤 많은 운영체제에서 해당 방식을 사용하고 있다.

왜냐하면 데드락은 매우 드물게 일어나기 때문에 이를 처리하는 비용이 더 크기 때문이다.

사실 현실에서도 컴퓨터가 멈추면 대부분의 사용자들은 껐다 킨다.

모니터란?

모니터는 스레드가 mutex를 보장할 수 있도록 하는 동기화 메커니즘이다.

조건에 따라서 스레드를 waiting 상태로 전환시키는데 이를 cooperation이라고 한다.

mutex - 락을 가지고 있는 스레드만이 임계 영역에 들어갈 수 있고 메소드를 실행할 수 있다.

모니터의 작동 방식

모니터는 크게 두가지의 구성 요소로 이루어져 있다.

뮤텍스

mutual exclusion을 보장하는 장치이다. 락을 가지지 못한 스레드는 뮤텍스에서 관리하는 엔트리 큐에 들어간다.

condition variable

wating queue를 이용해 조건이 충족되지 않은 스레드들이 대기 상태로 머물 수 있도록한다.

만약 스레드의 조건이 충족되었을 경우 스레드를 깨우는 작업이 필요한데 이러한 메커니즘으로 인해 3개의 동작(상태)를 가진다.

1. wait - 스레드가 자신을 cv(condition variable)의 waiting 큐에 넣고 대기(wait) 상태로 전환한다.

2. signal - wating 큐에서 대기 중인 스레드 중 하나를 깨운다. 

3. broadcast - wating 큐에서 대기 중인 모든 스레드를 깨운다.

모니터에는 두 개의 큐가 존재한다.

엔트리 큐 - 임계영역 (critical section)에 진입을 기다리는 큐 -> 뮤텍스가 관리한다.

waiting 큐 - 조건이 충족되길 기다리는 큐 -> cv가 관리한다.

signal and continue

시그널을 주고 기존 스레드가 중단되지 않는다.

signal and wait

시그널을 주고 기존 스레드는 대기 상태에 들어가며 다시 락을 얻으면 깨어난다.

자바에서의 모니터

모든 자바 객체는 기본적으로 내부에 모니터를 하나씩 가지고 있다.

그리고 이것은 synchronized 키워드를 통해서 사용할 수 있다.

*자바의 모니터는 cv를 하나만 가진다.

그리고 자바의 모니터도 세가지 상태가 있는데, 용어만 살짝 다를 뿐 기능은 같다.

스케줄링이란?

CPU 버스트*를 고려하여 운영체제가 공정하고 합리적으로 CPU 자원을 분배하는 것이다.

CPU 버스트: CPU를 사용하는 구간

스케줄링을 사용하는 이유

스케줄링의 주요 목적은 멀티 프로그래밍 환경에서 CPU의 유휴(idle) 시간을 최소화하여 CPU의 이용률을 최대하하는 것에 있다.

물론 아무 프로세스나 랜덤으로 넣어서는 안되고 프로세스들의 여러 조건들을 고려해서 어떤 것부터 처리할 지 결정한다.

한가지 예를 들어보자

입출력 작업이 많은 프로세스와 CPU 사용이 많은 프로세스가 있다. 이 둘 중 어떤 것을 먼저 처리해야 될까?

이 경우 일반적으로 입출력 작업이 우선 순위를 가진다. 

왜냐하면, 입출력 작업을 먼저 빨리 끝마친 뒤에 CPU 사용이 많은 프로세스에게 많은 CPU 자원을 할당해줄 수 있기 때문이다.

CPU 스케줄링은 이처럼 중요성과 우선 순위를 고려해서 프로세스들에게 자원을 할당해준다.

만약 무조건 먼저 요청한 순서대로 처리한다면, 당장 급한 프로세스가 실행되지 않고 별로 급하지 않은 프로세스들만 실행될 수 있다.

이는 곧 전체 성능의 저하를 초래하기 때문에 적절한 스케줄링 규칙은 필수로 요구된다.

스케줄링 동작 방식

앞에서 스케줄링을 시에 CPU 버스트를 고려하여서 우선 순위를 책정한다고 하였다.

이러한 우선 순위 정보들은 PCB 라는 곳에 저장되어 있는데, CPU 입장에서 PCB를 일일이 뒤져서 스케줄링을 하는 것은 여간 번거로운 일이 아닐 것이다.

따라서 이때 사용하는 것이 스케줄링 큐인데 이 큐를 이용하여서 프로세스들의 대기열을 관리할 수 있다.

스케줄링 큐는 대표적으로 두가지가 있다.

- 준비큐(ready queue)

메인 메모리에 상주하면서 CPU를 할당받아서 실행될 준비가 된 프로세스 집합이다. 즉, 스케줄러에게 선택되어 CPU에 올라가기를 기다리는 프로세스들의 집합이다.

- 대기큐(wait,device queue)

입출력 작업이 필요하지만 지금 당장 CPU를 사용하지 않는 장치들이 대기하고 있는 프로세스들의 집합이다.

예를 들어 프로세스가 디스크에 입출력 요청을 했다고 가정했을 시에 디스크는 여러 요청을 처리하느라 지연이 발생할 수 있다.

이때 CPU를 사용하지도 않는 프로세스가 CPU 자원을 받는 것은 비효율 적이기 때문에 대기큐로 빠지게 된다.

이렇게 큐에 프로세스들이 쌓이는 것을 알았다면 어떻게 프로세스를 선점하는 지를 알아보자

그 전에 스케줄링 디스패처의 구조를 알 필요가 있다.

대게 스케줄러와 디스패처를 같은 범주로 묶어서 말한다. 하지만 둘의 역할은 명확한 차이가 있다.

프로세스의 상태 변화로 인해 프로세스가 비어있게 되면 어느 프로세스를 CPU로 가져올지에 대한 작업이 이루어진다.

이 과정은 스케줄러가 담당한다.

스케줄러는 앞에서 배웠던 준비 큐에서 우선 순위에 따라 프로세스를 선택하고 실행한다.

디스패처는 이렇게 선택된 프로세스가 실제로 CPU에서 실행될 수 있도록한다.

선택 된 프로세스로 컨텍스트 스위칭을 해주며 이 작업을 위해 커널모드로 진입했다가 다시 프로세스 실행을 위해 유저 모드로 전환한다.

그리고 새로운 프로세스의 마지막 작업 상태를 불러오고 적절한 위치로 이동시켜준다.

그렇다면 "어떻게 CPU를 선점할 것인가?" 에 대한 고민이 필요한데 크게 선점형 , 비선점형 방식이 있다.

비선점형

실행 상태에서 프로세스의 자발적인 상태 변경으로 인한 스케줄링이 일어나는 것을 말한다.

1. IO request : 발생 시

2. terminate 발생 시 : 실행하던 프로세스가 끝났을 경우

비선점형 방식은 상호 협력적(다른 프로세스를 위해 양보하는 경우)이라는 장점이 있는 반면에 느린 응답 시간*이라는 단점이 있다.

모든 프로세스를 공정하게 처리한다.

Response time(응답 시간): ready 큐에 들어와서 처음으로 CPU(최초로)를 얻기까지 걸린 시간

선점형

프로세스가 끝나지 않았음에도 운영체제가 개입할 수 있다.

1. interrupt 발생 시 : 외부에서 인터럽트가 들어온 경우

2. IO request : 발생 시

3. time-out 발생 시 : time slicing (시분할) 에 의해, 주어진 시간이 끝났을 경우

4. wake-up 발생 시 : 대기 큐에 있는 프로세스들을 준비 큐에 옮길때

5. terminate 발생 시 : 실행하던 프로세스가 끝났을 경우

기본적으로 비선점형에서 하는 방식을 모두 사용하지만 운영체제가 적극적으로 스케줄링에 개입한다.

이로 인해 데이터 일관성 문제가 발생하기도 한다. -> 이것을 방지하기 위해 뮤텍스 , 세마포어 기술 적용

외부 인터럽트를 허용한다! 하지만 잦은 컨텍스트 스위칭으로 인해 오버헤드가 발생할 수 있다.

또한 우선 순위로 프로세스를 처리하기 때문에 우선 순위가 낮은 프로세스들은 CPU를 할당받지 못할 수 있다. (기아 현상)

이제 마지막으로 스케줄러가 어떤 알고리즘으로 큐에서 가져오는 지 알아보자

여러가지가 있지만 대표적으로 7가지만 추려보았다.

스케줄링 알고리즘

- FCFS

준비큐에 먼저 도착한 순서대로 처리한다.

프로세스들이 기다리는 시간이 매우 길어질 수 있다.

Convoy effect 현상이 발생할 수 있다. 

 Convoy effect: 실행 시간이 긴 프로세스로 인해 뒤에 있는 프로세스들의 대기시간이 길어지는 현상

- SJF(Shortest job first)

프로세스의 CPU 버스트가 가장 짧은 순서대로 실행한다.

CPU 사용시간이 긴 프로세스는 나중에 , 짧은 프로세스는 먼저!

기존적으로 비선점 형으로 구현된다.

- SRTF

SJF + Round Robin

남은 CPU 버스트가 가장 짧은 순서대로 실행한다.

time slice만큼 cpu를 이용하되, 남은 작업 시간이 가장 적은 프로세스부터 실행

- priority

우선 순위가 높은 프로세스부터 실행

우선 순위가 같다면 FCFS로 처리

starvation(기아) 현상이 발생할 수 있음 (우선 순위가 낮은 프로세스는 실행 무기한 지연)

-> 에이징 기법으로 해당 문제를 완화할 수 있음

- Round-Robin

FCFS + 타임 슬라이스

time slice로 나눠진 CPU time을 번갈아가며 실행

정해진 시간이 끝났음에도 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입한다.

Round Robin에서 time slice의 크기가 너무 크다면 fcfs에서 발생하는 문제가 그대로 나타나고,

반대로 너무 작아져버리면 context switching으로 인한 CPU의 오버헤드가 발생한다.

따라서 적절한 time slice의 크기를 필연적으로 고려해야한다.

- multilevel-queue

우선 순위별로 준비큐를 여러개 사용하는 방식

프로세스 유형별로 그룹화해서 큐별로 다른 스케줄링 알고리즘을 적용할 수 있다.

queue 간의 이동이 불가능하고 기아 현상이 발생할 수 있다.

- multilevel-feedback-queue

queue 간의 이동이 가능한 multilevel-queue 스케줄링 방식

정해진 time slice 안에 프로세스를 완료하지 못했으면 우선 순위가 낮은 큐로 이동한다.

-> 다른 프로세스의 우선 순위가 상대적으로 높아짐

에이징 기법도 적용 가능하다.

CPU 스케줄링의 가장 일반적인 형태이다!

결론

운영체제는 멀티프로세스 환경에서 CPU의 이용률을 최대화하기 위해 여러 스케줄링 방식을 사용한다.

만일 적합하지 못한 방식을 사용한다면 프로세스가 무기한 지연되는 기아(starvation) 현상이나 응답 시간의 지연을 초래할 수 있다.

따라서 CPU 선점 방식에서부터 알고리즘 까지, 상황에 맞게 적당한 방식을 고르는 것이 중요하다.

💡 운영체제란 무엇인가?

- 운영체제란 유저의 편의를 위해 컴퓨터의 자원들을 대신 관리해주는 시스템 소프트웨어이다.

- 여기서 자원은 메모리 , CPU 그리고 I/O 디바이스들이 있다.

- 운영체제를 사용함으로써 유저는 동작원리를 알지 못해도 PC를 활용할 수 있다.

(ex. 윈도우 , 리눅스 , 유닉스)

💡 프로세스와 스레드에 대해 설명해주세요.

- 프로세스는 운영체제로부터 작업을 할당받는 작업의 단위이며 , 스레드는 그 자원을 이용하는 실행의 단위이다.

- 프래세스 내에 스레드는 여러개가 생성될 수 있으며 최소 한 개 이상을 가져야한다.

💡 멀티 스레드의 장점 및 단점은 무엇인가?

- 스레드는 서로 메모리를 공유하기 때문에 프로세스보다 가볍다는 특징이 있다.

- 이는 통신 비용 감소 및 시스템 자원의 효율적인 사용으로 이어진다.

- 또한 컨텍스트 스위치를 비용이 멀티 프로세스에 비해 줄어든다.

- 하지만 자원을 공유한다는 특성은 곧 여러 단점을 낳는다.

- 대표적으로 동기화의 문제인데, 여러 스레드가 한 자원에 접근하는 경우 의도치 않은 여러 문제가 생길 수 있다.

- 그리고 스레드 하나가 종료 되면 해당 자원을 공유하는 다른 스레드들에게도 영향을 미치기 때문에 안정성 문제도 발생한다.

- 따라서 멀티 스레드의 에러 처리 및 동기화 처리를 필수적이라고 볼 수 있다.

💡 멀티 프로세스 대신 멀티 스레드를 사용하는 이유

- 멀티 스레드만의 장점은 자원을 서로 공유함으로써 스레드간 통신 비용이 감소하고 자원을 효율적으로 쓴다는 것이다.

- 따라서 스레드 간 데이터 공유가 빈번하거나, 컨텍스트 스위칭이 자주 일어나는 경우 멀티 스레드를 사용하는 것이 적합하다.

- 하지만 프로그램이 메모리가 공유되서는 안되며 동기화 문제에 취약한 경우 멀티 스레드 보단 멀티 프로세스를 사용해야한다.

💡 스레드에 스택을 독립적으로 할당하는 이유?

- 스레드에게 최소한의 독립적인 실행을 보장해주기 위해서이다.

- 함수 호출을 위한 여러 정보를 담고 있는 스택을 할당해줌으로써 이를 보장해줄 수 있다.

💡 PC레지스터를 스레드마다 독립적으로 할당하는 이유?

- 스레드의 레지스터는 "마지막 상태"를 의미한다.

- 예를 들어 스레드가 동작하다가 스케줄링에 의해 CPU 점유권이 넘어가게 된다면 스레드는 마지막 상태를 저장하고 종료된다.

- 이 상태가 저장되는 곳이 PC 레지스터이다.

💡 자바 스레드란?

- 기존 스레드 개념과 동일하게 JVM 프로세스 내에서 관리되어 지는 실행 단위이다. 

- 처음 프로세스를 시작하면 main 함수에서 스레드 하나가 만들어지는데, 필요에 따라 멀티 스레드 환경을 구현할 수 있다.

- 단 이 경우 메인 스레드가 종료되어도 실행되고 있는 스레드가 있다면 프로세스가 종료되지 않는다.

💡 Thread-safe가 뭐에요?
- 멀티 스레스 환경에서 여러 스레드가 동시에 자원에 접근할 때 실행 결과에 영향을 주지 않는 것을 "스레드 세이프" 하다고 한다.

- 즉 레이스 컨디션 환경에서 동기화를 통해 데이터의 일관성을 유지하는 것이다.

Mutual exclusion (상호 배제)

- 락을 사용해 공유 자원에 동시 접근을 제한하는 방법이다.

- 대표적으로 스핀 오프 , 뮤텍스 , 세마포어가 있다.

Atomic operation (원자 연산)

- 공유 자원에 접근할 때 원자 연산 혹은 원자적으로 접근한다. 

*원자적이란 모두 성공하던지 아니면 모두 실패하는 지를 보장해주는 것을 말한다.

Thread-local storage (쓰레드 지역 저장소)

- 공유 상태를 피할 수 없을 때 각각의 스레드에서만 접근 가능한 저장소들을 사용함으로써 동시 접근을 막는 방법이다.

- 전역 변수의 사용을 막음으로써 만들 수 있다.

Re-entrancy (재진입성)

- 스레드가 병렬적으로 실행되더라도 실행 결과에 영향을 미치지 않는 것을 보장해주는 것이다.

- 모든 재진입 함수는 스레드-안전하지만, 모든 스레드 함수가 재진입이 가능한 것은 아니다.

💡 세마포어와 뮤텍스를 설명해주세요.

- 뮤텍스는 공유 자원에 대해 하나의 프로세스나 스레드가 락을 가지고 다른 락은 슬립 상태로 대기하는 방법이다.

- 세마포어는 공유 자원에 접근하는 프로세스나 스레드의 수를 제한하는 방식이다. 

- 세마포어의 제한을 1로 둠으로써 뮤텍스 환경을 어느정도 구현할 수는 있지만 뮤텍스는 락을 가진 자만이 락을 해제할 수 있다는 점에서 차이가 있다.