[컴구웅 스터디 7회차] CPU 스케줄링, 프로세스 동기화

heiler·2025년 6월 15일

CPU scheduling Process Synchronization Semaphore monitor mutex

컴구웅(컴퓨터 구조 + 운영체제) 스터디

목록 보기

7/9

💬 Intro

안녕하세요, 헤일러입니다.
이전에는 모니터 개념이 무엇인지 모호했는데, 좀 더 구체적으로 알게 됐습니다.

아래는 학습한 내용 목차입니다.

스케줄링 큐
비선점형 스케줄링, 선점형 스케줄링
프로세스 동기화
뮤텍스, 세마포어, 모니터

❓ CPU 버스트와 I/O 버스트가 무엇인가요?

✅ CPU 버스트

CPU 버스트는 프로세스가 CPU를 점유하여 연속적으로 명령어(instruction)를 수행한 시간 구간을 의미합니다.

CPU 버스트가 긴 작업을 자주 수행하는 프로세스를 CPU 집중 프로세스(CPU bound process)라고 부릅니다.

대표적인 CPU 집중 작업으로는 컴파일, 렌더링과 같은 그래픽 처리, 머신 러닝 모델 학습, 소수 판별이나 행렬 계산 같은 복잡한 수학 연산 등이 있습니다.

✅ I/O 버스트

I/O 버스트는 프로세스가 CPU를 점유하지 않고 I/O 장치의 작업 결과를 기다리는 시간 구간을 의미합니다. 이 때 프로세스는 I/O 장치의 작업이 끝나기를 기다리는 대기 상태입니다.

I/O 버스트가 긴 작업을 자주 수행하는 프로세스를 I/O 집중 프로세스(I/O bound process)라고 부릅니다.

대표적인 I/O 집중 작업으로는 파일 입출력 처리, 웹 서버의 요청과 응답, 사용자 입력 대기, SQL 쿼리 처리 등이 있습니다.

📌 CPU 버스트와 I/O 버스트 요약

항목	CPU Burst	I/O Burst
정의	CPU를 연속으로 점유한 시간 구간	I/O 장치의 작업을 대기한 시간 구간
프로세스의 상태	Running	Waiting (Blocked)
CPU 점유	O	X
종료 조건	연산 완료 또는 I/O 요청	I/O 완료 인터럽트

❓ 스케줄링 큐가 무엇인가요? Ready Queue와 Waiting Queue는 무엇인가요?

스케줄링 큐는 특정 상태에 있는 프로세스를 관리하는 자료구조를 의미합니다.

큐 이름	설명
Job Queue	실행을 기다리고 있는 아직 메모리에 로드되지 않은 프로그램들의 큐
Ready Queue	메모리에 로드되어 CPU 할당을 기다리는 프로세스들의 큐
Waiting Queue	I/O 요청을 하고 I/O 작업의 완료를 기다리는 프로세스들의 큐

Ready Queue에 포함된 프로세스들 중에 어떤 프로세스에게 CPU를 할당해 Running 상태로 만들지 결정하는 과정을 스케줄링이라고 합니다.

❓ 선점형 스케줄링과 비선점형 스케줄링에 대해 설명해주세요.

✅ 비선점형 스케줄링

운영체제가 실행 중인 프로세스가 자발적으로 CPU를 반납할 때까지 기다리는 스케줄링 방식입니다.

프로세스가 작업을 마치고 종료되거나, I/O 요청을 하여 대기 상태가 되기 전까지는 CPU를 계속 점유합니다. 그래서 실시간성이나 빠른 응답이 필요한 환경에는 적합하지 않습니다.

장점
- 구현이 단순합니다.
- 스케줄러 호출 빈도가 낮아 Context Switching 오버헤드가 적습니다.
단점
- CPU 사용이 긴 프로세스가 있으면 다른 프로세스들이 오래 대기할 수 있어 전체 시스템의 응답성이 떨어질 수 있습니다.

✅ 선점형 스케줄링

운영체제가 실행 중인 프로세스로부터 CPU를 강제로 회수하여, 다른 프로세스에 CPU를 할당하는 스케줄링 방식입니다.

