2-1) OS 정리

• Operating System
  • program that acts between computer user and computer hardware.
  • 하드웨어와 유저 사이의 연결을 돕는 프로그램
• Computer System Structure
  • hardware, operating system, application programs, users

  

• Operating System def :
  1. Resource allocator : manages all resources, decides between conflicting requests for efficient and fair resource use.

     모든 자원을 관리하면, 효율적인 자원 사용을 위해 요청들을 조정함

  2. Control program : Controls execution of programs to prevent errors and improper use of the computer.

     프로그램 실행을 제어하여 오류나 부적절한 컴퓨터 사용을 방지함
• Kernel : The one program running at all times on the computer
  • 커널 : 컴퓨터에서 항상 실행되고 있는 단 하나의 프로그램

• Computer System Operation
  • I/O devices and the CPU can execute concurrently

    I/O 장치와 CPU는 동시에 실행할 수 있음

  • Each device controller is in charge of a particular device type

    각 장치 컨트롤러는 특정 장치 유형을 담당함

  • Each device controller har a local buffer

    각 장치 컨트롤러는 로컬 버퍼를 가짐

  • CPU moves data from/to main memory to/from local buffers

    CPU는 메인 메모리와 로컬 버퍼 간에 데이터를 이동함

  • I/O is from the device to local buffer of controller

    I/O는 장치에서 컨트롤러의 로컬 버퍼로 이루어짐

  • Device controller informs CPU that it has finished its operation by causing an interrupt

    장치 컨트롤러는 Interrupt를 발생시켜 작업 완료를 CPU에 알림
• Interrupt
  • def : The occurrence of an event is usually signaled by an interrupt from either the hardware and the software.

    이벤트 발생은 보통 하드웨어 또는 소프트웨어 중 하나로부터 Interrupt 신호로 전달될 수 있음

    change of flow in system

  • When CPU is interrupted
    • Stops what it is doing

      하던 작업 중단

    • Immediately transfers execution to a fixed location

      즉시 실행을 바뀐 위치로 교체

    • the fixed location usually contains the starting address where the service routine for the interrupt is located

      해당 변경 위치는 보통 인터럽트의 서비스 루틴 시작 주소를 포함함

    • executes the interrupt service routine

      인터럽트 서비스 루틴을 실행함

    • resumes the interrupted computation on completion

      완료되면 중단된 기존의 연산을 재개할 수 있음

  • Interrupt common function
    • Interrupt transfers control to the interrupt service routine generally, through the interrupt vector, which contains the addresses of all the service routines.

      일반적으로 인터럽트는 모든 서비스 루틴 시작주소가 담긴 인터럽트 벡터를 통해 서비스 루틴으로 제어를 전달할 수 있음

  • Incoming interrupts are disabled while another interrupt is being processed to prevent a lost interrupt

    하나의 인터럽트를 처리하는 동안 다른 인터럽트가 들어와도 비활성화 되어 인터럽트 손실을 방지할 수 있음

  • Trap
    • def : a software-generated interrupt caused either by an error or a user request.

      오류나 사용자 요청으로 인해 소프트웨어가 생성한 Interrupt.

  • Trap vs Interrupt
    • Interrupt is sth generated by the hardware but Trap is an exception in a user process invoked by software.

      인터럽트는 보통 하드웨어, 트랩은 소프트웨어가 일으킨 인터럽트를 지칭함. 즉 software interrupt = trap

  • An OS is interrupt driven.
• Interrupt Handling
  • The operating system preserves the state of the CPU by storing registers and the program counter.

    운영체제는 레지스터나 프로그램 카운터를 사용하여 CPU의 상태를 보존함

  • Polling
    • 운영체제가 주기적으로 각 장치 컨트롤러의 상태를 확인(Poll) 하여 인터럽트를 감지하는방식
  • vectored interrupt system
    • 인터럽트가 발생하면 하드웨어가 바로 CPU에 인터럽트 벡터를 제공하고, 이 번호로 인터럽트 벡터 테이블에서 해당 서비스 루틴의 주소를 찾아 바로 점프함

• I/O Structure
  • Device controller
    • hardware connected to common bus
  • Device Driver
    • understands the device controller

• I/O operation
  • Program-controlled I/O
    • device moves data between memory and buffer in the device. CPU is busy
  • Direct Memory Access(DMA)
    • device move data from memory itself. CPU is not busy

• Caching
  • copying information into faster storage system
• OS operations
  • Dual-mode operation allows OS to protect itself and other system components

• Kernel
  • responds to system calls, interrupts and exceptions

• Timer
  • timer interrupt maintains OS to control over the CPU
  • prevent infinite loop, process hogging resources
• Process
  • program in execution
  • It is a unit of work within the system
  • program is passive, process is active

• Thread
  • smallest unit execution in process

• Cache coherency
  • all CPUs have the most recent value in their cache

• Real-Time OS
  • end in limited time

• OS service
  • User Interface
    • Command Line (CLI), Graphics User Interface(GUI), Batch
  • Program Execution
    • load a program into memory, run, end execution
  • I/O operations
    • give I/O Interface

• System calls
  • Programming interface to the services provided by the OS
  • Mostly accessed by programs via API rather than direct system call use
  • Why use API rather than system calls?
    • to provide a simplified method of the use of system calls and hide details

• Syscall parameter passing
  1. pass by registers
  2. pass by memory block
  3. pass by stack

• Type of syscall
  • process control, file management, device management, …

• Operating System Design
  • Mechanisms : how to do sth
  • Policies : what will be done

• Layered Approach
  • OS is divided into a number of layers(levels)
  • bottom layer(0) : hardware
  • highest layer(n) : user interface

  

• Modules
  • modern OS : kernel modules
    • object-oriented
    • core component is separate
    • talks over known interfaces
  • more flexible than layers

• Virtual Machines
  • software-made machine operate like real computer

