Reverse Proxy, Load Balancer, HTTP 캐시 서버 등으로 다양한 네트워크 역할을 수행하는 소프트웨어다!

백엔드 개발에서는 특히, 클라이언트와 Spring Boot 사이 중간 계층 역할로 사용된다

Reverse Proxy 란?

클라이언트 요청을 받아 실제 백엔드 서버로 대신 전달하는 서버다!

Client → Nginx → Spring Boot 구조

Reverse Proxy를 사용하는 이유

1. 백엔드 서버의 직접 노출을 방지하고, 포트를 숨긴다 (ex. 8080 → 80)
2. 여러 서버로 요청 분산이 가능하다 (로드밸런싱)
3. 정적 파일 처리와 캐싱 가능
4. HTTPS 설정 간소화 가능

Nginx 동작 방식

Nginx는 요청이 들어오면 다음과 같은 순서로 처리한다.

1. 클라이언트 요청 수신 (80/443 포트)
2. 요청 URL 분석
3. 설정 파일 (nginx.conf)에 따라 처리 방식을 결정
4. 필요 시 백엔드 서버로 전달한다 (proxy_pass)

Nginx 사용 시 자주 발생하는 문제

1. 502 Bad Gateway

: 백엔드 서버가 죽었거나, 포트가 불일치 되는 등의 경우다.

1. 404 / 403

: location 설정 or root 경로 문제 등의 경우다.

1. 정적 파일 안불러와짐

: 경로 설정에 오류가 있거나, static 파일 위치의 문제

1. 설정 적용 안됨

sudo nginx -s reload

위 명령어를 실행하지 않으면 설정 반영이 안된다!!

Nginx 주요 파일

• /etc/nginx/nginx.conf → 메인 설정
• /etc/nginx/sites-available/ → 설정 파일
• /etc/nginx/sites-enabled/ → 활성화된 설정

컨테이너화된 애플리케이션을 자동으로 배포, 확장, 관리해주는 오픈소스 플랫폼이다!

즉, Docker 컨데이너를 대규모로 자동 관리해주는 시스템이라 생각하자

왜 사용하는가?

K8s를 통해서는

• 자동 배포, 자동 확장, 자동 복구, 로드 밸런싱이 가능해진다.
• 기존에는 서버마다 환경이 다르거나, 장애 발생 시 자동 복구가 어려운 등 문제가 있었다.

Kubernetes 핵심 구조

1. Cluster 구성

• Control Plane
• Worker Node

[1] Control Plane

주요 컴포넌트

• (1) API Server
  • 모든 요청의 출입구
  • kubectl 명령이 여기로 들어간다
• (2) etcd
  • 클러스터의 상태를 저장하는 DB
• (3) Scheduler
  • 어떤 노드에 Pod를 배치할지 결정한다
• (4) Controller Manager
  • 시스템 상태를 지속적으로 원하는 상태로 유지한다

[2] Worker Node

: 실제로 컨테이너가 실행되는 곳이다

• (1) Kubelet
  • 노드에서 Pod 상태를 관리한다
• (2) Kube Proxy
  • 네트워크, 로드밸런싱을 담당한다
• (3) Container Runtime
  • Docker, containerd 등

핵심 개념

1. Pod

• K8s의 가장 작은 실행 단위다
• 하나 이상의 컨테이너를 포함하고 같은 네트워크, 스토리지를 공유한다

2. Deployment

• 원하는 Pod 개수를 유지
• 자동 복구와 롤링 업데이트를 지원한다

3. Service

• Pod에 접근하기 위한 네트워크 추상화
  • Pod는 IP가 계속 바뀌기 때문에 직접 접근이 불가하다.
• 종류 : ClusterIP, NodePort, LoadBalancer

4. Namespace

• 클러스터 내 리소스를 논리적으로 분리한다

5. ConfigMap, Secret

• ConfigMap : 설정 정보
• Secret : 비밀번호, API Key 등 민감 정보

Kubernetes의 동작 흐름

상황 예시 : 웹 서버 3개를 띄워보자

1. 개발자가 yaml 작성
2. kubectl로 API Server에 요청
3. etcd에 상태를 저장
4. Scheduler가 Pod 배치
5. Kubelet이 컨테이너 실행
6. Controller가 상태 유지

→ 핵심 : 원하는 상태를 유지

YAML 예시

apiVersion: apps/v1
kind: Deployment
metadata:
  name: nginx-deployment
spec:
  replicas: 3
  selector:
    matchLabels:
      app: nginx
  template:
    metadata:
      labels:
        app: nginx
    spec:
      containers:
      - name: nginx
        image: nginx:latest
        ports:
        - containerPort: 80

뜻 : nginx 컨테이너를 3개 실행하고, 장애 발생 시 자동 복구한다.

Kubernetes 핵심 특징

1. Self-Healing

• Pod가 죽으면 자동으로 재생성

2. Auto Scaling

• 트래픽에 따라 자동으로 확장

3. Rolling Update

• 무중단 배포가 가능하다

4. Declarative 방식

• 원하는 상태만 정의한다

Kubernetes VS Docker

그래서 둘의 차이가 무엇인가??

Kubernetes를 써야하는 경우는 언제인가

• MSA(마이크로서비스) 구조
• 트래픽 변동이 큰 서비스
• 무중단 배포 필요
• 대규모 서비스

위와 같은 상황에서 사용하는 것이 좋다!

RAM이 부족할때 디스크 공간을 임시 메모리처럼 사용하는 기술. 속도는 느리지만 OOM이기 때문에 프로세스가 죽는걸 방지할 수 있다

AWS EC2 t2.micro 에서 Spring Boot 프로젝트를 운영하고 있었는데, 자꾸 프로세스가 죽는 일이 생겼다ㅠ

해결 방법을 찾아보던 중, Swap에 대해 접했다.

사용방법

1. Swap 파일 생성

sudo dd if=/dev/zero of=/swapfile bs=128M count=16

위 명령어를 통해 128MB x 16 의 Swap 파일을 생성할 수 있다. (필자는 프리티어 1GB 기준이고, 2GB의 파일을 생성한다.)

2. 권한 설정

sudo chmod 600 /swapfile

root만 읽고 쓸 수 있도록 설정한다.

3. 영역 설정

sudo mkswap /swapfile

mkswap 명령어를 통해 swap 영역을 설정한다.

4. 파일 적용

sudo swapon /swapfile

swap 메모리를 활성화시킨다.

5. 재부팅 시에도 유지 (선택사항)

echo '/swapfile none swap sw 0 0' | sudo tee -a /etc/fstab

swapon 명령어만 수행할 경우에는 재부팅될때마다 swap 파일 설정이 비활성화 되기 때문에, 위 명령어를 통해 영구적으로 자동 활성화 시킬 수 있다.

적용 시

위와 같은 결과를 확인할 수 있다.

public void addAndGet() throws Exception{ 
    UserDao dao = new DaoFactory().userDao();

    User user = new User();
    user.setId("user1");

    dao.add(user);
    User user2 = dao.get("user1");

    assertEquals(user.getId(), user2.getId());
}

작성한 dao가 제대로 동작하는지 확인해야한다.

위 코드처럼 작성하면, add()과 get()을 통해 비교하게 된다.

JUnit

테스트를 자동화하기 위해 사용한다

대표적인 어노테이션으로 @Test, @Before 가 있다.

@Test
public void addAndGet() {
    ...
}

주요 특징을 살펴보면 “자동실행”, “결과 비교(assert)”, “반복가능” 이 있다

DI가 테스트에 미치는 영향

만약 DI가 없다면,

UserDao dao = new UserDao();

내부에서 DB를 직접 생성하기 때문에, 테스트용 DB로 바꾸기가 어렵다

하지만 DI가 있다면?

UserDao dao = new UserDao(new TestConnectionMaker());

테스트용 DB로 쉽게 교체가 가능하다!

스프링 컨테이너

이제 아래와 같은 기존 코드를

UserDao dao = new DaoFactory().userDao();

스프링 방식으로 변화시켜보자

ApplicationContext context =
    new AnnotationConfigApplicaionContext(DaoFactory.class);

UserDao dao = context.getBean("userDao", UserDao.class);

달라진 점을 살펴보자면, 객체를 직접 만들지 않고 스프링이 대신 만들어준다는 것을 확인할 수 있다!

즉, 스프링 컨테이너는 객체를 대신 만들어주고 관리해주는 시스템이라고 생각하면 된다

Bean

Bean이 무엇일까? 한마디로 표현하면 스프링 컨테이너가 관리하는 객체다.

@Bean
public UserDao userDao() {
    return new UserDao(connectionMaker());
}

ApplicationContext

이게 뭘까?

ApplicationContext는 Bean을 저장하고 꺼내주는 창구와 같은 역할을 하는 스프링 컨테이너의 대표 인터페이스다.

ApplicationContext context = 
    new AnnotationConfigApplicationContext(DaoFactory.class);

UserDao dao = context.getBean("userDao", UserDao.class); 

핵심 흐름을 살펴보자면

1. 설정 클래스 등록
2. Bean 생성
3. DI 수행
4. 필요할때 꺼냄

의 과정을 통하는 것을 확인할 수 있다.

Singleton

스프링의 기본 전략은 “객체를 하나만 만들어서 공유” 하는것이다.

이럴 위해서 싱글톤을 활용한다

UserDao dao1 = new UserDao();
UserDao dao2 = new UserDao();

위와 같은 일반적인 방식으로는 서로 다른 객체 2개가 생성된다.

UserDao dao1 = context.getBean(...);
UserDao dao2 = context.getBean(...);

하지만 이러한 방식대로 작성하면, dao1 == dao2 즉 같은 객체가 된다!

주의해야할 점도 있는데, 싱글톤은 상태를 가지면 위험하다.

