Blog For Me

1. 교착 상태(Dead lock) 한정된 자원을 여러 곳에서 사용하려고 할 때 발생하는 문제 프로세스가 공유 자원을 얻지 못하여 다음 작업을 처리하지 못하는 상황 프로세스 1과 프로세스 2가 모두 자원 A, 자원 B를 얻어야 한다고 할 때, 우선 프로세스 1은 자원 A를 얻었고 프로세스 2는 자원 B를 얻은 상태이다. 그리고 그 상황에서 프로세스 1은 자원 B를 기다리고, 프로세스 2는 자원 A를 기다리고 있다. 여기서 현재 서로 원하는 자원이 상대방에게 할당되어 있어 두 프로세스는 무한정 wait 상태에 빠지게 되고 이러한 상황을 deadlock(교착 상태)라 한다. 2. 교착 상태 발생 조건 교착 상태는 4가지 조건이 동시에 성립할 때 발생한다. 4가지 조건 중 하나라도 성립하지 않으면 교착 상태 ..

The Dining Philisophers Problem(식사하는 철학자 문제) 출처: Operating System Concepts tenth Edition, Abraham Silberschatz, Peter Baer Galvin, Greg Gagne 철학자 다섯 명이 원형 테이블에서 식사를 하려고 한다. 테이블 중앙에 음식이 있고, 다섯 개의 젓가락이 철학자 사이에 놓여 있다. 철학자가 배고파서 음식을 먹으려 할때 자신의 왼쪽과 오른쪽 젓가락을 잡으려고 하고, 두 젓가락을 잡아야 식사가 가능하다. 이후 식사가 끝나면 젓가락 두 개를 테이블에 놓고 다시 생각에 빠지는 상황이다. 철학자 문제 알고리즘은 다음과 같다. while(true) { wait(chopstick[i]); // 왼쪽 젓가락 집기 wa..

1. The Bounded-Buffer Problem 여기에서는 두 종류의 프로세스가 있는데, 하나는 Producer 프로세스, 또 다른 하나는 Consumer 프로세스이다. 즉, 이는 생산자-소비자 문제(Producer-Consumer Problem)이라고도 불린다. Producer 프로세스는 데이터를 만들어 버퍼에 삽입하고, Consumer 프로세스는 버퍼에서 데이터를 꺼내는 역할을 수행한다. 여기서 발생할 수 있는 문제점은 어느 생산자 프로세스가 버퍼 중 빈 곳에 데이터를 쓰려고 할때, Interrupt가 발생하여 다른 프로세스한테 공유자원이 넘어가서 다른 프로세스가 해당하는 빈 곳에 데이터를 쓸 때 나타날 수 있다. 그렇게 되면 둘 중에 한 프로세스의 데이터가 유실될 수 있을 가능성이 농후하기 때..

최근에 lock 방법이 지닌 문제점을 해결하기 위하여 소프트웨어적 방법을 이용하기보다는 더 이상 쪼개지지 않는 원자적 명령어로 구현하거나 Interrupt 제어로 해결한다. 하드웨어 명령어 lock 함수 코드부분 void lock(struct lock *i) { while(i->held); i->held=1; } 이 lock 함수의 문제점은 A 프로세스가 2번 라인의 코드를 실행하고 다음에 3번 라인의 코드를 실행하기 직전에 Interrupt 걸렸을 상황에서 두드러진다. 즉, A 프로세스가 3번 코드인 'i->held=1'을 실행하기 직전에 Interrupt 걸려서 B 프로세스로 전환된 것이다. 그럼 B 프로세스는 아직 held 값이 0인 걸 보고 바로 임계영역에 진입해버리므로 Race Condition..

Peterson's Algorithm은 1981년 수학자였던 개리 피터슨이라는 사람이 고안한 알고리즘이다. 발표 당시 이 알고리즘에서는 오직 두 개의 프로세스에만 적용 가능하다고 했었지만 지금은 2개 이상의 프로세스들 사이에서도 이 방법이 통용된다. Lock 방식이 지니고 있는 문제점을 해결하기 위해 고안된 알고리즘이라 볼 수 있다. Peterson's Algorithm 구조 여러 개의 프로세스가 있을 때, i번째 프로세스의 Peterson 알고리즘 구조도 // flag: 신호, 공유자원을 사용하고 싶다라고 표현하기 위한 변수, 임계구역에 들어갈 때는 true, 나올 때는 false로 설정 // turn: 차례, 누구 차례인지를 명시하는 변수, turn = 0 이면, 0번째 프로세스가 임계 구역에 들어가..

Lock Lock은 의미 그대로 잠군다는 것을 뜻한다. 마치 화장실을 사용하고 있는 동안에 문을 잠궈서 자기가 사용하는 동안 아무도 못 들어오게 하는 것처럼, 특정 프로세스나 스레드가 lock을 통해 임계 영역을 잠궈서 혼자 사용할 수 있게 하는 방법이다. 이는 동기화 기법의 한 가지 방법이다. 은행 계좌 관련 사례를 살펴보자면 다음과 같다. A라는 사람과 B라는 사람이 같은 계좌를 공유하고, 그 계좌에는 현재 100만원 있다. 이때 우연찮게도 A와 B는 동시에 그 계좌에서 10만원을 인출하는 상황이 발생했다. 여기서 A라는 사람이 인출을 했는데 인출함수 수행하는 과정에서 4번째 줄에서 Timer Interrupt가 발생했다면, 스케줄러에 의해 B가 10만원을 인출하는 프로세스가 이 함수를 수행하는데, ..