필기용 블로그

○Signal

 ▷프로세스에 특정 사건이 일어났음을 알리는 작은 메세지

 ▷Exception, interrupts와 유사

 ▷Kernal -> Process

 ▷작은 Int값 ID로 식별

 ▶전송

  ▷Kernal이 Destination pprocess에 전달

  ▷Destination process의 내용의 상태를 Update함으로써 전달.

  ▶전달하는 경우

   ▷Kernal이 system event (SIGFPE, SIGCHLD)를 감지했을 경우

   ▷process가 다른 process에게 kill Signal을 보낸 경우

  ▶전달 방법

   ▷kill 명령어로전달 (pid / grp)

   ▷Ctrl-c / Ctrl-z

   ▷kill 함수로 전달

 ▶수신

  ▶동작의 종류

   ▷Ignore : 무시

   ▷Terminate : process 종료

   ▷SIGCONT 대기 : SIGCONT가 올 때 까지 정지

   ▷Catch Signal handler : Signal handler 호출 (Exception catch와 유사)

  ▶pnb = pending & ~block 계산

   ▷Pending되었지만, Nonblocked인 bit vector

   ▷pnb == 0 : 원래 instruction 계속 수행

   ▷pnb != 0 : signal을 받아 적절한 처리, 처리 후에는 원래 Control flow로 돌아감.

  ▶Signal Handler Install

   ▷handler_t *signal (int signum, handler_t *handler)

    ▷signum : Handler를 설치 할 

    ▶handler

     ▷SIG_IGN : ignore

     ▷SIG_DFL : default action

     ▷Address of user defined-function

   ▶handler 함수

    ▷유저가 정의한 Signal의 행동 함수

    ▷Handling중에는 동일한 Signal은 Block

    ▷동일 프로그램에서 동시에 진행되기 때문에, 주의해야함.

    ▶가이드라인

     ▷되도록 짧고 간결하게

     ▷async-signal-safe 함수들만 사용 - printf, sprintf, malloc은 안전하지 않음

     ▷errno를 저장하고 끝나기 전에 복원해라

     ▷shared data에 접근하는 동안 다은 signal을 막아라

     ▷global 변수를 volatile로 선언해라 (레지스터에 저장하지 않음)

     ▷global flag를 volatile sig_atomic_t를 이용해서 선언해라 (flag의 변경 - atomic하게)

    ※안전한 I/O 라이브러리

 ▶Pending

  ▷전송했지만, 수신되지 않은 상태

  ▷Signal은 Queue가 되지 않음 -> 동일한 Type의 Signal은 단 하나만 Pending될 수 있음 (그 뒤에 오는것들은 버림)

  ▷각 프로세스에서 bit vector로 관리 (각 Signal마다 0, 1)

  ▶Block (signal mask)

   ▷Pending해둔걸 받지 않고 그 상태에 놔둠

   ▷Unblock된다면, 그 때 받음.

   ▷각 프로세스에서 bit vector로 관리

   ▷sigprocmask : 명시적 Block / Unblock

   ▶Signal Mask 함수들

   ◎Temporarily Blocking

※Linux Process Hierarchy

○Shell

 ▷명령어를 받아 프로그램을 실행하기 위한 프로세스를 생성해줌.

 ▷sh, csh/tosh, bash - Default ("Bourne-Again" Shell)

 ◎Simple Shell eval Function

   ▶문제점

    ▷background jobs에 대해 Child가 zombie로 남을 수 있음