→ 싱글톤 객체는 상태없는 (Stateless)구조로 만든다.

핵심 개념 관계정리

각 개념들의 관계를 정리해보자면,

스프링 컨테이너 → ApplicationContext (인터페이스) → Bean (객체) → 싱글톤으로 관리 → JUnit으로 검증

public class UserDao {
    public void add(User user) throws Exception {
        Connection c = DriverManager.getConnection(...);
        PreparedStatement ps = c.prepareStatement(...);
        ps.executeUpdate();
        ps.close();
        c.close();
    }

    public void get(String id) throws Exception {
        Connection c = DriverManager.getConnection(...);
        ...
    }
}

위의 코드는 치명적인 문제점들이 있다.

1. DB에 연결하는 코드 getConnection() 이 반복된다
2. DB가 바뀌면 모든 DAO를 바꿔야하는 변경에 취약한 문제가 있다
3. 비즈니스 로직과 DB 연결 부분이 섞여있다.

관심사의 분리

위와 같은 문제를 해결하기 위해 각 역할을 나눠야한다!

public abstract class UserDao {
    protected abstract Connection getConnection();
}

• DB 연결 부분을 따로 뺐다

public class NUserDao extends UserDao {
    protected Connection getConnection() {
        return DriverManager.getConnection(...);
    }
}

• 이젠 DB 변경 시 하위 클래스만 수정하면 된다!
• 하지만 아직 상속에 의존하고 있다

템플릿 메소드 패턴

• 위의 구조는 템플릿 메소드로 표현할 수 있다
  • 상위 클래스 : 알고리즘 구조 정의 역할
  • 하위 클래스 : 일부만 구현
• 템플릿 메소드의 한계
  • 강한 결합
  • 런타임 변경이 어렵다

인터페이스 도입

그래서 더 좋은 방식을 쓰기 위해 상속 대신 인터페이스를 사용한다!

public interface ConnectionMaker {
    Connection makeConenction();
}

인터페이스로 분리하고

public class DConnectionMaker implements ConectionMaker {
    public Connection makeConnection() {
        return DriverManager.getConnection(...);
    }
}

위와 같이 구현

public class UserDao {
    private ConnectionMaker connectionMaker;

    public UserDao(ConnectionMaker connectionMaker) {
        this.connectionMaker = connectionMaker;
    }
}

→ 이렇게 작성하면 UserDao는 구현이 아닌, 인터페이스에 의존할 수 있게 된다

의존관계 주입 (DI)

그런데, ConnectionMaker를 누가 넣어주게 될까?

UserDao dao = new UserDao(new DConnectionMaker());

→ 객체가 직접 생성하지 않고, 외부에서 넣어준다

팩토리 도입

public class DaoFactory {
    public UserDao userDao() {
        return new UserDao(new DConnectionMaker());
    } 
}

팩토리를 통해 “객체 생성”과 “사용”을 분리시킨다

IoC (제어의 역전)

기존에는 개발자가 직접 객체를 생성했다면,

이제는 팩토리가 대신 생성하게 시킨다. 즉, 객체의 생성/관리 권한이 외부로 넘어간다!

스프링으로 연결

이러한 개념을 자동으로 해주는게 바로, “스프링 컨테이너”다!

스프링은 “객체 생성”, “의존관계 주입”, “라이프사이클 관리” 의 역할을 수행한다.

한 줄로 정의 내리자면 "AI가 일을 잘하도록 “환경, 도구, 규칙”을 설계하는 엔지니어링 방식" 이라 표현할 수 있는 듯 하다.

기존 개발 방식이

• 사람이 코드를 작성 & AI는 보조

라고 한다면, 최근으로 와서는

• AI가 코드, 문서, 테스트까지 직접 생성
• 여기에 버그 수정, 배포까지 수행 가능

하지만 AI는 완벽하지 않다는 점을 간과해서는 안된다.

복잡한 작업일수록 더욱 주의를 필요로 하기 때문에, 등장한 개념이 바로 하네스 엔지니어링이다.

하네스 엔지니어링의 개념

AI를 도구보다 "에이전트"로 생각한다.

엔지니어의 역할이 바뀐다

하네스(Harness)란?

• Harness : 안전장치 / 제어장치.

AI에게 그대로 맡기는 것은 위험하다. 그러므로 제어 시스템을 씌워줘야 한다. 구성 요소 : 시스템 프롬프트, workflow, 도구 연결, 검증 시스템, 제한 규칙

핵심 기술요소 4가지

1. AI가 읽고 판단할 수 있도록 문서, 코드 구조, 규칙 정리 등
2. 작업 분해 : 기능 구현 -> 테스트 -> 검증 -> PR AI는 작은 단위에서 더 잘 작동한다!
3. 피드백 루프 : 테스트 실행, 실패 시 수정, 다시 테스트하며 AI가 스스로 검증할 수 있게 한다!
4. 아키텍처 강제 : AI가 마음대로 구조를 망치지 못하도록 레이어 구조를 고정하거나, 의존성을 제한하며 안정성을 확보한다!

동작 흐름 예시

AI에게 명령하고나면

• 코드 상태 분석 -> 버그 재현 -> 수정 코드 작성 -> 테스트 실행 -> 결과 검증 -> PR 생성 -> 리뷰 반영

이 모든 과정을 자동으로 수행 가능하다

정리

• 하네스 : 자동차 전체 구조
• AI : 엔진

-> 하네스 엔지니어링 : AI에게 일을 맡기는게 아니라 AI가 스스로 개발 작업을 수행할 수 있도록 환경, 규칙, 도구, 피드백 구조를 설계하는 새로운 소프트웨어 엔지니어링 패러다임

Github Action이란?

github에서 지원하는 CI/CD 툴.

CI/CD란?

• CI: 버그 수정 및 코드 변경 사항이 빌드, 테스트를 통해 레포지토리에 merge되는 것
• CD: 빌드, 테스트 후 배포를 진행하는 것

Github Action 요소

• Workflow: 자동화된 프로세스의 집합, ./github/workflows안에서 YAML로 작성
• Event: Workflow를 트리거하는 이벤트 (push, pull request 등)
• Job: 여러 Step으로 구성된 작업 단위
• Step: Job에서 순차적으로 실행되는 단위. 스크립트 명령어나 정의된 액션으로 구성
• Action: Job을 구성하기 위한 Step의 조합으로 구성된 독립적 명령.

변수 설정 (Secrets and Variables)

• Workflow 파일에서 자주 사용하는 변수, 민감한 정보를 Secrets and Variables 를 통해 관리 가능

Repository → Settings → Secrets and Variables → action에서 variable 선택

• 변수명 사용시 {{변수명}} 형태로 참조

Quick Start

https://docs.github.com/en/actions/get-started/quickstart

Github 홈페이지에 Github Action을 간단하게 구성 가능한 안내를 확인할 수 있음.

: 한 클래스는 하나의 책임만 가진다

• 변경 시에 파급효과가 적으면 SRP를 잘 따른 것 (ex. 객체 사용분리, UI변경)

OCP 개방-폐쇄 원칙

: 다형성을 활용해 확정에는 열려있고, 변경에는 닫혀있게 한다

• 객체를 생성, 연관관계를 맺는 별도의 설정이 필요함

LSP 리스코프 치환 원칙

: 객체는 프로그램의 정확성을 깨뜨리지 않으면서 하위 타입의 인스턴스로 바꿀 수 있어야 한다

• ex. 자동차 interface의 악셀은 앞으로 가는 기능이기 때문에 뒤로 가도록 구현하면 LSP에 위반

ISP 인터페이스 분리 원칙

: 특정 클라이언트 위한 인터페이스 여러 개가 하나의 범용 인터페이스보다 낫다

• ex1. 자동차 : 운전, 정비 인터페이스로 분리
• ex2. 사용자 : 운전자, 정비사 클라이언트로 분리

DIP 의존관계 역전 원칙

: 구현클래스가 아닌, 인터페이스에 의존해야 한다

• 구현체에 의존하면 변경이 매우 어려워짐

요약

1. 객체지향은 다형성이 중요하다
2. 그러나 다형성 만으로는 OCP(개방-폐쇄), DIP(의존관계 역전) 를 지킬 수 없다.
3. 역할, 구현을 분리하는게 좋다.
4. 인터페이스 부여가 좋지만, 기능 확장이 없을때는 구체클래스 선 도입 후 리팩터링을 통해 인터페이스를 도입할 수 있다.

• Binary Tree : Map 항목을 저장할 수 있는 우수한 데이터 구조 -> key에 정의된 order relation
• Binary Search Tree : 각 위치 p가 key-value 쌍 (k, v)을 저장하는 이진 트리 T (p의 왼쪽은 k보다 작고, 오른쪽은 k보다 크다)
• Sorted Map
  • 항목은 key에 따라 순서대로 저장됨 -> 가장 가까운 이웃 query 지원 가능

Navigating a Binary Search Tree

• Recall : 이진 검색 트리 순서대로 이동 (왼쪽 서브트리 먼저 방문, 그 후 루트 방문, 그 후에 오른쪽 서브트리 방문)

• 이진 검색 트리 순서대로 순회하면 키 순서가 증가하는 위치 방문

• tree에 저장된 키 특성에 기초한 이진 검색 트리에 대한 추가 네비게이션 방법

Searches

