과제 3: 병행 프로세스

병행 프로세스에 관한 문제입니다.
마감일까지 문제를 풀어 제출하시기 바랍니다.
워드프로세서로 작업하기 어려우면, 손으로 풀어 스캔해서 제출해도 됩니다.

과제3.hwp

<작업전>

추후 업로드 예정

<작업후>

과제3+done (1).docx

운영체제 과제 # 3

 

 

1 [20점] 상호배제 문제를 해결하기 위하여 다음과 같은 (Dekker's algorithm과 비슷한) 프로그램을 작성했으나, 상호배제가 안 되는 경우가 발생했다. 어느 경우에 이 프로그램이 잘못될 수 있는지, 그 시나리오를 만들어 보라. 이 문제에서 시나리오라 함은 P1과 P2 프로세스의 각 행이 실행될 때, 각 변수가 어떻게 변하는가를 추적하는 일이다. P1과 P2의 각 행이 어떤 순서로 실행되면 상호배제가 안 되는가?

 

<Solution>

             

아래 코드는 전체 코드중 잘못된 부분이다. 아래의 코드가 parbegin/parend, 즉 병행실행이 되면 프로세서가 동시에 실행이 되기 때문에 상호배제가 되지 않는다. 따라서 결과값도 예상하기 힘들다. 이를 해결하기 위해서, 순차적으로 실행을 시켜줘야한다. Begin/End 로 해결할 수 있다.

             

Parbegin -> begin                    

P1;

P2

Parend -> end

 

 

 

 

 

program Mystery;

                           var turn: integer; c1, c2: integer;

                           procedure P1;

                           begin

                              while true do

                                begin

                                      c1 := 0;

                                        while turn = 2 do

                                           begin

                                                      while c2 = 0 do;

                                                      turn := 1

                                           end;

                                        critical_section1;

                                        c1 := 1;

                                        remainder1

                                end

                           end;

                           procedure P2;

                           begin

                              while true do

                                begin

                                      c2 := 0;

                                        while turn = 1 do

                                           begin

                                                      while c1 = 0 do;

                                                      turn := 2

                                           end;             

                                        critical_section2;

                                        c2 := 1;

                                        remainder2

                                end

                           end;

                           begin (* Main Program *)

                              c1 := 1;

                              c2 := 1;

                              turn := 1;

                              parbegin                   

                                        P1;

                                        P2

                              parend        

                           end.

 

 

2 [20점] 다음의 선행 그래프를 병행문장(parbegin/parend)을 이용하여 프로그램 하라.

 

 

 

 

 

<Solution>

 

S1;

Parbegin

S4;

Parbegin

S2;

S3;

Parend

S5;

Parend

S6;

 

 

 

 

 

 

 

 

3 [20점] Test-and-Set 명령을 이용하여 lock은 false로 초기화하고 각 프로세스 Pi의 구조는 아래와 같이 하여 상호배제 문제를 해결했다. 만약, TestAndSet 명령이 원소적이 아니라면, 상호배제가 안 되는 경우가 발생할 수 있다. 어느 경우에 잘못될 수 있는지, 그 시나리오를 만들어 보라.                              

                           do {

                              while TestAndSet(&lock))

                        ; // do nothing

                                       // critical section

                              lock = false;

                                        // remainder section

                           } while (true);

 

 

<Solution>

 

원자적 연산

원자적 연산은 중단없이 실행하고 중간에 다른 사람이 수정할 수 없는 최소 단위 연산이다. 메모리의 1비트에서 작동하고, 대다수 기계에서 워드의 메모리 참조, 할당은 원자적이지만 나머지 명령은 원자적이지 않다.

 

TestAndSet 명령어는 일부 시스템에서 원자 명령어의 하나로, 읽기와 쓰기 모두를 제공한다. 이 명령어는 해당 주소의 값을 읽고 새 값으로 교체하면서 해당 메모리 위치의 이전 값을 돌려준다. 다시 말해, 레지스터에 메모리 워드의 내용을 읽어와 그 위치에 1 값을 기록한 후 메모리의 이전 내용을 반환 하는 일련의 원자적 연산을 수행한다.

 

부울변수 lock을 사용하여 프로세스가 임계 영역에 있으면 1로, 없으면 0으로 설정할 수 있다. 그러므로 기계가 TestAndSet 명령어를 지원할 때는 부울 변수 lock을 false로 초기화하여 상호배제를 구현할 수 있다.

 

 

