Jeong in Tech

1. 데이터베이스의 이해 

1.2 데이터베이스 시스템의 개요

데이터베이스관리시스템(DBMS)

데이터베이스관리시스템(DBMS)이 사용자에게 서비스 형태로 제공되는 앱 = 데이터베이스시스템(Database System)

1.3. 데이터 베이스 관리 시스템의 목적 (a.k.a 파일 처리 시스템과의 비교)

1960년대 유일한 운영체제 지원 데이터관리 수단 = 파일(file)

이러한 방식을 '파일 처리 시스템(File Processing System)'이라고 한다.

DBMS 이전 대다수의 시스템이 이러한 파일 처리 시스템 사용.

파일 처리 시스템의 문제점: 1) 데이터의 종속 2) 중복 3) 무결성 훼손 및 4) 동시 접근 

1) 데이터의 종속: 해당 프로그램에 종속되는 파일이 생긴다. 데이터 구조의 변경이 프로그램의 변경으로 이어지며 유지보수 비용 증가. 타 프로그램과 공유 불가.

2) 데이터의 중복: 데이터 중복은 다음 세 가지 관점에서 문제가 생긴다. (1) 일관성 문제 (2) 보안성 문제 (3) 경제성 문제

3) 데이터의 무결성 훼손

4) 동시 접근 이상

1.4. 데이터베이스 관리 시스템의 특징

1) 프로그램 및 데이터의 추상화: 데이터가 어떻게 물리적으로 저장장치에서 관리되는지 상세한 정보보다는 사용자가 데이터의 의미만으로 접근할 수 있도록 데이터에 대한 개념적인 표현을 제공.

2) 자기 기술성(메타 데이터): DBMS가 데이터베이스 자체 뿐만 아니라 데이터에 대한 정의나 설명에 대한 것까지 포함하고 있는 특성

3) 데이터 공유와 일관성: 여러 사용자의 요청 작업을 최대한 동시에 처리함으로써 전체적인 처리성능을 향상시킴. 또한 이러한 동시 작업 시 발생 가능한 데이터 일관성 문제를 해결하기 위해, 단일 논리 작업을 수행하는 트랜잭션과 동시성 제어기법이라는 명령어 집합 포함.

4) 다중 뷰: 사용자들은 필요에 따라 서로 다른 관점으로 데이터를 바라볼 필요가 있으며, 이를 위해 사용자의 역할과 권한에 맞는 데이터에 접근 가능하도록 데이터베이스에 대해 필요한 부분만 추출해서 제공.

1.5 데이터베이스 관리 시스템의 구조

1) 데이터 추상화, 데이터 독립성 충족 필요
2) 3단계 구조: 내부 - 개념 - 외부

• 내부 단계: 가장 낮은 추상화 단계. 내부 스키마에 의해 기술됨. 레코드 유형 정의 등 구체적인 사항에 대해 정의.
• 개념 단계: 데이터 베이스의 전체 구조를 추상화 하는 단계. 
• 외부 단계: 추상화의 최상위 단계. 외부 스키마(=뷰)에 의해 기술됨.

3) 단계간 사상(mapping)

• 외부-개념 사상: 외부 스키마(뷰) 와 개념 스키마 간의 대응 관계. 논리적 데이터 독립성 확보 기능.
• 개념-내부 사상: 개념 단계의 데이터 스키마가 디스크 내의 내무 필드와 어떻게 대응하는가를 정의. 즉, 물리적 데이터 독립성 확보.

1.6. 데이터베이스 언어

1) 데이터 정의 언어(DDL): 데이터 베이스의 물리적 저장 구조와 데이터의 원시수준의 특징을 규정하는 언어. 

2) 데이터 조작 언어(DML): 데이터 베이스에 의해 구조화된 데이터에 사용자가 접근 및 사용할 수 있도록 지원하는 언어

1.7. 데이터베이스 관리 시스템 아키텍쳐

1) 중앙집중식

2) 클라-서버(2티어)

3) 클라-웹서버-서버(3티어): 2티어 구조에 비즈니스 규칙을 저장하는 중간 계층인 WAS를 추가한 형태.

1.8. 데이터베이스 사용자 및 관리

2. 데이터베이스 모델링

2.1. 데이터베이스 모델링의 이해

모델링 단계

제안요청서(RFP) -> 사용자 요구 사항 분석 -> 개념적 데이터 모델링 -> 논리적 데이터 모델링 -> 물리적 데이터 모델링 -> 내부 스키마 저장

• 요구 사항 분석: 도출, 분석, 기록으로 단계 세분화됨. 
  • 도출 --(요구사항 명세서, requirement specification)--> 분석 --(요구사항 정의서, requirement definition)--> 기록 단계
• 개념적 데이터 모델링: 추상화 기법 사용. 이를 위해 다양한 개념적 데이터 모델들이 제안 및 사용되었고, 대표적인 것이 E-R 모델.
• 논리적 데이터 모델링: DBMS에 맞는 구현 데이터 모델인 스키마로 변환하는 작업. 일반적으로는 관계형 모델 사용.
• 물리적 데이터 모델링: 논리적 데이터 모델링 후 생긴 논리 스키마는 데이터들의 논리적 구성만을 명시하는데, 이를 데이터베이스 파일의 물리적 저장 방식을 결정하는 과정.

2.2 사용자 요구사항 분석 과정

2.3. ER 모델(Entity-Relationship Model)

• 정의 및 관련 용어:
  • 개체(entity): ER모델의 가장 기본 요소. 실세계에 존재하는 유,무형 대상. - ex) 학생, 교수, 과목, 계좌
  • 개체 집합(entity set): 실세계에 존재하는 유,무형 대상들의 모임.
  • 속성(attribute): 그 개체를 특정 지을 수 있는 다수의 속성들. 일부 속성은 개체를 유일하게 구별하는 역할. - ex) 학생번호, 학생 이름, 성별, 나이
  • 값(value): 구체적 속성 값 - ex) 학생번호(속성)-201934(값)
• 하나의 DB는 다수의 개체 집합으로 이루어진다. 
• 이러한 ER모델을 표기하는 방법은 시간을 거치며 발전해왔는데, 최근에는 UML(Unified Modeling Language)라고 불리는 표기법을 사용한다.
  • 키(key): 모든 개체를 고유하게 구분하는 존재
  • 도메인(domain): 속성이 가질 수 있는 모든 가능한 값들의 범위

• 관계 집합: 
  • 정의: 
• 속성:
  • 단순 속성 / 복합 속성: 들여쓰기. 여러 값을 가질 수 있는 속성이어야 한다. ex) 나이, 
  • 단일값 속성 / 다중값 속성: { }
  • 유도 속성 / 저장 속성: () 다른 속성값으롭퉈 유도되어 결정되는 속성값과 실제 값을 저장해야만 의미가 유지되는 속성값.
• 제약 조건
  • 사상수
  • 참가 제약조건: 관계에 참여하는 개체 집합의 범위
    
    • 하나의 실선(일부 참가)
    • 이중 실선(전체 참가)
  • 키 속성
    • 밑줄 표시

2.4. ER모델 기호

ERD -> 그림 예시로 주어지면 읽을 줄 알아야 함.

약한 집합 관계: 기본 식별 개체가 삭제되면 함께 삭제되는 개체. 키 속성이 일반 밑줄이 아닌 점선 밑줄 처리된다.

3. 관계형 모델

논리적 데이터 모델링 단계를 다룬다. 논리적 데이터 모델링 단계는 개념 모델링 다음 단계로, 데이터베이스에 저장될 데이터의 논리적 구조인 스키마(schema)를 산출하는 단계였다. 

대표적 구현 모델인 관계형 모델의 기본적 이론과 용어에 대해 학습한다.

구체적으로는 릴레이션을 조적하기 위한 관계 대수 연산자, 관계 ㅇ대수 연산식, ERD를 관계형 모델로 변환하는 방법.

#4. MySQL을 이용한 데이터베이스 모델링

#5. SQL

6. 정규화

6.1. 좋은 릴레이션과 나쁜 릴레이션

나쁜 데이터베이스 모델링

1) 데이터의 중복

2) 갱신 이상: 삽입 이상, 삭제 이상, 수정(또는 갱신) 이상

좋은 릴레이션의 고려사항

1) 한 릴레이션 내의 컬럼 간의 관계 분석

2) 원하지 않는 데이터의 종속과 중복 제거

3) 새로운 컬럼들이 데이터베이스에 추가될 때, 기존 컬럼과 관계 수정 최소화

6.2. 함수적 종속성

6.2.1. 함수적 종속성의 정의

어떤 릴레이션을 여러 개의 릴레이션으로 분할함으로써 데이터의 중복을 최소화 시키는 방법 = 정규화

-> 그럼 어떤 컬럼을 떼네고 어떻게 릴레이션을 분할해야 하지? -> 함수적 종속성 고려

1) 릴레이션 인스턴스(스키마 자체 X 인스턴스 O)를 분석하여 속성들(컬럼들) 간의 연관관계를 표현한 것

2) 릴레이션 효율성을 향상시켜 좋은 릴레이션으로 변환하는데 이용되는 중요한 개념

임의의 릴레이션 스키마 R의 인스턴스 r에 포함되는 서로 다른 두 레코드 r1, r2와 컬럼 집합 X와 Y에 대해, r1[X] = r2[X] 일 때, r1[y] = r2[y] 이면 함수적 종속성 X -> Y가 성립한다. 

ex) 위 그림1을 보면 등급이 할인율을 결정한다. 예를 들어 GOLD(등급) 면 무조건 5%(할인율). 즉, 등급은 할인율에 종속된다. 등급은 "결정자", 할인율은 "종속자"가 된다. 

함수적 종속성의 확장

하나의 릴레이션에는 수 개~수십 개의 함수적 종속성이 존재할 수 있다. 우리가 눈으로 찾아낸 게 실제로 존재하는 모든 종속성을 찾았다고 효율성 여부를 판단하기 어렵다. 

1) 함수적 종속성은 릴레이션의 효율성 여부에 중요한 판단 기준.

2) 그러나 릴레이션의 인스턴스만으로 내재된 모든 함수정 종속성을 찾아내기 어렵다. 

3) 판별되지 않은 모든 함수적 종속성을 찾기 위해 추론 규칙을 사용하여 함수적 종속성을 확장.

4) 클로저(closure): 판별된 함수적 종속성 집합으로부터 유추할 수 있는 모든 함수적 종속성 집합.

* F: 눈으로 찾아낸 모든 종속성 집합

** F+ : 추론 규칙을 사용해(=함수적 종속성을 확장해) 찾아낸 최종 모든 종속성 집합.

함수적 종속성의 추론 규칙 based on 암스트롱 공리

카노니컬 커버

1. 함수적 종속성 추론 규칙으로 확장된 클로저에는 "자명한 종속성"과 "중복된 종속성"을 포함한다.

• 자명한 종속성: A-> A / 의미가 당연
• 중복된 종속성: X -> AB, X->B / 의미가 여러번 존재. -> 문제