• 이진 검색 트리에서 키 'k'를 찾기 위해 각 위치 p에서 질문함
  • 'k'는 top.key((p에 저장된 키)와 같음. 검색이 성공적으로 종료
• 최악의 running time은 O(h), T경로의 위치에서 T(T, p, k)가 루트에서 시작하여 한 단계씩 내려가는 위치에서 트리 검색 (T, p, k)호출

Insertion. M[k]=v

Deletion

: 삭제할 키 'k'로 항목을 저장하는 위치 p를 찾음, 검색 성공 시 노드 삭제

• Leaf Node

• one child node

• two children node

• database 저장 장치
  • 데이터 저장하는 방법, 접근에 영향
  • 직접 접근 저장 장치 (DASD)인 disk 사용 (Nonvolatile storage, Online device)
• 임의 접근 시간
  • 데이터 접근 시간
  • 헤드가 원하는 트랙에 있는 레코드 찾아 전송하는데 걸리는 시간
  • 탐구시간 + 회전지연시간 + 데이터 전송 시간
  • 접근 시간은 메인 메모리 접근 시간에 비해 느림
  • 실제 데이터 전송 시간은 전체의 10분의 1!!!
  • 대량 전송률 : 연속적인 블록 전송하는 시간
• database 성능 향상 초점 : 디스크 접근 횟수 최소화!!! (디스크에 배치, 저장하는 방법이 중요한 문제)

Database 접근

• Database 접근 과정
  • DBMS는 사용자가 요구하는 레코드 결정 (file manager에게 그 저장 레코드 검색 요청)
  • file manager는 저장 레코드가 들어있는 페이지 결정 (disk manager에게 그 페이지 검색 요청)
  • disk manager는 그 페이지의 물리적 위치를 결정 (디스크에 I/O 명령 내림)

디스크 관리자

• 기본 입출력 서비스 지원 모듈

  • 모든 물리적 I/O 연산에 대한 책임
  • 물리적 디스크 주소 알고 있음
  • operating system의 한 구성 요소

• file manager를 지원

  • file manager가 디스크를 일정 크기의 페이지, 즉 블록으로 구성된 page set로 취급할 수 있도록 지원
  • page set 중에는 하나의 free space page set가 있음
  • 각 page는 해당 디스크 내에서 유일한 page number 가짐

• 디스크 관리

  • 페이지 번호를 물리적 디스크 주소로 mapping

  • file manager를 장비에서 독립

  • file manager의 요청에 따라 page set에 대한 페이지 할당, 회수 수행

• disk manager의 페이지 관리 연산

  • file manager가 명령 가능한 연산
    1. page set S로부터 페이지 P의 검색
    2. S 내에서 P의 교체
    3. S에 새로운 P 첨가
    4. S에서 P 제거
    -> 3, 4는 자유 공간 다룸 & disk manager 필요에 따른 연산임

파일 관리자

• DBMS가 디스크 저장 공간을 저장 화일들의 집합으로 취급할 수 있도록 지원
• 저장 화일
  • 한 타입의 저장 레코드 어커런스들의 집합
  • 한 page set는 하나 이상의 저장 화일을 저장
  • 화일 이름 또는 화일 ID로 식별
• 저장 레코드
  • 레코드 번호 또는 레코드 ID로 유일하게 식별
  • 전체 디스크 내에서 유일
  • <페이지 번호, 오프셋(슬롯 번호)>
• file manager의 화일 관리 연산
  • DBMS가 file manager에게 명령 가능한 연산
    1. 저장 화일 f에서 저장 레코드 r을 검색
    2. f에 있는 저장 레코드 r을 대체
    3. f에 새로운 레코드 첨가하고 새로운 레코드 ID, r을 반환
    4. f에서 저장 레코드 r을 제거
    5. 새로운 저장 화일 f를 생성
    6. 저장 화일 f를 제거

Page Set과 화일

• disk manager의 페이지 관리 : file manager가 물리적 디스크 I/O가 아닌 논리적인 페이지 I/O를 수행할 수 있게끔 지원하는 disk manager의 기능
• 대학 데이터베이스 예
  • 레코드들의 논리적 순서는 그림과 같이 학번, 과목번호, 학번-과목번호 순
  • 저장 순서도 논리적 순서와 같다
  • 저장 화일들은 28개의 페이지로 구성된 page set에 저장
  • 각 레코드들은 하나의 페이지를 차지

대학 데이터베이스 예제 연산 과정

• 빈 디스크 : 하나의 자유 공간 page set만 존재(1~27) 페이지 0 제외 : 디렉터리
• file manager : 5개의 학생 화일 레코드를 삽입
  • disk manager : 자유 공간 page set의 페이지 1에서 5까지를 학생 page set이라 이름 붙이고 할당
• 과목과 등록 화일에 대한 page set를 할당
  • 4개의 page set가 만들어짐
  • 학생(15), 과목(610), 등록(1121), 자유공간 page set(2227)

대학 데이터베이스의 초기 적재 후 디스크 배치도

• 연산 과정
  • file manager : 새로운 학생 S6 (학번 600)을 삽입 disk manager : 첫번째 자유 페이지(페이지22)를 자유 공간 page set에서 찾아서 학생 page set에 첨가
  • file manager : 학생 S2 (학번 200)을 삭제 disk manager : S2가 저장되어 있던 페이지 (페이지 2)를 자유 공간 page set으로 반납
  • file manager : 새로운 과목 C6 (E 515)를 삽입 disk manager : 자유 공간 page set에서 첫 번째 자유 페이지 (페이지 2)를 찾아서 과목 page set에 첨가
  • file manager : 학생 S4를 삭제 disk manager : S4가 저장되어 있던 페이지 (페이지 4)를 자유 공간 page set에 반납

삽입, 삭제 연산 뒤의 디스크 배치도

• 일련의 삽입, 삭제 뒤에는 page set들의 물리적 인접성이 없어짐

Pointer 표현 방법

• 한 page set에서 페이지의 논리적 순서를 물리적 인접으로 표현하기 어려움
• 페이지 헤드에 제어 정보를 저장
  • next page pointer : 논리적 순서에 따른 next page의 물리적 주소, next page pointer는 disk manager가 관리 (file manager는 무관)
• 페이지 헤드에 next page pointer가 포함되어 있는 경우의 디스크 배치도

• disk directory (page set 디렉터리)
  • 실린더 0, 트랙 0에 위치
  • 디스크에 있는 모든 page set의 리스트와 각 page set의 첫 번째 페이지에 대한 포인터를 저장
• disk directory (페이지 0)

파일 관리자의 기능

• 저장 레코드 관리 : DBMS가 페이지 I/O에 대해 알 필요 없이 저장 화일과 저장 레코드로 처리할 수 있도록 지원

• 예시

  • 하나의 페이지에 여러 개의 레코드 저장
  • 학생 레코드에 대한 논리적 순서는 학번 순

  1. 페이지 p에 5개의 학생 레코드(S1 ~ S5)가 삽입 되었다고 가정

     2. DBMS : 학생 레코드 S9 (학번 900)의 삽입 요청

  -> 페이지 p의 학생 레코드 S5 바로 다음에 저장

  3. DBMS : 레코드 S2의 삭제 요청

  -> 페이지 p에 있는 학생 레코드 S2를 삭제하고 뒤에 있는 레코드들을 모두 앞으로 당김

  4. DBMS : 레코드 S7 (학번 700)의 삽입 요청

  -> 학생 레코드 S5 다음에 들어가야 하므로 학생 레코드 S9를 뒤로 옮김

RID의 구현

• RID = <페이지 번호 p, 오프셋(슬롯번호)>
• 오프셋 내용 = 페이지 시작에서부터 저장된 레코드의 위치를 저장
• 레코드 위치 변경 시 RID의 변경 없이 오프셋의 내용만 변경
• 최악의 경우 두 번의 접근으로 원하는 레코드 검색 가능
  • 해당 페이지가 overflow 되어 다른 페이지로 저장된 경우 두 번 접근

Note!

• 화일에 있는 모든 저장 레코드들의 순차적 접근
  • 순차적 접근 : page set 내에서는 페이지 순서, 페이지 내에서는 레코드 순서
  • 레코드 순서 : RID의 오름차순
• control information
  • 저장 레코드에 있는 정보 중, 시스템이 필요로 하는 정보
    • file ID
    • record length
    • deletion flag
  • 레코드 앞에 prefix로 만들어 저장
  • 일반 사용자에게는 무관
• user 데이터 필드
  • 저장 레코드에 있는 정보 중, 사용자가 필요로 하는 정보
  • DBMS가 이용, file manager와 disk manager는 알 필요 없음 (화일 관리자는 화일을 단순히 바이트 스트링으로 인식)

File의 조작 방법

• 파일 : DBMS에서 관리하는 모든 데이터는 파일 형태로 기록 (같은 타입의 레코드들의 집합)
• 레코드의 저장과 접근 방법을 결정

순차 방법

• 레코드들의 논리적 순서가 저장 순서와 동일
  • heap 또는 파일 : 엔트리 순차 화일
  • 일반적인 순차 화일 : 키 순차 화일
• 레코드 접근 - 물리적 순서
• 화일 복사, 순차적 일괄 처리 응용

인덱스 방법

• 인덱스를 통해 데이터 레코드를 접근
• 인덱스된 파일의 구성
  • 인덱스 파일
  • 데이터 화일

인덱스 된 순차 파일

• 하나의 인덱스를 사용
• 순차 접근과 직접 접근을 지원
• 순차 데이터 화일
  • 레코드를 순차적으로 정렬 -> 레코드 집합 전체에 대한 순차 접근 요구를 지원하는데 사용
  • 순차 접근 방법
• 인덱스
  • 레코드들에 대한 포인터 -> 개별 레코드들에 대한 임의 접근 요구를 지원하는데 사용
  • 직접 접근 방법

다중 키 파일

• 데이터를 중복시키지 않으면서 여러 방법으로 데이터를 접근할 수 있는 경로를 제공
• 역 화일 -> 각 응용에 적합한 인덱스를 선정해 구축
• 다중 리스트 화일 -> 하나의 인덱스 값마다 데이터 레코드 리스트를 구축

Index 종류

• 인덱스의 구조
  • <레코드 키 값, 포인터(레코드 주소)>
  • 레코드 키 값은 탐색 키 값임
• 기본 인덱스
  • 기본 키를 포함한 인덱스
  • 하나의 레코드만 식별
• 보조 인덱스
  • 보조 키를 포함
  • 여러 개의 레코드를 식별
• 집중 인덱스
  • 탐색 키 값 순서와 데이터 레코드의 물리적 순서가 같도록 구성된 인덱스 -> 기본 인덱스는 집중 인덱스의 특수한 경우
  • 화일에 하나만 존재 가능
  • 동일한 탐색 키 값을 가진 레코드는 물리적으로 집단화 되어 검색이 효율적
• 비 집중 인덱스
  • 집중 인덱스가 아닌 인덱스
  • 하나의 데이터 화일에 여러 개 존재 가능
• 밀집 인덱스
  • 모든 탐색 키 값에 대해 하나의 인덱스 엔트리가 만들어진 인덱스
  • 역 인덱스는 보통 밀집 인덱스 형태
• 희소 인덱스
  • 일부 탐색 키 값에 대해 인덱스 엔트리가 만들어진 인덱스

이진 검색 트리

• 이진검색트리의 각 노드는 키 값을 하나씩 가짐.
• 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식 가짐
• 임의의 노드 키 값은 자신의 왼쪽 자식 노드의 키 값보다 크고, 오른쪽 자식의 키 값보다 작다.

B-트리

• 디스크의 접근 단위는 블록
• 디스크에 한 번 접근하는 시간은 수십만 명령어의 처리 시간과 맞먹는다
• 검색 트리가 디스크에 저장되어 있다면 트리의 높이를 최소화 하는 것이 유리
• B-트리는 다진검색트리가 균형 유지하도록 하여 최악의 경우 디스크 접근 횟수를 줄인 것임
• B-트리는 균형잡힌 다진검색트리로 다음의 성질을 만족
  • 루트 제외한 모든 노드는 적어도 [m/2]-1 개의 키 값 (최대 m개의 서브 트리)를 갖는다
  • 모든 리프 노드는 같은 깊이 가짐
• B-트리의 노드 구조

다진 검색 트리

레코드 접근

• B-트리를 통해 레코드에 접근하는 과정

3차 B-트리

연산

• B-트리에서의 연산
  • 직접 탐색 : 키 값에 의한 분기
  • 순차 탐색 : 중위 순회로 가능
  • 삽입, 삭제 : 연산 뒤에 트리의 균형을 유지해야됨
  • 분할 : 노드의 오버플로 발생 시
  • 합병 : 노드의 언더플로 발생 시
• 삽입
  • 삽입은 항상 리프 노드에서 수행하게 됨
    • 빈 공간 있는 경우 : 단순히 빈 공간에 삽입하면 됨
    • 오버플로 1) 두 노드로 분할 2) [m/2] 번째의 키 값 -> 부모 노드에 삽입 3) 나머지는 반씩 왼쪽, 오른쪽 서브트리가 됨

