packets

17.3 NTPVM Project Overview

The tasks in NTPVM are independent processes grouped into units called computations. The dispatcher is responsible for creating and managing tasks. In general, the tasks of a computation do not have to reside on the same machine, and the specification of the project is designed with this extension in mind. However, a single dispatcher controls all the computations for the project described in this chapter.

The dispatcher communicates with the outside world by reading packets from its standard input and writing packets to its standard output. The dispatcher might receive a packet requesting that it create a new task, or it might receive a data packet intended for a task under its control. The dispatcher forwards output generated by the tasks under its control to its own standard output in the form of packets. For the first four parts of the project, the tasks send ASCII data and the dispatcher wraps the data in a packet. Later, the tasks generate the packets themselves .

Program 17.1 shows the ntpvm.h header file that contains the relevant type definitions for the dispatcher. Include this file in all the programs in this project.

The dispatcher packets include a computation ID, a task ID, a packet type, a packet length and the packet information. The first four items make up a fixed-length packet header that is stored in a structure of type taskpacket_t . Assume that the information portion of the packet contains no more than MAX_PACK_SIZE bytes.

The dispatcher keeps information about each active task in a global tasks array of type ntpvm_task_t , which should be implemented as an object with appropriate functions for accessing and modifying it. When the description refers to "modifying" or "accessing" information in the tasks object, it means calling a public function in the file to perform the action. Do not allow the dispatcher to execute more than MAX_TASKS simultaneous tasks. Initially, set the compid member of each element of the tasks array to 1 to indicate that the slot is empty.

Program 17.1 ntpvm.h

The ntpvm.h header file .

 #include <pthread.h> #include <sys/types.h> #define MAX_PACK_SIZE 1024 #define MAX_TASKS 10 #define NUMTYPES 6 typedef enum ptype {NEWTASK, DATA, BROADCAST, DONE,                     TERMINATE, BARRIER} packet_t; typedef struct {      int compid;      int taskid;      packet_t type;      int length; } taskpacket_t; typedef struct {      int compid;                            /* computation ID for task */      int taskid;                               /* task ID for the task */      int writefd;                        /* holds dispatcher->child fd */      int readfd;                         /* holds child->dispatcher fd */      int recvbytes;      int recvpacksets;      int sentbytes;      int sentpackets;      pid_t taskpid;                   /* process ID of the forked task */      pthread_t tasktid;             /* thread ID of task output thread */      int barrier;         /* -1 if not at barrier, else barrier number */      pthread_mutex_t mlock;                  /* mutex lock for element */      int endinput;                   /* true if no more input for task */ } ntpvm_task_t; 

There are six types of dispatcher packets in all: NEWTASK , DATA , BROADCAST , DONE , TERMINATE and BARRIER . A packet consists of a header structure of type taskpacket_t followed by a data field that is an array whose size is specified by the length field of the header. The maximum value of length is MAX_PACK_SIZE . The dispatcher interprets the packet types as follows .

1. When the dispatcher receives a NEWTASK packet on standard input, it initiates a new task. The information portion of this packet gives the command line to be executed by the forked child task. The dispatcher creates two pipes and forks a child that calls execvp for the specified command.

2. The dispatcher treats the DATA packets that it receives on standard input as input data for the task identified by the computation ID and task ID members of the packet header. For the first four parts of the project, the dispatcher strips off the packet header and writes the actual packet data to writefd of the appropriate task.

3. When a task writes data to its standard output, the dispatcher forwards the data to standard output. The first four parts of this project run standard UNIX utilities as the tasks. Since these commands produce just ASCII text as output, the dispatcher packages the data into DATA packets before sending to standard output. Starting with part five, the tasks send DATA packets.

4. When the dispatcher receives a DONE packet on standard input, it closes the writefd file descriptor for the task identified by the computation ID and task ID members of the packet header. The corresponding task then detects end-of-file on its standard input.

5. When the dispatcher detects end-of-file on the readfd descriptor of a task, it performs the appropriate cleanup and sends a DONE packet on standard output to signify that the task has completed.

6. The dispatcher forwards any BROADCAST packets from standard input to all tasks in the specified computation.

7. If a task sends a BROADCAST packet to the dispatcher, the dispatcher forwards the request to all tasks in the same computation and also forwards the request on its standard output. In this way, all the tasks within a computation receive the message.

8. If the dispatcher receives a TERMINATE packet on its standard input, it kills the task identified by the packet's computation ID and task ID. If task ID is 1, the dispatcher kills all tasks in the specified computation. The dispatcher handles a TERMINATE packet received from readfd in a similar way. However, if no task ID matches the packet or if task ID is 1, the dispatcher also writes the TERMINATE packet to standard output.

9. The BARRIER packets synchronize tasks of a computation at a particular point in their execution.

The NTPVM project has the following parts:

Part I:	Setup of I/O and testing [Section 17.4].
Part II:	Single task with no input (handle NEWTASK and outgoing data) [Section 17.5].
Part III:	One task at a time (handle NEWTASK , DATA and DONE packets) [Section 17.6].
Part IV:	Multiple tasks and computations (handle NEWTASK , DATA and DONE packets) [Section 17.7].
Part V:	Task synchronization (handle BROADCAST and BARRIER packets) [Section 17.8].
Part VI:	Cleanup (handle TERMINATION packets and signals) [Section 17.9].
Part VII:	Ordered message delivery [Section 17.10].

In the first four parts of the project, the child tasks do not communicate by using packets, and the dispatcher strips off the packet headers before writing to writefd . This format allows the dispatcher to run ordinary UNIX utilities such as cat or ls as tasks. In Part V, the tasks communicate with the dispatcher by using packets. At that point, the project requires specific task programs for NTPVM testing. The remainder of this section gives examples of different types of packets and methods the dispatcher uses to handle them.

17.3.1 NEWTASK packets

The dispatcher waits for a NEWTASK packet from standard input. Such a packet includes a computation ID, a task ID and a command-line string.

Example 17.1

The following NEWTASK packet requests that task 2 in computation 3 be created to execute ls -l .

Computation ID:	3
Task ID:	2
Packet Type:	NEWTASK
Packet Data Length:	5
Packet Information:	ls -l

The data in the packet of Example 17.1 is not null- terminated . The dispatcher must convert the data to such a string before handing it to makeargv or execvp .

The dispatcher asks the tasks array to find a free entry and to store the information about the new task. The dispatcher discards the packet and reports an error if it detects that a task with the same computation and task IDs is already in the tasks array. The new entry has sentpackets , sentbytes , recvpackets , recvbytes and endinput members of the tasks array entry set to 0 and the barrier member set to 1 to signify that the task is not waiting at a barrier.

The dispatcher then creates two pipes and uses two of the four resulting pipe file descriptors for communication with the child task. These descriptors are stored in the readfd and writefd members of the tasks array entry. The dispatcher forks a child and stores the child process ID in the taskpid member of the tasks entry. The dispatcher closes unused pipe file descriptors and then waits for I/O either from its standard input or from the readfd descriptors of its tasks.

The child task forked by the dispatcher redirects its standard input and output to the pipes and closes the unused file descriptors. The child then calls execvp to execute the command string. Use the makeargv function of Program 2.2 on page 37 to create an argument array for input to execvp .

17.3.2 DATA packets

When the dispatcher reads a DATA packet from standard input, it asks the tasks object to determine whether the packet's task ID and computation ID match those of any entry in the tasks array. The dispatcher discards the packet if no entry matches. Otherwise, the dispatcher updates the recvpackets and recvbytes members of the task's entry in the tasks array.

For the first four parts of the project, the tasks are standard UNIX utilities that accept ASCII input. The dispatcher forwards the information portion of the packet to the task on the task's writefd descriptor. In Parts V, VI and VII the tasks receive the full data packets directly.

Example 17.2

After receiving the following DATA packet, the dispatcher sends the words This is my data to task 2 in computation 3.

Computation ID:	3
Task ID:	2
Packet Type:	DATA
Packet Data Length:	15
Packet Data:	This is my data

The dispatcher also forwards data received from individual tasks to its standard output in the form of DATA packets. For the first four parts of the project, the dispatcher interprets input from readfd as raw output from the task. It creates a DATA packet with the task's computation ID and task ID and uses the information read from readfd as the information portion of the packet. The dispatcher then writes the DATA packet to its standard output. Starting with Section 17.8, each task reads and writes its data in packet format. In these sections, the dispatcher copies the DATA packets to its standard output.

17.3.3 DONE packets

When the dispatcher receives a DONE packet on standard input, it sets the corresponding task's endinput member in the tasks array and closes the writefd descriptor for the task. The dispatcher discards any subsequent DONE or DATA packets that arrive for the task.

Example 17.3

The following DONE packet specifies that there is no more input data for task 2 in computation 3.

Computation ID:	3
Task ID:	2
Packet Type:	DONE
Packet Data Length:
Packet Data:

When the dispatcher receives an end-of-file indication on a readfd descriptor, it closes that descriptor and forwards a DONE packet on its standard output. If the writefd descriptor for the task is still open , the dispatcher closes it. The dispatcher must eventually call wait on the child task process and set the compid member of the tasks array entry to 1 so that the array entry can be reused.

If the dispatcher receives an end-of-file indication on its own standard input, it closes the writefd descriptors of all active tasks and sets the endinput member of the tasks array entry for each active task to 1. When it has received an end-of-file indication on the readfd descriptors for all active tasks, the dispatcher waits for each task and exits. The dispatcher should also periodically wait for all its completed children.