●Process

 ▷실행중인 프로그램

 ▶Abstraction (추상화)

  ▶Logical Control Flow

   ▷각 프로그램이 각자의 CPU를 가지고 있는 것 처럼 행동함.

   ▷Context Switching에 의해 구현

  ▶Private Address Space

   ▷각 프로그램이 독립된 메모리 공간을 가지는 것 처럼 행동함

   ▷Virtual Memory에 의해 구현

 ▶Reality 

  ▶Traditional

   ▷하나의 Processor가 여러개의 프로세스를 번갈아가며 동시에 실행

   ▷레지스터를 Saved registers에 저장하고, 다음 Process를 실행

  ▶Modern

   ▷Multicore Processors (여러 CPU가 하나의 Chip에 있음, 여러 Process 동시 실행 가능)

 ▶Context Switching

  ▷각 프로세스는 각자의 control flow를 가진다.

  ▷만약 프로세스들의 flow가 겹치면, 이는 Concurrently하게 진행된다.

  ▷그렇지 않으면 Sequential하게 진행된다.

  ▶Kernal

   ▷프로세스는 메모리 상주 시스템 OS인 kernal에 의해 관리됨.

   ▷Context switch를 일으킴.

 ▶Process Groups

  ▷하나의 부모 (foreground process)에 대해 여러 개의 자식(background process)가 존재

  ▷getpgrp() : 현재 프로세스의 Group

  ▷setpgid() : 프로세스의 Group을 바꾼다.

○Process Control

 ▶Process ID 얻기

  ▷pid_t getpid(void) : 현재 process의 PID 반환

  ▷pid_t getppid(void) : 부모 process의 PID 반환

 ▶프로세스 종료

  ▷행동이 terminate인 signal을 받음.

  ▷main routine에서 return

  ▶void exit(int status)

   ▷exit status를 status로 설정하고, 종료시킴

   ▷0이면 종료 성공, 아니면 에러

   ▷단 한번만 호출되며, 리턴되지 않음.

 ▶프로세스 생성 (Child process)

  ▶int fork(void)

   ▷Child 프로세스를 생성함.

   ▷Child에는 0을, Parent에는 Child의 PID를 return함.

   ▷Child는 Parent와 거의 유사함. (Parent의 Virtual Address Space, Open File Descriptor를 복사함 (하지만 메모리를 공유하지는 않음))

   ▷Child는 Parent와 Concurrent하게 진행됨.

   ▷한번 호출되면, 2번 return됨 (Parent, Child)

  ▶Process Graph

   ▷Vertex : Statement의 실행

   ▷Edge a->b : a다음에 b가 일어남

   ▷Edge에 현재 변수를 기록 가능

   ▷printf Vertex는 출력을 기록 가능

   ▷Inedge가 없는 vertex에서 시작 (Start vertex)

   ▷topological sort :  모든 Vertices의 순서가 왼쪽에서 오른쪽으로 감. -> feasible (발생가능)

  ▶Reaping/Waiting Child process

   ▷Zombie 상태의 Child process를 제거

    ▷zombie : 종료되었지만, 시스템 리소스를 차지하는 상황

   ▷Parent가 kernal에 exit status information을 전달하면, Kernal에서 이를 제거

   ▷Parent가 먼저 종료되면, init 프로세스가 대신 제거

  ▶Synchronizing Child

   ▶int wait(int *child_status)

    ▷Child 프로세스가 종료할 때 까지 Parent 프로세스가 대기한다.

    ▷Child process PID return

    ▶child_status!=NULL 이라면 MACRO를 통해 status 확인 가능

     ▷WIFEXITED : 정상적인 종료라면 true

     ▷WEXITSTATUS : 정상적으로 종료된 child의 status

   ▶int waitpid(pid_t pid, int& status, int options)

    ▷특정 Child에 대해 wait 가능

    ▷옵션 설정 가능

  ▶int execve(char *filename, char *argv[], char *envp[])

   ▷동시에 다른 프로그램 시행 가능

   ▷파일 : obj, 스크립트, 실행 파일...

   ▷env : 환경 변수

   ▷Parent에서 복사한 Code, Data, Stack을 Overwrite한다. (PID는 유지)

   ▷return