따라서,TestAndSet가 원소적이아니라면 원자적 연산을 할 수가 없다.

원자적 연산이 안되면 상호배제도 되지 않는다.

4 [20점] UNIX 기계에서 다음의 명령을 입력했다.

                           % cp oldfile newfile

UNIX가 이 명령을 수행하는 과정을 프로세스의 생성, 파일의 접근 등 시스템 호출을 중심으로 설명하라.

 

 

<Solution>

프로세스 생성과정

새로운 프로세스에 프로세스 식별자를 할당한다.

프로세스의 모든 구성 요소를 포함하고 있는 주소 공간과 프로세스 제어 블록공간을 할당한다.

프로세스 제어 블록을 초기화 한다. 프로세스 상태, 프로그램 카운터 등 초기화, 자원 요청, 프로세스 제어 정보(우선순위)등을 포함한다.

링크를 건다.(해당큐에 삽입한다.)

 

Fork 명령어로 새로운 프로세스를 생성하면 부모 프로세스의 주소 공간을 복사하여 부모 프로세스와 자식 프로세스의 정보를 쉽게 교환할 수 있다. 부모 프로세스와 자식 프로세스가 fork 명령어를 동시에 실행을 계속하면 자식 프로세스는 식별자가 0이 되고, 자식 프로세스의 식별자는 부모 프로세스의 식별자가 된다. 즉, fork명령어를 실행하면 자식프로세스에는 0을 반환하지만, 부모 프로세스에는 자식 프로세스의 식별자를 반환한다.

 

<요약>

Cp는 자식 프로세스 생성하는 코드이며 프로세스 생성은 fork명령을 이용한다.

Fork는 현재 프로세스를 부모 프로세스로 하고, 새로 생성된 프로세스를 자식 프로세스라고 한다. 부모 프로세스와 자식 프로세스는 병행 수행이 가능하며 두 프로세스의 주 기억장치의 공간은 공유하지 않으나 오픈파일은 모두 공유하고, 부모 프로세스의 기록 가능한 데이터 세그먼트들은 자식 프로세스에 모두 복사된다.

 

 

 

 

부모프로세스

è  자식의 자원 공유를 제한할 수 있으며 동작 종료시 운영체제에게 자원 사용 종료를 알리며 자식 프로세스가 종료되더라도 부모프로세스는 종료되지 않는다.

자식프로세스

è  부모의 자원을 공유하여 사용할 수 있으며, 동작종료시 부모프로세스에게 반납, 부모 프로세스 종료시 자식프로세스도 같이 종료한다.

 

 

5 [20점] 생산자-소비자 문제를 해결하기 위하여, 다음과 같이 알고리즘을 작성했다. 그러나 이 프로그램에는 bug이 있어서 교착상태가 발생한다. 어떤 경우에 교착상태가 발생하는지 그 시나리오를 만들어 보라. 이 문제에서 시나리오라 함은 producer와 consumer 프로세스의 각 행이 실행될 때, 각 변수가 어떻게 변하는가를 추적하는 일이다. producer와 consumer의 각 행이 어떤 순서로 실행되면 교착상태가 발생하는가? 그 이유는? 어떻게 수정하면 되는가?              

<Solution>

Parbegin~ parend 에서 병행수행이 되면 교착상태가 발생한다. 왜냐하면 프로세서가 병행하여 사용하고 있기 때문에, 결과값을 예상할 수 없다. 따라서 교착상태가 발생하고 이를 해결하기 위해서는 프로세서를 순차적으로 실행시켜주어야 한다. 그 방법으로는 begin / end로 바꾸는 방법이 있겠다.

program producer_consumer;

                           var n: integer; mutex, delay: semaphore;

                           procedure producer;

                           begin

                             while true do

                               begin

                                        produce;

                                        wait(mutex);

                                        append;

                                        n := n + 1;

                                        if n = 0 then signal(delay);

                                        signal(mutex)

                               end

                           end;

                           procedure consumer;

                           begin

                             while true do

                               begin

                                        wait(mutex);

                                        n := n - 1;

                                        if n = -1 then wait(delay); (* Here's the bug!! *)

                                        take;

                                        signal(mutex);

                                        consume

                               end

                           end;

                           begin

                             n:= 0;

                             mutex := 1;

                             delay := 0;

                             parbegin  -> begin

                               producer;

                               consumer

                             parend  ->  end

                           end.