백짱미 개발log

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

보안과 보호

보안(Security)

• 컴퓨터 시스템의 물리적 자원인 데이터와 코드에 대한 정보 무결성을 보호하기 위해 사용자 인증 보장
• 인증받지 않은 접근, 악의적인 파괴, 변경/실수에 의한 데이터 변경 방지
• 지정된 일부의 인원만 알고 있어야하는 정보를 위험으로부터 지킴
• authentication : 인증

보호(Protection)

• 운영체제로부터 적절한 권한을 획득한 프로세스만이 memory segments, CPU와 같은 자원 사용할 수 있도록 보장
• 사용자에게 허용되는 접근의 종류를 제한함으로써 시스템에 접근하는 것을 제어
• 보호해야할 가치가 있는 정보를 외부의 위협으로부터 지키는 일련의 행동
• authroization : 인가, 권한 보호

Security Problem

컴퓨터 자원 (Computer Resources)

• 우연히 혹은 의도적으로 잘못 사용되는 것을 방지
• 공격을 감지하여 방어하고, 실수를 제어함
• cryptography(암호학)

컴퓨터 자원 보안 (Security)

• 보안은 컴퓨터 자원을 보호해야함
  • 권한 없는 접근
  • 악의적인 침입 및 변경
  • 실수로 데이터 일관성을 해치는 행위

보안 위배 요소

• thread: 보안 위반을 일으킬 수 있는 잠재적인 가능성, 주로 실수에 의해 발생
• attack: 악의적인 공격

보안 위배 사항 분류

• 무결성 위반 (Confidentiality)
• 데이터 안정성 위반 (integrity)
• 유용성 위반 (availability)
• 서비스 절도 (Theft of service)
• 서비스 방해, 디도스 공격 (Denial of service (Dos) 혹은 Distributed Dos (DDos))

보안의 4단계 

• 물리적 단계(Physical) : 인가된 사용자만이 진입할 수 있도록 물리적으로 보호
• 네트워크 단계(Network) : 보안 측면에서 해로운 단계
• 운영체제 단계(Operating System) : 공격할 수 있는 지점을 줄이고 침투를 못하게 막음
• 응용 프로그램 단계(Application) : 보안을 위배하는 버그를 포함 (가장 상위 단계)

Program Threats

프로그램 (또는 프로세스) 보안 취약점 

• 멀웨어 (Malware)
  • 컴퓨터 시스템을 공격, 비활성화 또는 손상시키도록 설계된 소프트웨어
  • 트로이 목마(Trojan horse), 스파이웨어(spyware), 랜섬웨어(ransomware), 백도어(backdoor), 로직붐(logic bomb)
• 코드 주입 (Code Injection)
  • 대부분 소프트웨어는 악의적이지 않으나 code-injection 공격으로 심각한 피해
• 바이러스와 웜 (Viruses and Worms)
  • 바이러스 : 일반적인 프로그램에 있는 코드의 조각, 다른 프로그램 감염하도록 자가복제
  • 웜: 사람의 도움 없이 스스로 복제하기 위해 네트워크 사용

System and Network Threats

시스템 및 네트워크의 위협

• 네트워크 트래픽을 통한 공격
  • 스니핑 (sniffing) : 침입자가 능동적으로 다른 상대방들의 네트워크 트래픽을 intercept
  • 스푸핑 (spoofing) : 다른 사람의 컴퓨터 시스템에 접근할 목적으로 IP 주소를 변조 후 합법적인 사용자인 것처럼 위장하여 시스템 접근 ⇒ IP 주소에 대한 추적을 피하는 해킹 기법

• 서비스 거부 공격 (Denial of Service)
  • 시스템을 악의적으로 공격해 해당 시스템의 자원을 부족하게 하여 원래 의도된 용도로 사용하지 못하게 하는 공격
• Port Scanning
  
  • 취약점 탐지의 사전 작업
  • 포트 스캐닝 자체로는 정상적인 동작이나 공격 용도로 이용할 때가 있음
  • 시스템이나 네트워크가 어떤 포트를 열고 서비스하고 있는지 알아내기 위한 작업

Cryptography as a Security Tool

네트워크로 연결된 컴퓨터에서는 네트워크 메세지의 잠재적인 송신자와 수신자가 존재한다.

운영체제 입장에서는 이 메세지를 어떻게 신뢰할까?

바로 Cryptography, 암호술이다. cryptography는네크워크에서 컴퓨터들에 대해 선택적으로 분산된 키(keys)를 기반으로 하여 네트워크를 신뢰할 수 있도록 한다.

암호화 (Encryption)

sender가 키를 가지고 receiver만 메세지를 읽을 수 있도록 함

• 암호화 알고리즘의 컴포넌트
  • 키의 집합 : K
  • 메시지의 집합 : M
  • 암호화된 문자의 집합 : C
  • 암호화 함수 E : K -> (M -> C)
  • 복호화 함수 D : K -> (C -> M)

• 암호화 알고리즘의 핵심적인 특징
  • 암호화된 문자 c가 주어졌을때 메시지 해석
  • 키 k를 보유한 컴퓨터는 암호문자를 복호화하여 일반 텍스트로 복호화 가능
  • 키 k를 보유하지 못한 컴퓨터는 암호문자를 복호화 불가능
  • 암호문자를 일반적으로 노출이 되어 있지만 암호문자로부터 키 k를 도출하는 것은 불가능

암호화 알고리즘의 종류

1. 대칭형(symmetric) 암호화 알고리즘

• A와 B가 사용하는 key가 같을 때 (암호화, 복호화시 사용하는 키같음)
• key는 보호되어야함

2. 비대칭형(asymmetric) 암호화 알고리즘

• 암호화와 복호화하는데 key가 다름
• 공개키 (public key) : 암호화하는데 사용되는 키
• 개인키 (private key) : 복호화하는데 사용되는 키
• 공개키는 외부에 공개되어도 상관 없지만, 개인키는 노출되어선 안

대칭형 암호화 알고리즘 (Symmetric Encryption)

• 송신자와 수신자 모두 동일한 키를 가지고 암호화, 복호화 수행
• 암호화와 복호화는 송신자와 수신자 둘 간의 발생할수도 있고 신뢰받는 3자를 통해서 발생할 수 있음
• 대칭형 암호화 알고리즘 종류
  • DES : Data Encryption Standard
  • AES : Advanced Encryption Standard

비대칭형 암호화 알고리즘 (Asymmetric Encryption)

• 공개키와 개인키를 구분하여 암호화와 복호화 수행하는 방식
• 암호화 키와 복호화 키를 서로 다르게 쓰면 누가 listening해도 상관 없음
• 공개키는 외부에 노출 가능하지만 개인키는 노출되어선 안됨
• RSA 알고리즘 : Rivest, Shamir, and Adleman
  • 현대까지도 많이 사용되는 비대칭 알고리즘

인증 (Authentication)

• hashing을 통해 키를 가진 수신자만 복호화
• 송신자의 메세지를 제한하여 중간에 수정되지 않도록 보장
• 인증 알고리즘  
  • 키의 집합 : K
  • 메시지의 집합 : M
  • 인증자들의 집합 : A
  • 보안(해시) 함수 S : K-> (M->A)
  • 검증(verification) 함수 V : K->(M x A -> {true, false})
• 메세지 m이 주어지면 메세지를 가지고 k를 알아야 컴퓨터는 인증자 a 생성 가능 (ex 전자서명)
• 오직 k를 가지고 있는 경우에 V_k(m, a) = true 
  • k를 가지고 있는 경우 메세지에 인증자를 생성하여 확인 
  • 그렇지 않으면 인증자 생성 불가
• 인증 알고리즘의 종류
  • MAC : Message-Authentication Code
  • Digital Signature Algorithm

Goals of Protection

• 컴퓨터 시스템에 의해 정의된 자원에게만 프로세스와 사용자에게 권한 부여해줌 
• 컴퓨터 시스템의 reliability를 증가하여 인터넷과 같은 보안 커뮤니케이션 platform에 접근하도록 함

최소한의 권한 원칙 (The Principle of Least privilege)

• 프로세스, 유저, 시스템에게 최소한의 권한 부여
  • ex) UNIX user & file privileges : root, sudo, chmod
  • permissions 획득해야지 악성 공격 가능성 완화

Access Matrix

• matrix로 ACL (Access Control LIst, 권한의 집합)을 생성하여 어디까지 접근 가능한지 정리
• 어떤 도메인에 어떤 객체가 접근 가능한지 행렬로 정리해 정책(policy)을 관리

Sandboxing & Code Signing

• Sandboxing
  • credential 있는 프로세스만 유효한 범위 내에서 실행 가능
  • running process와 같이 할 수 있는 거만 제한
    
    • ex) JAVA and .NET

• Code signing
  • 어떤 프로그램이나 스크립트, 앱을 어떻게 실행할 수 있을까? 만약 코드나 스크립트가 바뀐다면?
  • 프로그램에 Code signing을 하여 안전한 프로그램임을 인증 (digital siging of programs and executables)
    • 전자 서명, Operating System의 patch 작업, 안드로이드나 iOS 앱에서 사용

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

Mass-storage Structure

• Mass-storage는 보조기억장치 시스템 (비휘발성 메모리)
• HDD(Hard Disk Drive) or NVM(Non-Volatile Memory)
• 때로는 마그네틱 테이프(백업용), 광학 디스크, 클라우드 저장소 의미

Hard Disk Drives

• 하드디스크 드라이브 : 전통적인 저장 장소
• 대용량 데이터를 저장하는 용도

HDD 스케줄링

스케줄링의 목적은 접근 시간 (or seek time) 최소화 및 데이터 대역폭 (bandwith) 최대화를 목표로 한다.

• Seek Time : 헤드가 저장된 트랙(특정 섹터)으로 이동하는데 걸리는 시간
• Rotation Latency : 헤드가 트랙 내에서 원하는 섹터로 이동하는 것까지 걸리는 시간
• Disk Bandwidth : 첫 요청에서 마지막 전송 완료시까지 (전송 용량 / 전체 시간)을 계산 → 시간당 한 번에 전송할 수 있는 용량

FIFO 스케줄링

• 먼저 들어온 요청 섹터를 먼저 처리
• 공평하나 매우 느림(비효율적)

Scan 스케줄링

• 디스크 한쪽 끝에 암을 배치하고 다른 쪽 끝으로 암을 이동시키며 스캔
• 방향 중요
• 이 과정에서 헤드는 반전되고 계속해서 이동

C-SCAN 스케줄링

• 스캔시 uniform scan time 부여
• 디스크 끝에 도달 후 처음으로 돌아올 때 속도를 위해 데이터 읽지 않음
• 원형 리스트처럼 다룸 → 마지막 실린더가 첫 실린더를 감싸는 순환 구조

Boot block

• 부팅에 필요한 파일을 담는 디스크 영역
• 전원이 인가되었을깨 컴퓨터 로딩시키기 위해 반드시 실행되어야하는 프로그램
  ⇒ 부트스트랩 프로그램 적재
• NVM flash memory에 저장
• 전원 인가돠면 메모리에 올라와서 운영체제 커널 로드 후 운영체제에 넘겨줌

RAID

• RAID : Redundant Arrays of Independent Disks (복수 배열 독립 디스크)
• 여러 디스크를 묶어 하나의 디스크처럼 사용하는 디스크 구성 기술
  • 여러 개의 하드 디스크에 일부 중복된 데이터를 나눠서 저장
• 드라이브를 병렬로 작동시켜 데이터의 읽기 및 쓰기 속도 향상 
• 신뢰성(Redundancy)을 높여 데이터 보호 능력 향상
  • 한 디스크의 데이터를 다른 디스크로 미러링(중복 저장)하여 데이터 보존
  • 충분한 정보가 많은 장지체 저장 
• Parallelism을 통해 성능 향상
  • bandwitdth를 striping하여 데이터를 전송할 때 드라이브에서 한번에 보낼 수 있도록 함
  • Multiple drive 있다면 전송률 향상할 수 있음

RAID LEVEL

• Mirroring : 데이터 카피 → 신뢰성을 높여주지만 비용이 비쌈
• Striping : 효율적이나 신뢰성을 낮춤
• 레이드 레벨로 구분 → 분류를 통해 cost-performance trade off

• 비용 대비 성능에 따라 레벨로 분류
  • RAID 0 : 데이터를 여러 디스크에 분할 저장하는 방식, 한 디스크에서 장애 발생 시 데이터가 모두 손실
  • RAID 1 : 디스크에 기록된 정보를 모두 미러링하여 저장
  • RAID 4 : parity 디스크를 추가하고, parity bit를 넣어 디스크에 에러가 발생하지 않았는지 검사
  • RAID 5 : 각 디스크에 parity bit 추가
  • RAID 6 : 각 디스크에 parity bit를 이중으로 추가하여 더 정교하게 에러 감지

• RAID 0 + 1 : stripe한 디스크를 미러링 하는 방식, 미러링 전에 한 디스크가 고장나면 데이터가 손실될 수 있음
• RAID 1 + 0 : 미러링한 디스크를 stripe하는 방식이며 안정성이 높아 현업에서 주로 사용

I/O systems

• 컴퓨터가 하는 두가지 일 : I/O and computing
• I/O가 메인 작업 (웹 브라우징, 파일 편집, 유튜브, 게임 등)
• 운영체제가 I/O 장치와 연산 관리

• Memory-Mapped I/O
  • 디바이스에 내리는 명령을 어떻게 정할 것인가?
    • Data-in register
    • Data out
    • Status
    • Control
  • I/O address에 관련있는 controller 레지스터와 함께 메모리에 매핑
    • 메모리에 I/O 명령을 내리면 controller 레지스터 역할 수행

Three types of I/O

• Polling : or busy-waiting
  • Busy bit이 종료될때까지 Status register를 반복해서 읽음
• Interrupt
  • 대기할 때 시그널 주는 명령
  • CPU는 Interrupt-request line이라고 불리는 와이어 보유
  • CPU가 인터럽트 탐지하면 이를 ISR(interrupt service routine)으로 이동
  • ISR 주소는 인터룹트 벡터 테이블에 구체화됨
• DMA(Direct Memory Access)
  • Programmed I/O (직접 I/O 작업)를 피하기 위해 사용
  • 대용량 데이터 전송을 위해 사용

Blocking I/O vs Non-Blocking I/O

