Multi Process(멀티 프로세스)

멀티 프로세스란?

• 다수의 프로세스로 하나의 Task를 처리하는것
• 프로세스간 메모리 구분이나 독립된 공간이 필요할때 사용

  특징

• 독립된 구조로 다른프로세스에게 서로 영향을 주지않아서 문제가 발생해도 해당 프로세스 이외에는 영향이 없다. -> 안정적이다.

  단점

• 서로 독립된 영역에서 작업을 진행하기 때문에 작업량이 많아질수록 Context Switching에 의한 오버헤드가 발생하여 성능의 저하가 일어날 수 있다
• 서로 독립되어있기 때문에 통신을 위해 별도의 통신설비를 이용해야함(IPC, Inter Process Communication)
• 프로세스간 변수등의 자료 교환을 할 수 없다.

Multi Thread(멀티 스레드)

멀티 스레드란?

• 하나의 프로세스에 여러개의 스레드로 자원을 공유하여 다수의 작업을 동시에 처리하는것

  특징

• 프로세스 안에서 공유 메모리를 가지고 있기때문에 시간, 자원의 손실이 프로세스대비 적다
• 스레드간 자료, 변수의 공유가 가능하다.

  단점

• 공유메모리를 가지기 때문에 공유메모리의 공간의 손상이 발생하면 다른 스레드또한 작업이 불가능한 상태가 되어버린다.
• 위의 문제를 가지기 때문에 주의깊은 설계가 필요하다. -> Critical Section
  
  
  # Context Switching
• 하나의 프로세스나 쓰레드가 CPU를 사용중인 상태에서 다른 프로세스나 쓰레드가 CPU를 사용하기위해 현재 프로세스의 상태정보를 저장하고 다른 프로세스의 상태값을 불러오는 과정 -> PCB에 저장
• 상태값을 저장하고 불러오는 동안에는 작업을 수행할 수 없다 -> 오버헤드

프로세스와 스레드

Process(프로세스)

프로세스란?

• 컴퓨터에서 연속적으로 실행되는 컴퓨터 프로그램
• 프로그램을 구동하여 메모리상에서 실행되는 작업단위
• OS로 부터 독립된 메모리 영역을 할당받는다.

프로세스의 구조

프로세스는 아래와 같은 구조를 가진다.

• Code : 코드 자체를 구성하는 메모리 영역
• Data : 전역변수, 정적변수, 배열등을 저장
• Heap : 동적 할당시 사용(new(), malloc() 등)
• Stack : 지역변수, 매개변수, 리턴값 등을 임시적으로 저장하는 영역

왜 이렇게 나눈걸까?

1
2

공유 할 수 있는 데이터는 공유하여 메모리의 사용량을 줄이기 위해서
Stack과 Data를 나눈 이유는 스택의 특성과 전역변수를 활용하기 위해서

Process Control Block(PCB, 프로세스 제어 블록)

특정 프로세스에 대한 정보(Process MetaData)를 저장하고 있는 자료구조(Linked List)
아래와 같은 데이터가 저장되어 있다.

• Process MetaData
  • Process ID : 프로세스의 식별번호
  • Process State : 프로세스의 상태(new, ready, running, waiting, terminated)
  • Program Counter : 이 프로세스 다음에 실행할 명령어의 주소
  • CPU Registers
  • CPU 스케줄링 정보: 우선 순위, 최종 실행시각, CPU 점유시간 등
  • 메모리 관리 정보: 해당 프로세스의 주소 공간 등
  • 프로세스 계정 정보: 페이지 테이블, 스케줄링 큐 포인터, 소유자, 부모 등
  • 입출력 상태 정보: 프로세스에 할당된 입출력장치 목록, 열린 파일 목록 등

PBC는 CPU에서 프로세스의 상태에 따라 교체작업(Context Switching)이 이루어질때 PBC에서 저장되어있는 내용들을 불러와 이전 종료시점부터 다시 작업을 재실행한다.

Thread(스레드)

Thread란?

• 프로세스 내부에 존재하는 실행 단위
• 하나의 프로세스가 생성될때 내부에 적어도 하나의 스레드가 같이 생성된다.
• 스레드는 Stack만 따로 할당받고, 나머지 Code, Data, Heap은 공유

프로세스와 스레드의 차이

• 프로세스는 고유한 공간과 자원을 할당받아서 사용하지만(프로세스간 공유하지 않음) 스레드는 고유한 메모리(Stack)를 프로세스로 부터 할당받긴 하지만, 서로 공유하는 메모리(Code, Data, Heap)가 존재함

Stack를 스레드마다 독립적으로 할당 받는 이유

