Protocol

• 네트워크에서는 통신할떄의 규약을 protocol이라고 함.
• 최근 이더넷 - TCP/IP 기반 protocol로 획일화되고 있는 추세이다.
  • 물리적인 측면 : 데이터 전송 매체 , 신호 규약 , 회선 규격 등 이더넷이 널리 쓰인다.
  • 논리적인 측면 : 장치들간에 통신하기 위한 protocol 규격으로 TCP/IP가 널리 쓰인다.

과거에는 네트워크 환경과 컴퓨팅 환경이 열악해 한정된 자원으로 최대한 효율적인 protocol을 정의하고 사용해야 했음. 따라서 대부분의 protocol이 문자 기반이 아닌 2진수 bit 기반으로 만들어졌음. application level의 protocol은 bit 기반이 아닌 문자기반으로 많이 사용되고 있음. ex) HTTP,SMTP

문자기반으로 사용할 경우, 효율성은 bit 기반 protocol보다 많이 떨어지지만 다양한 확장이 가능하다.

TCP/IP protocol stack

• TCP(transport 계층)와 IP(network 계층)는 별도의 계층에서 동작하는 protocol 이지만 함께 사용하고 있는데 , 이런 프로토콜의 묶음을 protocol stack이라고 부름

• TCP/IP protocol stack은 총 4개 부분으로 나뉜다.

OSI 7계층과 TCP/IP

• OSI 7계층은 네트워크의 주요 reference model로 활용되고 있지만, 현재는 대부분의 protocol이 TCP/IP protocol stack 기반으로 되어 있다.

• 계층별로 표준화된 protocol을 개발함으로서 네트워크 구성 요소들을 모듈화 할 수 있다.
• 모듈화함으로서 기존에 다른 계층의 protocol들과 연동해 사용할 수 있다.

OSI 7계층은 다시 2가지 계층으로 나뉜다.

1. Data Flow layer (Lower Layer) : 1~4 계층
2. Application Layer (Upper Layer) : 5~7 계층

Data flow layer 는 데이터를 상대방에게 잘 전달하는 역할을 가지고 있으며 , application layer는 데이터를 잘 표현하는데 역할을 가지고 있다. 따라서 네트워크 엔지니어는 Data flow layer 을 고려하고, application 개발자는 application layer를 고려한다.

OSI 7계층과 TCP/IP protocol stack의 차이점

• OSI reference model은 7 계층으로 이루어진 반면, TCP/IP 모델은 4계층으로 구분된다.

• TCPI/IP 모델은 상위 3개 계층 (application,presentation,session) 은 하나의 application 계층으로 묶고, 하위 2개 계층 (physical , data link) 계층을 하나의 network access 계층으로 분류한다.

FIFO (First in, First out)

FIFO(First-in-First-out,선입선출) 또는 FCFS(First-Come-First-Served,FCFS) 스케쥴링이다.

말그대로 먼저 도착한 process부터 cpu를 할당받는 것이다.

FIFO방식의 가장 큰 문제점은 작업 실행 시간이 긴 process가 먼저 왔을때, 뒤에 있는 process들이 이를 끝나기를 기다려야 한다는 점이다. 이를 convoy effect라고 부른다.

SJF(Shortest Job First)

가장 짧은 실행 시간을 가진 작업을 먼저 실행시킨다.

FIFO에서 가지는 convoy-effect문제를 해결할 수 있으나, 모든 작업이 동시에 도착한다는 가정하에서다. 즉 긴 작업이 짧은 작업보다 먼저 도착한다면 여전히 convoy-effect문제가 발생할 수도 있다.

예를 들면 위처럼 작업시간이 긴 A라는 process가 먼저 도착했고, 그 뒤에 작업 시간이 짧은 B,C가 도착하였다. SJF는 비선점형이므로, A가 끝날떄까지 기다려야 한다.

위의 FIFO와 SJF는 비선점형 scheduler로 각 작업이 종료될떄까지 계속 수행된다. 이제부터 정리할 스케쥴링 알고리즘은 선점형 방식으로 작업이 종료되기 전에 다른 작업으로 전환이 가능하다

