제2부 프로세스 관리(Process Management) 실행중인 프로그램(program in execution) CPU time, memory, files, I/O devices 등 자원 요구 시스템의 작업단위 (the unit of work) 종류 1. 사용자 프로세스(user process) - user code 실행 2. 시스템 프로세스(system process) - system code 실행 프로세스 관리 사용자 프로세스와 시스템 프로세스의 생성과 삭제 프로세스 스케줄링 프로세스들의 동기화 기법 지원 프로세스들의 통신 지원 프로세스들의 교착상태(deadlock)처리 2000 운영체제

프로세스 개념(Process Concept) ~ 제4장 프로세스(Processes) 예전 1 program 실행 -> 오늘날 multiple program의 동시 실행 프로세스 개념(Process Concept) ~ 프로세스 (The Process) 프로그램 코드 + 현재 활동(Current activity) PC(Program Counter) 레지스터 값 스택(stack) : 서브루틴, 매개변수, 복귀주소, 임시변수 등 데이터 부분(data section) : 전역변수 프로세스 상태(Process State) 생성(new) 수행(running) : CPU가 실행 대기(waiting) : I/O완료나 signal 기다림 준비(ready) : Processor를 받을 준비가 됨 종료(terminated) 2000 운영체제

프로세스 상태(Process State) 2000 운영체제

프로세스 개념(Process Concept) 프로세스 제어 블럭(Process Control Block) 각 프로세스는 PCB로 표현됨 PCB 프로세스 상태: new, ready, running, waiting, halted 프로그램 카운터: next instruction의 주소 CPU레지스터들: accumulator, index register, stack pointers, 범용 registers, condition-code CPU스케줄 정보: priority, pointers to scheduling queues 메모리 관리 정보: base and limit registers, page tables, segment tables 계정 정보: time used, time limits, account numbers, job#, process# 입출력 상태 정보: I/O devices list allocated to the process, list of open files 스레드(Threads) a process = a single thread of execution (one task) 많은 현대 OS들이 multiple threads of control (multitasks at a time) 지원 2000 운영체제

Process Control Block (PCB) 2000 운영체제

프로세스 스케줄링(Process Scheduling) ~ 스케줄링 큐(Scheduling Queues) 작업 큐 (job queue) : memory 할당 기다리는 큐(disk에서) 준비 큐 (ready queue) : CPU에 할당 기다리는 큐 장치 큐 (device queue() : 입출력 기다리는 큐 큐잉 도표 (queueing diagram) : 그림 4.5 스케줄러(Schedulers) 장기 스케줄러(long-term scheduler, job scheduler) pool -> memory(degree of multiprogramming) Unix 같은 시분할 시스템에는 없음 단기 스케줄러(short-term scheduler, CPU scheduler) CPU 할당 : must be very fast 중기 스케줄러(medium-term scheduler) swapping degree of multiprogramming을 줄임 memory -> backing store 2000 운영체제

준비큐와 다양한 입출력 장치 큐 2000 운영체제

프로세스 스케줄링을 표현하는 큐잉 도표 2000 운영체제

큐잉 도표에 중기 스케줄링(Medium Term Scheduling) 추가 2000 운영체제

프로세스 스케줄링(Process Scheduling) 문맥 교환(Context Switch) CPU가 한 process에서 다른 process로 switch될 때 save the state of the old process : CPU와 메모리 상태(PCB정보) load the saved state for new process : CPU와 메모리 상태(PCB정보) pure overhead : performance bottleneck -> threads로 해결 context-switch time : 1-1000microsecond address space 보존 방법 : memory 관리기법에 좌우 2000 운영체제

한 프로세스에서 다른 프로세스로의 CPU Switch 2000 운영체제

프로세스에 대한 오퍼레이션(Operations on Processes) ~ 프로세스 생성(Process Creation) 프로세스 생성 시스템 호출 : fork, exec.. 부모 프로세스 자신 프로세스 : 사용 자원을 부모 프로세스의 자원(memory, files) 공유 새 프로세스 생성 후 부모는 계속 실행 모든 자식이 끝날 때 까지 기다림 : wait system call로 2000 운영체제

전형적인 UNIX System의 프로세스 트리 2000 운영체제

프로세스에 대한 오퍼레이션(Operations on Processes) ~ 새 프로세스의 2모델 (자식의 주소 공간 관점에서 본) 1) 자식은 부모의 것을 복제 : fork 2) 자식은 자신의 새 프로그램을 가짐 : fork+exec군 execl : 문자형 인수 포인터들 execv : 인수배열의 포인터 char *av[3]; av[0] = “ls”; av[1] = “-l”; av[2] = (char *)0; execv(“/bin/ls”, av); Unix의 예 : fork + exec 프로그램 참조 1) fork : 자식 process 생성, 모든 process는 PID(Process identifier)를 가짐 2) fork + exec : 호출하는 프로세스의 기억장소에 새 프로그램 load 2000 운영체제

