提纲 1 Process Scheduling Process Scheduling Queues Schedulers Context Switch( 上下文切换 ) 2 Operation on processes Process Creation Process Termination 3 I

操作系统原理与设计第 3 章 Processes( 进程 )2 陈香兰中国科学技术大学计算机学院 March 19, 2014 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 1 / 50

提纲 1 Process Scheduling Process Scheduling Queues Schedulers Context Switch( 上下文切换 ) 2 Operation on processes Process Creation Process Termination 3 Interprocess Communication ( 进程间通信, IPC) Shared-Memory systems Message-Passing Systems 4 Example of IPC Systems POSIX Shared Memory Mach Windows XP 5 Communication in C/S Systems 6 小结和作业陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 2 / 50

Process Scheduling The objective of multiprogramming to have some process running at all times, to maximize CPU utilization The objective of time sharing to switch the CPU among processes so frequently that users can interact with each program whilt it is running What the system need? the process scheduler selects an available process to execute on the CPU 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 3 / 50

Outline 1 Process Scheduling Process Scheduling Queues Schedulers Context Switch( 上下文切换 ) 2 Operation on processes Process Creation Process Termination 3 Interprocess Communication ( 进程间通信, IPC) Shared-Memory systems Message-Passing Systems 4 Example of IPC Systems POSIX Shared Memory Mach Windows XP 5 Communication in C/S Systems 6 小结和作业陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 4 / 50

Process Scheduling Queues Processes migrate among the various queues Job queue set of all processes in the system Ready queue set of all processes residing in main memory, ready and waiting to execute Device queues set of processes waiting for an I/O device 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 5 / 50

Ready Queue And Various I/O Device Queues 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 6 / 50

Representation of Process Scheduling Queueing-diagram representation of process scheduling 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 7 / 50

Schedulers I Long-term ( 长期 ) scheduler (or job scheduler) selects which processes should be brought into the ready queue Short-term ( 短期 ) scheduler (or CPU scheduler) selects which process should be executed next and allocates CPU 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 9 / 50

The primary distinction between long-term & short-term schedulers I The pri1mary distinction between long-term & short-term schedulers lies in frequency of execution Short-term scheduler is invoked very frequently (UNIT: ms) must be fast Long-term scheduler is invoked very infrequently (UNIT: seconds, minutes) may be slow WHY? The long-term scheduler controls the degree of multiprogramming ( 多道程序度 ) the number of processes in memory stable? 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 10 / 50

The primary distinction between long-term & short-term schedulers II Processes can be described as either: I/O-bound (I/O 密集型 ) process spends more time doing I/O than computations, many short CPU bursts CPU-bound (CPU 密集型 ) process spends more time doing computations; few very long CPU bursts IMPORTANT for long-term scheduler: A good process mix of I/O-bound and CPU-bound processes 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 11 / 50

The long-term scheduler may be absent or minimal UNIX, MS Windows, The stability depends on physical limitation self-adjusting nature of human users 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 12 / 50

Addition of Medium Term ( 中期 ) Scheduling Medium-Term ( 中期 ) Scheduler can reduce the degree of multiprogramming the scheme is called swapping ( 交换 ): swap in VS swap out Addition of medium-term scheduling to the queueing diagram 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 13 / 50

Context Switch ( 上下文切换 ) I CONTEXT ( 上下文 ) when an interrupt occurs; When scheduling occurs the context is represented in the PCB of the process CPU registers process state memory-management info operation: state save VS state restore 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 15 / 50

Code reading 观察队列的组织上下文的内容和组织上下文切换 linux-011 linux-2626 uc/os-ii 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 16 / 50

Operation on processes The processes in most systems can execute concurrently, and they may be created and deleted dynamically The OS must provide a mechanism for process creation process termination 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 17 / 50

Process Creation I Parent process ( 父进程 ) create children processes ( 子进程 ), which, in turn create other processes, forming a tree of processes Most OSes identify processes according to a unique process identifier (pid) UNIX & Linux Command: ps -el typically an integer number 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 19 / 50