제한적 직접 실행 (Limited Direct Execution)

• 제한적 직접 실행과 반대되는 개념인 직접 실행(Direct Execution)은 프로그램을 한번 실행하면 종료될떄까지 cpu상에서 그냥 직접 실행시키는 것을 말합니다.

하지만 직접 실행 방식은 아래와 같은 문제점을 가지고 있습니다.

1. 악의적인 process의 경우 os가 제어 불가
2. 시분할 기법(time sharing) 구현 불가

+) 참고로 시분할 기법이란 process가 실행될떄 일정한 time quantuam 값내에서만 실행되고, 시간이 초과되면 timer interrupt를 발생시켜 다른 process로 context switching 하는 기법을 말합니다.

3. 시스템 자원에 대한 제어 불가

예를 들면 user process가 디스크 입출력 요청이나, cpu , memory와 같은 시스템 자원에 추가할당을 요청할때, user process가 직접 시스템 자원을 꺼내쓴다면 악의적인 process의 경우 시스템 자원을 모두 점유하는 문제점이 있을 것입니다.

kernel mode , user mode

위 시스템 자원에 대한 제어권을 운영체제가 제어하기 위해서 나온 개념이 사용자 모드(user mode) , 커널 모드(kernel mode)입니다.

user process가 실행될떄는 user mode로 전환됩니다. 이 user mode에서는 할 수 있는 일이 제한되는데, 예를 들면 시스템 자원에 대한 요청 (ex)입출력 요청등) 이 제한됩니다.

시스템 자원에 대한 요청은 kernel mode에서 가능합니다. user mode 에서 kernel mode로 전환이 일어나는 메카니즘은 system call입니다.

정규화 이론의 목표

• 가능한 데이터 중복성(Redundancy)를 제거해서 한가지 사실은 한 곳에서만 나타난다라는 원칙을 지키도록 한다.
• 즉 정규화 과정(Normalization procedure)란 중복을 최소화하기 위해 데이터를 구조화 하는 작업이다.
• 정규화 과정을 통해 특정 조건을 만족시키는 relation을 정규형이라고 한다. 제 1,2,3…정규형 등이 존재한다.

왜 정규화가 필요한가?

• 정규화를 하지 않는 경우에 data redundancy로 인해 다음과 같은 이상현상들이 발생할 수 있다.

1. insert annomaly (삼입 이상 ) : 특정 데이터를 삼입하고 싶은데, 자료가 부족해 삼입할 수 없다. 예를 들면 공급자,도시,부품이라는 attribute가 있다고 하면 공급자가 어떤 도시에 살고 있다는 정보는 부품이라는 정보가 있어야만 삼입할 수 있다.

2. deletion annomaly (삭제 이상) : 하나의 정보를 삭제하고 싶지만, 필요한 정보까지 삭제될 수 있다. 위 예와 동일한데, tuple을 삭제할 경우에 공급자가 어떤 도시에 살고 있다는 정보가 소실될 수 있다.

3. update annomaly (갱신 이상) : 데이터 갱신 중간 과정에 일부 data는 update된 상태, 일부 data는 original 상태로 inconsistent한 상태가 생길 수 있다.

정규형 만족 조건

• 분해 집합은 무손실 조인, 무손실 분해 (nonloss decomposition)를 만족해야 한다.
• 분해 집합은 함수적 종속성(functional dependency)을 보존해야 한다.

Nonloss Decomposition (무손실 분해) 이란?

• non-loss decomposition : 특정 relation 을 다른 relation으로 분해하는 것으로 , 이 과정은 정보의 손실이 있어서는 안된다. 즉 가역적이여야 한다.
• 가역적이란 말은 분해 이후 다시 table을 join 하였을떄 최초의 relation과 동일해야 한다는 말이다.

Functional Dependency (함수적 종속성) 이란?

• 특정 relation 안에서 하나의 속성 집합에서 다른 속성으로의 다대일 (many-to-one)관계이다. 정확한 정의는 다음과 같다.

