Class Note for EECS 678 with Professor Kulkarni at KU 2
Class Note for EECS 678 with Professor Kulkarni at KU 2
Popular in Course
Popular in Department
This 13 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 16 views.
Reviews for Class Note for EECS 678 with Professor Kulkarni at KU 2
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 ofOpemting Systems 7 Sp ng 2009 15 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 le is loaded into memory 0 same program executed multiple times will correspond to different process each time EECS 678 Fundamentals of Operating Systems 7 Spling 2009 Process in Memory max stack heap data text EECS 678 Fundamentals ofOpemting Systems 7 Sp ng 2009 a 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 nished execution l Each processor can only run one process at a instant EECS 678 Fundamentals of Operating Systems 7 Spling 2009 9 Diagram of Process State admitted interrupt exit terminated scheduler dispatch IO or event completion IO or event wait EECS 678 Fundamentals of Operating Systems 7 Spring 2009 1539 Process Control Block PCB l PCB is representation of a process in an operating system maintains processspeci c information necessary for scheduling l Information associated with each process process state program counter CPU registers CPU scheduling information memorymanagement information accounting information O status information EECS 678 Fundamentals of Operating Systems 7 Spring 2009 9 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 9 CPU Switch From Process to Process process PO operating system process P1 interrupt or system call executing J1 save state into PCB0 Idle gt idle interrupt or system call J reload state from PCB0 executing u reload state from PCB1 I save state into PCB1 r executing idle EECS 678 Fundamentals of Operating Systems 7 Spring 2009 g 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 Spring 2009 9 5 Ready Queue And Various IIO Device Queues queue header PCB7 P082 ready head 39j queue tail registers registers mag head i tape 39 unitO 13 39 3 tmag head 1 a e unih taquot PCB3 PCB14 PCB6 gt gt i disk head I unitO tau P085 terminal unit 0 EECS 678 Fundamentals ofOperating Systems 7 Spring 2009 10 7 Representation of Process Scheduling gt ready queue A lO queue IO request time slice expired child fork a executes child interrupt occurs EECS 678 Fundamentals of Operating Systems 7 Spring 2009 11 wait for an interrupt 5 Schedulers l Systems with a possibility of huge deluge ofjob requests may use multiple schedulers l Longterm scheduler orjob scheduler o selects processes to be brought into the ready queue 0 controls the degree of multiprogramming 0 controls the mix of active CPUbound and IIObound processes 0 invoked infrequently 0 can afford more time to make selection decision I Shortterm scheduler or CPU scheduler o selects the process to be executed next and allocates CPU 0 invoked frequently 0 necessary to limit scheduling overhead EECS 678 Fundamentals ofOperating Systems 7 Spring 2009 12 a Context Switch I A context switch is the process of storing and restoring the state context ofthe CPU such that multiple processes can share a single CPU resource 0 for timesnared or multiprogramming environments 0 context of a process represented in the PCB 0 context switcn involves a state save of the current process and a state reslore of the process being resumed next 0 switch from userto xemelmode orviceversa is a mode switch I Contextswitch time is overhead 0 the system does no useful work while switcning 0 overnead depends on hardware support gt Sun UltraSPARC provides multiple banks of registers y lntel x86 processors also provide some support EECs mxmmgmmwmwswm swgmv 3 a Process Creation I 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 cnild process 0 processes identified and managed via a process identifier pid I Resource sharing options 0 parent and children snare all resources 0 children snare subset of parent s resources 0 parent and child snare no resources I Execution options 0 parent and children execute concurrently 0 parent waits until cnildren terminate EcsmmMMammuwmgswm Spunng N 9 Process Creation Cont I 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 afork to replacetne process memory space with a new program EECs mxmmgmmwmwswm swgmv 5 is Process Creation Example on Unix nt mainll l pm pm is gm 5mm pmess si pm mm is ipia lt m l is em occurred si sprinsiissam wer reliedquot emi 1i i else is ipia oi i is child pmess si execlplquotbnJsquot quotlsquot quotum i else I is pm pmess si is pm mu we in the child to swim si wait inuLLi prlntf lquotmld Completequot exltl lr EcsmmMMammuwmgswm Spunng 6 a Process Creation l Parent waiting for child process to finish parent resumes EECS 678 Fundamentals of Operating Systems Spring 2009 17 9 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 I 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 Spring 2009 13 E 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 Spring 2009 19 5 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 Spring 2009 20 15 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 0 slower communication 0 easy to implement even for intercomputer communication EECS 678 Fundamentals of Operating Systems 7 Spring 2009 21 Models of IPC 2 process A process A f 1 shared 2 process B process B 534 2 1 kernel kernel 60 b message passing shared memory EECS 678 Fundamentals ofOperating Systems 7 Spring 2009 22 Message Passing Another mechanism for interprocess communication 0 can be employed for clientserver communication Message passing facility provides at least two operations 0 send message and receive message If P and Q wish to communicate they need to o establish a communication link between them 0 exchange messages via sendreceive Implementation issues 0 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 Spring 2009 23 19 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 ofOperating Systems 7 Spring 2009 24 5 Message Passing Naming 2 I Indirect communication 0 messages are directed and received from mailboxes also referred to as ports i send A message send a message to mailbox A i 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 y each pair of processes may share several communication links gt link may be unidirectional or bidirectional y multiple receivers may need synchronization 0 mailbox can be held in the process address space or in the kernel EECs mxmmgmmwmwswm swgmv 25 5 Message Passing 3 I 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 0 nonblocking receive has the receiver receive a valid message or null I Buffering queue ofmessages attached to the link 0 zero capacity 0 messages 0 y Sender must wait for receiver 0 bounded capacity finite length of n messages gt Sender rriust wait if linkfull 0 unbounded capacity infinite length i Sender never waits ECSWXRIMmm sanpc rmgsysmu Spunng 26 is lnterprocess Communication in Unix I Provides multiple modes ofch o pipes FlFOs names pipes message queues shared memory sockets EECs mxmmgmmwmwswm swgmv n is Pipes I Most basic form ofch on all Unix systems 0 also provides a useful commandline interface I Conduit for two processes to communicate I Issues to be addressed 0 is communication unidirectional or bidirectional 7 y Ufilgtlt pipes only allow unidirectional communication 0 should communication processes be related 7 v anonymous pipes can only be constructed between parentchild 0 can pipes communicate over a network gt processes must be controlled by the same 08 I Pipes exist only until the processes exist 0 premature process exit may cause data loss I Data can only be collected in FIFO order ECSWXRIMmm sanpc rmgsysmu Spunng n is Simple Example Using Pipes llJnclude ltunestclhgt llJnclude ltsthohgt llJnclude ltstr1nghgt BJHO l char s bufl1024 ent fdslzl s quotmacs 573 Spreng 2009nquot open a pepe ECHO es opened for readeng and fdll for wreteng pepelttdsgt wrete to the wretesencl of the pepe wreteltfdsl1 s str1enltsgtgt Thes can be read from the other end of the pepe readltfdsl0 buf str1enltsgtgt prntfquotfd50 to fd51 tcunquot fdslol fdsllll erte1 buf str1enltsgtgt EECs x mdmualulsafqemmgswau smegma 29 IPC Example Using Pipes maenO l char s bufl1024 ent fdslzl s quotEms 573 Spreng 2009 PJpe program Znquot create a pepe pepelttdsl create a new process uang fork Jf forkO 0gt l cthd process All le descreptors encludeng pepe are enheretecl and copeecl ertefds1 s str1enltsgtgt exetlt0gt l parent process readltfdsl0 buf str1enltsgtgt wrete1 buf str1enltsgtgt Ecsmxnmdmmmafclwmgswm swam 30 1sPipes Used for Process Synchronization maenO l char s bufl1024 ent fdle s quotEms 573 Spreng 2009 PJpe program 3nquot create a pepe pepelttdsl Jf forkO 0 l cthd process prntfquotCthd 1ene 1nquotgt readltfd50 s str1enltsgtgt prntfquotCthd 1ene znquotgt l else l parent process prntfquotParent 1ene 1nquotgt ertefds1 buf str1enltsgtl prntfquotParent 1ene znquotgt EECs x mdmualulsafqemmgswau smegma 3 is Pipes Used in Unix Shells I Pipes commonly used in most Unix shells 0 output of one command ls lrlput to the next command 0 example b1nps ef l benmore I How does the shell realize this command 0 create a process to rurl ps ef 0 create a process to rurl more 0 create a plpe frorrl ps ef to more 0 the standard output of the process to rurl ps ef ls redlrected to a plpe strearrllrlg to the process to rurl more 0 the standard lrlput of the process to rurl more ls redlrected to be the plpe from the process rurlrllrlgps ef Ecsmxnmdmmmafclwmgswm swam 32 53 FIFO Named Pipes I Pipe with a name I More powerful than anonymous pipes 0 no parentsibling relationship required 0 allow bidirectional communication 0 FlFOs exists even after creating process is terminated I Characteristics of FlFOs 0 appear as typical files 0 only allow halfdu plex communication 0 communicating process must reside on the same machine EECs m Haidamain ofOpmmig Sysrau span 2009 33 1 Producer Consumer Example with FIFO I Producer Code namltgt i char strlrLAX LENGTH Jnt num fd mkafoFIFD NAME 0556 create FIFD lee prntfquotwatng for readers quotr fd openFIFD NAME 0 worm open FIFD for ertJng prntfquotgot a reader inquoti prntfquotEnter text to erte Jn tne FIFD lee quotl fgetsltstr max LENGTH sthnlf whlelfeofstd1ngt gt H Jf num wrltefd str strlenstrgtgt 1 perrorquotwrtequotgtf else prntfquotproducer wrote ad bytesnquot num fgetsstr Max LENGTH atdm l l Ecs mdmmakofuwmgsysrm swam M Mroducer Consumer Example with FIFO 2 I Consumer code mani0 l enar atrimax LENGTH Jnt nun fd nrkafoFIFD NAME 055m make fJfo 1f not already present prntfquotwatng for erters quoti fd openFIFD NAME 0 RDDNLY open fJfo for readdng prntfquotgot a erter inquoti dot Jfnum readfd str MAX LENGTHH 1 perror quotreadquot elset atrinun 39G39 prntfquotconsumer read d bytesnquot Hum prntfquotsquot atrgt i lwhlenum gt m EECs x mdmuaimsofOpmmigswau swgmv 35 is Message Passing in Unix I Linux uses indirect communication or mailboxes I Queues can be associated with multiple processes 0 synchronization may be required I Communicating processes can use any number of queues 0 each queue is identified by a unique identifier I Capacity ofthe link is system initialized 0 can be overridden by the user I Messages are ofa xed size 0 specified by the buffer length I Each communicating process can send and receive from the same queue Ecs mdmmakofuwmgsysrm swam 36 a Message Queue Example int main identifier for the message queue int queue id send and receive message buffers struct msg buf send bUf recy bUf39 create a message queue queue id msggeto s lRUSRlS lWUSRllPC CREAT send a message to the queue strcpysend buf quotEECS 678 Spring 2009 Classquot msgsndqueue id struct msg bufampserid buf sizeofserid pun get the message from the queue msgrcvqueue id struct msg pumsrecy buf sizeorrecy buf o o printfquotsriquot recy purpufrer delete the message queue and deaiiocate resources msgctiqueue id ngtc RMID NULL return a EECs m mumps ofOpmmig system spring 2009 37 a Message Queues Example 2 I Message passing in Linux is done via message queues I msgget create a new message queue 0 return existing queue identifier if it exists I msgsnd send a message to the queue 0 each message should be in a buffer like struct msg but long mlype char mtextll o nonblocking unless no space in ihe queue I msgrcv receive message from the queue 0 mtype can be used to get specific messages I msgctl perform control operations speci ed by cmd 0 second argument We use it to terminate queue scsmmmmaimuwmgsysm Spunng 33 9 Memory Sharing in Unix I Multiple processes share single chunk of memory I Implementation principles 0 uniquely naming the shared segment t systemWide or anonymous name 0 specifying access permissions t read Write execute 0 dealing With race conditions t atomic synchronized access I Most threadlevel communication is via shared memory EECs m mumps ofOpmmig system spring 2009 39 1 Shared Memory Example int main int segment id charshared memory const int size 4095 aiiocate and attach a shared memory segment segment id shmgetlPC PRIVATE size s lRUSRlS lWUSR shared memory char shmatsegment id NULL 0 write and print a message to the shared memory segment sprintfshared memory quotEECS 678 Spring 2009 Class printfquotsriquot shared memory detach and remove the shared memory segment shmdtshared memory shmctisegment id PC RMID NULL return a scsmmmmaimuwmgsysm Spunng ya 5 Shared Memory Example 2 I shmget create shared memory segment 0 lPCPRlvATE 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 I shmat attach shared memory segment 0 must for every processwaritirig access to the region 0 segment identified by segmentid 0 system chooses a suitable attach address I shmctl performs the control operation speci ed by cmd 0 command is lPCRMlDto remove shared segment I see program sharedmemory2c I Read man pages EECs thdamaiukafOpmmigsynau swam M 1 Unix Domain Sockets I Sockets 0 can be defined as an endpointfor communications 0 twoWay communication pipe 0 can be used in a variety of domains including internal I Unix Domain Sockets 0 communication between processes on the same Unix system 0 special file in thefile 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 connectionbasediTCP 0 coririectiorilessi UDP ECSWXRIMmcmakaf pumgsysmu swam n 5 Unix Domain Sockets System Calls I socket create the Unix socket o m sockettm domam 1n type 1n protocol 0 domain is A1qu I bind assign a name to a socket o m b1nd1nt sockfd const struct sockaddr myiaddr socklenit addrlen o myiaclclr is addrlen byleslong I listen listen to incoming client requests 0 1n llstentmt sockfd 1n backlog o backlog speemesihe queue limit lor incoming connmions EECs m Nadamain afOpmmig ewe spear 2009 M is Unix Domain Sockets System Calls 2 I accept create a new connected socket o m accepum sockfd struct sockaddr addr socklenit addrlen 0 only lor connemionrbased pmlocols I recv receive messages from socket o sslze t recv1nt s vold buf 512e len m flags 0 message placed in but I close close the socket connection ECSWXRIMmcmakaf pumgsysmu swam M 5 Socket Example Echo Server I see socketserverc I see socketclientc EECS 678 Fundamentals of Operating Systems 7 Spring 2009 45 a Communications in ClientServer Systems I Sockets l Remote Procedure Calls l Remote Method Invocation Java EECS 678 Fundamentals of Operating Systems 7 Spring 2009 46 g 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 marshalling 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 Spring 2009 47 a Marshalling Parameters client remote object val serversomeMethodAB boolean someMethod Object x Object y implementation of someMethod stub skeleton A B someMethod ll boolean return value EECS 678 Fundamentals of Operating Systems 7 Spring 2009 48 Execution of RFC client user calls kernel to send RPC message to procedure X kernel sends message lo matchmaker lo rind port number kernel places port P In user Fl PC message kernel sends HPC kernel receives reply passes it to user messages server From client matchmaker receives message looks ltoulpulgt 1039 9pc x up answer From server To cllenl matchmaker Perl kernel replies I0 cllenl Re RFC X with porl P Port P From client daemon To server lislening to Port porl P porl P receives ltconrenrsgt message From RPC daemon Port P Processes To client request arid Forl kernel processes 59quotquot output EECS 678 Fundamentals of Operating Systems 7 Spring 2009 49 539 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 Java 0 program r emote method 39 InVoCat Ion EECS 678 Fundamentals of Operating Systems 7 Spring 2009 JVM 0 remote object ss 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'