운영체제란?

운영체제는 프로세스, 리소스, 사용자 인터페이스 등을 관리하기 위해 응용 프로그램에 시스템 서비스를 제공하기 위해 컴퓨터에서 상시 실행되는 프로그램이다.

커널

커널은 운영체제의 핵심이라 할 수 있는 중요한 소프트웨어로 하드웨어의 자원을 자원이 필요한 프로세스에게 나눠주고, 프로세스 제어, 메모리 제어, 프로그램이 운영 체제에 요구하는 시스템 콜 등을 수행하는 부분이다.

프로그램

프로그램이란 컴퓨터 하드웨어한테 특정 테스크를 실행시키는 명령어들의 집합이다.

시스템 콜

사용자 모드

응용 프로그램이 실행되는 모드이다. 사용자 모드에서는 프로세스가 제한된 권한으로 실행되고 프로세스가 직접적으로 하드웨어 자원에 접근할 수 없으며, 운영 체제의 제어 하에 실행된다.

직접적으로 커널에 접근할 수 없다.

커널 모드

운영 체제의 핵심 부분인 커널이 실행되는 모드이다. 커널 모드에서는 운영 체제가 전체 시스템 자원을 통제하고 다양한 프로세스 및 하드웨어 자원에 직접적으로 접근할 수 있다.

시스템 콜

운영 체제의 커널이 제공하는 서비스에 대해, 응용 프로그램의 요청에 따라 커널에 접근하기 위한 인터페이스이다.

1. 사용자 모드에서 애플리케이션이 실행중이다.
2. 커널의 서비스를 사용하기 위해 시스템 콜을 호출한다.
3. 사용자 모드에서 커널 모드로 변경된다.
4. 시스템 콜을 실행한다.
5. 커널 모드에서 사용자 모드로 변환된다.

프로세스

프로세스란 실행중인 프로그램을 의미한다. 프로그램이 메모리에 올라간 상태.

• 프로세스는 운영체제의 작업의 단위이다.
• 프로세스는 실행되기 위해 다음 자원이 필요하다.
  • CPU Time
  • memory
  • files
  • I/O Device

메모리 구조

• Text section: 실행할 프로그램의 코드가 저장된다.
• Data section: 전역 변수와 정적 변수가 저장된다.
• Heap section: 프로그램 런타임 시 동적 할당된 객체가 저장된다.
• Stack section: 지역 변수나 함수 호출 스택, 함수 파라미터가 저장된다.

Stack과 Heap은 서로 다른 방향으로 메모리를 채워 나간다.

5개의 프로세스 상태

OS가 프로세스를 관리하기 위해, 5개의 생명 주기를 가진다.

• New: 프로세스가 생성된 상태이다.
• Running: CPU를 점유해서 프로세스의 명령어를 CPU에 로드해서 실행하는 상태이다.
• Waiting: 프로세스가 외부 이벤트를 기다리는 동안 잠시 멈춰있는 상태이다.
  • 예를 들어 I/O가 완료 인터럽트까지 기다리는 경우
• Ready: 프로세스가 CPU를 실행하기 위해 대기 중인 상태이다. CPU를 제외한 다른 자원이 준비완료된 상태이다.
  • I/O가 끝났다는 시그날이 오면 Ready Queue로 옮겨지고 Ready 상태가 된다.
• Terminated: 프로세스가 종료한 상태이다.

scheduler dispatch: OS가 프로세스에게 cpu를 할당하는 것

9개의 프로세스 상태

시스템의 복잡성이 증가하면서 더 정교한 제어와 관리가 필요해졌다.

• New: 프로세스가 생성되고 시스템에 등록되는 단계이다. 이 단계에서는 프로세스에 필요한 시스템 자원이 할당되고 초기화된다.
• Ready: 프로세스가 실행을 기다리는 상태이다. 모든 필요한 자원이 할당되어 있고, CPU가 사용 가능한 상태일 때 프로세스는 준비 상태에 있다.
• Running: CPU에서 명령어를 실행하는 상태이다. 현재 실행 중인 명령어를 처리하고 있다.
• Blocked: 프로세스가 어떤 이벤트(예: 입출력 작업의 완료)가 발생할 때까지 기다리는 상태이다. 프로세스는 일시적으로 중단되고, 해당 이벤트가 발생하면 준비 상태로 전환된다.
• Exit: 프로세스의 실행이 완료되었거나, 오류로 인해 종료된 상태이다. 이 단계에서는 프로세스가 소멸하고 사용한 자원이 반환된다.
• Ready Suspend, Blocked Suspend: 준비 또는 차단 상태의 일시 중지된 프로세스를 나타낸다. 일시 중지된 상태에서 다시 실행될 때 기다리는 상태다.

추가 상태

• Resident: 프로세스의 일부 또는 전체가 메모리에 존재하는 상태이다. 프로세스가 실행되기 위해서는 메모리에 상주해야 한다.
• Swapped Out: 프로세스의 일부 또는 전체가 메모리에서 스왑 아웃되어 디스크에 저장된 상태다. 이는 메모리 부족 시에 사용될 수 있다.

Process Control Block

프로세스가 가져야 할 모든 정보를 저장하는 구조체이다. PCB(Process Control Block)는 프로세스의 정보를 담고 있으므로, 메모리의 커널 영역에 위치한다.

• 프로세스 상태(Process State)

• 프로그램 카운터(Program Counter)

• CPU Register

• CPU-스케줄링 정보(CPU-scheduling information)

• 메모리 관리 정보(Memory-management information)

• 입출력 상태 정보(I/O status information)

Program Counter와 CPU Register, Process State 등을 Context라 지칭한다.

프로세스 스케줄링

멀티 프로그래밍의 목적

• 프로세스를 동시에 작동시키는 것
• CPU 사용을 최대화하기 위해서

Time Sharing의 목적

• CPU core를 프로세스 간에 자주 변경
• 각 프로그램이 동시에 실행되는 것 처럼 보이게 위한 것

스케줄링 큐

프로세스가 시스템에 들어서면, 프로세스는 Ready는 Ready Queue에 Waiting은 Wait Queue에 삽입된다.

Queue는 PCB의 linked list 형태로 구현된다.

Queueing Diagram

Ready Queue에 대기하고 있는 프로세스가 CPU 자원을 획득하면 실행 중인 상태로 변한다. 이때 다음과 같은 이벤트들이 발생할 수 있다.

• I/O Request가 발생하면 I/O Wait Queue에 들어갔다가 I/O가 끝나면 다시 Ready Queue에 들어간다.
• Time Slice가 끝나면 바로 Ready Queue에 들어간다.
• fork가 발생하면 새로운 프로세스는 new 상태가 되고, child 프로세스는 Ready Queue에 들어간다.
• interrupt가 발생하면 interrupt 종료를 기다리다가 종료하면 Ready Queue에 들어간다.

Context Switching

PCB(프로세스가 사용되고 있는 상태)를 문맥(context)이라 한다.

Interrupt가 발생하면 추후에 CPU를 획득하여 running 할 수 있게 현재 실행 중인 프로세스의 문맥을 저장한다.

어디까지 저장했는지가 중요하므로 PC(Program Counter)는 중요한 요소이다.

Context Switching은 CPU core를 다른 프로세스에게 넘겨주는 것이다. 현재 프로세스의 문맥을 PCB에 저장하고, 새로 획득할 프로세스의 문맥을 복원하는 작업이 이뤄진다.

1. 프로세스가 CPU를 할당 받고 실행되던 중, 인터텁트나 시스템 콜이 발생한다.
2. 원래 수행 중인 프로세스는 PCB에 문맥을 저장한다.
3. 새롭게 실행시킬 프로세스에게 CPU를 넘긴다.
   • 이 과정에서 원래 수행 중인 프로세스는 준비(ready) 상태로, 새로 실행시킬 프로세스는 실행(running) 상태로 변한다.
4. 새롭게 CPU를 할당받을 프로세스는 예전에 저장했던 PCB로부터 실제 하드웨어로 복원한다.

문맥 교환의 오버헤드

• 레지스터 저장 및 복원: 현재 실행 중인 프로세스의 레지스터 상태를 저장하고, 새로운 프로세스의 레지스터 상태를 복원하는 작업이 필요하다. 이는 CPU의 레지스터에 저장된 값들을 메모리로 이동하고, 다시 레지스터로 복원하는 작업을 수반하며, 이 과정에서 오버헤드가 발생한다.

• 메모리 관리: 프로세스 간의 메모리 공간을 교환하고, 페이지 테이블을 업데이트하는 등의 작업이 필요하다.

• Latency: 컨텍스트 스위칭 자체가 프로세스 간의 전환이므로, 스위칭이 발생할 때마다 일정량의 시간이 소요됩니다. 이는 프로세스 상태를 저장하고 복원하며, 레지스터, 캐시, 메모리 등의 상태를 전환하는 과정에서 발생합니다.

프로세스 생성과 소멸

생성

실행되는 동안 프로세스는 여러 개의 새로운 프로세스를 생성할 수 있다. 이때 생성하는 프로세스를 부모(parent) 프로세스, 새로운 프로세스를 자식(child) 프로세스라고 부른다.

현대 운영체제들은 유일한 프로세스 식별자를 사용하여 프로세스를 구분한다.

실행 측면

프로세스가 새로운 프로세스를 생성할 때, 두 프로세스를 실행 측면에서 두 가지 경우가 존재한다.

• parent와 child가 동시에 실행되는 중이다.
• child가 종료될 때까지 parent는 wait 상태를 유지한다.

주소 공간 측면

새로운 프로세스들의 주소 공간 측면에서 두 가지 경우가 존재한다.

• parent와 child는 같은 작업이다: 같은 메모리 공간 공유
• parent와 child는 다른 작업이다:새로운 프로그램 로딩

fork()

Parent process에서 fork()를 실행하게 되면 parent process의 프로그램을 복제하여 child process를 생성하고, parent process는 다음 문장을 실행한다.

fork()로 인해 parent process와 child process라는 두 개의 독립적인 프로세스가 만들어진다. 이들 프로세스는 exec()을 호출하기 전까지는 같은 프로그램을 실행한다. 두 프로세스는 다른 메모리에 위치하고 있으며, 상태를 공유하지 않는다.

parent process가 마지막 구문을 실행했으면, wait() 시스템 콜을 호출한다.

• wait()을 부모 프로세스에게 다음을 허용한다.

1. 자식 프로세스가 종료될 때까지 기다린다.
2. 자식 프로세스의 상태 전달받는다.
3. 자식 프로세스가 종료하면서 return이 있다면 넘겨받을 수 있다.

pid = fork(); 시 parent process의 경우 0보다 큰 값을, child process의 경우 0을 pid로 반환한다.

exec()

exec() 시스템 호출은 현재 실행 중인 프로세스의 이미지를 새로운 프로그램 이미지로 교체한다.

exec() 함수가 호출되면 현재 프로세스의 메모리에 있는 코드 및 데이터는 모두 지워지고, 새로운 프로그램의 코드와 데이터가 메모리에 로드된다. 따라서 exec() 함수를 호출하면 현재 프로세스는 새로운 프로그램의 시작점에서 실행을 시작한다. 이는 새로운 프로그램을 실행하기 위해 현재 프로세스의 상태를 변경하고, 새로운 프로그램을 로드하는 것과 동등하다.

