운영체제(6) Synchronization Tools

Shy·2023년 4월 8일
운영체제
0

운영체제

목록 보기
1/8

학습 목표 및 학습 내용

학습 목표

  • 동기화의 필요성을 설명할 수 있다.
  • 임계 구역 문제를 설명할 수 있다.
  • 세마포어의 정의와 사용법을 설명할 수 있다.

학습 내용

  • Critical Section Problem
  • Synchronization Hardware
  • Semaphore

운영체제에서 다중 프로세스나 스레드가 실행되는 동안, 공유 데이터에 동시에 접근하면 데이터 불일치 및 오류가 발생할 수 있습니다. 이를 처리하기 위해 Race Condition과 Critical Section Problem에 대해 알아봅니다.

Race Condition

  • Concurrent access to shared data may result in data inconsistency.
  • Race condition
    • Situation where several processes access & manipulate shared data concurrently.
    • To prevent race conditions, concurrent processes must be synchronized.
    • In uniprocessor environment, race condition can also occur by CPU scheduler.
  1. Race Condition
    Race Condition은 여러 프로세스나 스레드가 공유 데이터에 동시에 접근하고 조작할 때 발생하는 상황입니다. 이로 인해 데이터 불일치 및 오류가 발생할 수 있으며, 이를 방지하기 위해 동시성 프로세스를 동기화해야 합니다. 유니프로세서 환경에서도 CPU 스케줄러에 의해 레이스 컨디션이 발생할 수 있습니다.

Critical Section Problem

  • Critical section
    • A code segment in which the shared data is accessed.
  • Critical section problem
  • ensure that when one process is executing in its critical section, no other processes are allowed to execute in its critical section.
  1. Critical Section Problem
    Critical Section은 공유 데이터에 접근하는 코드 영역을 의미합니다. 크리티컬 섹션 문제는 하나의 프로세스가 자신의 크리티컬 섹션에서 실행되고 있을 때, 다른 프로세스가 동시에 그 크리티컬 섹션에 들어갈 수 없도록 보장하는 것입니다.

Critical Section Problem

  • It is required to design a protocol that the processes can use to cooperate.
  • General structure of a typical process Pi
    • Entry section
      • code segment of requesting permission to enter the critical section.
    • Exit section
      • code segment of notifying the exit of the critical section.

이 문제를 해결하기 위해 프로토콜을 설계해야 합니다. 일반적인 프로세스 Pi의 구조는 다음과 같습니다:

  • Entry section: 크리티컬 섹션에 들어가기 위한 허가를 요청하는 코드 영역입니다.
  • Exit section: 크리티컬 섹션에서 나오는 것을 알리는 코드 영역입니다.

프로세스는 동기화를 통해 크리티컬 섹션에 동시에 들어가는 것을 방지하고, 데이터 불일치 및 오류를 피할 수 있습니다. 이를 통해 프로세스 간의 협력 및 공유 데이터에 대한 안정적인 접근이 가능해집니다.

다음으로, 크리티컬 섹션 문제를 해결하기 위한 요구사항과 해결 방법을 살펴보겠습니다.

Requisites for solution

  • Mutual Exclusion
    • If process Pi is executing in its critical section,
    • then no other processes can be executing in their critical sections.
  • Progress
    • If no process is executing in its critical section and
    • there exist some processes that wish to enter their critical section,
    • then the selection of the processes that will enter the critical section next cannot be postponed indefinitely.
  • Bounded Waiting
    • A time bound must exist to prevent the starvation.
  1. 해결 방법의 요구사항:
  • 상호 배제(Mutual Exclusion): 프로세스 Pi가 크리티컬 섹션에서 실행 중이면, 다른 프로세스는 자신의 크리티컬 섹션에서 실행할 수 없습니다.
  • 진행(Progress): 크리티컬 섹션에서 실행 중인 프로세스가 없고, 크리티컬 섹션에 들어가려는 프로세스가 있으면, 다음에 크리티컬 섹션에 들어갈 프로세스를 무한정 미루지 않고 선택해야 합니다.
  • 유한 대기(Bounded Waiting): 기아 상태(Starvation)를 방지하기 위해 시간 제한이 존재해야 합니다.

