Thread / Process

Process

A Program in Execution(실행중인 프로그램)
하나의 프로세스는 적어도 하나의 스레드를 포함
Code, Data, File, Register, Stack, Thread를 포함하는 개념

Thread

프로세스의 실행 단위(흐름)
Code, Data, File은 스레드 간 공유되는 자원이며, 프로세스에서 확보한 공간이다.
Register, Stack은 스레드 간 독립적인 자원이며, 프로세스에서 확보해놓은 메모리 공간 내에서 스레드마다 별도의 공간을 가진다.

PCB

Process Control Block 프로세스 제어 블록
프로세스 생성 시 마다 고유의 PCB를 생성한다.
프로세스에 대한 중요 정보를 저장하고, 불러오는 작업을 하기 위해 이용된다.
프로세스 고유 식별자 포인터, 프로세스의 현재 상태, 스케쥴링 우선순위, CPU 레지스터 정보, 주기억장치 관리 정보 등을 포함하고 있다.
(PID, Program Counter, File, Pointer, Register, etc ...)

프로세스와 쓰레드 상태 전이도

프로세스 상태 전이도

  • Running

    ​ 

    Process가 CPU에 의해 수행되고 있는 상태.
TimeOut에 의해 Ready Queue로 이동될수 있음.
IO 등에 의해 Block 될수 있다.

  • Ready 

    프로세스가 실행중이지만, CPU에 의해 스케쥴링이 되지않아, 실질적으로 수행이 되지 않은 상태. 
Dispatch되면 Running 상태로 전이된다.

  • Block

    Running 상태의 프로세스가 인터럽트 등에 의해 Block 되었을때의 상태. 
Block이 끝나면 스케쥴링을 위해 Ready Queue로 이동한다.

스레드의 상태 전이도

  • Runnable

    스케쥴링 Timeout(), Notify(), I/O Finish 등 다시 실행시킬수 있게 된 상태

  • Not Runnable

    Suspend(), Wait(), Sleep() 등 I/O Block 등에 의해 실행 불가능하게 된 상태

  • Dead

    실행중인 쓰레드가 Stop 혹은 Exit되었을때.
실행 불가능한 스레드가 Stop 되었을때.

Logical Address, Physical Address

Logical Address(논리적 주소)

호스트나 라우터가 사용하는 논리적 주소
네트워크에서는 IP주소를 의미, 로컬에서는 CPU가 메모리에 접근하기 위해 사용하는 Virtual Address로 볼수 있다. 

ex) ARP(Address Resolution Protocal)

Physical Address(물리 주소)

로컬 주소라고도 하며, 로컬 네트워크에서만 유효한 주소
일반적으로 하드웨어로 구현하며, 호스트나 라우터 내에 포함되어 있음.

ex) TLB(Translation Lookaside Block)
      - 가상 주소에서 물리주소의 변환의 속도를 위한 캐싱
      - 최근에 참조한 주소 변환 정보를 캐싱해 주었다가 재사용

IPC(Inter-Process Communication) Mechanism

배경

프로세스 간에는 가상 메모리 공간을 공유하지 않는다. (기본적으로 프로세스 간 커뮤니케이션은 불가능)

목적

프로세스 간 통신을 위해서 존재

IPC 기법의 종류

+ 공유 메모리 : 메모리 자체를 공유
+ File, Socket : 하나의 파일을 여러 프로세스가 공유하거나, Socket을 이용해서 메세지를 넘긴다.
+ Signal : 한 프로세스가 다른 프로세스에게 Signal을 줄수 있다.
+ Message Qeueing : 한 프로세스가 다른 프로세스에게 메세지 큐를 이용해 전달한다.
+ Pipe : 파이프를 이용해 메시지를 주고 받을수 있다.
+ Semaphore : 동기화 기법과 겸용해서 IPC에서 1:N 관계에서 사용한다.
+ Message Passing : 병렬 컴퓨팅을 이용하기 위한 표준 규격
+ Memory Mapping File : 가상 메모리처럼 프로세스 주소 공간을 예약하고, 예약한 영역에 물리 저장소를 커밋하는 기능을 제공한다.

