[OS] Mutex, Semaphore, Monitor

Monitor

The difficulty of using semaphore

• 세마포어는 synchronizatio에 편리하고 효과적이다.
• 하지만 timing errors(타이밍 문제) 발생 e.g. semaphore’s problem
  • 모든 프로세스가 1로 초기화된 바이너리 세마포어 뮤텍스를 사용하는 경우, 모든 프로세스는 임계영역 진입 전에 wait(mutex)를, 임계영역을 빠져나올 때 signal(mutex)를 호출해야 한다. 만약 이 과정이 없다면 임계영역에 여러 프로세스가 존재하는 순간이 발생할 수 있다.

💡 timing error(타이밍 문제)란? 특정 시점에 따라 문제가 발생할 수도 발생하지 않을 수도 있는 문제를 의미하며, 대처와 디버깅이 어렵다. 예를 들어, 프로그래머가 잘못 코드를 작성하면 Context Switch가 발생하는 타이밍에 따라 문제가 발생할 수도, 발생하지 않을 수도 있다.

위와 같은 문제점을 방지하기 위해 고수준의 동기화 도구인 monitor 탄생했다.

monitor type

• 상호 배제(mutual exclusion)를 제공해주는 기능들을 포함한 ADT

conditional variable

• 모니터는 몇몇 동기화 스키마를 모델링 할 때 부족했기 때문에 추가적인 동기화 메커니즘을 제공하는 condition 이라는 도구를 정의해야 했다.
• condition variable은 wait(), signal() 메소드를 제공한다.

/* exmaple using conditional variables */
condition x, y;
x.wait();
x.signal();

Java Monitors

• monitor-lock 혹은 intrinsic-lock이라고 불리는 쓰레드 동기화 도구인 monitor-like를 제공한다.

  e.g. synchronized keyword, wait(), notify() method

• synchronized 키워드

  • 임계영역에 해당하는 코드 블록을 선언할 때 사용하는 Java의 키워드
  • synchronized 키워드로 선언된 코드 블록(임계 영역)에는 모니터 락을 획득해야 진입 가능
  • 모니터락을 가진 객체 인스턴스를 지정 가능
  • 메소드에 선언하면 메소드 코드 블록 전체가 임계 영역으로 지정되고, 이 때, 모니터락을 가진 객체 인스터는 this 인스턴스

synchronized (object) {
	// critical section
}

public synchronized void add() {
  // critical section
}

• wait(), notify() 메소드
  • Java의 모든 객체가 가진 메소드(java.lang.Object 클래스에 선언된 메소드)
  • 쓰레드가 어떤 객체의 wait() 메소드를 호출하면 해당 객체의 모니터락을 획득하기 위해 대기 상태로 진입
  • 쓰레드가 어떤 객체의 nofity() 메소드를 호출하면 해당 객체 모니터에 대기 중인 쓰레드 하나를 깨운다.
  • notifyAll() 메소드를 호출하면 해당 객체 모니터에 대기 중인 모든 쓰레드를 깨운다.

e.g. Java Non-Synchronization Example

public class NonSyncronizationExample {
	static class Counter {
		public static int count = 0;
		public static void increment() {
			count++;
	  }
	}

	static class MyRunnable implements Runnable {
		@Override
		public void run() {
			for (int i = 0; i < 10000; i++) {
				Counter.increment();
			}
		}
  }

	public static void main(String[] args) throws Exception {
		Thread[] threads = new Tread[5];
		for (int i = 0; i < threads.length; i++) {
			threads[i] = new Thread(new MyRunnable());
			threads[i].start();
    }
		for (int i = 0; i < threads.length; i++) {
			threads[i].join();
		}
		System.out.println("counter = " + Counter.count);
  }
}

e.g. Java Synchronization Example1

public class SyncronizationExample1 {
	static class Counter {
		public static int count = 0;
		synchronized public static void increment() {
			// This code block is critical section
			// since this block is defined with synchronized keyword
			count++;
	  }
	}

	static class MyRunnable implements Runnable {
		@Override
		public void run() {
			for (int i = 0; i < 10000; i++) {
				Counter.increment();
			}
		}
  }

	public static void main(String[] args) throws Exception {
		Thread[] threads = new Tread[5];
		for (int i = 0; i < threads.length; i++) {
			threads[i] = new Thread(new MyRunnable());
			threads[i].start();
    }
		for (int i = 0; i < threads.length; i++) {
			threads[i].join();
		}
		System.out.println("counter = " + Counter.count);
  }
}

e.g. Java Synchronization Example2

public class SyncronizationExample2 {
	static class Counter {
		private static Object object = new Object();
		public static int count = 0;
		public static void increment() {
			synchronized (object) {
				count++;
			}
	  }
	}

	static class MyRunnable implements Runnable {
		@Override
		public void run() {
			for (int i = 0; i < 10000; i++) {
				Counter.increment();
			}
		}
  }

	public static void main(String[] args) throws Exception {
		Thread[] threads = new Tread[5];
		for (int i = 0; i < threads.length; i++) {
			threads[i] = new Thread(new MyRunnable());
			threads[i].start();
    }
		for (int i = 0; i < threads.length; i++) {
			threads[i].join();
		}
		System.out.println("counter = " + Counter.count);
  }
}

e.g. Java Synchronization Example3

public class SyncronizationExample3 {
	static class Counter {
		public static int count = 0;
		public void increment() {
			synchronized (this) {
				Counter.count++;
			}
	  }
	}

	static class MyRunnable implements Runnable {
		Counter counter;

		public MyRunnable(Counter counter) {
			this.counter = counter;
		}

		@Override
		public void run() {
			for (int i = 0; i < 10000; i++) {
				counter.increment();
			}
		}
  }

	public static void main(String[] args) throws Exception {
		Thread[] threads = new Tread[5];
		for (int i = 0; i < threads.length; i++) {
			threads[i] = new Thread(new MyRunnable(new Counter()));
			threads[i].start();
    }
		for (int i = 0; i < threads.length; i++) {
			threads[i].join();
		}
		System.out.println("counter = " + Counter.count);
	}
}

e.g. Java Synchronization Example4

public class SyncronizationExample4 {
	static class Counter {
		public static int count = 0;
		public void increment() {
			synchronized (this) {
				Counter.count++;
			}
	  }
	}

	static class MyRunnable implements Runnable {
		Counter counter;

		public MyRunnable(Counter counter) {
			this.counter = counter;
		}

		@Override
		public void run() {
			for (int i = 0; i < 10000; i++) {
				counter.increment();
			}
		}
  }

	public static void main(String[] args) throws Exception {
		Thread[] threads = new Tread[5];
		Counter counter = new Counter();
		for (int i = 0; i < threads.length; i++) {
			threads[i] = new Thread(new MyRunnable(counter));
			threads[i].start();
    }
		for (int i = 0; i < threads.length; i++) {
			threads[i].join();
		}
		System.out.println("counter = " + Counter.count);
	}
}

Liveness

• 세마포어와 모니터는 Critical Secion Problem의 progress(avoid deadlock), bounded-waiting(avoid starvation)을 충족하지 못 한다. 이를 해결하기 위해 등장한 개념이 Liveness
• Liveness의 두 가지 기능: deadlock, priority inversion

💡 Deadlock이란? 두 개 이상의 프로세가 대기 중인 프로세스 서로의 작업 종료 이벤트를 무한정 기다리는 상황