• Process
  • process execution must progress in sequential fashion
  • a program in execution
    • Program Counter
    • Stack
    • Data Section
  • process in memory
    • Stack
      • contains temporary data
    • Data Section
      • contains global variables
    • Heap
      • memory that is dynamically allocated
• Process State
  • new
    • process created
  • running
    • instructions are executed
  • waiting
    • process is waiting for some event
  • ready
    • process is waiting to be assigned to CPU
  • terminated
    • process has finished execution
• Process Control Block(PCB)
  • data structure that maintains on memory to manage process
    • Process state
    • Program counter
    • CPU registers
    • CPU scheduling info
    • …
  • PCB is on memory, kernel area

• Context Switching
  • Saving state of current running process and loading and running new process

• Process scheduling
  • multiprogramming is to have some process running at all times, to maximize CPU utilization
  • time sharing is to switch the CPU among processes so frequently that users can interact with each program

• Process scheduling Queues
  • Job queue
    • set of all processes in the system
  • Ready queue
    • set of all processes in main memory, ready and waiting to execute
  • Device queues
    • processes waiting for an I/O device

• Schedulers
  • component of OS, select a process execution
  • Long-term scheduler : brought from disk into the ready queue , infreq, controls multiprogramming
  • Short-term scheduler : executed from the ready queue, allocates CPU , freq

• Long-term scheduler : balance between I/O bound process and CPU bound process

• Medium-term scheduler
  • swapping

• Context Switch
  • task of switching CPU to another process
  • saving the current process’s state and restoring different process’s state
  • Context-switch time is overhead, system does no useful work while switching

• Process Creation
  • Resource sharing
    • share all resources
    • subset of parent’s resources
    • share no resources
  • Execution possibilities
    • execute concurrently
    • parent waits until children terminate

• fork, exec
  • fork : create new process
  • exec : used after fork to replace process memory space with new program
  • fork() : return 0 for child, return Pid for parent

• Process Termination
  • exit
    • status value returned from child to parent(wait)
    • resources are deallocated by OS
  • abort (강제 종료)
    • parents kill child process if you need
  • cascading termination
    • if parent is terminated, its child also terminated

      부모 프로세서가 죽으면 자식도 같이 없어짐
• Interprocess Communication(IPC)
  • Shared memory :shared memory region (reading, writing)
    • done at memory speeds. faster than message passing
    • system call for only establishing region
  • Message passing : messages exchanged between processes (sending, receiving) (by kernel)
    • exchanging smaller amounts of data, no conflicts
    • require more task of kernel(overhead)
  • many system implements both

• Producer Consumer Problem (Shared memory)
  • paradigm for cooperating processes
    • In unbounded buffer
      • producer : no wait
      • consumer : wait if buffer is empty
    • In bounded buffer
      • producer : wait if buffer is full
      • consumer : wait if buffer is empty
  • Shared buffer is implemented as a circular array with two logical pointer : in, out

• Message Passing System
  • Direct communication
    • direct link to communicate
  • Indirect communication
    • using mailbox to communicate

• Thread
  • a flow of control within a process
• Multi-Threaded programs
  • benefits
    • Responsiveness
    • Resource sharing
    • Economy

• Two types of threads
  • User thread : we create
    • visible to the programmer. ex) POSIX, WIN32, Java
  • Kernel thread : OS creates
    • directly managed by OS. ex) Solaris, Linux, MacOSX

• Multithreading Models
  • A relationship between user threads and kernel threads
    • Many to One
      • Many User threads mapped to single kernel thread
      • thread management is done by thread library
    • One to One
      • provides more concurrency than the many to one model
      • allows another thread run when a thread makes blocking syscall
    • Many to Many
      • allows many user level threads to be mapped to smaller or equal kernel threads
    • Two level thread
      • similar to many to many
      • allows user thread to be bound to kernel thread
  • Thread Cancellation
    • Asynchronous cancellation : Immediately terminates
    • Deferred cancellation : check if it should be cancelled
• Signal handling
  • Signal : notify a process that particular event is occured

• Two types of signal
  • Synchronous signals(동기 시그널)
    • illegal memory access
  • Asynchronous signals(비동기 시그널)
    • user keystrokes, time expire

• In a single processor system : Only one process can run at a time.

• Process Scheduling
  • to select process from the ready queue and assign the CPU
    • Maximum CPU utilization

• I/O Burst Cycle
  • Process execution consist of CPU execution(CPU burst) and I/O wait(I/O burst)
  • execution begins with a CPU burst, followed by I/O burst, and so on
  • final CPU burst ends with an system call to terminate

• I/O bound process vs CPU bound process
  • I/O bound process has many short CPU bursts
  • CPU bound process might have a few long CPU bursts
• Process scheduler
  • selects process in memory, allocates the CPU
  • decisions
    • run —> wait
    • run —> ready
    • wait —> ready
    • run —> terminated
    • new —> ready
      • 1, 4 = non preemptive (비선점)
      • 2,3,5 = preemptive (선점)
  • non preemptive scheduling
    • keeps the CPU until it releases the CPU
  • preemptive scheduling
    • terminating, switching
  • dispatcher
    • gives control of CPU to the process
      • switching context
      • switching to user mode
      • jumping to the proper location to restart
    • dispatch latency
      • time it takes for a dispatcher to stop one and start another
• Scheduling Criteria
  • CPU utilization
  • Throughput
  • Turnaround time
  • Waiting time
  • Response time

• Process Scheduling Algorithms
  • FCFS
    • first come first served
    • non preemptive —> convoy effects(problem of fcfs)
  • SJF
    • shortest job first
      • non p
      • p
  • Priority Scheduling
    • priority number first
      • non p
      • p
    • problem : starvation
      • low priority processes may never execute
        • solution : aging
          • as time progresses, increase the priority of process
  • RR
    • each process gets a small unit of CPU time (time quantum)
      • wait less than (n-1) * q time units
      • q large —> same as FCFS
      • q small —> high concurrency