Process Creation II A tree of processes on a typical Solaris 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 20 / 50

Parent and children Resource sharing In general, a process will need certain resources (CPU time, memory, files, I/O devices) to accomplish its task When a process creates a subprocesses Execution Parent and children may share all resources, or Children may share subset of parent s resources, or Parent and child may share no resources Parent and children execute concurrently Parent waits until children terminate Address space Child duplicate of parent Child has a program loaded into it 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 21 / 50

UNIX examples: fork + exec fork system call creates new process exec system call used after a fork to replace the process memory space with a new program #include <unistdh> pid t fork(void); #include <unistdh> extern char **environ; int execl(const char *path, const char *arg, ); int execlp(const char *file, const char *arg, ); int execle(const char *path, const char *arg,, char * const envp[]); int execv(const char *path, char *const argv[]); int execvp(const char *file, char *const argv[]); 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 22 / 50

C Program Forking Separate Process int main(void) { pid t pid; /* fork another process */ pid = fork(); if (pid < 0) { /* error occurred */ fprintf(stderr, Fork Failed ); exit(-1); } else if (pid == 0) { /* child process */ execlp( /bin/ls, ls, NULL); } else { /* parent process */ /* parent will wait for the child to complete */ wait (NULL); printf ( Child Complete ); exit(0); } } 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 23 / 50

Process Termination 1 Process executes last statement and asks the OS to delete it by using the exit() system call Output data (a status value, typically an integer) from child to parent (via wait()) Process resources are deallocated by the OS 2 Termination can be caused by another process Example: TerminateProcess() in Win32 3 Users could kill some jobs 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 25 / 50

Process Termination Parent may terminate execution of children processes (abort) Child has exceeded allocated resources Task assigned to child is no longer required If parent is exiting Some operating system do not allow child to continue if its parent terminates All children terminated - cascading termination UNIX Example: exit(), wait() If the parent terminates, all its children have assigned as their new parent the init process 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 25 / 50

Interprocess Communication ( 进程间通信,IPC) I Processes executing concurrently in the OS may be either independent processes or cooperating processes Independent process cannot affect or be affected by the execution of other processes Cooperating process can affect or be affected by the execution of other processes Advantages of allowing process cooperation Information sharing: a shared file VS several users Computation speed-up: 1 task VS several subtasks in parallel with multiple processing elements (such as CPUs or I/O channels) Modularity Convenience: 1 user VS several tasks Cooperating processes require an IPC mechanism that will allow them to exchange data and information 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 26 / 50

Interprocess Communication ( 进程间通信,IPC) II Two fundamental models of IPC Message-passing ( 消息传递 ) model useful for exchange smaller amount of data, because no conflicts need be avoided easier to implement exchange information via system calls such as send(), receive() Shared-memory ( 共享内存 ) model faster at memory speed via memory accesses system calls only used to establish shared memory regions 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 27 / 50

Shared-Memory systems Normally, the OS tries to prevent one process from accessing another process s memory Shared memory requires that two or more processes agree to remove this restriction They can exchange information by R/W data in the shared areas The form of data and the location are determined by these processes and not under the OS s control The processes are responsible for ensuring that they are not writing to the same location simultaneously 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 29 / 50

Producer-Consumer Problem ( 生产者 - 消费者问题 ) Producer-Consumer Problem ( 生产者 - 消费者问题,PC 问题 ): Paradigm for cooperating processes producer ( 生产者 ) process produces information that is consumed by a consumer ( 消费者 ) process Example: complier Shared-Memory solution assembly code assembler a buffer of items shared by producer and consumer object models loader Two types of buffers unbounded-buffer places no practical limit on the size of the buffer bounded-buffer assumes that there is a fixed buffer size 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 30 / 50