2. 불필요한 함수적 종속성(중복된 종속성)을 제거한 표준형으로 변환 후 정규화를 수행해 효율성을 높이자! -> 카노니컬 커버!

3. 표준형 조건

• F의 모든 함수적 종속성의 오른편 속성(=종속자)은 반드시 1개
  • {x,y} -> {z} (o)
  • {x} -> {a,b} (x, 가능은 하지만 표준형은 아님)
• F에서 X -> A를 X의 진 부분집합 Y에 대하여 Y->A 로 교체했을 때, 그 집합이 F와 동등한 집합이 불가능.
• F에서 어떤 함수적 종속성을 제거했을 때, 그 집합이 F와 동등한 집합이 불가능.

6.3. 정규화

정규형의 개념

1. 정의: 이상 현상을 최소화하도록 특정 조건을 갖춘 릴레이션의 형식

2. 분류: 제1정규형~제5정규형까지 존재한다. 보통 현업에서는 2~BC정규형이 많이 쓰인다.

3. 기능: 릴레이션을 효과적으로 표현, 검색 알고리즘을 효과적으로 작성할 수 있도록 지원, 바람직하지 않은 삽입, 수정, 삭제 등 이상 발생 방지, 새 데이터 삽입 시 릴레이션 재구성의 필요성 축소

제1정규형

• 가장 조건이 단순한 정규형
• 릴레이션 스키마에서 정의된 모든 속성의 도메인이 원자값을 갖는 상태
• 관계형 모델 조건에 따라 자동 적용되는 정규형

제2정규형

• 제1정규형 + 기본키가 아닌 속성들이 기본키에 대해 완전 종속인 상태

제3정규형

• 제2정규형 + 기본키가 아닌 속성들이 어떤 키에도 이행적으로 종속하지 않는 상태.

BC정규형

• 어떤 릴레이션 스키마 R에서 성립하는 X -> A 형태의 모든 함수적 종속성에 대해 X가 R의 수퍼키인 상태.

7. 데이터 저장과 파일

7.1. 물리적 저장 장치(메모리)

* 휘발성(volatile): 전원 공급이 중단되면 데이터가 소멸되는 특징.

7.2. 논리적 저장 장치(파일)

7.2.1. 파일의 구성

• 파일: 데이터 영구 저장 위해 사용되는 가장 기본이 되는 논리적 구조
• 블럭: 파일을 고정 길이로 분할하여 생긴 균등한 크기의 데이터 묶음. 일반적으로 메모리와 디스크 간 데이터 전송 단위로 사용.
• 레코드: 블럭을 구성하는 요소. 더 이상 분리될 수 없는 최소 데이터 저장 단위.
  • 고정 길이 레코드: 고정적인 바이트 수를 갖는 레코드를 저장하는 방법 - ex) 이름(보통 3글자)
    1.  데이터 접근. 모든 레코드는 k바이트로 구성. -> i번째 레코드 접근 (i-1)*k+1 바이트부터 k개의 바이트를 읽어 접근.
       • 문제: 길이가 고정되어 있기 때문에 잔여 공간 발생
       • 해결책: 
         1. 남겨둔다(잔여 고정 길이 레코드 할당) -> 메모리 낭비 발생.
         2. 한 레코드를 두 블럭으로 나누어 저장한다. -> 효율적 저장 가능 but 레코드 접근 시 두 블럭을 접근해야 함(연산 2배)
       • 문제: 레코드 삭제시 해당 레코드가 저장된 위치에 빈 공간 생성되고, 이렇게 노는 공간, 즉 메모리 낭비가 발생하게 된다.
       • 해결책:
         • 마지막 레코드로 공백 대체 -> 공간의 낭비는 막지만 레코드 순서가 달라져 검색 시 시간이 더 낭비될 수 있다.
         • 삭제 레코드 이후의 레코드를 모두 앞으로 당김. -> 낭비도 막고 순서도 지키지만(검색 효율도 그대로), 모든 레코드 이동 시 시간이 많이 걸린다.
         • 가용 리스트 관리.
           • 동작 원리: 파일 헤더에 공백 레코드 포인터를 담고, 삭제 시 해당 공백을 가리키는 포인터를 추가한다. 새 레코드 추가 시 포인터를 따라가면 됨. -> 이점 많음. 가장 많이 사용되는 방법.
  • 가변 길이 레코드: 블럭에 저장되는 레코드의 길이가 서로 다를 떄 레코드에 가변적인 길이를 할당하는 방법.
    • 필요 상황 ⭐️
      • 한 블럭 내에 저장되는 레코드 유형이 둘 이상
      • 길이가 고정되지 않은 컬럼의 개수가 하나 이상
      • 레코드가 멀티셋을 허용한 컬럼을 가질 때 
        • 멀티셋: 레코드의 컬럼값이 여러 개인 컬럼. -> 관계형 모델에는 없지만, 몇 다른 모델에서는 이러한 멀티셋을 지원하는 경우 있음.
    • 동작 원리:
      • 첫 번째 들어오는 가변 길이 컬럼/행 있다? (포인터 저장)
      • 해당 포인터 따라가면 값 + 해당 값 앞에 특정 길이만큼 Null(가용 공간) 저장
        
        • 슬롯 페이지 구조 ⭐️: 가변 길이 레코드를 저장, 관리하기 위해 사용되는 대표적인 구조. 
          
          • 블럭 초반부는 블럭 헤더로 구성. 블럭에 대한 요약 정보를 담고 있어 레코드 빠른 검색 가능케 함.
          • 신규 레코드는 중간에 있는 가용 공간의 뒤쪽에서부터 쌓이게 됨.

7.2.2. 파일 처리 시스템 

• 파일 구조화
  • 정의: 파일 수준에서 레코드 관리하는 기법
  • 종류: 힙 파일 구조, 순차 파일 구조, 해시 파일 구조
    • 힙 파일 구조: 저장 순서 고려 없이 파일 내 임의의 위치에 배치
      • 저장은 빠르나, 추후 검색 시 많은 시간 소요도
    • 순차 파일 구조: 레코드들이 탐색키 기준으로 정렬되어 저장
      • 삽입/삭제에 많은 비용
      • 오버플로우 블럭: 순차파일구조에서 레코드의 정렬된 상태 유지를 위해 삽입된 신규 블럭
    • 해시 파일 구조: 해시 함수 사용하여 블럭 주소 계산

7.3. 저장장치 관리

7.3.1. 데이터 관리의 필요

저장 장치 접근(= 블록 전송)

• 파일(논리적 관점의 저장 객체)
• 블록(물리적 단위의 저장 객체)

• 버퍼 관리자: DBMS상의 소프트웨어는 필요 블록 있을 시 버퍼 관리자에게 해당 블록 요청.
  • 요청된 블럭이 버퍼에 있으면 버퍼 관리자는 블럭이 위치한 메모리 주소를 프로그램에 전달
  • 없으면, 버퍼 관리자는 버퍼 내의 새로운 공간 할당 후 해당 블럭 적재
  • 더 적재할 공간 없으면 버퍼에 있는 기존 블럭을 선택해 해지하고 해당 블럭 적재
    • 버퍼 교체 전략: 운영체제 메모리 부분 참조
      • LRU(Least Recently Used): 가장 적게 참조된 블럭을 교체
      • MFU(Most Frequently Used): 특정 기간 동안 가장 여러번 사용된 블럭을 선택해 교체
  • 고정 블록 설정 및 블럭 강제 출력 등

8. 인덱싱과 해싱

8.1. 인덱스의 이해

정의:

인덱스란, DBMS에서 요청된 레코드에 빠르게 접근할 수 있도록 지원하는 데이터와 관련된 부가적 구조

인덱스 탐색키 이용해 해당 레코드가 저장된 블럭을 디스크 저장장치 또는 메모리에서 파악해 해당 블럭 빠르게 적재

종류: 순서 인덱스, 해시 인덱스

• 순서 인덱스: 특정 값에 대해 정렬된 순서 구조
• 해시 인덱스: 버킷의 범위 안에서 값의 균일한 분포에 기초한 구조로 해시 함수가 어떤 값이 어느 버킷에 할당할지 결정

평가 기준⭐️: 접근 비용, 유지 비용, 공간 비용 -> 삭제 비용 X

8.2. 순서 인덱스

특징: 탐색키 활용한 빠른 접근. 

종류: 밀집 인덱스, 희소 인덱스, 다단계 인덱스

• 밀집 인덱스
  • 모든 레코드에 대해 인덱스 엔트리 쌍 가짐
  • -> 검색 속도 빠름(적은 양의 디스크-메모리 입출력으로  but 모든 레코드에 대해 포인터(인덱스) 가지기 때문에 메모리 많이 차지. 
• 희소 인덱스
  • 일부의 레코드에 대한 탐색키 값만을 인덱스 엔트리 쌍 가짐.
  • -> 인덱스가 차지하는 메모리 더 적지만 검색 속도는 더 느림.

• 다단계 인덱스 ⭐️
  • 밀집 인덱스와 희소 인덱스의 장점만 결합. 
  • 밀집 인덱스처럼 인덱스 용량이 커, 인덱스의 크키 > 메모리 크기인 경우, 인덱스 블ㄹ럭을 읽어 들이는 입출력(I/O)비용이 증가해 탐색 시간이 증가.
  • 인덱스에 대한 인덱스를 구성하자!
    • 내부 인덱스: 레코드를 직접 가리키는 인덱스. 밀집 인덱스로 구성. 
    • 외부 인덱스: 레코드를 직접 가리키는 인덱스(내부 인덱스)를 가리키는 인덱스. 희소 인덱스로 구성.

8.3. B+- 트리 인덱스 ⭐️

8.3.1. 정의

• 다단계 인덱스의 일종
• 순서 인덱스 문제: 파일이 커질수록 데이터를 탐색하여 접근하는 비용이 커진다는 단점.
• 해결책: B+- 트리 인덱스. 경로 길이가 같은 높이 균형 트리 형태로 구성된 인덱스로, 검색의 속도를 일정하게 향상시켜 안정적 데이터 검색이 이루어질 수 있도록 함. 현대 상용 DBMS에서 가장 널리 사용되는 순서 인덱스의 일종.

8.3.2. B+- 트리의 구조

• 인덱스 세트: 루트 노드와 중간 노드로 구성. 단말 노드의 탐색키 값을 찾아가는 경로를 제공. [n/2]~n사이의 개수를 자식으로 소유. *n:차수
• 순차 세트:  단말 노드로 구성. 모든 노드가 순차적으로 서로 연결되어 있다. 탐색키에 대한 실제 레코드를 지칭하는 포인터를 제공. [(n-1)/2]개의 탐색키를 포함. 

8.3.3. 검색, 삽입, 삭제 연산

8.4. 해싱

8.4.1. 해싱과 버킷

• 해시(hash): 함수를 사용해 데이터 배분 및 접근하는 기법
• 버킷(bucket): 한 개 이상의 레코드를 저장할 수 있는 저장공간의 단위. 크기는 디스크 블록의 크기와 일치?

8.4.2. 정적 해싱

특징: 1) 버킷의 갯수가 고정된 해싱 기법 2) 키 값이 K인 레코드 삽입 3) 키 값이 K인 레코드 검색