• Multilevel Queue
  • fore : RR
  • back : FCFS

Background

Concurrent access to shared data —> data inconsistency

producer-consumer problem solution :

Race Condition(경쟁 조건)

def : Several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place

produce and consume executed concurrently—> may not function correctly

• if counter == 5, execute the statements ++ and —
  • count++ 연산은 다음과 같이 구현될 수 있다
  1. register1 = counter
  2. register1 = register1 + 1
  3. counter = register1
  • count-- 연산은 다음과 같이 구현될 수 있다
  1. register2 = counter
  2. register2 = register2 - 1
  3. counter = register2
  1. S0: 생산자(producer)가 register1 = counter 실행 → register1 = 5
  2. S1: 생산자(producer)가 register1 = register1 + 1 실행 → register1 = 6
  3. S2: 소비자(consumer)가 register2 = counter 실행 → 이 시점의 counter는 아직 5이므로 register2 = 5
  4. S3: 소비자(consumer)가 register2 = register2 - 1 실행 → register2 = 4
  5. S4: 생산자(producer)가 counter = register1 실행 → counter = 6
  6. S5: 소비자(consumer)가 counter = register2 실행 → counter = 4

  After execution, counter may be 4, 5, or 6

  To prevent the race condition

Critical-Section(CS) Problem (임계 구역 문제)

System consisting of n processes

Each process has a segment of code, called a critical section, where the process may change

no two processes are executing in their critical section at the same time

• 시스템에는 n개의 프로세스가 존재한다.
• 각 프로세스는 코드 중에서 “임계 구역(Critical Section, CS)”이라고 불리는 공유 자원(공통 변수, 파일, 데이터베이스 등)을 변경·갱신하는 부분이 있다.
• 요구 사항: 임계 구역이 동시에 두 개 이상의 프로세스에서 실행되면 안 된다는 것이다.

  즉, “어떤 시점에도 오직 하나의 프로세스만 임계 구역에 들어가 있어야 한다.”

  이를 **상호 배제(Mutual Exclusion)**라고 부른다.

Solution to CS problem

Solution to the Critical-Section Problem

1. Mutual Exclusion(상호 배제) :

   if one process is executing in CS, no other processes can be executing in their critical sections

   임계구역에는 한 번에 하나씩만
2. Progress(진행) :

   if no process is executing in CS and there exist some processes that want to enter their CS, then the selection of processes that enter the CS next cannot be postponed indefinitely

   —> deadlock-free condition

   임계 구역이 비어있고 대기중인 프로세스가 있을 때는 반드시 그 중 하나가 즉시 진입해야 함

3. Bounded Waiting(한정 대기) :

   A bound must exits on the number of times

   —> starvation-free condition

   진입을 요청한 프로세스는 자신의 앞 차례 번호에 대한 상한이 있어야 함

위 세가지 조건을 만족하는 protocol을 설계하여 Race Condition을 예방하고 안정성과 효율성을 보장함

Peterson’s Solution (two process solution)

Solution for CS problem among two processes

SW based solution

Two processes share two variables

int turn;
boolean flag[2];

turn : whose turn to enter the CS

flag[i] : implies that processes i is ready

Peterson의 해법

두 개의 프로세스 간의 임계 구역 문제를 해결하기 위한 동기화 기법

turm 이라는 공유 변수를 사용하여 누구의 차례인지 표시함

flag 배열을 사용하여 준비 상태인지 아닌지 확인함

피터슨의 해법은 3가지 조건을 모두 만족함

1. 상호 배제 :

   Pi 가 임계구역에 접근하려면 반드시 flag[j]가 false 이거나 turn == i 이여야 한다. 이로써 Pi와 Pj 가 동시에 임계 구역에 들어갈 수 없도록 보장한다.

2. 진행 :

   Pi 가 임계 구역에 들어가지 못하고 계속 대기하는 경우는 flag[j]가 참이고 turn == j일 때 뿐이다. 임계 구역이 비어있다면 turn이 자신일 때만 들어가므로 무한정 지연되지 않고 곧바로 진입한다가 참이 된다.

3. 한정 대기

   Pi 가 임계 구역 진입을 요청한 시점 이후, 실제로 임계 구역에 들어오기까지 최대 한 번 Pj 가 임계 구역에 진입할 수 있다. 자신의 앞 차례에 오직 1번만 임계 구역 차례를 넘겨주었으므로 그 다음 즉시 들어갈 수 있다는 보장이 생긴다. 이로써 한정 대기 조건도 충족시킨다.

예제 1.

do {
    while (turn != i);   // 진입 구역: turn이 i가 될 때까지 대기
    // ========= CRITICAL SECTION =========
    // 공유 자원에 대한 작업 수행
    turn = j;           // 임계 구역 종료 후 turn을 j로 넘김
    // ========= REMAINDER SECTION =========
    // CS와 무관한 나머지 작업
} while (TRUE);

turn이 i 가 될 때 까지 대기함

turn이 i가 되었을 때만 CS 코드가 실행된 뒤 turn을 j로 바꿈

위 코드의 문제점 : 진행 조건을 만족시키지 못함

예제 2.

do {
    flag[i] = TRUE;       // Pi가 진입 의사를 표시
    while (flag[j]);      // 상대 Pj가 진입 의사를 철회할 때까지 대기
    // ========= CRITICAL SECTION =========
    // 공유 자원에 대한 작업 수행
    flag[i] = FALSE;      // Pi가 임계 구역 사용을 마쳤음을 표시
    // ========= REMAINDER SECTION =========
    // CS와 무관한 나머지 작업
} while (TRUE);

flag[i] 이 true가 되어 Pi가 들어갈준비가 됨을 알림