Fork()로 새 프로세스를 생성하는 C program #include <stdio.h> void main(int argc, char *argv[]) { int pid; /* fork another process */ pid = fork(); if(pid < 0) { /* error occurred */ fprintf(stderr, “Fork Failed”); exit(-1); } else if (pid== 0) { /* child process) */ execl(“/bin/ls”, “ls”, NULL); } else { /* parent process */ wait(NULL); printf(“Child Complete”); exit(0); } 2000 운영체제

프로세스에 대한 오퍼레이션(Operations on Processes) 프로세스 종료(Process Termination) exit 시스템 종료 계산 결과는 부모에게 Return 메모리(물리적/가상적), 오픈한 화일, I/O버퍼를 OS에게 돌려줌 abort 시스템 호출 부모만 호출(그렇지 않으면 서로 죽이는 일 생김) 실행 종료 이유 자식이 할당된 자원을 초과 사용할 때 자식의 task가 더 이상 필요 없을 때 부모가 종료될 때 DEC VMS 또는 Unix 계단식(cascading) 종료 부모 종료 -> OS가 모든 자식 종료 (예) Unix exit system call로 프로세스 종료 wait system call : return값 = 종료하는 자식의 pid wait(&status) /* int status */ status :자식이 exit으로 종료될 때의 상태정보 정상종료 경우 : 하위 8bits는 0, 상위 8bits 는 exit status(자식 프로세스가 exit 명령으로 전달한 값), signal로 종료된 경우 : 하위 8bits는 signal 번호, 상위 8bits는 0 (상위 8 비트 추출) status >> 8; status &= 0xFF; 2000 운영체제

프로세스 협조(Cooperating Processes) ~ 프로세스 협조하는 이유 정보 공유 (information sharing) 계산 속도 증가 (computation speedup) : parallel computing으로 모듈화(modularity) 편이성(convenience) : parallel computing으로 프로세스 협조 예 : 생산자-소비자(producer-consumer)문제 compiler : assembly code 생산 assembler : assembly code 소비, object code 생산 loader : object code 소비 생산자와 소비자가 동시에 수행되려면 => buffer가 필요(동시 수행을 위해) => 생산자와 소비자의 동기화 필요(생산되지 않은 자료 소비하지 않게) 생산자-소비자 문제 종류 1. 무한 버퍼(unbounded-buffer) 생산자-소비자 문제 생산자는 항상 생산, 소비자는 소비할 자료를 기다릴 수도 2. 유한 버퍼(bounded-buffer) 생산자-소비자 문제 버퍼가 꽉 차 있으면 생산자가 대기, 버퍼가 비어 있으면 소비자가 대기 2000 운영체제

프로세스 협조(Cooperating Processes) 유한 버퍼 생산자-소비자 문제(bounded-buffer producer-consumer problem) -> 스레드(LWP)로 하면 효과적 Version 1: 공유 메모리를 이용한 해결책 Version 2: 메시지 전달을 이용한 해결책(4.5절) Version 3: 세마포어를 이용한 해결책(7.5절) Version 4: 세마포어와 스레드를 이용한 해결책(7.6절) Version 5: Java synchronization을 이용한 해결책(7.8절) 2000 운영체제