R을 relation이라 하고, X와 Y를 R의 속성 집합의 임의의 부분집합이라고 할때, Y가 X에게 함수적으로 종속되기 위한 필요 충분 조건은 다음과 같다. R에 있는 각각의 X의 값이 정확하게 하나의 Y의 값과 관련을 갖는 것이다.

이를 “X가 Y를 함수적으로 결정한다.” 또는 기호로는 X->Y 로 표시한다.

Graph 정의

정점(Vertex)과 간선(Edge)의 집합

그래프 용어 정리

• 방향 그래프 (Directed Graph) : 간선에 방향이 있는 그래프

• 무방향 그래프(Undirected Graph) : 간선에 방향이 없는 그래프

• 차수(Degree) : 임의의 정점에 인접한 정점의 수

• 경로 : 시작 정점 u로부터 도착 정점 v까지의 정점들

  • 단순 경로 : 경로 내 모든 정점들이 다른 경우
  • Cycle : 시작 정점과 도착 정점이 동일한 경우

• 연결 성분 (Connected Component) : 그래프에서 정점들이 서로 연결되어 있는 부분

• 가중치 그래프 (Weighted Graph) : 간선에 가중치가 부여된 그래프

• 신장트리 (Spanning Tree) : 그래프가 하나의 연결성분으로 구성되어 있을 때, 그래프의 모든 정점들을 cycle없이 연결하는 부분 그래프

  그래프 구현 방법

  그래프를 구현하기 위한 방법으로 2가지가 존재한다.

1. 인접행렬 (Adajacent Matrix) : 2차원 배열로 표현하는 방법으로 n개의 정점이 존재한다고 하였을 떄 , n x n 배열로 표현하여 그래프의 정점 i 와 정점 j 간에 연결선이 존재하면 1을 표시하고, 연결선이 존재하지 않으면 0을 표시하여 구성한다. dense graph를 표현할떄 유리하다.

• 장점 : 정점간의 연결선 여부를 O(1) 으로 파악 가능
• 단점 : O(N^2)의 공간 복잡도를 가짐

2. 인접 리스트 (Adjacency List) : 정점과 해당 정점에 인접한 정점들을 연결리스트로 표현하는 방식으로, n개의 정점이 존재한다고 하였을떄, n x n 연결리스트로 구성된다. sparse graph를 표현할떄 유리하다.

• 장점: O(N+E)의 공간 복잡도를 가짐
• 단점 : 정점간의 연결선 여부를 O(N) 으로 파악가능

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

public class Graph<T> {

    // 연결리스트
    private Map<Vertex<T>, List<Vertex<T>>> adjVertices = new HashMap<>();

    void addVertex(T label){
        adjVertices.putIfAbsent(new Vertex(label),new ArrayList<>());
    }

    void removeVertex(T label){
        Vertex vertex = new Vertex(label);
        adjVertices.values().stream().forEach((e)->e.remove(vertex));
        adjVertices.remove(vertex);
    }

    void addEdge(T label1,T label2){
        Vertex<T> v1 = new Vertex(label1);
        Vertex<T> v2 = new Vertex(label2);
        adjVertices.get(v1).add(v2);
        adjVertices.get(v2).add(v1);
    }

    void removeEdge(T label1, T label2){
        Vertex v1 = new Vertex(label1);
        Vertex v2 = new Vertex(label2);
        List<Vertex<T>> vertices1 = adjVertices.get(v1);
        List<Vertex<T>> vertices2 = adjVertices.get(v2);
        if(vertices1 != null){
            vertices1.remove(v2);
        }
        if(vertices2 != null){
            vertices2.remove(v1);
        }
    }
    List<Vertex<T>> getAdjvertices(T label ){
         return adjVertices.get(new Vertex(label));
    }
    public class Vertex<T>{
        T label;
        Vertex(T label){
            this.label = label;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vertex vertex = (Vertex) o;
            return Objects.equals(label, vertex.label);
        }

