杭电操作系统实验基于DOS的多任务系统的实现.doc

操作系统课程设计报告小组编号： 小组成员：一、课程设计概述1、 题目：基于DOS的多任务系统的实现2、 实现内容（1）用C语言完成线程的创建和撤消，并按先来先服务方式对多个线程进行调度。（2）将线程调度算法修改为时间片轮转算法，实现时间片轮转调度。（也可以结合优先权，实现优先权加时间片轮转算法的线程调度。）（3）改变时间片的大小，观察结果的变化。思考：为什么时间片不能太小或太大。（4）假设两个线程共用同一软件资源（如某一变量，或某一数据结构），请用记录型信号量来实现对它的互斥访问。（5）假设有两个线程共享一个可存放个整数的缓冲，其中一个线程不停地计算至的平方，并将结果放入缓冲中，另一个线程不断地从缓冲中取出结果，并将它们打印出来，请用记录型信号量实现这一生产者和消费者的同步问题。（6）实现消息缓冲通信，并与4、5中的简单通信进行比较。二、 设计思路（主要算法描述、程序流程图等）：1、程序的设计思想：该程序主要是分5大块内容：线程的创建和撤销，线程的调度，线程的同步与互斥，线程的阻塞与唤醒，利用消息缓冲队列的线程间的通信。由这五大块功能来完成的基于DOS的多任务系统的实现。在这个系统中，首先先由main函数进行一些初始化工作，然后直接创建0#线程对应于main函数，再由0#线程调用create创建1#，2#线程分别对应与函数f1(),f2()，最后将系统的中断服务程序设置为new_int8，并把控制交给1#线程，启动多个线程的并发执行。0#线程是一个比较特殊的线程，它在创建的时候没有使用create来创建，而是在系统初始化后直接创建的，因它对应的程序段为main函数中的一段，所以也直接使用整个系统的堆栈，而不再创建时为私有堆栈分配额外的空间；同样，撤销的时也不需要释放私有堆栈的空间，所以也没有over()函数而是直接撤销，从这方面来看，它是一个系统线程。此外，在启动多个线程并发执行过程后，0#线程将系统控制权转交出去，直至系统中其他进程都不具备执行条件时，它才有可能重新得到CPU，从这方面看，0#线程相当于是一个空转线程，最后，0#线程还担负着一个特别的使命：等待系统中所有其他的线程的完成，此时，它将直接撤销自己并恢复原来的时钟中断服务程序，从此终止整个多任务系统。2、 主要算法描述用C语言来描述，一个最简单的TCB的数据结构可以表示如下： /* 状态码常量定义 */ /* null0not assigned */ #define FINISHED 0 /*表示线程处于终止态或TCB是空白状态*/ #define RUNNING 1 /*表示线程处于运行态*/ #define READY 2 /*表示线程处于就绪态*/ #define BLOCKED 3 /*表示线程处于阻塞态*/ struct TCB unsigned char *stack; /* 线程堆栈的起始地址 */ unsigned ss; /* 堆栈段址 */ unsigned sp; /* 堆栈指针 */ char state; /* 线程状态 ，取值可以是FINISHED、RUNNING、READY、BLOCKED*/ char name10; /* 线程的外部标识符 */ tcbNTCB; /*NTCB系统允许的最多任务数*/Swtch()的设计如下void interrupt swtch(void) disable(); /*关中断*/ /* 保存现行堆栈的段址和栈顶指针供下次切换时用 */ ss1=_SS; /* ss1保存线程1的堆栈段址 */ sp1=_SP; /* sp1保存线程1的堆栈栈顶指针 */ /* 切换堆栈 */ _SS=ss2; /* ss2是线程2的堆栈段址 */ _SP=sp2; /* ss2是线程2的堆栈的栈顶指针 */ enable(); /*开中断*/ /* 如果返回值是1，表示dos忙；*/ /* 如果返回值是0，表示dos不忙；*/ /* 如果返回值是-1，表示还没有调用InitDos() */ int DosBusy(void) if (indos_ptr && crit_err_ptr) return(*indos_ptr | *crit_err_ptr); else return(-1); /* InitDos() hasn't been called */ 创建线程 int create(char *name, codeptr func, int stack_len) int i; unsigned char *fp; struct int_regs *regs; for (i = 0; i < NTCB; i+) if (tcbi.state = FINISHED) /* 创建新线程 */ fp = (unsigned char *)malloc(stack_len *sizeof(unsigned char); /为新线程的私有堆栈分配内存空间 regs = (struct int_regs *)(fp + stack_len); regs-; /* 对私有堆栈进行初始化 */ regs->seg = FP_SEG(over); regs->off = FP_OFF(over); regs->flags = 0x200; regs->cs = FP_SEG(func); /* 代码段的段地址 */ regs->ip = FP_OFF(func); /* 获取代码段的段内偏移地址 */ regs->es = FP_SEG(regs); /* 附加数据段的段地址 */ regs->ds = FP_SEG(regs); /* 获取数据段的段地址 */ /* 对TCB进行初始化 */ tcbi.stack = fp; strcpy(tcbi.name, name); tcbi.ss = FP_SEG(regs); tcbi.sp = FP_OFF(regs); tcbi.state = READY;return i; return -1;/* 阻塞函数 */void block(struct TCB *qp) struct TCB *p; /* 1. 将线程的状态改成阻塞态 */ tcbcurrent.state = BLOCKED; /* 2. 将线程插入到指定的阻塞队列末尾 */ tcbcurrent.next = NULL; if (*qp) = NULL) /* 阻塞队列为空时 */ (*qp) = &tcbcurrent; else p = *qp; while (p->next != NULL) p = p->next; p->next = &tcbcurrent; /* printf("n %s is BLOCKED!n", tcbcurrent.name); */ /* 3. 重新进行CPU调度 */ my_swtch();/* 唤醒函数 */void wakeup_first(struct TCB *qp) struct TCB *tp; if (*qp) = NULL) /* 如果阻塞队列为空 */ return; /* 1. 把阻塞队列头上的第一个线程的TCB取下 */ tp = *qp; *qp = (*qp)->next; tp->next = NULL; /* 2. 将其状态改为就绪态 */ tp->state = READY; /* printf("n%s is wakeup!n", tp->name); */* 信号量P操作 */void p(semaphore *sem) struct TCB *qp; disable(); sem->value-; if (sem->value < 0) qp = &(sem->wq); block(qp); /互斥信号量小于0阻塞 enable();/* 信号量V操作 */void v(semaphore *sem) struct TCB *qp; disable(); qp = &(sem->wq); sem->value+; if (sem->value <= 0) wakeup_first(qp); enable();3、 系统的总流程图 New_int8()函数的执行过程图,如下：三、程序实现代码：#include <stdio.h>#include <stdlib.h>#include <string.h>#include <dos.h>#define GET_INDOS 0x34#define GET_CRIT_ERR 0x5d06#define FINISHED 0 /* 表示线程处于终止态或TCB是空白状态 */#define RUNNING 1 /* 表示线程处于运行态 */#define READY 2 /* 表示线程处于就绪态 */#define BLOCKED 3 /* 表示线程处于阻塞态 */#define NTCB 5 /* 表示系统允许线程的最大数 */#define NTEXT 20 /* 消息的最大字节数 */#define NBUF 5 /* 消息缓冲区的数目 */char far *indos_ptr = 0; /* INDOS标志的地址 */char far *crit_err_ptr = 0; /* 严重错误标志的地址 */int current = 0; /* 当前线程的内部标识符 */int timecount = 0; /* 从调度至今运行的时间 */int TL = 1; /* 时间片大小 */int sum;int buf5;int in, out;/* 记录型信号量 */typedef struct int value; /* 信号量的值，表示空闲资源总数 */ struct TCB *wq; /* 线程阻塞队列队首指针 */ semaphore;/* 线程控制块 */struct TCB unsigned char *stack; /* 线程堆栈的起始地址 */ unsigned ss; /* 堆栈段址 */ unsigned sp; /* 堆栈指针 */ char state; /* 线程状态，取值可以是FINISHED、RUNNING、READY、BLOCKED */ char name10; /* 线程的外部标识符 */ struct TCB *next; /* 指向下一个线程的指针 */ struct buffer *mq; /* 接收线程的消息队列队首指针 */ semaphore mutex; /* 接收线程的消息队列的互斥信号量 */ semaphore sm; /* 接收线程的消息队列的计数信号量，用于实现同步 */ tcbNTCB;/* 线程的私有堆栈，保存现场信息 */struct int_regs unsigned BP, DI, SI, DS, ES, DX, CX, BX, AX, IP, CS, Flags, off, seg;/* 消息缓冲区 */struct buffer int sender; /* 消息发送者的内部标识 */ int size; /* 消息长度<=NTEXT个字节 */ char textNTEXT; /* 消息正文 */ struct buffer *next; /* 指向下一个消息缓冲区的指针 */ *freebuf; /* 空闲消息缓冲队列 */semaphore mutexfb = 1, NULL; /* 空闲消息缓冲队列的互斥信号量 */semaphore sfb = NBUF, NULL; /* 空闲消息缓冲队列的计数信号量 */semaphore mutex = 1, NULL;semaphore empty = 5, NULL;semaphore full = 0, NULL;typedef int (far *codeptr)(); /* 定义一个函数指针类型 */void interrupt (*old_int8)(); /* 定义一个函数指针old_int8 */void initDos(); /* 初始化DOS，获得INDOS标志的地址和严重错误标志的地址 */void initTcb(); /* 初始化TCB */int DosBusy(); /* 判断当前DOS是否忙碌 */int create(char *name, codeptr code, int stackLen); /* 线程创建 */void destroy(int id); /* 线程撤销 */void over(); /* 线程自动撤销 */void interrupt new_int8(); /* 时间片到时引起的CPU调度 */void interrupt my_swtch(); /* 其他原因引起的CPU调度 */void block(struct TCB *qp); /* 插入线程到阻塞队列 */void wakeup_first(struct TCB *qp); /* 唤醒阻塞队列队首进程 */void P(semaphore *sem); /* 对信号量的P操作 */void V(semaphore *sem); /* 对信号量的V操作 */void initBuf(); /* 初始化消息缓冲区 */struct buffer *getbuf(); /* 获取消息空闲缓冲区 */void putbuf(struct buffer *buff); /* 插入空闲消息缓冲队列 */void insert(struct buffer *mq, struct buffer *buff); /* 插入消息缓冲区到消息队列 */struct buffer *remov(struct buffer *mq, int sender); /* 获取消息缓冲区 */void send(char *receiver, char *a, int size); /* 发送原语 */int receive(char *sender, char *b); /* 接收原语 int find(); / 寻找READY状态线程的内部标识符 */void tcb_state(); /* 线程状态信息 */int finished(); /* 检查除0#线程外的所有其他线程是否都已运行 */* 初始化DOS，获得INDOS标志的地址和严重错误标志的地址 */void initDos() union REGS regs; struct SREGS segregs; /* 获得 INDOS 标志的地址 */ regs.h.ah = GET_INDOS; intdosx(&regs, &regs, &segregs); /* intdosx()：Turbo C的库函数，其功能是调用DOS的INT21H中断 */ indos_ptr = MK_FP(segregs.es, regs.x.bx); /* MK_FP()：不是一个函数，只是一个宏。其功能是做段基址加上偏移地址的运算，也就是取实际地址。 */ /* 获得严重错误标志的地址，代码中用到的_osmajor、_osminor是Turbo C的全程变量，其中前者为DOS版本号的主要部分，后者为版本号的次要部分。 */ if (_osmajor < 3) crit_err_ptr = indos_ptr + 1; /* 严重错误在INDOS后一字节处 */ else if (_osmajor = 3 && _osminor = 0) crit_err_ptr = indos_ptr - 1; /* 严重错误在INDOS前一字节处 */ else regs.x.ax = GET_CRIT_ERR; intdosx(&regs, &regs, &segregs); crit_err_ptr = MK_FP(segregs.ds, regs.x.si); /* 初始化TCB */void initTcb() int id; for (id = 0; id < NTCB; id+) tcbid.stack = NULL; tcbid.state = FINISHED; tcbid.name0 = '0' tcbid.next = NULL; tcbid.mq = NULL; tcbid.mutex.value = 1; tcbid.mutex.wq = NULL; tcbid.sm.value = 0; tcbid.sm.wq = NULL; /* 判断当前DOS是否忙碌 */int DosBusy() if (indos_ptr && crit_err_ptr) return (*indos_ptr | *crit_err_ptr); /* 返回值是1，表示dos忙；返回值是0，表示dos不忙 */ else return -1; /* 还没有调用initDos() */* 线程创建 */int create(char *name, codeptr code, int stackLen) int id; struct int_regs far *regs; disable(); /* 关中断 */ for (id = 1; id < NTCB; id+) /* 寻找空的TCB */ if (tcbid.state = FINISHED) break; if (id = NTCB) /* 没找到空的TCB */ printf("n * xian cheng %s chuang jian shi bai *n", name); return -1; /* 初始化TCB */ tcbid.stack = (unsigned char *)malloc(stackLen); regs = (struct int_regs far *)(tcbid.stack + stackLen); regs-; tcbid.ss = FP_SEG(regs); tcbid.sp = FP_OFF(regs); tcbid.state = READY; strcpy(tcbid.name, name); /* 初始化私有堆栈 */ regs->DS = _DS; regs->ES = _ES; regs->IP = FP_OFF(code); regs->CS = FP_SEG(code); regs->Flags = 0x200; regs->off = FP_OFF(over); regs->seg = FP_SEG(over); printf("n * xian cheng%d %s yi chuang jian *n", id, tcbid.name); enable(); /* 开中断 */ return id;/* 线程撤销 */void destroy(int id) disable(); /* 关中断 */ /* 释放私有堆栈空间，清空TCB信息 */ free(tcbid.stack); tcbid.stack = NULL; tcbid.state = FINISHED; tcbid.name0 = '0' tcbid.next = NULL; tcbid.mq = NULL; tcbid.mutex.value = 1; tcbid.mutex.wq = NULL; tcbid.sm.value = 0; tcbid.sm.wq = NULL; printf("n * xian cheng%d %s yi che xiao *n", id, tcbid.name); enable(); /* 开中断 */* 用于自动撤销线程 */void over() destroy(current); /* 撤销当前线程 */ my_swtch(); /* CPU调度 */* 时间片到时引起的CPU调度 */void interrupt new_int8() (*old_int8)(); /* 调用原来的时钟中断服务程序 */ timecount+; /* 计时 */ if (timecount < TL | DosBusy() /* 时间片未到或DOS正忙 */ return; my_swtch(); /* 调用my_swtch()进行重新调度 */* 其他原因引起的CPU调度 */void interrupt my_swtch() int id; disable(); /* 关中断 */ /* 保存现行堆栈的段址和栈顶供下次切换时用 */ tcbcurrent.ss = _SS; tcbcurrent.sp = _SP; if (tcbcurrent.state = RUNNING) tcbcurrent.state = READY; id = find(); if (id < 0) id = 0; /* 切换堆栈 */ _SS = tcbid.ss; _SP = tcbid.sp; tcbid.state = RUNNING; current = id; timecount = 0; /* 重新开始计时 */ enable(); /* 开中断 */* 插入线程到阻塞队列 */void block(struct TCB *qp) struct TCB *tcbp; tcbcurrent.state = BLOCKED; if (*qp) = NULL) /* 若阻塞队列为空，队首指向当前线程 */ (*qp) = &tcbcurrent; else /* 否则插入队尾 */ tcbp = (*qp); while (tcbp->next != NULL) tcbp = tcbp->next; tcbp->next = &tcbcurrent; tcbcurrent.next = NULL; my_swtch(); /* CPU调度 */* 唤醒阻塞队列队首进程 */void wakeup_first(struct TCB *qp) struct TCB *tcbp; if (*qp) = NULL) return; tcbp = (*qp); (*qp ) = (*qp)->next; /* 阻塞队列队首指向下一个线程 */ tcbp->state = READY; tcbp->next = NULL;/* 对信号量的P操作 */void P(semaphore *sem) struct TCB *qp; disable(); /* 关中断 */ sem->value-; /* 空闲资源数减1 */ if (sem->value < 0) /* 没有空闲资源 */ qp = &(sem->wq); block(qp); /* 插入线程到阻塞队列 */ enable(); /* 开中断 */* 对信号量的V操作 */void V(semaphore *sem) struct TCB *qp; disable(); /* 关中断 */ sem->value+; /* 空闲资源数加1 */ if (sem->value <= 0) /* 阻塞队列中有进程 */ qp = &(sem->wq); wakeup_first(qp); /* 唤醒阻塞队列队首进程 */ enable(); /* 开中断 */* 初始化消息缓冲区 */void initBuf() struct buffer *bufp, *buff; int i; buff = (struct buffer *)malloc(sizeof(struct buffer); buff->sender = -1; buff->size = 0; buff->text0 = '0' freebuf = bufp = buff; for (i = 1; i < NBUF; i+) buff = (struct buffer *)malloc(sizeof(struct buffer); buff->sender = -1; buff->size = 0; buff->text0 = '0' bufp->next = buff; bufp = buff; bufp->next = NULL;/* 获取空闲消息缓冲区 */struct buffer *getbuf() struct buffer *buff; buff = freebuf; freebuf = freebuf->next; /* 空闲消息缓冲队列队首指针指向下一个空闲缓冲区 */ return buff;/* 插入空闲消息缓冲队列 */void putbuf(struct buffer *buff) struct buffer *bufp = freebuf; if (freebuf = NULL) /* 若空闲消息队列为空，队首指向当前消息缓冲区 */ freebuf = buff; else /* 否则插入队尾 */ while (bufp->next != NULL) bufp = bufp->next; bufp->next = buff; buff->next = NULL;/* 插入消息缓冲区到消息队列 */void insert(struct buffer *mq, struct buffer *buff) struct buffer *bufp; if (buff = NULL) return; if (*mq) = NULL) /* 若消息队列为空，队首即为当前消息缓冲区 */ (*mq) = buff; else /* 否则插入队尾 */ bufp = (*mq); while (bufp->next != NULL) bufp = bufp->next; bufp->next = buff; buff->next = NULL;/* 从消息队列获取消息缓冲区 */struct buffer *remov(struct buffer *mq, int sender) struct buffer *bufp, *buff; bufp = (*mq); /* 若消息队列队首是sender发送的消息，则取出该消息缓冲区 */ if (bufp->sender = sender) buff = bufp; (*mq) = buff->next; buff->next = NULL; return buff; /* 寻找发送者为sender的消息缓冲区 */ while (bufp->next != NULL && bufp->next->sender != sender) bufp = bufp->next; /* 若找不到，则返回NULL */ if (bufp->next = NULL) return NULL; buff = bufp->next; bufp->next = buff->next; buff->next = NULL; return buff;/* 发送原语 */void send(char *receiver, char *a, int size) struct buffer *buff; int i, id; disable(); /* 关中断 */ /* 寻找接受者线程 */ for (id = 0; id < NTCB; id+) if (!strcmp(receiver, tcbid.name) break; if (id = NTCB) /* 如果接收者线程不存在，则不发送，立即返回 */ enable(); /* 开中断 */ return; /* 获取空闲消息缓冲区 */ P(&sfb); P(&mutexfb); buff = getbuf(); V(&mutexfb); buff->sender = current; buff->size = si