• Blocking : 요청 스레드의 실행이 즉시 지연됨 (Running 상태에서 Waiting Queue로)
• Non-blocking : 요청 스레드의 실행 중단하지 않고 요청시 바로 리턴
• Asysnchronous system call : 실행 계속 해 나감
  • Non-blocking과 Asysnchronous system call 차이
    
    • Non-blocking: 즉시 리턴, 데이터가 이용 가능한지 여부, 양 상관 없음
    • Asysnchronous system call : 리드 호출하면 요청하고 자기 할일 또 계속 할 수 있음, 계속 실행해 나감

File system Interface

파일 시스템은 운영체제의 모든 사용자 데이터, 프로그램을 논리적으로 저장하고 사용자가 접근 가능하게 설정하는 것이다.

관련 데이터를 저장하는 파일과 시스템 내의 모든 파일을 정리하는 디렉터리로 파일 시스템이 구성된다.

접근 방법

1. 순차 접근 (Sequential access) 

• 파일 내 정보를 순서대로 접근하는 것
• 파일 레코드가 순차적으로 기록되어 있어 판독할 때도 순차적으로 판독 

2. 직접 접근 (Direct access)

• 파일의 레코드가 순차적으로 기록되어 있어 판독할 때도 순차적으로 판독

디렉토리 구조

• 디렉터리 : 파일 시스템 내부에 있는 것, 디스크에 존재하는 파일에 대한 여러 정보를 가지고 있는 특수한 형태의 파일
• 각 파일의 위치, 크기등의 정보를 가지고 있음
• 디렉토리 구조 종류 4가지 (Single-level, Two-level, Tree-structured, Acyclic-graph, General graph)

File-System Implementation

파일 시스템 자체로도 위의 사진과 같이 여러 레벨 지닌다.

(application programs → logical file system → file-organization module → basic file system → I/O control → devices)

파일 시스템 내 문제 중 하나로, 파일 공간 할당을 어떻게 할 것인가?

Allocation method

• 디스크 공간에 파일을 할당할 때 어떤 방식으로 해야 더 효율적일까?
• Contiguous allocation
  • 하나의 파일이 디스크에 연속적으로 저장되는 것
  • 파일이 삭제되면 홀이 생기고 반복되면 홀이 흩어짐 ⇒ 새 파일을 어느 홀에 배치할 수 있느냐에 따라 외부 단편화 문제 발생
• Linked allocation
  
  • Linked List를 이용해 아무 곳에나 들어갈 수 있도록 만드는 방법
  • 연속 할당의 문제 해결
  • 중간에 한 섹터에 문제가 발생하면 이후의 링크도 모두 잃기에 안정적이지 않음
• FAT (file allocation table)
  • 연결 할당의 변종으로 하나의 데이터 블록에 다음 블록에 대한 정보를 담고 있는 테이블
  • 포인터를 별도의 테이블에 보관하는 방법
  • 연결 할당 문제점 해결
• Indexed allocation
  • 각 파일에 포인터가 순서대로 저장된 인덱스 블록을 할당
  • 인덱스 블록의 i 번째 항목이 파일의 i 번째 블록을 가리킴
  • 너무 큰 파일인 경우 하나의 블록으로 인덱스를 모두 저장할 수 없기 때문에 다중 인덱스 블록을 구성해야 함

• FreeSpace Management
  • Free Disk Space를 추적하기 위해 Free-space List 보유

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

Background

가상메모리

• 어떤 프로세스의 실행을 실제 메모리에 다 올리지 않아도, 물리 메모리보다 프로세스의 메모리가 더 커도 실행 가능하도록 할 수 있도록 하는 기술
• 가상의 메모리로 생각하면 물리 메모리에서 논리 메모리 분리 가능
• 매우 효율적인 메커니즘
• 사용하지 않는 메모리는 서브 메모리(SSD, HDD)에 업로드 

가상 주소 공간

• 논리 프로세스 메모리 구조
• 연속적인 메모리에 존재

Page Sharing

• 두 개 이상 프로세스에서 파일과 메모리 공유 쉬움
• 공유하는 파일과 메모리를 shared page에 두고 사용 

Demand Paging

보조기억장치에서 메인메모리로 프로세스를 실행하면서 로딩하는 과정이 필요한데, 사용하지 않는 것까지 모두 올리는 것은 비효율적이다. 

그래서 모든 메모리를 올리는 대신 페이지 단위로 잘라서 올린다.

Demand paging을 통해 각각의 페이지를 올리는 시점을 정해 요청할 때마다 올리도록한다.

Demand-page 이슈

Demand paging은 유용하지만 많은 것을 고려해야한다. Demand될 때 어떻게 관리할 것인가?

• 어떤 프로세스가 실행 중일 때는 필요한 자원이 메인 메모리나 보조기억장치에 있어야함
• Demand paging에서의 유효성 확인 (메인에 있는지 보조기억장치에 있는지)
  • Vaild : 해당 페이지가 유효하고 메모리에 존재함
  • Invalid : 해당 페이지가 유효하지 않거나 보조기억장치에 있음

Page Fault

아직 메모리에 로딩이 안된 페이지에 접근 요청

• 내부 테이블 체크하여 유효한 페이지인지 확인
• 만약 Valid라면 페이지 제공
• 만약 Invalid라면 페이지 메모리에 로드
  • 비어있는 프레임(free frame) 발견하여 HDD에 있는 페이지를 로드해야함
  • 내부 테이블이나 페이지 테이블에 해당 페이지가 메모리에 있다고 표시 후 명령 재시작

Pure demanding page

요청하지 않으면 페이지를 메모리에 올리지 않음

• 메모리에 페이지 없는 채로 프로세스 실행
• 처음 메인 메모리에 아무것도 없으므로 첫번째 요청은 무조건 page fault 발생

참조 국부성 (Locality of Reference)

• 어떤 프로세스의 각 명령어가 여러 개의 페이지를 접근한다면 multiple page faults 일으킬 수 있음
• 다행히 통계적으로 이런 경우가 드물며, 특히 메모리 관점으로 봤을 때 국부성(지역성)이 있음

Hardware Support to Demand Paging

• Page table
  • 페이지 테이블을 사용하기 위해 해당 페이지가 저장된 실제 물리 메모리 주소를 알아야함
  • valid or invalid인지 마크할 수 있는 능력 보유 (dirty bit 사용해서 확인)
• Secondary memory (swap space)
  • 별도의 장치 사용해서 페이징 스왑을 위해 세컨더리 메모리 활용

Free Frame List

Page Fault가 발생할 때, OS는 보조기억 장치에서 메모리로 요구되는 페이지를 가져온다.

Page Fault를 해결하기 위해 OS는 Free Frame list를 유지한다.

Free Frame list는 이러한 요청을 만족하는 Frame list의 pool이다.

Demand Paging Performance

page fault가 발생하면 실행 중인 프로세스를 대기큐에 보내서 페이지 스왑 완료시 프로세스를 재시작하도록 한다.

페이징 아웃, 인 과정에서 위치가 정확해야하고, 프로세스별로 페이징 테이블을 관리해야 한다.

• Demand-paging memory에 효율적으로 접근하는 시간을 실행하는 방법?
• ma : memory access time
• p : probability of a page fault
  • EAT = (1 − 𝑝) × 𝑚𝑎 + 𝑝 ∗ 𝑝𝑎𝑔𝑒 𝑓𝑎𝑢𝑙𝑡 𝑡𝑖𝑚𝑒 
• page fault를 서비스하는데 필요한 시간? (3가지 주요 Activities) 
  • Service the page-fault interrupt
  • Read in the page
  • Restart the process

Copy-on-Write

• Read만 할 때 페이지의 변경 작업이 이뤄지지 않으므로 CRUD 과정 중 R할 때만 Copy
• shared page로 활용하고 CUD 할 때만 Copy 진행 → fork

Page Replacement

• No free frame의 경우 어떤 일이? ( == 페이지를 메인 메모리에 로드할 공간이 X)
  • 멀티프로그래밍의 차수를 늘려나가면 over-allocating memory 상태 
  • 페이지를 in 시키기 위해서는 메인 메모리에 올라간 페이지를 제거해서 공간을 만들어야함

Page Replacement

1. Page Fault 과정에서 free frame이 없다면, 희생자를 선정하는 알고리즘에 의해 제거할 페이지를 선정
2. 새로운 페이지를 메모리에 올리고 페이지와 프레임 테이블을 변경
3. page fault + page replacement 가 끝나면 프로세스는 작업을 재개함

Page Replacement의 두 가지 문제

• Frame-allocation algorithm : 희생자 선정하는 알고리즘  
• Page-replacement algorithm : 프로세스마다 몇 개의 프레임을 할당 

보조 기억 장치에 I/O를 하는 비용은 비싸며, demand paging의 성능이 조금만 좋아져도 시스템 효율이 굉장이 높아진다. 

Page Replacement algorithm 평가기준

• page fault의 비율을 낮춤
• reference string (참조 문자열) : 메모리 레퍼런스
• the number of page faults minimize
• 프레임 많을수록 pf 줄어들것

FIFO Page Replacement

• 가장 간단한 알고리즘
• 가장 오래된 페이지를 대체
• Belady’s Anomaly
  • 할당된 프레임 수가 증가함에 따라 Page Fault 비율 증가

Optimal Page Replacement

• 가장 적은 Page Fault 비율 → Belady algorhtim으로 고통 X
• 앞으로 사용 안할 거 같은, 오랫동안 사용안할 거 같은 페이지(OPT)를 내보냄
• 최적화는 미래 knowledge가 필요 → 다른 연구와 비교용으로 사용

LRU Page Replacement (Least Recently Used)

• 최근에 젤 안사용된 페이지를 사용
• 각 페이지 마지막으로 사용한 기록을 바탕으로 젤 오래된 페이지 찾기
• LRU Policy : 효율 좋고 자주 사용
  • 프레임이 언제 마지막으로 사용되었는지 알아야함 (알려면 복잡 ..)
  • 하드웨어 지원받으면 좋은데 쉽지 않음
  • Belady anomaly 겪을 수 없음
• LRU 구현
  • Counter Implementation (페이지 쓸떄마다 카운트 갔다오거나 clock을 복사)
  • Stack Implemenation (페이지 넘버를 스택에 넣고 없어질때까지)
• LPU Approximation
  • HW 지원 필요, 많은 OS가 reference bit 제공
  • reference bit : 페이지 reference할 때마다 reference bit 0으로 치환 (원래 1)

Second-Chance Alogorithm

• LRU 컨셉의 알고리즘 중 하나
• FIFO 알고리즘 + reference bit 
  • r bit 0이면 페이지 교체
  • r bit 1이면 second chance 줌 (FIFO에 의해 다음 페이지 선택)
  • r bit을 가지고 reset 가능

Allocation of Frames 

N개의 프로세스가 있을 때 M개의 프레임이 있다면, 각 페이지에 얼마만큼 배정해야할까?

분배 (Equal vs Proportional)

• Equal allocation : 모든 프로세스에게 동일한 프레임을 할당
• Proprtional allocation : 프로세스 사이즈가 큰 경우에게 더 많이 할당

교체 범위 (Global vs Local)

• Global replacement : 프로세스에게 할당된 프레임 중 희생자를 정해서 교체
• Local replacement : 프로세스들이 사용하고 있는 모든 프레임 중 희생자를 선정하여 교체

Thrashing

Demand paging으로 가상 메모리를 사용하면 HW 메모리에 큰 프로그램을 만들 수 있다. 그러나  어떤 프로세스가 페이지 스와핑(page in and out) 작업으로 본 일을 해야하는 프로세스가 멈춰있을 수 있다.

충분한 페이지가 없다면 page-fault 비율이 매우 높아질 것이다. 이에 따라 degree of multiprogramming 또한 높아지며 CPU 사용량이 올라가는데, 어느 순간 Thrashing이 발생하면서 CPU 활용이 떨어지게 된다. 

이 현상이 발생한 경우 방안으로 Working-Set Model이 있다.

Working-Set Model

• based on the assumption of locality
• working-set window를 델타 크기만큼 지정하고 해당 working set 안으로 들어오는 page 대신, 그 밖에 있는 page를 victim으로 삼으면 page fault가 줄 것
  • working-set : 최근 페이지 레퍼런스
• 페이지가 active use라면 working set에 있음 
• 더이상 사용 안하면 working set에 drop

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

Background

• 프로세스 = 실행 중인 프로그램으로, 메인 메모리에 로드되어 있는 상태
• 메모리 = large byte의 배열로 구성, 각 바이트에 주소 저장
• CPU = 프로그램 카운터가 지정한 주소에서 명령을 가져와 실행, 명령어에서 load나 store 같이 메모리에 접근하는 연산을 수행

Memory Space

멀티프로그래밍 및 멀티프로세서 환경에서는 메모리에 각 프로세스가 자신들의 메모리 공간을 사용하고 있다는 점이 중요하다.

• 메모리 주소 공간을 따로따로 관리해야하는게 멀티 프로세싱의 목적 ⇒ base resigter & limit register가 필요
  
  • 특정 메모리 주소에 접근하고자 할 때 주소가 base와 limit 사이에 존재하는 합법적인 주소 접근일 때만 접근 가능
  • 잘못된 접근인 경우 세그멘테이션 오류 (segmentation fault)가 발생하여 프로그램 중단

Address Binding

프로그램은 실행되기 전까지 단지 디스크에 저장되어있는 이진 실행파일에 불과하다. 실행을 위해 메인 메모리에 올라가면 비로소 프로세스가 된다.

• 프로그램에서 주소를 다루는 방식은 단계별로 다름
• binary executable file로 디스크에 프로그램이 저장
• 실행시키기 위해 프로그램을 메모리로 가져옴
  • 프로세스의 주소는 OS커널에서 지정하기 때문에 00000000주소에서 시작 되지 않음
  • 컴파일러는 프로그래머가 symbolic하게 작성한 소스코드 내 주소를 재배치 가능한 주소에 바인딩 
• 소스 코드 단계 (symbolic한 코드) → 컴파일 (재배치 가능한 주소) → 링커 (논리적 주소) → 로더 (물리적 주소)
  ⇒ 각 단계마다 다른 주소 바인딩이 이뤄짐

논리 주소 공간 vs 물리 주소 공간

• 논리주소 (logical address) : 사용자 프로세스에서 사용하기 위해 CPU에서 생성된 주소
• 물리주소 (physical address): 실제 하드웨어 상의 주소, 메모리 유닛에 의해 보이는 주소
  논리 주소와는 아무런 관계가 없어야 하며, 메모리 주소 레지스터 (memory-address register)에 저장되는 주소

논리 주소를 물리 주소에 매핑하기 위해서 논리 주소 공간과 물리 주소 공간이 분리되어야 한다.

MMU (Memory Management Unit)