종료

프로세스가 마지막 문장의 실행을 끝내고, exit 시스템 콜을 사용하여 운영체제에 자신의 삭제를 요청하면 종료한다. 이 시점에서, 프로세스는 자신을 기다록 있는 부모 프로세스에 상태 값을 반환할 수 있다.

OS는 종료된 프로세스의 메모리, file, I/O 버퍼 등을 해제한다.

부모 프로세스는 wait 시스템 콜을 사용해서 자식 프로세스가 종료할 때를 기다릴 수 있다. wait 시스템 콜은 부모가 자식의 종료 상태를 얻어낼 수 있도록 하나의 인자를 전달 받는다. 이 시스템 콜은 부모가 어느 자식이 종료됐는지 구별할 수 있도록 종료된 자식의 프로세스 식별자를 반환한다.

좀비 & 고아 프로세스

프로세스가 종료하면 사용하던 자원은 운영체제가 되찾아 간다.

• Zombie Process: child process는 종료했는데 parent process가 wait하지 않는 상태이다. Child process의 자원이 회수되지 않은채 남아있는 것을 Zombie라한다.
• Orphan Process: child process는 실행 중인데, parent process가 wait를 하지 않고 종료했다. Parent process가 없는 child process를 Orphan이라 한다.

좀바 프로세스 해결법

Parent process가 wait() 시스템 콜 호출하면 좀비 프로세스의 프로세스 식별자와 프로세스 테이블의 해당 항목이 운영체제에 반환된다.

고아 프로세스 해결법

부모 프로세스가 정상적으로 종료되면 init(systemD) 프로세스가 책임을 맡는다. UNIX 시스템에서 init 프로세스는 모든 프로세스의 부모다. init 프로세스는 주기적으로 wait()를 호출하여 Orphan process의 종료 상태를 수집하고 프로세스 식별자와 프로세스 테이블의 해당 항목이 운영체제에 반환된다.

Orphan Process 해결범으로 Double-forking을 통한 방법도 존재.

Inter Process Communication

프로세스가 동시(concurrently)에 실행되면 독립(independent)적일 수도 있고, 협력적(cooperating)일 수도 있다.

• independent: 프로세스는 다른 프로세스와 데이터의 공유가 없다
• cooperating: 영향을 주거나 받는다. 데이터(메세지)를 주고 받는다

Cooperating 프로세스 간에 데이터를 주고 받는 IPC가 필요하다.

• 정보 공유: 여러 응용 프로그램이 동일한 정보에 협력할 수 있다. 예를 들어 특정 프로세스에서 다른 프로세스로 복사, 붙여넣기를 하게 되는 경우가 있다.
• 계산 가속화:
• 모듈성:

프로세스 간 통신에는 기본적으로 두 가지 모델이 있다.

• shared memory: 특정 메모리 영역을 통해 통신
• message passing: 프로세스의 주소 공간이 다르므로 운영체제(커널)에게 통신을 맡김

Shared Memory Model

공유 메모리를 사용하는 프로세스 간 통신에는 통신하는 프로세스들이 공유 메모리 영역을 구축해야 한다. 일반적으로 공유 메모리 영역은 세그먼트를 생성하는 프로세스의 주소 공간에 위치한다. 이 공유 메모리 세그먼트를 이용하여 통신하고자 하는 다른 프로세스들은 이 세그먼트를 자신의 주고 공간에 추가해야 한다. 공유 메모리는 둘 이상의 프로세스가 메모리 공유 금지 제약 조건을 제거하는 것에 동의하는 것을 필요로한다.

일반적으로 운영체제는 한 프로세스가 다른 프로세스의 메모리에 접근 금지임을 기억하자.

생산자-소비자 문제

A producer produces iinformation that is consumed by a consumer.

Ex) a compiler produces assembly code, and a assembler consumes it.

생산자는 정보를 생산하고, 소비자는 그 정보를 소비한다.

생산자와 소비자는 동시에 실행되어야 한다!

버퍼를 이용하면 해결할 수 있다.

• 생산자는 버퍼를 채운다.
• 소비자는 버퍼를 비운다.

대부분은 bounded buffer이므로 버퍼가 가득차면 생산자는 wait 상태가 된다. 소비자는 버퍼가 비게 되면 wait 상태가 된다.

shared memory는 생산자 소비자 문제에서 버퍼의 역할로 만들면 통신이 가능하다.

다수의 Prosumer-Prosumer 간의 빠른 통신에 적합

문제점

• 개발자가 명시적으로 메모리 영역을 설정해야한다.
• 여러 프로세스가 동시에 메모리에 접근하는 문제가 발생할 수 있어서 별도의 동기화 과정이 필요하다는 단점이 있다.

POSIX 공유 메모리

POSIX 공유 메모리는 메모리에 파일을 생성하는 형태인 memory-mapped file을 이용한다.

Message Passing Model

메세지 전달 모델은 동일한 주소 공간을 공유하지 않고도 프로세스들이 통신을 하고, 그들의 동작을 동기화할 수 있게 OS가 프로세스 간 통신을 위한 api를 제공한다.

두 가지 작업으로 이루어진다.

• send(message)
• receive(message)

Message Passing에서 다양한 방법으로 구현될 때, 고려할 수 있는 요소들이다.

• direct/indirect
• synchronous/asynchronous
• automatic/explicit buffering

직접 통신

명시적(explicitly)으로 송신자와 수신자를 작성한다.

• send(P, message): 프로세스 P로 메시지를 전달한다.
• receive(Q, message): 프로세스 Q가 메시지를 받는다.

Link가 자동으로 생성된다. 두 개의 프로세스 간에 단 하나의 Link만이 존재한다.

간접 통신

메시지가 port로부터 송수신된다. port는 object라고도 볼 수 있으며, 프로세스로부터 메시지를 받을 수 있고 제거될 수 있다.

• 각 프로세스에 대해 하나의 포트가 존재한다.
• 메시지 전송: send(A, message) 형태로 포트 A로 메시지를 전송한다.
• 메시지 수신: receive(A, message) 형태로 포트 A에서 메시지를 가져온다.

두 개의 프로세스가 port가 존재해야 Link가 생성된다. Link는 두 개 이상의 프로세스로 이루어질 수 있다. 두 개의 프로세스 사이에서 여러 개의 Link가 존재할 수 있다.

OS가 프로세스에게 제공하는 기능: Create Port, Send Port, Receive Port, Delete Port

동기/비동기

• Blocking send: 메시지가 수신될 때까지 전송자는 blocking된다.
• Non-blocking send: 전송자는 메시지를 보내고 나서, 계속 다음 구문을 진행한다.
• Blocking receive: 메세지를 모두 받을 때까지 blocking된다.
• Non-blocking receive: 수신자는 유효한 메세지를 받거나 null 메시지를 받는다.

Pipe

Pipe는 두 프로세스가 통신할 수 있게하는 전달자로서 동작한다.

Pipe 구현을 위한 이슈 4가지가 존재한다.

• 한 파이프 내의 unidirectional/bidirectional
• 통신에서 half-duplex/full-deplex
  • half-duplex은 한순간에 한 방향 전송만 가능, full-duplex은 동시에 양방향 전송 가능
• 프로세스 간 relationship(parent/child or etc)
• 네트워크 통신의 가능 여부

Ordinary Pipe

일반 Pipe는 두 개의 프로세스가 producer-consumer의 형태를 가진다. Producer는 한 쪽 끝에서 write/read를 진행하고, consumer는 반대 끝에서 read/write를 진행한다.

일반 pipe는 pipe를 생성한 프로세스 이외에는 접근할 수 없다. 따라서 일반적으로 parent process가 fork()로 생성한 child process와 통신하기 위해 사용된다.

Ordinary pipe는 한쪽으로만 데이터를 전송할 수 있으며 오직 단방향 통신만이 가능하다. 따라서 양방향 통신이 필요하다면 두 개의 파이프를 사용해야 한다.

Windows 시스템의 일반 파이프는 익명 파이프라고 불리며 UNIX의 대응되는 파이프와 유사하게 동작한다.

Named Pipe

일반 파이프는 한 쌍의 프로세스가 통신할 수 있는 간단한 기법을 제공한다. 그러나 일반 파이프는 오로지 프로세스들이 서로 통신하는 동안에만 존재한다. UNIX와 Windows 시스템 모두에서 프로세스들이 통신을 마치고 종료하면 일반 파이프는 없어지게 된다.

Named pipe는 양방향으로 가능하며 parent/child 관계 이외에도 사용 가능하다. 지명 파이프가 구축되면 여러 프로세스들이 이를 사용하여 통신할 수 있다. 실제 통상의 시나리오에서 지명 파이프는 다수의 writer를 가진다. 추가로 통신 프로세스가 종료하더라도 지명 파이프는 계속 존재하게 된다.

부가적으로 통신하는 두 프로세스는 동일한 기계 내에 존재해야 한다. 서로 다른 기계에 존재하는 프로세스 사이에 통신이 필요하다면 소켓을 활용해야 한다.

소켓

소켓은 원격 통신을 위한 양종단점(end point)를 뜻한다. 이는 IP 주소(컴퓨터의 식별)와 Port(특정한 프로세스나 서비스가 데이터를 주고받을 수 있는 지점) 번호를 묶어서 식별된다. 두 프로세스가 네트워크 상에서 통신을 하려면 양 프로세스마다 하나씩, 총 두 개의 소켓이 필요하다.

Java에서의 socket 인터페이스

• Socket class: TCP
• DatagramSocket class: UDP
• MulticastSocker class: 다양한 수신자

소켓을 이용한 통신은 분산된 프로세스 간에 널리 사용되고 효율적이지만, low-level이다. 스레드 간에 구조화되지 않은 바이트 스트림만을 통신하기 때문이다. 이러한 원시적인 바이트 스트림 데이터를 구조화하여 해석하는 클라이언트와 서버의 책임이다.

RPC

RPC(Remote Procedure Calls)는 원격지에 있는 함수나 프로시저를 실행할 수 있게하는 프로세스 간 통신이다.

Java에서는 RMI로 구현할 수 있다.

Client는 원격지 host에 있는 함수를 실행하고 싶다.

1. Client의 stub은 파라미터를 marshaling하여 전송한다.
2. Server의 stub이 메세지를 수신하면, marshaling된 데이터를 unpack한다.
3. 프로시져를 수행한다.

마샬링

데이터를 네트워크를 통해 전송 가능한 형태로 변환하는 과정을 말한다.

마샬링은 크게 두 가지 작업을 포함한다.

• 직렬화(Serialization): 데이터를 바이트 스트림으로 변환하는 과정이다. 이는 메모리에 저장된 객체나 데이터를 네트워크를 통해 전송 가능한 형태로 변환하는 작업이다. 직렬화된 데이터는 네트워크를 통해 전송될 수 있고, 이를 통해 원격 프로시저 호출이 이루어진다.

• 데이터 포맷 변환: 서로 다른 시스템 간에 데이터 표현 방식이 다를 수 있다. 마샬링은 데이터를 전송에 적합한 형태로 변환하여 상호 운용성(interoperability)을 확보한다. 예를 들어, 서버는 데이터를 특정 방식으로 표현하고, 클라이언트는 다른 방식으로 표현할 수 있다. 마샬링은 이러한 데이터 형식의 차이를 해결한다.