Interrupt

Interrupt

정의

A Signal to the Processor or An Instruction in Software.
CPU 외부의 HW or SW에 의해 정상적인 실행 흐름을 변경하여, 시급한 작업을 먼저 수행한뒤, 실행중인 프로세스로 복귀하는 방법
  • 비동기적인 주변장치의 서비스 요청 이벤트 처리
  • 인터럽트 발생 시 복귀 주소를 저장해 두었다가, ISR(Interrupt Service Routine) 마지막에 복귀 명령에 이용한다.
  • 운영체제는 인터럽트 의존적이다.

인터럽트 종류

+ Hardware Interrupt(External) : 입출력 등 외부 장치에서 발생하는 인터럽트
+ Software Interrupt(Internel과 유사) : 잘못된 명령이나 데이터 사용에 의해 발생하는 인터럽트 = Trap

실질적으로 Hardware Interrupt만 존재한다. Trigger가 SW일 경우 Software Interrupt라고 부르기만 할뿐
실질적으로 Hardware Interrupt만 존재한다. Trigger가 SW일 경우 Software Interrupt라고 부르기만 할뿐

ISR(Interrupt Service Routine)

인터럽트가 발생하면, 유저모드에서 커널 모드로 들어가서 인터럽트를 처리한다.
  • 인터럽트가 발생하면 현재 프로그램 상태를 PCB에 저장
  • Interrupt Vector(인터럽트에 해당하는 ISR 실행 정보를 담는 벡터)를 탐색
  • 인터럽트 처리 : 요청 장비를 식별, 실질적 인터럽트 처리
  • 상태를 복구하고, PC에 저장된 프로그램 상태를 통해 실행 개재

인터럽트 발생을 확인하는 방법

  • Polling : 하나씩 인터럽트가 걸린 프로세스를 확인
  • Vector Interrupt System : 인터럽트 요청을 한 프로세스를 확인할수 있다.
  • Daisy-Chain : 하드웨어적 방법으로 확인한다.

Top Half, Bottom Half

배경

인터럽트가 발생했을 시, 데이터를 가져오고 수행하는 단계에서 처리 과정의 시간이 길어질 경우 오랫동안 아무 작업을 못한다는 단점이 있다.

목적

인터럽트가 발생했을 때 데이터를 가져오는 빠른 동작을 수행하고, 데이터를 처리하는 동작은 그 이후에 수행한다.

Top Half

데이터를 가져오는 동작 -> 비교적 빠른 동작

Bottom Half

가져온 데이터를 처리하는 동작 -> 비교적 느린 동작

과정

인터럽트 Disable --> Top-Half 처리 --> 인터럽트 Enable --> Bottom-half 처리

Hard Link, Symbolic Link

Original File Data를 가르키는 INode를 직접 가르키고 있다.(원본과 동일한 inode)

Hard Link된 파일을 수정하면 원본도 같이 수정된다.

원본 파일 자체에 Link를 연결한 방식

바로가기와 유사한 개념, 심볼릭 링크 파일을 수정해도 원본은 변하지 않는다.

iNode

커널 내에 현재 사용중인 파일의 대한 자료구조
해당 파일의 대한 대부분의 정보를 가진다. : 파일의 소유권/권한, 디스크 내의 물리적 주소, 파일의 링크 수/형태/크기, 파일 관련 시간, inode 수정 시간
사람은 파일을 이름으로 구분하고 , 컴퓨터는 iNumber로 구분한다.

Race Condition

정의

스레드 간 데이터를 공유하면서 발생하는 논리적 오류

문제의 해결 방안

데이터에 접근하는 연산을 Atomic Operation으로 처리한다.
Critical Section으로 설정함으로써 동기화 한다.

임계 영역

  1. 스레드들이 하나의 자원에 접근할 때 순서를 만들어 실행해 준다.
  2. 공유 자원의 독립적인 처리를 보장한다.

  3. 임계 구역의 관리 방법(Lock)과 동기화 객체

    - Mutex(Mutual Exclusion 상호배제) : 제어되는 섹션에 하나의 스레드만을 허용
