Sunny's Tech Blog

트랜잭션 (Transaction) 이란?

데이터베이스의 상태를 변환시키는 하나의 논리적 기능을 수행하기 위한 작업의 단위 또는 한꺼번에 모두 수행되어야 할 일련의 연산들을 의미

트랜잭션의 특징

1. 데이터베이스 시스템에서 병행 제어 및 회복 작업 시 처리되는 작업의 논리적 단위

2. 사용자가 시스템에 대한 서비스 요구 시 시스템이 응답하기 위한 상태 변환 과정의 작업 단위

3. 하나의 트랜잭션은 Commit 또는 Rollback 수행

트랜잭션의 성질

Atomicity(원자성)

1. 트랜잭션의 연산은 데이터베이스에 모두 반영되든지 아니면 전혀 반영되지 않아야 한다.

2. 트랜잭션 내의 모든 명령은 반드시 완벽히 수행되어야 하며, 모두가 완벽히 수행되지 않고 어느하나라도 오류가 발생하면 트랜잭션 전부가 취소되어야 한다.

Consistency(일관성)

1. 트랜잭션이 그 실행을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 변환한다.

2. 시스템이 가지고 있는 고정요소는 트랜잭션 수행 전과 트랜잭션 수행 완료 후의 상태가 같아야 한다.

Isolation(독립성,격리성)

1. 둘 이상의 트랜잭션이 동시에 병행 실행되는 경우 어느 하나의 트랜잭션 실행중에 다른 트랜잭션의 연산이 끼어들 수 없다.

2. 수행중인 트랜잭션은 완전히 완료될 때까지 다른 트랜잭션에서 수행 결과를 참조할 수 없다.

Durablility(영속성,지속성)

1. 성공적으로 완료된 트랜잭션의 결과는 시스템이 고장나더라도 영구적으로 반영되어야 한다.

트랜잭션 연산 및 상태

1) Commit연산

- 한 개의 논리적 단위(트랜잭션)에 대한 작업이 성공적으로 끝났고 데이터베이스가 다시 일관된 상태에 있을 때, 이 트랜잭션이 수행한 연산이 완료된 것을 트랜잭션 관리자에게 알려주는 연산

2) Rollback연산

- 하나의 트랜잭션 처리가 비정상적으로 종료되어 데이터베이스의 일관성을 깨뜨렸을 때, 이 트랜잭션의 일부가 정상적으로 처리되었더라도 트랜잭션의 원자성을 구현하기 위해 이 트랜잭션이 행한 모든 연산을 취소(Undo)하는 연산

- Rollback시에는 해당 트랜잭션을 재시작하거나 폐기함

3) Savepoint 연산

- 현재 작업 중인 트랜잭션을 잘게 쪼개는 역할

- 저장점(Savepoint)을 정의하면 Rollback할 때 트랜잭션에 포함된 전체 작업을 Rollback하는 것이 아니라, 현 시점에서 SAVEPOINT까지 트랜잭션의 일부만 Rollback

트랜잭션 상태

활동(Active) : 트랜잭션이 실행중인 상태

실패(Failed) : 트랜잭션 실행에 오류가 발생하여 중단된 상태

철회(Aborted) : 트랜잭션이 비정상적으로 종료되어 Rollback 연산을 수행한 상태

부분 완료(Partially Committed) : 트랜잭션의 마지막 연산까지 실행했지만, Commit 연산이 실행되기 직전의 상태

완료(Committed) : 트랜잭션이 성공적으로 종료되어 Commit 연산을 실행한 후의 상태

자료구조 '힙(Heap)'

- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
- 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조

- 힙의 종류

  1) 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

  2) 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

* 완전 이진 트리란?

  - 완전 이진트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있어야 함

  - 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 함

* 우선순위 큐(Priority Queue)란?

  - 큐는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조

  - 우선순위 큐는 먼저 들어오는 데이터가 아닌, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조

  - 우선순위 큐는 배열, 연결리스트, 힙 등의 자료구조를 통해 구현 가능 → '힙'으로 구현하는 것이 가장 효율적

힙 정렬

- 힙 자료구조의 특성을 이용한 정렬

- 배열을 힙 자료구조에 넣은 다음에 원소를 하나씩 빼면,

  → 최소힙일 경우는 작은 값부터 큰 값 순서대로 정렬되어서

  → 최대힙일 경우는 큰 값부터 작은 값 순서대로 정렬되어서 나옴

- 내림차순 정렬을 위해서는 최대 힙을 구성하고, 오름차순 정렬을 위해서는 최소 힙을 구성

힙 정렬 과정

1. 정렬해야 할 N개의 요소들로 최대힙을 구성 → 내림차순 정렬
2. 그 다음으로 한 번에 하나씩 요소를(최댓값부터) 힙에서 꺼냄
3. 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬 [최대 힙 삭제 과정]

* 내림차순 정렬을 위한 최대 힙의 구현

  - 힙(heap)은 1차원 배열로 쉽게 구현될 수 있음
  - 정렬해야 할 N개의 요소들을 1차원 배열에 기억한 후, 최대힙 삽입을 통해 차례대로 삽입

* 최대 힙 삽입 과정

  - 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입
  - 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킴

* 최대 힙 삭제 과정

  - 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소(=루트 노드)를 삭제하는 것
  - 삭제된 루트 노드에는 힙의 마지막 노드를 가져옴
  - 힙을 재구성

결론적으로...

힙 정렬이란, 힙(Heap)이라는 자료구조의 성질을 활용하여 정렬을 하는 방법을 의미한다.