Model 비교

• 메세지 전달 모델은 충돌을 회피할 필요가 없기 때문에 적은 양의 데이터를 교환하는데 유용하다.
• 메세지 전달 모델은 분산 시스템에서 공유 메모리 모델보다 구현이 쉽다.
• 메세지 전달 모델은 통상 시스템 콜을 사용하여 구현되므로 커널 간섭 등의 부가적인 시간 소비 작업이 필요하기 때문에 공유 메모리 모델이 메시지 전달이 빠르다.
  • 공유 메모리 모델에서는 공유 메모리 영역을 구축할 때만 시스템 콜이 사용되기 때문이다.

스레드

지금까지 프로세스는 싱글 스레드로 실행한다 가정하였다. 문맥 교환 없이 register set 정보를 유지하고 같은 프로그램 안에서 실행 스레드만 달리하여 실행할 수 있다.

스레드는

• CPU 실행의 기본 단위이고
• thread id, program counter, register set, stack을 가진다.

멀티스레드의 장점

• responsiveness: blocking되어 있을 필요없이 non-blocking으로 스레드를 생성하여 실행할 수 있다.
• resource sharing: 스레드는 프로세스의 자원을 공유하므로 IPC 같은 기술이 불필요하다.
• economy: 프로세스 생성보다 값 싸다. thread context switching이 context switching보다 오버헤드가 적다.
• scalability: multiprocessor 아키텍처에서 병렬처리도 가능하다.

프로세스와 스레드의 비교

장점

• 프로세스 그룹보다 리소스 공유가 원활함
• 스레드 컨텍스트 스위칭이 프로세스 컨텍스트 스위칭보다 훨씬 빠름

단점

• 스레드 그룹은 리소스 공유로 인해 하나의 스레드가 오작동을 일으키면 다른 스레드에 영향을 받음
• 서로 다른 시스템에서 실행될 수 없음

Java의 스레드

스레드 생성

• Thread class의 상속: void run() 메서드를 오버라이드한다.
• Runnable interface 구현: void run() 메서드를 오버라이드한다.
• Lambda Expression: Lambda Expression으로 Runnable을 대체한다.

Thread class의 장단점

장점

• 코드 간결성: Thread 클래스를 상속받는 방법은 간단하고 직관적이다. 하위 클래스에서 run() 메서드를 오버라이딩하여 스레드가 수행할 작업을 정의할 수 있다.

단점

• 다중 상속 불가능: Java는 단일 상속만 허용하므로, 다른 클래스를 상속받아야 하는 경우 Runnable 인터페이스를 구현하는 방법이 더 선호된다.

Runnable 인터페이스 장단점

장점

• 다중 상속 가능: 클래스는 여러 인터페이스를 구현할 수 있으므로, 이미 다른 클래스를 상속받고 있는 경우에도 Runnable 인터페이스를 구현하여 스레드 기능을 추가할 수 있다.
• 코드 재사용성: Runnable은 함수형 인터페이스이므로 람다 표현식과 함께 사용할 수 있습니다. 이는 코드의 재사용성을 높일 수 있다.
• 스레드 풀 사용 용이: Runnable을 사용하면 Executor와 같은 인터페이스를 이용하여 스레드 풀에서 쉽게 관리할 수 있다.

단점

• 약간의 추가 작업이 필요: Runnable을 구현하는 방법은 Thread 클래스를 상속받는 방법보다 약간의 추가 작업이 필요할 수 있다.

Thread 대기

thread.join();

Thread 종료

thread.interrupt();

멀티코어 프로그래밍

• single-core: 스레드들이 전 시간에 걸쳐 끼어들어간다. (동시성)
• multi-core: 병렬적으로 실행된다. (병렬성)

Multicore Programming의 challenging

• Indentifying tasks: 여러 개의 task로 나눌 구역을 찾는 것
• Balance: 공정한 일을 나눌 수 있는지에 대한 보장
• Data spliting: 데이터도 core마다 분배되어야 한다
• Data dependency: 실행된 task에서 데이터 의존성 측면에서 동기화가 이루어져야한다.
• Test and debugging: single thread보다 어려움

Amdahl’s law

코어는 많을수록 좋은가?

어떤 시스템을 개선하여 전체 작업 중 P%의 부분에서 S배의 성능이 향상되었을 때 전체 시스템에서 최대 성능 향상은 다음과 같다.

Amdahl’s law에 의해 코어가 많은 것이 항상 좋은 것은 아니다.

Multi-Thread Model

• 사용자 스레드(User Thread): 사용자 모드에서 커널의 지원 없이 직접 생성하거나 이용하는 스레드
• 커널 스레드(Kernel thread): 커널 모드에서 운영체제가 직접 관리하는 스레드

사용자 스레드와 커널 스레드의 관계

사용자 스레드와 커널 스레드의 연관 관계인 다대일, 일대일, 다대다 모델을 살펴보자.

다대일 모델

다대일(Many-to-One) 모델은 하나의 core가 kernel thread에 붙어 있다. kernel thread의 서비스를 받아서 여러 개의 user thread가 context switching이 발생하면서 실행된다.

단점)

• user thread가 수천, 수만개면 하나의 kernel thread로 감당하기 힘들다.
• 다중 코어의 등장으로 하나의 커널 스레드가 담당할 필요가 없다. 즉 다중 처리 코어의 이점을 살릴 수 없다.

일대일 모델

일대일(One-to-One) 모델은 하나의 kernel thread에 하나의 user thread가 실행된다. 다대일 모델보다 더 많은 병렬성을 제공한다.

단점)

• user thread의 개수만큼 kernel thread를 만들어야 하기 때문에 많은 수의 커널 스레드가 시스템 성능에 부담을 줄 수 있다.

다대다 모델

다대다(Many-to-Many) 모델은 여러 개의 kernel thread에 여러 개의 user thread가 실행된다.

단점)

• 구현하기가 까다롭다.
• 기술 발전에 따라 굳이 커널 스레드의 제한이 필요없어졌다.

Java는 초창기에 User thread인 green thread(Many-To-One) 쓰다가 운영체제 쓰레드인 native thread(Many-to-Many)를 사용한다.

Thread Library

• POSIX Pthread
• Windows thread
• Java Thread

Java Thread는 운영체제가 유닉스 계열이면 POSIX Pthread를 이용하고, windows 계열이 Windows thread를 이용한다.

Implicit Threading

개발자에서 컴파일러 및 런타임 라이브러리로 스레드 생성 및 관리를 맡기는 것을 의미한다.

스레드 풀

제한되지 않은 스레드는 CPU 시간 또는 메모리와 같은 시스템 리소스를 소진할 수 있다.

Thread Pools은 시작할 때 미리 여러 개의 스레드를 생성하여 작업을 기다리는 풀에 배치한다.

장점

1. 기존 스레드를 사용하여 요청을 처리하는 것이 스레드 생성을 기다리는 것보다 빠르다.
2. 스레드 풀은 한 지점에 존재하는 스레드의 수를 제한한다. 이는 특히 많은 수의 동시 스레드를 지원할 수 없는 시스템에서 중요하다.
3. 수행할 작업과 작업 생성 메커니즘을 분리하면 작업을 실행하는 데 다른 전략을 사용할 수 있다.

단점

1. 자원 소비: 스레드 풀에 너무 많은 양의 스레드를 만들어둔다면 메모리 낭비가 심해질 수 있다는 점이다.

Java Executor 인터페이스

Executor 인터페이스는 Java에서 스레드 생성 및 관리를 추상화하기 위한 인터페이스이다. 주로 스레드 풀을 관리하고 작업을 비동기적으로 실행하는데 사용된다.

public static void main(String[] args){
    Executor executor = Executors.newFixedThreadPool(3);

    Runnable runnable = () -> {
        System.out.println("Hello from Runnable");
    };

    executor.execute(runnable);
}

newSingleThreadExecutor()

• 특징: 크기가 1인 스레드 풀을 생성한다.
• 용도: 작업을 순차적으로 실행하거나, 한 번에 하나의 작업만을 처리해야 할 때 유용하다.
• 장점: 작업 큐에 들어온 순서대로 실행되며, 순차적으로 처리되기 때문에 예측 가능한 동작을 보장한다.
• 단점: 단일 스레드이기 때문에 병렬성을 활용할 수 없다. 작업을 처리하는 속도에 따라 큐에 쌓일 수 있으므로, 작업이 길게 걸리는 경우 효율성이 떨어질 수 있다.

newFixedThreadPool(nThread)

• 특징: 크기가 고정된 스레드 풀을 생성한다. 풀에는 지정된 개수(nThread)의 스레드가 유지된다.
• 용도: 동시에 여러 작업을 병렬로 처리해야 할 때 사용한다.
• 장점: 풀에 유지되는 스레드의 개수가 고정되어 있어서, 너무 많은 스레드가 생성되어 시스템 부하를 일으키는 것을 방지한다.
• 단점: 스레드 개수가 고정되어 있기 때문에 작업 부하가 증가하면 성능에 영향을 미칠 수 있다.

newCachedThreadPool()

• 특징: 필요에 따라 스레드를 동적으로 생성하고, 불필요한 스레드를 제거하여 크기가 자동으로 조절되는 스레드 풀을 생성한다.
• 용도: 각 작업이 짧은 시간 동안 수행되는 경우나, 작업 부하가 변동적인 경우에 유용하다.
• 장점: 풀에는 필요한 만큼의 스레드가 생성되기 때문에 자원의 효율성을 높일 수 있습니다.
• 단점: 스레드의 동적 생성 및 해제로 인해 오버헤드가 발생할 수 있다. 스레드 개수를 제한하지 않기 때문에 너무 많은 스레드가 생성되어 시스템에 부하를 줄 수 있다.

newWorkStealingPool()

• 특징: Java 8에서 도입된 ForkJoinPool을 사용하여 작업을 분할하고 여러 프로세서에서 병렬로 실행할 수 있는 스레드 풀을 생성한다.
• 용도: 작업을 작은 단위로 분할하고, 여러 코어에서 효율적으로 실행할 때 사용한다. 병렬성이 높은 작업을 작은 단위로 분할하고 병렬로 실행하는데 적합하다. 특히 각 작업이 서로 독립적이고, 작은 단위로 쪼개어 병렬로 실행될 수 있는 경우에 유리하다. newWorkStealingPool()은 다중 코어 또는 프로세서 시스템에서 효과적으로 작동한다. 각각의 프로세서가 자신의 큐에서 작업을 처리하면서 효율적으로 병렬성을 높일 수 있다. 대용량의 작업을 작은 단위로 나누어 각각을 병렬로 처리하고자 할 때 적합하다. 예를 들어, 대규모 데이터 처리 또는 재귀적인 작업 등이 이에 해당할 수 있다.
• 장점: ForkJoinPool은 워크 스틸링(work-stealing) 알고리즘을 사용하여 각 프로세서가 할당된 큐에서 작업을 훔치는 방식으로 병렬 처리를 수행한다.
• 단점: 일부 특수한 경우에는 다른 스레드 풀보다 높은 오버헤드가 발생할 수 있다. 특별한 작업 유형에 대한 최적화가 아닌 경우에는 다른 풀보다 복잡할 수 있다.