단점: 1) 데베 크기 커질 수록 성능 감소 2) 초기 비용 큼 3) 재구성시 대량의 비용 발생 => 동적 해싱 기법 제안됨

문제1) 충돌과 동거자

• 충돌: 서로 다른 두 레코드가 동일한 버킷에 대응. 
• 동거자 ⭐️: 동일한 버킷에 있는 레코드들.

문제2) 오버플로 ⭐️

버킷에 레코드를 저장할 여유 공간이 없는 상황

추가적인 버킷을 할당하여 처리

오버 플로우가 발생할 수록 접근 시간이 길어지고 해시 성능 저하

=> 해시 인덱스

8.4.3. 동적 해싱

정의: 버킷의 개수 가변적. 데베 증대 혹은 축소에 따른 인덱스 구조를 조절 및 해시 함수를 동적 변경

• 확장성 해싱 ⭐️: 동적 해싱의 일종으로 디렉터리(버킷 주소 테이블)와 버킷의 2단계 구조.
  
  • 모조키(pseudo key): 확장성 해싱 함수는 먼저 레코드의 키값을 일정 길이의 비트 스트링으로 만드는 데 이 때 사용되는 키. 모조키의 처음 d비트가 디렉터리에 접근하는 데 사용된다.
  • 버킷 헤더: 모조키의 첫 번째 숫자부터 숫자 i까지 일치함을 표시.

디렉터리에 숫자 3(버킷 헤더)은 모조키 첫 3글자를 넣겠다는 의미이다. 각 버킷의 3,3,2,1은 각 모조키의 첫 n숫자를 보겠다는 의미이다. 디렉토리에 담겨진 모조키 시작 3자리 숫자들은 각 조건(000, 001, 01, 1로 시작하는 값)에 맞는 버킷에 담긴다.

8.5. 비트맵 인덱스 ⭐️⭐️

비트맵 인덱스

개념: 탐색키의 중복 비율이 높은 컬럼을 대상으로 하는 질의를 효율척으로 처리하기 위해 고안된 특수 형태의 인덱스. 예를 들어, 탐색키가 성별인 경우. 50%는 여자, 50%는 남자가 된다.

비트맵: 간단한 비트의 배열. 0과 1의 나열.

• i번째 비트가 0이다. = 조건과 일치 하지 않는다.
• i번째 비트가 1이다. = 조건과 일치한다.

예제에서 볼 수 있듯이, 컬럼에 대해 값이 비교적 작은 규모의 집합으로 만들 수 있다.

예제)

특징:

1) 컬럼에 대한 값의 범위가 유한하고 비교적 개수가 적은 규모일 때 용이

2) 실제 릴레이션 크기에 비해 비트맵 인덱스의 크기는 매우 작은 것이 장점.

10. 트랜잭션과 동시성 제어

10.1. 트랜잭션 이해

데이터 동시 접근의 문제

트랜잭션: 데이터베이스를 조작하기 위한 하나의 논리적 단위를 이루는 일련의 연산의 집합. 데이터베이스를 사용하여 처리하는 작업을 하

나의 묶음으로 인식해 묶음 단위로 실행되도록 정의한 개념.

ex) 예금 인출

작업 단위: 예금 1000원 인출

일련의 연산: Read(A), A=A-1000, Write(A)

• Read(A): 잔액 읽기
• A=A-1000: 연산 수행
• Write(A): 연산 수행 후 결과로 잔액 재설정

이러한 연산 작업을 하나의 묶음으로 데이터를 처리!

10.2. 트랜잭션 특징

ACID 특성⭐️

• 원자성(Atomicity): 하나의 트랜잭션에 포함된 모든 연산은 완전히 수행되거나 전혀 수행되지 않음
• 일관성(Consistency): 특정 트랜잭션이 수행되기 전과 후에 데이터 베이스가 일관된 상태를 유지
• 고립성(Isolation): 특정 트랜잭션이 데이터베이스를 갱신하는 동안 다른 트랜잭션에 의해 방해받지 않음
• 지속성(Durability): 완료된 트랜잭션의 결과는 어떠한 시스템의 장애에도 데이터베이스에 반영되어야 함
  • 트랜잭션 실행하다 시스템 오류 이후 실행결과가 데베에 반영되어 있는지 먼저 확인 후, 반영되지 않은 경우에만 트랜잭션 재실행.

10.3. 트랜잭션의 동작 방식

트랜잭션의 연산

• Read(X): DB에서 X라는 데이터를 읽은 후, 트랜잭션이 실행되는 메모리의 변수 X에 값을 저장하는 연산.
• Write(X): 트랜잭션이 실행되는 메모리의 변수 X에 값을 DB에 저장하는 연산.

트랜잭션 실행의 연산

• Commit
• Rollback

10.4. 트랜잭션의 동시성

동시성 고려

• 장)
  • 처리율, 자원 이용률 향상
  • 대기시간 감소로 인한 사용자 신뢰도 및 만족도 향상
  • 데이터의 가용성 향상
• 단)
  • 동시 실행으로 데이터 갱신 시 일관성 훼손 문제 발생(일관성, 무결성 훼손)
• 해결: 동시성 제어(cocurrencty control)
  • 다수의 트랜잭션이 성공적으로 동시에 실행되어도 일관성을 유지할 수 있도록 지원하는 기법.
  • 뒤에서 더 자세히

스케쥴(schedule)

• 트랜잭션에 포함된 연산의 실제 실행순서를 나타낸 것
  • 직렬 스케줄: 순차적으로 실행되는 스케쥴
  • 병렬 스케줄: 동시다발적으로 실행되는 스케쥴

직렬 가능 스케쥴

다수의 트랜잭션이 동시에 수행된 결과가 직렬 스케쥴의 결과와 동일한 스케쥴. 일관성 유지 가능한 스케쥴.

• 충돌: 서로 다른 트랜잭셔닝 연산을 수행할 때, 최소 하나의 연산이 Write 연산일 경우, 두 트랜재션은 서로 충돌(conflict)한다 라고 한다.
• 충돌 동등: 특정 스케줄 S가 있을 때 충돌이 일어나지 않는 연산의 순서를 바꿔서 충돌이 없는 스케줄 S'로 변환할 수 있는 상태.
• 충돌 직렬성 ⭐️: 순서 교환이 가능한 연산을 교환해, 직렬 스케줄의 연산과 동등하게 변환이 가능한 스케쥴

10.5 트랜잭션 회복

회복성

만약 트랜잭션 Ti가 실패하면 실패하기 전까지 실행되었던 모든 연산을 트랜잭션이 시작되기 이전 상태로 회복시켜야 한다.

Commit 된 순간, 취소가 불가하다.

회복 가능 스케줄(recoverable scedule)

모든 트랜잭션 순서쌍 Ti와 Tj에 대해, Ti가 기록한 데이터 항목을 Tj가 읽는다면 Ti의 커밋이 Tj 의 커밋보다 먼저⭐️ 나타나는 스케줄 의미.

즉, 스케줄에서 오류가 발생하더라도 Tj는 Ti가 커밋을 완료할 때까지 기다려야 함.

비연쇄적 스케줄(cascadeless schedule)

연쇄적 롤백은 많은 연산을 동반하기 떄문에 연쇄적 롤백이 일어나지 않도록 스케쥴이 제한을 둔 스케쥴.

10.6 동시성 제어

앞서 언급된 '직렬화'과 '회복화'이 동시 실행 가능 여부와 회복  가능 여부를 판별하는 기법이었다면,

동시성 제어(concurrency control)은 실제 동시 실행을 가능하게 하는 기법이다.

이러한 동시성 제어 기법은 2가지 규약을 따른다.: 1) 락 기반 규약 2) 타임 스탬프 규약

10.6.1. 락 기반 규약

정의

락(lock)을 가지고 있는 트랜잭션만 진행 가능하다는 규약이다.

약간 화장실 키 같은 개념

종류

• 공유 락(shared lock): 트랜잭션 T가 데이터 항목 Q에 공유하는 형태의 락을 얻으면(S로 표기), T는 Q를 읽을 수는 있으나 쓸 수는 없다.
• 배타 락(exclusive lock): 트랜잭션 T가 데이터 항목 Q에 공유하는 형태의 락을 얻으면(X로 표기), T는 Q를 읽고 쓸 수 있다.

명령어

• LS(Q):
• LX(Q):
• UN(Q):

적법한 스케줄

• 스케줄 S가 라킹 규약을 준수하는 스케줄이면, S는 주어진 락킹 규약하에서 적법한 스케쥴이라고 한다. 
• 또한 모든 적법한 스케줄에서 각 트랜잭션들에 대해 사이클(cycle)이 포함되지 않으면(-> 들이 서로 환원상태가 된 것) 락킹 규약은 충돌 직렬성을 보장(=순서대로 진행)한다고 할 수 있다.
• 언락(UN, unlock)을 너무 뒤에서 몰아서 하면, 중간에 사이클이 생기는 좋지 않은 상황이 발생할 수 있다.

2단계 락킹 규약

락 기반 규약 중 하나로, 락을 요청'만' 할 수 있는 확장 단계와 반납'만' 할 수 있는 축소 단계로 나뉜다.

직렬성을 보장하나 교착상태를 예방할 수는 없다.

엄격한 2단계 락킹 규약

기존의 2단계 락킹 규약과 달리 트랜잭션이 모든 락을 유지하다 커밋되거나 중단될 경우에만 락을 해지한다.

10.6.2. 타임스탬프 기반 규약

락킹 규약에서 트랜잭션 간의 직렬성 순서는 락을 획득한 순서에 따라 결정된다.

직렬성 순서를 결정하는 또 다른 방법은 트랜잭션 간의 순서를 미리 선택하는 것이다.

여기에 가장 보편적으로 사용되는 규약이 타임스탬프 순서 규약이다.

트랙잭션이 시스템에 들어올 때 타임스탬프를 부여하는 시스템 클럭 방법과,

새로운 타임스템프가 발급될 때마다 증가되는 논리적 계수기 값을 설정하는 논리적 계수기 방법이 있다. 

일반적인 타임 스탬프 규칙 vs 토마스 기록 규칙

(작성 예정)

10.6.3. 교착상태

트랜잭션 간 상호대기 상태에 놓여 더는 진행이 불가한 경우 이를 교착상태(deadlock)이라고 한다.

DBMS에서는 트랜잭션의 교착상태 여부를 파악하고 처리하는 여러 방법을 사용한다.