        @Override
        public int hashCode() {
            return Objects.hash(label);
        }
    }
}

Transaction

Transaction은 작업의 논리적인 단위로서 , 예를 들면 은행에서 출금 후 입금을 한다고 가정하였을떄 실제로 DB query문은 여러 번 나가겠지만 하나의 논리적인 작업 단위로 볼 수 있다.
Transaction이 필요한 이유는 데이터베이스 연산 중간에 일관되지 않은 상태가 존재하기 떄문이다. 2개의 연산중에 하나만 수행되고 하나는 아직 수행되지 않은 상태가 존재할 수도 있다.
따라서 데이터베이스는 작업의 완전성을 보장해주기 위해서 , 일련의 연산들을 사용자 입장에서 마치 단일 연산인것처럼 보이게 해준다.

추가로 transaction은 다음과 같은 특징을 갖는다.

• Transaction은 recovery 단위이다. 실제로 DB에 쓰여지는 과정에서 system failure시 write ahead log (WAL) 라고 하는데 log라는 자료구조에 먼저 transaction을 쓰고나서 commit처리를 해준다. 즉 commit 이후에 system failure시에는 이 log를 보고 복구가 가능하다.
• 아래에 Transaction 특성 중에 Isolation (독립성) 이 있다. 서로 다른 transaction은 독립적으로 수행될 수 있어야 하는데 , 이를 위해서는 concurrency control (동시성 제어) mechanism 이 필요하다.

Transaction의 특성 (ACID)

Transaciton 은 작업의 완전성을 보장하기 위해서 다음과 같은 4개의 특성을 갖는다.

1. Atomicity (원자성): 원자성을 가지므로, 전부 실행되거나 (commit) 혹은 전부 실행되지 않는다 (rollback)
2. Consistency(일관성) : Transaction은 데이터베이스의 일관성을 유지해야 한다. 즉 일관된 상태에서 일관된 상태로 변환해야 한다.
3. Isolation(독립성): Transaction은 서로 독립적으로 수행될 수 있어야 한다.
4. Durability(지속성) : Transaction이 commit되면 DB에 영구적으로 저장되야 한다.

Transaction 상태

transaction은 다음과 같은 상태를 가진다.

• Active state : transaction이 아직 실행중인 상태
• Partially committed state : transaction의 마지막 연산까지 전부 수행되었지만 commit 하기전의 상태
• Failed : transaction중 오류가 발생해 중단된 상태
• committed : transaction이 성공적으로 종료되어서 DB에 영구적으로 반영된 상태
• aborted : transaction이 비정상적으로 종료되어서 rollback 연산을 통해서 작업을 취소하여 transaction 수행 이전의 일관된 DB 상태로 돌아간 상태

transaction의 병행수행 제어 기법 (concurrency control mechanism )

다른말로 동시성 제어인데, 여러가지 transaction 이 공유자원 (DB 데이터)를 동시에 접근할떄 여러가지 문제가 발생할 수 있다

대표적으로 다음과 같은 문제가 생길 수 있다

• lost update problem(갱신 분실 문제) : transaction A 가 수행한 update가 transaction B가 수행한 update를 덮어씌움.
• uncommitted dependency problem (비완료 의존성 문제) : transaction A 가 완료되지 않은 상태에서 갱신한 데이터를 transaction B 가 갱신했는데, transaction A가 rollback됨.

Index 정의

Disk I/O를 최소화시키면서 원하는 데이터를 효율적으로 검색하기 위한 자료구조로 Data file과 분리된 index file 에 보관되며, 데이터 필드에 대한 탐색 키값과 record 물리적 위치를 가르키는 포인터로 구성된다.

• Index의 크기는 data file에 비해 휠씬 작다.
• 하나의 data file에 여러 개의 index가 정의될 수 있다. (하나의 희소인덱스와 여러개의 밀집 인덱스를 가질 수 있다. )
• Index가 정의된 table의 필드를 탐색 키라고 한다.

network 구성 요소