• 독립적인 실행 단위로써 스레드를 사용하기 위해서는 독립적인 메모리 공간이 필요하고, 이를 만족시키는 최소조건이 Stack을 제공하는것 이기 때문이다.

Hash Table

1. Hash Table이란

해시 테이블은 (Key,value)를 기반으로 데이터를 저장하는 자료구조중 하나이다.
해시테이블은 아래의 그림과 같이 Key값을 Hash 함수를 이용하여 고유한 index값으로 변환하고, 이 index에 해당되는 배열(bucket)의 위치에 저장한다. 이런한 구조로 인해 Key값에 Hash 함수를 수행하기만 하면 value값이 저장되어있는 Index를 얻는것이 가능하기 때문에 탐색에 O(1)의 시간복잡도가 소요된다.

2. Hash Functions

Hash 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
Hash Table에서는 Hash 함수를 이용하여 Key에서 부터 고유한 index를 얻는다. 아래에는 간단한 Hash 함수들을 나열해 보았다.

• Division Method : 가장 간단한 Hash함수중 하나로 Key값을 Bucket의 사이즈로 나누어서 계산한다.
• Digit Folding : Key의 문자를 ASCII 코드로 바꿔 합한 데이터를 테이블 주소로 사용한다.
• Multiplication Method :

3. Hash Collapse

Hash 함수에 서로 다른 입력값을 넣었지만 같은 출력값이 나올경우 발생할 수 있는 상황을 말한다. 이러한 상황이 발생할때 해결방법으로 아래와같은 충돌 처리기법이 존재한다.

3.1 충돌 처리 기법

• Open Hashging : 주소 밖의 메모리에 저장
  • Chaining : 충돌이 발생하면 해당 주소에 linked list 이용해서 연결해 저장하는 방법
    • 데이터를 찾을시에 순차탐색을 해야하는 단점이 생김
• Close hashing(Open Addressing) : 테이블 내의 새로운 주소를 탐색하여 데이터를 입력하는 방식
  • Linear probing : 충돌이 발생할때마다 고정값만큼 이동한 주소에 저장하는 방법
  • Quadratic probing : 충돌이 발생한 만큼의 제곱값을 폭으로 주소에 저장하는 방법
  • Double hashing : 해시된 값을 한번더 해싱하여 새로운 주소를 할당하는 방법

reference

http://www.laurentluce.com/posts/python-dictionary-implementation/

KEY

Key는 데이터베이스에서 조건에 만족하는 튜플을 찾거나 순서대로 정렬할 때 다른 튜플들과 구별할 수 있는 유일한 기준이 되는 Attribute(속성)

1. 슈퍼키(Super Key)

• 데이터 베이스에서 테이블의 행을 고유하게 식별할 수 있는 속성 또는 속성의 집합
• 고유하게 식별하는 모든 조합을 나타냄

2. 후보 키(candidate key)

• 슈퍼 키 중에 더이상 줄일 수 없는 형태를 가진 것
• 슈퍼 키를 구성하는 속성 중 하나라도 빠지면 유일성을 잃어버리는 조합
• 기본 키로 선정될 수 있는 후보이기 때문에 후보키라고 이름이 붙여짐
• Null 값을 허용할지 안할지는 여러가지 설이 존재함(된다 하는 사람도 있고 안된다 하는 사람도 있음)

3. 기본 키(Primary Key, 주 키)

• 식별자로 이용하기에 가장 적합한 것을 설계자가 선택 정의한 후보키
• 후보키중 하나를 설계자가 선택해서 기본키로 삼을수 있음
• 항상 고유한 값을 가짐
• Null 값이 존재하지 않아야함

4. 대리 키(alternate key)

• 후보 키들중 기본키로 선택받지 못한 나머지 키들
• 기본키의 조건도 만족하기때문에 언제든지 기본키로 대체될 수 있다.
• 대체 키(surrogate key)라고도 함

5. 외래 키(외부 키, Foreign Key)

• 테이블과 테이블을 연결시켜주는 키
• 여러 테이블을 동시에 분석할때 유용하다
• 하나의 테이블로 저장할때 발생하는 중복된 데이터 발생을 방지하면서 데이터를 이어줄 수 있다.

2. TCP/UDP

2.1 TCP 전송 제어 프로토콜

2.1.1 TCP개요

• 인터넷 상에서 데이터를 메세지의 형태(TCP 세그먼트)로 보내기 위해 IP와 함께 사용하는 프로토콜
• IP와 함께 TCP/IP라는 명칭으로 불린다. IP가 주소를 통해 데이터의 배달을 한다면 TCP는 패킷을 추적 및 관리하는 역할을 한다.