• 논리 주소를 물리 주소로 map하는 하드웨어 장치
• 재배치 레지스터 relocation register 존재 (Base register in MMU)

Dynamic Loading

• 전체 프로그램과 데이터가 물리적 메모리에 있는게 필수인가?
• 메모리 주소 공간을 효율적으로 쓰기 위해 필요할때만 routine 호출하는 프로그램
• 재배치 가능한 링킹 로더 lining loader가 필요할 때마다 호출되어 주소 테이블(address table)에 변화 반영

동적 링킹(Dynamic Linking) & 공유 라이브러리(Shared Libraries)

• DLLs (Dynamically Linked Libraries)
  • 프로그램 실행 중간에 유저 프로그램이 링킹되어 사용할 수 있는 시스템 라이브러리
  • 실행 시 한번에 링킹되지 않고 라이브러리만 로딩된 상태에서 필요할 때 링킹됨
  • 공유 라이브러리 shared library로 부르기도 함
• 정적 링킹 static linking : 시스템 라이브러리가 다른 오브젝트 모듈처럼 한꺼번에 로더에 의해 이진 프로그램 코드로 합쳐짐
• 동적 링킹 dynamic linking : 동적 로딩과 비슷하게 링킹 작업을 실행 시간 (execution time)에 수행하는 것

Contiguous Memory Allocation

• 여러 사용자 프로세스에 동시에 메모리 있을 수 있기에 사용 가능한 메모리 할당해야함
• 연속 메모리 할당 ⇒ 단일 구역 (single section)에 할당하는 방식 (한 구역에 할당되어 있으므로 연속적임)
• 메모리 보호 ⇒ 재배치 레지스터와 한계 레지스터를 통해 이뤄짐

프로세스의 할당 & 해제를 반복하다보면 빈 공간이 생기는데, 이를 구멍 (hole)이라고 한다. 구멍을 잘 관리하는 것이 중요한데, 저장 공간에 동적으로 메모리를 할당 시 크기 n만큼의 메모리를 어느 구멍에 할당할지에 대한 문제가 발생한다.

3가지 해결 방법

1. 최초 적합 (first-fit): 구멍들을 탐색하다가 할당할 수 있는 가장 첫 번째 구멍에 할당하는 것
2. 최적 적합 (best-fit): 할당할 수 있는 가장 작은 구멍에 할당하는 것 (구멍들의 리스트를 우선순위 큐로 구현)
3. 최악 적합 (worst-fit): 할당할 수 있는 가장 큰 구멍에 할당하는 것

Fragmentation 단편화 문제

• 외부 단편화 (external fragmentation)
  • 많은 수의 작은 구멍로 메모리가 단편화됨
  • 메모리 공간이 조각조각 나눠져 있어 메모리 할당 요청을 받을 수 없는 상태
• 내부 단편화 (internal fragmentation)
  • 빈 공간에 메모리를 할당하고 난 뒤 공간이 남아 다른 메모리를 할당할 수 없는 상태

페이징을 하면 내부 단편화 문제가, 연속 메모리 할당을 하면 외부 단편화 문제가 발생한다.

Paging

프로세스의 물리적 주소 공간을 불연속적 (non-contiguous)으로 나눠 관리하는 것이다.

외부 단편화 문제를 해결할 수 있으며, 여러 곳에 나눠져 있는 공간을 압축할 필요도 없다. 메모리 할당과 관련된 부분이기 때문에 OS와 하드웨어의 도움을 받아 구현해야 한다.

Basic Method

• 물리 주소를 fixed-sized block으로 부서짐 (frames)
• 논리 주소를 같은 사이즈의 block으로 부숨 (pages)
• 논리 주소를 물리적 주소와 분리
• 논리 메모리에 있는 프로그램을 물리 메모리에 올릴 때 연속 할당처럼 메모리 조각을 물리 메모리의 위치에 맞게 올리기

기본적인 paging 방법

• 주소를 넘겨줄 때 페이지 번호, 오프셋을 넘겨줌
  • page number (p)
  • page offset (d)

→ p 페이지에 있는 d번째 메모리에 할당해줘

프로세스마다 페이지 개수가 다르기에 페이지 테이블을 통해 관리해야 한다.

CPU에 의해 이뤄지는 단계 

• CPU는 논리 주소로부터 페이지 번호(p)를 얻어 이에 해당하는 프레임 번호(f)로 변환
• 그 결과 논리 주소가 물리 주소로 매핑됨

페이지 사이즈 (like frame size)

• 하드웨어에 의해 정해짐
• 논리 주소 : 2^m, 페이지 사이즈 : 2^n
  • high-order 페이지 개수는 m-n bits
  • low-order 페이지 크기는 n bit

페이지 테이블의 경우 프로그램의 크기가 다양하고 커지면서 더이상 하드웨어만으로 페이지 테이블을 관리하는 것이 어려워졌다.  PTBR (page-table base register)을 따로 만들어서 페이지 테이블의 시작 주소를 가리키게끔 한다.

• 페이지 테이블에서 시작
• 페이지 테이블이 메인 메모리에 있음
• 컨텍스트 전환 빠르지만 메모리 접근 시간 느림

Translation Look-aside Buffer(TLB)

• CPU에서 페이지 테이블에 바로 접근하기보다는 TLB를 중간에 거쳐서 접근
• 캐시 메모리기에 매우 빠른 속도로 메모리 접근 가능
• TLB hit : 캐시 메모리에 페이지 번호 O
  발생시 빠르게 하드웨어적으로 물리 주소로 변환
• TLB miss : 캐시 메모리에 페이지 번호 X
  발생시 페이지 테이블에서 실제 값을 찾아 물리 주소로 변환
• hit ratio : 페이지 넘버 수 

TLB hit가 얼마나 발생했는지에 따른 hit ratio에 따라 유효 메모리 접근 시간 (effective memory-access time)이 달라진다.

Memory Protection with Paging

• 페이징을 사용할 경우 보호 비트 (protection bit)를 통해 프레임별로 메모리를 보호
• 하드웨어적으로 유효-무효 비트 (valid-invalid bit)를 각 프레임에 추가하여 메모리 접근이 유효한 접근인지 확인
  • 유효한 비트라면 합법한 페이지
  • 무효한 비트라면 불법한 페이지 → 트랩 (인터럽트)를 걸어버림 

Structure of the Page Table

현대적인 시스템의 경우 논리 주소 공간이 매우 크기 때문에 페이지 테이블 또한 매우 크다. 따라서 페이지 테이블을 구조화하는 것이 필요하다.

1. 계층적 페이징 Hierarchical Paging

• 페이지 테이블의 페이지 테이블을 만들어 관리
• 페이지 테이블 자체가 너무 커서 묶어서 관리하는 방법

2. 해시 페이지 테이블 Hashed Page Table

• 해싱을 하드웨어적으로 구현한 테이블
• 논리 주소의 p, d 값을 해시 함수를 통해 해시 값을 생성한 뒤, 이를 물리 주소의 값으로 사용하여 매핑
• 주소 공간의 크기가 32 bit를 넘어갈 때 자주 사용

3. 역 페이지 테이블 Inverted Page Table

• 프로세스의 주소를 통해 페이지 테이블에 접근하는 방식을 역으로 적용
• pid (process identifier)를 추가하여 해당 pid의 페이지를 역으로 저장

Swapping

• 물리 주소 공간 크기보다 초과하는 경우 스와핑을 사용해 문제 없이 실행
• 하나의 페이지만 메모리에 올라가면 되므로 프로세스 동시 실행 가능 → multiprogramming 의 차수를 증가
• 메모리에 엑세스할 때만 지원

표준 스와핑 Standard Swapping

• 전체 프로세스를 메인 메모리와 보조 기억장치 (backing store) 사이로 이동시킴
• swap out & swap in
  • swap out : 메인 메모리 → 보조 기억장치
  • swap in : 보조 기억 장치 → 메인 메모
• 전체 프로세스를 swap하는 비용 & 부담이 큰 작업 

페이징을 통한 스와핑 Swapping with Paging

• 프로세스를 페이지 단위로 swap
• 오늘날 페이징 = swapping with paging
• swap in, swap out 대신 page in, page out (페이지 단위) 
• paging은 가상 메모리에서 잘 쓰임

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

System Model

Multiprogramming 환경에서는 여러 스레드들이 유한한 자원을 두고 경쟁하며 스레드에 분배한다. 

스레드가 다른 대기 중인 스레드가 점유 중인 자원을 요청해 waiting state인 경우가 계속 발생할 수 있다.

이처럼 데드락은 모든 프로세스들이 다른 프로세스의 이벤트를 대기하고 있을 때를 말한다.

• 시스템 모델에서 한정된 리소스로 구성된 시스템을 여러 스레드로 공유해야함
• 리소스 타입은 여러 개의 동일한 인스턴스 타입으로 구성 : e.g., CPU cycles, files, and I/O devices(such as printers, drive, etc.)
• 스레드(혹은 프로세스)가 어떤 리소스의 한 인스턴스를 요청시 동일 리소스의 인스턴스를 할당하여 요청을 충족
  • 리소스의 타입이 중요하고, 안의 인스턴스의 개수는 중요하지 않음
• 스레드가 리소스를 실행할 때 과정
  ⇒ Request(요청) → Use(사용) → Release(해방)

Deadlock in Multithreaed Applications

스레드 실행 순서에 따라 데드락이 안 일어 날 수 있다.

스레드2가 lock을 획득하기 전, 스레드1이 mutex1, mutex2에 대한 lock을 획득하고 해제한다.

그러나 특정 스케줄링 상황에서만 발생하는 데드락에 대한 식별과 검사는 어렵다.

Deadlock Characterization

데드락을 발생시키기 위해 특정 짓는 네 가지 조건이 있다.

1. Mutal Exclusion (상호 배제)

• 어떤 리소스에 접근할 때 순간적으로 하나의 프로세스만 접근할 수 있음
• 적어도 하나의 리소스가 non-sharable mode

2. Hold and Wait (점유 후 대기)

• 프로세스는 적어도 하나의 리소스를 점유하고 있고 다른 스레드의 추가 리소스 획득을 대기하고 있음
• 프로세스가 리소스를 점유하고 있지 않으면, 애초에 데드락이 일어나지 않음.

3. No preemption (선점 불가)

• 리소스는 선점될 수 없음
• 선점이 되어버리면 프로세스가 실행을 종료하니 데드락이 일어나지 않음

4. Circular Wait (순환 대기)

• 프로세스가 순환적으로 서로를 기다리고 있음
• 스레드 circular RAP
• T0 → T1 → T2 → ... → Tn → T0

Resource-Allocation Graph(RAP)

• 데드락을 정확하게 묘사한 단방향 그래프
• 각 정점을 V 라고 칭하며 V에는 두 가지 타입 존재
  
  • T : 스레드 집합
  •  R : 리소스 집합
• 각 간선은 E 라고 칭하며 두 가지 타입 존재
  
  • Ti → Ri (Request edge) Ti가 Ri를 요청
  • Ri → Ti (assignment edge) Rj가 Ti에 할당됨

• 왼쪽 그림 : 순환 대기로 데드락이 일어나지 않은 상황 (만약 그래프 내 사이클이 있다면 데드락 가능성 O)
  • 인스턴스가 하나인 경우 → 사이클은 데드락 의미
  • 인스턴스가 여러 개인 경우 → 사이클이 데드락 의미 X
• 오른쪽 그림 : T3가 R2에게 리소스를 요청하면서 데드락 발생
  • T1, T2, T3간 데드락 발생

• T1과 T3 사이 사이클이 존재하지만 R2의 인스턴스는 2개
  → T4가 작업을 완료하고 리소스를 놓아주면 T3가 R2에 접근할 수 있으므로 데드락 발생하지 않음

RAP에서 사이클을 그리지 않으면 데드락은 절대 발생하지 않는다.

사이클이 발생한다고 해서 데드락이 무조건 발생하는 것은 아니다.

Methods for Handling Deadlocks

1. 문제 발생 무시 (발생하지 않을 것이라고 가정)

2. 데드락을 방지/회피하기 위한 프로토콜 사용

• 프로토콜을 이용하여 어떤 상황에서도 데드락에 빠지지 않게 설정
  • Deadlock prevention
  • Deadlock avoidance

3. 시스템이 데드락 상황에 빠진 것을 확인했을 때 회복

• Deadlock detection
• Deadlock recovery

Deadlock Prevention

• 데드락을 완전히 방지하는 방법
• 데드락 발생의 네 가지 조건 중 하나를 완전히 해결해 데드락을 예방하는 방법

1. Mutual Exclusion

• 리소스가 공유할 수 있도록 함
• 특정 자원은 근본적으로 공유가 불가능하므로 현실적으로 어려움

2. Hold and Wait

• 프로세스가 리소스를 점유하고 있지 못하게 하는 방법
• Hold와 Wait을 동시에 하지 않도록 함
• 프로세스가 리소스를 요청할 때, 가지고 있는 리소스를 모두 내려놓고 리소스를 요청하고, 이후 획득시 가지고 있던 리소스 다시 요청
  • Resource utilization 저하
  • Starvation 발생 가능

3. No preemption

• 다른 프로세스가 리소스를 점유하고 있을 때 해당 리소스 빼앗을 수 있음
• 선점당한 프로세스는 어떤 작업을 하든 waiting 상태로 전환
• 이전 리소스와 새 리소스를 되찾아야 이전 프로세스 실행 가능

4. Circular Wait

• 4가지 방법 중 가장 실용적
• 리소스에 순서를 부여하여 오름차순으로 리소스를 할당하는 방법
• 우선순위를 부여하는 것과 마찬가지로 기아 상태가 발생할 가능성 존재

Deadlock Avoidance

데드락 방지를 사용하면 디바이스 사용률이 낮아지고, 시스템의 처리량이 감소할 위험이 높아지며 멀티 스레딩으로 얻은 장점이 사라진다.

이를 피하기 위해 데드락 회피 방법을 사용한다.

프로세스들에 배분할 수 있는 자원의 양을 고려해 데드락이 발생하지 않을 정도로 자원을 배분하는 방법이다.

• 프로세스의 리소스 요청을 받을 때 시스템은 발생 가능한 데드락이 있는지 먼저 확인
• 데드락이 발생하지 않으면 리소스 요청 허용O, 데드락이 발생하면 요청 허용X
• 얼만큼의 리소스 양이 필요하며 어느 타입의 리소스 요구되는지?
  ⇒ 필요한 정보의 양과 유형에 따라 다양한 회피 알고리즘 존재

Safe State