타이머 인터럽트, 우선순위, 시간 할당량(time quantum) 등의 개념을 도입하여 스케줄러가 CPU 점유를 적극적으로 제어하는 방식입니다.

장점
- 한 프로세스의 자원 독점을 막을 수 있습니다.
- 우선순위가 높은 작업이나 긴급한 작업을 빠르게 처리할 수 있어 응답성이 뛰어납니다.
단점
- Context Switching이 자주 발생해 오버헤드가 발생할 수 있습니다.
- 우선순위 관리가 복잡해질 수 있습니다.

❓ CPU 스케줄링 알고리즘의 종류는 어떤 것들이 있나요?

✅ 비선점형 스케줄링

▶️ 선입 선처리 (FCFS: First Come First Served)

Ready Queue에 삽입된 순서대로 CPU를 할당하는 스케줄링 방식입니다.

▶️ 최단 작업 우선 (SJF: Shortest Job First)

Ready Queue에 삽입된 프로세스들 중 CPU 이용 시간이 가장 짧은 프로세스부터 CPU를 할당하는 스케줄링 방식입니다.

✅ 선점형 스케줄링

▶️ 우선순위 스케줄링(Priority Scheduling)

프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스에게 CPU를 할당하는 스케줄링 방식입니다. 우선순위가 낮은 프로세스는 기아 현상이 발생할 가능성이 있습니다.

▶️ 라운드 로빈(RR: Round Robin)

FCFS에 시간 할당량(Time Quantum) 개념이 더해진 스케줄링 방식입니다.

각 프로세스에 동일한 시간 할당량을 주고, Ready Queue 삽입 순서대로 CPU를 할당합니다. 시간 할당량만큼 실행 시키고, 다음 프로세스를 실행 시킵니다. 응답 시간이 일정한 시스템에 적합합니다.

▶️ 최소 잔여 시간 우선(SRTF: Shortest Remaining Time First)

Shortest remaining time, also known as shortest remaining time first (SRTF), is a scheduling method that is a preemptive version of shortest job next scheduling
출처: https://en.wikipedia.org/wiki/Shortest_remaining_time

남은 실행 시간이 가장 짧은 프로세스에게 CPU를 할당하는 스케줄링 방식입니다. 새로운 프로세스가 Ready Queue에 추가됐을 때 남은 실행 시간이 더 짧으면 현재 실행 중인 프로세스를 중단하고 새 프로세스를 실행합니다.

📌 스케줄링 알고리즘 요약

알고리즘	선점 여부	기준	특징
FCFS	X	도착 순서	구현 단순
SJF	X	예상 실행 시간	평균 대기 시간 최소
Priority	O	우선순위	기아 가능성 있음
RR	O	시간 할당량 (TQ)	응답 시간 균일, 컨텍스트 스위칭 많음
SRTF	O	남은 실행 시간	SJF의 선점형 버전

❓ 프로세스 동기화가 무엇인가요?

동기화는 둘 이상의 프로세스나 스레드가 동시에 실행될 때 공유 자원에 대한 접근을 제어하여 데이터의 일관성과 신뢰성을 유지하는 기능입니다.

둘 이상의 프로세스나 스레드가 동시에 공유 자원에 접근하여 읽거나 쓰는 과정에서, 실행 순서나 타이밍에 따라 실행 결과가 달라지는 상황을 레이스 컨디션(Race Condition)이라고 부릅니다.

레이스 컨디션과 같은 상황이 발생하지 않도록, 프로세스들의 실행 순서를 안전하게 제어하거나, 특정 자원에 접근할 때 한 개의 프로세스만 접근하게 하는 방법(상호 배제, Mutual Exclusion)을 사용하여 동기화가 제대로 이루어지도록 해야 합니다.

❓ 생산자-소비자 문제(Producer-Consumer Problem)에 대해 설명해주세요.

공유 버퍼를 사이에 두고, 버퍼에 데이터를 삽입하는 프로세스를 생산자, 버퍼로부터 데이터를 소비하는 프로세스를 소비자라고 부릅니다.

생산자-소비자 문제는 동시에 여러 생산자 혹은 소비자가 공유 버퍼에 접근하여 데이터를 수정, 조회했을 때 발생할 수 있는 동기화 문제를 의미합니다.