공유 메모리를 이용하는 생산자-소비자 문제 Import java.util.*; public class BoundedBuffer { public BoundedBuffer() { // buffer is initially empty count = 0; in = 0; out = 0; buffer = new Object[BUFFER_SIZE]; } // producer calls this method public void enter(Object item) { //Figure 4.10 The enter method // consumer calls this method public Object remove() { //Figure 4.11 The remove() method public static final int NAP_TIME = 5; private static final int BUFFER_SIZE = 5; private volatile int count; private int in; // points to the next free position private int out; //points to the next full posiiton private Object[] buffer; 2000 운영체제

생산자 enter() 메소드 public void enter(Object item) { while (count == BUFFER_SIZE) ; // do nothing // add an item to the buffer ++count; buffer[in] = item; in = (in + 1) % BUFFER_SIZE; if (count == BUFFER_SIZE) System.out.printIt(“Producer Entered “ + item + “ Buffer Full”); else System.out.printIt(“Producer Entered “ + item + “ Buffer size = “ + count); } 2000 운영체제

소비자 remove() 메소드 public Oject remove() { Object item; while (count == 0) ; // do nothing // remove an item to the buffer --count; item = buffer[out]; out = (out + 1) % BUFFER_SIZE; if (count == 0) System.out.printIt(“Consumer Consumed “ + item + “ BufferEmpty”); else System.out.printIt(“Consumer Consumer “ + item + “ Buffer size = “ + count); } 2000 운영체제

프로세스간 통신(Interprocess Communication) ~ 통신 방식 <- 한 시스템에서 둘 다 사용해도 됨 공유 메모리 방식(shared-memory) 응용 프로그램 작성자가 응용 레벨에서 통신기능 제공 (예)유한버퍼 생산자-소비자 문제 version 1 메시지 전달 방식(message-passing) IPC(interprocess-communication)기능 이용 : OS가 통신기능 제공 (예)유한 버퍼 생산자-소비자 문제 version 2 IPC 기본 구조(Basic Structure) IPC기능의 2연산 send (message) receive(message) 프로세스 P와 Q가 통신함 -> 통신선이 전재 링크 공유 메모리 bus network send/receive 연산 메시지 시스템을 구현하는 기법들 직접(direct) 또는 간접 통신 대칭(symmetric) 또는 비대칭(symmetric) 통신 자동(automatic) 또는 명시적(explicit) 버퍼링 복사(copy)에 의한 전송 또는 참고(reference)에 의한 전송 고정길이(fixed-sized) 또는 가변길이(variable-sized) 메시지 2000 운영체제

프로세스간 통신(Interprocess Communication) ~ 명칭 부착(Naming) 1) 직접통신(Direct Communication) 대칭적 통신 : 두 프로세스(sender/receiver)가 상대의 이름을 호출 Send(P, message) : 프로세스 P에게 메시지 보냄 Receive(Q, message) : 프로세스 Q로부터 메시지 받음 비대칭적 통신 : sender만 receiver 호출 Receive(id, message) : 임의의 프로세스로부터 메시지 받음 id = 통신이 일어난 순간 메시지를 보낸 프로세스의 이름으로 설정됨 직접통신의 단점 프로세스 이름 바뀌면 전부 고쳐야(limited modularity) 2) 간접통신(Indirect Communication) mailbox(ports) 통해 통신 send(A, message) : mailbox A에 메시지 보냄 receive(A, message) : mailbox로부터 메시지 받음 mailbox의 구현 프로세스가 mailbox소유 OS가 mailbox소유 2000 운영체제

프로세스간 통신(Interprocess Communication) ~ 동기화(Synchronization) Blocking send: 수신 프로세스가 메시지를 받을 때까지 멈춤 Nonblocking send: 메시지 보내고 다른 연산 계속 Blocking receive: 메시지가 있을 때까지 멈춤 Nonblocking receive: 올바른 메시지이거나 널 메시지이거나 상관하지 않고 받음 버퍼링(Buffering) 링크의 메시지 보유 용량 Zero capacity : rendez-vous(no buffering)…동기적 통신 Bounded capacity : 유한 길이 큐 이용…자동 버퍼링 Unbounded capacity : 무한 길이 큐 이용…자동 버퍼링 2000 운영체제

프로세스간 통신(Interprocess Communication) ~ 자동 버퍼링 경우 보통 비동기적 통신(asynchronous communication)이 일어남 보낸 메시지 도착 여부 모름 꼭 알아야 할 경우 : 명시적 통신 P : send(Q, message); receive(Q, message); Q : receive(P, message); send(P, “acknowledgment”); 특별한 경우 비동기적 통신: 메시지 보낸 프로세스는 절대로 지연되지 않음 보낸 메시지 미처 받기 전에 새 메시지 보내면 이전 메시지 유실될 수 있음 메시지 유실 방지 위해 복잡한 명시적 동기화 필요 동기적 통신: 메시지 보낸 프로세스는 받았다는 회신 받을 때까지 기다림 Thoth OS : reply(P, message) 가 메시지 보낸 프로세스와 받는 프로세스의 수행 재개 Sun RPC(Remote Procedure Call) 동기적 통신(synchronous communication) sender : subroutine call -> reply올 때까지 블록 됨 receiver : 계산 결과를 reply (http://marvel.inchon.ac.kr의 Information 참조) 2000 운영체제

프로세스간 통신(Interprocess Communication) ~ 예외 조건(Exception Conditions) centralized 또는 distributed system에서 고장 발생시 오류의 회복(예외 조건) 필요 프로세스 종료(Process Terminates) P는 종료된 Q를 기다림 -> P는 블록 됨 P 종료 Q 종료 사실을 P에 알림 P가 종료된 Q에 메시지 보냄 -> Q의 reply 기다려야 할 경우 블록 됨 메시지 유실(Lost Messages) OS가 탐지 및 처리 책임 sender가 탐지 및 처리 책임 OS가 탐지, sender가 처리 훼손된 메시지(Scrambled Messages) 통신 채널의 잡음(noise) 때문 -> 보통 OS가 재전송 오류검사코드(check sums, parity, CRC)으로 조사 2000 운영체제

Mailbox를 이용하는 생산자-소비자 문제 Import java.util.*; public class MessageQueue { public MessageQueue() { queue = new Vector(); } // This implements a nonblocking send public void send(Object item) { queue.addElement(item); // This implements a nonblocking receive public Object receive() { Object item; if (queue.size() == 0) return null; else { item = queue.firstElement(); queue.removeElementAt(0); return item; private Vector queue; 2000 운영체제

메시지 시스템의 생산자 프로세스와 소비자 프로세스 MessageQueue mailBox; while (true) { Date message = new Date(); mailBox.send(message); } 소비자 프로세스 Date message =(Date) mailBox.receive(); if (message !=null) // consume the message 2000 운영체제

프로세스간 통신(Interprocess Communication) ~ 실례 : Mach 분산시스템을 위한 OS 시스템 호출, task 간 정보전달을 메시지로 port(= mailbox) task 생성 => (kernel mailbox, notify mailbox) 생성 system calls msg_send msg_receive msg_rpc (remote procedure call) port_allocate : 새 mailbox 생성, buffer size = 8, FIFO order port_status : 주어진 mailbox의 메시지 수 반환 메시지 형태 고정길이 header 메시지 길이 두 mailbox 이름(그 중 하나는 sender의 mailbox; reply 위한 return address 포함) 가변길이 data portion: 정형화된(typed) 데이터 항목들의 리스트 2000 운영체제

프로세스간 통신(Interprocess Communication) ~ send 연산 수신 mailbox가 full이 아니면 메시지 복사 수신 mailbox가 full이면 4 가지 중 선택 mailbox에 빈 공간이 생길 때까지 대기 최대 n 밀리초 대기 기다리지 않고 즉시 복귀 메시지를 임시로 cache : 메시지 하나만 OS가 보관 (메시지가 실제로 목표 mailbox에 들어갔을 때 reply ; only one pending message) line printer driver 등 서버 태스크 경우 receive 연산 어떤 mailbox 또는 mailbox set로부터 메시지를 읽을지를 명시 지정된 mailbox로부터 또는 mailbox set 중 한 mailbox로부터 메시지 수신 읽을 메시지 없으면 최대 n 밀리초 대기하거나 대기하지 않음 메시지 시스템의 단점 double copy(sender -> mailbox, mailbox -> receiver) Mach는 virtural memory 기법으로 두번 복사 않음(송신 스레드와 수신 스레드를 같은 주소 공간으로 mapping 시킴) 2000 운영체제

프로세스간 통신(Interprocess Communication) ~ 실례 : Windows NT NT subsystem server와 메시지 전달 방식으로 통신 : 지역 프로시주어 호출 기능(LPC; Local Procedure Call facility) LPC: RPC(Remote Procedure Call) 기법과 유사 연결 포트(connection port)와 통신 포트(communication port) 사용 통신 작업 클라이언트가 연결 포트 객체에 대한 handle을 open 클라이언트가 연결 요청 서버는 두 개의 사적인(private) 통신 포트를 생성하고 클라이언트에게 두 포트 중 하나의 handle을 돌려줌 클라이언트와 서버는 해당 통신 포트의 handle을 이용하여 메시지를 보내거나, 응답호출(callback)을 하거나, 응답(reply)을 기다림 2000 운영체제

프로세스간 통신(Interprocess Communication) 세 가지 메시지 전달 기법 포트의 메시지 큐(~256 bytes)를 중간 저장소로 이용, 즉시 응답하기 어려울 때 알려주는 callback 기법 사용 가능 전송할 메시지가 크면 공유 메모리인 섹션 객체(section object)를 이용, 섹션 객체의 포인터와 크기 정보 전송하여 데이터 복사 피함, 즉시 응답하기 어려울 때 알려주는 callback 기법 사용 가능 quick LPC : 클라이언트가 연결 요청 후 quick LPC 지시, 서버는 클라이언트 전용 서버 스레드(dedicated server thread) 생성 연결 요청, 메시지 담을 64KB 섹션 객체, 동기화를 수행하는 한 쌍의 사건 객체(event pare object) 처리 장점 : 메시지 복사, 포트 객체 사용, 호출한 클라이언트 파악위한 overhead 제거 단점 : 다른 두 방법보다 많은 자원 사용 메시지 전달 overhead 감소위해 여러 메시지들을 한 메시지로 batch 하기도 함 2000 운영체제