- Semaphore : 공유 리소스에 접근할수 있는 최대 허용치만큼 동시에 접근할수 있도록 허용 (열쇠가 여러개 있음.)
- Event : 쓰레드의 작업 순서나 시기를 결정한다.

Deadlock

정의

프로세스가 자원을 얻지 못해 다음 처리를 못하는 상황
= 원하는 리소스가 다른 프로세스(스레드)에게 할당되어 있기 때문에, 무한히 기다리게 되는 상황

DeadLock의 조건

  1. Mutual Exclusion : 한 리소스는 두개의 프로세스에게 동시에 할당될수 없다.
  2. Hold And Wait : 한 프로세스가 한 리소스를 가지고 있고 필요한 또다른 리소스는 다른 프로세스가 가지고 있다.
  3. No Preemption : 할당되어 있는 리소스는 프로세스가 해제하기 전까지 강탈할수 없다.
  4. Circular Wait : P0가 원하는 자원은 P1이 P1이 원하는 자원은 P2가 …. Pn이 원하는 자료는 P0가 가지고 있다.

DeadLock의 해결(예방)

  1. Mutual Exclusion 부정 : 자원의 공유가 가능하다면 여러개의 프로세스가 동시에 점유할수 있다.
  2. Hold And Wait 부정 : 미리 자원을 점유하지 못하고, 필요한 자원이 모두 이용 가능할 경우 한꺼번에 점유하고 실행된다.
  3. No Preemption 부정 : 중간에 강제로 자원을 선점할수 있다.
  4. Circular Wait 부정 : 각 프로세스에 우선순위를 부여하고 프로세스의 실행 순서를 지정한다.

Context Switching

정의

Running 상태에서 Task(스레드, 프로세스)가 사용하던 Context를 메모리 특정 영역에 저장한 후, 새로 수행될 Task의 Context를 PCB 또는 Stack에서 CPU 레지스터 영역으로 복사하여 수행되도록 하는 작업

Context Switching 순서

  1. 인터럽트 : 현재 상태를 PCB에 저장한다.
  2. 프로세스(스레드) 스케쥴링 : 프로세스(스레드) 스케쥴러에 의해 다음 프로세스를 Ready Queue에서 선택한다.
  3. Dispatch : 다음 프로세스를 PCB에서 복구한다.

Context Switching of Process & Thread

  1. Process : 커널 레벨 문맥 교환
  2. Thread : 유저 레벨/ 커널 레벨 문맥 교환
    • PCB가 저장되고 복귀하는 과정이 없기 때문에, 프로세스의 문맥교환보다 오버헤드가 줄고, 효율성이 올라간다.
    • 하지만 동기화가 불완전하거나 불확실한 경우 Race Condition 발생 가능

Preemptive / Non-Preemptive Scheduling

Preemptive(선점) 스케쥴링

우선순위가 높은 다른 프로세스가 실행중인 CPU를 강제로 빼앗아 사용할수 있음.

Non-Preemptive(비선점) 스케쥴링

CPU가 한 프로세스를 할당하면, 다른 프로세스는 CPU를 선점할수 없음.

Virtual Memory

목적

쉬운 프로그래밍이 가능하다 -> 실제 물리주소와 물리적 구조를 몰라도 프로그래밍이 가능
Multi-Programming의 정도를 올릴수 있다.
메모리와 하드디스크 간 Swapping 횟수를 줄일수 있다.

가상 메모리 기법

  1. CPU가 가상 메모리에 우선적으로 수행할 작업을 로드
  2. Virtual Memory 공간에는 연속적인 가상 메모리가 구성된다.
  3. MMU를 통해 가상 메모리의 논리적 주소를 물리적 주소로 사상(Mapping) 한다.
    - 이 과정에서 MMU는 페이지 테이블을 거친다.
  4. 실제 메모리의 물리적 주소 공간에 페이지가 로드된다.

MMU(Memory Management Unit)

CPU가 메모리에 접근하는 것을 관리하는 장치.
가상 메모리 주소와 실제 메모리 주소 사이의 변환을 위해 MMU는 변환 참조 버퍼(Translation Lookaside Buffer, TLB)라는 고속의 보조기억장치를 참조한다

