CS代考 COMP 2432 2021/2022

Operating Systems
Interprocess Communication and Programming

 Interprocess communication

Copyright By PowCoder代写 加微信 powcoder

 Unix/Linux interprocess communication  Unix/Linux unnamed pipe programming  Communication topology
 Unix/Linux named pipe programming
COMP 2432 2021/2022

Interprocess Communication
 Interprocess communication (IPC) mechanisms allow processes to communicate and to synchronize.
 Data transfer and sharing  Event notification
 Resource sharing
 Synchronization
 Process control
 Two major IPC mechanisms:  Shared memory
 Message passing
COMP 2432 2021/2022

Interprocess Communication
 Message passing is more common in practice.
 It is hard to share memory content across different
computers over the network.
 Even sharing memory within the same computer with several CPU’s is not always straightforward.
 Workable for a shared bus or cross-bar switch to multiple memory banks, but not easy for individual memory modules with CPU.
 Issues on message passing:
 How are links established?
 Are links directly or indirectly connecting the processes?
 Can a link be associated with more than two processes?
 How many links between every pair of processes?
 What is the capacity of a link?
 Is the size of a message for a link fixed or variable?
 Is a link unidirectional or bi-directional? COMP 2432 2021/2022

Interprocess Communication
 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:
 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.
COMP 2432 2021/2022

Interprocess Communication
 Indirect communication
 Messages are directed and received from mailboxes (also called ports).
 Each mailbox has a unique identifier.
 Processes can communicate only if they share a mailbox.
 Properties of communication link:
Link is established only if processes share a common mailbox.
 A link may be associated with many processes.
 Each pair of processes may share several links.
 Link may be unidirectional or bi-directional.
 Operations:
 create a new mailbox.
 send and receive messages through mailbox.
 destroy a mailbox. COMP 2432 2021/2022

Interprocess Communication
 Synchronization between message sender and message receiver.
 Message passing may be either blocking or non- blocking.
 Blocking is considered synchronous (need to wait).
Blocking send ensures that the sender is blocked until the message is received by the receiver.
Blocking receive ensures that the receiver is blocked until a message is available from the sender.
 Non-blocking is considered asynchronous (no need to wait).
Non-blocking send allows the sender to send a message and can always continue.
Non-blocking receive allows the receiver to receive a
valid message or receive null if message is not available. COMP 2432 2021/2022

Interprocess Communication
 Four possible communication arrangements could be made.
 Which is the most common / least common?
Receive Send
Blocking send / blocking receive
Non-blocking
Blocking send / non-blocking receive
Non-blocking
Non-blocking send / blocking receive
COMP 2432 2021/2022
Non-blocking send / non-blocking receive

Interprocess Communication
 A queue of messages is attached to the link to store (buffer) those outstanding messages.
 Three different implementations for the message queue:
 Zero capacity
 No message could be buffered.
 Sender must wait for receiver and vice versa.
 Bounded capacity
 Queue can only store up to n messages.  Sender must wait if the queue is full.
 Unbounded capacity
 Queue can hold infinite number of messages.
 Sender never needs to wait. COMP 2432 2021/2022
 Buffering
 Sender may have sent several messages and
receiver has not read them.

Providing IPC
 IPC package is used to establish interprocess communication.
COMP 2432 2021/2022
 The package sets up a data structure in kernel space.  The data structure is usually persistent, i.e., it will
normally continue to exist until being deleted.
 Appropriate system calls are provided for a programmer to develop a program using IPC mechanisms.
 Creation  Writing  Reading  Deletion
Why should the IPC data structure be in kernel space?

Unix/Linux IPC
 Why is shared memory not as practical in Unix/Linux?  Consider the following C program:
 No sharing can be done to the data part. COMP 2432 2021/2022
 What would happen in MS-DOS?  Case 1: treat a.out as a.com  Case 2: treat a.out as a.exe
A good OS will provide proper protection mechanism against system crash.
 At most only the user program should crash, but not others.
With protection, a process cannot (and should not) access the memory space of other processes, nor the system (kernel) memory space.

Unix/Linux IPC
 Shared memory mechanism
 Special system calls are provided to create shared memory segments within kernel memory space.
User processes make system calls to create / remove / write to / read from the shared kernel memory space.
 This is not flexible and is seldom used.
 Unix Pthreads library provides more well-defined and more comprehensive mechanisms to support shared memory, since threads within the same process naturally share the memory space.
 Linux also has Pthreads library available.