Critical-Section Handling

  • Two approaches depending on if kernel is preemptive or non-preemptive
    • Preemptive – allows preemption of process when running in kernel mode
    • Non-preemptive – runs until exits kernel mode, blocks, or voluntarily yields CPU
      • Essentially free of race conditions in kernel mode
  1. 크리티컬 섹션 처리:
    커널이 선점형(preemptive)인지 비선점형(non-preemptive)인지에 따라 두 가지 접근 방법이 있습니다.
    선점형: 커널 모드에서 실행 중인 프로세스를 선점할 수 있습니다.
    비선점형: 커널 모드에서 종료할 때까지 실행되거나, 블록되거나, 자발적으로 CPU를 양보합니다. 이 방식은 기본적으로 커널 모드에서 레이스 컨디션을 방지합니다.

Peterson’s Solution

  • Solution for two processes synchronization.
  • The two processes share two variables.
    • int turn;
      • whose turn it is to enter the critical section.
    • boolean flag[2];
      • indicates if a process is ready to enter the critical section.
      • flag[i] = true, if process Pi is ready.

3.피터슨의 솔루션(Peterson's Solution):

  • 두 개의 프로세스 동기화를 위한 솔루션입니다.
  • 두 프로세스는 두 개의 변수를 공유합니다.
    • int turn; 크리티컬 섹션에 들어갈 차례를 나타냅니다.
    • boolean flag[2]; 프로세스가 크리티컬 섹션에 들어갈 준비가 되어 있는지를 나타냅니다. flag[i] = true이면, 프로세스 Pi가 준비된 것입니다.

Peterson’s Solution

피터슨의 솔루션은 위의 그림처럼 동작합니다. 프로세스는 크리티컬 섹션에 들어가기 전에 준비 상태를 설정하고, 다른 프로세스의 차례를 기다립니다. 그런 다음 크리티컬 섹션에 들어가 작업을 수행한 후, 준비 상태를 해제하고 다른 프로세스에게 차례를 넘깁니다.

이 방법을 사용하면 두 개의 프로세스가 상호 배제, 진행 및 유한 대기 원칙을 준수하면서 크리티컬 섹션에 안전하게 접근할 수 있습니다. 피터슨의 솔루션은 두 프로세스에 대한 간단한 동기화를 제공하지만, 더 많은 프로세스에 대해서는 확장되지 않습니다.

그러므로, 더 많은 프로세스를 지원하는 다른 동기화 기법이 필요합니다. 세마포어(Semaphore), 뮤텍스(Mutex), 모니터(Monitor) 등의 동기화 기법을 사용하여 더 큰 규모의 프로세스 동기화 문제를 해결할 수 있습니다. 이러한 기법들은 상호 배제, 진행 및 유한 대기 원칙을 준수하여 프로세스 간 공유 데이터에 대한 동시 접근을 안전하게 관리합니다.

Synchronization Hardware

  • Simple tool - lock
  • Modern machines provide special atomic hardware instructions.
    • Atomic = non-interruptable
    • Either test memory word and set value, or
    • swap contents of two memory words.
  • TestAndSet instruction
    • Test and modify the content of a word atomically.
  • Shared boolean variable lock is initialized to false.
  • Solution
  • Swap instruction
    • Switch the values of two words.
void Swap (boolean *a, boolean *b)
{
	boolean temp = *a;
    *a = *b;
    *b = temp:
}
  • Shared boolean variable lock is initialized to FALSE.
  • Each process has a local boolean variable key.
while (true) {
	key = TRUE;
	while (key == TRUE)
		swap (&lock, &key);
	critical section
	lock = FALSE;
	remainder section
}

“key == true” means “I want to enter”.
“lock == true” means “He entered”.

  • Simple tool - lock
  • Modern machines provide special atomic hardware instructions.
    • Atomic = non-interruptable
    • Either test memory word and set value, or
    • swap contents of two memory words.
  • TestAndSet instruction
    • Test and modify the content of a word atomically
boolean TestAndSet (boolean *target)
{
	boolean rv = *target;
	*target = TRUE;
	return rv:
}
  1. Return original value.
  2. Set the value to true.
  • Shared boolean variable lock is initialized to false.
  • Solution
while (true) {
	while (TestAndSet(&lock )) ; /* do nothing */
	critical section
	lock = FALSE;
	remainder section
}
  1. Return the value of ‘lock’.
  2. Set ‘lock’ to true.
  • Swap instruction
    • Switch the values of two words.
void Swap (boolean *a, boolean *b)
{
	boolean temp = *a;
	*a = *b;
	*b = temp:
}
  • Shared boolean variable lock is initialized to FALSE.
  • Each process has a local boolean variable key.

동기화를 지원하는 하드웨어 기능에 대해 살펴보겠습니다. 이러한 하드웨어 기능은 프로세스 간 동기화를 더욱 효과적으로 처리할 수 있도록 돕습니다.

1.간단한 도구 - 잠금(lock)

  • 잠금(lock)은 공유 리소스에 대한 동시 접근을 제한하는 기본적인 도구입니다.

2.원자적(atomic) 하드웨어 명령

  • 최신 머신에서는 원자적(atomic) 하드웨어 명령을 제공합니다. 원자적이라는 것은 명령이 중단되지 않는다는 것을 의미합니다.
  • 메모리 워드를 테스트(test)하고 값을 설정(set)하거나, 두 메모리 워드의 내용을 교환(swap)하는 데 사용됩니다.

3.TestAndSet 명령

  • 명령은 워드의 내용을 원자적으로 테스트하고 수정합니다.
  • 공유된 boolean 변수 lock은 false로 초기화됩니다.
  • 솔루션은 아래와 같이 작동합니다.
while (true) {
    while (TestAndSet(&lock )) ; /* do nothing */
    critical section
    lock = FALSE;
    remainder section
}
  • lock의 값을 반환하고, lock 값을 true로 설정합니다

4.Swap 명령

  • Swap 명령은 두 워드의 값을 교환합니다.
void Swap (boolean *a, boolean *b)
{
    boolean temp = *a;
    *a = *b;
    *b = temp:
}
  • 공유된 boolean 변수 lock은 FALSE로 초기화됩니다.
  • 각 프로세스는 로컬 boolean 변수 key를 가집니다.
  • 솔루션은 아래와 같이 작동합니다.
while (true) {
    key = TRUE;
    while (key == TRUE)
        swap (&lock, &key);
    critical section
    lock = FALSE;
    remainder section
}
  • "key == true"는 "들어가고 싶다"는 의미이고, "lock == true"는 "그가 들어갔다"는 의미입니다.

이러한 하드웨어 기반 동기화 기능을 사용하면 프로세스 간 동기화를 더욱 효율적으로 처리할 수 있습니다. 이 기능은 원자적 동작을 보장하여 프로세스가 공유 데이터에 대한 안전한 접근을 유지할 수 있도록 돕습니다.

Semaphore

  • Semaphore S

    • just integer variable

  • Two standard operations to modify S.

    • wait() and signal()
      • originally called P() and V().

  • Usage of semaphore

    • There are two processes Pi & Pj and two critical sections A & B.
    • Initialize S to 1.

  • Binary semaphore

    • integer value can range only between 0 and 1.
    • Provides mutual exclusion

  • Counting semaphore

    • integer value can range over an unrestricted domain.

세마포어(Semaphore)는 프로세스 간 동기화를 관리하는 데 사용되는 정수 변수입니다. 세마포어는 두 가지 기본 연산, wait()와 signal()을 사용하여 수정할 수 있습니다. 이들은 원래 P()와 V()로 불렸습니다.

세마포어의 사용 예시는 다음과 같습니다. 두 개의 프로세스 Pi와 Pj와 두 개의 크리티컬 섹션 A와 B가 있습니다. 세마포어 S를 1로 초기화합니다. 프로세스는 크리티컬 섹션에 들어가기 전에 wait()를 호출하고, 크리티컬 섹션에서 나올 때 signal()을 호출합니다. 이렇게 함으로써 다른 프로세스가 크리티컬 섹션에 동시에 접근하는 것을 방지할 수 있습니다.

세마포어는 두 가지 유형이 있습니다.

1.바이너리 세마포어(Binary Semaphore) :

  • 정수 값의 범위가 오직 0과 1 사이입니다.
  • 상호 배제(mutual exclusion)를 제공합니다.

2.카운팅 세마포어(Counting Semaphore) :

  • 정수 값의 범위가 제한 없이 확장될 수 있습니다.
  • 프로세스가 공유 자원에 대한 동시 접근을 조정하거나, 특정 수의 프로세스가 동시에 수행되는 것을 허용하는 데 사용됩니다.

세마포어는 프로세스 간 동기화를 효과적으로 관리하고, 프로세스가 공유 데이터에 안전하게 접근할 수 있도록 도와주는 중요한 동기화 도구입니다.

Semaphore implementation

  • Busy waiting

    • While a process is in critical section, other processes must loop continuously.
    • is also called a spinlock.
    • wastes CPU cycles.

  • Block and wakeup

    • There is an associated waiting queue for each semaphore.

  • Two operations

    • Block
      • Suspends the process that invoked P(S) itself.
      • Inserts this process’ PCB into wait queue for semaphore S.
    • Wakeup(P)
      • Removes a process P’s PCB from wait queue for semaphore S.
      • Resumes the execution of P.

  • Implementation of semaphore with block and wakeup.

P(S){
	S.value--;
	if (S.value < 0) {
		add this process to waiting queue.
		block();
	}
}
V(S){
	S.value++;
	if (S.value <= 0) {
		remove a process P from the waiting queue.
		wakeup(P);
	}
}
  • Which is better?
    • Busy-waiting
      • No context switching is required.
      • It is good when the length of critical section is short.
    • Block-wakeup
      • Context switching is required.
      • It is good when the length of critical section is long.

세마포어 구현은 크게 두 가지 방식으로 나뉩니다: 바쁜 대기(Busy waiting)와 블록(Block)과 깨우기(Wakeup).

1.바쁜 대기(Busy waiting):

  • 프로세스가 임계 구역에서 실행되는 동안 다른 프로세스들은 계속해서 루프를 돌아야 합니다. 이를 스핀락(spinlock)이라고도 합니다.
  • 이 방식은 CPU 사이클을 낭비하게 됩니다.

2.블록(Block)과 깨우기(Wakeup):

  • 각 세마포어마다 대기 큐(waiting queue)가 있습니다.
  • 두 가지 연산이 수행됩니다.
    • 블록(Block): P(S)를 호출한 프로세스를 중단하고, 프로세스의 PCB를 세마포어 S의 대기 큐에 삽입합니다.
    • 깨우기(Wakeup): 세마포어 S의 대기 큐에서 프로세스 P의 PCB를 제거하고, 프로세스 P의 실행을 재개합니다.

블록(Block)과 깨우기(Wakeup)를 사용한 세마포어 구현은 다음과 같습니다.

P(S){
	S.value--;
	if (S.value < 0) {
		add this process to waiting queue;
		block();
	}
}
V(S){
	S.value++;
	if (S.value <= 0) {
		remove a process P from the waiting queue;
		wakeup(P);
	}
}

어떤 방식이 더 좋을까요?

  • 바쁜 대기(Busy-waiting):
    • 컨텍스트 전환(context switching)이 필요하지 않습니다.
    • 임계 구역의 길이가 짧을 때 좋습니다.
  • 블록(Block)과 깨우기(Wakeup):
    • 컨텍스트 전환(context switching)이 필요합니다.
    • 임계 구역의 길이가 길 때 좋습니다.

두 방식 모두 장단점이 있으며, 상황에 따라 적절한 방식을 선택하여 사용해야 합니다.

Summary

  • Race condition is a situation where several processes access and manipulate shared data concurrently.
  • The critical section is a code segment in which the shared data is accessed.
  • A semaphore S is an integer variable that is accessed only through P() and V() operations.
  • Busy waiting is good for short critical section, while blockwakeup is good for long critical section.

레이스 컨디션은 여러 프로세스가 동시에 공유 데이터에 접근하고 조작하는 상황을 말합니다. 이를 방지하기 위해 동시성 제어와 동기화가 필요합니다.

임계 구역은 공유 데이터에 접근하는 코드 세그먼트를 말합니다. 임계 구역 문제를 해결하기 위해서는 프로세스 간 협력을 위한 프로토콜을 설계해야 합니다.

세마포어 S는 정수 변수로, P()와 V() 연산만을 통해 접근할 수 있습니다. 이를 통해 프로세스 간 동기화를 관리할 수 있습니다.

바쁜 대기(Busy waiting)와 블록(Block) 및 깨우기(Wakeup) 방식은 세마포어 구현에 사용되는 두 가지 방식입니다. 바쁜 대기는 임계 구역의 길이가 짧을 때 적합하며, 블록 및 깨우기 방식은 임계 구역의 길이가 길 때 적합합니다. 이 두 방식은 각각의 장단점이 있으므로, 상황에 따라 적절한 방식을 선택하여 사용해야 합니다.

profile
Shy
스벨트 자바스크립트 익히는중...

0개의 댓글