먼저 입력되는 배열의 숫자들을 최대힙 또는 최소힙으로 구성시킨 후 (최소힙/최대힙 삽입 과정), 가장 상위 노드부터 출력하여(최소힙/최대힙 삭제 과정) 숫자들을 정렬한다.

힙 정렬 코드

/* 현재 요소의 개수가 heap_size인 힙 h에 item을 삽입한다. */
// 최대 힙(max heap) 삽입 함수
void insert_max_heap(HeapType *h, element item){
  int i;
  i = ++(h->heap_size); // 힙 크기를 하나 증가

  /* 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정 */
  // i가 루트 노트(index: 1)이 아니고, 삽입할 item의 값이 i의 부모 노드(index: i/2)보다 크면
  while((i != 1) && (item.key > h->heap[i/2].key)){
    // i번째 노드와 부모 노드를 교환환다.
    h->heap[i] = h->heap[i/2];
    // 한 레벨 위로 올라단다.
    i /= 2;
  }
  h->heap[i] = item; // 새로운 노드를 삽입
}

// 최대 힙(max heap) 삭제 함수
element delete_max_heap(HeapType *h){
  int parent, child;
  element item, temp;

  item = h->heap[1]; // 루트 노드 값을 반환하기 위해 item에 할당
  temp = h->heap[(h->heap_size)--]; // 마지막 노드를 temp에 할당하고 힙 크기를 하나 감소
  parent = 1;
  child = 2;

  while(child <= h->heap_size){
    // 현재 노드의 자식 노드 중 더 큰 자식 노드를 찾는다. (루트 노드의 왼쪽 자식 노드(index: 2)부터 비교 시작)
    if( (child < h->heap_size) && ((h->heap[child].key) < h->heap[child+1].key) ){
      child++;
    }
    // 더 큰 자식 노드보다 마지막 노드가 크면, while문 중지
    if( temp.key >= h->heap[child].key ){
      break;
    }

    // 더 큰 자식 노드보다 마지막 노드가 작으면, 부모 노드와 더 큰 자식 노드를 교환
    h->heap[parent] = h->heap[child];
    // 한 단계 아래로 이동
    parent = child;
    child *= 2;
  }

  // 마지막 노드를 재구성한 위치에 삽입
  h->heap[parent] = temp;
  // 최댓값(루트 노드 값)을 반환
  return item;
}

// 우선순위 큐인 힙을 이용한 정렬
void heap_sort(element a[], int n){
  int i;
  HeapType h;

  init(&h);

  for(i=0; i<n; i++){
    insert_max_heap(&h, a[i]);
  }

  for(i=(n-1); i>=0; i--){
    a[i] = delete_max_heap(&h);
  }
}

힙 정렬 시간복잡도

최선, 평균, 최악 모두 O(nlogn)

힙 정렬 장단점

1. 장점

- 시간 복잡도가 좋은편 (최악의 경우에도 시간 복잡도인 O(nlogn)을 보장)
- 힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 필요할 때

2. 단점

- 데이터들의 상태에 따라 같은 O(nlogn) 시간 복잡도 라도 조금 느림
- 데이터의 순서가 바뀌는 불안정 정렬 알고리즘

※ 참고 - Python은 heapq라는 모듈을 통해 최소힙, 최대힙 쉽게 구현 가능

운영체제는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램의 일부만 주기억장치에 적재하여 사용한다. 이를 가상메모리 기법이라고 한다.

메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 시(페이지 부재), 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라고 한다.

페이지 교체 알고리즘 종류

1. OPT - Optimal : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체

- 프로세스가 앞으로 사용할 페이지를 미리 알아야 한다는 전제조건이 필요

- 이 전제 조건이 실제 활용에서는 알 수 있는 방법이 없기 때문에 최적 알고리즘은 구현이 불가능한 알고리즘

- 따라서 이는 실제 구현 목적보다 다른 알고리즘과 비교 연구 목적을 위해 주로 사용

2. FIFO - First In First Out : 가장 오래된 페이지를 먼저 교체

- 이해가 쉽고, 구현이 간단하다는 장점이 존재

- 그러나 활발하게 사용 중인 페이지를 계속해서 교체한다면 페이지 부재율이 높아지고 실행속도가 떨어질 위험이 있음

3. LRU - Least Recently Used : 가장 오랫동안 사용되지 않은 페이지 교체

- 최적 알고리즘(OPT)은 실제 구현이 불가능하므로, 최적 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법을 사용한 것이 LRU 알고리즘

4. LFU - Least Frequently Used : 참조 횟수가 가장 작은 페이지 교체

- 교체 대상인 페이지가 여러 개 일 경우, LRU 알고 리즘을 따라 가장 오래 사용되지 않은 페이지로 교체

5. MFU - Most Frequently used : 참조 횟수가 가장 많은 페이지 교체

- LFU 알고리즘과 반대로, 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘

- LFU와 MFU는 실제 사용에 잘 쓰이지 않음

(구현에 상당한 비용이 들고, 최적 페이지 교체 정책을 LRU 만큼 제대로 유사하게 구현해내지 못하기 때문)

6. NUR - Not Used Recently : 최근에 사용하지 않은 페이지 교체

- LRU에서 나타나는 오버헤드를 줄일 수 있음

- 최근 사용 여부를 확인하기 위해 각 페이지마다 두 개의 비트 사용 

  ▷ 참조비트(Reference Bit) : 페이지가 호출되지 않았을 때 0, 호출되었을 때 1

  ▷ 변형비트(Modified Bit) : 페이지 내용이 변경되지 않았을 때 0, 변경 되었을 때 1