• 시스템이 특정 순서대로 스레드에 리소스를 할당하고 데드락도 발생하지 않는 상태
  • 해당 순서 : 안전 배열(safe sequence)
  • 안전 배열이 있으면 시스템은 safe state(not deadlock state)
• 데드락을 회피하기 위해서는 알고리즘을 이용하여 안전하지 않은 상태에서 안전한 상태로 이동할 수 없게 설정
• 안전한 상태의 스레드는 계속해서 안전한 상태로 머물러야 함

Resource-Allocation-Graph Algorithm

• 각 리소스 유형의 인스턴스가 한 개만 존재할 때
• 새로운 간선을 그릴 때 실선이 아닌 점선 → 클레임 엣지(claim edge) (스레드가 나중에 리소스를 요청할 수 있음)
• 점선을 이용하여 선을 그렸을 때 사이클이 일어나지 않는지 확인
  → 사이클이 그려지지 않으면 안전 상태로 판단
  → 사이클이 그려지면 안전하지 않은 상태로 판단
• 사이클이 발견되면 스레드는 요청이 충족될 때까지 wait

Banker's Algorithm

• RAG는 multiple instance에 사용못하기에 은행원 알고리즘 사용
  • 여러 인스턴스가 있을 때 데드락 회피를 위한 방법으로 적합
  • RAG에 비해 복잡하고 효율이 떨어짐
• 리소스의 최대 개수를 할당해도 안전한 상태가 유지되는지 확인
• 안전하지 않은 상태면 다른 스레드가 자원 해제할 때까지 wait

Data structures for Banker's Algorithm

• n : 시스템에 있는 스레드의 수
• m : 시스템에 있는 리소스의 수
• Available : 사용 가능한 리소스의 인스턴스 수
• Max : 각 스레드가 요청할 인스턴스의 최대 수
• Allocation : 각 스레드에 할당된 리소스의 수 
• Need : 앞으로 요청할 리소스의 수
• Request : 스레드가 요청한 리소스의 수 

Safety Algorithm

1. Work, Finish 벡터를 아래와 같이 초기화한다.
	Work = Available, Finish[i] = false
    
2. 아래의 두 조건을 만족하는 인덱스를 찾는다.
	Finish[i] == false, Need[i] <= Work
	만족하는게 없다면 4번으로 간다.
	조건을 만족한다면 아래를 실행한다.

3. Work = Work + Allocation[i]
	Finish[i] = true
	다시 2번으로 돌아가 끝날 때까지 반복한다.
    
4. 만약 Finish[i]가 모두 true라면, 안전한 상태라는 의미이다.

Resource - Request Algorithm

1. Request[i] <= Need[i] 이면 2번으로 간다.
	반대의 경우 최초 등록한 Max 보다 더 많은 양의 리소스를 요청했다는 것을 의미한다.
    
2. Request[i] <= Available[i] 이면 3번으로 간다.
	반대의 경우 할당 가능한 인스턴스의 양보다 요청 양이 더 많다는 것을 의미한다.

3. 요청을 받아주며 아래의 식을 적용한다.
	Allocation[i] = Allocation[i] + Request[i];
	Available = Available - Request[i];
	Need[i] = Need[i] - Request[i];

4. 이 후 다시 위의 안전 알고리즘을 적용하여 안전한 상태라면 리소스를 완전히 할당한다.

Deadlock Detection

• 데드락이 일어났는지 확인하기 위한 시스템 상태를 검사하는 알고리즘
• 데드락을 허용하고 발생하는지 감시하고, 데드락에 빠지면 그 때 복구

Single Instance of Each Resource Type

• 리소스에 인스턴스가 1개 있는 경우에는 위의 RAG를 변형한 wait-for graph 사용
• 주기적으로 알고리즘을 실행하여 사이클이 있는지 확인
• 그래프에서 리소스를 제외

Several Instances of a Resource Type

• 은행원 알고리즘을 변형하여 데드락 탐지

1. Work = Available 로 초기화하고, Allocation[i] 가 0이면 Finish[i] 를 true로 설정한다.

2. 아래의 두 조건을 만족하는 스레드를 찾는다.
	Finish[i] == false, Request[i] <= Work
	마찬가지로 조건에 만족하는 스레드가 없다면 4번으로 간다.
    
3. 아래의 두 연산을 실행한다.
	Work = Work + Allocation[i], Finish[i] == true
    
4. Finish[i] == false 이면 해당 스레드는 데드락이 발생한 상태임을 의미한다.

Recovery from Deadlock

데드락 발생을 확인한 후 처리할 복구 작업이 여러 가지 있다.

1. Process and Thread Termination

• 데드락에 걸린 모든 프로세스를 종료하는 방법
• 오래 실행되던 프로세스 중지되고 나중에 다시 실행

2. Resource Preemption

• Selecting a victim : 희생할 리소스를 선점(비용 최소화)
• Rollback :요청한 스레드에 주고 안전한 상태로 후퇴 후 다시 시작
• Starvation : 동일 프로세스가 항상 선점되지 않도록 보장 

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

Classic Problems of Synchronization

다수 동시성 제어의 고전적 문제

• Bounded-Buffer Problem (유한 버퍼 문제)
• Readers-Writers Problem (읽기 쓰기 문제)
• Dining-Philosophers Problem (철학자들의 저녁식사 문제)

1. Bounded-Buffer Problem

Producer-Consumer 문제

• 각각 하나의 항목을 보유할 수 있는 n개의 버퍼와 상호배제를 제공하는 이진 semaphore로 구성된 풀이 있다고 가정
• 생산자는 소비자를 위해 버퍼를 가득 채워야 함
• 소비자는 생산자를 위해 버퍼를 비워야 함

생산자 프로세스 코드

while (true) {
    /* produce an item in next produced */
    wait(empty);
    wait(mutex);
    /* add next produced to the buffer */
    signal(mutex);
    signal(full;
}

• empty 세마포가 0보다 클 때 (빈 공간이 있을 때) 
• mutex가 존재할 때 (락을 얻을 수 있을 때) 

임계구역에 진입해서 버퍼에 데이터를 입력할 수 있다.

소비자 프로세스 코드

while (true) {
    wait(full);
    wait(mutex);
    /* remove an item from buffer to next consumed */
    signal(mutex);
    signal(empty);
    /* consume the item in next consumed */
}

• full 세마포가 0보다 클 때 (버퍼에 데이터가 있을 때)
• mutex가 존재할 때 (락을 얻을 수 있을 때) 

임계구역에 진입해서 버퍼를 소비할 수 있다.

Readers-Writers Problem

공유되는 DB에서 readers와 writers process가 있을 때, reader는 동시 접근이 가능하지만 writer는 동시 접근 시 문제가 된다.

따라서 writer는 쓰기 시 데이터베이스에 대해 배타적 접근 권한을 가져야 한다.

1. 우선 순위 활용

• first readers-writers problem reader에게 우선 순위를 준다 ⇒ writer에서 starvation 발생 가능
• seconde readers-writers problem
• writer에게 우선 순위를 준다 ⇒ reader에게 starvation 발생 가능

⇒ 두 case 모두 starvation이 발생하기에, semaphore를 이용해 문제를 해결한다.

2. first readers-writers problem with semaphore

• Reader process는 자신 이외의 reader process가 종료되기 전까지 wait() 을 호출할 수 없음
• 즉, Writer 프로세스는 Reader 프로세스 모두가 종료될 때까지 대기함을 의미
  ⇒ Reader 프로세스가 계속해서 물밀듯이 들어오면 writer 프로세스는 기아(Starvation) 상태에 빠질 수 있음

2. Second readers-writers problem with semaphore

• 만약 writer 프로세스가 오브젝트에 접근하면, 새로운 reader 프로세스는 실행할 수 없음
  • writer 프로세스에게 우선 순위를 높게 주어 먼저 실행하게 만드는 것
  • 또한 writer 프로세스가 물밀듯이 들어올 경우 reader 프로세스가 기아 상태에 빠질 수 있음

첫번째 readers-writers problem (독자에게 우선권을 주는 문제)에 대해 더 알아보자.

semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0; // reader의 개수

• rw_mutex : reader, writer 사이의 상호 배제를 위해 사용됨
• mutex : 공유 변수인 read_count에 대한 상호 배제를 위해 사용
• read_count : 얼마나 많은 프로세스가 읽고 있는지 나타내기 위해 사용
  read_count = 0 → writer 프로세스 진입

while(true) {

    wait(rw_mutex); // 독자로부터 신호가 오면 진입
    
    /* writing is performed */
    
    signal(rw_mutex);
}

while(true) {

    wait(mutex); // 공유 자원 접근을 위한 요청
	read_count++; // 읽고 있는 프로세스의 수 더하기
    if(read_count == 1)
    	wait(rw_mutex); // 독자 프로세스는 여러 프로세스가 진입이 가능하다.
    signal(mutex);
    
    /* reading is performed */
    
    wait(mutex); // 공유 자원 접근을 위한 요청
    read_count --;
    if (read_count == 0)
    	signal(rw_mutex);    
    signal(mutex); 
}

• Writer 프로세스가 임계 영역에 접근하면 많은 Reader 프로세스는 waiting 상태에 빠짐
• 한 개의 Reader 프로세스는 rw_mutex에서, 나머지 독자 프로세스는 mutex에서 대기
• Writer가 signal(rw_mutex) 연산을 실행할 때 대기중인 Writer/Reader 프로세스 실행 여부는스케줄러에 의해 결정
• 어떤 프로세스의 우선 순위를 높이느냐에 따라 해결책이 갈림
  ⇒ 독자 프로세스의 우선 순위를 높인다면 첫번째 방법, 작가 프로세스의 우선 순위를 높인다면 두번째 방법이 될 것이다.

Dining-Philosophers Problem

테이블에 앉은 철학자는 자신의 양쪽에 놓인 젓가락을 집어야 식사를 할 수 있다.

철학자들에게 제공된 젓가락은 딱 다섯 개이다.

철학자들은 배가 고파지면 두 개의 젓가락이 있어야 음식을 먹을 수 있다.

만약 인접한 철학자가 동시에 배고파지면, 한 철학자는 젓가락을 못잡을 것이다.

이 상황은 여러 자원을 여러 프로세스가 공유하고 있는 상황으로, 모두가 아무 것도 할 수 없는 deadlock 상황(교착 상태)이 발생한다.

(철학자 = process, 젓가락 = resource)

Semaphore Solution

while (true) {
    wait (chopstick[i]); // Left
    wait (chopstick[(i+1) % 5]); // Right
    
    /* eat for a while */
	
    signal (chopstick[i]);
    signal (chopstick[(i+1) % 5]);
    
    /* think for a while */
}

• 각 젓가락에 세마포어를 부여해주는 방식
• 철학자들은 젓가락을 잡을 때 wait() 연산, 젓가락을 놓을 때 signal() 연산을 실행하여 상호 배제 보장
• 5명의 철학자가 동시에 배고파지기라도 하면, 그 누구도 양쪽의 젓가락을 집을 수 없음
  ⇒ 데드락과 기아 문제를 해결하지 못한 방법

해결 방법

(1) 최대 4명만 동시에 앉음

(2) 양쪽 젓가락이 가용할 때만 집도록 허용

(3) 비대칭 방법 ⇒ 홀수/짝수 번호별로 다르게 동작

Monitor Solution

• 모니터를 이용해 해결하는 방법
• 철학자들은 양쪽의 젓가락이 모두 놓여져 있을 때 젓가락을 집음
• 철학자들의 상태를 3가지로 구분

enum {THINKING, HUNGRY, EATING} state[5];

• 이웃들이 Eating이 아닐 때 Eating 상태가 될 수 있다.

(state[i+4)%5] != EATING) and (state[(i+1) % 5] != EATING)

한 철학자가 음식을 먹으려면, 인접한 두 철학자가 eating 상태가 아니어야 한다.

또한, 상태 변수를 이용하여 철학자가 hungry 상태이지만 음식을 먹을 수 없을 때 스스로를 지연시키도록 한다.

class DiningPhilosopherMonitor {
    private int numOfPhils;
    private State[] state;
    private Condition[] self; // Condition Value
    private Lock lock;

    public DiningPhilosopherMonitor(int num) {
        numOfPhils = num;
        state = new State[num];
        self = new Condition[num];
        lock = new ReentrantLock();
        for (int i = 0; i < num; i++) {
            state[i] = State.THINKING;
            self[i] = lock.newCondition(); // Condition
        }
    }

    private int leftOf(int i) {
        return (i + numOfPhils - 1) % numOfPhils;
    }

    private int rightOf(int i) {
        return (i + 1) % numOfPhils;
    }

    private void test(int i) {
        if (state[i] == State.HUNGRY && state[leftOf(i)] != State.EATING && state[rightOf(i)] != State.EATING) {
            state[i] = State.EATING;
            self[i].signal();
        }
    }

    public void pickup(int id) {
        lock.lock();
        try {
            state[id] = State.HUNGRY;
            test(id);
            if (state[id] != State.EATING) self[id].await();
        } catch (InterruptedException e) {

        } finally {
            lock.unlock();
        }
    }

    public void putdown(int id) {
        lock.lock();
        try {
            state[id] = State.THINKING;
            test(leftOf(id));
            test(rightOf(id));

        } finally {
            lock.unlock();
        }
    }
}

• monitor인 DiningPhilosopher에 의해 젓가락의 분배가 이뤄짐

DiningPhilosophers.pickup(i);
	...
   	eat
    ...
DiningPhilosophers.putdown(i);

• 이웃한 두 사람이 동시에 식사하지 않고 deadlock이 일어나지 않음을 보장
• 그러나 starvation이 발생할 수 있음

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

Background

CPU 스케줄러가 프로세스 사이를 오가며 모든 프로세스를 병행 실행시킨다.

이것은 한 프로세스가 다른 프로세스가 스케줄 되기 전에 일부분만 진행한다는 것을 의미하는데, 한 변수에 서로 의존하는 경우 값이 변경되면 무결성을 해치는 상황이 된다. 

협력 프로세스(Cooperating Process)

Cooperating process 간 비동기적 실행, 데이터 공유로 인한 무결성 문제를 해결해야 한다.

• 서로에게 영향 주고 받음
• 논리적 주소 공간을 공유하거나 데이터를 서로에게 공유 가능
• 공유 데이터에 동시 접근하는 것은 데이터 불일치 야기
• 협력 프로세스에서는 순서대로 실행할 수 있게끔 설정하는 것이 중요
• 순서대로 실행한다면 논리적 주소 공간에서의 데이터 일관성을 유지 가능

Race Condition (경쟁 상황)

이처럼 동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황이라고 한다.