ForkJoinPool은 워크 스틸링(Work-Stealing) 알고리즘을 기반으로 동작된다. 각 워커 스레드는 자신의 작업이 끝날 때 다른 워커 스레드의 큐에서 작업을 훔쳐올 수 있다. 이를 통해 작업이 균형 있게 분배되고, 부하가 고르게 분산된다. ForkJoinPool은 작업을 작은 단위로 분할하고, 분할된 작업을 병렬로 실행하여 다중 코어를 활용한다. 큰 작업을 여러 작은 작업으로 나누어 각각을 병렬로 실행함으로써 성능을 향상시킬 수 있다.

OpenMP

OpenMP(Open Multi-Processing)는 공유 메모리 다중 처리를 위한 API(응용 프로그래밍 인터페이스)로, 병렬 컴퓨팅을 쉽게 활용할 수 있도록 도와주는 표준이다.

CPU 스케줄링

Multiprogramming의 목적은 1)프로세스의 실행을 동시성을 띄게하기 위해서와 2)CPU의 이용을 최대화하기 위함이다.

프로세스의 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다.

• CPU bound process: CPU burst가 큰 프로세스
• I/O bound process: I/O burst가 큰 프로세스

Histogram에서 I/O bound process가 빈도가 높은 것을 알 수 있다. 컴퓨터 시스템 내에서 수행되는 프로세스의 CPU 버스트를 분석해보면 대부분의 경우 짧은 CPU 버스트를 가지며, 극히 일부분만 긴 CPU 버스트를 갖는다. 이는 다시 말해서 CPU를 한 번에 오래 사용하기보다는 잠깐 사용하고 I/O 작업을 수행하는 프로세스가 많다는 것이다.

즉 사용자에 대한 빠른 응답을 위해서는 I/O bound process에게 우선적으로 CPU를 할당하는 것이 바람직하다. 만약 CPU bound process에게 먼저 CPU를 할당한다면 그 프로세스가 CPU를 다 사용할 때까지 많은 I/O bound process는 기다려야할 것이다.

이러한 이유로 CPU Scheduling 실행되어야 하는 우선순위를 조절하여 CPU 효율을 높일 수 있다.

CPU 스케줄러

CPU Scheduler는 Ready 상태이면서 실행 가능한 프로세스에게 CPU를 할당한다.

선점 vs 비선점

• 선점(Preemptive): 스케줄러가 CPU를 선점하고 있는 프로세스를 교체할 수 있다.
• 비선점(Non-preemptive): 현재 프로세스가 스스로 종료하거나 Wait 상태가 될 때까지, 계속 CPU를 유지한다.

Dispatcher

Dispatcher는 CPU Scheduler에 의해 선택된 프로세스에데 CPU core의 제어권을 넘겨주는 것이다.

기능

• 다른 프로세스로 context switching이 발생
• user mode로 변환
• user program을 재게하기 위해 적절한 location으로 jump

CPU Scheduler가 선택만 할 뿐, Dispatcher가 실제로 switching한다.

Dispatch latency

Dispatcher는 모든 프로세스의 Context Switching 시 호출되므로, 가능한 한 빠르게 수행되어야 한다. Dispatcher가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데 소요되는 시간을 Dispatch latency라 한다.

스케줄러의 성능 기준

• CPU 이용률(CPU Utilization): 가능한 한 CPU를 최대한 바쁘게 이용
• 처리량(Throughput): 단위 시간 당 완료한 프로세스 수
• 총처리 시간(Turnaround time): 프로세스 입장에서 프로세스를 실행하는데 걸리는 시간.
  • 총처리 시간 = 준비 큐 대기 시간 + CPU 실행 시간 + I/O 시간
• 대기 시간(Waiting time): 스케줄링 알고리즘은 프로세스가 Ready Queue에 대기하는 시간의 양에 영향을 미침
• 응답 시간(response time): 응답이 시작되는 데까지 걸리는 시간

FCFS 스케줄링

FCFS(First-Come, First-Served) 스케줄링은 CPU를 먼저 요청한 프로세스에게 순서대로 CPU를 할당한다.

• FIFO Queue로 구현할 수 있다.
• 비선점(non-preemptive)이다.
• CPU-burst time에 따라 waiting time이 길어진다.
• Convoy Effect 발생.

호위 효과

호위 효과(Convoy Effect)는 CPU 사용시간이 긴 프로세스에 의해 사용시간이 짧은 프로세스들이 오래 기다리는 현상이다. 이 효과는 짧은 프로세스들이 먼저 처리되도록 허용될 때보다 CPU와 장치 이용률이 저하되는 결과를 낳는다.

SJF(Short Job First) 스케줄링

SJF(Short Job First) 스케줄링은 CPU Burst time이 가장 작은 프로세스에 CPU를 할당한다. 만약 Burst time이 같을 경우, 먼저 요청한 프로세스(FCFS 스케줄링)에게 할당한다.

• 주어진 프로세스 집합에 대해 최소의 평균대기 시간(Minimal Waiting time)을 가진다는 점에서 최적이다.
• 다음 프로세스의 CPU burst time을 정확히 구하는 것은 불가능하기 때문에 구현이 불가능하다.
• 선점형이거 비선점형일 수 있다.

SRTF 스케줄링

Ready 상태로 도착한 프로세스가 현재 running 프로세스의 잔여시간보다 작으면 선점한다.

• 선점(preemptive)이다.

라운드 로빈(Round-Robin) 스케줄링

• Time Quantum(time slice)을 가진 선점(preemptive) FCFS이다.
• Ready Queue를 원형 Queue로 구현한다.

1. Time Quantum이 끝나기 전에 프로세스가 종료하면 다음 프로세스를 진행한다.
2. CPU burst가 time Quantum보다 클 경우, timer interrupt가 발생하고 context switching이 실행된다.

Time Quantum(Time Slice)

Time Quantum을 길게 설정하면 context switching이 적게 발생하지만, FCFS와 비슷한 Scheduling이 된다. Time Quantum을 짧게 설정하면 context swiching이 많이 발생하고, dispatch latency가 계속 발생한다.

우선순위(Priority-base) 스케줄링

우선순위가 높은 프로세스에게 CPU를 할당하고, 우선순위가 같을 경우 FCFS로 작동한다.

기아 상태

기아 상태(Starvation)는 실행 준비는 되어 있어 우선순위가 Ready Queue에 존재하는 낮은 프로세스가 우선순위가 높은 프로세스가 계속 Ready Queue에 삽입되면 무한정 대기하게 되는 현상이다.

Aging

오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.

Multi-Level Queue(MLQ) 스케줄링

우선순위와 라운드 로빈 스케줄링을 사용할 때 모든 프로세스가 단일 큐에 배치되고 스케줄러는 우선순위가 가장 높은 프로세스를 선택하여 실행시킨다. 방식에 따라 우선순위가 가장 높은 프로세스를 결정하기 위해 O(n) 검색이 필요할 수 있다.

우선순위마다 별도의 큐를 갖게하는 것이 더 쉬울 수 있다. 해당 방식은 아래와 같다.

Multi-Level Queue(MLQ) 스케줄링은 우선순위 스케줄링이 특정한 큐의 스케줄링 정책(RR, SJF, ..)과 결합한 형태이다.

또한 큐와 큐 사이에도 스케줄링 알고리즘이 있어야 하며, 일반적으로 고정 우선순위의 선점형 알고리즘으로 구현된다.

Multilevel Feedback Queue(MLFQ) Scheduling

MLQ 스케줄링은 고정적으로 우선순위를 가지고 있다. 따라서 프로세스들은 한 큐에서 다른 큐로 이동하지 않는다. 이 때문에 낮은 우선순위의 Queue에 있는 프로세스는 무한정 대기하게 된다.

프로세스들은 CPU 버스트 성격에 따라서 구분한다. 어떤 프로세스가 CPU 시간을 많이 사용하면, 낮은 우선순위의 큐로 이동된다. 이 방법에서는 I/O 중심의 프로세스와 대화형 프로세스들을 짧은 CPU 시간을 갖기오 높은 우선순위로 배치된다.

낮은 우선순위의 큐에서 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다. 이를 통해 기아 현상을 방지한다.

스레드 스케줄링

Kernel thread는 user thread를 매핑만 해준 뿐이지, 동작 과정은 관여 안하므로 Thread Scheduling은 kernel thread에 대해서만 진행된다.

동기화

동시성, 병렬성 프로그래밍에서 데이터를 공유하면, 데이터가 일관성을 잃는 것을 유의해야 한다.

실행 순서를 제어해야 한다.

생산자-소비자 문제

데이터를 공유하고, 생산자와 소비자 비동기적으로 실행한다고 가정하자.

• 생산자: item을 버퍼에 추가해 증가시킨다. count++
• 소비자: item을 제거해 버퍼에서 꺼내온다. count--

실제로는 count++, count-- 위와 같이 instruction이 섞여 작동하여서 원하는 결과를 얻을 수 없다.

Race Condition

**두 개 이상의 프로세스(스레드)**가 데이터를 공유하는데, 이를 동시에 접근할 때 실행의 결과는 특정 순서에 의해 결과가 달라지는 현상이다.

• 프로세스(스레드) 동기화: Race Condition을 막기 위해서 데이터 엑세스를 한 프로세스가 할 수 있도록 한다.

Critical Section

프로세스들이 코드의 특정 영역에서 데이터를 공유한다면, 그 코드의 영역을 Critical Section이라 한다.

Critical Section 영역에서 하나의 프로세스가 접근하면, 나머지 프로세스는 접근하지 못하게 하게 만들기 위해

• entry-section: Critical Section에 들어갈 수 있는 권한을 요청하는 코드 영역
• exit-section: 빠져나오는 영역
• remainder-section: 남은 코드 영역

