实验一 体验Nachos下的并发程序设计
一、小组成员及分工
汪于波（23020078104116）：main.cc的修改、threadtest.cc的修改和实验报告 潘羽龙（23020078104100）：dllist.cc的实现 吴道裕（23020078104132）：dllist-driver.cc的实现和实验报告的完成 谭原（23020078104111）：dllist.h的实现和Makefile.common的修改
二、实验目的
对nachos进行熟悉，并初步体验nachos下的并发程序设计。
三、实验内容
1．安装nachos；
2．用C++实现双向有序链表；
3．在nachos系统中使用你所写的链表程序并演示一些并发错误
四、实验步骤
1．首先明确Nachos各部分的关系
在~/nachos/nachos-3.4/code/下有一个Makefile.common，在code/的各个子目录下的Makefile都继承这个Makefile.common。通过阅读main.cc知道，main函数一旦启动，立即调用Initialize，进行初始化的操作，然后对相应的参数进行处理，之后在分模块进行相应模块下的函数调用，执行相应的功能。 2．编写相应的函数
实验要求利用对双向链表的操作来演示并发程序可能出现的错误，首先需要实现双向链表dllist，包括dllist.h,dllist.cc。当DLList类实现后，需要编写链表驱动函数Insert和Remove来对链表进行驱动。通过改写threadtest.cc，使得多个线程在没有进行任何互斥操作的情况下对同一数据结构进行操作，在这个过程中就可能出现并发错误。改写Makefile.common和main.cc。 3．详细设计 a)dllist.h（~/nachos/nachos-3.4/code/threads/） 类DLList的声明 class DLLElement {
public: };
class DLList { public:
DLList();//initialize the list DLList(int type);
~DLList();//de-allocate the list
DLLElement(void *itemPtr,int sortKey);//initialize a list element DLLElement *next;//next element on list DLLElement *prev;//previous element on list int key; void *item;
};
void Prepend(void *item);//add to head of list void Append(void *item);//add to tail of list
void *Remove(int *keyPtr);//remove frome head of list bool IsEmpty();//return true if list has elements void SortedInsert(void *item,int sortKey);
void *SortedRemove(int sortKey);//remove first item with key==sortKey DLLElement *first; DLLElement *last;
int yield_type;//different yield positon
private:
b) dllist.cc（~/nachos/nachos-3.4/code/threads/）
类DLList方法的实现，其中核心操作Remove，SortedInsert。
//---------------------------------------------------------------------- // DLList::Remove
// Remove the first \//
// Returns:
// Pointer to removed item, NULL if nothing on the list.
//---------------------------------------------------------------------- void *
DLList::Remove(int *keyPtr) {
DLLElement *temp; void *tempitem = NULL; if(IsEmpty()) {
keyPtr = NULL; *keyPtr = first->key; if(yield_type == 1)
currentThread->Yield(); //the 1th positon of yield ****(1) //the returned tempitem may not the item we just removed! //the item maybe incorrect tempitem = first->item; temp = first; if(first != NULL) { if(yield_type == 2)
currentThread->Yield(); //the 2th positon of yield ****(2) //the dllist may lose its item first->prev = NULL; }else last = NULL; }else {
first = first->next;
}
delete temp;
return tempitem; }
//---------------------------------------------------------------------- // DLList::SortedInsert
// Insert an \// sorted in increasing order by \
//---------------------------------------------------------------------- void
DLList::SortedInsert(void *item, int sortKey) {
DLLElement *element = new DLLElement(item, sortKey); DLLElement *ptr;
if (IsEmpty()) { // if list is empty, put first = element; if(yield_type == 3)
currentThread->Yield(); //the 3th positon of yield ****(3)
//the thread may make a mess of the dllist
last = element;
} else if (sortKey < first->key) {
// item goes on front of list element->next = first; first->prev = element; first = element;
// look for first elt in list bigger than item
// keep track
} else {
ptr = first;
while((sortKey >= ptr->key)&&(ptr->next != NULL)) }
ptr = ptr->next;
(ptr->prev)->next = element; element->prev = ptr->prev; element->next = ptr; if(yield_type == 4) if (sortKey < ptr->key) {
currentThread->Yield(); //the 4th positon of yield ****(4) //the dllist may be broken by multi-threads }
ptr->prev = element; ptr->next = element; element->prev = ptr; last = element; }else {
}
c)dllist-driver.cc （~/nachos/nachos-3.4/code/threads/）
链表驱动函数Insert，Remove
void Insert(int N,DLList *dllist,int TdNo) //Insert N items into the dllist. {
int rd;
srand(time(0)); for(int i=0;i void Remove(int N,DLList *dllist,int TdNo) //Remove N items from the dllist. { int keyword; for(int i=0;i dllist->Remove(&keyword); printf(\(key=%d)\\n\ } } rd = rand()0; dllist->SortedInsert(NULL,rd); printf(\ (key=%d)\\n\ } d)线程测试threadtest.cc （~/nachos/nachos-3.4/code/threads/） 其中我们设置了几个全局变量，testnum,threadnum,N,lb1_cor_type，dllist。 testnum：测试号，对应相应的测试函数 threadnum：线程数，通过命令行参数录入 N：用于驱动函数插入或者删除链表项的控制 lb1_cor_type：用于指示不同切换位置可能出现的错误种类，通过命令行参数修改 dllist：用于线程操作的公共链表 我们在threadtest.cc中添加了新的测试函数ThreadTest2，在其中，我们创建了threadnum个线程，每个线程都执行相同的操作，插入N个项，之后删除N个项，在这里通过调用DLListThread函数实现。同时在进行这些操作的时候打印出相应的提示信息。 void DLListThread(int n) { Insert(N,dllist,n); Remove(N,dllist,n); } void ThreadTest2() { DEBUG('t', \ dllist = new DLList(lb1_cor_type); for(int i = 1; i < threadnum; i++) { Thread *t = new Thread(\t->Fork(DLListThread, i);