코딩소년 - 기술블로그

Set 컨테이너

set 컨테이너의 경우 

Red Black Trees를 사용하여 만들어진다.

Red Black Trees = 이진트리와 비슷한 형태로 만들어진다. 

Input에 상관없이 정렬되어서 출력 된다.

중복을 허용하지 않는다. 

#include <iostream>
#include <set>

int main(int argc, char const *argv[])
{
	str::set<int> nums{1,2,3,4,5};
    
    for(const int num : nums)
    {
    	std:count << num << " ";
    }
    std:cout << std::endl;
    
    return 0;
}

Multi-Set 컨테이너

일반적인 set컨테이너와는 다르게 여러개의 키를 가질 수 있다.

시간복잡도는 Search, Removal, Insertion Operations 모두 O(log n)의 시간복잡도를 가진다. 

Unordered-Set 컨테이너 

순서 없이 출력된다.

시간복잡도는 Search, Removal, Insertion Operations 모두 O(1)의 시간복잡도를 가진다. 

rehashing = O(n)

bucket_count 

Map 컨테이너

map 컨테이너도 set 컨테이너와 마찬가지로 

red-black trees로 만들어진다.

시간복잡도는 Search, Removal, Insertion Operations 모두 O(log n)의 시간복잡도를 가진다. 

UnOrdered Map 컨테이너

시간복잡도는 Search, Removal, Insertion Operations 모두 O(1)의 시간복잡도를 가진다. 

내부적으로 요소는 특정 순서로 정렬되지 않고 버킷으로 구성됩니다. 요소가 배치되는 버킷은 전적으로 해당 값의 해시에 따라 다릅니다. 이렇게 하면 개별 요소에 빠르게 액세스할 수 있습니다. 해시가 계산되면 요소가 배치된 정확한 버킷을 참조하기 때문입니다.

수정하면 요소의 해시가 변경되고 컨테이너가 손상될 수 있으므로 컨테이너 요소를 수정할 수 없습니다

STL Standard Template Library 

C++ 표준 템플릿 라이브러리를 의미한다. 

알고리즘, 컨테이너, 함수, 반복자 라는 네가지 구성 요소를 제공한다.

시퀀스 컨테이너 : vector, deque, list,

연관(Associative) 컨테이너 : map, multimap, hast_set, hash_map, hash_multiset, hash_multimap

컨테이너 어댑터(adaptors) : queue, priority_queue, stack 

Array 

스택에 연속된 공간이 할당된다. (STACK)

컴파일 타임에 메모리가 할당되므로 Fixed Size

Vector

Vector는 메모리 할당을 연속적으로 하고, List는 따로따로 할당을 한다.

힙에 연속된 공간이 할당된다. (HEAP)

Runtime에 메모리가 할당 되므로 flexible size 

dynamic array like C Array.

시간복잡도 

- Random Access - Constant O(1)

백터에 아무공간이나 접근하는 것은 O(1)의 시간 복잡도를 가진다.

- Insertion or removal of elements at the end - amortized constant O(1)

마지막 공간에 삽입하거나 제거하면 O(1)의 시간 복잡도를 가진다.

- Insertion or removal of elements - linear in the distance to the end of the vector O(n)

마지막 공간이 아닌 다른 공간에 삽입이나 삭제가 일어나면 삽입이나 삭제가 일어난 곳 부터 끝까지 O(n)의 시간복잡도를 가진다.

- find 의 경우 O(n) 하지만 연속적인 메모리 공간을 사용하므로 list보다 find를 수행하는 능력이 빠르다. 그러므로 99%는 vector를 사용하고 list는 잘 사용하지 않는다고 한다. 

size 는 실제크기

capacity는 실제 확보한 메모리 

List

forward_list의 경우 singly linked list(단방향리스트)이다.

더블링크드 리스트(양방향리스트)이다. 비연속적으로 메모리를 할당한다. 

시간복잡도 

- 어느공간에서 삽입과 삭제가 일어나든 O(1)의 시간복잡도를 가진다. (주소를 가르키는 방향만 바꿔주면 되기 때문이다.)

- 백터와는 다르게 O(1)의 랜덤 액세스는 불가능하다. 랜덤 엑세스는 O(n)이다.

- find의 경우 O(n)

프로세스 (Process)란?

* 프로세스란 실행중인 프로그램의 메모리,리소스 등을 총칭하는 의미이다.

프로세스는 실행파일(바이너리파일)이 스택,힙,데이터영역,코드영역에 담겨서 프로그램을 순서대로 실행하게 된다. 

OS가 레지스터에 연산할 것을 가져다 놓고, CPU는 레지스터에 있는 데이터를 가져와서 연산을 한다. 

CPU는 다시 그 데이터를 레지스터에 가져다 놓고, OS가 레지스터의 데이터를 다시 가져간다.

이 전체의 과정이 프로세스이다. 

* CPU의 레지스터(Register) - CPU에 들어 있는 엑세스가 매우 빠른 메모리 공간 

Swap File : 운영체제는 둘 이상의 프로세스가 실행 될 경우, 데이터를 하드디스크에 보관한다.

