[ OS ] 07. Synchronization Examples

38A·2023년 5월 28일

Operating System

목록 보기

7/14

If the buffer is full, the producer must wait until the consumer deletes an item.
- Producer needs an empty space
- # of empty slot is represented by a semaphore empty
If the buffer is empty, the consumer must wait until the producer adds an item.
- Consumer needs an item
- # of item is represented by a semaphore full
Producer-consumer problem with bounded buffer
- Semaphores: full = 0, empty = n, mutex = 1;

There are multiple readers and writers to access a shared data
- Readers can access database simultaneously.
- When a writer is accessing the shared data, no other thread can access it
Behavior of a writer
- If a thread is in the critical section, all writers must wait
- The writer can enter the critical section only when no thread is in its critical section
  - It should prevent all threads from entering the critical section
Behavior of a reader
- If no writer is in its critical section, the reader can enter the critical section.
- Otherwise, the reader should wait until the writer leaves the critical section.
- When a reader is in its critical section, any reader can enter the critical section, but no writer can
  - Condition for the first reader is different from the following readers → exist writer in critical section?
Shared data
- semaphore mutex=1, wrt=1;
- int readcount = 0;
  - # of readers in critical section
Writer
wait(wrt);
...
writing is performed
...
signal(wrt);
Reader
wait(mutex); → mutual exclusion
readcount++;
if (readcount == 1) wait(wrt); → first reader
signal(mutex); → mutual exclusion
...
reading is performed
...
wait(mutex); → mutual exclusion
readcount--;
if (readcount == 0) signal(wrt); → last reader
signal(mutex); → mutual exclusion

Problem definition
- 5 philosophers sitting on a circular table
  - Thinking or eating(critical section)
- 5 bowls, 5 single chopsticks
- No interaction with colleagues
- To eat, the philosopher should pick up two chopsticks closest to her
- A philosopher can pick up only one chopstick at a time
- When she finish eating, she release chopsticks
A possible solution, but deadlock can occur
Necessary conditions for deadlock → 4개다 성립해야 deadlock
1. Mutual exclusion
2. Hold and wait →
3. No preemption → hold할때 누군가에 의해서 release 해야하는것
4. Circular wait → 가장 쉬운 해결책, 짝수는 left, 홀수는 right

Data structures (Field)
- enum { thinking, hungry(want to eat), eating } state[5];
- condition self[5]; → wait, signal
Process of i-th philosopher implemented by a monitor dp (Method)
dp.pickup(i); // entry section
...
Eat // critical section
...
dp.putdown(i); // exit section

→ Deadlock-free(withour hold and wait), but not starvation-free

→ midterm 1번 확인!

Creation and initialization
#include <pthread.h>
pthread_mutex_t mutex; // global declaration
pthread_mutex_init(&mutex,NULL); // call before first lock
↔️ pthread_mutex_destroy(&mutex);

or

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
→ Global variable 때 편함
Critical section
pthread_mutex_lock(&mutex); // wait
/* critical section */
pthread_mutex_unlock(&mutex); // signal

Multiple unrelated processes(다른 PC끼리 name으로 connect) can easily use a common semaphore
Creation and initialization
#include <semaphore.h>
sem_t *sem; // global declaration
sem = sem_open("SEM", O_CREAT, 0666, 1);
↔️ sem_close(); / sem_unlink() : remove
Critical-section
sem_wait(sem); // acquire the semaphore
/* critical section */
sem_post(sem); // release the semaphore

→ fork() 이전에 생성시 공유

Creation and initialization
#include <semaphore.h>
sem_t sem; → no pointer // global declaration
sem_init(&sem, 0, 1);
↔️ sem_destroy(&sem);
Critical-section>
sem_wait(&sem); // acquire the semaphore
/* critical section */
sem_post(&sem); // release the semaphore

Windows kernel
- A multithreaded kernel
- Provides support for real-time applications
  → preemptive priority scheduling, response time ⬇️ (scheduling을 자주)
- Provides support for multiple processors
Accessing global variables
- Single-processor system: mask interrupt (disable interrupt)
- Multi-processor system: spinlocks
  - Only to protect short code segments
  - The kernel ensures that a thread will never be preempted while holding a spinlock
For thread synchronization outside the kernel, windows provides dispatcher objects
- Mutex locks, semaphores, events, timers
States of dispatcher objects
- Signaled state: the object is available → mutex = 1, unlock
  - Thread will not block when acquiring the object.
- Nonsignaled state: the object is not available → mutex = 0, lock
  - Thread will block when attempting to acquire the object.
  - Its state changes from ready to waiting, and the thread is placed in a waiting queue for that object
Critical section object: a user-mode mutex that can often be acquired and released without kernel intervention
→ Hybrid lock(spinlock + blocking)
- A critical-section object first uses a spinlock while waiting for the other thread to release the object
  ➔ Does not allocate kernel object. (efficient)
- If it spins too long, the acquiring thread will then allocate a kernel mutex and yield its CPU

From v.2.6., Linux kernel is fully preemptive
Atomic integer (atomic_t)
- All math operations are performed without interruption
  Ex) atomic_t counter; → prevent race condition
  int value;
Mutex locks in kernel → 실습 x
- int mutex_init(mutex_t mp, int type, void arg);
- int mutex_lock(mutex_t *mp); → wait
- int mutex_trylock(mutex_t *mp);
- int mutex_unlock(mutex_t *mp); → signal
- int mutex_consistent(mutex_t *mp);
  - Makes a mutex consistent
- int mutex_destroy(mutex_t *mp);
Spinlocks
- spin_lock(), spin_unlock(), etc.
- Useful for short duration
- Inappropriate on single processing core
Enabling/disabling kernel preemption → usermode에서 실행X
- preempt_disable(), preempt_enable()