Class Note for EECS 678 with Professor Kulkarni at KU 3
Class Note for EECS 678 with Professor Kulkarni at KU 3
Popular in Course
Popular in Department
This 50 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 14 views.
Reviews for Class Note for EECS 678 with Professor Kulkarni at KU 3
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Chapter 3 Processes I What is a process I What is process scheduling I What are the common operations on processes I How to conduct processlevel communication I How to conduct clientserver communication EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 Process Concept l Process 0 is a program in execution o is an instance of a computer program being sequentially executed 0 process execution must progress in sequential fashion 0 process is also called ajob I Program Vs process 0 program is a passive entity process is an active entity 0 program only contains text process is associated with code data PC heap stack registers and other information 0 program becomes a process when an executable file is loaded into memory 0 same program executed multiple times will correspond to different process each time EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 Process in Memory max stack heap data text EECS 678 Fundamentals of Operating Systems 7 Spring 2009 Process State I During execution the process may be in one of the following states 0 new process is being created 0 running instructions are being executed o waiting waiting for some event to occur 0 ready waiting to be assigned a processor 0 terminated process has finished execution l Each processor can only run one process at a instant EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 9 Diagram of Process State admitted interrupt scheduler dispatch 10 or event completion 0 or event wait EECS 678 Fundamentals of Operating Systems 7 Spring 2009 g Process Control Block PCB l PCB is representation of a process in an operating system 0 maintains processspecific information o necessary for scheduling l Information associated with each process 0 process state program counter CPU registers CPU scheduling information memorymanagement information accounting information O status information EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 a Process Control Block PCB 2 process state process number program counter registers memory limits list of open files EECS 678 Fundamentals of Operating Systems 7 Spring 2009 CPU Switch From Process to Process process PO operating system process P1 interrupt or system call executing save state into PCBo 39 idle reload state from PCB1 t idle interrupt or system call executing save state into PCB1 idle reload state from PCBD executing EECS 678 Fundamentals of Operating Systems 7 Spring 2009 x5 Process Scheduling l Process scheduling selects the process to run on a CPU 0 maximizes CPU utilization in a multiprogramming OS 0 provides illusion of each process owning the system in a timeshared OS I Terminology used in OS schedulers 0 job queue set of all processes in the system 0 ready queue set of all processes residing in main memory ready and waiting to execute 0 device queues set of processes waiting for an O device I Processes migrate among the various queues EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 5 Ready Queue And Various IIO Device Queues queue header PCB7 PCB2 ready head 39 39j queue tail registers registers I I mag head I tape quot unitO taquot 39 39 tmag head a e unif1 taquot PCB3 PCB14 PCBE disk unit 0 P035 terminal head 39 39 39 unit 0 rail EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 10 9 Representation of Process Scheduling gt ready queue gt IO O queue IO request lt time slice expired child fork a child interrupt wait for an occurs interrupt EECS 678 Fundamentals of Operating Systems 7 SpIing 2009 Schedulers l Systems with a possibility of huge deluge ofjob requests may use multiple schedulers l Longterm scheduler orjob scheduler selects processes to be brought into the ready queue controls the degree of multiprogramming controls the mix of active CPUbound and lObound processes invoked infrequently can afford more time to make selection decision I Shortterm scheduler or CPU scheduler selects the process to be executed next and allocates CPU invoked frequently necessary to limit scheduling overhead EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 12 Context Switch l A context switch is the process of storing and restoring the state context of the CPU such that multiple processes can share a single CPU resource 0 for timeshared or multiprogramming environments 0 context of a process represented in the PCB O context switch involves a state save of the current process and a state restore of the process being resumed next 0 switch from user to kernel mode or viceversa is a mode switch I Contextswitch time is overhead 0 the system does no useful work while switching o overhead depends on hardware support gt Sun UltraSPARC provides multiple banks of registers gt Intel x86 processors also provide some support EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 13 x9 Process Creation l Any process can create other processes during its execution 0 operating systems have a primordial process 0 creating process called parent process 0 new process called child process 0 processes identified and managed via a process identifier pid l Resource sharing options 0 parent and children share all resources 0 children share subset of parent s resources 0 parent and child share no resources I Execution options 0 parent and children execute concurrently 0 parent waits until children terminate EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 14 9 Process Creation Cont l Address space options 0 child duplicate of parent 0 child has a program loaded into it I UNIX examples 0 fork system call creates new process 0 exec system call used after a fork to replace the process memory space with a new program EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 15 Process Creation Example on Unix int main pidt pid fork another process pid fork if pid lt O error occurred fprintfstderr quotFork Failedquot exit l else if pid child process execlpquotbinlsquot quotlsquot NULL else parent process parent will wait for the child to complete wait NULL printf quotChild Completequot exit0 EECS 678 Fundamentals of Operating Systems 7 Spn39ng 2009 16 9 Process Creation l Parent waiting for child process to finish EECS 678 Fundammtals of Operating Systems 7 Spring 2009 I GSleeS 17 Process Termination l Process terminates after executing last statement 0 can explicitly invoke the exit system call to terminate 0 OS implicitly calls exit 0 child can pass return status to parent via wait 0 process resources are deallocated by operating system I Parent may terminate execution of children processes abort 0 child has exceeded allocated resources 0 task assigned to child is no longer required 0 if parent is exiting gt some operating system do not allow child to continue if its parent terminates gt all children terminated cascading termination EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 18 x9 Interprocess Communication l Communication within the same system I Processes may need to cooperate for several reasons 0 information sharing 0 computation speedup o modularity o convenience l Cooperating process can affect or be affected by other processes 0 typically by sharing data I Cooperating processes need interprocess communication IPC EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 19 x9 ProducerConsumer Problem I Common paradigm for cooperating processes 0 producer process produces information 0 consumer process consumes the produced information I Processes need synchronization 0 consumer cannot use information before it is produced by the producer I Abstraction models 0 unboundedbuffer places no practical limit on the size of the buffer 0 boundedbuffer assumes that there is a fixed buffer size EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 20 9 Models of IPC l Shared memory 0 share a region of memory between cooperating processes 0 read or write to the shared memory region 0 fast communication 0 convenient communication l Message passing 0 exchange messages send and receive 0 typically messages do not overwrite each other gt no need for conflict resolution 0 typically used for sending smaller amounts of data a slower communication 0 easy to implement even for intercomputer communication EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 21 Models of IPC 2 process A M process A i 1 shared 2 process B M process B H 1 kernel M kernel 60 b message passing shared memory EECS 678 Fundamentals of Operating Systems 7 Spring 2009 22 Message Passing l Another mechanism for interprocess communication can be employed for clientserver communication l Message passing facility provides at least two operations send message and receive message I If P and Q wish to communicate they need to establish a communication link between them exchange messages via sendreceive l Implementation issues how are links established can a link be associated with more than two processes how many links between every pair of communicating processes what is the capacity of a link fixed or variable sized message is the link unidirectional or bidirectional EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 23 x9 Message Passing Naming l Direct communication 0 processes must name each other explicitly gt send P message send a message to process P gt receiveQ message receive a message from process Q 0 properties of communication link gt links are established automatically gt a link is associated with exactly one pair of communicating processes gt between each pair there exists exactly one link 0 disadvantage gt process identifiers are hardcoded EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 24 x9 Message Passing Naming 2 l Indirect communication 0 messages are directed and received from mailboxes also referred to as ports gt send A message send a message to mailbox A gt receive A message receive a message from mailbox A 0 each mailbox has a unique id 0 processes can communicate only if they share a mailbox 0 properties of communication link gt link may be associated with many processes gt each pair of processes may share several communication links gt link may be unidirectional or bidirectional gt multiple receivers may need synchronization O mailbox can be held in the process address space or in the kernel EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 25 Message Passing 3 l Synchronization 0 message passing may be either blocking synchronous or nonblocking asynchronous blocking send has the sender block until the message is received blocking receive has the receiver block until a message is available nonblocking send has the sender send the message and continue nonblocking receive has the receiver receive a valid message or null l Buffering queue of messages attached to the link 0 zero capacity 0 messages gt Sender must wait for receiver 0 bounded capacity finite length of 17 messages gt Sender must wait if link full 0 unbounded capacity infinite length gt Sender never waits EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 26 g Interprocess Communication in Unix I Provides multiple modes of IPC o pipes FIFOs names pipes message queues shared memory 0 o o o sockets EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 Pipes l Most basic form of IPC on all Unix systems 0 also provides a useful commandline interface I Conduit for two processes to communicate l Issues to be addressed 0 is communication unidirectional or bidirectional gt Unix pipes only allow unidirectional communication 0 should communication processes be related gt anonymous pipes can only be constructed between parentchild o can pipes communicate over a network gt processes must be controlled by the same 08 l Pipes exist only until the processes exist 0 premature process exit may cause data loss I Data can only be collected in FIFO order EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 28 t Simple Example Using Pipes include ltunistdhgt include ltstdiohgt include ltstringhgt main char 5 buf1024 int fds2 s quotEECS 678 Spring 2009nquot open a pipe fd0 is opened for reading and fdl for writing pipe fds write to the write end of the pipe writefdsl s strlens This can be read from the other end of the pipe readfds0 buf strlens printfquotfds0d fdsldnquot fdsl writel buf strlens fds0 EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 29 t IPC Example Using Pipes main char s buf1024 int fds2 s quotEECS 678 Spring 2009 Pipe program 2nquot create a pipe pipefds create a new process using fork if fork child process All file descriptors including pipe are inherited and copied writefdsl s strlens exit0 parent process readfds0 buf strlens writel buf strlens EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 30 Pipes Used for Process Synchronization main char s buf1024 int fds2 s quotEECS 678 Spring 2009 Pipe program 3nquot create a pipe pipe fds if fork 0 child process printfquotChild line lnquot readfds0 s strlens printfquotChild line 2nquot else parent process printfquotParent line lnquot writefdsl buf strlens printfquotParent line 2nquot EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 9 Pipes Used in Unix Shells l Pipes commonly used in most Unix shells output of one command is input to the next command example binps ef binmore I How does the shell realize this command create a process to run ps ef create a process to run more create a pipe from ps ef to more the standard output of the process to run ps ef is redirected to a pipe streaming to the process to run more the standard input of the process to run more is redirected to be the pipe from the process running ps ef EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 32 x9 FIFO Named Pipes l Pipe with a name I More powerful than anonymous pipes o no parentsibling relationship required 0 allow bidirectional communication 0 FlFOs exists even after creating process is terminated l Characteristics of FlFOs 0 appear as typical files 0 only allow halfduplex communication 0 communicating process must reside on the same machine EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 33 Producer Consumer Example with FIFO l Producer Code main char strMAXLENGTH int num fd mkfifoFIFONAME 0666 create FIFo file 11 openFIFONAME OWRONLY open FIFo nquot printfquotwaiting for readers fd printfquotgot a reader printfquotEnter text to write in the FIFO file fgetsstr MAXLENGTH whilefeofstdin if num writefd perrorquotwritequot stdin str strlenstr else printfquotproducer wrote d bytesnquot fgetsstr MAXLENGTH stdin EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 for writing quotgt 1 num 34 Producer Consumer Example with FIFO 2 l Consumer code main char strMAXLENGTH int num fd 0666 make fifo if not already present mkfifo FIFONAME quot printfquotwaiting for writers fd openFIFONAME ORDONLY open fifo for reading printfquotgot a writer nquot do ifnum readfd str MAXLENGTH 1 perrorquotreadquot else strnum 39039 printfquotconsumer read d bytesnquot num printfquotsquot str whilenum gt 0 EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 35 x9 Message Passing in Unix Linux uses indirect communication or mailboxes Queues can be associated with multiple processes 0 synchronization may be required Communicating processes can use any number of queues 0 each queue is identified by a unique identifier Capacity of the link is system initialized o can be overridden by the user Messages are of a fixed size 0 specified by the buffer length Each communicating process can send and receive from the same queue EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 36 Message Queue Example int main identifier for the message queue int queueid send and receive message buffers struct msgbuf sendbuf recvbuf create a message queue queueid msgget0 SIRUSRSIWUSRIPCCREAT send a message to the queue strcpysendbuf quotEECS 678 Spring 2009 Classquot msgsndqueueid struct msgbuf ampsendbuf sizeofsendbuf get the message from the queue msgrcvqueueid struct msgbuf amprecvbuf sizeofrecvbuf 0 0 printfquotsnquot recvbufbuffer delete the message queue and deallocate resources msgctqueueid IPCRMID NULL return 0 EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 37 9 Message Queues Example 2 Message passing in Linux is done via message queues msgget create a new message queue 0 return existing queue identifier if it exists msgsnd send a message to the queue 0 each message should be in a buffer like struct msgbuf long mtype char mtextl o nonblocking unless no space in the queue msgrcv receive message from the queue o mtype can be used to get specific messages msgctl perform control operations specified by cmd 0 second argument we use it to terminate queue EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 38 x9 Memory Sharing in Unix I Multiple processes share single chunk of memory I Implementation principles 0 uniquely naming the shared segment gt systemwide or anonymous name 0 specifying access permissions gt read write execute o dealing with race conditions gt atomic synchronized access I Most threadlevel communication is via shared memory EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 39 g Shared Memory Example int main int segmentid char sharedmemory const int size 4096 allocate and attach a shared memory segment segmentid shmgetIPCPRIVATE size SIRUSRSIWUSR sharedmemory char shmatsegmentid NULL 0 write and print a message to the shared memory segment sprintfsharedmemory quotEECS 678 Spring 2009 Classquot printfquotsnquot sharedmemory detach and remove the shared memory segment shmdtsharedmemory shmctsegmentid IPCRMID NULL return 0 EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 40 t9 Shared Memory Example 2 shmget create shared memory segment 0 PCPRVATE specifies creation of new memory segment of size rounded to the system page size 0 access permissions as for normal file access 0 returns identifier of shared memory segment shmat attach shared memory segment 0 must for every process wanting access to the region 0 segment identified by segmentid 0 system chooses a suitable attach address shmctl performs the control operation specified by cmd 0 command is PCRMID to remove shared segment see program sharedmemory2c Read man pages EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 41 Unix Domain Sockets l Sockets 0 can be defined as an endpoint for communications 0 twoway communication pipe 0 can be used in a variety of domains including Internet I Unix Domain Sockets 0 communication between processes on the same Unix system 0 special file in the file system I Mostly used for clientserver programming 0 client sending requests for information processing 0 server waiting for user requests 0 server performing the requested activity and sending updates to client I Socket communication modes 0 connectionbased TOP 0 connectionless UDP EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 42 Unix Domain Sockets System Calls l socket create the Unix socket int socketint domain int type int protocol 0 domain is AFUNIX l bind assign a name to a socket 0 int bindint sockfd socklent addrlen const struct sockaddr myaddr O myaddr is addrlen bytes long I listen listen to incoming client requests 0 int listenint sockfd int backlog O backlog specifies the queue limit for incoming connctions EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 43 g Unix Domain Sockets System Calls 2 I accept create a new connected socket 0 int acceptint sockfd struct sockaddr addr socklent addrlen 0 only for connectionbased protocols l recv receive messages from socket O ssizet recvint s void buf sizet len int flags 0 message placed in buf I close close the socket connection EECS 678 Fundamentals of Operating Systems 7 Spn39ng 2009 44 5 Socket Example Echo Server I see socketserverc I see socketcientc EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 45 59 Communications in ClientServer Systems I Sockets l Remote Procedure Calls l Remote Method Invocation Java EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 46 Remote Procedure Calls l Remote procedure call RPC abstracts subroutine calls between processes on networked systems 0 subroutine executes in another address space 0 uses message passing communication model 0 messages are wellstructured o RPC daemon on the server handles the remote calls I Clientside stub o proxy for the actual procedure on the server 0 responsible for locating correct port on the server 0 responsible for marshaling the procedure parameters l Serverside stub 0 receives the message 0 unpacks the marshalled parameters 0 performs the procedure on the server returns result EECS 678 Fundamentals of Operating Systems 7 Sp ng 2009 47 9 Marshalling Parameters client remote object val serversomeMelhodAB stub boolean someMethod Object x Object y implementation of someMethod skeleton A B someMethod boolean return value EECS 678 Fundamentals of Operating Systems 7 Spring 2009 48 Execution of RFC cllenl user calls kernel to send RFC message to procedure X kernel sends message to matchmaker to nd port number kernel places pan Pin user FlPC message kernel sends RFC kernel receives reply passes ll to user messages server F f a i 39 malohmaker Port matchmaker racewes Flezaddress quot1555399 looks for Rpc x up answer From39 sewer malchmaker replies to clienl Fle RFC X wilh port P Port P From client daemon To sewer listenlng lo Porl porl P purl P receives ltcomenlsgt message From RPC daemon Perl P processes To lent requesl and Perl kernel Processes semi lt0ulpulgt output EECS 678 Fundamentals of Operating Systems 7 Spring 2009 49 3 Remote Method Invocation l Remote Method Invocation RMI Java mechanism API to perform RPCs Java remote method protocol JRMP only allows calls from one JVM to another JVM CORBA is used to support communication with nonJVM code client obtains reference to remote object and invokes methods on them JVM JVM Java remote eth program 0d Invocatlo 0 remote object EECS 678 Fundamentals of Operating Systems 7 Spring 2009 50
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'