杭电操作系统实验-基于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() hasnt been called */ 创建线程 int create(char *name, codeptr func, int stack_len) int i; unsigned char *fp; struct int_regs *regs; for (i = 0; i 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(, 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, ); */ /* 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 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 #include #include #include #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(®s, ®s, &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(®s, ®s, &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; 0 = 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 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, ); enable(); /* 开中断 */ return id;/* 线程撤销 */void destroy(int id) disable(); /* 关中断 */ /* 释放私有堆栈空间，清空tcb信息 */ free(tcbid.stack); tcbid.stack = null; tcbid.state = finished; 0 = 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, ); 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 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 wq); block(qp); /* 插入线程到阻塞队列 */ enable(); /* 开中断 */* 对信号量的v操作 */void v(semaphore *sem) struct tcb *qp; disable(); /* 关中断 */ sem-value+; /* 空闲资源数加1 */ if (sem-value 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 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 sender = current; buff-size = size; for (i = 0; i size; i+, a+) buff-texti = *a; /* 将消息缓冲区插入到接收者线程的消息队列末尾 */ p(&tcbid.mutex); insert(&(tcbid.mq), buff); v(&tcbid.mutex); v(&tcbid.sm); enable(); /* 开中断 */* 接收原语 */int receive(char *sender, char *b) struct buffer *buff; int i, id, size; disable(); /* 关中断 */ /* 寻找发送者线程 */ for (id = 0; id size; for (i = 0; i size; i+, b+) *b = buff-texti; buff-sender = -1; buff-size = 0; buff-text0 = 0; /* 插入空闲消息缓冲队列 */ p(&mutexfb); putbuf(buff); v(&mutexfb); v(&sfb); enable(); /* 开中断 */ return size;/* 寻找ready状态线程的内部标识符 */int find() int id; for (id = current + 1; id ntcb; id+) if (tcbid.state = ready) return id; for (id = 0; id current; id+) if (tcbid.state = ready) return id; return -1;/* 线程状态信息 */void tcb_state() int id; printf(n * dang qian xian cheng zhuang tai *n); for (id = 0; id ntcb; id+) printf(xian cheng%d %9s zhuang tai wei , id, ); switch (tcbid.state) case finished: puts(finished); break; case running: puts(running); break; case ready: puts(ready); break; case blocked: puts(blocked); break; /* 检查除0#线程外的所有其他线程是否都已运行完 */int finished() int id; for (id = 1; id ntcb; id+) if (tcbid.state != finished) return 0; return 1;/* 不断输出a，共50个 */void f1() int i, j, k; for (i = 0; i 50; i+) putchar(a); /* 延时 */ for (j = 0; j 1000; j+) for (k = 0; k 1000; k+); /* 不断输出b，共50个 */void f2() long i, j, k; for (i = 0; i 30; i+) putchar(b); /* 延时 */ for (j = 0; j 1000; j+) for (k = 0; k 1000; k+); /* 不断对sum加1，共50次，与f4互斥 */void f3() int i; int tmp; for (i = 0; i 50; i+) p(&mutex); tmp = sum; delay(5); /* 暂停5毫秒 */ tmp+; sum = tmp; printf(%d, sum); v(&mutex); /* 不断对sum加1，共50次，与f3互斥 */void f4() int i; int tmp; for (i = 0; i