Chapter 3. Process Concept Introduction to Operating Systems CSW3020 Prof. Young Pyo JUN CSW3020/Introduction to Operating Systems 1
What is a Process? 실행중인프로그램 프로그램은저장장치에, 프로세스는메인메모리에존재 시스템콜을통해자원을요구하는개체 멀티프로세싱혹은멀티태스킹 시분할시스템의경우여러개의프로세스를동시에수행 하나의프로그램이수행중여러개의프로세스를만드는경우도있음 사용자프로세스와시스템프로세스로나눌수있겠으나자원경쟁측면에서는동일 사용자프로세스 응용프로그램이실행되는것 시스템프로세스 운영체제가필요에의해생성 상태변화가있는동적인객체 CSW3020/Introduction to Operating Systems 2
프로그램과프로세스 HDD CPU Free-memory ls 프로세스 shell kernel ls 프로그램 CSW3020/Introduction to Operating Systems 3
프로세스구성 (createprocess()).. int cnt = 0; int main(void) { int i, j, sum; char *heapdata; Contains temporary data such as function parameters, return addresses, and local variables } i = 10; j = 20; sum = add(i, j, ++cnt); printf( Sum is %d\n, sum);.. heapdata = (char *) malloc(sum);.. Contains memory that is dynamically allocated during process runtime (e.g., malloc()) Contains gloval variables int add(int k, int l, int m) { int sum; } sum = k + l + m; return sum; CSW3020/Introduction to Operating Systems 4
프로세스실행 프로세스시작 Int main 호출 : 스택에 main 함수의지역변수 push I = 10; 부터명령실행 (I, j 등변수값변경 ) sum = add(i, j, ++cnt); add() {.. return sum;} heapdata = (char *)malloc(sum) => heap data 할당.. int cnt = 0; int main(void) { int i, j, sum; char *heapdata; i = 10; j = 20; sum = add(i, j, ++cnt); } printf( Sum is %d\n, sum); heapdata = (char *) malloc(sum); int add(int k, int l, int m) { int sum; sum = k + l + m; return sum; } int main int I, j, sum char *heapdata int add(..) int sum malloc(sum) 전역변수, 함수정의 Int cnt, int main, int add) 프로그램코드 Main(sum=add, printf, heapdata=..) Add(sum=.., return..) SP SP SP HP HP CSW3020/Introduction to Operating Systems 5
프로세스상태 프로세스생명주기 new: 프로세스가처음생성 ready: CPU에의해할당되기를기다리는상태 running: 명령어들이실행되고있는상태 waiting: 프로세스가어떤사건 ( 입출력완료등 ) 을기다리고있는상태 terminated: 프로세스의실행이종료 CSW3020/Introduction to Operating Systems 6
Process Control Block (PCB) 프로세스관리를위한정보의모임 Process state Process ID: 프로세스의고유번호 Program counter: 현제실행위치 CPU registers: 프로세스실행상태값 CPU scheduling information: 우선순위등 Memory-management information: 프로세스가사용하는메모리정보 Accounting information: 사용시간, 계정등 I/O status information: I/O 관련정보 CSW3020/Introduction to Operating Systems 7
Concept of Process Scheduling 다중프로그래밍 : CPU 활용률을최대화하여여러프로세스가동시실행 시분할처리 : CPU가번갈아가면서프로세스를실행 단일프로세싱시스템 : 하나의프로세스를전적으로실행 여러프로세스가있는경우나머지는경쟁적으로다음번에 CPU를사용하기위해스케쥴링되어야함 이와같이여러프로세스를하나의 CPU로처리하기위해줄을세우고순서를정해처리하는데이것이프로세스스케쥴링 CSW3020/Introduction to Operating Systems 8
Process Scheduling Queues Job queue 시스템안의모든프로세스로구성 Ready queue 주메모리에존재하며준비완료상태에서실행되기를기자리는프로세스큐 Device queues (I/O queue) 입출력등을필요로하는프로세스가많이있기때문에장치큐에넣어순서대로실행 프로세스는다양한큐를옮겨다니며순서를기다림 CSW3020/Introduction to Operating Systems 9
Ready Queue and I/O Device Queues CSW3020/Introduction to Operating Systems 10
Process Scheduling 과정 CSW3020/Introduction to Operating Systems 11
Schedulers 큐에있는프로세스를선택하는것을스케쥴링이라고함 Long-term scheduler (or job scheduler, 장기스케쥴러 ) 보통일괄처리시스템에서제출된프로세스를실행가능한메모리로적재. 거끔발생. UNIX, Windows 등시분할시스템에는보통장기스케쥴러가없음 Short-term scheduler (or CPU scheduler, 단기스케쥴러 ) 보통다중프로그래밍, 시분할시스템에서레디큐에있는프로세스를 CPU에할당. 자주발생. 프로세스의유형 : I/O-bound process I/O 작업이많은프로세스. 한번에사용하는 CPU 사용시간이매우짧다 CPU-bound process I/O보다 CPU 계산이많은프로세스. 한번에사용하는 CPU 사용시간이길다 CSW3020/Introduction to Operating Systems 12
Medium-Term Scheduler Swapping: 메모리에있는프로세스를 HDD 로내리고차후에다시메모리로불러와실행 다중프로그래밍의정도를완화 가용메모리확보등 CSW3020/Introduction to Operating Systems 13
Context Switch ( 문맥교환 ) 다중처리, 시분할처리에서수행중인프로세스를잠시멈추고새로운프로세스를로드하여처리하는과정 처리상태를메모리에기록 (state save) 하고가져 (state restore) 와야함 State restore 문맥내용은 PCB 에있음 ( 프로세스실행 당시위치, 임시레지스터값, 상태등 ) 문맥교환시간은시스템의오버헤드. 이 시간낭비보다다중프로그래밍효과가 커야다중프로그래밍의가치가있는것 State save CSW3020/Introduction to Operating Systems 14
Example of Context Switch CSW3020/Introduction to Operating Systems 15
프로세스생성 Parent Process가 Child Process 생성, Tree 구조 프로세스식별자로구분됨. process identifier (pid). 부모자식간자원공유방식 Parent and children share all resources. Children share subset of parent s resources. Parent and child share no resources. 실행방식 Parent and children execute concurrently. Parent waits until children terminate. 주소공간공유방식 Child는 Parent와동일한복사본으로시작 (fork()). Child는새로운프로세스로재실행하여자신을덮어씀 (exec()). CSW3020/Introduction to Operating Systems 16
Processes Tree on a Linux System fork() execl() init pid = 1 login pid = 8415 kthreadd pid = 2 sshd pid = 3028 bash pid = 8416 khelper pid = 6 pdflush pid = 200 sshd pid = 3610 ps pid = 9298 emacs pid = 9204 tcsch pid = 4005 CSW3020/Introduction to Operating Systems 17
Process Creation in UNIX UNIX examples fork system call creates a new process. The new process consists of a copy of the address space of the original process. Both processes continue execution at the instruction after fork() with one difference: Returned pid values are different (i.e., parent (pid > 0), child (pid == 0)). exec system call used after a fork to replace the process memory space with a new program. CSW3020/Introduction to Operating Systems 18
Example of a Process Creation (UNIX) #include <stdio.h> main(int argc, char *argv[]) { int pid; pid = fork(); /* create a new process */ } if ( pid < 0 ) { /* error occurred */ fprintf(stderr, Fork Failed ); exit(-1); } else if ( pid == 0 ) { /* child process */ execlp( /bin/ls, ls, NULL); /* replace the process memory space */ } else { /* parent process */ /* parent will wait for the child to complete */ wait(null); printf( Child Complete ); exit(0); } CSW3020/Introduction to Operating Systems 19
Example of a Process Creation (UNIX) #include <stdio.h> main(int argc, char *argv[]) { int pid; pid = fork(); if ( pid < 0 ) { // error fprintf(stderr, Fork Failed ); exit(-1); } else if ( pid == 0 ) { // child execlp( /bin/ls, ls, NULL); } else { // parent wait(null); printf( Child Complete ); exit(0); } } parent process int main() int pid = 1002020 프로그램코드 main(int argc, char *argv[]) pid = fork(); child process int main() int pid = 0 프로그램코드 main(int argc, char *argv[]) pid = fork(); wait() printf("...") exit() /bin/ls CSW3020/Introduction to Operating Systems 20
simple shell example (UNIX) #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <strings.h>int main(int argc, char *argv[]) { int pid; while(1) { char cmd[99]; printf("# "); scanf("%s", cmd); if(strcmp(cmd, "exit") == 0) break; pid = fork(); /* create a new process */ if ( pid < 0 ) { /* error occurred */ printf("fork Failed"); exit(-1); } else if ( pid == 0 ) { /* child process */ execlp(cmd, cmd, NULL); } else { /* parent process */ /* parent will wait for the child to complete */ wait(null); } } } CSW3020/Introduction to Operating Systems 21
프로세스종료 exit(status) 시스템호출을사용하여운영체제에게자신의삭제를요청. Parent can get a status value from child (via wait(&status)). Process resources are de-allocated by operating system. exit() 호출이없더라도 main() 프로그램이끝나면자동으로 exit() 호출됨 parent 프로세스가 kill(pid) 시스템호출을사용하여 child 프로세스를강제종료. Child has exceeded allocated resources. Task assigned to child is no longer required. Parent is exiting. Operating system does not allow child to continue if its parent terminates. Cascading termination (some systems do not allow a child to exist if its parent has terminated -> all its children must also be terminated). CSW3020/Introduction to Operating Systems 22
Zombie vs. Orphan Processes A zombie process or defunct process is a process that has completed execution but still has an entry in the process table. A process that has terminated, but its parent has not yet collected the status via wait -> usually because of bugs or coding errors. All processes can normally exist as zombies only briefly. When the parent calls wait, the child terminates normally. Parent is executing, while the child is dead. When a parent didn t invoke wait and instead terminated, its children processes are orphan processes (i.e., still executing). The init process is assigned to the new parent of those processes. The init process periodically invokes wait to collect the exit status of any orphan processes. Parent (original) is dead, while the child is executing. CSW3020/Introduction to Operating Systems 23
Inter-Process Communication (IPC) Mechanism for processes to communicate and to synchronize their actions. 메시지전달 : 커널내메모리를통하여공유 ( 시스템호출사용 ) 공유메모리 : 사용자영역에공유메모리생성 ( 시스템호출없이빠르게사용 ) 메시지전달 (message passing) 공유메모리 (shared memory) CSW3020/Introduction to Operating Systems 24
공유메모리시스템 두프로세스합의하에 OS 개입없이메모리를공유 생산자 - 소비자구조로동기화필요 버퍼의유형 무한버퍼 (unbounded buffer): 크기가무한하여생산자는계속버퍼를채울수있음 유한버퍼 (bounded buffer): 크기가고정되어있어공간이차면생산자는기다려야함 생산자와소비자가공유메모리에동시접근할경우? 프로세스동기화필요 (5 장 ) CSW3020/Introduction to Operating Systems 25
Message Passing System Message passing system processes communicate with each other without sharing the same address space. IPC (message passing) facility provides two operations: send(message) message size fixed or variable receive(message) If P and Q wish to communicate, they need to: establish a communication link (logical link) between them exchange messages via send/receive Issues designing message passing system Naming direct or indirect communication Synchronization blocking or nonblocking Buffering CSW3020/Introduction to Operating Systems 26
Naming Direct Communication: Processes must name each other explicitly: send (Q, message) send a message to process Q receive(p, message) receive a message from process P A link established automatically between every pair of processes that want to communicate Processes only need to know each other s identity link is associated with exactly two processes link is usually bidirectional but can be unidirectional Process A Process B while (TRUE) { while (TRUE) { produce an item receive ( A, item ) send ( B, item ) consume item } } CSW3020/Introduction to Operating Systems 27
Naming Asymmetric addressing: only the sender names the recipient recipient not required to name the sender - need not know the sender send ( P, message ) : send message to process P receive ( id, message ) : receive from any process, id set to sender Disadvantage of direct communications : limited modularity - changing the name of a process means changing every sender and receiver process to match need to know process names 하드코딩방식의불편함 CSW3020/Introduction to Operating Systems 28
Naming Indirect Communication: Messages are directed and received from mailboxes (also referred to as ports). Each mailbox has a unique id. Processes can communicate only if they share a mailbox. Primitives are defined as: send(a, message) send a message to mailbox A receive(a, message) receive a message from mailbox A A communication link is only established between a pair of processes if they have a shared mailbox. A pair of processes can communicate via several different mailboxes if desired. A link can be either unidirectional or bidirectional. A link may be associated with more than two processes. allows one-to-many, many-to-one, many-to-many communications CSW3020/Introduction to Operating Systems 29
동기화 (Synchronization) Message passing may be either blocking or non-blocking. Blocking is considered synchronous. Non-blocking is considered asynchronous. Send and receive primitives may be either blocking or nonblocking. Blocking send: The sending process is blocked until the message is received by the receiving process or by the mailbox. Non-blocking send: The sending process sends the message and resumes operation. Blocking receive: The receiver blocks until a message is available. Non-blocking receive: The receiver retrieves either a valid message or a null. CSW3020/Introduction to Operating Systems 30
Buffering Queue of messages attached to the link; implemented in one of three ways. Zero capacity 0 messages Sender must wait for receiver (rendezvous). Bounded capacity finite length of n messages Sender must wait if link full. Unbounded capacity infinite length Sender never waits. CSW3020/Introduction to Operating Systems 31
IPC 사례 (UNIX) Inter-Process Communication : Mechanism for various processes to communicate among them. Different processes run on different address space. OS needs to provide mechanisms to communicate -> IPC. Types of IPCs in UNIX Shared memory in POSIX: shm_open, shm_unlink Traditional UNIX IPCs : signal, pipe, socket System V IPCs : message queue, semaphore, shared memory CSW3020/Introduction to Operating Systems 32
POSIX Shared Memory (Producer) CSW3020/Introduction to Operating Systems 33
POSIX Shared Memory (Consumer) CSW3020/Introduction to Operating Systems 34
Pipe Unidirectional byte streams which connect one process into the other process. The data written at one end of the channel is read at the other end. From a logical point of view, a pipe can be compared to a FIFO queue of characters. write read Process A Process B Communication Pipe No structured communication : it is not possible to know the size, sender/receiver of data contained in the pipe. Access to pipes is achieved by reading/writing from/to file descriptors. CSW3020/Introduction to Operating Systems 35
Pipe Used by Commands One current usage of the pipe mechanism is performed by means of the command line interpreter when commands are linked: (e.g., > ps -aux grep root tail) [ /home/parksy ] ps -aux grep root tail root 9232 0.0 0.1 1392 664? S Aug26 0:00 in.identd -e -o root 9233 0.0 0.1 1392 664? S Aug26 0:00 in.identd -e -o.. root 16763 0.2 0.1 1704 876? S 10:32 0:00 in.telnetd root 16764 0.1 0.2 2320 1232 pts/0 S 10:32 0:00 login -- parksy parksy 16800 0.0 0.1 2236 528 pts/0 S 10:33 0:00 grep root ps -aux grep root tail out in out in CSW3020/Introduction to Operating Systems 36
Anonymous Pipe Created by a process and the transmission for associated descriptors is achieved only by inheritance by its descendants. (i.e., by creating a child process using fork() system call) Restrictive in that it only allows communication between processes with a common ancestor which is a creator of a pipe. Creation of an anonymous pipe : int pipe(int filesdes[2]); -> filesdes[0] : read descriptor, filesdes[1] : write descriptor. write(filesdes[1]) read(filesdes[0]) Writing Reading Anonymous Pipe CSW3020/Introduction to Operating Systems 37
Use of Pipe - Example #include <stdio.h> #include <unistd.h> int main(void) { inr n, fd[2], pid; char line[100]; Parent Child fork fd[0] fd[1] fd[0] fd[1] PIPE Kernel } if (pipe(fd) < 0) exit(-1); if ((pid = fork()) < 0) exit(-1); else if (pid > 0) { /*parent */ } close(fd[0]); write(fd[1], Hello World\n, 12); wait(null); else { /* child */ } close(fd[1]); n = read(fd[0], line, MAXLINE); write(stdout_fileno, line, n); CSW3020/Introduction to Operating Systems 38
Named Pipe (FIFO) Remove the constraint of anonymous pipe (i.e., no name, only used between processes that have a parent process in common) because they are entries in the file system. Has a name and handled exactly like files with respect to file operations (e.g., open, close, read, write). Created by mkfifo or mknod commands. Can be created by C functions : mkfifo(). int mkfifo(const char *path, mode_t mode); Reading from / writing to a named pipe can be achieved by using standard read() and write() system calls. CSW3020/Introduction to Operating Systems 39
Named Pipe (Producer and Consumer) writer.c reader.c #include <fcntl.h> #include <sys/stat.h> #include <sys/types.h> #include <unistd.h> int main() { int fd; char * myfifo = "/tmp/myfifo"; } /* create the FIFO (named pipe) */ mkfifo(myfifo, 0666); /* write "Hi" to the FIFO */ fd = open(myfifo, O_WRONLY); write(fd, "Hi", sizeof("hi")); close(fd); /* remove the FIFO */ unlink(myfifo); return 0; #include <fcntl.h> #include <stdio.h> #include <sys/stat.h> #include <unistd.h> #define MAX_BUF 1024 int main() { int fd; char * myfifo = "/tmp/myfifo"; char buf[max_buf]; } /* open, read, and display the message from the FIFO */ fd = open(myfifo, O_RDONLY); read(fd, buf, MAX_BUF); printf("received: %s\n", buf); close(fd); return 0; CSW3020/Introduction to Operating Systems 40
Communication in Client-Server Systems Sockets Remote Procedure Calls CSW3020/Introduction to Operating Systems 41
Sockets A socket is defined as an endpoint for communication. Concatenation of IP address and port number The socket 161.25.19.8:1625 refers to port 1625 on host 161.25.19.8 Communication consists between a pair of sockets. ftp user http user telnet Port # (21) Port # (5000) Port # (80) Port # (7000) Port # (23) TCP(UDP)/IP (Kernel) TCP(UDP)/IP (Kernel) IP Address (161.25.19.8) IP Address (161.25.19.1) CSW3020/Introduction to Operating Systems 42
Socket Communication CSW3020/Introduction to Operating Systems 43
End of Chapter 3 CSW3020/Introduction to Operating Systems 44