삽입 알고리즘

BTreeInsert(t,x)
{
    x를 삽입할 리프 노드 r을 찾는다;
    x를 r에 삽입한다;
    if (r에 오버플로우 발생) then clearOverflow(r);
}
clearOverflow(r)
{
    if (r의 형제 노드 중 여유가 있는 노드가 있음) then {
        r의 남는 키를 넘긴다};
    else {
        r을 둘로 분할하고 가운데 키를 부모 노드로 넘긴다;
        if (부모 노드 p에 오버플로우 발생) then clearOverflow(p);

삽입 예

연산

• 삭제
  • 리프 노드에서는 그대로 삭제
  • 삭제할 키가 리프가 아닌 노드에 존재하는 경우
    • 후행 키 값과 자리 교환을 하고 리프 노드에서 삭제
  • 키 값의 수 < [m/2]-1이 되어 언더플로가 발생
    1. 재분배 : [m/2] 개 이상의 키를 가지고 있는 형제 노드가 있는 경우에 그 형제 노드로부터 키를 이동
    2. 합병 : 재분배 불가능 시 (형제 노드 + 부모 노드의 키 + 언더플로 노드)

삭제

B+-트리

• B+- 트리는 인덱스 세트와 순차 세트로 구성

  1. 인덱스 세트
  • 내부 노드로 구성되고 리프 노드에 있는 키들에 대한 경로만 제공
  • 직접 접근을 지원
  2. 순차 세트
  • 리프 노드로 구성되고 모든 키 값들을 저장
  • 순차 세트는 순차적으로 연결

  • 순차 접근을 지원

  • 리프 노드는 내부 노드와 상이한 구조를 가짐

• m차 B+-트리의 특성

  • 노드 구조는 <n, P0, K1, - - ,P n-1 Kn, Pn>
    • n : 키 값의 수
    • P0, - - , Pn : 서브트리에 대한 포인터
    • K1, - - , Kn : 키 값
  • 루트는 0이거나 2에서 m개 사이의 서브트리를 가짐
  • 리프가 아닌 노드에 있는 키 값의 수는 그 노드의 서브트리 수보다 하나 적음
  • 모든 리프 노드는 같은 레벨
  • 한 노드 안에 있는 키 값들은 오름차순

  • Pi가 지시하는 서브트리에 있는 노드들의 모든 키 값들은 K i+1보다 작거나 같음

  • Pn이 지시하는 서브트리에 있는 노드들의 모든 키 값들을 Kn보다 크다

  • 순차 세트를 구성하는 리프 노드는 모두 링크로 연결된 연결 리스트를 구성

  • 리프 노드 구조 <q, <K1, A1>, <K2, A2>, -- <Kq, Aq>, P next>

    • Ai : 키 값 Ki를 가지고 있는 레코드에 대한 주소
    • q : [m/2]<=q
    • P next : 다음 리프 노드에 대한 링크

  • B-트리와의 차이점

    • 인덱스 세트에 있는 키 값을 찾아가는 경로로만 제공하기 위해 사용

    • 인덱스 세트에 있는 키 값은 모두 순차 세트에 다시 나타남

    • 인덱스 세트의 노드와 순차 세트의 노드는 그 내부 구조가 서로 다름
      • 리프 노드 : 키 값과 이 키 값을 가진 레코드에 대한 주소가 함께 저장
      • 인덱스 세트 노드 : 키 값만 저장
      • 노드에 저장할 수 있는 원소의 수도 서로 다름
    • 순차 세트의 모든 노드가 순차적으로 연결된 연결 리스트
      • 순차 접근을 효율적으로 지원

차수가 3인 B+-트리

B+-트리의 연산

• 탐색
  • B+-트리의 인덱스 세트 : m-원 탐색 트리와 같음
  • 레코드는 리프에서 검색
• 삽입
  • B-트리와 유사
  • 리프가 오버플로가 되면 분할 -> 중간 키 값은 부모 노드로 올라가 저장되지만 분할 노드에도 존재
  • 순차 세트의 연결 리스트의 순차성 유지
• 삭제
  • 리프에서만 삭제 (재분배, 합병이 필요 없는 경우)
    • 인덱스 세트에 있는 키 값은 분리자로 유지 (키 값 탐색하는데 분리 키 값으로 사용)
  • 재분배 : 인덱스 키 값 변화, 트리 구조 유지
  • 합병 : 인덱스의 키 값도 삭제
  • 삭제 예

해싱 방법

• 다른 레코드의 참조 없이 목표 레코드의 접근을 직접 지원 - 직접 화일
• 키 값과 레코드 주소 사이의 mapping 관계를 함수로 설정
• 해싱 함수
  • 키 값으로부터 레코드 주소를 계산
  • 사상 함수 : 키 -> 주소
  • 삽입, 검색에 모두 이용

버킷 해싱

• 버킷
  • 하나의 주소를 가지면서 하나 이상의 레코드를 저장할 수 있는 화일의 한 구역
  • 버킷 크기 : 저장 장치의 물리적 특성과 한번 접근으로 채취 가능한 레코드 수를 고려
• 버킷 해싱 : 키 -> 버킷 주소
• 충돌 : 상이한 레코드들을 같은 주소로 변환
  • 동거자
  • 버킷 만원 - 오버플로 버킷
  • 한번의 I/O가 추가됨

충돌 해결

• 체이닝
  • 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트로 관리
  • 추가적인 연결 리스트 필요
• 개방주소 방법
  • 충돌 일어나도 어떻게든 주어진 테이블 공간에서 해결
  • 추가적인 공간 필요하지 않음
  • 빈자리가 생길 때까지 해시값 계속 만들어낸다
  • 중요한 세가지 방법 : 선형 조사, 이차원 조사, 더블 해싱

충돌 해결 : 선형 조사

hi (x) = (h(x) + i) mod m

• 선형 조사 : 1차 군집에 취약함 (1차군집 : 특정 영역에 원소 몰리는 현상)

충돌 해결 : 이차원 조사

• 2차군집 : 여러 개의 원소가 동일한 초기 해시 함수값을 갖는 현상

충돌 해결 : 더블 해싱

• 충돌 해결 : 개방 주소 방법 시 주의할 점

확장성 해싱

• 충돌에 대처하기 위해 제안된 기법
• 레코드 검색은 최대 2번의 디스크 접근만 필요
• 모조 키
  • 확장성 해싱 함수 : 키 값 -> 일정 길이의 비트 스트링, pseudokey로 변환
  • pseudokey의 처음 d 비트를 디렉터리의 인덱스로 사용
• 디렉터리
  • 헤더에 현재의 디렉터리 깊이 d를 유지 d : 전역 깊이
  • 2^d개의 버킷들을 지시할 수 있는 포인터 엔트리로 구성
  • 디스크에 저장
• 버킷
  • 헤더에 현재의 버킷 깊이 p를 유지, p = 지역 깊이
  • 각 버킷에 저장된 레코드들의 모조 키들은 처음 p비트가 모두 동일

확장성 해싱의 연산

• 검색
  • 모조 키의 처음 d 비트를 디렉터리에 대한 인덱스로 사용
  • 접근된 디렉터리 엔트리는 목표 버킷에 대한 포인터 제공
  • 검색 예 1) 레코드 키 값 k -> 모조키 101000010001 2) 디렉터리 깊이가 3이므로 모조 키의 처음 3비트 사용
    • 디렉터리의 6번째 (101) 엔트리 접근 3) 엔트리는 4번째 버킷에 대한 포인터
    • 키 값 k를 가지고 있는 레코드가 저장되어있는 버킷
    • 버킷 깊이, p=1 : 모조 키의 공통 비트 수가 1, 즉 이 버킷은 비트 1로 시작하는 레코드들을 저장