❓ 공유 자원과 임계 구역에 대해 설명해주세요.

공유 자원(shared resource)은 둘 이상의 실행 흐름(프로세스든 스레드든 상관X)이 동시에 접근할 수 있는 자원을 의미합니다. 프로세스의 관점에서 전역 변수, 메모리의 mmap 영역/Heap 영역/Text 영역 등이 공유 자원이 될 수 있습니다.

임계 구역(critical section)은 한번에 오로지 하나의 실행 흐름만 진입할 수 있는 코드 블록을 의미합니다. 임계 구역으로 지정된 코드 블록은 일종의 공유 자원입니다. 둘 이상의 실행 흐름이 임계 구역에 접근하면 안되는 경우, 락을 사용하여 임계 구역을 제어합니다.

❓ 뮤텍스 락과 세마포어는 어떤 차이점이 있나요?

✅ 뮤텍스 락(Mutex Lock, Mutual Exclusion Lock):

뮤텍스 락은 공유 자원에 오직 하나의 실행 흐름만 접근하도록 하는 도구입니다. 임계 구역을 보호하기 위해 사용되며, 한 번에 하나의 스레드만 임계 구역에 진입 가능하게 합니다.

✅ 세마포어(Semaphore)

세마포어는 공유 자원에 접근할 수 있는 실행 흐름의 수를 1개가 아닌 n개까지 허용하고 싶을 때 사용하는 도구입니다. (카운팅 세마포어 기준)

전역 변수 S: 임계 구역에 진입할 수 있는 실행 흐름의 수
wait 함수(P): 임계 구역에 들어가도 좋은지, 기다려야 할지 알려주는 함수
signal 함수(V): 임계 구역에 들어가길 기다리고 있는 실행 흐름에게 들어가라고 보내는 신호

wait();
// 임계 구역
signal();

wait() {
	S--;
	if (S < 0) {
		add process to Queue;
		sleep();
	}
}

signal() {
	S++; // 자원 반납
	if(S <= 0) {
		remove a process p from Queue;
		wakeup(p);
	}
}

📌 뮤텍스 락 예제 by c언어
c언어에서는 #include <linux/mutex.h>의 mutex_lock_interruptible()을 통해 임계 구역을 잠그고, mutex_unlock()을 통해 임계 구역의 잠금을 해제할 수 있습니다.

아래는 스터디 5회차 때 실습 예제로 작성했던 Device Driver 코드의 일부입니다.

ssize_t uds_read (struct file *pfile, char __user *buffer, size_t length, loff_t *offset) {
    long long duration;

    printk("read uds char drv\n");
    if (length != sizeof(duration)) {
       printk(KERN_DEBUG "uds_read: Invalid length size\n");
       return -EINVAL;
    }

    if (mutex_lock_interruptible(&mutex))
       return -ERESTARTSYS;

    /* critical section starts */
    switch (((int) pfile->private_data)) {
       case 0:
       {
          is_echo_clear = 0;
          gpio_set_value(UDS_TRIGGER_BCM_NUM, HIGH);
          udelay(10);
          gpio_set_value(UDS_TRIGGER_BCM_NUM, LOW);

          wait_event_timeout(wait_queue, is_echo_clear, HZ / 10.0);

          if (!is_echo_clear) {
             printk(KERN_ERR "uds_read: timeout elapses\n");
             mutex_unlock(&mutex);
             return -EIO;
          }
          duration = ktime_to_us(ktime_sub(echo_end, echo_start));
       }
       break;

       default:
          printk("uds_read: Invalid device minor number %d\n", (int) pfile->private_data);
          mutex_unlock(&mutex);
          return -EINVAL;
    }

    printk(KERN_INFO "duration: %lld\n", duration);
    if(copy_to_user(buffer, &duration, sizeof(duration))) {
       printk(KERN_ERR "uds_read: copy_to_user failed\n");
       mutex_unlock(&mutex);
       return -EACCES;
    }
    mutex_unlock(&mutex);
    /* critical section ends */

    return sizeof(duration);
}

❓ 모니터(Monitor)에 대해 설명해주세요.