Priority Queue

Priority Queue

우선순위 속성을 갖는 데이터를 다루며, 우선순위가 높을수록 앞에 자동정렬되어 배치된다.
우선순위 큐는 힙(Heap, 완전 이진트리)를 이용해 구현된다.

Difference between System Call and Interrupt

System Call

유저 레벨에서 커널이 제공하는 서비스(OS 제공 하는 기능/모듈)를 이용하기 위해 호출된다.

커널 영역에서 서비스를 이용하기 위한 인터페이스적 개념
Application(User) <-> System Call <-> OS

Interrupt

주변 장치와 커널이 Communication하는 방식 중 하나(신호의 개념)
주변 장치나 CPU가 자신에게 발생한 사건을 커널에게 알리기 위한 매커니즘

Locality of Reference(참조의 지역성)

지역성의 원리

주어진 시간동안 CPU가 메모리 참조가 제한된 영역에서만 이루어지는 현상

지역성의 원리에 의해 한번 참조된 부분은 다시 참조될 확률이 높다.

Cache Memory

CPU의 빠른 처리 속도와 Main Memory의 느린 처리 속도 차이를 해결하기 위한 기법
캐시 메모리는 지역성의 원리를 이용한 좋은 예제

Cache <-> CPU  WORD 단위
Cache <-> Main Memory  Block 단위

Cache Miss

  1. Compulsory Miss

    최초 데이터 접근 시 반드시 발생하는 미스

  2. Capacity Miss

    캐시 사이즈가 작아서 발생하는 미스, 캐시가 모든 블럭을 포함하지 않음.

  3. Conflict Miss

    캐시의 한 블락에 너무 많은 메모리 블럭이 매핑되어서 생기는 미스
    (Set Associative / Direct Mapped)

  4. Invalidation

    두 CPU가 동시에 하나의 데이터에 접근하면서 발생하는 미스

Atomic Operation

Operation을 결합하여 하나의 Operation으로 표시되어, 결과가 성공이나 실패로 나타나는 Operation.

Race Condition을 막기 위해 만들어졌다.

연산이 끝날때 까지 다른 프로세스는 값의 변화에 대해 알수 없음.
연산 실패시 시스템은 다른 Operation이 시작되기 전까지 이전의 실패한 상태를 저장.

ex) InterlockedAdd, InterlockedExchange 등

Paging, Demand Paging Technique

페이징 기법

작업을 동일한 크기의 여러 페이지로 나누어 보조 기억장치에 저장해 두고, 작업이 실행을 시작하면, 필요한 때마다 해당 페이지를 주기억 장치로 로드하는 방식

Page Fault

해당 페이지(작업이 요구된 페이지)의 페이지 엔트리가 유효하지 않을때 발생

페이지 교체(Page Replacement) 정책

  1. FIFO

    • 메모리에 오래 있던 페이지를 교환
    • 계속 사용하는 페이지의 경우 문제가 발생할수 있다.
    • Belady’s Anomaly(벨라디의 모순)이 나타남 : 프로세스에게 프레임을 더 주었는데, 더 많은 페이지 폴트가 발생하는 현

  2. LRU(Least Recently Used)

    • 가장 오랫동안 사용하지 않은 페이지를 교체(지역성의 이론 근거하여 만들어짐)
  3. OPT
    Optimal하게 페이지를 교체 구현이 어렵다.
  4. LFU(Least Frequently Used)
    • 각 페이지들에 대해 참조된 횟수를 기준으로 교체

Thrashing(쓰레싱)

메모리나 캐쉬 등에서 너무 많은 페이지 교체가 발생하는 현상 -> 속도저하를 일으켜 성능을 떨어트린다.

Segment Technique

정의

각 작업을 여러개의 서로 다른 세그먼트로 나누어 작업 실행에 필요한 세그먼트만 주 기억장치로 적재하여 실행하는 방식

세그먼트 기법에서는 주 기억장치가 작업을 동적인 크기로 할당한다. <-> 페이징에서는 동일한 Page크기로 분할

Pipeline Processing 방식

Pipeline