• 실행의 결과는 어떤 순서에 따라 접근되는지에 따라 결정됨
• 오로지 하나의 포르세스가 특정 시간에 공유 데이터를 다룰 수 있게끔 설정해야 함
  • 이를 보장하기 위해 프로세스가 어떤 식으로든 동기화되어 있어야 함

경쟁 상황이 생기지 않도록 하나의 프로세스만이 자료를 조작하도록 보장해야한다. 이런 보장을 위해 프로세스들을 동기화할 필요가 있다.

Critical Section Problem (임계 구역 문제)

프로세스 동기화에 관한 논의는 임계구역 문제로부터 시작한다.

각 프로세스는 임계구역이라는 코드 부분이 존재하고, 임계구역 코드 안에서는 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있다. 

• 시스템에 n개의 프로세스가 구성되어 있다고 가정했을 때 각각 프로세스의 코드 영역 → 크리티컬 섹션
• 프로세스가 하나 이상의 다른 프로세스와 공유되는 데이터에 액세스하고 업데이트 가능
• 하나의 프로세스가 크리티컬 섹션을 실행중일 때 다른 프로세스는 크리티컬 섹션에 진입할 수 없게 설정하는 것이 시스템의 중요한 특징 중 하나

Critical-Section Problem 해결 방안

1. 상호 배제 (mutual exclusion)

• 임계구역 하나당 하나의 프로세스만 실행

2. 진행 (progress)

• 현재 임계구역에서 실행 중인 프로세스가 없는데 임계구역에서 실행하려는 프로세스를 막아서는 안됨
• 데드락 방지하기 위한 요구사항
• 아무도 크리티컬 섹션에 진입하지 못하는 상황은 없어야 함

3. 한정된 대기 (bounded waiting)

• 어떤 프로세스가 임계구역으로 들어가고자 하면 기다리는 시간에 대해 bound가 있어야 함
• 기아 상황 방지하기 위한 요구사항
• 동일 프로세스가 독점할 수 없게끔 함

Peterson's Solution

임계구역 문제를 해결하는 소프트웨어적 방법 중 하나이다.

임계구역과 나머지 구역을 번갈아가며 실행하는 두 개의 프로세스로 한정하고 두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결한다.

• 상호 배제, 진전, 한정 대기, 세 가지 요구 사항을 모두 충족하는 알고리즘
• turn과 flag 변수로 크리티컬 섹션에 진입할 프로세스 혹은 스레드를 결정
  • turn : 누가 임계구역에 들어갈 차례인지 표시
  • flag : 임계구역에 들어갈 준비가 되었다는 의사 표시

int turn; // 임계구역으로 진입할 프로세스
boolean flag[2]; // 프로세스가 입계구역으로 진입할 준비가 됐으면 1

임계구역에 진입하기 위해서 P[i]는 먼저 flag[i]를 참으로 만들고, turn을 j로 지정한다.

이렇게 하여 프로세스 j가 임계구역으로 진입하기를 원한다면 진입 가능하다는 것을 보장한다.

만약 두 프로세스가 동시에 진입하기 원해도 한 프로세스만 배정이 지속되기 때문에 turn의 값이 누가 먼저 임계구역으로 진입할 것인지 결정하게 된다.

while(True) {
	flag[i] = true;
    turn = j;
    while (flag[j] && turn == j)
    	;
        /* critical section */
    flag[i] = false;
    	/* remainder section */
}

이 해결책이 올바르게 동작하는지 증명하기 위해 아래와 같은 사실을 보이면 된다.

1. mutual exclution (상호 배제)가 제대로 지켜지는가?

→ 동시에 실행되지만 turn 값에 따라서 임계 구역에 한 process만 진입하고 있으므로 만족한다. 한 process가 CS에 있는 한, 조건이 변하지 않고 유지되므로 나머지 process는 무조건 대기해야 한다.

2. Progress에 대한 요구 조건을 만족하는가?

3. Bounded-waiting이 한없이 길어지지 않는가?

→ 프로세스 Pi는 while문에서 대기하면서 변수 값을 변경하지 않으므로, Pj가 CS를 나오면서 flag[j]를 false로 변경할 때 CS에 진입한다. (1회 대기 → bounded waiting)

→ Pj가 CS를 나오면 다음 CS 진입 process는 대기 중인 Pi가 된다. (Pj가 다시 진입 X → progress)

Peterson의 해결책은 최신 컴퓨터에서는 작동하지 않는다. 시스템 성능을 향상시키기 위해 종속성이 없는 읽기/쓰기 작업을 재정렬할 수 있기 때문이다.

또한 Instruction들의 재배치로 인해 제대로 실행함을 보장할 수 없다.

상호 배제를 유지하는 방법은 적절한 동기화 도구를 사용하는 것이다.

Hardware Support for Synchronization

하드웨어를 사용하여 Critical-Section problem을 해결할 수 있다.

1. Memory Barriers

메모리 장벽은 매우 낮은 수준의 연산으로 일반적으로 Mutual Exclusion 을 보장하는 특수 코드를 작성할 때 커널 개발자만 사용한다.

다음 명령 실행 전 모든 load와 store이 완료됨을 보장하고, reorder되더라도 후속 명령의 실행 전에 저장을 완료하고 그 결과를 모두에게 보여준다.

즉, 메모리 간 변경 사항을 전파해 명령어들의 순서를 보장한다.

2. Hardware Instructions - TAS, CAS

특별한 하드웨어 명령으로 원자성을 가진 명령을 추가하는 방법이다.

한 워드의 내용을 검사하고 변경하거나 두 워드의 내용을 원자적으로 교환할 수 있게 한다.

즉, 인터럽트 할 수 없는 하나의 단위로 간단하게 크리티컬 섹션을 해결할 수 있다.

• test_and_set() : 제일 처음 process만 CS에 진입하도록 함 
• compare_and_swap() : swapping에 기반하여 two words에 atomic하게 동작하도록 함

example code test_and_set

boolean test_and_set(boolean *target) {
    	boolean rv = *target;
        *target = true;
        
        return tv;
    }
    
    do {
    	while (test_and_set(&lock)); /* do nothing, context switching X */
		// 본인의 lock 을 true 로 만들고 진입한다.
        
		/* critical section */
        
        lock = false; // 크리티컬 섹션을 빠져나온 후 false로 만들어 다른 프로세스 진입을 허용
        
        /* remainer section */
    	
    } while (true);

example code compare_and_swap