세마포어는 훌륭한 프로세스 동기화 도구이지만, 매번 임계 구역의 앞뒤로 wait과 signal 함수를 명시적으로 호출해주어야 하는 번거로움이 있습니다. 혹시라도 wait과 signal을 잘못된 순서로 호출하면 예기치 못한 버그를 발생 시킬 수 있습니다. 휴먼 에러 발생 가능성이 있다는 말이죠.

이 문제를 해결하기 위해 모니터가 등장했습니다. 모니터는 임계 구역을 고수준으로 추상화 해놓은 기술입니다. 임계 구역 진입 시 자동으로 락을 획득하고 임계 구역 종료 시 자동으로 락을 해제하는 구조를 제공해주어, 세마포어에 비해 개발자가 편리하게 사용할 수 있습니다.

모니터를 통해 공유 자원에 접근하고자 하는 프로세스를 큐에 삽입하고, 큐에 삽입된 순서대로 하나씩 공유 자원을 이용하도록 합니다.

모니터 밖에서 모니터에 들어가기 위해 락을 기다리는 프로세스는 진입 큐(Entry Queue)에 삽입되고, 모니터 내부에서 특정 조건이 만족할 때까지 대기하고 있는 프로세스는 조건 큐(Condition Queue)에 삽입됩니다.

모니터는 이 두 개의 큐를 이용하여 모니터 안에 항상 하나의 프로세스만 들어오도록 하여 상호 배제를 통한 동기화 기능을 제공합니다.

✅ 모니터 in Java

▶️ `synchronized`

Java의 synchronized 키워드는 모니터 락을 프로그래밍 언어 문법 수준에서 구현한 것입니다.

public synchronized void increment() {
    count++;  // count는 공유 자원
}

JVM은 increament() 메서드를 포함하고 있는 객체를 하나의 모니터로 취급합니다. synchronized가 걸린 메서드나 코드 블록은 모니터 락(monitor lock)을 획득한 스레드만 진입 가능합니다.

생산자-소비자 문제를 synchronized를 통해 해결하는 조금 더 복잡한 예제를 살펴보겠습니다.

class Shared {
    private int data = 0;
    private boolean available = false;

    public synchronized void produce(int value) throws InterruptedException {
        while (available) wait(); // 이전 데이터가 아직 소비되지 않았다면 대기
        data = value; // 데이터 수정 작업
        available = true; // 소비 가능 상태로 전환
        notifyAll(); // 대기 상태인 소비자 스레드를 깨움
    }
    
    public synchronized int consume() throws InterruptedException {
        while (!available) wait(); // available을 확인하며 대기
        available = false; // 소비 불가능 상태로 전환
        notifyAll(); // 대기 중인 생산자 스레드를 깨움
        return data;
    }
}

data 변수: 생산자가 값을 수정하고, 소비자가 값을 조회하는 공유 자원
available 변수: 조건 변수(condition variable) 역할
synchronized: 이 메서드가 실행될 때 해당 객체(this)에 대해 모니터 락을 획득해야 함을 명시
wait(): 락을 반환하고 스레드를 waiting 상태로 전환
notifyAll(): 대기 중인 스레드를 깨움

▶️ `ReentrantLock`의 `lock()`

개발자가 명시적으로 임계 구역의 시작과 끝을 직접 설정할 필요가 있다면 java.util.concurrent.locks.ReentrantLock을 사용할 수 있습니다. 뮤텍스나 세마포어처럼 저수준의 동기화 기능을 제공해주는 도구입니다.

class Shared {
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition notEmpty = lock.newCondition();
    private final Condition notFull = lock.newCondition();
    private int data;
    private boolean available = false;

    public void produce(int value) throws InterruptedException {
        lock.lock();
        try {
            while (available)
                notFull.await(); // 소비되기 전까지 기다림
            data = value;
            available = true;
            notEmpty.signal(); // 소비자 스레드를 깨움
        } finally {
            lock.unlock();
        }
    }

    public int consume() throws InterruptedException {
        lock.lock();
        try {
            while (!available)
                notEmpty.await(); // 생산되기 전까지 기다림
            available = false;
            notFull.signal(); // 생산자 스레드를 깨움
            return data;
        } finally {
            lock.unlock();
        }
    }
}

Reference

혼자 공부하는 컴퓨터 구조+운영체제, 강민철
Monitor
- https://www.baeldung.com/cs/monitor