COMP 2432 2021/2022

Unix/Linux IPC
 Message passing mechanism
 Achieved via pipes and sockets.
 Two major types of pipes:  Unnamed pipes
 Named pipes
 Conceptually, a socket looks like a named pipe.
 A Unix/Linux pipe is a unidirectional, FIFO, unstructured data stream:
 A buffer allocated within the kernel.
 Operates in one direction only.
 Some plumbing is required to use a pipe.  Fixed maximum size.
 No data type being transferred.
 Very simple flow control.
 Cannot support broadcast.
COMP 2432 2021/2022

Unnamed Pipe
 An unnamed pipe is created via system call pipe().  A kernel buffer is allocated.
 Two file descriptors (fd) forming a 2-element array are created to identify the read-end and write-end of the pipe.
 Consistent with the meaning of stdin and stdout for file I/O, fd[0] is for reading and fd[1] is for writing.
 A process will call read() to read data from the pipe via fd[0] and call write() to write data to the pipe via fd[1].
user process
COMP 2432 2021/2022

create a pipe  Program fragment for unnamed pipe:
Unnamed Pipe
if (pipe(fd) < 0) { printf("Pipe creation error\n"); exit(1); } ... strcpy(buf,”hello”); write data int fd[2]; write(fd[1], buf, strlen(buf)); printf(“String [%s] written to pipe\n",buf); n = read(fd[0], buf2, 80); /* read from pipe */ buf2[n] = 0; printf("%d char read from pipe: [%s]\n", n, buf2); Lecture 5 It sends data over the pipe to itself !!! COMP 2432 2021/2022 Unnamed Pipe  A pipe should connect two processes, not to connect a process with itself.  Otherwise it just naively talks to itself.  Child processes need to be created via system call fork() like before, but after the pipe is created.  Recall that fork() will make the child an exact copy of the parent. user process fd[0] fd[1] parent fd[0] fd[1] child fd[0] fd[1] COMP 2432 2021/2022 Unnamed Pipe  Now both child and parent can write to fd[1] and read from fd[0].  There is only ONE pipe, so both will write to the SAME pipe and read from the SAME pipe.  To avoid confusion, the unused ends must be closed.  Closing the read end of parent and write end of child via system call close(), parent can write to child and child can read from parent, and not the other way round. parent fd[0] fd[1] child fd[0] fd[1] COMP 2432 2021/2022 parent create a child create a pipe Program fragment with child getting data from parent: Unnamed Pipe if (pipe(fd) < 0) { printf("Pipe creation error\n"); exit(1); } pid = if (pid < 0) { printf("Fork failed\n"); exit(1); } else if (pid == 0) { /* child */ close(fd[1]); /* close child out */ // child program here ... read read read close(fd[0]); /* close child in */ } else { /* parent */ close(fd[0]); /* close parent in */ // parent program here ... write write write close(fd[1]); /* close parent out */ close unused end close unused end COMP 2432 2021/2022 Unnamed Pipe  Childoftenneedstosenddatatoparent.  This can also be achieved by creating another pipe.  We need to close the unused ends for this usage.  Closing the read end of child and write end of parent via system call close(), child can write to parent and parent can read from child, and not the other way round.  Communication can thus go in both direction, i.e. bi-directional communication.  Programmingguidelinestoreducebugs:  Draw a diagram for all the pipes between parent and children.  Indicate the direction of data flow on each pipe.  Create array variable(s) to store fd[] for all the pipes.  Since parent will see all pipes, and children can see part or all of them, each process needs to close all unused ends in the diagram based on the fd[] variables. COMP 2432 2021/2022  How can a parent talk to child and get data back from child?  Keep both pairs of pipes, one for parent to write to child as before, and one for child to write to parent as here. parent create a child create a pipe Program fragment with child sending data to parent: Unnamed Pipe if (pipe(fd) < 0) { printf("Pipe creation error\n"); exit(1); } pid = if (pid < 0) { printf("Fork failed\n"); exit(1); } else if (pid == 0) { /* child */ close(fd[0]); /* close child in */ // child program here ... write write write close(fd[1]); /* close child out */ } else { /* parent */ close(fd[1]); /* close parent out */ // parent program here ... read read read close(fd[0]); /* close parent in */ close unused end close unused end COMP 2432 2021/2022 Unnamed Pipe  Unnamed pipes are widely used in Unix/Linux.  Shell programs implement the command level pipe (e.g. ls | wc) via a combination of fork() / pipe() / exec*().  fork() is used to create child processes to hold and execute the relevant commands, e.g. ls and wc.  pipe() is used to create the pipe(s) to be shared between the processes, e.g. ls and wc.  exec*() is used to replace the child processes with the programs, e.g. ls and wc.  Note that three child processes and two pipes will be created to execute a chained command like prog1 | prog2 | prog3. COMP 2432 2021/2022 Unnamed Pipe Limit  What is the maximum number of unnamed pipes that can be created?  Remember that each unnamed pipe will occupy two file descriptors in Unix/Linux.  How can you find out the answer?  On apollo and apollo2, maximum number of fd = 1024, but fd 0, 1 and 2 are already reserved for stdin, stdout, and stderr.  How can you verify the answer?  How many unnamed pipes can be created on a Mac?  You could try out. COMP 2432 2021/2022 Communication Topology  Star topology  Parent or coordinator talks to each individual child process.  Simple to do, but bottleneck at parent.  Very few pipes.  At most 2 rounds of messages.  Ring topology  Processes connected in a ring.  Very few pipes.  Quite many rounds of messages.  Linear topology  Processes connected in a single line or chain.  Very few pipes.  Many rounds of messages. COMP 2432 2021/2022 Communication Topology  Fully connected  Parent or child processes directly talk to one another.  Need many pipes.  Fast communication.  Tree topology  Parent at each level of tree talks to its child process.  Very few pipes.  More rounds of messages. COMP 2432 2021/2022 Communication Topology  Mesh topology  Links follow some structure, often grid-like.  Fewer pipes than fully connected.  Could be harder to program and maintain.  Need routing for non-neighboring processes.  Flexible.  Hypercube topology  Links follow a cube-structure.  Fewer pipes than fully connected.  Well-established routing mechanism for non-neighboring processes.  Flexible.  Bus topology is not considered with pipes.  Like Ethernet. COMP 2432 2021/2022 Communication Topology  Howmanypipesareneededwithnprocesses?  Star: 2(n-1) for both directions  Bottleneck/single-point-of-failure at parent with 2(n-1) pipes  Noparticularbottleneck  Linear:2(n-1)  Node failure will separate the communication.  Fullyconnected:n(n-1)  No bottleneck: everybody with 2(n-1)  Tree:2(n-1)  Bottleneckspreadaround  Mesh: between 2(n-1) and n(n-1)  Each node is connected to around 4 neighbors  Hypercube: between 2(n-1) and n(n-1)  Each node is connected to log2 n neighbors COMP 2432 2021/2022 Program fragment with parent/child/grand child getting data from parent: Linear Communication COMP 2432 2021/2022 int fdP2C[2], fdC2G[2]; if (pipe(fdP2C) < 0) { printf("Pipe creation error\n"); exit(1); } if (pipe(fdC2G) < 0) { printf("Pipe creation error\n"); exit(1); } if (fork() == 0) { /* child */ if (fork() == 0) { /* grand child */ close(fdC2G[1]); close(fdP2C[0]); close(fdP2C[1]); /* close excessive */ // grand child program here ... read read read close(fdC2G[0]); /* close grand child in */ grand } else { /* child */ /* close excessive */ child // child program here ... read write read write read write close(fdP2C[0]); close(fdC2G[1]); /* close child in and grand child out */ } else { /* parent */ close(fdP2C[1]); close(fdC2G[0]); close(fdP2C[0]); close(fdC2G[0]); close(fdC2G[1]); /* close excessive */ // parent program here ... write write write close(fdP2C[1]); /* close parent out */ Star Communication fd[0] fd[9] child 0 . . . child 9  Programfragmentwith10childrengettingdatafromparent: // use a loop over child from 0 to 9 to create more pipes if (pipe(&fd[child][0]) < 0) { printf("Pipe creation error\n"); exit(1); } // use a loop to create more child processes if (fork() == 0) { /* child */ /* find out my own id and store in me (a number from 0 to 9) */ /* close child out */ // close(fd[not me][1]); close(fd[everybody][0]); - close excessive // child program here ... read read read close(fd[me][0]); /* close child in */ } else { /* parent */ // close(fd[everybody][0]); - close parent in for all children // parent program here ... write write write // close(fd[everybody][1]); - close parent out for all children } COMP 2432 2021/2022 close(fd[me][1]); int fd[10][2]; Named Pipe  Anamedpipeisactuallyafile.  A named pipe is created by creating a special file, via the system call mkfifo().  After a named pipe is created, any two processes knowing the name of the file will first open() the pipe like a file.  They can then communicate by writing to and reading from it, using write() and read() accordingly like a file.  The pipe remains even after both processes have completed.  It is a good programming practice to create the named pipe and then delete the named pipe inside the program at the end, via unlink() system call. user process 1 outfd user process 2 infd COMP 2432 2021/2022 char pipename[] = "/tmp/mypipe"; Named Pipe create named pipe open to write  Program fragments with P2 getting data from P1: /* create the named pipe */ if (mkfifo(pipename,0600) < 0) { printf("Pipe creation error\n"); exit(1); } /* open pipe for writing */ if ((fd = open(pipename,O_WRONLY)) printf("Pipe open error\n"); exit(1); } write write write unlink(pipename); open to read /* open pipe for reading */ if ((fd = open(pipename,O_RDONLY)) printf("Pipe open error\n"); exit(1); read read read remove the pipe Lecture 5 COMP 2432 2021/2022 Named Pipe  Sometimes it is clumsy to develop two separate programs for communication.  Note that there is no distinction between parent and child.  It is also tedious for the user to physically run the two programs (and to make sure to run the two programs in proper order, i.e. run the program creating the named pipe first).  This can be done by executing them on two different windows.  This can also be done by executing one program and put it to background (using &) and then run the second program.  We could make use of the fork() mechanism for the parent to create the child and run the two programs in one single shot.  We could also combine the two programs into one. COMP 2432 2021/2022 Advantage: pipe is always created before use char pipename[] = "/tmp/mypipe"; Named Pipecreate named pipe execute P2  Program fragments with P2 automatically executed: if (mkfifo(pipename,0600) < 0) { printf("Pipe creation error\n"); exit(1); } returnpid = fork(); if (returnpid < 0) { printf("Fork failed\n"); exit(1); } else if (returnpid == 0) { /* child */ execl(”P2”,”P2”,NULL); /* execute P2 */ } else { /* parent */ if ((fd=open(pipename,O_WRONLY)) < 0) { printf("Pipe open error\n"); exit(1); } write write write wait(returnpid); unlink(pipename); } /* open pipe for reading */ if ((fd = open(pipename,O_RDONLY)) < 0) { printf("Pipe open error\n"); exit(1); } read read read Lecture 5 COMP 2432 2021/2022 char pipename[] = "/tmp/mypipe"; Named Pipecreate named pipe  Program fragment with one single copy of code: if (mkfifo(pipename,0600) < 0) { printf("Pipe creation error\n"); exit(1); } returnpid = fork(); if (returnpid < 0) { printf("Fork failed\n"); exit(1); } else if (returnpid == 0) { /* child */ /* open pipe for reading */ if ((fd = open(pipename,O_RDONLY)) < 0) { printf("Pipe open error\n"); exit(1); } read read read exit(0); } else { /* parent */ if ((fd = open(pipename,O_WRONLY)) < 0) { printf("Pipe open error\n"); exit(1); } write write write wait(returnpid); unlink(pipename); } Lecture 5 COMP 2432 2021/2022 Named Pipe  Among the three different approaches in using named pipe, which one do you prefer? COMP 2432 2021/2022  Option 1: two separate programs run separately.  Option 2: two programs, with one program executing the  Option 3: one single program.  Under which situation would option 1/2/3 be more preferable?  Option 1 is like socket programming in a network.  The special file is replaced by an IP address (or a domain name) and a port number. Socket programming is improved as a new process would be created by P1 with a new communication path talking to incoming process P2. Named Pipe  Named pipes could also be structured with topology.  Given the potential larger naming space (on the names of pipes), it is less common to involve many processes.  Managing named pipes with many processes is also tedious and error-prone, especially explicit creation and deletion are required.  Named pipes are not used often in Unix/Linux programming.  Sockets are more common and more flexible.  Advantage of named pipe is often related to the support of heterogeneous programs, perhaps from different users. COMP 2432 2021/2022  Interprocess communication  Unix/Linux interprocess communication  Unix/Linux unnamed pipe programming  Communication topology  Unix/Linux named pipe programming COMP 2432 2021/2022 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com