Bounded-Buffer Shared-Memory Solution Shared variables reside in a shared region #define BUFFER SIZE 10 typedef struct { } item; item buffer[buffer SIZE]; int in = 0; // index of the next empty buffer int out = 0; // index of the next full buffer all empty? all full? Insert() Method while (true) { /* Produce an item */ while (((in + 1) % BUFFER SIZE) == out) ; /* do nothing no free buffers */ buffer[in] = item; in = (in + 1) % BUFFER SIZE; } Remove() Method while (true) { while (in == out) ; // do nothing nothing to consume } // remove an item from the buffer item = buffer[out]; out = (out + 1) % BUFFER SIZE; return item; Solution is correct, but can only use BUFFER SIZE-1 elements 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 31 / 50

Message-Passing Systems Message passing ( 消息传递 ) provides a mechanism for processes to communicate and to synchronize their actions without sharing the same address space processes communicate with each other without resorting to shared variables particularly useful in a distributed environmet IPC facility provides at least two operations: send(message) message size fixed or variable receive(message) If process P and Q wish to communicate, they need to: establish a communication link between them exchange messages via send/receive Implementation of communication link physical (eg, shared memory, hardware bus) logical (eg, logical properties) 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 33 / 50

Implementation Questions How are links established? Can a link be associated with more than two processes? How many links can there be between every pair of communicating processes? What is the capacity of a link? Is the size of a message that the link can accommodate fixed or variable? Is a link unidirectional or bi-directional? 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 34 / 50

Direct Communication Processes must name each other explicitly: send(p, message) - send a message to process P receive(q, message) - receive a message from process Q Properties of communication link in this scheme Links are established automatically A link is associated with exactly one pair of communicating processes Between each pair there exists exactly one link The link may be unidirectional, but is usually bi-directional Symmetry VS asymmetry send(p, message) receive(id, message) - receive a message from any process 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 35 / 50

Indirect Communication Messages are directed and received from mailboxes (also referred to as ports) Each mailbox has a unique id (such as POSIX message queues) 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 Properties of communication link in this scheme Link established only if processes share a common mailbox A link may be associated with more than two processes Each pair of processes may share several communication links Link may be unidirectional or bi-directional 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 36 / 50

Indirect Communication Mailbox sharing problem P1, P2, and P3 share mailbox A P1, sends; P2 and P3 receive Who gets the message? Solutions to choose Allow a link to be associated with at most two processes Allow only one process at a time to execute a receive operation Allow the system to select arbitrarily the receiver Sender is notified who the receiver was 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 36 / 50

Indirect Communication Who is the owner of a mailbox? a process the OS Operations only owner can receive messages through its mailbox, others can only send messages to the mailbox when the process terminates, its mailbox disappears the mailbox is independent and is not attached to any particular process create a new mailbox send/receive messages through mailbox destroy a mailbox 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 36 / 50

Synchronization Message passing may be either blocking or non-blocking Blocking is considered synchronous Blocking send has the sender block until the message is received Blocking receive has the receiver block until a message is available Non-blocking is considered asynchronous Non-blocking send has the sender send the message and continue Non-blocking receive has the receiver receive a valid message or null Difference combinations are possible If both are blocking rendezvous( 集合点 ) The solution to PC problem via message passing is trivial when we use blocking send()/receive 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 37 / 50

Buffering Queue of messages attached to the link; implemented in one of three ways 1 Zero capacity 0 messages Sender must wait for receiver (rendezvous) 2 Bounded capacity finite length of n messages Sender must wait if link full 3 Unbounded capacity infinite length Sender never waits 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 38 / 50

POSIX Shared Memory POSIX API for shared memory #include<sys/ipch> #include<sys/shmh> int shmget(key t key, size t size, int shmflg); int shmctl(int shmid, int cmd, struct shmid ds *buf); #include<sys/typesh> #include<sys/shmh> void* shmat(int shmid, const void* shmaddr, int shmflg); int shmdt(const void* shmaddr); 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 40 / 50