• 저장
  • 저장할 레코드 모조 키의 처음 d 비트로 디렉터리 접근
  • 엔트리 포인터가 지시하는 버킷에 레코드 저장
  • 버킷의 오버플로 처리
    • 새로운 버킷 할당
    • 버킷 깊이가 p인 오버플로된 버킷과 새로 할당된 버킷의 깊이를 모두 p+1로 설정
    • 오버플로된 버킷에 있는 레코드들과 새로 저장할 레코드를 모조키의 p+1 번째 값에 따라 기존의 오버플로된 버킷과 새로 할당한 버킷에 분산
    • 이때 d < (p+1) 되면 디렉터리 오버플로가 발생 -> d값을 1 증가시켜 디렉터리 크기를 2배로 확장 -> 2배로 증가된 디렉터리 엔트리 포인터들을 모두 조정

버킷 오버플로 예

• Memory pressure로 인해 OS는 페이지를 페이징하여 활발하게 사용되는 페이지의 공간을 확보해야 함
• 어떤 페이지를 퇴출할 지 결정하는 것은 OS의 교체 정책 내에서 캡슐화 됨

Demanding Paging

• Page Fault Rate (0 <= p <= 1.0)
  • p = 0이면 no page fault
  • p = 1이면 모든 Reference가 fault
• Effective Access Time
  • EAT = (1 - p) x memory access time + p x page fault service time
  • Example
    • Memory access time = 200ns
    • Average page fault service = 8ms
    • EAT = (1 - p) x 200 + p x 8,000,000 = 200 + p x 7,999,800
    • 1000개 중 하나의 access로 인해 page fault가 발생하면 EAT = 8,200ns (40배 정도 둔화된 것)
• page fault rate low 낮게 유지하는 게 중요 : 좋은 page replacement 정책이 필요

Page Replacement

• Page replacement
  • 실제로 사용하지 않은 page 찾아내 swap out
  • 좋은 page replacement 알고리즘 : page fault 수가 최소화 됨
• Locality of reference
  • 동일한 페이지를 여러 번 메모리에 가져올 수 있음
  • 실제 대부분의 프로그램에서 관찰되는 현상임
  • 일정 시간에 극히 일부 page만 집중적으로 reference 하는 program behavior (Loop)
  • Paging system이 성능이 좋게 되는 근거
• Ideal algorithm : page fault율이 가장 낮음
• 알고리즘 평가 요소
  • 메모리 참조의 특정 문자열에서 실행 가능 (참조 문자열)
  • 해당 문자열의 page fault 수 계산

The Optimal Replacement Policy

• 전체적으로 가장 적은 미스 수로 이어짐
  • 미래에 가장 멀리 접근할 페이지를 바꿈
  • cache 누락 가능성이 가장 적음
• 미래에 가장 멀리 접근할 페이지를 바꿈
  • 최적 알고리즘이 페이지의 하한을 나타냄
  • 얼마나 근접했는지 알기 위한 비교 정도로만 쓰셈

Tracing the Optimal Policy

• 미래에 가장 나중에 참조될 page를 evict
• 가장 적은 가능성의 cache miss optimal policy 기준으로 다른 policy

A Simple Policy : FIFO

• 페이지가 시스템에 들어갈 때 대기열에 놓였음
• replacement 발생 시, 대기열 끝에 있는 페이지가 삭제 됨(First in page)

Tracing the FIFO Policy

: replacement가 발생하면 첫번째로 들어온 페이지가 evict 됨

BELADY'S ANOMALY

: cache size가 커지면 cache hit 비율이 올라갈거라 생각하지만, FIFO 구조에선 worse해질 수 있음 (cache miss가 오히려 늘어남)

: cache size가 4일 때 cache miss가 더 증가함

Another Simple Policy : Random

• memory pressure로 교체할 random page를 선택
  • 어떤 블록을 evict할지 너무 고민할 필요 ㄴ
  • random은 전적으로 얼마나 운이 좋으냐에 따라 달려있음

Using History

• 이력을 사용
  • recency (최근에 접근한 게 확률 더 ㅇㅇ) : LRU
  • frequency (자주 접근한 게 확률 더 ㅇㅇ) : LFU
• LRU : 마지막으로 사용된 시간이 가장 오래된 page를 쫓아내는 방식
  • locality 기반으로 한 알고리즘
  • Stack 사용한 알고리즘 : Belady's anomaly 없음
  • 구현 어려움 (page가 언제 접근되었는지 모두 기록하고 있어야 함)
  • 모든 Workload에 유용하지는 않음

Workload Example

• 100개의 page에 랜덤으로 접근하는 상황

: page의 locality가 적용되지 않아 cache size에 비례해서 page hit rate가 높아짐

• 80-20 Workload

: 80%의 접근 시도가 20개의 페이지에 국한, 20%의 접근 시도가 80개의 페이지에 국한됨 -> 지역성 기반 알고리즘인 LRU가 FIFO나 RAND 알고리즘 보다 효율적임

• Looping Sequential

: 50개의 page가 loop를 돌면서 순차적으로 접근

• LRU와 FIFO는 크기가 49까지 모두 cache miss 발생 (cache size가 49page 까지 hit ratio=0, 가장 예전에 접근한 page 쫓아내고 50이 들어올때 0이 쫓겨나감)

Implementing Historical Algorithms

• 가장 최근에 사용된 페이지 추적을 위해 시스템은 모든 메모리 참조에 대해 몇 가지 회계 작업을 수행해야 함
  • HW 지원도 조금 추가

Approximating LRU

• 사용 비트 형태의 하드웨어 지원이 필요
  • 페이지 참조할 때마다 사용 비트는 하드웨어에 의해 1로 설정
  • 하드웨어는 비트를 삭제하지 않음. OS의 책임임
• Clock Algorithm
  • 시스템의 모든 페이지가 원형 목록으로 배열
  • 시계 바늘은 먼저 특정 페이지를 가르킴 : use bit를 통해서 최근에 접근이 되었는지만 판단 (LRU와 비슷한 동작), page fault 발생 시 손이 가리키는 페이지가 검사됨

Workload with Clock algorithm

• Clock algorithm은 완벽한 LRU만큼 잘 작동하지 않음. 이전을 전혀 고려하지 않는 접근이 더 나음

Considering Dirty Pages

• HW엔 수정된 비트 포함
  • 페이지는 수정되었기 때문에 dirty함. 삭제하려면 디스크에 다시 기록해야 함
  • 페이지 수정되지 않았으면 삭제는 그냥 자유

Page Selection Policy

• OS는 페이지를 메모리에 가져올 시기를 결정해야함
• OS에 몇 가지 다른 옵션을 제공

Prefatching

• OS는 페이지가 곧 사용될 것이라고 예측하고, 페이지를 미리 가져옴

Clustering, Grouping

• 보류 중인 여러개의 pending writes를 메모리에 함께 모아서 한 번의 쓰기로 기록
  • single large write를 many small ones보다 효율적으로 수행

Thrashing

• 프로세스에 충분한 page frame이 없는 경우, page fault이 매우 높아짐
• Thrashing : 페이지를 주고 받는 중
  • 발생 이유 : size of locality의 합이 total memory size보다 크기 때문

Working-set Model

• Working-set Model

  • locality의 assumption에 기반 두고 있음

  • working-set window : 고정된 page reference 수

  • WSS

    • 가장 최근 working-set window에서 참조된 총 page 수
    • w.s.w가 작으면 entire locality를 포함하지 않을 것
    • w.s.w가 크면 several locality를 아우를 것

• 제한된 physical memory size : physical memory의 사용가능한 공간보다 큰 프로그램 실행 불가
• 일반 program 실행 패턴
  • 프로그램 전체가 아닌 일부만 실행
  • 프로그램 특정 옵션 및 기능은 거의 안쓰일 수 있음
• Virtual memory : memory에 완전히 있지 않은 process도 실행 가능 (program 일부는 memory에 있어야 함)

: logical memory address space와 physical memory address space의 분리, logical memory address space는 physical memory address space보다 클 수 있음

Demand Paging

• Virtual memory는 demand paging 통해 구현될 수 있음
• 필요할 때만 page를 memory에 넣음
  • 적은 I/O, memory 필요
• page를 주고받을 수 있어야 함

How to Swap?

(memory 꽉찼을 때 밀어내는거 : swapping)

• Overlays

  • 프로그래머는 필요에 따라 코드나 데이터를 메모리 안팎으로 수동으로 이동시킴
  • OS에서 지원받을 필요 없음

• Process-level swapping

  • process는 일시적으로 메모리 부족으로 backing store로 swap된다
  • 나중에 실행되기 위해 memory로 돌아옴