1. 교착상태 방지(prevention)
   • wait-die 기법
     비선점유 기반. 락이 걸린 데이터 항목 요청 경우, 요청한 트랜잭션이 요청 받은 트랜잭션보다 먼저 시행된 경우(=요청한 쪽의 타임스탬프 값이 더 작은 경우)에만, 락이 반환되길 기다린다. (아니면 뺸 먹고 기다릴 수도 없다.)
   • wound-wait 기법
     선점유 기반. 락이 걸린 데이터 항목 요청 경우, 요청한 트랜잭션이 요청 받은 트랜잭션보다 나중에 시행된 경우(요청한 쪼그이 타임스탬프 값이 더 큰 경우)만, 락이 반환되길 기다린다. (아니면 뺸 먹고 기다릴 수도 없다.)
2. 교착상태 탐지와 복구(detection & recovery)
   • 탐지(detection): 대기 그래프(wait-for graph)라는 방향성 그래프를 이용해 교착상태를 확인 가능하다.
   • 회복(recovery): 희생자(victim, 롤백시킬 트랜잭션)을 선택한 뒤 롤백 시킨다. 간혹 무한정 기다림(starvation)이 발생하기도 한다.

11. 회복 시스템

11.1 회복 시스템 개요

11.1.1 실패의 유형

• 트랜잭션 실패: 논리적 오류 혹은 시스템 오류로 구분. 논리적 오류는 트랜잭션이 잘못된 데이터의 입력 등으로 정상 실행이 안되는 상태이고, 시스템 오류는 dBMS가 교착상태 같은 상황에 도달해 실행 지속이 어려운 상태.
• 시스템 장애: 하드웨어 고장 혹은 소프트웨어 오류로 인한 휘발성 저장장치의 내용 손실 및 트랜잭션 처리 중단 상태
• 디스크 실패: 비휘발성 디스크 저장 장치의 일부 혹은 전체의 손상 및 고장. 데이터의 손상 및 손살 상태.

11.1.2 회복 데이터의 구성

회복의 방법은 바로 복제본을 두는 것이다.

복제본 생성의 2가지 방법

• 백업(backup): 디비 일부 또는 전체를 다른 저장장치에 주기적으로 복제하는 방식
• 로그(log): 디비에서 변경 연산이 요청될 때마다 데이터 변경 이전 이후 값을 별도의 파일에 저장하는 방식

11.1.3. 저장장치 구조와 연산

11.2 로그 기반 회복

DB가 수행한 모든 수정 작업을 기록한 여러 종류의 로그를 사용해 회복하는 시스템

WAL(Write-ahead Log)

트랙잭션은 DB 수정 전, 로그 레코드를 생성해 기록한다.

11.2.1 로그 레코드 종류

Redo(Ti) 

• 트랜잭션 Ti 에 의해 수정된 새로운 값으로 DB의 데이터 값 수정. 
• <Ti start>를 갖고 있고 <Ti commit> 혹은 <Ti abort> 레코드를 포함할 경우, Ti 는 Redo 되어야 한다.

Undo(Ti) 

• 트랜잭션 Ti 에 의해 수정된 모든 데이터 항목을 이전 값으로 복귀 완료 후, <Ti abort>.
• <Ti start>를 갖고 있지만,  <Ti commit> 혹은 <Ti abort> 레코드를 포함하지 않을 경우, Undo 되어야 한다.

11.2.2 데이터베이스 변경과 커밋

11.2.3 회복의 유형

• 지연 갱신 회복(deferred update restore)
  부분 커밋까지는 디스크 반영을 지연시키고 로그에만 기록. 실패 시 별도의 회복 작업 없이 로그만 수정
• 즉시 갱신 회복(immdidate update restore)
  갱신 요청을 바로 디스크에 반영. 실패 시 디스크에 반영된 갱신 내용을 로그를 바탕으로 회복

11.2.4 체크 포인트를 이용한 회복

로그 기반 회복 시스템의 한계

시간이 지남에 따라 로그가 계속 증가해 로그 탐색 비용이 매우 커짐. -> 체크 포인트 기법 제안

체크 포인트 기법 발생시⭐️

• 현재 시점에 메인 메모리 버퍼 블록에 존재하는모든 레코드를 안정 저장 장치로 기록.
• 수정된 모든 버퍼 블럭을 디스크에 반영.
• 로그 레코드 <checkpoint ListT>를 안정한 저장장치에 기록.  -> checkpoint 시 실행된 트랜잭션( <start>가 있었던 모든 Ti)은 모두 ListT에 담기게 된다.

11.3 회복 알고리즘

11.3.1. 시스템 장애 후 회복 알고리즘

11.4. 백업

# Reference

<데이터베이스시스템>, 정재화 지음

목차

#1. 운영체제 소개

##1.1. 운영체제 정의

##1.2. 운영체제 역할

##1.3. 컴퓨터 시스템과 운영체제

##1.4. 커널 모드와 사용자 모드 

#2. 프로세스와 쓰레드

#3. 프로세스 스케줄링

#4. 병행 프로세스

#3. 프로세스 스케줄링

##3.1. 프로세스 스케줄링

###3.1.1. 스케줄링 단계

###3.1.2. 스케줄링 목표

###3.1.3. 스케줄링 정책

- 문맥(Context)과 문맥 교환(Context Switching)

  문맥이란 CPU의 모든 레지스터(특히 프로그램 카운터(PC))와 기타 운영체제에 따라 요구되는 프로세스의 상태들을 의미한다. 문맥 교환이란 CPU가 현재 실행하고 있는 프로세스의 상태를 프로세스 제어 블록(PCB, 그중 PC)에 저장하고, 다른 프로세스의 PCB로부터 문맥을 복원하는 작업을 의미한다.

  ex) 프로세스 A 작업이 진행 중이다가 프로세스 B가 갑자기 실행되어야 할 경우. 현 CPU 레지스터에 있는 값들을 프로세스 A PC에 임시보관 후, 프로세스 B의 정보를 프로세스 B의 PC에서 꺼내와 CPU에 할당 후 실행.

###3.1.4 스케줄링 평가 기준

평균대기시간: 각 프로세스가 수행이 완료될 때 까지 준비 큐에서 기다리는 시간의 합의 평균값.

평균반환시간: 각 프로세스가 생성된 시점부터 수행이 완료된 시점까지의 소요시간의 평균값

ex) 

##3.2. 스케줄링 알고리즘

###3.2.1. FCFS 스케줄링

- FCFS(First-Come First-Served): 들어온 순서대로 처리

- 비선점 방식: 한 번 들어오면 인터럽트 되지 않음.

- 준비 큐에 도착한 순서에 따라 디스패치

- ex)

여기서

평균대기시간은 A(0) + B(7) + C(11) + D(12) = 30 를 4로 나누면 7.5

평균반환시간은 A(7) + B(11) + C(12) + D(15) = 45 를 4로 나누면 11.25

- 장점: 가장 간단

- 단점: 1) 짧은 프로세스가 긴 프로세스를 기다리거나, 중요한 프로세스가 나중에 수행될 수 있음 -> 시분할 운영체제나 실시간 운영체제에는 부적합. 2) 프로세스들의 도착 순서에 다라 평균 반환 시간 차이가 큼.

###3.2.2. SJF 스케줄링

- SJF(Shortest Job First): 준비 큐 작업들 중 예상 시간이 가장 짧은 작업을 먼저 처리(디스패치)하는 방식.

- 비선점 방식

- ex) FCFS 방식에서 든 예시와 같으나 각 작업의 도착시간이 모두 0으로 같지 않고 제각각이라는 데에서 차이.

대기시간: 

평균대기시간: (0+9+3+3) / 4 = 15 / 4 = 3.25

반환시간:

평균반환시간: (7+13+4+6) / 4 = 30 / 4 = 7.5

- 장점: 일괄처리 환경에서 구현하기 쉬움.

- 단점: 실제로는 먼저 처리할 프로세스의 시간을 예상할 수 없다. 2) FCFS방식과 마찬가지로 비선점 방식이기 때문에,  새로 들어온 짧은 프로세스가 긴 프로세스를 기다리거나 중요한 프로세스가 나중에 수행될 수 도 있음. -> 시분할 운영체제나 실시간 운영체제에는 부적합. 

###3.2.3. SRT 스케줄링

- SRT(Shortest Remaining Time): 준비 큐 작업들 중 예상 시간이 가장 짧은 작업을 먼저 처리(디스패치)하는 방식. 치.

- SJF 알고리즘의 선점 방식

- ex) 선점 방식(실행 중인 프로세스에 인터럽트 가능. 이 알고리즘에서 인터럽트 기준은 예상 시간)이기 때문에 A가 시랳ㅇ중이다가도 B가 들어오면 

대기시간: 

평균대기시간: (8+1+0+2)/4 = 11/4 = 2.75

반환시간:

평균반환시간: (15+5+1+5) / 4 = 26/4 = 6.5

- 장점: SJF보다 평균대기시간이나 평균반환시간에서 효율적

- 단점: 1) 마찬가지로 실제로는 프로세스의 시간을 예상할 수 없고, 2) 각 프로세스의 실행시간 추적, 선점 위한 문맥 교환 등의 오버헤드가 큼

###3.2.4. RR 스케줄링

- RR(Round Robin): 앞서 봤던 FCFS 방식(준비 큐에 도착한 순서대로 디스패치)이지만, 차이점은 정해진 시간 할당량에 의해 실행 시간 제한이 있다는 점. 주어진 시간이 넘어가면 다시 CPU를 빼앗기고 준비 큐의 뒤로 이동하게 된다.

- 선점 방식

- ex) 시간 할당량 = 4 라고 가정한다면, 아래와 같이 처리되게 된다.

- 대기시간

- 평균대기시간: (5+2+4+7)/4 = 18/4 = 4.5

- 반환시간

- 평균반환시간: (12+6+5+10)/4 = 33/4 = 8.25

- 장점: CPU를 독점하지 않고 공평하게 이용 -> 시분할 운영체제에 가장 적합

- 단점: 1) 시간할당량이 너무 크면 FCFS 스케줄링과 동일 2) 시간할당량이 너무 작으면 너무 많은 문맥 교환 발생으로 오버헤드 커짐 

###3.2.5. HRN 스케줄링

- HRN(Highest Response Ration Next): 준비 큐에서 기다리는 프로세스 중 응답 비율이 가장 큰 것을 먼저 디스패치

- 비선점 방식

- 응답 비율: 예상실행시간이 짧을 수록, 대기시간이 길수록(오래 기다릴 수록) -> 응답 비율이 커짐

- ex) 비선점 방식이므로 한 작업이 끝날 때까지 인터럽트 되지 않는다. 가장 먼저 들어온 A가 처리되는 동안 들어온 B,C,D는 A가 작업이 끝나는 시점에 맞춰 응답 비율을 비교하게 된다. 이 시점에서의 응답 비율은 각각 2.25, 4, 1.67로, 가장 응답 빙비율이 큰 C가 다음 작업으로 선정되어 CPU를 할당 받게 된다. C가 끝나는 시점에서도 마찬가지로 추후 작업 발생.

- A가 끝나는 시점의 남은 작업 B,C,D의 응답 비율