만약 flag[j]가 true라면 Pj 가 안나왔으므로 대기함

flag[j]가 false이면 진입

위 코드의 문제점 : 진행 조건을 만족시키지 못함

만약 동시에 flag가 모두 true가 된다면 모두 while문에 들어가게 된다. 이때 서로를 기다리는 Deadlock이 되어 진행하지 못하고 무한 대기하게 됨

Bakery 알고리즘 (다중 프로세스용)

peterson과 달리 n개의 프로세스에 대해 모든 조건을 보장할 수 있는 동기화 기법

/* 프로세스 P_i의 의사 코드 */
do {
    /* 1) Entry Section: 번호표 뽑기 시작 */
    choosing[i] = TRUE;

    /* 
       현재 다른 모든 프로세스(P₀, P₁, …, Pₙ₋₁)의 number 값을 살펴보고
       그중 최대값을 찾은 뒤 +1을 하여,
       number[i] 에 새로운 번호표를 부여한다.
    */
    number[i] = max(number[0], number[1], …, number[n-1]) + 1;
    choosing[i] = FALSE;  // 번호표 뽑기 완료 표시

    /* 2) Waiting Section: “내 차례인가?” 확인하며 대기 */
    for (j = 0; j < n; j++) {
        /* (a) 다른 프로세스 j가 아직 번호표를 뽑는 중이라면 대기 */
        while (choosing[j]) {
            ;  // busy-wait: P_j가 번호표를 뽑을 때까지 기다린다.
        }

        /*
           (b) P_j가 이미 번호표를 뽑았고(number[j] != 0),
               그리고 (number[j], j) < (number[i], i) 이라면
               -> P_j가 순서상 우선순위가 높으므로 대기
        */
        while ((number[j] != 0) &&
               ((number[j] < number[i]) ||
                (number[j] == number[i] && j < i))) {
            ;  // busy-wait: “(P_j의 번호표) < (P_i의 번호표)” 순서일 때까지 기다린다.
        }
    }

    /* 3) Critical Section: 공유 자원에 대한 작업 수행 */
    // ... 임계 구역 코드 ...

    /* 4) Exit Section: 번호표 해제 */
    number[i] = 0;

    /* 5) Remainder Section: 임계 구역 외 나머지 작업 */
    // ... 나머지 코드 ...

} while (TRUE);

1. 상호 배제

   번호표가 가장 작은 프로세스만이 CS에 진입할 수 있다. 두 프로세스가 같은 번호와 인덱스를 가질 수 없기 때문에 두 개 이상의 프로세스가 CS에 들어갈 수 없다.

2. 진행

   반드시 번호표를 뽑아야 CS 진입을 할 수 있다. 또한 무한정 지연되지 않는다.

3. 한정 대기

   번호표를 뽑은 시점을 기준으로 최대 몇 번 다른 프로세스가 들어올 수 있는지에 대한 상한을 정할 수 있다.

Dekker 알고리즘

두 프로세스 Pi 와 Pj 가 공유하는 변수 flag[ ], turn을 사용

/* 프로세스 P_i */
do {
    flag[i] = TRUE;                          // (1) P_i는 임계 구역에 들어갈 의사를 표시

    // (2) 상대 프로세스 P_j가 임계 구역을 원하고 있을 때 
    while (flag[j]) {                        
        if (turn == j) {                     // (2a) 만약 turn이 j라면
            flag[i] = FALSE;                 //    → P_i는 잠시 “진입 의사”를 철회
            while (turn == j)                //    → turn이 바뀔 때까지 대기
                ;
            flag[i] = TRUE;                  //    → turn이 바뀌면 다시 “진입 의사”를 표시
        }
    }

    // ====== Critical Section ======
    // (3) 임계 구역: 공유 자원 안전하게 사용
    // ==============================

    turn = j;                                // (4) 임계 구역 종료 후 우선권을 j에게 양보
    flag[i] = FALSE;                         // (5) P_i는 더 이상 임계 구역을 원하지 않음을 표시

    // ====== Remainder Section ======
    // (6) 임계 구역 외 나머지 작업 수행
    // ================================

} while (TRUE);

Synchronization Hardware

시스템들은 CS코드의 동기화를 돕기 위해 하드웨어 차원의 기능을 제공함

Uni-processor 에서의 방법 :

Atomic hardware instructions

Semaphore

Synchronization tool that does not require busy waiting

세마포어 S는 정수 변수 하나로 관리됨

세마포어의 값을 증가시키거나 감소시키는 두가지 연산은 항상 원자적으로 실행됨

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

signal(S) {
	S++
}

wait : S 가 0 이하라면 사용가능한 자원이 없다는 의미로, 계속 반복해서 S값을 확인함

signal : S값을 1 증가시킴

Counting Semaphore :

Binary Semaphore :

Usage of Semaphore :

Deadlock and Starvation

Deadlock :

Starvation :

Bounded-Buffer Problem

생산자가 2개 이상, 소비자가 2개이상, 버퍼는 N개 아이템만 보관 가능

Solution With semaphore

Semaphore mutex = 1;   // 임계 구역 상호 배제용 바이너리 세마포어
Semaphore full  = 0;   // 버퍼에 들어있는 아이템 개수 카운터
Semaphore empty = N;   // 버퍼의 빈 슬롯 개수 카운터

producer

do {
    // 1) 아이템 생성
    item newItem = produce_item();

    // 2) 버퍼에 빈 슬롯이 있을 때까지 대기
    wait(empty);    // empty--, 0 이하면 대기(block)
    wait(mutex);    // mutex--, 0 이하면 대기(block)

    // 3) 임계 구역(Critical Section)
    buffer[in] = newItem;
    in = (in + 1) % N;

    // 4) 임계 구역 해제 및 소비자 알림
    signal(mutex);  // mutex++
    signal(full);   // full++

    // (아이템 하나 생산 완료)
} while (TRUE);