• Page-level swapping

  • page를 memory에서 backing store로 swap (swap-out)
  • backing store에서 page를 memory로 swap (swap-in)

  Where to Swap?

  • Swap space
    • page를 앞뒤로 이동하기 위해 예약된 디스크 공간 (page 단위로 swap)
    • swap space의 크기에 따라 사용할 수 있는 최대 메모리 페이지 수가 결정됨
    • 블록 크기는 페이지 크기와 도일함
    • 파일 시스템에서 전용 파티션 또는 파일일 수 있음

Present Bit

• 디스크 간에 Page를 swap할 수 있도록 시스템에서 일부 기계를 상위에 추가 : 하드웨어가 page table entry를 검색하면 물리적 메모리에 페이지가 없는 것을 발견 할 수 있음
  • Value 1 : page가 physical memory에 있음
  • Value 0 : page가 memory에는 없지만 disk에 있음

The Page Fault

• physical memory에 없는 page에 접근
  • 페이지가 존재하지 않고 디스크를 swap한 경우 , OS는 페이지 오류 해결하기 위해 페이지를 메모리로 swap 해야 함
  • page fault handler(페이지 장애 처리기)로 알려진 특정 코드가 실행되고 페이지 장애를 처리해야 함

Page fault handler

• Page fault handling

Memory가 다 찼다면?

• OS는 새 페이지를 가져올 공간을 마련하기 위해 페이지를 넘기는 것을 좋아함
  • 시작하거나 바꿀 페이지를 선택하는 프로세스를함page-replacement (페이지 교체 정책)이라 함

Page Fault control Flow - HW

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
//  VPN 추출
(Success, TlbEntry) = TLB_Lookup(VPN)
//  추출한 VPN에 대한 주소 변환 정보가 TLB에 있는지 확인
if (Success == True)
//  TLB에 있으면
    if (CanAccess(TlbEntry.ProtectBits) == True)
        Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else RaiseException(PROTECTION_FAULT)
else
//  TLB에 없으면
PTEAddr = PTBR + (VPN * sizeof(PTE))
//  Page Table에 접근해 page위치 알아옴
PTE = AccessMemory(PTEAddr)
if (PTE.Valid == False)
    RaiseException(SEGMENTATION_FAULT)
else
    if (CanAccess(PTE.ProtectBits) == False)
        RaiseException(PROTECTION_FAULT)
    else if (PTE.Present == True)
    //  Present bit가 True라면 (메모리에 page table 존재)
        TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
        RetryInstruction()
    else if (PTE.Present == False)
    //  Present Bit가 False라면 (Swap 공간에 page table 존재)
        RaiseException(PAGE_FAULT)
        //  Page Fault 발생

Page Fault control Flow - SW

PFN = FindFreePhysicalPage()
//  Page 가지고 와서 할당할 메모리 공간을 찾음
if (PFN == -1)
    PFN = EvictPage()
    DiskRead(PTE.DiskAddr, PFN)
    //  disk에서 page table 데이터를 가지고 옴
    PTE.present = True
    // Present Bit를 True로 수정
    PTE.PFN = PFN
    RetryInstruction()

• OS는 곧 오류가 발생할 페이지의 물리적 프레임을 찾아야 함
• 해당 페이지가 없는 경우 replace algorithm (교체 알고리즘)이 실행되어 일부 페이지를 메모리에서 꺼낼 때까지 기다림

Replacement Occur 시

• OS는 메모리가 완전히 채워질 때까지 기다렸다가 다른 페이지의 공간을 만들기 위해 페이지를 바꿈 : 비현실적임. OS가 작은 부분의 메모리를 더 적극적으로 사용할 수 있도록 유지해야 하는 여러 가지 이유가 있음
• Swap Daemon, Page Daemon
  • 사용 가능한 LW page 수가 적으며, 이는 메모리 실행의 자유를 담당하는 백그라운드 스레드임
  • 스레드는 사용 가능한 HW page가 있을 때가지 페이지를 내보냄

What to Swap

• low mem에서 각 유형의 page frame에 발생하는 작업
  • Kernel code
  • Kernel data
  • Page tables for user processes
  • Kernel stack for user processes § User code pages
  • User data pages
  • User heap/stack pages
  • Files mmap’ed to user processes § Page cache pages → Not swapped → Not swapped → Not swapped → Not swapped → Dropped → Dropped or swapped → Swapped → Dropped or go to file system → Dropped or go to file system
• Page replacement은 내보낼 페이지 선택

: 모든 process마다 page table이 하나씩 있음. page table : 4byte entry -> Page table은 너무 큼

Paging : Smaller Tables

: 16KB 페이지와 4byte page table entry가 있다고 가정 (page 하나를 위한 entry하나) -> Big pages는 internal fragmentation 유발

Problem

• process의 entries address space를 위한 single page table

: 대부분의 page table들은 사용되지 않음

Hybrid Approach : Paging and Segments

• Segmentation
  • virtual address space를 segments로 나눔
  • 각 segment는 다양한 length 가질 수 있음
• Paging
  • segment를 고정된 크기의 pages로 나눔
  • 각 segment는 page table 구성
  • 각 segment는 해당 segment에 대한 physical address, limit를 추적함

-> page table의 의미없는 공간 줄이기 : Segmentation, Paging

Simple Example of Hybrid Approach

• 각 process는 3개의 page table이 연결되어 있음

: VPN에서 상위 두개를 빼서 seg

TLB miss on Hybrid Approach

• HW는 page table에서 physical address로
  • HW는 segment bit(SN)를 사용해 사용할 base and bound 쌍을 결정
  • HW는 physical address를 가져와 VPN과 결합하고 Page Table Entry의 주소를 형성

    SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT
    VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT
    AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))

    Problem of Hybrid Approach

• 크기가 크지만 잘 쓰지 않는 heap이 있으면 page table 낭비 많이 발생 가능

• external fragmentation이 다시 발생하는 원인 (할당해놓고 안쓰는게 많음)

Multi-level Page Tables

• linear page table을 tree와 같은 것으로 바꿈

: page table을 page-sized units로 쪼갬,

• 모든 page table entries의 page들이 유효하지 않은 경우 page table의 해당 page를 할당하지 않음
• page table의 page가 유효한지 여부 보려면 page directory 사용

Multi-level Page Tables : Page directory

: Linear Page Table의 PFN 203 & 203은 invalid하기 때문에 할당되지 않았음 -> page table을 page크기의 단위로 나누고 해당 page table의 page invalid하다면 메모리에 할당하지 않음

• page directory에는 page table의 page 당 하나의 entry가 포함됨 (page directory entries로 구성됨)
• PDE에는 유효한 비트 및 PFN이 있음

Multi-level Page Tables : Advantage & Disadvantage

• Advantage
  • 사용 중인 address space의 양에 비례해 page table 공간 할당
  • OS는 page table을 할당하거나 확장해야 할 때 다음 free page를 잡을 수 있음
• Disadvantage
  • Multi-level table은 time-space trade-off의 예시임
  • 복잡함

A Detailed Multi-level Example

: address space가 16KB(2^4, 2^10 -> 14bits), page size가 64bytes(6bit) -> offset도 6bits, VPN = 14-6 = 8bits

A Detailed Multi-level Example : Page Directory Idx

: page directory는 page table의 page마다 하나의 Entry 필요함. page directory의 entry가 invalid하면 예외 발생

-> page directory entry가 valid하다면 이 PDE가 가리키는 page table의 page에서 page table entry 가져옴

-> 그때부터 page table index를 그 page table을 가리키는 index로 사용할 수 있음 !!!

• page directory는 모두 할당되어야 함

Two-level Page Table Scheme

• 32bit Processor의 address translation
  • logical address은 20bits(page number), 12bits(page offset)
• page table자체가 page이기 때문에 page number가 더 나뉘어져 있음
  • 10bits(page directory - outer page table), 10bits(page table - inner page table)

Three-level Page Table Scheme

Multi-level Page Table Control Flow

VPN = (VirtualAddress & VPN_MASK) >> SHIFT  // Virtual Page Number를 추출해냄
(Success,TlbEntry) = TLB_Lookup(VPN)  //  TLB가 이 VPN에 대한 translation을 보유하고 있는지 확인
if(Success == True)
    if(CanAccess(TlbEntry.ProtectBits) == True)  
    //  if문 만족 시 해당 TLB 항목에서 page frame number, 원하는 physical address와 access memory를 추출
        Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
        else RaiseException(PROTECTION_FAULT);
else  // full multi-level lookup 수행 

else  //  Page Directory Index를 추출
        PDIndex = (VPN & PD_MASK) >> PD_SHIFT
        PDEAddr = PDBR + (PDIndex * sizeof(PDE))
        //  Page Directory Entry를 가져옴
        PDE = AccessMemory(PDEAddr)
        if(PDE.Valid == False)
        //  if문 만족 시 : Page Directory Entry의 valid flag를 체크해 true가 되면, page table로 부터 page table entry를 가져옴
            RaiseException(SEGMENTATION_FAULT)
        else  //  PDE가 valid (PTE를 Page table에서 가져옴)

Translation Process : Remember TLB !

PTIndex = (VPN & PT_MASK) >> PT_SHIFT
PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))
PTE = AccessMemory(PTEAddr)
if(PTE.Valid == False)
    RaiseException(SEGMENTATION_FAULT)
else if(CanAccess(PTE.ProtectBits) == False)
    RaiseException(PROTECTION_FAULT);
else
    TLB_Insert(VPN, PTE.PFN , PTE.ProtectBits)
    RetryInstruction()

Inverted Page Table

[page table은 process마다 page table가지고 있어야 함. 사용되지 않는 page가 있어도 page 최대 개수만큼 page table entry가 있어야함]

-> Inverted Page Table 등장