○Depth-First Search (DFS)

 ▷G의 모든 Vertices, Edges를 탐색

 ▷G가 Conncted graph인지 확인

 ▷G의 Connected components를 계산

 ▷G의 Spannng forest를 계산

 ▷O(e + v) - 각 vertex/edge가 2번씩 마킹됨. (UNEXPLORED, VISITED/BACK)

 ▶Algorithm

  ▷모든 U, V를 UNEXPLORED로 마킹

  ▶모든 Vertices에 대해 DFS(G, v)를 적용

   ▷해당 vertex를 VISITED로 마킹 

   ▶vertex의 모든 incident edges에 대해

    ▷만약 UNEXPLORED라면, edge의 opposite를 받아옴.

     ▷opposite이 UNEXPLORED라면,  edge를 DISCOVERY로 마킹하고, opposite에 대해 DFS(G,v)

     ▷opposite이 UNEXPLORED가 아니라면 edge를 BACK으로 마킹

 ▶특성

  ▷모든 Vertices, Edges를 방문

  ▷DISCOVERY edges로 Spanning Tree를 만들 수 있다.

 ▶Path finding

  ▷원래 알고리즘에서 Stack추가 (목적지에 도달하면 Stack 반환)

  ▷방문시 push, 나갈시 pop.

 ▶Cycle finding

  ▷back edge (v, w)를 만나면 w까지의 stack을 반환

○Breadth-First Search (BFS)

 ▷G의 모든 Vertices, Edges를 탐색

 ▷G가 Conncted graph인지 확인

 ▷G의 Connected components를 계산

 ▷G의 Spannng forest를 계산

 ▷O(e + v) - 각 vertex/edge가 2번씩 마킹됨. (UNEXPLORED, VISITED/CROSS)

 ▶Algorithm

  ▷모든 U, V를 UNEXPLORED로 마킹

  ▶모든 Vertices에 대해 BFS(G, v)를 적용

   ▷해당 vertex를 VISITED로 마킹

   ▷새로운 Sequence (L_0)를 만들고 해당 Vertex를 insertBack

   ▷i = 0

   ▶L_i가 empty할 때 까지

    ▷새로운 Sequence (L_i+1) 생성

     ▶모든 L_i element에 대해

      ▶모든 incidend edges에 대해

      ▷만약 UNEXPLORED라면, edge의 opposite를 받아옴.

       ▷opposite이 UNEXPLORED라면,

        ▷edge를 DISCOVERY로 마킹

        ▷opposite을 VISITED로 마킹후, L_i+1에 insertBack

       ▷opposite이 UNEXPLORED가 아니라면 edge를 CROSS으로 마킹

    ▷i++

 ▶특성

  ▷모든 Vertices, Edges를 방문

  ▷DISCOVERY edges로 Spanning Tree를 만들 수 있다.

  ▷L_0을 root로 한 Tree로 봤을 때, 각 Level은 root에서 도달하는데 필요한 최소 edge 수이다.

※DFS vs BFS