consumer

do {
    // 1) 버퍼에 아이템이 있을 때까지 대기
    wait(full);     // full--, 0 이하면 대기(block)
    wait(mutex);    // mutex--, 0 이하면 대기(block)

    // 2) 임계 구역(Critical Section)
    item value = buffer[out];
    out = (out + 1) % N;

    // 3) 임계 구역 해제 및 생산자 알림
    signal(mutex);  // mutex++
    signal(empty);  // empty++

    // 4) 아이템 소비
    consume_item(value);
} while (TRUE);

특징

1. 상호 배제 (Mutual Exclusion)

   wait(mutex), signal(mutex) 로 임계 구역을 오직 하나의 프로세스만 사용

2. 버퍼 과부족 방지

   empty가 0이면 생산자 대기 → 버퍼가 가득차면 더 이상 넣지 않음

   full이 0이면 소비자 대기 → 버퍼가 비면 더 이상 꺼내지 않음

3. Progress

   signal(mutex), signal(empty)가 블록된 프로세스를 깨워주므로, 누군가 반드시 유한 시간 내에 임계 구역에 진입 가능 → No Starvation, No Deadlock

Readers-Writers Problem

여러 Readers는 동시에 읽기 수행, 수정은 하지 않음

Writers는 단 하나만 읽기, 쓰기 수행 가능

Writer가 수행 중에는 어떤 Reader도 접근 불가

Solution with Semaphore

Semaphore mutex    = 1;   // readcount 접근 보호용
Semaphore wrt      = 1;   // writers 진입 보호용
int       readcount = 0;  // 현재 읽기 중인 Reader 수

Writer

do {
    wait(wrt);              // ① writer 전용 임계 구역 진입 대기
    // ====== CRITICAL SECTION ======
    // 데이터 집합 읽기·쓰기 수행
    // ==============================
    signal(wrt);            // ② writer 임계 구역 해제
} while (TRUE);

Reader

do {
    wait(mutex);            // ① readcount 보호
    readcount++;            //    첫 Reader인지 확인하기 위함
    if (readcount == 1)     //    첫 번째 Reader라면
        wait(wrt);          //    Writer 진입 차단
    signal(mutex);          // ② readcount 보호 해제

    // ====== CRITICAL SECTION ======
    // 데이터 집합 읽기 수행 (여러 Reader 동시 가능)
    // ==============================

    wait(mutex);            // ③ readcount 보호
    readcount--;            //    마지막 Reader인지 확인
    if (readcount == 0)     //    마지막 Reader라면
        signal(wrt);        //    Writer에게 임계 구역 해제
    signal(mutex);          // ④ readcount 보호 해제
} while (TRUE);

문제 :

철학자 5명이 원형 테이블에 앉아 번갈아가며 생각(think)과 식사(eat)를 반복함

테이블 중앙에 밥그릇 하나, 젓가락 5개

각 철학자는 식사할 때 왼쪽, 오른쪽 젓가락 두 개를 모두 집어야만 먹을 수 있음

제약:

Solution with Semaphore (Deadlock 발생)

Semaphore chopstick[5] = {1,1,1,1,1};

void philosopher(int i) {
    do {
        // 왼쪽(i) 젓가락 집기
        wait(chopstick[i]);
        // 오른쪽(i+1)%5 젓가락 집기
        wait(chopstick[(i+1)%5]);

        // ====== 식사 ======
        eat();
        // ==================

        // 젓가락 내려놓기
        signal(chopstick[i]);
        signal(chopstick[(i+1)%5]);

        // ====== 생각 ======
        think();
        // ==================

    } while (TRUE);
}

장점 : 이웃 철학자끼리 동시에 먹지 못해 Mutual Exclusion 보장

문제 :

해결법 :

Semaphore Misuse

• signal(mutex) … wait(mutex)
  • 락을 헤제한 뒤 다시 획득하면 다른 프로세스가 임계 구역에 들어갈 기회를 빼앗아버려 상호 배제가 깨질 수 있음
• wait(mutex) * 2
  • 같은 프로세스가 중복해서 락을 기다리면 자신이 해제(signal) 하기 전까지 영원히 대기 → Deadlock 발생
• wait, signal 누락

Monitors

고수준 추상화로, 프로세스 간 동기화를 간편하고 안전하게 처리해줌

C++이나 Java같은 객체 지향 언어로 설계 됨

한 모니터 인스턴스는 여러 프로세스가 공유하여 사용

언제나 하나의 프로세스만 내부 코드를 실행할 수 있도록 함

monitor 모니터이름
{
  // ─── PRIVATE: 내부 공유 데이터 ───
  // (모든 프로시저가 접근 가능하나, 외부에서는 접근 불가)
  shared 변수선언들;
  Condition 변수선언들;   // (필요 시)

  // ─── INITIALIZATION: 초기화 코드 ───
  initialization {       
    // 모니터가 생성될 때 딱 한 번 실행
    // 데이터 초기화, 변수 설정 등
  }

  // ─── PUBLIC PROCEDURES: 외부에서 호출 가능한 메서드 ───
  procedure P1(매개변수…) {
    // Entry: 자동으로 상호 배제 락 획득
    … 처리 로직 …
    // 필요 시 wait(cond) 또는 signal(cond) 호출
    // Exit: 자동으로 락 해제
  }

  …
  
  procedure Pn(매개변수…) {
    … 처리 로직 …
  }
}

Condition Variables

조건 변수를 만들어 특정 프로세스만 조작함

condition x, y;

각 조건 변수는 자신만의 대기 큐를 가짐

x.wait()
// 호출한 프로세스를 조건 변수 x의 대기 큐에 넣고 block 함
x.signal()
// 조건 변수 x의 대기 큐에서 한 프로세스만 선택하여 깨워줌

Deadlocks

A set of blocked processes each holding a resource and waiting to acquire a resource