• page frame마다 page table 하나 (process마다가 아님), page table entry개수가 physical memory의 frame 개수와 동일함
• 각 page table저장하는데 필요한 memory는 감소하지만 순차 탐색하기 때문에 탐색에 많은 시간이 소요

• 시간적 오버헤드가 크다
• Address translation이 너무 느림
• 목표 : address translation을 빠르게 하는 것

TLB (Translation Lookaside Buffer)

• CPU -> Logical Address -(TLB Lookup)-> MMU -> TLB Miss시 Page Table, TLB Hit시 Physical Address -> Physical Memory

• logical address에서 page number은 process마다 있음

TLB Performance

• Effective Access Time With TLB

  • TLB Lookup time : e
  • Memory Access time : 1
  • Hit ratio : a (TLB에서의 Percentage)

• = (1+e)a + (2+3)(1-a) = 2+e-a

TLB Basic Algorithm

VPN = (VirtualAddress & VPN_MASK ) >> SHIFT 
(Success , TlbEntry) = TLB_Lookup(VPN)
if(Success == Ture){  // TLB Hit (TLB에 변환 정보 존재할 시)
    if(CanAccess(TlbEntry.ProtectBit) == True ){  // 접근 가능한지 확인 후 TLB 정보로 주소 변환
        offset = VirtualAddress & OFFSET_MASK 
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset 
        AccessMemory( PhysAddr )
    } else
        RaiseExceotion(PROTECTION_ERROR)
else  //  TLB에 변환 정보 없을 때
        PTEAddr = PTBR + (VPN * sizeof(PTE)
        PTE = AccessMemory(PTEAddr)
        (--)

        TLB_Insert( VPN , PTE.PFN , PTE.ProtectBits)  //TLB에 변환 정보 저장
        RetryInstruction()
    }
}    

• Accessing An Array : 첫번째 array[0]에 접근 시 TLB에 아무런 address가 cache 되어있지 않음. 그런데 a[1]에 접근하면 같은 page가 TLB에 cache 되어있어 빠르게 찾기 가능

• a[0], a[3], a[7]모두 같은 현상이고 나머지 7번의 접근, 즉 70%에서 TLB Hit 발생 (배열이 연속된 주소공간에 있어 Spatial Locality라 함)

Locality

(program간, program 내에서도 Locality 존재)

• Temporal Locality : 참조했던 걸 다시 참조
• Spatial Locality : 주소 x에 접근 시, x의 근처로 접근

TLB entry

: TLB는 Full Association(결합된) 방법으로 관리됨

• 32 / 64 / 128 entry 가짐
• HW에선 원하는 translation 찾기 위해 전체 TLB를 병렬로 검색
• Typical TLB : VPN & PFN & other bits

TLB Issue : Context Switching

: process A, B의 VPN가 10으로 동일하지 PFN이 다름 -> TLB에 정보 저장 시 어떤 정보가 어떤 프로세스의 정보인지 알 수 없음

• 해결 방법

1. Context Switch 발생 시 기존 process의 주소변환 정보를 flush (모두 지워버림) -> 추가적인 비용 발생
2. TLB유지 위해 HW의 도움 받음 (TLB구조에 ASID 정보 추가), ASID는 identifier 역할로 process를 구분짓는다

: PFN이 같은 상황(코드 공유) -> page 공유는 메모리 사용을 줄이기 때문에 메모리 공간 확보 가능

TLB Replacement Policy

: TLB가 꽉차있어서 버려야할때

• LRU : 가장 오랜 시간 사용되지 않은 process의 정보 제거 : Total TLB miss : 11

A Real TLB Entry

[MIPS R4000의 예시 - 32비트 주소공간에 4KB페이지 지원]

• 32비트 주소 공간
• 4KB페이지 : VPN 19비트, offset 12비트, 남은 1비트는 사용자인지 커널인지 판단
• PFN 24비트 할당
• PFN(물리 프레임 번호)로 24비트 할당
• G(전역 비트) 설정 되어 있으면 ASID무시, 예시에서는 8비트 길이의 ASID 있음 -> 이 부분 보고 주소 공간 구분
• Dirty bit는 페이지 갱신 시 세팅
• Valid bit는 변환 정보가 존재하는지 나타냄
• 마지막 64번째 비트는 사용하지 않음

• View 클래스 (Widget)

  • 다른 위젯 담을 수 있는 위젯을 레이아웃이라 함
  • 레이아웃은 ViewGroup 클래스 아래 존재

• View의 상속 받은 클래스 계층도

• Button 속성

  • TextView / View에서 상속받음

    View 클래스의 XML 속성

  • XML : 데이터 정의하는 규칙 제공하는 마크업 언어

    xmlns:android="http://schemas.android.com/apk/res/android" .....

  : xml에서의 import 가능, Button의 id속성을 지정 가능한 것은 android라는 변수에 "http://schemas.android.com/apk/res/android" 위치에 있는 android 라이브러리를 지정했고, id속성을 가져와서 지정해줬기 때문

• id 속성

  • 모든 위젯의 아이디 나타냄
  • Java 코드에서 위젯에 접근할 때 id속성에 지정한 아이디 사용
  • "@+id/" 형식으로 지정
  • 새로 지정할 id적기 -> (위젯형) findViewById(R.id.위젯id);

• 클릭했을 때 동착이 필요한 위젯에만 id속성 지정

• layout_width, layout_height 속성

  • match_parent : 레이아웃에 폭이나 높이 맞춤(전체 레이아웃)
  • wrap_content : 자신의 폭, 높이를 안에 글자가 들어갈 정도로만 설정

• background 속성

  • RR, GG, BB 위치는 16진수 00~FF 표현

• padding 속성

  • padding은 위젯 경계선으로부터 위젯 안의 요소가 떨어지도록 설정

• layout_margin 속성

  • 위젯과 위젯 사이 여유 두고 싶을 때 사용

• visibility 속성

  • 위젯 보일건지 여부 결정
  • invisible : 보이지 않을 뿐더러 원래 자리 계속 유지
  • gone : 안보이며 자리까지 없어짐

• enabled, clickable 속성

  • enabled : 위젯 동작 여부
  • clickable : 클릭/터치 가능하게 함
  • true / false 지정
  • XML보다 자바코드에서 주로 사용

• rotation 속성 : 위젯 회전시켜서 출력 (값은 각도로 지정)

텍스트뷰

• 텍스트뷰 java.lang.Object ㄴ android.view.View ㄴ android.widget.TextView

• 텍스트뷰 속성

  • text : 텍스트뷰에 나타나는 문자열 표현
  • textColor : 글자 색상 지정
  • textSize : 글자 크기 지정
  • typeface : 글자 글꼴 지정
  • textStyle : 글자 스타일 지정
  • singleLine : 글 길어서 넘어갈 경우 한 줄만 출력, 문자열 맨 뒤에 ... 표시

버튼과 에디트텍스트

• 버튼과 에디트텍스트

  • 사용자에게서 어떤 값 입력받기 위한 가장 기본적인 위젯
  • View와 TextView 클래스를 상속받으므로 거의 비슷하게 사용 가능

• 버튼 java.lang.Object ㄴ android.view.View ㄴ android.widget.TextView ㄴ android.widget.Button

  • 일반적인 버튼 XML 코드

    <Button
    android:id="@+id/button1"
    android:text="확인" />

• 에디트텍스트

  • 값 입력받은 후 해당 값을 자바 코드에 가져와서 쓰는 용도로 많이 사용
  • 일반적인 에디트텍스트의 XML 코드

고급 질의어 -> 검사기 / 파서 (구문분석하는 컴파일러 역할) -> 내부 형태 질의문 (파이, 시그마 등) -> 질의어 최적기 (여러 관계대수 문 만들고 제일 빠른 경우 찾음) -> 질의문 계획 -> 질의문 코드 생성기 -> 질의문 실행 코드 -> 런타임 데이터 베이스 처리 -> 질의어 결과

질의어 최적화

• 최적화 : 더 효율적인 성능
• 성능측정 : 디스크 I/O 횟수, 중간결과 크기(중간결과 크면 계속 계산해야함), 응답시간(계산시간 빨라야)
• 질의어 최적화 과정
  1. 질의문 내부 표현
  2. 효율적인 내부 형태로 변환 (동등한 내부 표현을 바꿈)
  3. 후보 프로시저 선정
  4. 질의문 계획 평가 및 결정

질의문 내부 표현

• 내부 표현
  • 사용자 질의문을 컴터가 처리하기에 적절한 내부 형태로 변환 (사용자는 sql문이 변함. DBMS가 사용하기에 더 편한 관계대수로 변환)
  • 사용자가 질의
• 형식론
  • 시스템의 질의어로 표현할 수 있는 것은 모두 이 형식으로 표현 가능해야함

효율적 내부 형태로 변환

후보 프로시저 선정

• Map : key-value entry들의 집합
• operation

• Priority Queue : Queue 값들 사이에 우선순위 존재 & minimum key인 요소가 다음에 제거됨
  • example

Implementing Priority Queue

• Unsorted List : 삽입 빠르지만 쿼리, 삭제 속도 느림
  • 우선순위 높은 O(n) 찾기 (작은 값=높은 우선순위, 높은 값 = 작은 우선순위)
  • 우선순위 높은 item Dequeue! O(1)

  • item 삭제된 자리가 비어있어 뒤의 item들을 한칸씩 앞으로 shift

• Sorted List : 쿼리, 삭제는 빠르지만 삽입 느림
  • 우선순위로 정렬되어 있어 item삭제는 O(1), 삭제된 부분 메꾸기는 O(n)

Heaps

: Heap은 binary tree [모양, 순서 조건을 만족]