- B가 끝나는 시점의 남은 작업 B,D의 응답 비율

- 대기시간: 생략

- 평균대기시간: 4

- 반환시간: 생략

- 평균반환시간: 7.75

- 장점: SJF 스케줄링의 단점 보완(기다릴 수록 응답비율이 커져 무작정 대기시간이 길어지는 걸 막아줌)

- 단점: 실제로는 프로세스의 시간 예상 불가.

###3.2.6. 다단계 피드백 큐 스케줄링

- 다단계 피드백 큐 스케줄링: 앞서 나온 RR방식의 확대. I/O 혹은 연산 프로셋스의 특성에 따라 서로 다른 시간 할당량 부여.

- 선점 방식

-- 1) RR방식과 마찬가지로 일정 시간 내에 처리되지 못하면 할당된 CPU 뺴앗기고 준비 단계로 돌아간다. 하지만 다단계 방식은 단계별로 준비 큐가 따로 존재해, 기존에 있던 준비큐의 뒤로 돌아가는 것이 아닌 다음 단계의 준비큐의 뒤로 들어가게 된다는 차이가 있다. 2) 단계가 커질 수록 시간 할당량이 커진다. 즉, 뒤로 갈 수록 CPU를 잡고 작업을 처리할 수 있는 시가닝 길어진다. 3) 단계 k의 준비 큐에 있는 프로세스가 디스패치 되려면, 단계 1부터 k-1까지 모든 준비큐가 비어있어야만 한다.

- 특징: 

1) I/O 위주 프로세스는 높은 우선권 유지

2) 연산 위주의 프로세스는 낮은 우선권이지만 긴 시간 할당량 

###3.2.7. 스케줄링 알고리즘 정리

- 비선점 방식의 3가지

- 선점 방식의 3가지

- 각 방식 사이의 관계:

1) FCFS을 선점 방식 + 시간 할당량 부여 = RR

2) RR을 단계별로 처리 => 다단계 피드백 큐

3) SJF 를 선점 방식 -> SRT

4) SJF 에 대기 시간(응답 비율 개념) 추가 => HRN

한 단계 더 나아가기) 

각 알고리즘은 언제 가장 적절하게 사용될까?

4. 병행 프로세스

4.1. 병행 프로세스 개요

병행성(cocurrency)

여러 개의 프로세스 또는 스레드가 동시 수행되는 시스템의 특성

병행 프로세스

정의: 동시 수행되는 여러 개의 프로세스 또는 스레드

실행 형태:

1) CPU의 갯수에 따라 -> (1) 1개의 CPU: 인터리빙 형식 (2) 여러 개의 CPU: 병렬 처리 형식

2) 멀티프로세서 시스템에서 메모리 구조에 따라 -> (1) 강결합 시스템 (2) 약결합 시스템

프로세스 간의 관계 

• 독립 프로세스: 수행 중인 다른 프로세스에 영향을 주지도, 받지도 않음. 데이터 및 상태를 다른 프로세스와 공유 x. 특징: 1) 결정적(실행 결과는 입력에 의해서만 결정됨) 2) 재생 가능(같은 입력에 대해 항상 동일한 실행 결과)
• 협력 프로세스: 수행 중인 다른 프로세스와 영향을 주고 받는다. 데이터 및 상태를 다른 프로세스와 공유한다. 특징: 1) 비결정적(실행 결과는 실행 순서에 좌우됨) 2) 재생 불가능(같은 입력에 대해 항상 동일한 실행 결과 보장 x)

4.2. 병행성 문제

병행성 문제

정의: 협력 프로세스인 경우 발생 가능한 문제로, 동시에 임계 영역에 접근해 무결성 문제가 발생한다. 이러한 무결성 문제 방지를 위해 임계영역에 동시 접근 시 처리 순서를 정해야한다. 프로세스들끼리 어떻게 전반적으로 통신할 것인가에 대해서도 논해야 한다.

논의점: 1) 상호 배제 2) 동기화 3) 통신

1) 상호 배제

2개 이상의 프로세스가 동시에 임계 영역(동시에 사용하면 안되는 공유자원에 접근하는 코드 영역)을 수행하지 못하도록 하는 것. 

2) 동기화

2개 이상 프로세스에 대한 처리 순서를 결정하는 것. 결국 상호 배제란 임계 영역에 대한 동기화 문제로 볼 수 있다.

3) 통신

프로세스들이 데이터를 공유하기 위해 통신이 필요하다. 이러한 프로세스 간 통신을 IPC(InterProcess Communication)라고 한다. 

통신 방법에는 2가지 방법이 있다: 1) 하나의 변수를 사용 2) 메시지를 서로 주고 받음 

4.3. 세마포어 ⭐️⭐️

정의: 상호배제와 동기화 문제를 해결하기 위한 도구로 Dijkstra가 제안한 정수형 공용 변수. 즉, 2개 이상의 프로세스가 공유하는 변수.

특징:

• 이 세마포어(변수)에 저장되는 값은 보통 사용 가능한 자원의 수 또는 잠금/풀림의 상태 등 정수로 표현 가능한 값이다.
• 상황에 맞춰 0 이상인 정수로 초기화한다.
• 두 기본 연산 P, V에 의해서만 사용된다. 즉, 기존 기본 변수와 다르게 그냥 접근해서 사용할 수 있는 것이 아니라,  두 연산에 의해서만 접근 및 사용 가능하다.
• 하나 주의 점은 이러한 연산 P와 V는 기본 연산(인터럽트 되지 않고 하나의 단위로 처리되는 연산)이라는 점이다. 즉, 연산 P 또는 V 중에는 작업이 끊기지 않는다.
• 이러한 세마포어는 대기 큐(FIFO 방식으로 동작)을 가져야 한다.

연산P: 검사, 감소시키려는 시도. 이러한 연산 P에 의해서 현재 프로세스가 대기 상태가 될 수 도 있다.

void P(semaphore s)
{
	if (s > 0)
    		s--;
        else
            현재 프로세스를 대기시킴;
}

연산V: 증가. 이러한 연산 V에 의해 현재 프로세스가 다시 진행이 될 수 도 있다.

void V(semaphore s) 
{
	if (대기 중인 프로세스 없음)
            s++;
        else
            대기 중인 프로세스 1개 진행;
}

예1: 세마포어를 이용한 상호 배제 문제 해결 예시: 세마포어 mutex(=mutual exclusion lock) 초깃값은 1.

예2: 세마포어를 이용한 동기화 문제 해결 예시: 세마포어 sync 초깃값은 0 

4.4 생산자-소비자 문제 ⭐️

정의: 두 협력 프로세스 사이에 버퍼를 두고, 생산자와 소비자의 상황을 다루는 문제

*생산자: 데이터를 넣는 프로세스

*소비자: 데이터를 꺼내는 프로세스

조건:

1. 상호배제(버퍼에 여러 프로세스가 동시에 접근할 수 없어야 한다. 즉, 버퍼에 데이터를 넣고 꺼내는 동안에는 데이터를 꺼내거나 넣을 수 없다.)
2. 동기화(버퍼의 크기가 유한하므로 동기화가 필요하다. 예를 들어, 버퍼가 가득 찬 경우 생산자는 대기해야 하고, 버퍼가 빈 경우에는 소비자가 대기해야 하는 상황이 발생한다. 이 때 동기화가 필요하다.)

세마포어를 이용한 해결: 3개의 세마포어 사용.

1. mutex: mutul exclusion의 약자
2. empty: 버퍼에 존재하는 빈 공간의 갯수. 초깃값: 버퍼의 크기 n. 버퍼가 가득 찬 경우(empty=0) 생산자는 데이터를 생산하더라도 소비자가 버퍼에서 데이터를 꺼낸 후에야 버퍼에 데이터 넣는 것 가능.
3. full: 버퍼에 존재하는 데이터의 갯수. 초깃값: 0. 가용 데이터가 0인 경우에 소비자는 사용할 데이터가 없으므로 생산자가 버퍼에 데이터를 넣은 후에야 소비자는 버퍼에서 데이터를 꺼낼 수 있음.

4.5. 판독기-기록기 문제 ⭐️

정의: 여러 협력 프로세스 사이에 공유 자원을 두고, 판독기와 기록기의 상황을 다루는 문제.

*판독기: 데이터를 읽는 프로세스

*기록기: 데이터를 쓰는 프로세스

조건:

1) 상호배제: 기록기가 공유자원에 데이터 쓰는 중에는 다른 기록기나 판독기는 공유 자원에 접근 불가.

2) 그러나 여러 판독기는 동시에 공유자원에서 데이터 읽기 가능.

문제:

제1판독기-기록기 문제와 세마포어를 이용한 해결: 판독기가 공유자원에 접근 중이라면 기록기보다 판독기에 우선 순위를 주는 경우. 즉, 새로운 "판독기"는 공유 자원에 접근 가능하다. -> 기록기의 기아 상태 유발 가능한 문제.

제2판독기-기록기 문제와 세마포어를 이용한 해결: 판독기가 공유자원에 접근 중이라면 판독기보다 기록기에 우선순위를 주는 경우. 즉, 대기 중인 기록기가 있다면 새로운 판독기는 공유 자원에 접근이 불가하다. -> 판독기의 병행성이 떨어지고, 판독기의 기아 상태 유발 가능한 문제 발생.

##4.6. 프로세스 간 통신(IPC, InterProcess Communication)

병행 프로세스가 데이터를 서로 공유하는 방법으로, 1) 공유 메모리 방법 2) 메시지 전달 방법 2가지 방법이 쓰인다. 하나의 운영체제에서 두 방법을 함께 사용하는 것도 가능하다.

1) 공유 메모리 방법 ⭐️

정의: 협력 프로세스가 동일한 변수(= 공유 자원인 메모리 공간 사용)를 사용.

특징:

1) 대량 데이터 교환 가능 -> 고속 통신 가능

2) 통신상 발생 가능 문제 해결 - 응용 프로그램

2) 메시지 전달 방법 ⭐️

정의: 협력 프로세스가 시스템 호출 send(), receive()을 통해 메시지를 직접적으로 주고 받음. 

특징:

1) 소량 데이터 교환에 적합

2) 통신상 발생 가능 문제 해결 - 운영 체제

논리적 구조

-통신 링크

-통신 링크의 구현

-통신 링크의 용량

직접 통신 & 간접 통신 ⭐️

직접 통신:

간접 통신: 두 프로세스 사이에 우체국을 두고 통신.

5. 교착 상태

5.1. 교착 상태 개요

프로세스의 자원 사용 절차

요구 -> (대기) -> 사용 -> 해제

교착 상태(deadlock)

여러 개의 프로세스가 서로 상대방의 작업이 끝나기만을 기다리고 있어 어느 쪽도 영원히 진행하지 못하는 상태.

* 기아상태와 교착 상태의 차이

기아 상태는 일부는 진행될 수 있는 가능성이라도 있지만, 교착 상태는 가능성이 없다는 데에서 차이가 있다.