2.1.2 TCP특징

• 연결형 서비스로 연결이 성공해야지만 통신 가능(3 & 4 way Handshaking : 연결설정, 연결해제)
• 데이터의 경계를 구분하지 않음
• 신뢰성이 있다
  • 패킷손실, 중복 순서바뀜을 보장 -> 정확한 데이터 전달 가능
• 흐름제어 및 혼잡제어를 제공
  • 흐름제어 : 송신처와 수신처의 데이터 처리속도를 조절하여 수신자의 버퍼 오버플로우를 방지
    • 수신측의 처리속도보다 송신속도가 빠를경우 도착한 데이터가 손상될 가능성이 존재
    • 수신자가 송신자에게 자신의 상태를 feedback 해서 속도를 조절한다.
  • 혼잡제어 : 네트워크 내의 패킷수가 넘치지 않도록 방지
    • 낮은속도로 전송하기 시작해서 속도를 올림
• Full-Duplex(전송이 양방향으로 동시에 일어날 수 있음), Point to Point(연결이 정확히 2개의 종단점을 가지고 있음)
• ex) 파일전송

2.2 UDP 사용자 데이터그램 프로토콜

2.2.1 UDP개요

• 데이터를 데이터그램 단위로 처리하는 프로토콜 -> 전송계층
• 비연결형, 신뢰성 없는 전송 프로토콜이다.

2.2.2 UDP특징

• 전송방식이 매우 단순해서 빠르다 -> 최소한의 오류만 검출한다.
• 신뢰성이 낮다 -> 전송하는 데이터의 순번이 바뀌거나 누락될 가능성이 존재한다.
• 비연결형 서비스이다
  • 논리적인 경로가 없기 때문에 각각의 패킷은 다른 경로로 전송되고 독립적인 관계를 가진다.
• ex) 실시간 서비스 : 영상통화 등등

2.3 TCP UDP 차이

출처 : soosungp33.log [CS] 📕 Network

1. OSI 모델이란?

컴퓨터 네트워크 프로토콜 디자인과 통신을 계층으로 나누어 설명한 것이다. 각 계층은 하위 계층의 기능만을 이용하고, 상위 계층에게 기능을 제공한다. 일반적으로 하위 계층들은 하드웨어로, 상위 계층들은 소프트웨어로 구현된다.

1.1 7계층으로 나눈 이유

통신이 일어나는 과정을 단계별로 파악할수 있고, 특정한 곳에 이상이 생기면 이상을 탐지하기 쉽고, 이상이 생긴 단계만 고칠수 있기 때문이다

1.2. 계층단계

1. 물리 계층
   • 네트워크의 기본 하드웨어 전송기술로 구성
   • 높은 수준의 기능의 논리데이터 구조를 기초로 한다
   • 하드웨어 기술이 접목되어있어 OSI 아키텍쳐중 가장 복잡한 계층이며 필수적이다
   • 전송단위는 Bit이다
   • 리피터, 케이블, 허브
2. 데이터 링크 계층
   • Point to Point 간 신뢰성 있는 전송을 보장하기 위한 계층
   • 네트워크 위의 개체들 간 데이터를 전달한다.
   • 물리계층에서 발생할 수 있는 오류를 찾아내고 수정하는데 필요한 기능적, 절차적 수단을 제공한다.
   • 주소값은 물리적으로 할당받는다.(MAC address)
   • 네트워크 브릿지나 스위치 등이 이계층에서 동작한다. (Ethernet)
   • 전송단위는 Frame
3. 네트 워크 계층
   • 여러개의 노드를 거칠때마다 경로를 찾아주는 역할을 하는 계층으로 다양한 길이의 데이터를 네트워크들을 통해 전달하고, 그 과정에서 전송 계층이 요구하는 서비스 품질(QoS)을 제공하기 위한 기능적, 절차적 수단을 제공
   • 라우팅, 흐름 제어, 세그멘테이션(segmentation/desegmentation), 오류 제어, 인터네트워킹(Internetworking) 등을 수행한다
   • IP부여, 경로설정(Route)
   • 전송단위는 Datagram(Packet)
4. 전송 계층
   • 양 끝단(End to end)의 사용자들이 신뢰성있는 데이터를 주고 받을 수 있도록 해 주어, 상위 계층들이 데이터 전달의 유효성이나 효율성을 생각하지 않도록 해준다.
   • TCP/UDP프로토콜을 사용한다.
   • 전송 단위는 Segment이다.
   • 여기까지가 물리 계층이라고 한다.
