非太并行虚拟机（NTPVM）项目介绍与实践

### 非太并行虚拟机（NTPVM）项目介绍与实践 #### 1. 非太并行虚拟机概述 非太并行虚拟机（NTPVM）是一种调度器，它与PVM控制守护进程（pvmd）有许多相似的特性。NTPVM调度器负责在单个主机上创建和管理任务。调度器通过标准输入接收请求，并通过标准输出进行响应，后续标准输入和输出可以重定向到网络通信端口。调度器可能会收到创建任务或向其控制下的任务转发数据的请求。 任务是执行指定程序的进程，每个任务由计算ID和任务ID标识。当调度器收到创建具有特定计算ID和任务ID的任务请求时，它会创建一对管道并派生一个子进程来执行该任务。调度器与子任务之间通过管道进行通信，从调度器到子任务的管道在调度器端标记为writefd，子任务将其标准输入重定向到该管道；从子任务到调度器的管道在调度器端标记为readfd，子任务将其标准输出重定向到该管道。 调度器支持向任务传递输入数据、接收任务的输出数据，并向具有相同计算ID的任务广播数据。此外，调度器还支持编号屏障和取消具有相同计算ID的任务。与真正的PVM相比，NTPVM在几个方面更为简单。PVM具有有序消息传递功能，允许任何任务与同一计算中的其他任务进行通信，有消息缓冲机制，还提供复杂的计算监控工具。而NTPVM在收到消息时就立即传递，不支持点对点任务通信，监控能力也较为原始。 #### 2. NTPVM项目概述 NTPVM中的任务是独立的进程，被分组为称为计算的单元。调度器负责创建和管理这些任务。一般来说，一个计算中的任务不必驻留在同一台机器上，项目规范也考虑到了这一扩展。不过，本章描述的项目由单个调度器控制所有计算。 调度器通过从标准输入读取数据包并向标准输出写入数据包与外界进行通信。它可能会收到创建新任务的数据包，或者收到针对其控制下任务的数据数据包。调度器将其控制下任务生成的输出以数据包的形式转发到自己的标准输出。在项目的前四个部分，任务发送ASCII数据，调度器将数据封装在数据包中；之后，任务自己生成数据包。 调度器数据包包含计算ID、任务ID、数据包类型、数据包长度和数据包信息。前四项组成固定长度的数据包头部，存储在taskpacket_t类型的结构中。假设数据包的信息部分包含不超过MAX_PACK_SIZE字节的数据。 调度器将每个活动任务的信息保存在全局的ntpvm_task_t类型的tasks数组中，该数组应实现为一个具有适当访问和修改函数的对象。调度器不允许同时执行超过MAX_TASKS个任务。初始时，将tasks数组每个元素的compid成员设置为 -1，表示该插槽为空。 以下是ntpvm.h头文件的代码： ```c #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; ``` 调度器数据包共有六种类型：NEWTASK、DATA、BROADCAST、DONE、TERMINATE和BARRIER。数据包由taskpacket_t类型的头部结构和一个数据字段组成，数据字段是一个数组，其大小由头部的长度字段指定。调度器对不同类型数据包的解释如下： | 数据包类型 | 调度器处理方式 | | ---- | ---- | | NEWTASK | 当调度器在标准输入上收到NEWTASK数据包时，它会启动一个新任务。该数据包的信息部分给出了派生的子任务要执行的命令行。调度器创建两个管道并派生一个子进程，该子进程调用execvp执行指定的命令。 | | DATA | 调度器将从标准输入读取的DATA数据包视为针对由数据包头部的计算ID和任务ID标识的任务的输入数据。在项目的前四个部分，调度器会剥离数据包头部，并将实际的数据包数据写入相应任务的writefd。调度器还会将从单个任务收到的数据以DATA数据包的形式转发到其标准输出。 | | DONE | 当调度器在标准输入上收到DONE数据包时，它会设置tasks数组中相应任务的endinput成员，并关闭该任务的writefd文件描述符。调度器会丢弃后续到达的针对该任务的DONE或DATA数据包。 | | BROADCAST | 调度器将来自标准输入的任何BROADCAST数据包转发到指定计算中的所有任务。如果任务向调度器发送BROADCAST数据包，调度器会将请求转发到同一计算中的所有任务，并将请求转发到其标准输出。 | | TERMINATE | 如果调度器在其标准输入上收到TERMINATE数据包，它会杀死由数据包的计算ID和任务ID标识的任务。如果任务ID为 -1，调度器会杀死指定计算中的所有任务。调度器以类似的方式处理从readfd收到的TERMINATE数据包。如果没有任务ID与数据包匹配，或者任务ID为 -1，调度器还会将TERMINATE数据包写入标准输出。 | | BARRIER | BARRIER数据包用于在计算中的任务执行的特定点同步任务。 | NTPVM项目由以下几个部分组成： 1. **Part I**：I/O设置和测试 2. **Part II**：无输入的单个任务（处理NEWTASK和输出数据） 3. **Part III**：一次处理一个任务（处理NEWTASK、DATA和DONE数据包） 4. **Part IV**：多个任务和计算（处理NEWTASK、DATA和DONE数据包） 5. **Part V**：任务同步（处理BROADCAST和BARRIER数据包） 6. **Part VI**：清理（处理TERMINATION数据包和信号） 7. **Part VII**：有序消息传递 在项目的前四个部分，子任务不使用数据包进行通信，调度器在写入writefd之前会剥离数据包头部，这种格式允许调度器将普通的UNIX实用程序（如cat或ls）作为任务运行。从第五部分开始，任务使用数据包与调度器进行通信，此时项目需要特定的任务程序进行NTPVM测试。 以下是不同类型数据包和调度器处理方法的示例： - **NEWTASK数据包**：调度器等待来自标准输入的NEWTASK数据包，该数据包包含计算ID、任务ID和命令行字符串。例如，以下NEWTASK数据包请求创建计算3中的任务2来执行ls -l命令： ```plaintext Computation ID: 3 Task ID: 2 Packet Type: NEWTASK Packet Data Length: 5 Packet Information: ls -l ``` 调度器会将数据包中的数据转换为以空字符结尾的字符串，然后请求tasks数组查找一个空闲条目，并存储有关新任务的信息。如果检测到具有相同计算和任务ID的任务已经存在于tasks数组中，调度器会丢弃该数据包并报告错误。新条目的sentpackets、sentbytes、recvpackets、recvbytes和endinput成员设置为0，barrier成员设置为 -1，表示任务不在屏障处等待。调度器创建两个管道，并使用其中两个管道文件描述符与子任务进行通信，将这些描述符存储在tasks数组条目的readfd和writefd成员中。调度器派生一个子进程，并将子进程的进程ID存储在tasks条目的taskpid成员中。调度器关闭未使用的管道文件描述符，然后等待来自标准输入或任务的readfd描述符的I/O。子任务将其标准输入和输出重定向到管道，并关闭未使用的文件描述符，然后调用execvp执行命令字符串。 - **DATA数据包**：当调度器从标准输入读取DATA数据包时，它会询问tasks对象，以确定数据包的任务ID和计算ID是否与tasks数组中的任何条目匹配。如果没有匹配的条目，调度器会丢弃该数据包；否则，它会更新任务在tasks数组条目中的recvpackets和recvbytes成员。在项目的前四个部分，任务是接受ASCII输入的标准UNIX实用程序，调度器将数据包的信息部分转发到任务的writefd描述符。从第17.8节开始，每个任务以数据包格式读写数据，调度器将DATA数据包复制到其标准输出。例如，以下DATA数据包请求将数据“This is my data”发送到计算3中的任务2： ```plaintext Computation ID: 3 Task ID: 2 Packet Type: DATA Packet Data Length: 15 Packet Data: This is my data ``` - **DONE数据包**：当调度器在标准输入上收到DONE数据包时，它会设置tasks数组中相应任务的endinput成员，并关闭该任务的writefd描述符。例如，以下DONE数据包指定计算3中的任务2不再有输入数据： ```plaintext Computation ID: 3 Task ID: 2 Packet Type: DONE Packet Data Length: 0 Packet Data: ``` 当调度器在任务的readfd描述符上检测到文件结束指示时，它会关闭该描述符，并在标准输出上发送一个DONE数据包，表示任务已完成。如果任务的writefd描述符仍然打开，调度器会关闭它。调度器最终必须对该子任务进程调用wait，并将tasks数组条目的compid成员设置为 -1，以便该数组条目可以被重用。如果调度器在其自己的标准输入上收到文件结束指示，它会关闭所有活动任务的writefd描述符，并将每个活动任务在tasks数组条目的endinput成员设置为1。当它在所有活动任务的readfd描述符上收到文件结束指示时，调度器会等待每个任务，然后退出。调度器还应定期等待所有已完成的子任务。 #### 3. 调度器的I/O和测试 调度器通过调用getpacket从标准输入接收输入数据，并通过调用putpacket向标准输出发送输出数据。数据总是分两部分传输：首先，调度器读取或写入taskpacket_t类型的头部；然后，它使用头部中的长度成员来确定要读取或写入的数据包数据的字节数；最后，它读取或写入数据包的数据部分。假设数据包数据字段包含不超过MAX_PAC