각자 일부 자원을 점유한 채 동시에 다른 프로세스가 점유 중인 자원을 무한히 기다리는 상황

해결을 위해서는 둘 중 하나가 양보(preempt, rollback) 해야 함

이에 따른 Starvation이 발생 할 가능성이 있음

Deadlock 발생 조건

다음 4가지 조건이 동시에 성립할 때 발생

Resource-Allocation Graph

정점 V

간선 E

기본 전제

Mutual Exclusion : 한 번에 두 개 이상이 동시에 사용 중, 또는 사용되지 않고 있음

Hold and Wait : P1, P2가 사용하면서 요청 중

No Preemption : Ykes

Circular Wait : No

→ 데드락 아님

Mutual Exclusion : 한 번에 두 개 이상이 동시에 사용 중, 또는 사용되지 않고 있음

Hold and Wait : P1, P2, P3이 사용하면서 요청 중

No Preemption : Yes

Circular Wait : Yes

→ 데드락 가능성 O

정리 :

Methods for Handling Deadlocks

데드락을 다루는 방법

1. Ensure that the system will never enter a deadlock state
   • deadlock prevention, deadlock avoidance
2. allow the system to enter a deadlock state and then recover
   • deadlock detection, deadlock recovery
3. Ignore, pretend that deadlocks never occur in the system

Deadlock Prevention

1. Mutual Exclusion : 비공유 자원만 상호 배제 적용
2. Hold and Wait : 요청 시 다른 자원 보유 X
   • all or nothing : 프로세스 시작 전에 필요한 모든 자원 요청, 할당
   • zero hold : 자원을 보유하지 않은 상태에서만 요청
3. No Preemption : 할당된 뒤에 강제 회수 가능하게 함
4. Circular Wait : 자원 유형(R)에 순서를 정하고, 항상 오름차순으로만 요청하도록 강제

데드락 예방 알고리즘 :

부작용 :

Deadlock Avoidance(DA)

프로세스가 리소스를 요청하기 전의 정보를 통해 데드락을 회피

각 프로세스는 필요한 최대 자원의 개수를 미리 선언함

요청 시점마다 Resource-allocation state를 검사하여 Circular wait이 일어나지 않는지 확인함

• 시스템이 **안전 상태(safe state)**에 있으면 → 데드락이 절대 발생하지 않는다.
• 시스템이 **비안전 상태(unsafe state)**에 있으면 → 데드락이 발생할 가능성이 있다.
• 회피(Avoidance) 기법은 → 시스템이 절대로 비안전 상태에 진입하지 않도록 보장하는 것이다.

Resource-Allocation Graph Algorithm

• Claim 엣지 Pi⇢Rj는 “프로세스 Pi가 앞으로 자원 Rj를 요청할 수 있다”는 것을 나타내며, 점선으로 표시
• 프로세스가 실제로 자원을 요청하면, Claim 엣지는 요청 엣지(Request edge) Pi→Rj로 변환
• 프로세스가 자원을 해제하면, 할당 엣지(Assignment edge) Rj→Pi가 다시 Claim 엣지로 되돌아감
• 모든 자원은 사전에 시스템에 Claim되어 있어야 함

프로세스가 지원을 요청할 때 요청 엣지가 할당 엣지로 바뀌었을 때 그래프에 사이클이 생기지 않는 경우만 요청을 허용함

사이클 유무는 그래프 순환 탐지 알고리즘을 사용 (cycle-detection algorithm)

사이클이 없으면 safe, 있으면 unsafe → wait

Resource Allocation Graph는 각 자원 유형이 단일 인스턴스 일 때만 사이클 유무로 Deadlock을 결정할 수 있다. 다중의 경우 가능성만 판단할 수 있다.

Banker’s Algorithm

Deadlock avoidance algorithm

여러 인스턴스를 가진 자원에도 적용 가능

Assumption :

• n: 프로세스 수
• m: 자원 유형 수

1. Available (길이 m 벡터)
   • Available[j] = k이면, 자원 유형 Rj의 사용 가능한 인스턴스가 k개 있다는 의미
2. Max (n×m 행렬)
   • Max[i][j] = k이면, 프로세스 Pi가 자원 Rj를 최대 k개까지 요청할 수 있음을 나타냄
3. Allocation (n×m 행렬)
   • Allocation[i][j] = k이면, 프로세스 Pi가 현재 자원 Rj를 k개 할당받아 사용 중임
4. Need (n×m 행렬)
   • Need[i][j] = k이면, 프로세스 Pi가 작업을 완료하기 위해 자원 Rj를 추가로 k개 더 필요로 함
   • 계산식:Need[i][j]=Max[i][j]−Allocation[i][j]

Resource Request Algorithm

1. 요청 한도 검사

   Request[i] ≤ Need[i] 이면 2단계로 이동

   아니라면 최대 요구량을 초과했으므로 오류 발생

2. 가용 여부 검사

   만약 Request[i] ≤ Available이면 3단계로 이동

   아니라면, 가용 자원이 부족하므로 Pi는 대기

3. 가상 할당 시뮬레이션
   복사

   c++

   Available = Available – Request[i];
   Allocation[i] = Allocation[i] + Request[i];
   Need[i]      = Need[i]      – Request[i];

   요청한 자원을 실제로 할당하기 전에 임시로 갱신하여 안전성 검사를 수행함

safe라면 리소스 할당

unsafe라면 대기, 가상 할당을 되돌림

Safety Algorithm

1. 초기화
   • Work는 길이 m인 벡터, Finish는 길이 n인 벡터로 선언
   • Work = Available
   • 모든 Finish[i] = false (i = 0, 1, …, n–1)
2. 조건을 만족하는 프로세스 찾기
   • Finish[i] == false 이고 Need[i] ≤ Work 를 동시에 만족하는 i를 찾는다.
   • 만약 그런 i가 없으면, 4단계로 이동.