5.2. 교착 상태 특성

교착 상태 발생 가능 조건 4가지 ⭐️

• 상호배제(mutual exclusion): 필요로 하는 자원을 다른 프로세스가 점유하고 있으면 반드시 대기해야 함.
• 점유대기(hold and wait): 한 프로세스가 한 자원을 이미 할당 받아 점유하고 있는 상황에서, 다른 프로세스가 점유하고 있는 또 다른 자원을 요청하여 해제 되기를 기다리는 상황 가능.
• 비선점(nonpreemption): 프로세스가 할당된 자원은 그 프로세스가 사용을 마치고 스스로 반납하기 전에는 해제되지 않음.
• 환형대기(circular wait): 프로세스의 자원 점유 및 점유된 자원의 요구관계가 환형을 이루며 대기하는 상황.

자원 할당 그래프 G = (V,E) ⭐️⭐️

자원이 어떻게 할당되고 있는지를 나타내는 그래프. 이 그래프 해석을 통해 교착 상태에 있는지 확인할 수 있다. 

• 사이클이 없으면 교착 상태가 존재하지 않음.
• 사이클이 있으면 교착 상태가 발생할 수 도 있고 아닐 수도 있음.

5.3. 교착 상태 처리 기법

교착 생태를 처리하는 3가지 방법

1. 예방(prevention) : 교착 상태의 네 가지 필요 조건이 동시에 만족되는 것을 피함으로써(4가지 중 1개라도 만족되지 않도록 함으로써) 교착 상태가 발생하지 않도록 하는 방법
2. 회피(avoidance) : 프로세스에 필요한 자원의 최대량에 대한 정보를 이용하여 교착 상태가 발생하지 않도록 하는 방법 ⭐️
3. 탐지 및 복구(detection and recovery) : 교착 상태의 발생 여부를 조사해, 발생한 경우에는 적절한 조치를 취하도록 하는 방법

1. 예방

2. 회피 ⭐️

• 안전 상태와 불안정 상태
• 회피 알고리즘(2가지)
  • 변형된 자원 할당 그래프 (각 자원의 단위 자원이 1개뿐인 경우): 선언 간선을 요구 간선으로 변경. 이후 요구 간선을 할당 간선으로 변경. 이 때 요구를 할당으로 바꿔도 사이클이 생기지 않는 경우에만 자원을 할당하고 할당 간선으로 변환.
  • 은행원 알고리즘 이용(각 자원의 단위 자원이 여러 개일 수 있는 경우): 자원을 요구 받으면 그 자원을 할당해 주고 난 후의 상태를 계산해서 그것이 안전상태인지 확인. 

3. 탐지 및 복구

6. 메모리 관리

6.1. 프로세스와 메모리

메모리 관리

일반적으로 메모리를 효율적으로 관리하기 위해 다양한 관리 유형과 기법이 필요하다.

• 메모리 분할: 메모리를 고정 분할 할 것인지, 동적 분할 할 것인지
• 메모리 보호: 메모리를 어떻게 보호할 것인지 
• 메모리 배치: 다음에 실행될 프로세스를 메모리 내의 어느 곳에 둘 것인지 고려
• 메모리 호출: 언제 새로운 프로세스를 메모리에 둘 것인지 고려
• 메모리 교체: 메모리가 꽉 찬 상태에서 어떤 프로세스를 제거할 지 고려
• ...

기억장치 계층구조

레지 - 캐시 - (주)메모리 - 보조기억장치

6.2. 단일 프로그래밍 환경

• 초기의 시스템
• 하나의 프로세스만 메모리를 단독으로 사용
• 연속 메모리 할당: 프로세스는 하나의 연속된 블록으로 메모리에 할당
• 문제점
  • 메모리의 용량을 초과하는 프로세스는 실행할 수 x
  • 지속적으로 사용되지 않는 프로세스도 메모리에 계속 적재
  • 한 명의 사용자가 메모리를 전용으로 사용 -> 자원 낭비

6.3. 다중 프로그래밍 환경

• 현대의 시스템
• 여러 프로세스가 메모리에 동시 적재
• 현재 실행 중인 프로세스가 입출력 대기를 해야하면, 다른 프로세스에 CPU 할당 가능
• CPU 연산과 입출력을 동시에 -> 자원 활용성 증가

6.3.1.메모리 분할 ⭐️

정의: 이러한 여러 프로세스를 메모리에 적재하기 위한 방법

종류:

• 고정 분할: 메모리를 여러 개의 고정된 크기 영역으로 분할하여 프로세스를 배치
  • 방법1) 각 분할 영역마다 큐를 두고, 큐에 들어온 프로세스는 해당 분할 영역에만 적재 (컴파일 시 절대 주소로 번역)
  • 방법2) 모든 프로세스를 하나의 작업 큐에 넣어, 어느 분할에서든 실행 가능하게 함 (컴파일 시 상대 주소로 번역)
  • 문제: 내부 단편화 발생 가능. 프로세스의 크기가 적재된 분할 영역의 크기보다 훨씬 작아서 분할 영역 내에 낭비되는 메모리 발생.
• 동적 분할: 메모리의 분할 경계가 고정되지 않고 각 프로세스에 필요한 만큼의 메모리만 할당
  • 방법: 프로세스에 필요한 만큼의 메모리를 할당하는 방식.
  • 문제: 외부 단편화 발생 가능. 
  • 해결 방법: 통합, 집약
    • 통합: 인접된 공백을 더 큰 하나의 공백으로 만드는 것.
    • 집약: 메모리 내의 모든 공백을 하나로 모으는 것.

6.3.2.메모리 보호

• 하한-상한 
• 하한-크기 

6.3.3. 메모리 배치 기법 ⭐️

• 최초적합
• 후속적합
• 최적적합
• 최악적합

한 걸음 더 나아가기) 후속 적합과 최악 적합은 도대체 왜 만들어졌을까? 어디에 쓰이는 걸까?

6.5. 가상 메모리 ⭐️

• 가상 메모리(virtual memory): 컴퓨터 시스템의 메모리크기보다 더 큰 기억 공간이 필요한 프로세스를 실행할 수 있게 하는 방법. 실행 중인 프로세스에 의해 참조되는 주소(가상 주소)를 메모리에서 사용하는 주소(실주소)와 분리.
• 사상(mapping): 가상 주소를 실 주소로 변환하는 과정.
• 동적 주소 변환(DAT): 프로세스가 실행되는 동안 사상을 하는 과정
• 인위적 연속성: 가상 주소 공간에서 연속적인 주소가 실주소 공간에서도 연속적일 필요는 없음.

블록단위 주소 변환 ⭐️

• 블록 사상 시스템: 바이트나 워드 단위로 처리하던 항목별 주소 변환의 문제점을 보완해(처리 시간,자원 많이 듬), 정보를 블록 단위로 구분하여 각 블록이 메모리의 어디에 위치하는지만 관리하는 기법.
• 블록 크기가 커질 수록 사상 정보 저장에 필요한 메모리양은 작아짐. 단점은, 블록 이동에 필요한 전송 시간이 늘고, 메모리를 공유할 프로세스 수가 줄어든다.
• 블록 구성 방식에는 페이지(블록 크기 동일)와 세그먼트(블록 크기 다름)이 존재.

블록 구성 방식

• 페이징 기법: 가상 메모리를 페이지 단위(블록 크기 동일)로 나누어 관리하는 기법.
• 세그먼트 기법
• 페이징/세그먼트 혼용 기법

6.6. 메모리(페이징) 호출 기법

• 요구 페이지 호출 기법: 한 프로세스의 페이지 요구가 있을 때 비로소 요구 페이지를 메모리에 적재하는 방법
• 예상 페이지 호출 기법: 곧 사용될 것으로 예상되는 페이지를 미리 메모리에 옮겨 놓는 방법
  • 예상이 잘못된 경우에는 예상 적재에 따른 시간과 메모리 공간 낭비가 발생한다.

6.7. 메모리(페이징) 교체 알고리즘

앞서 페이지를 호출하는 2가지 방법에 대해 배웠다.

그렇다면 페이지의 교체는 언제, 어떻게 발생할까? 페이지를 메모리에 추가하려 할 때 빈 페이지 프레임(페이지를 위한 실 메모리 공간)이 없다면 기존 페이지를 삭제하여 자리를 만들어야 한다. 이 때 기존 어떤 페이지를 삭제할 지 선택에 따라 효율이 달라진다.

참고: 

• 최적화 원칙: 앞으로 가장 적게 사용될 페이지를 예측하여 삭제하는 알고리즘이다. 하지만 실제로 이걸 예상하는 것은 불가능하므로, 삭제할 때 사용된다기 보다는, 효율성을 따지기 위해 실제 사용된 알고리즘과 비교하는 용도로 사용된다.
• 교체 제외 페이지: 페이지 중에는 교체 되어서는 안되는 페이지도 존재한다. 이러한 교체 제외 페이지는 페이지 프레임에 고정되어 교체되지 않는다. 페이징을 위한 커널 코드 영역, 보조 기억장치 드라이버 영역, 시간을 맞춰 동작해야 하는 코드 영역, 입출력 장치로부터 직접 데이터가 교환외더야 하는 데이터 버퍼 영역 등이 여기에 해당된다.

종류:

• FIFO(First-In First-Out): 매모리 내에 가장 오래된 페이지(큐의 가장 오른쪽)를 교체한다.
• LRU(Least Recently Used): 매모리 내에 가장 오래 사용되지 않은 페이지를 교체한다.
  • 국부성(locality)을 활용한 방식이다.
  • 2가지 구현법: 1) 리스트 2) 참조시간
• LFU(Least Frequently Used): 메모리 내에 참조된 횟수가 가장 적은 페이지를 교체한다.
• 2차 기회 페이지 교체: FIFO 교체 방식 + 참조 비트 개념 도입. 참조비트가 0이면서 메모리 내에 가장 오래된 페이지를 교체 한다.
  
  • 참조 비트: 0으로 시작해서 참조될 때마다 +1 추가. 
  • 클럭 페이지 교체 알고리즘

6.8. 프로세스별 페이지 집합관리

개념: 각 프로세스가 사용할 수 있는 페이지 프레임의 개수 제한

종류:

• 워킹 세트 알고리즘: 페이지 부재 비율을 감소시키지 위해 데닝(Denning)이 제안한 모델
  • W(t, s): 워킹 세트 단위. 시각 t에 t를 포함한 직전 s시간 동안 참조한 페이지의 집합
• PFF 알고리즘: 페이지의 부재 빈도(PFF, Page Fault Frequency)를 이용해 프로세스별 페이지 집합의 크기를 변화시키는 기법.

Reference

김진욱(2023). 운영체제. 서울: 한국방송통신대학교출판부.

https://medium.com/@sohailk1999/five-state-process-model-6e83d7428c8c

https://oizys.tistory.com/14