하나의 프로세스를 서로 다른 기능을 가진 여러 세부 서브 프로세스로 나누어 각 서브 프로세스가 동시에 서로 다른 데이터를 취급하도록 하는 방식

Pipeline 목적

  1. 프로세스 처리의 병렬성 증대
    • 병렬 시스템에서 각 프로세스 상에서 서로 다른 연산들이 동시에 수행된다.(파이프라인)
  2. MIMD(Multi Instruction Stream, Multi Data Stream)
    • 멀티 프로세서, 파이프라인 프로세서

파이프라인에서 중요한 점

한 단계의 처리 시간이 다른 단계의 처리 시간과 큰 차이가 날 경우, 병목현상으로 인한 성능저하. 단계별로 상호 동기화가 필요

주 기억 장치(RAM/ROM) <-> Cache 간 데이터 전송

Mapping Process

  1. Directed Mapping
  2. Associative Mapping : 무작정 빈곳을 찾아서 Cahce에 넣는 방식
  3. (N-Way) Set Associative Mapping : Directed Mapping 방식을 사용하는 Cache N개로 구성. 저장된 데이터에 대해서는 Associative Mapping.

Cache Arragement

  1. Cache 블록을 늘리는 방법
    Spatial Locality(공간적 지역성)에 대한 고려가 필요
  2. Cache Way 수를 늘리는 방법(Set-Associative)
    Temporal Locality(시간적 지역성)에 대한 고려가 필요

RISC, CISC

RISC(Reduced Instruction Set Computer)

CPU 명령어 갯수를 줄여 하드웨어 구조를 간단하게 만드는 방법
적은 수의 명령어만으로 명령어 집합을 구성
고정 길이 명령어를 사용하여 빠른 해석이 가능
파이프라인을 사용하지않음으로 많은 레지스터의 사용, 레지스터간 Save, Load 수행한다.

CISC(Complexed Instruction Set Computer)

복잡한 명령어 집합을 가짐.
가변 길이 명령어를 사용한다.
회로도가 많이 복잡하며, 레지스터 간 / 레지스터 - 메모리 / 메모리 - 메모리 연산을 수행한다.

Garbage Collection

정의

개발자가 명시적으로 해야 했던 메모리 관리를 자동적으로 처리하는 기법

목적

참조를 잃는 순간 지우는 등의 작업을 통해 메모리 누수를 방지한다.

GC Algorithm

Generation에 따라 적절한 알고리즘을 적용(Young-Tenured_Perm. 생성된지 얼마 안된 객체는 GC의 대상이 되기 쉽다.)
  1. Serial
    • 하나의 Garbage Collector가 차례대로 다 처리하는 방식
  2. Parallel
    • 여러개의 Garbage Collector가 나눠서 처리하는 방식
  3. Stop the World
    • 프로세스가 일시적으로 실행을 멈추고, GC 수행하는 방식
  4. Concurrent
    • 프로세스 실행과 함께 GC를 진행

  5. Compacting / Non-Compacting

    • 단편화를 신경써서 압축을 하는 방식 / 하지않은 방식

      5-1. 단편화

      내부 단편화 : 100 크기의 공간에 70크기의 프로세스가 들어가면 30의 공간이 남는데 이를 내부 단편화라고 한다.
      외부 단편화 : 프로세스의 크기(120)가 남아 있는 메모리 공간(100)보다 크기 때문에 발생하는 단편화를 외부 단편화라고 한다.

  6. Copying

    • 특정 영역으로 복하하여 추후에 메모리를 해제하는 방식

RPC, RMI

RPC(Remote Procedure Call)

다른 네트워크의 컴퓨터에 있는 함수를 호출할 수 있도록 해주는 저 수준의 프로세스 간 통신 방법

- 네트워프 프로그래밍을 함수 호출 레벨 수준으로 작성할수 있게 해주는 API

RMI(Remote Method Invocation)

원격 메소드 호출로 네트워크 상에서 떨어져 있는 객체의 메서드를 투명(Transparent) 하게 호출해주는 방법

- RPC와 비슷하지만 객체지향적 개념이 추가되었다고 볼수 있음.