int compare_and_swap(int *value, int expected, int new_value) {
    	int temp = *value;
        
        if (*value == expected)
        	*value = new_value;
          
        return tmp;
    }
    
    while (true) {
    	while (compare_and_swap(&lock, 0, 1) != 0);
        /* do nothing */
        
        /* critical section */
        
        lock = 0;
        
        /* remainer section */

3. Atomic Variables

원자적 변수는 기본 데이터 타입(integer, boolean)에 대해 원자적 연산을 제공한다.

경쟁 상황(race condition)이 일어나는 단일 변수에 대해 상호배제(mutual exclusion)를 보장해준다.

원자적 변수를 지원하는 시스템은 원자적 변수에 접근하고 조작하기 위한 기능뿐 아니라 특별한 원자적 데이터 유형을 제공한다.

Mutex Locks

임계구역 문제를 해결하기 위해 상위 수준의 소프트웨어 도구 중 가장 간단한 것이 Mutex Locks이다.

Mutex Locks는 Mutual exclusion으로, 임계구역을 보호하고 경쟁 조건을 방지하기 위해 사용한다.

즉 프로세스는 임계 구역에 들어가기 전에 반드시 lock을 획득해야 하고, 임계구역을 빠져나올 때 lock을 반환해야 한다. 여기서 lock을 획득하는 함수는 acquire()이고, lock을 반환하는 함수는 release()이다. 이 두 함수는 atomic하게 수행되어야 한다.

이 방식의 단점은 바쁜 대기(busy waiting)을 해야 한다.

한 프로세스가 임계 구역에 있는 동안 나머지 프로세스는 계속 조건을 확인하며 loop를 실행해야 한다. 이로 인해 CPU가 낭비된다.

여기에 나온 Mutex Locks은 스핀락(spinlock)이라고도 하는데, 락을 사용할 수 있을 떄까지 프로세스가 회전한다.

이때 스핀락은 context switch이 필요하지 않다.

Semaphore

임계구역 문제를 해결하기 위해 상위 수준의 소프트웨어 도구 중 가장 간단한 것이 Mutex Locks이다.

Semaphore는 Mutex와 유사하게 동작하지만 프로세스들이 자신의 행동을 더 정교하게 동기화할 수 있는 방법을 제공한다.

Semaphore는 wait()(STOP)과 signal()(GO)를 통해 process가 critical section에 진입하는 것을 관리한다.

이는 정수형 변수, 초기화를 제외하고 두 표준 atomic 연산으로만 접근된다. (wait, signal)

• 공유 자원이 여러 개 있는 상황에서도 적용 가능한 synchronization tool
• 여러 개의 process가 각각 공유 자원에 접근 가능
• binary semaphore & counting semaphore
  • S : 임계 구역에 진입할 수 있는 process 개수 (사용 가능한 공유 자원의 개수)
  • signal() : 임계 구역 앞에서 기다리는 process에게 '이제 가도 좋다'고 신호를 주는 함수
  • wait() : 임계 구역에 들어가도 좋은지, 기다려야 할지 알려주는 함수

wait(S) {
	while (S <= 0)
    	; // busy wait
    S--;
}

signal(S) {
	S++;
}

→ wait()와 signal() 연산 시 세마포의 정수 값을 변경하는 연산은 반드시 원자적으로 수행되어야 한다. 

Semaphore Usage

Counting semaphore

• 값들은 제한 없는 영역을 가짐
• 공유 자원이 N 개인 경우 (0이면 unavailable) 가용한 자원의 수로 초기화
  • wait() 연산 수행하여 세마포 값 줄임
  • signal() 연산 수행하여 프로세스가 자원 방출할 때 세마포 값 증가
  • count == 0이면 자원 모두 사용됨
  • count ≤ 0이면 프로세스는 block됨 

Binary semaphore

• 0 또는 1의 값만 가능
• 공유 자원이 1개인 경우 mutex lock 대신 사용 가능

Semaphore Implementation

Mutex Locks과 마찬가지로 Semaphore 연산 wait()과 signal() 역시 바쁜 대기 문제(busy waiting)를 가지고 있다.

따라서 wait()과 signal()을 아래와 같이 수정해야 한다. 또한 semaphore를 새롭게 정의한다.

• wait() : semaphore 사용을 위해 기다리면 프로세스가 list에 추가됨
  • busy waiting 대신 프로세스가 스스로 suspend operation (sleep())을 통해 waiting queue로 이동하여 waiting state로 전환
  • 제어가 cpu 스케줄러로 이동 후 다음 프로세스 선택
• signal() : 기다리던 process를 리스트에서 제거하고 wakeup시킴
  • S를 기다리던 suspend된 프로세스는 다른 프로세스의 signal()(wakeup())로 ready state로 전환되어 restart됨 

Monitors

Semaphore는 프로세스 간의 동기화를 위해 편리하고 효과적으로 쓸 수 있지만, 잘못 사용하면 특정 실행 순서에만 발생하는 오류라 발견하기 어려운 타이밍 오류를 야기할 수 있다.

그리고 두 프로세스가 동시에 임계구역 안에 있는 문제도 발생할 수 있다.

• Timing errors in Semaphores : wait() → CS → signal() 순서로 진행되어야 하는데 프로세스 중 하나라도 순서를 지키지 않고 잘못 동작하는 경우 timing error가 발생
• Semaphore나 mutex lock을 잘못 사용하면 error가 매우 쉽게 발생하는 구조

이를 비롯한 다양한 오류가 쉽게 생길 수 있기에 간단한 동기화 도구를 통합하여 고급 언어 구조물을 제공하는 것이 바로 모니터다.

Monitor Usage

• monitor : 공유 자원과 공유 자원에 접근하기 위한 interface(통로)를 묶어서 관리
• monitor = 공유 자원 + 공유 자원 접근 함수 && 2개의 큐
  • mutual exclusion queue, conditional synchronization queue
  • 상호 배타 큐 : 공유 자원에 하나의 프로세스만 진입하도록 하기 위한 큐
  • 조건동기 큐 : 이미 공유 자원을 사용하고 있는 프로세스가 특정한 호출 wait()을 통해 조건동기 큐로 들어감 
• abstract data type (ADT) : 특정 구현과 무관한 데이터 및 연산을 캡슐화함
• "monitor는 ADT다" → instance의 state를 정의한 변수와 그 변수에 동작하는 함수 본체 선언
  • monitor type은 process가 직접 사용 금지 → interface 통해 접근 (캡슐화)
  • monitor 내에서 한번에 한 process만 active함을 보장
  • 동기화를 위해 직접 정의하여 condition 변수 사용 (process나 thread의 실행 순서 제어)

• x.wait()
  • 특정 process가 아직 실행될 조건이 되지 않았을 때 해당 process를 suspend함
  • 다른 process가 x.signal()을 호출하기 전까지 suspend됨
• x.signal()
  • 특정 process가 실행될 조건이 충족되었을 때 해당 process의 실행을 resume함

모니터 내 (P, Q)의 경쟁 해결방안

condition x와 관계되는 process P, Q가 있다고 할 때 P에서 x.signal()을 호출하면 condition x에 대해 기다리면서 Q는 suspend된다.

이때 Q가 resume된다면 P는 wait해야하고 만약 P가 wait하지 않으면 monitor 내 P, Q 두 개가 동시에 active된다.

해결방안

1. Signal and Wait (P가 대기)

P는 Q가 monitor를 떠날 때까지 wait한다. 혹은 다른 조건 y에 대해 wait한다.

2. Signal and Continue (Q가 대기)

Q는 P가 monitor를 떠날 때까지 wait한다. 혹은 다른 조건 y에 대해 wait한다.

3. 절충안

P가 signal()하고 즉시 monitor를 떠난 후 Q가 즉시 resume한다.

Liveness

synchronization tool의 사용 결과로 임계 구역에 들어가려는 process의 무한 대기가 발생할 가능성이 있다.

무한 대기는 progress와 bounded-waiting을 위반한다.

시스템은 progress를 보장해야한다.

• Liveness : system이 process의 progress를 보장하기 위해서는 만족해야 하는 property set
• Liveness failuere가 생기면 성능과 응답성이 안 좋아진다 

⇒ Deadlock, Priority Inversion

Deadlock

• 둘 이상의 process가 대기 중인 process 중 하나에 의해 일어나는 event를 무한히 기다리는 상황
• P0는 P1이 signal(S)하기를 기다리고, P1은 P0이 signal(Q)하기를 기다림

⇒ 둘 다 무한 대기

Deadlocked state (교착 상태) : set 내 모든 process가 다른 process에 의해 야기되는 이벤트를 기다림

Priority Inversion

• 높은 순위의 process가 낮은 순위의 process가 사용 중인 kernel data에 접근하는 경우에 발생
• kernel data는 lock으로 보호됨 → 높은 순위의 process가 대기해야 함

Priority-inheritance protocol

: 높은 순위 process가 필요로 하는 자원에 접근하는 모든 process는 자원의 사용이 끝날 때까지 높은 순위를 상속받고 종료 시 원래 우선 순위로 돌아감 

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

CPU Scheduling Basic Concepts

• 멀티 프로그래밍을 채택한 O/S에서는 기본적으로 사용
• 멀티 프로그래밍의 기본적인 목표
  • CPU 사용률을 최대화하기 위해 프로세스들을 concurrent하게 항상 실행
  • 한 프로세스가 wait할 경우 OS CPU를 뺏은 뒤 다른 프로세스에 할당

⇒ 프로세스는 I/O 요청을 위해 CPU 스케줄링이 필요

CPU I/O Burst 사이클 

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

프로세스 실행은 CPU 버스트(burst)로 시작되고 뒤이어 I/O 버스트가 발생한다.

마지막 CPU 버스트는 또 다른 I/O 버스트가 뒤따르는 대신 실행을 종료하기 위한 요청과 함께 끝난다.

Durations of CPU bursts

• I/O-bound program : many short CPU bursts, 입출력 짧게 자주
• CPU-bound program : few long CPU bursts

CPU Scheduler

• CPU 스케줄러(CPU Scheduler) : 메모리 안의 실행 준비를 마친 프로세스 중 하나를 선택하여 CPU로 할당하는 역할을 수행
• ready 상태에 있는 프로세스들 중 CPU를 할당해줄 수 있는 프로세스를 선택하는 방법으로 무엇을 채택해야 할까?
  
  • Linked List / Binary Tree
  • FIFO Queue 
  • Priority Queue
  • → 큐 내 레코드들은 일반적으로 프로세스의 PCB

Preemptive (선점) and Nonpreemptive (비선점) Scheduling

• 선점형은 스케줄러에 의해 프로세스가 실행 도중에 CPU에서 빠져나올 수 있음을 의미
• 비선점형은 프로세스가 CPU에서 실행을 마치고 종료할 때까지 나머지 프로세스가 대기함을 의미
  즉, 프로세스가 terminaiting 상태나 waiting 상태로 변할 때까지 대기

Decision Making for CPU-scheduling

1. 프로세스가 running → waiting 상태로 스위칭
2. 프로세스가 running → ready 상태로 스위칭
3. 프로세스가 waiting → ready 상태로 스위칭
4. 프로세스가 terminates 상태가 될 때

1번과 4번은 프로세스가 자발적으로 CPU에서 빠져나오는, 즉 비선점 유형이다. 스케줄링 면에서는 선택의 여지가 없어서 실행에 의해 새로운 프로세스가 반드시 선택되어야 한다.

2번과 3번은 스케줄러에 의해 실행 중 CPU에서 빠져나올 수 있어 비선점 유형일수도, 선점 유형일수도 있다.

Dispatcher

디스패처는 CPU 스케줄러에 의해 선택된 프로세스에게 실질적으로 CPU의 제어권을 주는 역할을 수행한다.

스케줄러는 무엇을 변경할지 선택하는 것이고, 디스패처는 변경을 실제로 수행하는 것이다.

• CPU 스케줄러 내부에 포함
• 프로세스의 레지스터를 적재하고(Context Switching) 커널 모드에서 사용자 모드로 전환
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(jump)

Context Switching을 하는데 소요되는 시간을 dispactcher latency 라고 칭하고, 이 소요 시간을 줄이기 위해 디스패처는 최대한 빨라야 한다.

Dispatcher Latency는 CPU 사용 시간보다 가급적 짧아야 한다.

Scheduling Criteria

CPU 스케줄링 알고리즘별 특성이 다르기에, 상황에 따라 선택해야 한다.

비교하는 데 사용되는 특성에 따라서 알고리즘을 결정하는 데 큰 차이가 발생한다. 

Scheduling criteria는 스케줄링 알고리즘 비교를 위한 기준으로, 최선의 알고리즘을 선택하는데 기준점이 된다.

1. CPU 이용률 ( CPU utilization )
   • CPU는 바쁜 상태를 유지해야함 → 사용률을 늘려야함
   • 실제 시스템에서는 40%에서 90%까지의 범위를 가져야함
2. 처리량 ( Throughput )
   • 특정 시간 내 많은 양의 프로세스 처리
   • 작업량 측정의 한 방법은 단위 시간당 완료된 프로세스의 개수
3. 총 처리 시간 ( Turnaround time)
   • 프로세스 실행 후 종료까지의 시간을 최소화
   • 대기 시간 = 준비 큐에서 대기하면서 보낸 시간의 합
4. 응답 시간 ( Response time )
   • 첫 응답이 시작되는 데까지 걸리는 시간
   • 중간에 결과가 나온다면 그것이 기준이 됨
   • 응답 시작까지의 걸리는 시간이지 최종 응답 출력까지의 시간이 아님
5. 대기 시간 ( Waiting Time) 
   
   • 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지 걸리는 시간
   • 프로세스가 Ready 큐에 상주하는 시간을 최소화
   •  Waiting time을 개선하면 시스템의 효율을 크게 증대

CPU 이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직하다.

평균보다는 최대/최소값을 최적화시킨다.

Scheduling Algorithms

Ready queue 내의 어떤 프로세스에게 CPU core를 할당할 것인가의 문제를 해결한다.

FCFS(First-Come, First-Served) Scheduling

• 먼저 온 프로세스를 먼저 실행하는 방법
• 비선점 스케줄링 유형
• FIFO 큐를 참고하여 만들어진 방법으로 구현이 가장 쉽고 간단
• CPU 버스트 타임이 긴 프로세스가 먼저 실행되는 경우 waiting time이 크게 늘어나 효율성이 하락

SJF(Shortest Job First) Scheduling

• 도착 순서와 무관하게 짧은 작업을 먼저 수행
• 크기가 동일할 경우 먼저 도착한 프로세스 실행
• 선점 유형 or 비선점 유형
  • 다음 프로세스에게 대기 명령을 내리면 비선점 유형
  • 현 프로세스를 중단하고 다음 프로세스를 실행시키면 선점 유형
• 평균 waiting time 을 최대한 줄일 수 있는 최적의 옵션

• 다음 프로세스의 CPU burst 시간을 확실히 알 수 없기 때문에 현실적으로 구현하기 어려움
  • 이에 대한 방안으로 다음 프로세스의 CPU burst 시간을 예측하여 비슷하게라도 구현
  • 실행할 프로세스가 과거에 얼마나 CPU burst 시간을 소요했는지 저장하여 현재 소요할 시간을 예측
  • 그러나 시간을 얼마나 쓰는지 기록하는 것 역시 CPU에 저장되는 것이기 때문에 부담 O

SRTF(Shortest-Remaining-Time-First) Scheduling

• 현재 실행중인 프로세스보다 다음 프로세스의 실행 시간이 짧다면 바로 다음 프로세스를 실행하는 방법
• SJF, SRTF 스케줄링의 경우 계속해서 짧은 실행 시간을 가진 프로세스가 도착하면, 긴 실행 시간을 가진 프로세스는 영영 실행하지 못할 가능성이 있음

RR(Round-Robin) Scheduling

• 먼저 들어온 프로세스를 실행하지만, 시간 단위(time quantum)에 따라 끊임없이 스위칭하는 선점형 스케줄링 방법
• 원형 큐(순환 큐)로 처리
• 평균 waiting 시간을 줄일 수 있으나, 평균 response 시간이 크게 늘어날 수 있음

• 프로세스의 CPU 버스트 시간이 설정한 시간 단위보다 적다면?
  → 프로세스가 CPU에서 자발적으로 탈출하고 스케줄러는 ready 큐에 있는 다음 프로세스를 실행한다.
• 프로세스의 CPU 버스트 시간이 설정한 시간 단위보다 길면?
  → O/S에 의해 인터럽트와 함께 컨텍스트 스위칭이 발생한 후 다음 프로세스를 바로 실행한다. 그리고 현재 프로세스는 ready 큐의 끝으로 가 대기한다.

Priority-base Scheduling

• 각 프로세스에게 우선 순위를 할당하고, 우선 순위 순으로 프로세스를 CPU에 할당하는 방법
• 같은 우선 순위를 가지고 있다면, 먼저 온 프로세스를 실행
• CPU burst 시간이 클 때 우선 순위를 낮게 설정할 경우 SJF 스케줄링과 비슷한 결과가 나올 수 있다.
• 선점 유형 or 비선점 유형
• 가장 경계해야 할 문제는 기아(starvation) 현상
  • 우선 순위가 낮은 프로세스의 경우 무한정 대기 가능성 존재
  • 이에 대한 방안으로 오랜 기간 대기한 프로세스는 점진적으로 우선 순위를 높이는 방법

Multi-Level Queue(MLQ) Scheduling

• 우선 순위별로 큐를 지정하고, 큐에 따라 각각 다른 스케줄링을 적용하는 방법
• 새로운 프로세스가 들어왔을 때 어느 큐로 분류해야 하는지 애매

Multi-Level Queue(MLQ) Scheduling

• MLQ 스케줄링를 보완한 방법
• 우선 순위별로 큐를 지정하는 것까진 똑같으나, 최하단 우선 순위의 큐를 제외하고는 모두 RR 스케줄링을 적용한 방법
  • 처음 실행한 큐는 최상단 우선 순위의 큐로 들어감
  • 최상단 우선 순위의 큐에 시간 단위를 가장 낮게 설정하고, 시간 단위 안에 실행한 경우 프로세스는 해당 큐에 유지됨
  • 시간 단위안에 프로세스 실행을 마치지 못한 경우 해당 프로세스의 우선 순위를 한 단계 낮춤
  • 계속해서 시간 단위 내에 실행하지 못한다면 최하단 우선 순위로 내려가 순서대로 실행
• 실행 시간이 길어 우선 순위가 낮아진 프로세스의 경우 기아 현상이 발생할수도 있음

Thread Scheduling

• 실제로 OS에 의해서 process가 아닌 kernel-level thread가 스케줄링
• user level thread는 thread library에 의해 관리되고 커널은 존재를 모름

→ CPU에서 실행되려면 연관된 kernel level thread에 mapping되어야 한다.

경쟁 범위 Contention Scopre

다대일과 다대다 모델을 구현하는 시스템에서는 thread library는 사용자 수준 스레드를 가용한 LWP 상에서 스케줄한다. 이러한 기법은 동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁하기 때문에 프로세스 경쟁 범위(process-contention scope, PCS)로 알려져 있다.

CPU상에 어느 커널 스레드를 스케줄 할 것인지 결정하기 위해서 커널은 시스템 경쟁 범위(system-contention scope, SCS)를 사용한다.

1. Process Contention Scope (PCS)

• User level thread를 스케줄
• 프로세스 내 스레드 간 CPU core 경쟁
• 높은 우선 순위를 가진 스레드 선택
• 실행 중인 스레드 선점

2. System Contention Scope (SCS)

• Kernel level thread를 스케줄
• 시스템 전체 스레드 간 CPU core 경쟁
• 스레드 라이브러리가 가용 LWP에 스케줄 → OS가 LWP의 kernel thread를 물리적 CPU core에 스케줄

Pthread Scheduling

Pthreads는 다음과 같은 범위의 값을 구분한다.

• PTHREAD SCOPE PROCESS : PCS 스케줄링을 사용하여 스레드 스케줄

    → user level 스레드를 가용한 LWP에 스케줄함

• PTHREAD SCOPE SYSTEM : SCS 스케줄링을 사용하여 스레드 스케줄

    → 각 user level 스레드에 대한 LWP를 생성하고 연결함 (core에 일대일 매핑)

Multi-Processor Scheduling

Multi-Processor는 여러 개의 물리적 프로세서를 제공하는 시스템을 말하며, 각 프로세서에는 하나의 단일 코어 CPU가 포함되어 있다. Processor당 한 core에 여러 CPU가 가용한다면 부하 공유가 가능하다.

다중 처리기는 다음 시스템 아키텍처들에 사용할 수 있다.

• Multicore CPU (homogenous)
• Multithreaded cores (homogeneous)
• NUMA systems (homogeneous)
• Heterogeneous multiprocessing

Approaches to Multiple-Processor Scheduling

1. 비대칭 다중 처리기 AMP (asymmetric multiprocessing )

• 비대칭 (기능적으로 다름) : Master / others
• Master server가 모두 처리하며 나머지는 user code만 실행
• 오직 하나의 코어만 시스템 자료구조에 접근하여 자료 공유의 필요성을 배제하기 때문에 간단함
• Master server가 전체 시스템 성능을 저하할 수 있는 병목이 될 수 있음

2. 대칭 다중 처리 SMP (symmetric multi-processing)

• 독립적으로 작업 가능
• CPU마다 똑같은 일 처리 가능
• 다중 처리기를 지원하기 위한 표준 접근 방식
• 각 프로세서는 스스로 스케줄링 가능하며 스케줄러가 ready queue를 확인하고 실행할 스레드를 선택함

Multicore Processors

현대 컴퓨터 하드웨어는 동일한 물리적인 칩 안에 여러 개의 처리 코어를 장착하여 다중 코어 프로세서 (multicore processor)가 된다.

프로세서가 메모리에 접근할 때 데이터가 가용해지기를 기다리면서 많은 시간을 소비하는 메모리 스톨(memory stall)이라고 하는 이 상황은 최신 프로세서가 메모리보다 훨씬 빠른 속도로 작동하기 때문에 주로 발생한다.

현대 프로세스는 메모리보다 속도가 훨씬 빨라서 cache miss가 발생하게 된다.

이러한 상황을 해결하기 위해 

• 둘 이상의 hardware thread를 한 core에 할당
• 한 hardware thread가 메모리를 기다리며 중단되면 core가 다른 thread로 전환
• 각 hardware thread는 각 arhictectural state를 유지
• OS 입장에서는 hardware thread를 software thread를 실행하는 논리적인 CPU로 보고 스케줄링 진행 (chip multithreading; CMT)

Load Balancing (부하 균등)

SMP

운영체제와 메모리를 공유하는 여러 프로세서가 프로그램을 수행하는 것

• 시스템의 모든 처리기 사이에 부하가 고르게 배분되도록 시도
• 멀티프로세서의 이점을 최대한 활용하기 위해서인데, 그렇지 않으면 하나의 프로세서가 idle 상태일 때 다른 프로세서들은 부하가 클 수 있음 → ready queue에서 CPU를 기다리는 상황

Load Balancing

• SMP에서 모든 프로세서들의 부하를 동일하게 유지하는 것
• 각 프로세서별로 자신의 ready queue를 갖는 시스템에서는 필요함
• common run queue를 사용하는 system에서는 필요없음

Processor Affinity

스레드에 의해 가장 최근에 접근된 데이터가 그 처리기의 캐시를 채우게 된다. 그 결과 스레드에 의한 잇따른 메모리 접근은 캐시 메모리에서 만족한다.

그렇다면 스레드가 특정 processor에서 실행될 때 캐시 메모리는?

Warm Cache

• 스레드가 최근 접근한 데이터가 프로세서의 캐시를 채움
• 스레드에서의 연속적인 메모리 접근은 캐시 메모리에서 처리됨 → warm cache

캐시 무효화 및 다시 채우는 비용이 많이 들기 때문에 SMP를 지원하는 대부분의 운영체제는 스레드를 한 프로세서에서 다른 프로세서로 이주시키지 않고 같은 프로세서에서 계속 실행시키면서 warm cache 를 사용한다. 

Process Affinity 형태

1. Soft Affinity

• OS는 process가 동일 processor에서 실행되도록 노력함, 보장은 안됨
• 노력은 하지만 load balancing으로 이주 가능

2. Hard Affinity

• system call로 프로세스가 실행될 수 있는 프로세서의 집합을 지정
• 특정 프로세서에서 실행되도록 보장

메인 메모리 구조가 process affinity에도 영향을 준다.

• 특정 CPU에 스케줄된 스레드로부터 가까운 메모리를 할당한다.
• NUMA-aware인 경우 가까운 메모리에 할당한다.

Heterogeneous Multiprocessing (HMP)

• 모든 프로세서가 기능 면에서 동이하기에 스레드는 임의 core에서 실행 가능하다.
• load balancing, processor affinity, NUMA 등에 따라 메모리 접근 시간이 다르다.
  • core들이 기능적으로 다를 수 있음
  • 스레드가 특정 목적으로 특정 core에서 실행될 수 있음
  • task의 특정 요구에 기반해 특정 core에 할당함으로써 전력 소비를 더 잘 관리

Real-Time CPU Scheduling

Real-Time O/S에서의 스케줄링은 Soft Realtime 혹은 Hard Realtime 으로 구성된다.

• Soft real-time 시스템 : 반드시 정해진 시간 내에 실행하는 것은 아니며, 중요 태스크가 먼저 실행된다는 것만 보장
• Hard real-time 시스템 : 요구 사항이 매우 엄격하여 태스크는 반드시 시간 내에 실행되어야 함 

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

Overview

Thread란?

• 하나의 process에 존재하는 LWP (Lightweight Process) 
• CPU utilization의 기본 단위
• thread ID, program counter(PC), register set, stack으로 구성
• 동일한 process에 속하는 다른 thread들과 core, data, resource, file signal 공유
• 동시에 하나 이상의 task 실행 가능

현대 운영체제는 한 process가 다중 스레드를 포함하기에, 다중 CPU를 제공하는 multicore system에서 thread를 통한 병렬 처리가 중요하다.

application이 비슷한 여러 task를 수행할 일이 많기에 multi thread process를 사용한다.

ex) 여러 client들의 비슷한 request를 처리하는 web server