5. 세션 계층
   • 양 끝단의 응용 프로세스가 통신을 관리하기 위한 방법을 제공한다.
   • TCP/IP 세션을 만들고 없애는 책임을 진다.
   • 통신을 하기 위한 세션을 확립/유지/중단
6. 표현 계층
   • 코드 간의 번역을 담당하여 사용자 시스템에서 데이터의 형식상 차이를 다루는 부담을 응용 계층으로부터 덜어 준다.
   • 인코딩이나 암호화등의 동작이 이루어진다.
   • 송신층과 수신측 사이에서 데이터의 형식(png, jpg, webp 등등) 을 정해준다.
7. 응용 계층
   • 응용 계층(Application layer)은 응용 프로세스와 직접 관계하여 일반적인 응용 서비스를 수행한다.
   • DHCP, DNS, FTP, HTTP

Array & ArrayList & LinkedList 의 특징

Array(배열)

• Array는 선언함과 동시에 크기를 함께 적어줘야하는 자료구조이다.
• Array를 선언하면서 특정 자료형과 배열의 크기를 함께 적어주면 특정 자료형이 들어갈 메모리공간을 미리 할당한다.
• 데이터를 삭제해도 공간이 남아있다.
• 장점
  • 미리 주소값(Index)을 할당하다보니 데이터검색이 빠르다.
• 단점
  • 선언한 크기 이상의 데이터를 가지는것은 불가능하기 때문에 데이터가 늘어나거나 하는 최대사이즈를 알수없는 상황에서 사용하기 부적합하다.
• ex) c, c++의 배열

ArrayList

• ArrayList는 크기가 정해져 있지 않다.
• 데이터에 순서가 Index형식으로 존재한다.
• 데이터를 중간에 추가하면 기존에 데이터는 Index의 변화가 일어난다. (뒤로 하나씩 밀리거나 당겨지거나)
• 장점
  • 배열과 같이 Index가 존재하기 때문에 데이터검색이 빠르다.
  • 데이터 검색에 $O(1)$의 시간복잡도
• 단점
  • 중간에 추가하면 기존 데이터의 Index에 변화가 일어나기 때문에 추가적인 연산이 필요하다.
  • 데이터 추가와 삭제에 $O(n)$의 시간복잡도

LinkedList

• 각 노드가 데이터와 포인터를 가지고 연결되어 있는 방식으로 데이터를 저장
• 한방향으로만 연결되거나, 양방향으로 연결, 순환구조로 연결 등의 여러가지 방식이 존재한다.
• 장점
  • 노드의 연결만 끊어주면 되기때문에 데이터의 추가 삭제가 간단함
  • 시간복잡도 $O(1)$
• 단점
  • 특정위치의 데이터를 알기 위해서 처음부터 탐색을 해야하기 때문에 시간이 소요됨
  • 시간복잡도 $O(n)$
• 추가 정보

링크드리스트

링크드 리스트는 각 노드가 데이터와 포인터를 가지고 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다

장점

• 원소 추가와 제거가 쉬움 : 시간복잡도 $O(1)$
• list의 크기를 가변적으로 사용가능

단점

• 탐색에는 효율이 좋지 않음 : 특정위치 탐색에 걸리는 시간복잡도 $O(n)$

결론

• 가변적으로 자주 변하는 데이터에 사용하면 좋다

종류

• 단일 연결 리스트 : 단방향으로 포인터가 연결된 리스트
• 이중 연결 리스트 : 양방향으로 포인터가 연결된 리스트
• 순환 연결 리스트 : Head와 Tail의 노드가 연결되어 순환구조를 가지는 리스트

구현

양방향 리스트로 구현해 보았다.

1. 노드
   • 데이터를 담을 노드를 구현

     1 2 3 4 5

     class Node: def __init__(self, Data): self.Data = Data self.prev = None self.next = None

2. 리스트
   • head와 tail은 더미데이터를 넣어주어서 고려할 사항을 줄여줌

     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

     class linked_list: def __init__(self): dummy = Node(None) self.head = dummy self.tail = dummy self.current = dummy def add(self, data): # 새로운 노드를 추가 newNode = Node(data) self.tail.next = newNode newNode.prev = self.tail self.tail = newNode self.current = newNode def delete(self): # 현재 활성화 노드를 삭제하고 리턴 next_node, prev_node = self.current.next, self.current.prev if next_node != None: next_node.prev = prev_node prev_node.next = next_node return self.current def delete_n(self, n): # n번째 노드를 삭제하고 리턴 current = self.head.next for _ in range(n-1): current = current.next def prev(self): # 활성화 노드를 prev로 이동 self.current = self.current.prev def next(self): # 활성화 노드를 next로 이동 self.current = self.current.next