Context-Switching : 하나의 프로세스가 CPU를 사용 중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기 위해, 이전의 프로세스의 상태(문맥)를 보관하고 새로운 프로세스의 상태를 적재하는 작업을 말한다. 

프로세스 스케줄링(Process Scheduling)이란?

프로세스가 항상 CPU를 점유하고 있는 것은 아니다. 프로세스가 실행 가능한 시점까지 실행하고, I/O 등 CPU를 사용하지 않는 작업을 할 때는 다른 프로세스를 실행한다면 CPU의 사용 효율을 높일 수 있다.

오늘 날에는 위 아이디어를 프로세스 스케줄링(Process Scheduling)이라는 기술로 구현한다.

프로세스 상태 (Process State)

생성(create) : 프로세스의 생성

실행(running, burst) : 프로세스가 프로세서를 차지하여 명령어들이 실행되고 있다.

준비(ready) : CPU가 할당 되기를 기다리고 있다.

대기(wating) : 프로세스가 입출력 완료하고 시그널 수신 등 어떤 사건을 기다리고 있는 상태이다.

종료(terminate) : 프로세스의 실행이 종료되었다.

운영체제는 준비 큐(Ready Queue), 대기 큐(Wating Queue) 등의 자료구조를 두어 이들 프로세스를 관리한다.

선점(Preemptive)과 비선점(Non-Preemptive) 

선점 -> 빼았을 수 있다. (타의에 의해 자원을 빼았길 수 있음)

Context Switching 오버헤드가 크다.

비선점 -> 빼았을 수 없다. (할당 자원을 스스로 반납할 때까지 사용)

Context Switching 오버헤드가 적다.

프로세스 스케줄링은 다음 네 가지 경우 일어날 수 있다.

- 프로세스가 실행 상태에서 대기상태로 전환할 때

- 프로세스가 실행상태에서 준비 상태로 전환될 때

- 프로세스가 대기상태에서 준비 상태로 전환 될 때

- 프로세스가 종료되었을 때

1,4의 경우 비선점 스케줄링이라고 한다.

선점 스케줄링은 위의 네 가지 경우 모두 해당

스케줄링 기법

1 FCFS(First Come First Serve) 스케줄링 

큐와 같은 방식으로 CPU를 먼저 요청한 프로세스가 먼저 CPU를 배정받는 스케줄링 방법. 비선점 스케줄링 방식이다.

batch system에 적합, interactive system에 부적합 

convoy effect가 발생하므로 그렇게 좋은 처리 방법이 아니라고 한다. (평균대기시간이 길어질 수 있기 때문이다.)

convoy effect는 모든 프로세스들이 커다란 한 프로세스가 끝날 때까지 기다리는 현상이다.

2 SPN(Shortest-Process-Next) 스케줄링  = (SJF Shortest-Job-First)

비선점 스케줄링이다.

CPU 한 차례 사용시간(burst time) 이 작은 프로세스부터 먼저 끝내는 방법

convoy effect를 최소화 할 수 있다.

장점 : 평균대시간 최소화, 시스템 내 프로세스 수 최소화, 빠른 응답시간 제공

단점 : 무한대기(Starvation) 현상 발생, 정확한 실행시간을 알 수 없음.

3 SRTN(Shortest-Remaining Time Next) 스케줄링

잔여 실행이 더 적은 프로세스가 Ready 상태가 되면 선점됨

장점 : SPN의 장점 극대화

단점 : 총 실행시간 예측이 필요함, 잔여 실행을 계속 추적해야함 -> 오버헤드 발생, Context switching overhead,

구현 및 사용이 비현실적이다.

4 HRNN (High-Response-Ratio-Next) 

SPN + Aging concepts

Aging concepts = 프로세스의 대기시간을 고려하여 기회를 제공

비선점 스케줄링이다.

Response Ratio가 높은 프로세스가 우선이다.

Response Ratio = (대기시간+실행시간) / 실행시간

5 Robin Round 스케줄링 

도착시간 (ready queue 기준)

먼저 도착한 프로세스를 먼저처리

자원 사용제한 시간(Time Quantum)이 있음 (프로세스는 할당된 시간이 지나면 자원 반납)

대화형, 시분할 시스템에 적합

6 MLQ ( Multi-level Queue) 

작업 또는 우선순위 별 별도의 Ready Queue를 가짐. (레디큐가 여러개이다.)

큐 사이에는 우선순위 기반의 스케줄링사용

장점 : 중요한 애들의 빠른 응답시간

단점 : 여러개의 큐 관리 등 스케줄링 오버헤드

큐의 구성은 정책에 따라 관리

7 MFQ (Multi-level Feedback Queue)

프로세스의 큐간 이동이 허용됨.

피드백을 통해 우선순위 조정 (동적으로 우선순위 부여 가능)

특징

Dynamic Priority, 선점 스케줄링, 

장점 : 각 준비 큐마다 시간 할당량을 다르게 배정, 입출력위주 프로세스들을 상위 단계의 큐로 이동, 우선순위 높임

대기시간이 지정된 시간을 초과한 프로세스들을 상위큐로 이동(에이징 기법)

단점 : 설계 및 구현이 복잡

프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN 기법의 효과를 볼 수 있다.