POSIX Shared Memory C program illustrating POSIX shared-memory API #include <stdioh> #include <sys/shmh> #include <sys/stath> int main(){ int segment id; char* shared memory; const int size = 4096; segment id = shmget(ipc PRIVATE, size, S IRUSR S IWUSR); shared memory = (char*) shmat(segment id, NULL, 0); sprintf(shared memory, Hi there! ); printf( %s\n,shared memory); } shmdt(shared memory); shmctl(segment id, IPC RMID, NULL); return 0; 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 40 / 50

POSIX Shared Memory Two program using shared memory: program1 #include <stdioh> #include <stdlibh> #include <sys/typesh> #include <sys/ipch> #include <sys/shmh> #include <sys/stath> int main(void) { key t key; int shm id; const int shm size=4096; char * shm addr; key=ftok(, m ); shm id=shmget(key,shm size,ipc CREAT IPC EXCL S IRUSR S IWUSR); shm addr=(char*)shmat(shm id,0,0); } sprintf(shm addr, hello, this is 11111111\n ); printf( 111111: ); printf(shm addr); sleep(10); printf( 111111: ); printf(shm addr); shmdt(shm addr); shmctl(shm id,ipc RMID,0); return 0; 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 40 / 50

POSIX Shared Memory Two program using shared memory: program2 #include <stdioh> #include <stdlibh> #include <sys/typesh> #include <sys/ipch> #include <sys/shmh> #include <sys/stath> int main(void) { key t key; int shm id; const int shm size=4096; char * shm addr; key=ftok(, m ); shm id=shmget(key,shm size,s IRUSR S IWUSR); shm addr=(char*)shmat(shm id,0,0); } printf( 22222222: ); printf(shm addr); sprintf(shm addr, this is 22222222\n ); shmdt(shm addr); return 0; 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 40 / 50

LPC in Windows XP Subsystems application programs can be considered clients of the Windows XP subsystems server application programs communicate via a message-passing mechanism: local procedure-call (LPC) facility Port object: two types connection ports: named objects, to set up communication channels communication ports for small message, use the port s message queue for a larger message, use a section object, which sets up a region of shared memory this can avoids data copying 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 43 / 50

LPC in Windows XP Local procedure calls in Windows XP 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 43 / 50

Client-Server Communication Sockets ( 套接字 ) Remote Procedure Calls ( 远程过程调用,RPC) Remote Method Invocation ( 远程方法调用,RMI) (Java) 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 44 / 50

Sockets ( 套接字 ) A socket is defined as an endpoint for communication Concatenation of IP address and port The socket 16125198:1625 refers to port 1625 on host 16125198 Communication consists between a pair of sockets 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 45 / 50

Remote Procedure Calls( 远程过程调用, RPC) Remote procedure call (RPC) abstracts procedure calls between processes on networked systems Stubs client-side proxy for the actual procedure on the server The client-side stub locates the server and marshalls the parameters The server-side stub receives this message, unpacks the marshalled parameters, and peforms the procedure on the server 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 46 / 50

Remote Procedure Calls( 远程过程调用, RPC) Execution of a remote precedure call (RPC) 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 46 / 50

Remote Method Invocation( 远程方法调用, RMI) Remote Method Invocation (RMI) is a Java mechanism similar to RPCs RMI allows a Java program on one machine to invoke a method on a remote object 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 47 / 50

Remote Method Invocation( 远程方法调用, RMI) Marshalling Parameters 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 47 / 50

小结 1 Process Scheduling Process Scheduling Queues Schedulers Context Switch( 上下文切换 ) 2 Operation on processes Process Creation Process Termination 3 Interprocess Communication ( 进程间通信, IPC) Shared-Memory systems Message-Passing Systems 4 Example of IPC Systems POSIX Shared Memory Mach Windows XP 5 Communication in C/S Systems 6 小结和作业陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 48 / 50

阅读 Read related code in Linux or uc/os-ii Subsubsection An Example: Mach of subsection Examples of IPC Systems Subsubsection An Example: Windows XP of subsection Examples of IPC Systems Subsection Communication in Client-Server Systems 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 49 / 50

谢谢! 陈香兰 ( 中国科学技术大学计算机学院 ) 操作系统原理与设计 March 19, 2014 50 / 50