3. 자원 가상 회수 및 표시
   • Work = Work + Allocation[i] (프로세스 i가 반납할 자원을 더함)
   • Finish[i] = true
   • 2단계로 돌아가 반복
4. 안전 상태 판정
   • 모든 i에 대해 Finish[i] == true 이면 → 시스템은 안전 상태
   • 그렇지 않으면 → 비안전 상태

Example

Deadlock Detection

시스템이 데드락에 진입하도록 허용한 뒤, 주기적으로 검출 알고리즘을 통해 교착상태를 찾아냄

Deadlock Recovery

데드락이 검출 되었을 때 회복 방법

Memory Management

Background

Base , Limit register

위 사진에서 베이스 레지스터는 30004이고, 리미트 레지스터는 12090라고 할 때 이 프로세스의 메모리 영역은 30004부터 30004+12090 까지임

H/W address protection

Input Queue

Address Binding (of Insturction and Data to Memory)

각 단계에서 주소 바인딩 요약

• 컴파일 시점(Compile time)
  • 메모리 위치가 사전 확정되어 있으면 컴파일러가 절대 주소(absolute addresses)를 직접 생성함
  • 시작 위치가 바뀌면 재컴파일해야 함
• 로딩 시점(Load time)
  • 컴파일 시점에 메모리 위치를 모르면, 컴파일러는 재배치 코드를 생성함(relocatable code)
• 실행 시점(Execution time)
  • 프로세스가 실행 중에 메모리 구역을 옮길 수 있는 경우, 주소 바인딩을 런타임에 지연시킴

주소 바인딩은 컴파일→ 로드→ 실행의 세 단계에서 이루어지며, 각 단계마다 바인딩 시점과 요구되는 자원이 달라짐

Logical vs. Physical Address Space

논리 주소 공간과 물리 주소 공간

논리 주소 :

물리 주소 :

compile-time binding :

execution, load-time binding :

MMU : Logical → Physical 로 변환하는 하드웨어 장치

Swapping

프로세스를 메모리에서 디스크로 내보내고(swap out), 다시 메모리로 불러와(swap in) 실행을 이어가는 기법.

• 목적:

  메모리가 부족할 때 다른 프로세스를 실행하기 위해 공간 확보.

• 백업 저장소(Backing Store):

  모든 프로세스 메모리 이미지를 저장할 수 있는 빠른 디스크.

• 롤아웃/롤인:

  우선순위 스케줄러에서 낮은 우선순위 프로세스를 먼저 내보내고, 높은 우선순위 프로세스를 불러올 때 사용.

Contiguous Allocation

각 프로세스는 하나의 연속된 메모리 구간에만 적재됨

위에 있던 베이스 레지스터와 리미트 레지스터 내용과 일치함

Hole

Dynamic Storage-Allocation Problem

동적 메모리 할당 문제

크기 n인 메모리 요청을 여러 개의 빈 홀 중에서 어디에 어떻게 할당할 지 정해야 함

First, Best, Worst 3가지로 분류됨

• First-Fit
  • 리스트에서 처음 만나는 충분히 큰 홀을 찾아 할당
  • 탐색 범위가 짧아 속도가 빠름
• Best-Fit
  • 리스트 전체(또는 크기 순 정렬된 리스트에서)에서 가장 작은 충분히 큰 홀을 찾아 할당
  • 남는 홀 크기가 최소가 되도록 함
  • 모든 홀을 검사해야 하므로 탐색 비용이 큼
• Worst-Fit
  • 리스트 전체에서 가장 큰 홀을 찾아 할당
  • 남는 홀 크기가 최대가 되도록 함
  • 역시 모든 홀을 검사해야 하므로 탐색 비용이 큼

Fragmentation

단편화

• 외부 단편화(External Fragmentation)

  전체 가용 메모리 공간의 합은 요청 크기를 충족할 수 있지만,

  여러 개의 작은 홀로 흩어져 있어 “연속된” 큰 블록을 만들지 못하는 상태.

• 내부 단편화(Internal Fragmentation)

  프로세스에 할당된 연속 블록이 요청보다 약간 더 큰 경우,

  └─ 그 “여분 부분”은 해당 블록 내부에서 사용되지 못하고 낭비되는 메모리.

  Compaction을 통해 외부 단편화 해소

Paging

noncontiguous한 할당 허용

Address Translation Scheme

논리 주소는 두 부분으로 나뉨

• 페이지 번호(p):
  • 페이지 테이블의 인덱스로 사용됨
  • 페이지 테이블은 각 페이지에 대응되는 프레임의 물리적 시작 주소(베이스)를 저장함
• 페이지 오프셋(d):
  • 해당 페이지 내에서의 상대적 위치를 나타내며,
  • 페이지 테이블에서 가져온 프레임의 베이스에 더해져 최종 물리 주소를 결정함
• 비트 계산
  • logical address 공간 크기가 2^m이고, page 크기가 2^n 이라면:
    • 상위 m−n 비트가 페이지 번호(p)
    • 하위 n 비트가 페이지 오프셋(d) 를 나타냄

Free Frames

새 프로세스가 4개의 페이지 주소 공간을 필요로 할 때, OS는 먼저 빈 프레임(free frames) 목록에서 4개 이상의 프레임이 남아 있는지 확인합니다.

1. 할당 전
   • 예를 들어 빈 프레임 목록이

     {2,5,7,13,14,18,20,21,…} 처럼 남아 있다고 하면,

   • 여기서 4개(임의로 14,13,18,20)를 골라 할당할 수 있습니다.
2. 프레임 할당 & 페이지 테이블 생성
   • 새 프로세스용 페이지 테이블을 만들고,
     복사

     nginx
     복사편집
     page 0 → frame 14
     page 1 → frame 13
     page 2 → frame 18
     page 3 → frame 20

     처럼 매핑 정보를 저장합니다.

