알고리즘과 병행프로세스 분석

소개글

알고리즘과 병행프로세스 분석에 대한 보고서 자료입니다.

목차

Ⅰ. 알고리즘
1. 알고리즘의 정의
2. 최적의 알고리즘
3. 알고리즘의 기술방법
4. 알고리즘 표현방법
5. 알고리즘 분석

Ⅱ. 병행 프로세스
1 결정성과 경쟁 조건
2 상호배제(Mutual Exclusion)
3. 상호배제 해결
1) 소프트웨어적 해결 방법
* 데커(dekker) 알고리즘
* 피터슨(Peterson) 알고리즘
* Lamport의 알고리즘(bakery algorithm)
2) 하드웨어 방법
4. 세마포어(Semaphores)
5. 모니터(Monitor)
6. 프로세스간의 통신(IPC)

본문내용

. signal해 주는 프로세스 혹은 블록 상태에서 풀린 프로세스 중 하나가 다시 next 큐에서 대기해야 한다.
3) 모니터를 이용한 원형 버퍼(생산자-소비자)
monitor ringbuffermonitor
{
item buffer[slots];
int slotinuse, nextfill, nextempty;
condition HasData, HasSpace;
fillaslot(item s) //생산자
{
if (slotinuse == slots) HasSpace.wait(); // 버퍼공간이 차있으면 대기
buffer[nextfill] = s; // 정보 생산, 저장
slotinuse++;
nextfill = (nextfill+1)%slots;
HasData.signal();// 대기중인 소비자 프로세스를 풀어준다.
}
emptyaslot(item &s) //소비자
{
if (slotinuse == 0) HasData.wait(); // 버퍼에 정보가 없으면 대기
slotdata = buffer[nextempty]; // 정보 소비
slotinuse--;
nextempty = (nextempty+1)%slots;
HasSpace.signal();// 대기중인 생산자 프로세스를 풀어준다.
}
ringbuffermonitor()// 초기화 루틴
{
slotinuse = nextfill = nextempty = 0;
}
}
6. 프로세스간의 통신(IPC)
협동 프로세스들이 서로 통신하여 작동을 동기화할 수 있는 기능 제공
1) 프로세스간 통신(IPC) 기법 - 공유 기억장치(shared memory)를 이용하는 방식 : 세마포어프로세스들 간의 통신을 위해 변수를 공유.
통신 기능을 제공하는 책임은 응용 프로그래머에게 있으며, 운영체제는 공유 기억장치만을 제공.
- 메시지 전달(message passing)을 하는 방식. : 메시지 시스템
프로세스들이 메시지를 교환하며, 통신의 기능을 제공하는 책임은 운영체제에게 있다.
프로세스는 일반적으로 다음과 같은 호출에 의해 메시지를 주고 받음.
send(receiverprocess, message);
receive(senderprocess, message);
2) 프로세스가 전송하는 메시지 길이
고정 길이 메시지 : 구현하기는 간단하지만 프로그래밍 작업은 복잡
가변 길이 메시지 : 구현하기는 복잡하나 높은 적응력을 갖는다.
형식 메시지 : 우편함(mail box) 통신
3) 메시지 시스템의 구현 방법.
직접 또는 간접 통신
대칭 또는 비대칭 통신
자동 또는 명시적인 버퍼링
복사(copy)에 의한 전송 또는 참조(reference)에 의한 전송
고정 길이 또는 가변 길이 메시지
4) 버퍼링
메시지 통신 과정에 있어서 송신측 프로세스가 메시지를 전송하고자 하나 수신측이 준비가 되어 있지 않을 경우 메시지를 저장해야 하는 문제
메시지 큐는 통로에 있는 버퍼로 수용가능한 메시지의 개수를 결정한다.
구현 방법
- 무용량
. 큐의 최대 길이 0(통로에 대기 메시지 없다)
. 송신자는 수신자가 메시지를 수신할 때까지 대기 : 대기 송신(blocking send) 및 대기 수신(blocking receive)
. 메시지 이전을 위해 동기화 필요 : 랑데부(rendezvous)
- 제한 용량
. 큐의 길이 n(통로에 n개의 메시지 대기)
. 메시지가 큐에 놓여지면, 송신자는 대기하지 않고 다음 명령의 실행을 계속
. 큐가 차있으면 큐가 비게 될 때까지 대기 : 비대기 송신(nonblocking send) 및 비대기 수신(nonblocking receive)
- 무한 용량
. 큐의 용량이 무한대
. 송신자는 지연되지 않음.
5) 직접 통신
메시지 송수신을 원하는 각 프로세스가 송신자 혹은 수신자의 이름(예, 프로세스 id)을 정확하게 기술할 것을 요구.
send(receiverprocess, message);
receive(senderprocess, message);
통신하고자 하는 프로세스들 사이의 링크는 send/receive 명령으로 자동 설정
링크는 정확히 두 프로세스 사이에만 설정(일대일 통신)
각 쌍의 프로세스에 대해 하나의 링크만 존재
종류
. 대칭적 직접 통신 : 서로 상대방을 지정
. 비대칭적 직접 통신 : 송신자만 수신자를 지정.
send(P, message); // message를 프로세스 P에 전송
receive(id, message); // 임의의 프로세스로부터 메시지 수신. id는 통신이 발생한 프로세스의 이름으로 설정.
. 프로세스의 이름을 바꾸면, 모든 다른 프로세스 이름을 바꾸어야 함.
6) 간접 통신
메시지들이 메일 박스(mailbox)를 통하여 송신되고 수신.
send(A, message); // message를 메일 박스 A에 전송
receive(A, message); // 메일 박스 A에서 메시지 수신
두 프로세스가 하나의 우편함을 공유해야 링크 설정
한 링크는 2개이상의 프로세스와 연관
통신하는 프로세스 쌍 사이에는 여러 개의 다른 링크 존재(각 링크는 하나의 우편함)
7) 예외 처리
메시지가 처리되기 전에 송신자 혹은 수신자가 종료시 문제
. 교착 상태 발생.
. 해결 : 시스템이 P에게 Q의 종료 사실을 알려주거나 P를 종료.
통신 장애나 hardware 고장으로 메시지 분실
. 운영체제가 감지하여 송신자에게 알리고 메시지를 다시 보내도록 한다.
. 수신자가 감지하여 원하는 경우에는 메시지를 다시 보낸다.
8) 원격 프로시쥬어 호출(remote procedure calls:RPC)
분산 시스템에서 프로세스간 통신을 하는 데 있어, 보다 구조적이고 고급스러운 방식을 지원하기 위하여 고안.
RPC는 한 시스템 프로세스가 다른 시스템에 존재하는 프로세스 내의 프로시쥬어를 호출 할 수 있도록 해줌.
호출한 프로세스는 원격 시스템 내의 호출된 프로시쥬어로 부터의 응답이 올때 까지 블록 상태에 있게 되고 응답이 수신되면 다시 수행을 계속.
RPC는 send/receive를 가지고도 구현.
send(P, input_parameters);
receive(P, output_parameters);

키워드

알고리즘,   병행프로세스,   병행프로세서,   데커,   피터슨,   Lamport,   알고리즘정의,   알고리즘개념