multit thread process의 경우 code, data, files는 동일하되 thread별로 registers, stack, PC를 각각 구비한다.

Single-thread process VS Multi-thread process

• Single-thread process를 여러 개 생성하여 일 처리 → 시간, 자원 소모가 큼
• Multi-thread process → 한 process가 더 효율적으로 여러 일을 처리할 수 있음

⇒ 요청할 때마다 process를 생성하지 않음 → Thread 단위로 처리해서 자원과 시간 사용을 효율적으로 함

장점

1. Responsiveness
   • 스레드 단위로 분리하여 한 작업에 대해 응답을 기다리지 않고 다른 작업 수행 가능
   • UI 처리할 때 blocking 할 필요 없이 non blocking으로 계속 실행 가능
2. Resource Sharing
   
   • Process와 Process 처리할 때 자원 공유
   • 동일 주소 공간 내에 다른 여러 스레드 가질 수 있음
3. Economy 
   • 프로세스 생성하려면 메모리와 자원을 할당하는데 cost 소요
   • Process 내 thread 생성하여 자원을 공유하며 처리하는 것이 더 경제적
   • thread 생성이 process 생성보다 비용 저렴
   • thread 간 Context switching은 process보다 빠름
4. Scalabiliy
   • multiprocessor 구조의 이점으로 thread는 다른 core에서 병렬 수해 가능
   • core가 많더라도 single-threaded process는 한 프로세서에서만 실행

Multicore Programming

multi core를 효율적으로 사용하고 병행성을 향상시키는 프로그래밍 방법

• Multicore 있으면 동시성 매우 향상
• ex) 4개의 스레드 고려해보자
  • 싱글 : 시간에 따라 interleave (배치) → time sharing
  • 멀티 : 병렬로 실행 → time sharing 하는 동시에 parallel

processing core가 한 번에 하나의 스레드만 실행하여 스레드의 실행이 interleave된다.

개별 thread가 각 core에 할당되어 thread들이 병렬로 실행된다.

Programming Challenges in Multicore systems

1. Identifying tasks
   • 명확하게 독립된 태스크로 분류되도록 영역을 찾기
2. Balance
   • equal value로 equal work하도록 해야함 (밸런싱) → 작업 기여도 균등하도록
3. Data splitting
   • task가 사용하는 data를 seperate core에서 나눠서 실행되도록
4. Data dependency 
   • task에 접근하는 data의 의존성에 따라 동기화되도록 확인 필요
5. Testing and debugging
   • 병렬 수행하는 경우 다양한 실행 경로에 대해 test 및 debug 필요

Types of parallelism

• data parallelism : multiple core로 데이터를 분할
  • 동일한 task에 대해 수행 
  • 동일 data의 부분집합 분배
• task parallelism : 데이터는 유지하되 일을 분담
  • 다른 task를 분배하여 수행
  • 동일 data 또는 다른 data
    • 각 thread별 고유의 연산 수행

Amdahl’s Law

• 코어는 많을수록 좋은가? → 무조건 좋지는 않다!
• core의 개수가 performance에 주는 영향은 linear하지 않고 log 형태로 증가
• application 내에서 병렬적으로 수행될 수 없는 component들은 어쩔 수 없이 serial하게 수행되어야 하므로 병렬 처리가 불가능

Multithreading Model

• user thread (green thread)
  • 커널 support 없이 usermode에서 스레드 진행
  • system call 사용 안하는 thread
  • Java JVM
• kernel thread 
  • OS에 의해 직접 관리됨
  • 코어에서 직접 스레딩할 수 있음

user & kernel thread 사이 세 관계 (user, kernel thread 간 개수가 안맞을 가능성 O)

• Many to One Model
• One to One Model
• Many to Many Model

1. Many to one model
   • 한 번에 한 thread만 커널에 접근
   • 병렬 수행 X
   • 입출력 같은 system call이 필요하면 kernel thread에 접근
2. One to one model
   
   • thread가 blocking system call을 하더라도 다른 thread가 실행 가능
   • Linux, Window에서 사용
   • user thread 생성시 kernel thread도 생성 → kernel thread의 증가로 시스템 부담
     • 병렬 수행이 가능하지만 너무 많은 thread가 생성되지 않도록 관리 필요 
3. Many to many model
   • user thread를 개수가 작거나 kernel thread로 multiplex
   • user thread ≥ kernel thread
   • 4개보다 8개의 core를 가진 시스템에서 더 많은 kernel thread를 할당 받음
     • 개발자가 필요한 만큼 user thread 생성하여 대응되는 kernel thread가 병렬로 수행
4. Two-level model
   • Many to many model 변형
   • user level thread가 kernel thread에 묶일 수 있음
   • 가장 flexible하지만 구현 어려움 

core 수의 증가에 따라 kernel thread 수 제한의 중요성이 줄어들고 switching 부담이 증가하고 있다.

따라서 대부분의 OS들은 one to one model을 사용하고 있다.

Thread Libraries

개발자에게 thread를 생성, 관리하기 위한 API를 제공한다

구현 방법

1. user-level threads library
   • kernel 도움 없이 전적으로 user space에서 thread library 제공
   • 함수 호출은 system call이 아닌 user space에서의 local 함수 호출
2. kernel-level threads library
   
   • OS에 의해 직접 지원되는 kernel-level library 제공
   • API에서의 함수 호출은 kernel에 대한 system call 야기

3가지 main Thread Library

• Pthread (유닉스 계열의 user level, kernel level 라이브러리 제공)
• Windows thread library (윈도우 system의 kernel-level 라이브러리 제공)
• Java thread API (JVM이 host OS에서 실행되므로 host system에서 가용한 thread library로 구현)

Multiple threads 생성 전략

1. Asynchronous threading (비동기 스레딩)
   
   • 부모는 자식을 생성 후 자신의 실행 재개 → 동시/독립적 실행
   • data sharing이 거의 없음
   • multithreaded server, user interface 구현에 사용 (각 요청에 대해 비동기적으로 처리)
2. Synchronous threading (동기 스레딩)
   
   • 부모는 모든 자식 thread가 종료되길 기다림
   • 자식 thread는 concurrently하게 실행되어 종료되면 부모가 실행
   • 자식이 끝나서 종료되면 부모와 join (모든 자식들이 join되어야 부모가 실행 재개)
   • data sharing이 많이 일어남

부모가 자식의 수행 결과를 모아서 실행하기에 data sharing이 활발하다

Implicit Threading

multi core 시스템에서 multi threading application, design이 등장하게 되었다.

그러나 이는 처리가 어려우며, explicit threading은 너무 복잡하고 어렵다.

이에 따라 밑단에서 thread를 생성하며 관리를 알아서 해주는 implicit threading이 등장하게 되었다.

• application 개발자가 병렬 수행되는 task를 구분해야 함
• task는 함수로 작성하여 run-time library가 개별 thread로 map함

Threading Issues

1. Semantices of fort() and exec() system calls (복제)
   • UNIX의 두 버전 fork() 제공 (모든 thread 복제 vs 호출한 thread만 복제)
   • fork() 후 자식 스레드가 본인만의 코드를 실행하기 위해 exec()를 호출하는 경우 굳이 모든 thread를 복제할 필요가 없고 해당되는 thread만 복제
   • 부모와 똑같은 코드를 실행하는 경우 모든 thread 복제
2. Single handling (신호 전달)
   
   • signal : process에게 특정 event가 일어났음을 알림
   • Synchronous Signals : process 내부 이벤트 (같은 process)
     • 프로그램이 특정 행동시 signal 발생 (불법적인 행동)
     • signal을 야기한 연산을 수행한 process에게 전달
       • ex) 불법적인 메모리 접근
   • Asynchronous Signals : process 외부 이벤트
     
     • signal이 실행 중인 process의 외부 이벤트에 의해 생성 → 비동기적 전달
     • 보통 비동기적 signal은 다른 process로 전달됨
       • ex) ctrl + c
3. Thread cancellation of target thread (취소)
   • thread가 완료되기 전에 강제 종료
   • 병렬로 검색하다 하나가 결과를 찾으면 나머지 thread를 종료
   • Asynchronous cancellation
     • 다른 process에 의해 즉시 종료
   • Deferred cancellation
     • 지연 시간 제공, 값을 변경하는 경우 완료될 때까지 기다려줌
     • 종료시켜도 되는지 확인하는 시간을 줌
     • target thread가 스스로 종료되어야 하는지 확인하여 순차적으로 종료
       • * target thread : 취소되어야 하는 thread
   • Difficulty with cancellation
     • 만약 바로 종료시켜버릴 때 문제 되는 경우
       • 취소된 thread에 자원이 할당된 경우
       • 공유 데이터를 갱신하는 동안 취소되는 경우
         • ⇒ 필요 시스템 자원이 사용하지 못하게 될 수 있음
         • ⇒ deferred cancellation으로 target thread가 안전하게 취소될 수 있는지 검사
4. Thread-local storage (TLS) (저장소) 
   • thread 자신만의 data 필요 ⇒ Thread-local Storage (TLS)에 저장
     • ex) 각 트랜잭션을 독립된 thread로 서비스하는 경우
       • 트랜잭션별 id 부여
       • thread와 id를 연관시키기 위해 TLS 사용
5. Scheduler Activations (스케줄러)
   • kernel과 thread library 간 통신을 고려
   • many to many model, two-level model이 사용
   • Light Weight Process (LWP) 자료구조 
     • user와 kernel thread 사이 중재하는 자료 구조
     • application(user thread) 입장에서는 LWP가 마치 user thread를 스케줄하는 processor처럼 보임 (virtual processor)
     • 각 LWP는 하나의 kernel thread에 부착됨
     • ⇒ kernel thread의 수를 동적으로 조절

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

Process Concept

프로세스란?

• 실행 중인 프로그램
• OS의 작업 단위
• 하나의 프로세스가 실행되기 위해 자원 필요
  • CPU, memory, files, I/O devices

프로세스 상태 정보는 (1) program counter와 (2) contents of the processor's register로 구성

프로세스 레이아웃

• Text section ⇒ 명령어 실행 코드
• Data section ⇒ 전역 변수들
• Heap section ⇒ 함수 호출시 dynamic하게 저장되는 메모리
• Stack section ⇒ 함수 파라미터, 리턴되는 주소나 지역 변수를 저장하는 일시적 데이터 저장

• Text와 Data 부분은 고정
• Stack와 Heap 부분은 동적
  
  • Stack은 grow down
  • Heap은 grow up

⇒ 겹치지 않게 OS가 조절

Program and Process

• program : 디스크에 저장된 명령어 리스트를 포함하는 파일 (executable file)
• process : 다음 실행할 명령어를 나타내는 program counter와 관련 자원 집합을 가짐
  
  • 두 process가 동일 program과 관련되더라도 두 개의 독립된 실행 순서로 간주됨 ⇒ 이 경우 Text section은 동일하고 나머지는 다름

Process State