while (true) {
	// entry section
		critical section
	// exit section
		remainder section

해결법(요구사항)

Critical Section을 해결하기 위해서는 다음 세 가지 요구 조건을 충족해야 한다.

• Mutual Exclusion(상호배제): Critical Section에 하나의 프로세스가 진입하면, 다른 프로세스는 접근할 수 없다.
• Progress(진행): 실행중인 프로세스가 없고 진행할 다음 프로세스가 존재하면, 그 프로세스는 Critical Section에 진입할 수 있어야 한다.
• Bounded Waiting(대기): 한 번 Critical Section에 들어간 프로세스는 한정(bound)을 두어 다른 프로세스도 해당 임계 영역을 수행할 수 있도록 해야한다.

위 요구사항을 모두 만족해야 Critical Section이 해결되었다고 할 수 있다.

Interrupt를 막으면?

단일 코어 환경에서는 공유 변수를 수정하는 동안 인터럽트가 발생하는 것을 막으면 critical section 문제는 간단히 해결된다.

즉, 현재 실행 중인 명령어들은 선점 없이 순서대로 실행될 수 있다.

→ 인터럽트를 막았으므로 context switching이 발생하지 않는다.

근데 이 방법은 멀티 코어 환경에서는 불가능하다. 인터럽트가 발생하는 것을 막으려고 메시지 전달을 모든 코어에 하는 것은 시간이 많이 걸린다.

소프트웨어적 알고리즘

Perterson’s Algorithm

두 프로세스가 임계구역과 나머지 구역을 번갈아가며 실행하는 상황을 가정

int turn;
boolean flag[2];

while(true) {
	flag[i]=true;
	turn=j; # 턴을 j에게 넘겨 줌
	while (flag[j] && turn==j) # 만약 턴이 j이거나 flag[j]=true이면 대
		;
		/* critical section */
	flag[i] = flase;
		/* remainder section */
}

그럼 이 알고리즘이 임계구역 문제 조건을 만족하는가?

1. Mutual exclusion(상호 배제)

   프로세스 $P_i$가 임계구역에 들어갈 시점에 turn==i이거나 flag[j]=false이어야 한다. turn 변수의 값은 0이든지 1이든지 둘 중 하나여야 하므로 성공적으로 while문을 통과하는 것은 한 프로세스 뿐이다. 따라서, 상호 배제는 지켜진다.

2. 데드락/기아 현상이 발생하는가?

   $P_i$가 while문을 실행하고 나오면 flag[i]=false로 두며, $P_j$가 while문을 빠져나오도록 해준다. 이 때, $P_j$는 while 문 내에서 turn 값을 바꾸지는 않기 때문에 $P_i$가 while문 실행 전에 turn=j로 바꾸는 과정에서 while문에 진입하게 된다. 이는 $P_j$가 임계구역을 실행하도록 보장을 해준다.

근데, flag 변수와 turn 변수의 경우 서로 데이터 종속성이 없으므로 프로세스가 flag 변수에 true값을 넣기 전에 turn 변수를 바꿀 수 있다.

→ load/store 구조의 경우 보장되지 않는다.

하지만! 알고리즘적으로는 증명이 가능하다

상위 소프트웨어 도구

Mutex Lock

Mutex lock이란 Critical section을 보호하고 race condition을 예방하기 위해 Critical section에 진입하면 lock을 획득하고 빠져나갈 때 lock을 반환한다.

• acquire()와 release()를 통해 atomically하게 실행된다.

Busy Waiting

다른 프로세스가 critical section에 접근하기 위해 acquire() 함수를 호출하는 반복문을 실행하게 된다. 이는 다른 프로세스가 생산적으로 사용할 수 잇는 CPU cycle의 낭비로 이어진다.

Spinlock

Mutex lock이 busy waiting하는 현상을 Spinlock이라 지칭한다. Spinlock이라고 다르게 칭하는 이유는 mutex가 loop를 실행하는 현상이 여러 개의 cpu core에서 유용할 때가 있다.

장점)

• Spinlock이 Waiting Queue에 진입하는 방법보다 더 빠르다. (Ready Queue에 다른 프로세스를 기다려야하기 때문에)
• context switching까지의 소요 시간이 감소한다.

Semaphore

Semaphore는 정수 값을 통해 wait(), signal()을 통해 제어하는 방법이다. wait()와 signal() 연산 시 Semaphore의 정수 값을 변경하는 연산은 반드시 원자적으로 수행되어야 한다. 즉, 한 스레드가 Semaphore 값을 변경하면 다른 어떤 스레드도 동시에 동일한 Semaphore 값을 변경할 수 없다.

wait()은 원자적인 연산이기에 Semaphore는 critical section 내에서 race condition이 발생하지 않는다.

Binary Semaphore

n=1일 경우, mutex lock과 비슷하다. 몇몇 시스템에 mutex lock을 제공하지 않고 상호 배제를 보장하기 위해서 이진 Semaphore를 대신 사용한다.

Counting Semaphore

• wait(), P(): 프로세스가 리소스를 사용할 때, count를 감소시킨다.
• signal(), V(): 프로세스가 리소스를 해제할 때, count를 증가시킨다.
• 0일 경우, 모든 리소스가 사용되는 상태이기에 프로세스는 block된다.

Busy Waiting

Busy Waiting을 해결하기 위해 P(), V() 연산의 정의를 수정한다.

• wait(), P(): 만약 semaphore가 양수가 아니면 대기해야 하므로, Waiting Queue로 옮겨진다.
• signal(), V(): Waiting Queue에 있는 프로세스를 Ready Queue로 옮긴다.

문제점

Semaphore는 동기화를 위해 편리하고 효과적이지만, timing error가 발생할 수 있다.

• signal(mutex) -> wait(mutex) 순서로 호출한 경우
• wait(mutex) -> wait(mutex) 또는 signal(mutex) -> signal(mutex) 순서로 호출한 경우
• wait(mutex) 또는 signal(mutex) 호출을 한개 또는 둘다 생략하는 경우

이 때문에 고수준의 동시화 툴이 필요해졌다.

Monitor

심플한 동기화 툴이면서 에러가 잘 발생하지 않는 Monitor를 사용할 수 있다. 즉, Monitor는 고수준의 동기화 구조체이다. 추상 데이터 타입으로 상호 배제를 지원하는 데이터 타입으로 이해할 수 있다.

Monitor를 선언하고 monitor block 내부의 함수가 동기화된 함수로 사용할 수 있다.

Shared data와 Initialize code 동기화 되는 함수를 Monitor라는 자료구조로 묶는다. Monitor에 정의된 자료구조를 사용한 스레드는 entry queue라는 대기 큐로 관리된다.

Conditional Variable

Monitor가 자체적으로 동기화 문제를 해결하기에는 부족하다. 동기화 메커니즘을 제공하는 condition 변수를 추가한다. condition variable을 통해 lock을 걸 수 있다.

위 그림에서 condition variable x, y에 대하여 entry queue가 분리된다. Operation들이 각각의 condition variable에 대해 초기화되고 동기화된다. x, y가 호출될 수 있는 연산은 오직 wait()과 signal() 뿐이다.

Java Monitor

Java에서는 스레드 동기화의 동시성 메커니즘을 위해 monitor-lock 또는 intrinsic-lock을 제공한다.

thread concurrency를 위한 것을 기억하자.

자바의 모든 객체는 락(lock)을 갖고 있다. 모든 객체가 갖고 있으니 고유 락(intrinsic lock)이라고도 하는 것이다.

synchronized

synchronized는 Critical Section에 해당하는 코드 블럭을 선언할 때 사용하는 자바 키워드이다.

해당 코드 블럭에는 monitor lock을 획득해야 진입 가능하다. monitor lock을 가진 객체 인스턴스를 지정할 수 있다.

메서드에 선언하면 메서드 코드 블럭 자체가 임계영역으로 지정된다.

• 이때 monitor lock을 가진 객체 인스턴스는 this 객체 인스턴스이다.

synchronized (object) {
    // critical section
}

public synchronized void add() {
    // critical section
}

wait() and notify()

synchronized로 동기화해서 공유 데이터를 보호하는 것 까지는 좋은데, 특정 쓰레드가 객체의 락을 오랜 시간 보내지 않도록 하는 것도 중요하다.

java.lang.Object에 선언되어 있어, 모든 Java 객체가 가진 메서드이다.

• wait(): 갖고 있던 고유 lock을 반납하고, 스레드를 잠들게 한다.
• notify(): 객체 monitor에 대기 중인 스레드 하나를 깨운다.
• notifyAll(): 객체 monitor에 대기중인 스레드를 전부 깨운다.

위 기법들은 상호 배제를 위한 것이고, progress와 bounded-waiting을 위한 해결법은 Liveness가 존재한다.

Deadlock

데드락이란 대기 중인 스레드가 요청한 자원들이 다른 스레드에 의해 점유되어 있고, 그들도 전부 대기 상태에 있기 때문에 상태를 바꾸지 못하는 상태이다.

발생 조건

모든 조건이 만족해야 Deadlock이 발생할 수도 있다.

• 상호배제(Mutual Exclusion): 최소한 하나의 자원이 배타적으로(즉, 한 번에 하나의 프로세스 또는 스레드만 접근 가능하게) 사용될 수 있어야 합니다.
• 점유 대기(Hold and Wait): 스레드는 최소한 하나의 자원을 보유한 상태에서 다른 자원을 얻기 위해 대기합니다.
• 비선점(non-preemption): 선점할 수가 없어 자원을 계속 유지한다.
• 원형 대기(circular wait): Waiting 스레드의 집합이 원형 그래프 형태로 의존성을 갖는다.

RAG(Resource Allocation Graph)

Deadlock은 시스템 자원 할당 그래프라고 하는 방향 그래프로 더욱 정확하게 기술할 수 있다. RAG에서 만약 싸이클이 존재하지 않으면, 시스템은 Deadlock 상태가 아니다.

RAG에서 만약 싸이클이 존재하면, 시스템은 Deadlock이 존재할 수도, 아닐 수도 있다.

Deadlock 예방

Deadlock의 발생 4가지 조건 중 하나가 발생하지 않는다고 보장하면, Deadlock을 예방할 수 있다.

상호배제

• 모든 자원이 공유가능하면 된다. 읽기-전용 파일 같은 경우에 가능하다.
• 현실적으로 불가능하다. 어떤 자원들은 근본적으로 공유가 불가능하기 때문이다.
• mutex lock은 여러 스레드에 의해 공유될 수 없다.

점유 대기

• 스레드가 자원을 요청하면, 점유하고 있는 자원이 없어야 한다.
• 대부분의 응용 프로그램에서 실용적이지 않다.
• 자원이 할당되었지만 장기간 사용되지 않을 수 있다.
  • 스레드 전체 실행 기간 동안 mutex lock이 할당될 수 있지만, 사용 시간을 매우 짧을 수 있다.
• 기아가 발생할 수 있다.

비선점

• 선점으로만 유지한다.
• 교착 상태가 자주 발생하는 자원 유형인 mutex lock과 세마포어에 적용할 수 없다.

원형 대기

• 그나마 실용적이다.
• 자원 타입에 순서를 부여하여, 스레드가 자원을 요청하면 점유하고 있는 자원의 번호보다 높은 번호만을 요청할 수 있게 한다.
• Circular-wait가 존재하지 않는걸 증명할 수 있다.
• Starvation이 발생할 수도 있다.

Deadlock 회피

요청마다 스레드의 요청이 미래에 데드락이 가능할 것 같으면 요청을 기다리게 하는 방식으로 회피한다.

Safe State

어떤 자원을 각 스레드에 최대까지 특정 순서로 할당해줄 수 있는 데드락이 발생하지 않는 상태이다.

Safe Sequence가 존재한다면, 시스템은 Safe state에 있다.

Safe State에만 머무르도록 하여 확실히 Deadlock을 회피한다.

과정

이전 state는 safe state라 가정한다.

1. 스레드에 대한 요청이 들어온다.
2. 스레드가 시스템 Deadlock-Avoid 커널에 Claim-Edge를 제공한다.
3. RAG로 Cycle-detection을 통해 cycle을 검사한다.
4. Cycle이 없을 경우 safe로 판단하여 Grant를 반환한다.
5. Cycle이 있을 경우 unsafe로 판단하여 Non-Grant를 반환한다.
6. Grant일 경우, 요청을 실행한다.
7. Grant하지 못할 경우, wait한다.

시스템은 safe state를 유지하기 위해 자원을 할당할 것인지, 안할 것인지 결정한다.

Banker’s Algorithm

RAG는 3개 이상의 인스턴스 타입에 적용할 수 없다.