https://junsangkwon.tistory.com/45#:~:text=%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C%EA%B0%80%20%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4%EB%A5%BC%20%EC%A0%9C%EC%96%B4,Switching)%EC%9D%84%20%EC%9C%84%ED%95%B4%EC%84%9C%20%ED%95%84%EC%9A%94%ED%95%A9%EB%8B%88%EB%8B%A4.

1. 대칭키 암호화(Symmetric Encryption)

- 정의: 하나의 키가 데이터를 암호화하고 해독.

- 원리: 송신자가 키를 사용해 데이터를 암호화하고, 암호화된 데이터를 암호화한 키와 함께 한 패킷에 동봉하여 상대에게 전달한다. 이후 상대가 이 키(송신자가 암호화하는데 사용한 동일한 키)를 사용해 데이터를 복호화 해 읽는다. 이 과정에서 키가 탈취되면 키를 가진 누구나 데이터를 복호화 및 변조할 수 있게 되기 때문에, 안전하게 키를 전달하는 방법이 문제시 된다. 

- 장점: 1) 암호화 방식이 빠르다. 2) 기밀성을 제공한다.

- 단점: 1) 앞서 언급 되었듯이 키 교환 보안 문제가 대두된다.  2) 무결성/인증/부인방지를 보장하지 않는다.

- 대표 알고리즘: RSA, DSS 등

2. 비대칭키 암호화(Asymmetric Encryption)

- 정의: 두 개의 키가 쌍을 이루어 데이터를 암호화 및 해독. 한 사람 당 하나의 키가 아닌 두 개의 키(공개키, 개인키)를 가진다. 공개키는 암호화하는데 사용되며, 타인과 공유 가능하다. 개인키는 자신과 짝꿍인 공개키로 암호화된 데이터를 복호화하는데 사용되며 타인과 공유가 되지 않는다. 이러한 비대칭키 암호화는 대칭키 암호화와 비교하여 공개키라는 새로운 개념을 도입했기 때문에 '공개키 암호화'라고도 불린다. 

- 원리: 각 사용자가 자신의 컴퓨터에 키 관리 소프트웨어를 사용해 각각 한 쌍의 키를 생성한다. 통신을 하기 전 수신자A는 송신자B에게 자신의 공개 키를 공개 키 증명서와 함께 보낸다. 그럼 송신자B는 메시지를 받아온 수신자A의 공개키로 암호화 한뒤, 키를 암호화된 데이터와 함께 수신자A에게 다시 전달한다. 수신자A는 자신의 공개키로 암호화된 메시지를 자신의 개인키를 이용해 복호화하여 읽는다.

- 장점: 대칭키 암호화에서 문제되던 키 교환 시 보안 문제가 해결된다. 공개 키의 개념 덕에 개인 키를 공유할 필요 없어졌으며, 중간에 공개키가 탈취 당한다고 해도 탈취자는 개인 키가 없기 때문에 데이터 복호화가 불가능하다. 즉, 데이터는 송신자와 수신자가 아닌 타인에게 노출되거나 수정될 위험에서 안전하다. 

- 단점: 속도가 느리다. 공개 키 암호화는 대칭 키 암호화보다 계산적으로 더 많은 자원(비트, 시간)을 요구한다. 따라서 느리다. 

- 대표 알고리즘: DES, 3DES, AES, SEED, ARIA 등

1. 배경 지식

전자 봉투에 대해 알기 전에 대칭키와 비대칭키의 개념에 대해서 알아야 한다. 전자 봉투는 대칭 키 암호화와 공개 키 암호화의 장점들을 묶어 나온 기술이기 때문이다. 간단히 설명하면 전자봉투는 대칭 키의 장점인 빠른 속도와 공개 키 암호화의 장점인 보안성을 모두 확보한 기술이다. 아래 전자 봉투 기술을 사용한 암호화/복호화 과정을 살펴보며 그 원리를 이해해보자.

2. 전자 봉투(Digital Envelope)

2.1. 전자 봉투의 작동 원리

전자 봉투를 이용한 암호화 과정을 개략적으로 보면 위 그림과 같다.

1) 송신자의 문서+공개키를 대칭 키로 암호화: 먼저 빠른 것이 장점인 대칭 키를 사용했기 때문에 빠르다. 
2) 대칭키의 단점인 키 안전하게 분배 문제를 해결하기 위해, 1)에서 사용된 대칭 키를 수신자의 공개키로 암호화 한다.(공개 키 암호화) 이 때 이러한 대칭키 암호화 과정이 편지 봉투에 담는 것과 같다고 하여 전자 봉투라고 칭하게 되었다.
3) 1)에서 암호화된 데이터 + 2)에서 암호화된 키까지 한 패킷에 전송한다. 

참고로 전자 봉투는 이렇게 대칭키를 한 번 더 봉투에 감싸는 것과 같다고 하여 붙여진 이름이며,

좁게는 암호화된 대칭키, 넓게는 암호화된 대칭키 + 이와 함께 상대에게 전송된 암호화된 메시지까지 총칭한다.

2.2. 전자 봉투의 복호화 과정 

위 그림은 그림1의 과정을 더 상세히 표현 + 복호화 과정까지 담은 것이다.
이를 통해 더 자세한 전자봉투의 암호화 동작 원리와 나아가 복호화 원리까지 알수 있다. 이를 글로 풀어 설명하면 아래와 같다.

4) 수신자는 전달 받은 전자 봉투를 자신의 개인키로 열어 전자봉투로부터 대칭 키를 꺼내면(대칭키 복호화),
5) 그 대칭 키로 암호화된 메시지를 복호화한다.
6) 복호화된 메시지(원문+전자서명+송신자의 공개키)를 확인 가능하다.
8) 이 때 송신자의 공개키를 활용해 전자 서명을 복호화 한다. 원문은 해시 함수에 통과시킨다. 복호화된 전자서명과 해시함수를 통과한 메시지 다이제스트가 서로 일치하는 지 검증한다. -> 일치한다면 송신자A가 보낸 것이 맞다는 것이 검증된다.

3. 정리 

이렇게 대칭 키 암호화와 비대칭 키 암호화의 장점을 섞은 전자 봉투 기술의 개념과 동작 원리 방법에 대해 알아보았다. 대칭 키 암호화와 공개 키 암호화의 장점만을 차용한 전자 봉투 기술은 기존 대칭 키의 단점을 보완하여 기밀성과 무결성을 보안할 뿐 아니라 인증과 편리함을 제공한다. 이러한 전자 봉투 기술은 전자 상거래의 이중 서명 등으로 사용되며, 통신 안전을 높이는 데에 기여한다.

참조 문헌

https://help.sap.com/doc/saphelp_snc70/7.0/en-US/b8/821ffddadd11d2a60a0000e835363f/content.htm?no_cache=true

https://blog.naver.com/jvioonpe/221388172751

1. 인증과 인가

인증(Authentication): 자신의 신원을 시스템에 증명하는 것. 어떤 실체가 정말 그 실체가 맞는지 확인하는 과정.

인가(Authorization): 신원이 확인되어 인증 받은 사람이 출입문에 들어가도록 허락/허가하는 과정. 

2. 메시지 인증

메시지 인증: 송신자가 보낸, 수신자가 받기로 한 그 메시기가 맞는지 확인하는 과정.

메시지 무결성 확인: 수신된 메시지가 전송 도중 불법적으로 변경되지 않았는지 확인하는 것.

3. 메시지 인증 코드(MAC, Message Authentication Code)

MAC(Message Authentication Code): 메시지에 추가로 붙는 태그. 메시지 인증에 필요하다. MAC은 해당 데이터의 고유한  송신자는 메시지를 보낼 때 MAC을 함께 전송. 수신자는 받은 메시지의 변조 여부를 MAC을 통해 식별 가능. 참고로 메시지는 암호화 되지 않아 누구나 볼 수 있다. 

4. 메시지 인증 방법

4.1. 메시지 인증 방법의 3가지 특징

1. 비밀 키 사용

2. 기밀성 제공 안함 -> 메시지는 MAC과 독립적. 누구나 읽을 수 있다.

3. 작은 크기. -> MAC 크기는 메시지 크기와 무관.

4.2.메시지 인증 방법 종류

1. HMAC(Hash-based Message Authentication Code)

- 정의: 일방향 해시 함수를 이용해서 MAC을 구현하는 방법을  HMAC(Hash-based Message Authentication)이라고 한다.

- 특징 : 일방향이기 때문에 역방향 함수는 없으며, 생성된 MAC의 길이는 생성 시 바탕이된 메시지의 길이와 전혀 상관이 없다. 메시지는 암호화 되지 않기 때문에 누구나 읽을 수 있다는 특징도 있다. 사용하는 일 방향 해시 함수는 단 한 종류로 정해두고 있는 것이 아니며, 강한 일 방향 해시 함수라면 뭐든지 HMAC에 이용할 수 있다. 대칭  키, 공개 키, 비밀 값 등을 사용해 메시지 다이제스트를 사용하고 검증한다.

2. CMAC(Cipher-based Message Authentication Code)

- 정의: CMAC(Cipher-based Message Authentication Code)은 블록 암호 기반. CBC 모드 메시지 적용. 트리플 DES나 AES와 같은 블록 암호 사용해 메시지 인증 코드(MAC)를 구현한다. 블록 암호의 키를 메시지 인증 코드의 공유 키로 사용하고, CBC 모드를 써서 메시지 전체를 암호화 한다. 메시지 인증 코드(MAC)은 복호화 할 필요가 없으므로 마지막 블록을 제외하고 모두 폐기해 마지막 블록만 MAC값으로 사용한다.

5. HMAC vs CMAC

 HMAC(Hash-based Message Authentication)은 해시함수로, CMAC(Cipher-based Message Authentication Code)는 DES나 AES와 같은 암호 알고리즘을 사용해 메시지 인증 수단, 즉 MAC을 구현한다고 했다. 그렇다면 과연 둘 중 어떤 방법이 더 효율적일까? 우선 해시함수와 암호 알고리즘부터 비교해보자. 

해시 함수는 데이터 무결성을 검증하고 데이터를 고유하게 식별하기 위해 사용되며, 이러한 면에서 암호학적인 기술의 하나로 간주될 수 있다. 그러나 해시 함수는 "암호화"와는 다르다. 일반적으로 암호화는 평문 데이터를 암호화하여 암호문으로 변환하는 과정을 의미한다. 이러한 암호화 과정은 일반적으로 해독이 가능한 형태로, 즉 특정 키를 사용하여 원래 데이터를 복원할 수 있는 형태로 이루어진다. 즉, 암호화란 복호화가 가능해야한다. 반면에 해시 함수는 일방향 함수이므로, 해시 값으로 변환된 데이터는 원래의 데이터를 복원하기가 매우 어렵거나 불가능하다. 즉, 해시 값은 복호화가 웬만해서는 불가하다.