3. 할당 후
   • 빈 프레임 목록에서 13,14,18,20을 제거하고,

     예를 들어 {2,5,7,21,…}만 남게 됩니다.

이 과정을 통해 프로세스의 논리 페이지가 물리 프레임에 연속성 없이도 안전하게 배치되며,

페이지 테이블만 있으면 언제든 원하는 페이지를 해당 프레임으로 매핑할 수 있게 됩니다.

Implementation of Page Table

페이지 테이블 구현

• 페이지 테이블의 위치
  • 페이지 테이블 자체는 메인 메모리에 저장됩니다.
  • PTBR(Page-Table Base Register): 현재 실행 중인 프로세스의 페이지 테이블이 시작되는 메모리 주소를 가리킵니다.
  • PRLR(Page-Table Length Register): 페이지 테이블의 길이(엔트리 수)를 보관하여, 잘못된 페이지 번호 접근을 방지합니다.
• 이중 메모리 접근 문제
  1. 첫 번째 접근: 논리 주소의 페이지 번호를 이용해 페이지 테이블에서 프레임 번호를 읽음.
  2. 두 번째 접근: 얻은 프레임 번호와 오프셋을 합쳐 실제 데이터나 명령어를 읽음.

     → 매번 두 번의 메모리 접근이 필요하므로, 성능 저하가 발생합니다.

• TLB(Translation Lookaside Buffer)
  • 이 문제를 해결하기 위해 작고 빠른 캐시처럼 동작하는 TLB를 사용합니다.
  • 최근 참조된 페이지 번호 ↔ 프레임 번호 매핑을 저장해 두어,
  • 주소 변환 시 TLB에 먼저 조회하고, 히트하면 메인 메모리 접근을 한 번만 수행.
  • 미스 시에만 페이지 테이블을 참조한 뒤 TLB에 갱신합니다.

이 구조 덕분에, 페이지 기반 주소 변환의 유연성을 유지하면서도 성능을 크게 향상할 수 있습니다.

TBL(Translation Look-aside Buffer)

페이지 테이블의 일부 엔트리를 저장하는 연관(associative) 고속 캐시

• 동작 흐름:
  1. CPU가 논리 주소를 생성하면, 페이지 번호(p)를 TLB에 조회
  2. 히트(hit) 시 → 해당 프레임 번호(f)를 즉시 얻어 물리 메모리 접근
  3. 미스(miss) 시 → 메인 메모리의 페이지 테이블을 참조해 f를 얻고,

     → 그 (p→f) 매핑을 TLB에 추가

• 용량 제약:
  • TLB에는 소수의 엔트리만 저장 가능
  • 가득 찼을 때는 교체 정책에 따라 기존 엔트리를 제거하고 새 매핑을 저장
• 교체 정책 예시:
  • LRU(Least Recently Used): 가장 오랫동안 참조되지 않은 엔트리 제거
  • 랜덤(Random): 임의의 엔트리 제거

이를 통해, 페이지 테이블 접근 횟수를 줄여 주소 변환 성능을 크게 향상시킬 수 있습니다.

EAT(Effective Access Time)

TLB를 사용할 때 한 메모리 접근의 평균 소요 시간

• TLB 조회 시간: ε
• 메모리 접근 시간: τ
• TLB 히트율: α (예: 0.8 = 80%일 때)

Hierarchical Page Tables

32-bit logical address space, 4 KB of page size

기본 단일 페이지 테이블 구조의 한계 :

Two-Level Paging

32비트 logical address 공간을

로 나눔

20비트 페이지 번호를

로 분해함

Virtual Memory

separation of user logical memory from physical memory

실제 메모리에 프로그램 전체를 올리지 않고 일부만 로드하여 실행 가능

• Demand Paging (요구 페이징)
  • 페이지가 실제로 필요할 때 메모리로 가져옴
  • 페이지 부재(Page Fault) 발생 시 디스크에서 해당 페이지 로드
• Demand Segmentation (요구 세그멘테이션)
  • 프로그램을 세그먼트 단위로 나누고, 필요한 세그먼트만 메모리에 로드
  • 세그먼트도 필요할 때 디스크에서 로드

• Kernel :
  • 주소 공간 관리, 예외 처리, 메모리 할당
  • 물리 메모리 관리
• MMU :
  • 주소 변환, 예외 감지
  • 가상 주소 → 물리 주소 매핑

Demand Paging

Pages are loaded into memory only when they are needed during program execution → dynamic loading

프로그램 실행 중 필요한 시점에만 페이지를 메모리에 불러오는 방식

• 잘못된 참조(Invalid reference) → 프로세스 종료(abort)
• 미적재 페이지(Not-in-memory) → 정상적 페이지 폴트 처리 후 로드

page fault : find a target frame for loading a new page

: too slow

Page Replacement

1. CPU가 아직 메모리에 없는 페이지에 접근
2. → Page Fault 발생
3. → 메모리에 빈 프레임 없음
4. → 기존 페이지 중 하나를 제거하고(new), 필요한 페이지를 로드

이때 어떤 페이지를 제거할지 결정하는 것이 페이지 교체 알고리즘의 역할입니다.

대표 알고리즘

• FIFO (First-In-First-Out)

  가장 먼저 들어온 페이지를 먼저 교체

• Optimal (OPT)

  앞으로 가장 오랫동안 사용되지 않을 페이지를 교체

  (이론적으로 최적이지만 실제 구현은 불가능 → 비교용)

• LRU (Least Recently Used)

  가장 오랫동안 사용되지 않은 페이지를 교체

  (최근 접근 정보를 저장해야 하므로 구현 복잡도 ↑)

• LRU 근사 (Approximation) 알고리즘

ex) fifo

Reference String : 1,2,3,4,1,2,5,1,2,3,4,5

3 frames : 1 2 3