• n: 스레드의 개수
• m: 자원의 타입 개수
• Available: 가능한 자원 타입의 개수의 백터
• Max: 각 스레드가 요청할 수 있는 인스턴스의 최대 개수의 행렬
• Allocation: 각 스레드에 현재 할당된 자원 타입의 개수의 행렬
• Need: 각 스레드의 앞으로 요청할 자원 행렬

과정은 생략.

Deadlock Detect

데드락 avoid & prevent를 하지 않는다면 다음 알고리즘들을 지원해야 한다.

• 데드락이 발생했는지 시스템의 상태를 검사하는 알고리즘
• 데드락을 회복하는 알고리즘

1. 각 자원 유형이 한 개씩 있는 경우(Single Instance of Each Resource Type)

모든 자원이 한 개의 인스턴스만 있다면, 대기 그래프(wait-for graph)를 통해 데드락 탐지 알고리즘을 정의할 수 있다. 대기 그래프: RAG에서 자원 노드를 제거하고 간선을 적절히 결합한다.

$T_i → T_j$: 스레드 $T_i$가 스레드 $T_j$의 자원이 방출되기를 기다린다

Wait-for graph에서 사이클이 존재할 경우 데드락이 발생한다.

시스템은 wait-for graph를 유지하며 주기적으로 알고리즘을 호출한다.

시간 복잡도는 O(n^2)이다.

1. 각 유형의 자원을 여러 개 가진 경우

종류마다 자원이 여러 개씩 존재하는 상황

→ Banker’s Algorithm과 같이 자료구조를 사용해야 함

• Available: 현재 가용한 자원의 개수를 나타내는 벡터, 크기가 m
• Allocation: 각 스레드에 현재 할당된 자원의 개수를 나타내는 행렬

크기는 n x m

• Request: 각 스레드가 현재 요청 중인 자원의 개수를 나타내는 행렬

크기는 n x m Request[i][j]==k이면 현재 $T_i$가 $R_j$를 k개 요청 중임을 뜻한다.

Banker’s Algorithm과 거의 동일하다.

Deadlock Recover

프로세스/스레드 중지

프로세스 또는 스레드를 중지시킴으로써 교착 상태를 제거하기 위해 두 방법 중 하나를 택해야 한다.

• 데드락 상태 프로세스 모두 중지: 확실하게 데드락 상태의 사이클을 깨뜨리지만, 비용이 크다.
• 데드락이 해결될때까지 하나씩 중지: 프로세스를 중지할 때마다 데드락 탐지 알고리즘을 호출해 데드락 상태인지 확인한다. 하나씩 중지시키고 알고리즘을 호출해야하기 때문에 오버헤드가 엄청나다.

프로세스 종료 자체도 어려운 일이다. 프로세스가 파일을 갱신하는 도중이었다면, 그 중간에 종료시키면 파일이 부정확한 상태가 된다.

자원 선점

자원 선점을 통해 데드락을 제거하려면, 데드락 상태가 깨질 때까지 계속 자원을 선점해 다른 프로세스에게 주어야 한다. 자원 선점을 하기 위해 아래 세 가지를 고려해야 한다.

• 희생자 선택: 비용을 최소화할 수 있게, 어느 자원과 어느 프로세스가 선점될 것인지 결정한다.
• 롤백: 필요 자원이 부족하면 안전한 상태로 롤백한다.
• 기아 상태: 희생자를 선택하여 기아 상태에 한정된 시간 만큼만 빠지게 한다.

Main Memory

프로그램이 실행되었다는 뜻은 프로그램의 instruction set이 메모리에 로드된 상태인 것이다.

CPU는 메모리에서 instruction을 fetch해서 program counter가 지정하는 instruction을 실행한다. 실행하는 과정에서 instruction은 load, store 과정을 거친다.

Memory Space

각 프로세스가 분리된 메모리를 가질 수 있게 보장해야한다.

base register와 limit register를 통해 legal한 프로세스의 영역을 결정한다.

User mode에서 생성된 register를 매번 검사하여 base register <= address <= base+limit register일 경우 접근을 허용한다.

Address Binding

• Compiler: symbolic address to relocatable address
• Linker or Loader: relocatable address to logical address
• Runtime: logical address to physical address

MMU(Memory Management Unit)

• logical address: CPU에 의해 생성되 주소
• physical address: Memory 관점에서 본 주소
• logical address space: 모든 logical address의 집합
• physical address space: 모든 physical address의 집합

H/W적으로 logical address를 physical address로 변환을 가능하게 해준다.

346번지를 요청하면 relocation register인 14000번지를 참조하여 physical address인 14346번지로 변환한다.

Dynamic Loading

Memory 공간을 효율적으로 사용하기 위해 모든 routine을 한 번에 업로드할 필요가 없다. 즉 필요할 때 마다, routine이 로딩된다.

Dynamic Linking

• DLL(Dynamic Linked Library): 프로그램 실행 중에, 시스템 라이브러리가 user 프로그램에 링킹됨
• dynamic linking: 실행 시까지 linking 작업을 연기한다.

연속 메모리 할당

프로세스를 연속적으로 특정 메모리 섹션에 업로드한다.

hole: 프로세스를 적재할 수 있는 메모리 공간

size가 n인 요청을 어떻게 할당할 것인가?

• First-Fit: 넣을 수 있는 첫 hole에 적재한다.
• Best-Fit: 가장 작은 hole을 비교해 프로세스를 적재한다.
• Worst-Fit: 가장 큰 hole에 프로세스를 적재한다.

Fragmentation

External Fragmentation

연속 메모리 할당에서 hole에 메모리를 삽입 후 남는 메모리 공간을 의미한다. 큰 프로세스나 데이터 구조를 할당하기에 충분한 연속적인 메모리 공간이 부족한 상태를 나타낸다.

Internal Fragmentation

Paging을 통해 고정 크기의 단위로 데이터를 저장하는 경우에 발생한다. 남은 공간이 작은 조각들로 나누어져 데이터를 저장하지 못하게 된다.

Segmentation

라이브러리 함수, stack 영역, 메인 함수 영역, 힙 영역 등 메모리를 서로 다른 크기의 논리적인 세그먼트(부분)로 나누고 메모리에 저장하는 방식이다.

분리하면 가변 크기를 갖게 되어 내부 단편화를 완화할 수 있지만, 외부 단편화 문제는 여전히 발생할 수 있습니다.

Paging

프로세스의 물리 메모리 주소를 불연속적으로 저장할 수 있게하는 기법이다.

연속 메모리 할당의 두 가지 문제점을 완화한다.

• 외부 단편화 문제
• hole compaction의 필요성

OS와 컴퓨터 하드웨어를 통해 구현된다.

Basic Method

Physical Memory를 고정된 사이즈 블럭(Frame)으로 쪼갠다. 이를 Logical Memory를 쪼갠 단위인 Pages와 매핑한다.

이를 통해 Logical Address가 Physical address space와 완전히 분리된다.

CPU에 의해 주소가 생성되면, 두 가지 부분으로 분리된다.

• p: page number
• d: page offset

physical address = (page number) * (page size) + (page offset)

Page table

Page number가 process마다 다르므로 따로 page table에서 관리해야한다.

1. CPU가 생성되면 page number와 offset이 정해진다.
2. page table을 통해 page number를 실제 physical memory의 frame number로 변환한다.
3. frame number와 page offset을 통해 엑세스하고자 하는 물리 주소로 접근한다.

메인 메모리에 위치한다.

TLB(Transfer Look-aside Buffer)

Context Switching이 발생하면, page table도 reload 되어야 한다. 또한 메모리의 접근이 두 번 해야 한다는 단점이 존재한다.

• page table entry
• actual data

메모리 접근을 줄이기 위해 작고 빠른 캐시 역할의 TLB를 둔다.

한 명령어 사이클 안에서 메모리 탐색이 되기 때문에 빠른 것이다.

• TLB hit: page number가 TLB에 존재
• TLB miss: page number가 TLB에 없음
• hit ratio: TLB hit의 발생 빈도

1. Logical address를 physical address로 변환하기 위해 TLB에 접근한다.
2. TLB hit 시, page number를 frame number로 변환하여 actual data에 접근한다.
3. TLB miss 시, 메모리의 page table에 접근하여 frame number를 변화하고 다시 actual data에 접근한다.

Memory Protection

valid-invalid bit: 각 frame 별로 protection bit를 통해 구현된다.

Shared Page

Paging을 통해 공통되는 코드를 공유할 수 있다.

C library code 같은 경우, 변경될 일이 없어 공유 페이지로 설정하면 효율적이다.

각 프로세스가 libc 1, … libc 4까지 따로 갖고 있는 것처럼 보이지만, 각 프로세스의 page table entry가 같고 실제 물리 메모리에서는 단 한번만 저장되고 이용되는 것을 확인할 수 있다.

Page Table의 구조

Page Table이 너무 커져, Page table의 구조를 여러 가지 방식으로 고려해 볼 수 있다.

Hierarchical Paging

Page Table에 대한 여러 Page table을 가지게 한다.

Hashed Page Tables

Inverted Page Tables

pid를 통해 어떤 프로세스가 무슨 page를 가지고 있는지를 저장하는 방식이다.

Swapping

메모리가 부족한 상황에서 백그라운드에서 실행 중인 프로세스를 메인 메모리에서 디스크로 옮기는 작업이다.

• Swap out: 메인 메모리에 있는 프로세스 전체를 하드디스크로 보낸다.
• Swap in: 하드디스크에 있는 프로세스를 메인 메모리로 가져온다.

Swapping with Paging

전체 프로세스를 Swapping하는 것은 비효율적인다.

• Page out: 메인 메모리에 있는 page를 하드디스크로 보낸다.
• Page in: 하드디스크에 있는 page를 메인 메모리로 가져온다.

Virtual Memory

physical memory보다 더 큰 프로그램을 실행해야된다. Logical memory와 physical memory를 분리함으로써 main memory를 굉장히 큰 스토리지로 생각할 수 있다.

또한 다음과 같이 shared page를 통해 shared memory를 구현하여 프로세스 간 통신을 구현할 수 있다.

Demanding Paging

하드디스크의 전체 프로그램을 로딩하는 것은 비효율적이다. Demanding Paging은 page가 필요할 때, 로딩될 수 있게하는 기법이다.

Basic concept

프로세스가 실행 중일 때, 몇 개의 page는 메모리에 있고 몇 개의 page는 하드디스크에 있을 것이다.

두 가지 경우를 구별하기 위해, valid-invalid bit의 개념을 활용할 수 있다.

• valid: page가 legal하고 메모리에 있다.
• invalid: valid하지 않거나 하드디스크에 존재한다.

logical memory에서 page table에 접근했는데 메모리에 존재하지 않을 경우, page fault가 발생한다.

Page fault

1. Logical memory에서 page table에 접근했는데 invalid bit이다.
2. Valid하지만 page fault일 경우, page in을 진행한다.
3. Free frame을 탐색한다.
4. 하드디스크로부터 필요한 page를 읽어와서 새로운 frame에 할당한다.
5. 하드디스크로부터 읽기가 끝나면, page table의 정보(bit …)를 갱신한다.
6. Instruction을 재게한다.

참조 지역성