• Complete Binary Tree (어떤 node가 자식 node를 하나만 가지면 그 노드는 left child에만 존재)
• Heap Order
  • Max Heap : parent node 값은 child보다 크거나 같아야 함
  • Min Heap : parent node 값은 child보다 작거나 같아야 함
• Implementing Priority Queue with Heap : Priority Queue 저장하기엔 제일 자연스러운 방식 & 트리 높이 h = [O(nlogn)]

• Bubbling
  • up heap bubbling : Min Heap일 경우, 추가된 last node의 entry키가 parent보다 작을때까지 swap 진행
  • down heap bubbling : Min Heap일 경우, 변경된 root node의 entry키가 parent보다 클때까지 swap 진행

• Array-based Representation of Complete Binary Tree : 트리를 array에 저장
  • p가 root T면, f(p)=0
  • p가 position q의 left child면 f(p)=2f(q)+1
  • p가 position q의 right child면 f(p)=2f(p)+2
  • T의 원소는 범위 [0, n-1]에 있음,

• Analysis of Heap-Based Queue
  • Heap 기반 구현 통해 insertion, removal 시 실행시간 단축
• Python's heapq Module
  • heappush(L,e) : e를 리스트 L에 push, heap order 복구
  • heappop(L) : L에서 최소값을 pop & return하고 heap order 복구
  • heappushpop(L,e) : e를 L에 push, 최소값을 pop & return
  • heapreplace(L,e) : heappushpop과 비슷함
  • heapify(L) : 순서없는 list를 heap-order property로 변형
  • nlargest(k, iterable) : 주어진 iterable에서 k개의 최댓값 목록 생성
  • nsmallest(k, iterable) : k개의 최소값 목록 생성

Sorting with Priority Queue

• Selection-Sort

  1. 기존 priority queue에 있던 값들을 새로운 sequence에 원래 순서대로 옮김
  2. sequence에서 removeMin을 전체 값의 개수 n만큼 반복, 이 값들을 순서대로 기존 sequence에 옮김

• Insertion-Sort

  1. 기존 priority queue에 있던 값들을 새로운 sequence로 옮김(새로운 수가 들어올때마다 우선순위대로 해당 위치에 저장)
  2. sequence에 존재하는 값들을 순서대로 기존 sequence에 옮김

• Heap-Sort

  • 소요 메모리 양은 O(n)
  • insert, removeMin()은 O(logn)의 시간 소요
  • size, empty, min은 O(1)의 시간 소요 ex1)

  ex2)

Adaptable Priority Queues

• 현실 세계 -> 개념 세계 = 값 사실 -> 개념적 구조 (추상화 개념적 모델링)
• 개념 세계 -> 컴퓨터 세계 = 개념적 구조 -> 논리적 구조 (데이터 모델)

현실 세계 구조적 표현

: 데이터베이스 설계

1. 개념적 모델링
   • 현실 세계 -> 추상적 개념, 개체 타입으로 표현
2. 데이터 모델링
   • 개념적 구조 -> 논리적 개념, 레코드 타입
3. 데이터 구조화
   • 논리적 구조 -> 물리적 구조

Data Modeling

• 데이터베이스 설계 과정 일부 : 개념적인 구조와 논리적인 구조를 거쳐 실제 데이터를 저장할 수 있는 물리적 구조로 변환

1. 개념적 데이터 모델링 : 애트리뷰트로 기술된 개체 타입 & 개체 타입 간 관계 이용 ex) E-R Model

2. 논리적 데이터 모델링

   • field로 기술된 record type, 이들 간 관계 이용 ex)relational data model

Data model

• 데이터 모델 : D = <S, O, C>
• S (구조)
  • 데이터 정적 성질
  • 개체 타입, 관계 명시
• O (연산)
  • 데이터 동적 성질
• C (제약 조건)
  • 데이터 논리적 제약

Entity Type

• 개체 : 다른 것과 구별되는 객체 (개체=객체)

• 개체 타입 : 이름, 애트리뷰트로 정의

  • 개체 집합 : 개체 인스턴스의 집합

• 애트리뷰트 유형

  1. 단순 & 복합 (단순 : 더 이상 분해 불가)
  2. 단일 & 다중 (단일 : 특정 개체에 대해 하나의 값)
  3. 유도 & 저장 (유도 : 가지고 있는 값에서부터 유도됨)
  4. NULL (NULL값 가짐)

Relationship Type

: 개체 집합들 사이의 대응, 즉 사상(Mapping) 의미

• 사상 원소 수 : 관계 타입의 원소 수 제약조건
  • 일대일 ex) marriage : bridegroom ↔ bride
  • 일대다 ex) mothership : mother ← children
  • 다대일 ex) faculty : professor → department
  • 다대다 ex) enrollment : student ↔ course

• 관계 타입의 참여 제약조건

  • 전체 참여 : A-B 관계에서 개체 집합 A의 모든 개체가 A-B 관계에 참여
  • 부분 참여 : A-B 관계에서 개체 집합 A의 일부 개체만 A-B 관계에 참여

• 존재 종속 : 어떤 개체 b의 존재가 개체 a의 존재에 종속됨

Entity-Relationship Model (E-R Model)

• 개념적 데이터 모델(현실세계의 개념적 표현)

  • 개체 집합 : 한 개체 타입에 속하는 모든 개체 인스턴스
  • 관계 집합 : 한 관계 타입에 속하는 모든 관계 인스턴스

• E-R 모델 그래픽 표현

Entity Type & Key Attribute

• Key attribute : 개체 집합 내에서 개체마다 상이한 값 갖는 애트리뷰트 / 애트리뷰트 집합
  • Key : 개체 타입 내 모든 개체 인스턴스들 유일하게 식별 (동일한 값 갖는 개체 인스턴스는 없다)

Weak Entity Type

• 약한 개체 타입 : 애트립뷰트 만으로는 키 명세 불가
• 구별자 : 약한 개체 집합 내에서만 서로 구별할 수 있는 애트리뷰트
• 식별 관계 타입 : 약한 개체를 강한 개체에 연관시킴

E-R Diagram 표기법

-> example

Logical Data Model

: 개념적 구조를 데이터베이스로 구현하기 위한 중간 단계, 레코드 타입과 관계로 표현

• 개념적 데이터 모델 : 개체-관계 데이터 모델

Relational Data Model

• 데이터베이스 : 릴레이션 - 테이블의 집합
• 릴레이션 스키마 : 개체, 관계성을 릴레이션으로 정의

Data Structure Diagram

• 구성 요소

  • 사각형 노드 : 레코드 타입
  • 링크 : 레코드 타입 간 일대다 관계
  • 레이블 : 관계 이름

• 스키마 다이어그램

  • 트리 형태 : 계층 데이터 모델
  • 그래프 형태 : 네트워크 데이터 모델

Network Data Model

• 허용되는 레코드 타입, 관계성 명세

Hierarchical Data Model

• 스키마 다이아그램이 tree
• parent-child 관계

릴레이션 스키마의 설계

• 1. 애트리뷰트, entity, 관계성 파악
• 2. 관련 애트리뷰트를 릴레이션으로 묶음 (애트리뷰트 간 관계성, 데이터 종속성, 일관성 고려해야)
• 3. 변칙적 성질 예방 : 데이터 변경 시의 이상

이상 (Anomaly)

1. 삭제 이상 : 연쇄 삭제에 의한 정보 손실
2. 삽입 이상 : 원하지 않는 정보의 강제 삽입
3. 갱신 이상 : 중복 데이터 갱신으로 정보의 모순성 발생
   • 이상 원인 : 한 개체에 속한 애트리뷰트 간 존재하는 여러 개의 종속관계를 하나의 릴레이션으로 표현
   • 이상 해결 : 애트리뷰트 간 여러 종속관계를 분해 (종속성은 릴레이션으로 표현 = 정규화 과정)

스키마 설계, 변환

• 스키마 설계 : 데이터베이스의 논리적 설계
  1. 애트리뷰트, 제약조건들 수집
  2. 수집된 결과를 제약조건에 따라 여러 릴레이션으로 분할 (스키마 변환)
• 스키마 변환 원리
  1. 정보 표현의 무손실
  2. 최소 데이터 중복
  3. 분리 원칙 (관계성은 별도 릴레이션으로 분리시켜 표현)

함수 종속 (FD)

• 함수 종속 : 어떤 릴레이션 R에서, 애트리뷰트 X의 값 각각에 대해 애트리뷰트 Y의 값이 최대 하나만 연관된다 (애트리뷰트 Y는 애트리뷰트 X에 함수 종속)
  • X는 Y를 결정 (X는 결정자, Y는 종속자)
  • X나 Y는 각 두 개 이상의 애트리뷰트 집합 될 수 있음
• 릴레이션 R에서 애트리뷰트 X가 키면, R의 모든 애트리뷰트 Y에 대해 X -> Y 성립
• 함수 종속 X -> Y의 경우 애트리뷰트 X가 반드시 키라는걸 요건으로 안함 (X의 한 값에 대응되는 Y 값을 갖는 투플이 둘 이상 존재 가능)

함수 종속 다이어그램

• 수강 릴레이션 : 수강(학번, 과목번호, 학년, 성적)
• 2개 이상 구성된 애트리뷰트 집합 X에 대해 X -> Y가 성립할 때
  • 완전 함수 종속 : X'가 부분집합이고 X' -> Y가 성립되는 애트리뷰트 X'가 없음
  • 부분 함수 종속 : X'가 부분집합, X' -> Y가 성립되는 애트리뷰트 X' 존재

함수 종속의 폐포 (Closure)

• 스키마에 대한 종속의 집합 F가 있으면
  • 다른 특정 함수 종속도 그 스키마에 성립
  • 추가 존재하는 함수 종속을 논리적으로 함축되었다고 함
  • F+ : 논리적으로 함축되는 모든 함수 종속의 집합