heiler

Smiley

이전 포스트

[컴구웅 스터디 6회차] 프로세스와 스레드

다음 포스트

[컴구웅 스터디 7회차] CPU 스케줄링, 프로세스 동기화

컴구웅(컴퓨터 구조 + 운영체제) 스터디

💬 Intro

❓ CPU 버스트와 I/O 버스트가 무엇인가요?

✅ CPU 버스트

✅ I/O 버스트

❓ 스케줄링 큐가 무엇인가요? Ready Queue와 Waiting Queue는 무엇인가요?

❓ 선점형 스케줄링과 비선점형 스케줄링에 대해 설명해주세요.

✅ 비선점형 스케줄링

✅ 선점형 스케줄링

❓ CPU 스케줄링 알고리즘의 종류는 어떤 것들이 있나요?

✅ 비선점형 스케줄링

▶️ 선입 선처리 (FCFS: First Come First Served)

▶️ 최단 작업 우선 (SJF: Shortest Job First)

✅ 선점형 스케줄링

▶️ 우선순위 스케줄링(Priority Scheduling)

▶️ 라운드 로빈(RR: Round Robin)

▶️ 최소 잔여 시간 우선(SRTF: Shortest Remaining Time First)

📌 스케줄링 알고리즘 요약

❓ 프로세스 동기화가 무엇인가요?

❓ 생산자-소비자 문제(Producer-Consumer Problem)에 대해 설명해주세요.

❓ 공유 자원과 임계 구역에 대해 설명해주세요.

❓ 뮤텍스 락과 세마포어는 어떤 차이점이 있나요?

✅ 뮤텍스 락(Mutex Lock, Mutual Exclusion Lock):

✅ 세마포어(Semaphore)

❓ 모니터(Monitor)에 대해 설명해주세요.

✅ 모니터 in Java

▶️ `synchronized`

▶️ `ReentrantLock`의 `lock()`

Reference

[컴구웅 스터디 6회차] 프로세스와 스레드

[컴구웅 스터디 8회차] 교착 상태(Deadlock), 페이징을 통한 가상 메모리 관리

0개의 댓글

[컴구웅 스터디 7회차] CPU 스케줄링, 프로세스 동기화

컴구웅(컴퓨터 구조 + 운영체제) 스터디

💬 Intro

❓ CPU 버스트와 I/O 버스트가 무엇인가요?

✅ CPU 버스트

✅ I/O 버스트

❓ 스케줄링 큐가 무엇인가요? Ready Queue와 Waiting Queue는 무엇인가요?

❓ 선점형 스케줄링과 비선점형 스케줄링에 대해 설명해주세요.

✅ 비선점형 스케줄링

✅ 선점형 스케줄링

❓ CPU 스케줄링 알고리즘의 종류는 어떤 것들이 있나요?

✅ 비선점형 스케줄링

▶️ 선입 선처리 (FCFS: First Come First Served)

▶️ 최단 작업 우선 (SJF: Shortest Job First)

✅ 선점형 스케줄링

▶️ 우선순위 스케줄링(Priority Scheduling)

▶️ 라운드 로빈(RR: Round Robin)

▶️ 최소 잔여 시간 우선(SRTF: Shortest Remaining Time First)

📌 스케줄링 알고리즘 요약

❓ 프로세스 동기화가 무엇인가요?

❓ 생산자-소비자 문제(Producer-Consumer Problem)에 대해 설명해주세요.

❓ 공유 자원과 임계 구역에 대해 설명해주세요.

❓ 뮤텍스 락과 세마포어는 어떤 차이점이 있나요?

✅ 뮤텍스 락(Mutex Lock, Mutual Exclusion Lock):

✅ 세마포어(Semaphore)

❓ 모니터(Monitor)에 대해 설명해주세요.

✅ 모니터 in Java

▶️ synchronized

▶️ ReentrantLock의 lock()

Reference

[컴구웅 스터디 6회차] 프로세스와 스레드

[컴구웅 스터디 8회차] 교착 상태(Deadlock), 페이징을 통한 가상 메모리 관리

0개의 댓글

▶️ `synchronized`

▶️ `ReentrantLock`의 `lock()`