●Graphs

 ▶Graph G = (V, E)

  ▷V : Set of Vertex(Nodes), 정점 - Vertices

  ▷E : Collection of pairs of Vertices - Edges

  ▷V, E는 positions이고, elements를 저장한다.

 ▶종류

  ▶Directed graph

   ▷모든 edge가 Directed edge - 순서가 정해진 Edge (Origin(tail) -> Destination(head) )

  ▶Undirected graph

   ▷모든 edge가 Undirected edge - 순서가 없는 Edge

 ▶활용

  ▷전기회로

  ▷교통망

  ▷컴퓨터 네트워크

  ▷데이터베이스

 ▶용어

  ▶Endpoints of an edge

   ▷edge에 연결된 두 vertices

   ▷a - U, V

  ▶Edges incident on a Vertex

   ▷vertex에 연결된 edges

   ▷V - a, d, b

  ▶Adjacent vertices (인접한 vertices)

   ▷edge 하나로 연결되는 vertices

   ▷U, V

  ▶Degree of a vertex

   ▷vertex에 연결된 edges의 개수 (loop - 2개처리)

   ▷X : 5

  ▶Parallel edges

   ▷동일한 vertices와 연결된 edges

   ▷h, i

  ▶Self-loop (loop)

   ▷하나의 vertex와 연결된 edge

   ▷j

  ▶Path

   ▷하나의 Vertex로부터 edges, vertices를 거쳐 다른 Vertex로 가는 길

   ▶Simple Path

    ▷거치는 모든 Vertices, Edges가 반복되지 않음

  ▶Cycle

   ▷시작 Vertex와 끝 Vertex가 동일한 Path

   ▶Simple Cycle

    ▷거치는 모든 Vertices, Edges가 반복되지 않음

  ▶Subgraph

   ▷한 Graph의 일부로 만든 다른 Graph

   ▷Subgraph G' = (V', E')에서 V' ⊆ V, E' ⊆E

   ▶Spanning subgraph

    ▷Graph의 모든 Vertex는 포함하지만, 일부 Edge를 포함하지 않음.

    ▷Spanning subgraph G' = (V', E')에서 V' = V, E' ⊆E

  ▶Connected Graph

   ▷모든 Vertex pair에 대해 한쪽에서 다른 한쪽으로 가는 path가 존재함.

  ▶Connected component

   ▷가능한 최대로 연결된 connected subgraph

  ▶Complete Graph

   ▷모든 Vertex에 대해 가능한 최대의 edge를 연결한 것.

   ▷edge 개수 : v(v-1)/2 (v: vertex 개수)

  ▶(Free) Tree

   ▷Cycle이 없는 Undirected Connected Graph

   ▷Spanning Tree : Tree인 Spanning subgraph

  ▶Forest

   ▷Cycle이 없는 Undirected Graph

   ▷Forest의 Connected components는 Tree이다.

   ▷Spanning Forest : Forest인 Spanning subgraph

 ▶속성 (v : vertex 개수, e : edge 개수)

  ▷Σdeg(v) = 2e 

  ▷e ≤ v(v-1)/2 - complete graph의 edge 개수보다 작거나 같다.

○Graph ADT

 ▷Vertices, Edges는 position으로 구현한다.

 ▷element를 저장한다.

 ▶메소드

  ▶Accessor

   ▷e.endVertices() : e의 Endpoint vertices의 list 반환

   ▷e.opposite(v) : e에서 v의 반대쪽에 있는 vertex 반환

   ▷u.isAdjacentTo(v) : u와 v가 adjacent하다면 true 반환

   ▷*v : vertex v의 element

   ▷*e : edge e의 element

  ▶Update

   ▷insertVertex(o) : element o를 저장하는 vertex를 생성

   ▷insertEdge(v, w, o) : v, w vertices를 연결하는 element o 를 저장하는 edge 생성

   ▷eraseVertex(v) : vertex v 제거

   ▷eraseEdge(e) : edge e 제거

  ▶iterable collection

   ▷incidentEdges(v) : v와 연결된 edges의 list

   ▷vertices() : 그래프의 모든 vertices의 list

   ▷edges() : 그래프의 모든 edges의 list

 ▶Edge List Structure

  ▶Vertex Object

   ▷element를 저장

   ▷vertex sequence에서 position을 저장

  ▶Edge Object

   ▷element를 저장

   ▷edge sequence에서 position을 저장

   ▷origin/destination vertex object를 저장

  ▶Vertex sequence : vertex objects의 sequence

  ▶Edge sequence : edge objects의 sequence

  ▷Vertex에 관한 메소드가 비효율적

 ▶Adjacency List Structure

  ▷Edge List Structure를 기반으로 함.

  ▷Vertex 메소드의 효율성 개선

  ▶각 Vertex에 Incidence sequence 추가

   ▷각 Vertex가 Incident edges의 List를 가짐.

  ▶각 Edge가 Incidence sequece에서 자신의 position을 저장

 ▶Adjacency Matrix Structure

  ▷Edge List Structure를 기반으로 함.

  ▷각 Vertex가 고유한 Integer key값을 가지고 있음.

  ▶2차원 배열 Adjacency array

   ▷행의 Key값, 열의 Key값이 연결되는 Edge를 가졌다면, 그 Edge에 reference함. (Nondirected - 대각선에 대해 대칭)

   ▷연결되는 edge가 없으면 null값

 ▶Performance