• network edge : application (ex) web server ) , host
• network core : routers
• communication link : network 구성요소들을 이어주는 물리적인 cable

protocol

• 둘 이상의 통신 개체간에 교환되는 메시지 포맷과 순서뿐 아니라 , 메시지의 송수신과 다른 이벤트에 따른 행동들을 정의한다. (통신매체간 통신 규약)

network core 내 router간 데이터 교환 방식

1. circuit switching (회선 교환)

종단 system (network edge)간에 통신을 제공하기 위해 경로상에 필요한 자원 (link 전송률,buffer)를 통신 기간동안 미리 확보(예약) 해두는 방식

2. packet switching(패킷 교환) : 현재 인터넷에서 사용중인 방식

circuit switching 방식과는 다르게 on-demand방식으로 네트워크 자원을 사용하기 떄문에 더 많은 사용자 수용가능

• 송신측은 송신할 데이터를 packet이라고 하는 단위로 분할해서 송신.
• router 에서 packet을 store-and-forwarding transmission (저장-후-전달 전송) 방식으로 전달함

Process concept

• program : disk 상에 존재하며, 명령어의 모음
• process : program이 os로부터 메모리를 할당받아 실행중인 상태로 memory 부분이 code / data(전역변수,static 변수) / stack(지역변수,함수 매개변수,함수 return주소) / heap(malloc과 같은 system call을 호출하여 동적으로 할당되는 영역) 영역과 program counter 나뉜다

정확히 얘기하면 초기 OS 에서는 program의 전체 영역을 메모리에 올렸지만, 현대 OS에서는 필요한 영역만 메모리에 올리는 데 이 부분은 paging , swapping 과 관련된 개념이다.

(ref - https://gabrieletolomei.wordpress.com/miscellanea/operating-systems/in-memory-layout/ )

Process State

• new state : process가 처음 메모리에 load된 상태
• ready state : process가 cpu에 의해 실행될 수 있는 상태

ready state에서 OS의 scheduling 정책에 따라 cpu를 할당해줄 process를 선택한다. 선택된 process는 running state가 된다.

• running state : process가 cpu에 의해 실행되고 있는 상태

running state에서는 3가지 state로 분기할 수 있다.

1. ready state : OS는 선점형 (pre-emptive) 방식으로 time quantuam (일반적으로 10ms) 간격으로 process가 termination state 가 되지 않으면 timer interrupt를 걸어준다. (Time sharing , 시분할 시스템 ) 따라서 timer interrupt 된 process는 다시 ready state가 된다.
2. waiting state : process가 I/O 요청시 I/O응답이 오기전까지 CPU는 다른 process를 실행한다. I/O 작업 완료전까지는 waiting state가 되고, I/O 작업이 완료되면 다시 ready state가 된다.
3. termination state: process가 time quantuam이내에 정상 수행 종료된다.

정상 상태는 아니지만 예외적인 process 상태가 있다. UNIX system 에서는 zombie process 라고 부르는데 부모 process 가 fork() system call을 통해 부모 process와 동일한 code를 가진 자식 process를 생성하면 , 자식 process 는 exec() system call을 통해 새로운 code로 덮어씌워진 뒤 실행된다. 부모 process는 자식 process가 종료될떄까지 기다리고 자식 process 가 사용한 resource를 os에게 회수를 요청한다 (reaping)

부모 process , 자식 process 종료가 비정상적으로 일어났을때 나타날수 있는 process 상태는 다음과 같다.

1. zombie process : 자식 process가 비정상적으로 종료되어 부모 process는 waiting 중인 상태로 child process 의 resource가 반납이 안되고 있는 상태

부모 process가 kernel에게 resource 회수를 요청하지 못하고 있는 상태로 memory 누수현상이 발생한다.

2. orphan process : 반대로 parent process 가 wait() 하지않고 종료된 경우 자식 process는 orphan process가 된다.

kruskal 알고리즘은 최소 신장 트리 (Minimum Spanning Tree,MST)를 구하는 알고리즘으로, 그리디 알고리즘에 속한다