데커 알고리즘 (Dekker’s Algorithm) 데커 알고리즘(Dekker’s Algorithm)은 두 프로세스 간 **상호 배제(Mutual Exclusion)**를 보장하기 위해 1965년 네덜란드의 수학자 Theodorus Dekker가 개발한 최초의 소프트웨어 상호 배제(mutual exclusion) 알고리즘이다. 이 알고리즘은 두 개의 프로세스가 공유 자원에 동시에 접근하는 것을 방지하여 경쟁 상태(race condition)를 해결하는 방법을 제시한다. 공유 자원에 대한 안전한 접근을 위해 **플래그(flag)**와 턴(turn) 변수를 활용하며, 하드웨어적 명령어 없이 소프트웨어만으로 구현 가능하다. 데커 알고리즘은 상호 배제 문제 해결의 역사적 중요성을 가지지만, 현대 시스템에서는 **세마포어(Semaphore)**나 **뮤텍스(Mutex)**와 같은 더 효율적인 동기화 기법이 주로 사용된다. ...
램포트의 빵집 알고리즘 (Lamport’s Bakery Algorithm) 램포트의 빵집 알고리즘(Lamport’s Bakery Algorithm)은 N개 프로세스의 상호 배제(Mutual Exclusion) 문제를 해결하기 위한 소프트웨어 기반 알고리즘이다. 1974년 레슬리 램포트(Leslie Lamport)가 제안했으며, 빵집에서 번호표를 받아 순서대로 서비스받는 방식에서 아이디어를 얻었다. 램포트의 빵집 알고리즘은 병행 프로그래밍의 이론적 토대를 제공했지만, 현대 시스템에서는 주로 하드웨어 지원 동기화 기법이 사용된다. 단, 분산 시스템이나 임베디드 환경에서는 여전히 연구 및 적용 사례가 존재한다. 핵심 원리 번호표 시스템 각 프로세스는 임계 영역 진입 전 고유한 번호표를 받는다. 번호표는 단조 증가(monotonically increasing) 방식으로 발급되며, 동시 접근 시 프로세스 ID로 우선순위 결정한다. 단조 증가(monotonically increasing)란 함수나 수열이 항상 증가하거나 일정한 값을 유지하는 성질을 의미한다. 즉, 감소하는 구간 없이 유지되거나 증가하는 경우를 말한다. ...
피터슨 알고리즘 (Peterson’s Algorithm) 피터슨 알고리즘(Peterson’s Algorithm)은 두 프로세스의 **상호 배제(Mutual Exclusion)**를 보장하기 위한 소프트웨어 기반 동기화 알고리즘이다. 1981년 개리 피터슨(Gary L. Peterson)이 제안한 이 알고리즘은 간결성과 이론적 엄밀성으로 운영체제 및 병행 프로그래밍 분야에서 널리 연구된다. 피터슨 알고리즘은 이론적 완결성을 인정받지만, 현대 시스템에서는 주로 하드웨어 기반 동기화 기법(예: TAS, CAS)이 사용됩니다. 그러나 병행 프로그래밍의 근본 원리를 이해하는 데 여전히 핵심적인 역할을 한다. 핵심 구성 요소 플래그 배열(flag) 각 프로세스의 임계 영역 진입 의사 표시 (flag, flag 초기값 False) 턴 변수(turn) 임계 영역 진입 순서 결정 (0 또는 1 값을 가짐) 동작 원리 진입 의사 표시: 프로세스 i가 임계 영역 진입 전 flag[i] = True 설정. ...
프로세스 동기화 (Process Synchronization) 여러 프로세스가 공유하는 자원의 일관성을 유지하기 위한 메커니즘. 컴퓨터 시스템에서 여러 프로세스가 공유 자원에 접근할 때 충돌을 방지하고 데이터의 일관성을 유지하기 위해 동기화가 필요하다. 다음 두 가지 목적을 가진다: 실행 순서 제어: 프로세스를 올바른 순서대로 실행하기 상호 배제: 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하기 필요성 데이터 일관성 유지: 여러 프로세스가 공유 데이터에 동시 접근할 때 발생할 수 있는 예상치 못한 결과를 방지한다. 실행 순서 보장: 특정 프로세스의 실행이 다른 프로세스의 결과에 의존하는 경우, 올바른 순서로 실행되도록 한다. 임계 영역 문제 임계 영역(Critical Section)은 여러 프로세스가 공유하는 데이터를 접근하는 코드 영역을 말한다. 예를 들어, 은행 계좌의 잔액을 수정하는 코드가 임계 영역이 될 수 있다. ...
프로세스 제어 블록 (Process Control Block, PCB) 프로세스 제어 블록 (Process Control Block, PCB) 은 운영 체제에서 프로세스를 관리하기 위해 사용하는 핵심적인 데이터 구조이다. PCB 는 각 프로세스에 대한 중요한 정보를 저장하고 관리하며, 운영 체제가 프로세스를 효율적으로 제어하고 실행할 수 있게 한다. Sourece: https://www.geeksforgeeks.org/process-table-and-process-control-block-pcb/ PCB 의 주요 구성 요소 프로세스 식별자 (Process ID, PID): 각 프로세스에 할당되는 고유한 식별 번호이다. 프로세스 상태 (Process State): 프로세스의 현재 상태를 나타낸다. 주요 상태로는 생성 (new), 준비 (ready), 실행 (running), 대기 (waiting), 종료 (terminated) 등이 있다. 프로그램 카운터 (Program Counter): 다음에 실행할 명령어의 주소를 가리킨다. CPU 레지스터: 프로세스가 CPU 를 사용할 때의 레지스터 정보를 저장한다. CPU 스케줄링 정보: 프로세스의 우선순위, CPU 사용 시간 등 스케줄링에 필요한 정보를 포함한다. 메모리 관리 정보: 프로세스의 메모리 할당 정보, 페이지 테이블 등을 저장한다. 입출력 상태 정보: 프로세스에 할당된 입출력 장치, 열린 파일 목록 등을 관리한다. 계정 정보: CPU 사용 시간, 메모리 사용량 등 프로세스의 리소스 사용 정보를 추적한다. PCB 의 역할과 중요성 프로세스 관리: PCB 는 운영 체제가 프로세스의 생명주기를 관리하는 데 필수적이다. 컨텍스트 스위칭: PCB 는 프로세스 간 전환 시 현재 상태를 저장하고 복원하는 데 사용된다. 스케줄링: 운영 체제는 PCB 의 정보를 바탕으로 프로세스 스케줄링 결정을 내린다. 리소스 관리: PCB 는 프로세스에 할당된 리소스를 추적하고 관리한다. 동기화 및 통신: 프로세스 간 동기화와 통신에 필요한 정보를 저장한다. PCB 의 생명주기 프로세스 생성 시 PCB 가 생성되고 초기화된다. 프로세스 실행 중 PCB 정보가 지속적으로 업데이트된다. 프로세스 종료 시 PCB 가 제거된다. PCB 의 구현 및 저장 PCB 는 운영 체제 커널의 보호된 메모리 영역에 저장된다. 일부 운영 체제에서는 PCB 를 커널 스택의 시작 부분에 위치시킨다. ...
Context Switching Context Switching 은 운영 체제에서 매우 중요한 개념으로, 여러 프로세스나 스레드가 단일 CPU 자원을 공유하여 효율적으로 실행될 수 있게 하는 메커니즘이다. Context Switching 은 CPU 가 현재 실행 중인 프로세스나 스레드의 상태를 저장하고, 다른 프로세스나 스레드의 상태를 불러와 실행을 재개하는 과정을 말한다. 이를 통해 여러 작업이 동시에 실행되는 것처럼 보이게 된다. Source: https://www.geeksforgeeks.org/context-switch-in-operating-system/ Context Switching 의 필요성 멀티태스킹: 여러 프로세스가 동시에 실행되는 것처럼 보이게 하여 시스템 효율성을 높인다. 인터럽트 처리: 하드웨어 인터럽트나 시스템 호출 등에 신속하게 대응할 수 있다. 자원 공유: 단일 CPU 로 여러 프로세스를 실행할 수 있게 한다. Context Switching 의 과정 현재 실행 중인 프로세스의 상태 저장: CPU 레지스터, 프로그램 카운터 등의 정보를 PCB(Process Control Block) 에 저장한다. 새로운 프로세스 선택: 스케줄러가 다음에 실행할 프로세스를 선택한다. 새 프로세스의 상태 복원: 선택된 프로세스의 PCB 에서 상태 정보를 불러와 CPU 레지스터에 복원한다. 실행 재개: 새 프로세스의 실행을 시작한다. Context Switching 의 트리거 인터럽트: 하드웨어나 소프트웨어에서 발생하는 인터럽트. 시간 할당 종료: 프로세스에 할당된 CPU 시간이 끝났을 때. I/O 요청: 프로세스가 I/O 작업을 요청하여 대기 상태로 전환될 때. 우선순위: 더 높은 우선순위의 프로세스가 실행 준비될 때. Context Switching 의 구현 방식 하드웨어 스위칭: 프로세서 코어에 내장된 태스크 상태 세그먼트 (TSS) 를 사용한다. 소프트웨어 스위칭: 운영 체제의 커널 루틴과 데이터 구조를 사용하여 구현한다. 더 빠르고 일관성 있는 방식이다. Context Switching 의 장단점 장점: ...
세그먼테이션 (Segmentation) 세그먼테이션(Segmentation)은 운영체제의 메모리 관리 기법 중 하나로, 프로세스를 논리적 단위인 세그먼트로 나누어 관리하는 방식이다. 세그먼테이션의 기본 개념을 이해하기 위해, 먼저 프로그램의 구조를 생각해보자. 일반적인 프로그램은 코드 영역, 데이터 영역, 스택 영역 등 서로 다른 목적을 가진 영역들로 구성된다. 세그먼테이션은 이러한 논리적 단위들을 각각의 세그먼트로 관리한다. Source: https://www.geeksforgeeks.org/segmentation-in-operating-system/ 세그먼테이션의 주요 구성 요소와 작동 방식 세그먼트 테이블(Segment Table): 1 2 3 4 5 6 7 8 9 10 struct SegmentTableEntry { uint32_t base; // 세그먼트의 시작 주소 uint32_t limit; // 세그먼트의 크기 bool present; // 메모리 존재 여부 struct { bool read; // 읽기 권한 bool write; // 쓰기 권한 bool execute; // 실행 권한 } protection; }; 주소 변환 과정: 논리적 주소는 다음과 같이 구성된다: ...
페이징 (Paging) 먼저 페이징이 필요한 배경을 이해해보자. 초기 컴퓨터 시스템에서는 프로그램 전체가 물리 메모리에 연속적으로 적재되어야 했다. 이는 두 가지 큰 문제를 발생시켰다: 큰 프로그램은 메모리에 적재하기 어려웠다. 메모리 단편화(fragmentation)가 심각했다. 이러한 문제를 해결하기 위해 페이징이 도입되었다. 페이징의 기본 개념은 프로그램의 논리적 주소 공간과 물리적 메모리를 동일한 크기의 작은 단위로 나누어 관리하는 것이다. 이때 논리적 주소 공간의 단위를 ‘페이지(page)‘라 하고, 물리적 메모리의 단위를 ‘프레임(frame)‘이라고 한다. Source: https://www.geeksforgeeks.org/paging-in-operating-system/ 페이징 시스템의 주요 구성 요소 페이지 테이블(Page Table): ...