암호기술이 첨가된 해시 함수는 대칭 암호 알고리즘인 DES와 비교했을 때 몇 가지 장점이 있다. 첫째, 일반적으로 대칭 암호 알고리즘인 DES보다 소프트웨적으로 속도가 빠르다. 둘째, 암호기술이 포함된 해시 함수에 대한 코드들을 쉽게 구할 수 있다. 해시 함수(1997년)가 블록 암호 기술(2006년)보다 먼저 나왔기 때문이다.  셋째, 수출에 보다 자유롭다. 대칭 암호 알고리즘이나 MAC 에서 사용하는 대칭 암호 알고리즘까지 수출 규제를 받고 있는 데 반해, 암호적 해시 함수에 대해서는 미국이나 다른 나라들이 수출 규제를 하고 있지 않다. 

따라서 해시함수를 바탕으로 하는 HMAC이 더 널리 쓰이는 편이다. 하지만 예외적인 몇 사항 -ex)이미 블록 암호를 사용하는 프로그램에 적용경우- 에서는 CMAC을 사용하는 편이 나을 수 도 있다. 

6. HMAC 설계 목표​

- 수정하지 않고 쓸 수 있는 해시 함수들을 만든다. 소프트웨어에서 잘 돌아가고 코드를 무료로 제공하고 널리 쓰일 수 있도록 한다.

- 더 빠르고 안전한 해시 함수가 있거나 필요하다면 기존의 해시 함수를 쉽게 교환할 수 있도록 한다.

- 심각하게 기능저하를 유발하지 않고 해시 함수의 원래 성능을 유지하도록 한다.

- 키를 보다 쉽게 다루고자 한다.

- 내장된 해시 함수가 충분히 강하다면 인증 메커니즘의 강도에 대한 암호해독의 정도를 확실히 파악할 수 있도록 한다.

Reference

1.

https://withbabybird.tistory.com/6

2. 

https://m.blog.naver.com/wnrjsxo/221719726759

3.

https://crypto.stackexchange.com/questions/15721/use-cases-for-cmac-vs-hmac

목차

1. 대칭키 암호화와 비대칭키 암호화

2. 대칭키 암호의 분류

3. 블록화 암호의 분류

4. 블록화 암호의 운영 모드

1. 대칭키 암호화와 비대칭키 암호화

블록화 암호는 대칭키의 한 종류이다. 따라서 대칭키와 관련된 간략한 배경지식이 필요하다. 이에 대한 지식이 생소할 독자를 위해 대칭키와 이와 함께 등장하는 공개키 암호화 개념에 대해 다음 글에 간략히 정리해 두었다.

2. 대칭키 암호의 분류

1) 스트림 암호

평문과 같은 길이의 키 스트림을 생성하여, 평문과 키를 비트 단위로 XOR 하여 암호문을 얻는 대칭키 암호 방식.

ex) 메세지(평문)   1   0   1   1   0   1   0   1

      암호화키          1   1   0   0   1   1   0   0

      -----------------------------------

       XOR              0   1   1   1   1   0   0   1  (암호문)

ex) 암호문             0   1   1   1   1   0   0   1

      복호화키          1   1   0   0   1   1   0   0

      -----------------------------------

       XOR              1   0   1   1   0   1   0   1  (평문)

2) 블록화 암호

평문을 고정된 크기의 블록으로 나누어, 각 블록마다 암호화 과정을 수행하여 블록 단위로 암호문을 얻는 대칭키 암호 방식.

블록 암호화 알고리즘은 복호화가 가능한 파이스텔(Feistel) 구조와, 복호화가 불가능한 SPN 구조로 또 세분화된다.

또는 각 블록에 블록 암호화를 적용하는 방식에 따라 다양한 운영 모드를 가진다. 다양한 운영 모드가 있지만 대표적인 5가지는 다음과 같다: ECB, CBC, CFB, OFB, CTR

1.3. 블록화 암호의 분류

1) 파이스텔 구조

하나의 입력 블록을 분할하여 좌우 두 개의 블록으로 구분한 뒤 라운드 진행

2) SPN(Substitution Permutation Network)

하나의 입력 블록을 여러 개의 소블록으로 나눈 후 라운드 진행.

1.4. 블록화 암호의 운영 모드

* IV: Initialization Vector(IV)는 블록 암호화에서 사용되는 보조 입력 값으로, 이름에서 알 수 있듯 블록 암호화에서 사용되는 키와 함께 암호화 프로세스를 초기화한다. IV의 작업을 통해 암호화에 사용되는 블록들의 패턴이 반복되지 않도록 하여 최종적으로는 보안성이 향상된다.

1) 전자 코드 북(ECB, Electronic CodeBook) 모드

2) 암호 블록 연결(CBC, Cipher Block Chaining) 모드

3) 암호 피드백(CFB, Cipher FeedBack) 모드

4) 출력 피드백(OFB, Output FeedBack) 모드

5) 카운터(CTR, Counter) 모드

참고 문헌

브라우저 ≠ 인터넷 ≠ 웹

1년전 처음 코딩을 접했을 때, 비전공자였던 나는 브라우저라는 개념이 생소했다. '브라우저...들어보긴 했는데 그냥 인터넷 아니야?' 이정도 이해만이 내가 가진 전부였다. 그래서 브라우저가 무엇인지 생소한 분들을 위해 브라우저가 무엇인지에 대해서부터 짚고 넘어가고자 한다.

간단히 추상적으로 보자면 아래와 같다:

인터넷: 컴퓨터들이 정보 공유를 위해 서로 연결된 방식. 예전에는 직접 전선(유선)으로 컴퓨터와 컴퓨터를 연결했다. 하지만 네트워크의 등장으로 무선으로도 컴퓨터와 컴퓨터 연결이 가능해졌다. 즉, 현재 인터넷은 네트워크 방식인 셈이다.
웹(a.k.a World Wide Web): 사람들을 이어주는 정보 공간이다. 웹 서버들(건물)의 정보 공간(도시)
웹 서버: 하나의 빌딩.
웹사이트: 하나의 사무실.
브라우저: 인터넷을 이용하게 해주는 도구. 정확히는 웹 문서 코드를 유저에게 그려주는 역할을 한다.

인터넷은 컴퓨터들이 서로 연결된 방식이다. 눈에 보이는 개념은 아니지만 인터넷은 어디에나 있다. 인터넷을 이용해 이메일을 보낼 수도, 파일을 다운보낼 수도 있지만, 역시 가장 많이 쓰이는 인터넷의 용도는 웹에 접근하는 것이다. 웹(World Wide Web)을 남산타워에서 내려다본 서울의 빽빽한 빌딩들이라고 생각하면 편하다. 하나의 빌딩은 웹을 제공하는 웹 서버(언제나 인터넷에 연결되어 정보를 저장 및 제공하는 컴퓨터)이다. 우리가 프로그램으로 웹사이트를 만드는 것은 이 하나의 빌딩 안에 한 사무실(웹사이트)을 렌트하는 것과 같으며, 그 사무실의 주소가 웹 주소가 된다. 우리는 이 사무실에서 정보들을 엮고 연결해 웹을 이용하는 유저들에게 정보를 제공한다. 웹사이트 속 정보는 컴퓨터 언어(HTML, CSS, JavaScript)로 되어있다. 이 정보들은 당연히 프로그래밍 언어를 모르는 대부분의 사람들에게 친화적이지 않다. 이것들을 우리가 친숙해하는 인간언어(텍스트), 이미지 혹은 비디오로 바꾸어 유저들에게 보여주는 역할을 하는 프로그램을 브라우저라고 한다. 따지고 보면 웹은 빽빽한 빌딩들로 가득찬 아주 거대한 가상의 도시인 것이다. 이 도시에서는 수많은 사무실에서 컴퓨터 언어로 쓰인 문서로 소통한다. 다양한 컴퓨터 언어는 브라우저를 통해 우리가 공통으로 이해할 수 있는 수단(텍스트, 이미지 등)으로 번역된다.

결국 브라우저는 결국 인터넷에 떠도는 여러 정보를 이용하는 하나의 방법에 불과하다. 인터넷을 인터넷에 접속하는 방법은 꼭 브라우저일 필요 없다. 다양한 이유로 우리는 CLI, 앱 등의 방법으로 브라우저 대신 인터넷을 이용하고 있다. 그렇다. 우리가 개발시 사용하는 `npm i package`와 같은 CLI나, 모바일 기기라면 '앱'에 접속하는 것 모두 인터넷에 접속해 원하는 데이터를 사용하는 인터넷 이용 방법 중 하나이다.

하지만 아다시피 개발자를 제외한 많은 사람들은 CLI를 사용하지 않는다. 사용자로써 대부분은 브라우저 혹은 앱을 통해 인터넷에 접근하게 되는데, 아마도 아래와 같은 장점들 덕이라 생각한다:

1. 브라우저는 웹 페이지의 다양한 미디어 콘텐츠를 재생할 수 있습니다. 오디오나 비디오 파일, 이미지, 플래시 애니메이션 등을 브라우저 내에서 볼 수 있습니다. 또한 JavaScript와 같은 스크립트 언어를 지원하여 웹 페이지에 동적인 기능을 추가할 수 있습니다. 이러한 기능들은 사용자 경험을 향상시키고 다양한 웹 서비스를 즐길 수 있게 해줍니다.

2. 또한, 브라우저는 보안 기능을 제공하여 사용자를 안전하게 보호합니다. 예를 들어, 악성 웹 사이트로부터의 경고, 안전하지 않은 연결에 대한 경고, 팝업 창 차단 등의 기능을 제공합니다. 브라우저 개발사들은 보안 취약점을 해결하고 업데이트를 제공하여 사용자의 개인 정보와 시스템을 보호합니다.

3. 마지막으로, 브라우저는 다양한 플러그인과 확장 기능을 지원합니다. 사용자는 원하는 기능을 추가하고 확장할 수 있으며, 광고 차단, 비밀번호 관리, 웹 개발 도구 등 다양한 분야에서 활용할 수 있는 확장 기능을 설치할 수 있습니다.

브라우저의 작동원리

The information is transferred using the Hypertext Transfer Protocol, which defines how text, images and video are transmitted on the web. This information needs to be shared and displayed in a consistent format so that people using any browser, anywhere in the world can see the information.

Creating consistency between browsers, so that any user can enjoy the internet, regardless of the browser they choose, is called web standards.

When the web browser fetches data from an internet connected server, it uses a piece of software called a rendering engine to translate that data into text and images. This data is written in Hypertext Markup Language (HTML) and web browsers read this code to create what we see, hear and experience on the internet.

Hyperlinks allow users to follow a path to other pages or sites on the web. Every webpage, image and video has its own unique Uniform Resource Locator (URL), which is also known as a web address. When a browser visits a server for data, the web address tells the browser where to look for each item that is described in the html, which then tells the browser where it goes on the web page.

Cookies (not the yummy kind)

Websites save information about you in files called cookies. 

참조

https://www.mozilla.org/en-US/firefox/browsers/what-is-a-browser/

https://web.dev/howbrowserswork/

https://www.youtube.com/watch?v=fyOSkkQK14w 

https://www.youtube.com/watch?v=J8hzJxb0rpc