참조 지역성은 캐시 메모리의 효율성을 향상시키는 데 중요한 역할을 한다. 캐시 메모리는 주 메모리보다 빠르지만 제한된 용량을 가지고 있으며, 데이터를 캐시로 가져오는 데 시간이 소요된다. 따라서 참조 지역성이 높은 프로그램은 캐시 히트율을 높이고 성능을 향상시킬 수 있다.

• 시간 지역성(Temporal Locality): 특정 데이터나 명령어가 최근에 액세스되면 가까운 미래에 다시 액세스될 가능성이 높다는 개념

• 공간 지역성(Spatial Locality): 특정 데이터나 명령어에 액세스하면 주변의 데이터나 명령어에도 액세스할 가능성이 높다는 개념

Copy-on-Write

Write시에 공유 페이지를 복사하는 전략이다.

fork()시에 child 프로세스는 다른 메모리에 복사된다고 했다. 하지만 read 연산만 이루어질 경우, 굳이 나눌 필요가 있지 않다. 따라서 Figure 10.8과 같이 read시에는 parent, child process는 같은 페이지를 공유한다. 수정(write)이 발생하면, 그때 페이지가 복사가 되고 나서 해당 작업을 실행된다.

Page Replacement Algorithm

만약 free frame이 존재하지 않으면?

1. B에 page access가 발생한다.
2. invalid bit임을 확인한다.
3. page fault가 발생한다.
4. B를 swap in 시키려고 한다.
5. physical memory에 자리가 없어 하나를 교체해야 한다.

따라서 이를 Page Replacement를 통해 교체해야한다.

1. victim page를 page out 한다.
2. victim page의 bit를 invalid bit로 바꾼다.
3. loading하고 싶은 page를 page in한다.
4. 해당 page가 valid하다고 bit를 reset한다.

Demanding page의 두 가지 문제

1. Frame allocation algorithm: 각 프로세스에 몇 개의 frame을 할당할 것인지
2. Page replacement algorithm: 교체할 frame을 어떤 것을 선택할 것인지

I/O에 접근하는 비용은 상당하기 때문에, demand-paging 방법의 변화로 성능상 높은 이득을 볼 수 있다.

page fault를 최대한 줄이는 방법으로 고안해야 한다.

FIFO Page Replacement

FIFO(First-In-First-Out): 간단한 알고리즘으로 가장 오래된 page를 선택하여 교체한다.

Belady’s Anomaly

Page Frame을 늘리면, page fault가 감소해야하는데 그렇지 않은 현상

LRU Page Replacement

LRU(Least Recently Used): 각 page가 사용된 최근의 시간을 기록하여, 사용되지 않은 가장 오래된 page를 교체한다.

가장 사용 안할 것 같은 page를 교체하는 것이 최선이지만 미래를 예측할 수 없으니, 과거에 이 논리를 비슷하게 적용한 방법

성능도 좋고 자주 사용된다. 하지만 최근에 사용된 시간을 측정하는 것은 메모리 용량을 많이 차지한다. 이를 구현하는 방법은 counter와 stack이 존재한다.

Counter

page를 참조할때마다, counter나 clock을 복사한다. 가장 작은 값이나 최신 값을 victim page로 선택한다.

Stack

Stack 형태와 유사하게 최신을 기록한다.

• page가 사용되면 중간에서 꺼내어 stack의 top으로 올린다.
• victim page를 선정해야할 경우, 가장 아래 page를 선택한다.

Second Chance Algorithm

FIFO Algorithm을 활용하여 reference bit가 0이면 FIFO를 기준으로 victim page로 결정한다. 만약 reference bit가 1이면, second chance를 부여하고 0으로 바꾸고 다음 FIFO page를 결정한다.

Reference Bit

0으로 초기화한 후, Page가 참조되면 1로 변경한다.

FIFO + Reference Bit + Circular Queue

Frame Allocation Issue

두 프로세스가 존재할 때 frame을 얼마나 할당할 것이냐?

• Equal vs Proportional: 프로세스 마다 필요한 frame이 다른데, 동등하게 아니면 비율로 줄 것인지
• Global vs Local: 다른 프로세스의 frame에 관여하는지

Thrashing

Thrashing은 시스템이 과도하게 페이지 부재(Page Fault)를 발생시켜 CPU와 입출력 장치의 시간을 낭비하게 만드는 현상이다.

Working-Set Model

메모리를 확인해보니, locality가 있음을 확인했다.

Working-set-Window를 정의하여 page의 set을 만든다. 만약 page가 사용되면, working set내에 있을 것이며 사용되지 않으면 working set에 없을 것이다. 따라서 victim을 working set 밖에 있는 것으로 결정한다.

이를 Thrashing 문제 완화 가능하다.

대용량 저장 장치(Mass Storage)

비휘발성의 2차 저장장치이다. (ex. HDD, NVM)

HDD

디스크 플래터 내에 트랙이 존재하고, 트랙은 여러 색터들로 이루어져 있다. 헤드는 헤드를 한꺼번에 이동시키는 디스크 암에 부착되어 있다.

HDD 스케줄링

목표

access time(seek time)을 줄이고, 데이터 전송의 대역폭(bandwidth) 최대화하는 것이 관건이다.

• Seek time: Device arm이 head를 움직이는데 특정 섹터를 찾아가는데 걸리는 시간이다.
• Disk bandwidth: 첫 요청과 마지막 처리의 total transferred bytes / total time으로 정의

FCFS 스케줄링

공정하게 요청 순서대로 처리하지만, 빠른 서비스를 제공하지 않는다.

total head movement = 640 cylinders

SCAN 스케줄링

Disk arm을 한 쪽 end에서 반대 쪽 end까지의 SCAN을 양방향으로 반복하면서 요청들을 처리한다.

total head movement = 236 cylinders (방향을 0번 쪽으로 먼저 간다고 가정)

C-SCAN 스케줄링

Disk arm을 한 쪽 end에서 반대 쪽 end까지의 SCAN을 단방향으로 진행하면서 요청들을 처리한다. 반대 쪽 end에 다다르면 바로 시작점으로 돌아온다.

total head movement = 183 cylinders

C-SCAN 스케줄링 알고리즘은 기본적으로 실린더를 최종 실린더에서 첫 번째 실린더로 되돌아가는 순환 리스트로 처리한다.

NVM 스케줄링

NVM 장치에는 이동 디스크 헤드가 없으며 일반적으로 간단한 FCFS 정책을 사용한다. 예를 들어 Linux NOOP FCFS 정책을 사용하지만 인접한 요청을 병합하도록 수정한다.

Boot Block

Bootstrap loader(시작 프로그램)는 Boot Block(NVM flash memory)에 저장되어 있다. 컴퓨터에 전원이 인가되면, bootstrap loader가 메모리에 적재되어 운영체제 커널을 로드하고 제어권을 넘기게 된다.

Boot Block도 second storage의 일종이다!

RAID

여러 개의 하드 디스크에 일부 중복된 데이터를 나눠서 저장하는 기술이다.

• parallel: 데이터의 read/write의 속도 증가
• redundant: 데이터 storage의 신뢰성

Redundancy

Reliability를 위해서 데이터를 중복으로 저장해야 한다.

• mirroring: 모든 disk를 복제하는 것

Parallelism

Performance를 증가하기 위해서 병렬적으로 처리할 수 있다.

• bit-level-striping: 각 byte를 bit 단위로 쪼개어 전송하는 것
• block-level-striping: driver로 일반화하여 쪼개어 전송하는 것

RAID Level

고려 사항

• mirroring: 신뢰성이 높지만, 비용이 비싸다
• striping: 효율적이지만, 신뢰성과 관련 없다.
• parity bit: bit level 전송 에러 탐지 방법

종류

cost와 performance를 고려해 비교한다.

• RAID 0: 안정성이나 데이터 복원 기능은 제공하지 않음
• RAID 1: Copy disk를 그대로 생성
• RAID 4: 별도의 Parity bit 디스크 생성
• RAID 5: 각 디스크에 parity bit를 따로 저장
• RAID 6: P + Q redundancy
• Multidimensional RAID 6: array를 만들어서 저장

• RAID 0 + 1
• RAID 1 + 0

I/O Systems

• Computer의 두 가지 역할은 I/O와 계산이다.
• 운영체제의 역할은 I/O 동작과 I/O 장치를 관리하는 것이다.

각 bus를 통해서 CPU가 명령을 controller에게 전송한다.

Memory-Mapped I/O

특정 장치에게 명령을 어떻게 내려야 할까? 메모리에 I/O 명령을 전달하면 Memory-Mapped I/O가 그것을 device-control register로 변환한다.

I/O types

• Polling(busy waiting): 데이터가 입력 받을 때까지 status register를 계속 읽는 상태

• Interrupt: Interrupt-request line에 신호를 전달하면, CPU가 interrupt를 탐지한다. CPU는 어떤 interrupt인지 interrupt vector table에서 확인 후, 그 interrupt를 처리하는 ISR(Interrupt Service Routine)에 제어권을 넘긴다.

• DMA(Direct Memory Access): register(ADD, LOAD, STOR…)를 통한 데이터 교환을 하는 것이 아닌 HW 버스를 직접 이용하는 것이다. 즉, CPU의 도움없이 I/O 장치가 직접 메모리에 접근하는 방식이다. 대용량 데이터 전송에 용이하다.

CPU가 대용량 데이터를 전송하려면 CPU 버스를 다 쓰게 되어서 다른 작업이 불가능하다. DMA는 데이터를 메모리 간에 직접 전송하여 CPU와 독립적으로 작동하여 효율적이다.

Blocking, Non-blocking I/O

• Blocking I/O: thread가 일시정지한다. Running queue에서 waiting queue로 이동한다.

• Non-blocking I/O: thread의 실행이 멈추지 않는다.

파일 시스템

파일 시스템이란 쉽게 데이터를 저장하고, 찾고 또한 인출할 수 있게 함으로써 저장장치를 더욱 편리하게 사용할 수 있게 한다.

file과 directory로 나눌 수 있다.

접근 방식

순차 접근

데이터를 처음부터 끝까지 순서대로 차례대로 읽거나 쓰는 방식이다.

직접 접근(Direct access, Random access)

직접 접근(Direct access, Random access)은 파일 내의 특정 위치로 직접 이동하여 데이터를 읽거나 쓰는 방식이다.

여러 개의 데이터를 입력할 때, 순차 I/O는 디스크 헤드를 한 번만 움직이지만 랜덤 I/O는 디스크 헤더를 데이터의 개수만큼 움직여야 한다.

인덱스 레인지 스캔(Index Range scan)은 데이터를 읽기 위해 주로 랜덤 I/O를 이용하고 풀 테이블 스캔(Full Table scan)은 순차 I/O 를 사용한다.

디렉터리 구조

• Single-Level Directory

  • 모든 파일이 하나의 디렉터리에 모여 있는 간단한 구조다.
  • 모든 파일은 유일한 이름을 가져야 하며, 이름 충돌이 발생할 수 있다.

• Two-Level Directory

  • 사용자별로 디렉터리를 생성하여 각 사용자의 파일을 해당 디렉터리에 저장한다.
  • 각 사용자 디렉터리 내에서 파일 이름은 고유하다.
  • 사용자는 다른 사용자의 파일을 직접적으로 볼 수 없다.