• New : 프로세스가 막 생성된 상태
• Running : CPU가 프로세스를 점유하여 프로세스를 로딩하는 상태
• Waiting : 다른 프로세스가 CPU를 점유할 때 
• Ready : I/O 대기하고 있다가 점유할 준비, 대기중
• Terminated : 프로세스 실행 끝남

processor core에서 실행될 수 있는 process는 오직 한 번에 한 개뿐이지만, ready나 waiting 상태는 많은 process들이 존재할 수 있다.

Process Control Block (PCB)

PCB는 구조체 내 프로세스가 가져야하는 모든 정보들을 저장하는 저장소이다.

프로세스마다 각각 PCB를 가지며 이는 doubly linked list로 구현된다.

각 프로세스가 가져야하는 모든 정보들을 저장한다.

• Process state : new/running/ready/waiting/halted 등
• Program counter : 다음 명령어의 주소
• CPU registers : interrupt 발생 시 PC와 함께 상태 정보 저장하여 reschedule 후 계속 실행됨
• Memory-management information 
• Accounting information
• I/O status information

Threads

Single thread of execution

• Process는 single thread를 실행하는 program
  • 현대 OS 프로세스
• single thread 제어는 한번에 하나의 task만 실행됨 (ex. 문자 입력과 철자 검사를 동시에 X) 

Multiple Thread

• Process가 여러 실행 thread만 가지고 한 번에 하나 이상의 tasks를 실행함
• Multi core system인 경우 여러 thread가 병렬로 실행 가능
• Thread 지원 system에서 PCB가 각 thread에 대한 정보를 포함하도록 확장

Process Scheduling

Multiprogramming

항상 process들이 실행되도록 하여 CPU 이용률을 최대화한다.

multiprogramming의 목적 

• 동시에 여러 프로세스 실행
• CPU 사용률 증가
• Time sharing으로 프로세스 내 CPU core를 스위치하여 각 프로그램이 동시에 돌고 있는 것처럼 보이도록 함

Time sharing

Process 사이에서 CPU core를 자주 switch하여 user와 program이 상호작용한다.

→ core에서 프로그램을 실행하기 위해 process scheduler가 실행 가능한 process를 하나 고른다.

Single CPU core를 가진 system에서는 한 번에 한 process만 실행 가능하지만, multicore system에서는 multiple processes들이 동시에 실행될 수 있다.

이때 core의 수보다 process의 수가 더 많은 경우 process들이 wait해야 한다.

• multiprogramming과 time sharing의 균형을 위해 적절히 스케줄링 해야한다.
• 시간 소비에 따라 I/O bound or CPU bound process로 구분된다.

Degree of multiprogramming

현재 메모리 내 process 수

Scheduling Queues

• Process가 system에 진입하여 Ready queue에 삽입되어 대기한다.
• IO가 있으면 wait queue로 삽입된다.
• Ready Queue / Wait Queue는 linked list 형태로 저장된다.
• queue의 head는 첫 PCB 포인터를 가지며, 각 PCB는 다음 PCB에 대한 포인터를 가진다.

Queueing Diagram

종료 시점에 queue에서 제거되고 PCB와 자원이 해제된다.

CPU Scheduling 

process는 ready queue와 wait queue 사이를 이주한다.

CPU scheduler의 역할

• ready queue에서 하나의 process를 선택하고 CPU core를 할당한다.
• I/O bound process → 잠깐 실행 후 I/O 대기
• CPU bound process → 오랜 기간동안 CPU core가 필요해도 장기간 할당될 가능성은 없음 (CPU를 뺏어서 다른 process에게 스케줄함)

Swapping - 메모리 과부하 상태일 때 process 제거

• memory에서 process를 제거하여 다중화 정도를 낮추는 것
• 나중에 다시 memory로 적재되어 중단된 위치에서 계속 실행됨
• swapped out = 메모리 → 디스크
• swapped in = 디스크 → 메모리
  • 메모리가 초과 사용되어 해제되어야할 때만 필요

Context Switch (문맥 교환)

• CPU가 다른 프로세스와 CPU core를 교환하는 것
• Context : PCB 내 프로세스가 사용되고 있는 상태, PCB로 보면 됨
• interrupt 발생
  • 실행 중인 프로세스의 현재 context 저장 (PC, 어디까지 저장했는지)
  • OS는 현재 task로부터 CPU core를 뺏아 kernel 루틴을 실행하게 함
  • 다른 프로세스 로딩시 저장한 context를 restore

• 다른 process에게로 CPU core를 switching하는 것
• PCB에 old process의 문맥을 저장하여 실행될 new process의 saved 문맥을 load

Operations on Processes

프로세스는 동시에 수행되고 동적으로 생성/삭제된다.

프로세스는 새로운 프로세스를 생성할 수 있다. → 부모/자식 프로세스 by fork()

Process Creation

• 실행 중에 process는 새로운 process를 생성한다.
  • 생성한 process = 부모 process
  • 생성된 process = 자식 process
• 부모/자식 process는 병렬적으로 실행
• 부모는 자식이 종료될 때까지 기다림
• 자식이 부모의 복제본이면 부모와 동일한 프로그램과 데이터를 가짐 [fork() system call]
• 자식 process가 자신에게 load되는 새로운 프로그램을 가짐

Process identifier (pid)

• pid로 process를 식별
• kernel 내에서 다양한 process의 속성에 접근하기 위한 index로 사용

command

• ps -el : 현재 실행 중인 process들의 list를 보여줌
• pstree : tree로 보여줌

systemd process (pid=1)

• root parent process
• 모든 user process들의 부모이며 부트 시 생성되는 첫 user process
• 부팅되면 systemd가 추가적인 서비스를 제공하는 process를 생성함

Child process가 자원을 필요로 할 때

• 자식 process가 OS로부터 직접 자원을 할당받거나 부모 process 자원의 부분집합으로 제한
• 부모는 자식들 간 자원을 분할하여 사용하거나 자식들과 자원 공유

→ 한 프로세스가 너무 많은 자식을 생성하여 시스템을 과부하시키는 것을 막음

Child process에 필요한 data 전달

• OS가 자식 process에게 자원을 전달
• 부모 process가 자식 process에게 초기화 data 전달

자식 process

• 부모로부터 자원뿐만 아니라 특권, 스케줄링 속성을 물려받음
• exelip()를 이용해 자신의 주소 공간을 ls 명령어로 덮어씀 

부모 process

• wait() system call을 이용하여 자식 process가 끝날 때까지 기다림
• 자식 process 종료 시, 부모는 wait() 호출로부터 재개

UNIX OS에서의 process 생성 과정

fork() system call : 새로운 process 생성하는 시스템 콜

• 새로운 process는 original 주소 공간의 복사본으로 구성됨
• 부모와 자식이 쉽게 통신하게 함
• pid = for() : 리턴 = (1) 0 (자식) (2) child의 pid (부모)

After a fork() system call

• fork() 후, 한 process가 exec() system call하여 메모리 공간을 새 프로그램으로 교체
• binary file을 memory로 적재하고 실행함 
  • 적재 : 자신을 포함한 프로그램의 메모리 이미지를 파괴(덮어쓰기)
• 자식을 더 생성하거나 자식이 실행되는 동안 할 일이 없으면 자식이 종료될 때까지 ready queue에서 자신을 제거하기 위해 wait() system call을 함 

Process Termination

return(final Statement)로 종료를 명시하거나 exit()로 중도 out처리한다.

OS 입장에서는 메모리 및 자원 해제, 회수한다.

스스로 종료

• 마지막 문장을 실행하여 종료하고 exit() system call로 OS에 자신을 삭제 요청함
• wait() system call을 통해 대기 중인 부모 process에 상태값이 반환됨
• process의 자원들은 OS에 의해 할당이 해제되고 회수됨

다른(부모) process에 의한 종료

• system call로 다른 process를 종료시킴 (TerminateProcess() in Window)
• 종료시키는 system call은 부모 process로부터 호출됨
• process 종료를 위해서 부모는 자식의 pid를 알아야함 
  • process 생성 시 부모에게 pid 전달
• 이유
  • 자식이 할당된 자원을 초과 사용한 경우
  • 자식에게 할당된 task가 더 이상 필요하지 않은 경우 task 종료
  • 부모가 exit시 자식이 계속 실행되는 것을 OS가 허용하지 않은 경우

Cascading termination

• 부모가 종료되면 자식이 존재할 수 없음 → 모든 자식이 종료되어야 함
• 자식이 종료될 때 pid가 return되어 부모는 어느 자식이 종료됐는지 식별
  • pid = wait(%status) // exit(1) → 1인 status로 종료

사용자에 의한 종료

Process Table

PCB의 array는 현재 존재하는 모든 process의 PCB이다. 

→ process의 exit status가 process table에 저장되므로 process table의 항목은 부모가 wait()를 호출할 때까지 남아있어야 한다.

Zombie Process → 정상 종료 가능

• 종료되었거나 부모가 아직 wait()를 호출하지 않은 process
  • 자식 할 일 하게 냅워서 자식은 좀비처럼 계속 남아있음
• 부모가 wait()를 호출하면 좀비의 process pid와 process table의 항목이 해제됨

Orphan Process → 정상 종료 불가능

• 부모가 wait()를 호출하지 않고 종료한 경우 PCB에 정보가 계속 남음
• 이를 System 선에서 정리해야하는데, init process를 orphan process의 새로운 부모로 지정하여 해결
• int이 주기적으로 wait()를 호출하여 orphan process의 exit status를 수집하고 orphan process의 id와 process table 항목을 해제함

Interprocess Communication (IPC)

Process 간 협력 이유

• Information sharing
• Computation speed up
• Modularity

IPC Model

1. shared-memory model → 공유 메모리 주고 받음
   • 공유 메모리 영역을 만들 때만 system call이 일어나므로 빠름
   • 공유 메모리가 만들어지면 모든 접근이 일상적인 메모리 접근으로 취급되고 커널 도움 필요 없음
   • process들은 동시에 동일 위치에 쓰지 않도록 책임져야 함
2. message-passing model → 메세지 주고 받음
   • 작은 data 교환시 유용
   • 분산 system 환경에서 구현 쉬움
   • 느림

IPC in Shared-Memory Systems

• 공유 메모리 영역은 공유 메모리 segment를 생성하는 process의 주소 공간에 위치
• 공유 메모리 segment를 사용해 통신하기 원하는 process들은 자신의 주소 공간에 추가
• process들은 동시에 동일 위치에 쓰지 않도록 책임져야함

A solution using shared-memory

producer(정보 생산)와 consumer(정보 소비)는 동시에 실행되고, CPU를 잘 나눠서 점유한다.

• Complier → assembly code 생산, assembler → assembly code 소비
• client-server 패러다임
• 동시에 실행하기 위해 producer는 buffer를 채우고, consumer는 이를 받아 사용함
• producer와 consumer는 동기화되어야 함 → 생산되지 않은 정보를 소비하지 않음

Buffer

Buffer가 가득차면 Producer는 wait, 아직 모자라면 Consumer는 wait 상태를 유지한다.

• unbounded buffer : consumer는 item 대기 가능, producer는 계속 생성 가능
• bounded buffer : consumer는 empty일 때 대기, producer는 full일 때 대기 ⇒ 원형 배열로 구현

IPC in Message-Passing Systems

Shared-Memory system의 복잡한 내용들을 OS가 처리하게끔 한다! (By cooperating process 수단)

• 네트워크로 연결된 다른 컴퓨터들의 process간 통신
• send(message) receive(message)
• message의 길이는 고정이거나 가변이고, 통신을 원하면 message를 주고 받아야함
  • fixed-sized message : 시스템 수준 구현은 단순하나 task 프로그래밍이 어려움
  • variable-sized message : 시스템 수준 구현은 복잡하나 task 프로그래밍이 쉬움
• Naming → 통신을 원하는 process들은 서로 통신 상대를 지정해야 

Direct  communication (직접 연결 통신)

recipient/sender process의 이름을 명시한다.

• send(P, message) : process P에게 메세지 전달
• receive(Q, message) : process Q로부터 메세지 받음
• P와 Q가 직접적으로 연결됨
  • communication link는 자동으로 생성되고, 하나의 링크만 성립됨

 단점

• process 정의에서 modularity가 제한됨
• process id의 변경은 모든 다른 process 정의를 검사해서 변경해야 함
• id가 직접적으로 명시되는 hard-coding 기법

1. Symmetry in addressing 
   • 통신하려면 둘 다 상대의 이름을 지정
2. Asymmetry in addressing
   • sender만 recipient를 naming
   • send(P, message)
   • receive(id, message) : any process로부터 받음 (id는 통신이 일어난 process의 이름)

Indirect communication (간접 연결 통신) - mailbox

• mailbox는 process들이 메세지를 저장(send)하고 제거(receive)하는 객체
• 두 process가 공유 mailbox를 가질 때만 통신 가능
• 여러 mailbox를 통해 다른 process들과 통신
• send(A, message), receive(A, message) : mail box A를 통해서 통신

둘 이상의 process가 같은 mailbox를 공유하는 경우

• link가 최대 두 process만 연관되도록 제한
• 최대 한 번에 한 process만 receive()
• 어떤 process가 메세지를 receive할 지 선택 (round robin)

mailbox 소유

1. process 소유 
   • 소유자(수신자)와 사용자(송신자)로 구분
   • 각 mailbox마다 고유한 owner가 있음
   • mailbox를 갖는 process가 종료되면 mailbox도 사라짐
   • 사라진 mailbox에 메세지를 보내는 process는 mailbox가 없음을 통보받음
2. OS 소유
   • 독립적으로 존재하여 특정 process에 속하지 않음
   • process가 mailbox를 생성/삭제하는 기능을 OS가 제공
   • mailbox를 생성하는 process가 owner
   • mailbox에 대한 권한은 system call로 다른 process에 전달 가능

Synchronization 동기화

• process 간 통신은 send() / receive() 호출로 발생
• blocking (synchronous) Send : 수신될 때까지 send 대기 → 수신 후 송신
  • 메세지가 받아들여질 때까지 sender는 블락됨
• blocking (synchronous) Receive : 메세지가 avail할 때까지 receive 대기 → 송신 후 수신
  • 메세지 available할 때까지 receiver는 블락됨
• nonblocking (asynchronous) Send, Receive
  • sender가 메세지 보내고 할 일 계속함
  • receiver가 유효하거나 빈 메세지를 되찾아옴 (Retrieve)

⇒ send와 receive의 종류에 따라 4가지 조합 가능

Buffering 

• 메세지는 temporary queue에 보관

Queue 세 가지 구현 방법

• Zero capacity : 보관 X
• Bounded capacity : N개 메세지 보관
• Unbounded capacity : 무한개 보관