• Tree-Structured Directory

  • 디렉터리를 트리 구조로 조직화한다.
  • 최상위 디렉터리에서 하위 디렉터리로 계층적으로 구성되며, 각 디렉터리 내에 파일이나 하위 디렉터리가 존재할 수 있다.
  • Linux 및 UNIX 파일 시스템에서 사용되는 일반적인 구조다.

• Acycle-Graph Directory

  • 디렉터리 간에 순환 경로가 없는 구조다.
  • 파일이나 디렉터리 간에 링크를 통해 참조될 수 있지만 순환이 발생하지 않는다.
  • 일반적으로 파일 시스템의 불필요한 복잡성을 피하기 위해 사용된다.

• General-Graph Directory

  • 디렉터리 간에 임의의 그래프 구조를 가지며 순환이 발생할 수 있다.
  • 각 디렉터리는 파일이나 다른 디렉터리를 참조할 수 있으며, 파일 시스템이 복잡한 관계를 표현할 수 있다.

파일 시스템 구조

I/O 효율성을 향상하기 위해 메모리와 대용량 스토리지 간의 I/O 전송이 블록 단위로 수행된다. 하드 디스트 드라이브의 각 블록에는 하나 이상의 섹터가 있다.

파일 시스템 계층

파일 시스템은 여러 개의 계층으로 나누어져 있다. 각 층은 낮은 층의 기능을 사용하여 새로운 기능을 만들어 상위 층에게 제공한다.

• 응용 프로그램(application programs): 사용자가 파일을 접근 및 조작할 수 있는 인테페이스 제공한다.
• 논리적 파일 시스템(logical file system): 메타데이터 정보를 관리한다. 메타데이터는 파일의 내용 자체를 제외한 모든 정보를 의미한다.
• 파일 구성 모듈(file-organized module): 파일의 논리적 블록을 물리적 블록에 매핑하고, 파일 블록 할당과 해제를 처리한다.
• 기본 파일 시스템(basic file system): 적절한 장치 드라이버에게 저장장치의 블록을 읽고 쓰도록 일반적인 명령을 내리는 층이다.
• 입출력 제어(I/O control): 장치 드라이버 루틴과 인터럽트 핸들러로 이루어져 있어 디스크의 물리적 섹터에 대한 직접적인 접근을 처리하고, 하드웨어와의 상호 작용을 관리한다.
  • 장치 드라이버 루틴: 고수준의 명령을 저수준의 명령으로 변환한다.
• 하드웨어 장치(Devices): 물리적 디스크(HDD sector track)에 데이터를 실제로 저장하고 읽는 작업을 수행한다.

할당 방법

저장 공간을 효율적으로 사용하고 빠르게 읽기 위해서는 비어있는 공간에 파일들을 할당하는 방법이 중요하다.

연속 할당(Contiguous Allocation)

연속 할당은 각 파일이 저장장치 내에 연속적인 공간에 저장한다. 하나의 블록 b 다음에 블록 b+1을 접근한다면 헤드 이동을 요구하지 않는다.

단점)

• 외부 단편화(external fragmentation): 파일이 연속적으로 할당되기 때문에 가용 디스크 공간이 작게 나눠진다. 큰 연속된 파일이 저장될 경우, 작은 디스크 공간에 연속적으로 할당되지 못한다.
• Compaction: Compaction으로 모든 작은 가용 영역을 합쳐 하나의 큰 가용 영역을 만들 수 있다. 하지만 대용량 저장장치의 경우에 Compaction에 드는 시간과 비용이 많이 들 수 있다.

연결 할당(Linked Allocation)

연결 할당은 연속 할당의 문제를 해결할 수 있다. 연결 할당은 각 파일을 저장 장치의 블록 단위로 쪼개서, 장치 내의 흩어져 linked list 형태로 연결한다.

각 블록은 다음 블록을 나타내는 포인터를 포함한다.

장점)

• 외부 단편화가 발생하지 않는다.

단점)

• 순차 접근에는 효율적이지만, 직접 접근 방식에서 비효율적이다. i번째 block을 찾고 싶을 경우에도 불가피하게도 처음부터 탐색해야 한다.
• 포인터들을 위한 별도의 공간이 필요하다. (512B 중 4B = 0.78%)
• 장치 전체에 흩어져 있기 때문에 오류나 하드웨어의 고장으로 하나의 포인터를 잃어버리거나 잘못된 포인터 값을 가지면, 모든 데이터를 잃을 수 있다.
  • Double Linked List 방식을 도입하여 해결 가능하나, 오버헤드가 크다

클러스터

연결 할당의 단점을 위해 클러스터라는 개념이 등장했다. 블록을 모아 클러스터라는 단위로 만들고 클러스터를 할당하는 것이다. (4 블록 = 1 클러스터)

장점)

• 블록을 나타내야할 포인터의 개수가 감소하므로 파일 공간의 휠씬 적은 부분을 사용한다.

단점)

• 내부 단편화의 증가
• 소량 데이터 요청이 많은 양의 데이터 전송을 유발하기 때문에 Random I/O 성능이 저하된다.

FAT(File Allocation Table)

FAT 테이블은 각 블록마다 한 개의 항목을 가지고 있고, 이 항목은 디스크 블록 번호를 인데스로 찾는다.

디렉터리 항목은 각 파일의 첫 번째 번호를 가리킨다. 해당 블록 번호를 통해 FAT 테이블로 가서 다음 블록 번호를 찾는다. 이렇게 마지막 블록까지 계속되며, 마지막 블록의 테이블 항은 끝을 나타내는 특수한 값을 가지고 있다.

FAT 기법은 FAT가 캐시 되지 않으면 상당한 수의 디스크 찾기를 유발할 수 있다. FAT를 찾기 위해 디스크 헤드를 반드시 파티션의 시작 부분으로 움직여 찾고자 하는 블록의 주소를 알아내야 하고, 이어 그 블록이 있는 곳으로 다시 이동해야 한다. 즉 최악의 경우 각 블록마다 디스크 헤드를 두 번 이동해야 한다.

장점)

• Random I/O의 시간이 개선된다.

색인 할당(Indexed Allocation)

연결 할당은 연속 할당의 외부 단편화 문제를 해결했다. 하지만 FAT가 없다면 직접 접근 방식을 지원하지 않는다.

색인 할당은 각 파일은 색인 블록(index block)을 소유하게 되고, 색인 블록에는 모든 포인터를 갖고 있다.

장점)

• 저장장치의 어느 블록인든 더 많은 공간의 요청을 만족시킬 수 있다. 즉 외부 단편화 문제가 없다.

단점)

• 색인 블록의 오버헤드가 연결 할당의 포인터 오버헤드보다 크다.

가용 공간 관리(Free Space Management)

저장장치 공간은 제한되어 있기 때문에 삭제된 파일들이 차지하던 공간을 새로운 파일들을 위해 다시 재사용해야 한다. 시스템은 가용 영역을 리스트로 유지하고 관리한다. 이 리스트에 모든 가용 블록들을 등록한다. 새로운 파일을 만들려면 가용 공간 리스트를 탐색하여 새로운 파일을 위한 공간을 할당받아야 한다. 그러면 할당되는 공간은 가용 공간 리스트에서 삭제된다.

비트 벡터

가용 공간 리스트는 비트맵 또는 비트 백터로 구현된다. 블록이 비어 있으면 1, 블록이 할당되면 0으로 표시한다.

이진법이 아님을 주의하자.

001111001111111000110000001110000…

장점)

• 가용 블록을 찾는 일이 상대적으로 효율적

단점)

• 비트 벡터는 메모리에 존재하야하는데, 디스크 사용량이 커지면 비트 벡터의 크기도 커진다.

연결 리스트

모든 가용 영역을 연결하는 방식으로 이루어져있다. 첫 번째 가용 블록이 두 번째 가용 블록의 포인터를 가지고 있다.

HDD에서 가용 공간 리스트를 순회하려면 효율적이지 못하다. 그러나 가용 리스트 순회는 빈번하게 발생하지 않는다.

파일 시스템 캐시

Security

• authentication(인증): 사용자 신원을 검증
• authorization(인가): 자원에 대한 접근

Program 위협

• Malware: 다양한 형태의 악성 소프트웨어를 포괄적으로 지칭하는 용어이다.
• Code Injection: 악성 코드가 정상적인 프로그램의 코드에 주입되어 실행되는 과정을 나타낸다.
• Virus: 악성 코드의 한 형태로, 정상적인 프로그램이나 파일에 바이러스 코드를 감염시켜 복제하고 전파하는 소프트웨어이다.

Network 위협

• sniffing: 네트워크 상에서 데이터를 가로채어 엿보는 행위
• spoofing: 자신의 정체를 감추거나 다른 개체로 위장하여 다른 시스템이나 사용자를 속이는 행위를 의미
• DDOS: 대규모의 트래픽을 목표 시스템에 전송하여 리소스 고갈을 유도하거나, 특정 서비스를 마비시키기 위해 다양한 기술을 사용
• Port Scanning
  • 포트 스캐닝은 네트워크 상의 여러 시스템의 특정 포트들에 접근 가능한지를 확인하는 것을 의미
  • 공격자는 특정 포트에 접근하여 서비스가 열려 있는지, 어떤 종류의 서비스가 동작 중인지를 확인
  • 포트 스캐닝은 시스템의 보안 취약점을 찾거나 공격에 앞서 시스템의 상태를 조사하는 데 사용될 수 있다.

Encryption algorithms

• symmetric(대칭키): 같은 키(secret key)로 encrypt(암호화)와 decrypt(복호화)를 진행한다.
• asymmetric(비대칭키): 다른 키(public key, private key)로 encrypt(암호화)와 decrypt(복호화)를 진행한다.

Symmetric encryption

1. 송신자는 data를 write한다.
2. Message M이 secret key에 의해 암호화된다.
3. public하게 data가 전송된다.
4. 수신자는 secret key를 통해 복호화한다.
5. 수신자는 data를 read한다.

Symmetric encryption의 문제점은 수신자와 송신자가 같은 key를 갖게 하는 것이 문제다. key 전달 과정에서 attacker에 의해 노출될 수 있기 때문이다.

Asymmetric encryption

RSA algorithm: 비대칭 암호화에 쓰이는 알고리즘

1. 수신자가 public key, private key 생성한다.
2. public key를 등록하고 private key는 본인이 소유한다.
3. 송신자가 수신자의 public key를 가져온다.
4. 송신자가 수신자의 public key를 이용하여 data를 암호화한다.
5. 암호화된 data를 전송한다.
6. 수신자는 private key를 통해 복호화한다.

Reference

• https://www.yes24.com/Product/Goods/89496122
• https://ko.wikipedia.org/wiki/%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4
• https://ko.wikipedia.org/wiki/%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4_%EC%A0%9C%EC%96%B4_%EB%B8%94%EB%A1%9D
• https://ko.wikipedia.org/wiki/%ED%8F%AC%ED%8A%B8_(%EC%BB%B4%ED%93%A8%ED%84%B0_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%82%B9)
• https://ko.wikipedia.org/wiki/%EC%95%94%EB%8B%AC%EC%9D%98_%EB%B2%95%EC%B9%99
• https://yonghwankim-dev.tistory.com/323