多任务系统课程设计杭电

1、操作系统课程设计报告小组编号： 小组成员： 一、课程设计概述：1、题目：基于DOS的多任务系统的实现2、实现内容：（1）设计目的： 通过对线程（和进程）的创建和撤销，CPU的调度，同步机制，通信机制的实现，以达到以下目的： a. 加深对线程和进程概念的理解，明确进程和程序的区别。b.深对CPU调度过程（现场保护，CPU的分派和现场的恢复）的理解。c.进一步认识并执行的概念，明确顺序执行和并发执行的区别。d.加深对临界资源，临界区，信号量以及同步机制的理解。e.加深对消息缓冲通信的理解。（2）内容要求：a.用C语言完成线程的创建和撤销，并按优先权加时间片轮转算法对多线程进行调度。b.改变时间片的

2、大小，观察结果的变化，c.假设两个线程共用同一软件资源（如某以变量，或者某以数据结构），请用记录型信号量来实现对它的互斥访问。d.假设有两个线程共享一个可以存放5个整数的缓冲，一线程不停地计算1至50的平方，并将结构放入缓冲中，另一个线程不断地从缓冲中取出结果，并将它们打印出来，请用记录型信号量实现这一生产者和消费者的同步问题。e.实现消息缓冲通信，并与3，4中的简单通信进行比较。二、设计思路（主要算法描述、程序流程图等）： （1）程序的设计思想以及各个功能的实现思想：该程序主要是分5大块内容：线程的创建和撤销，线程的调度，线程的同步与互斥，线程的阻塞与唤醒，利用消息缓冲队列的线程间的通信。由

3、这五大块功能来完成的基于DOS的多任务系统的实现。在这个系统中，首先先由main函数进行一些初始化工作，然后直接创建0#线程对应于main函数，再由0#线程调用create创建1#，2#线程分别对应与函数f1(),f2()，最后将系统的中断服务程序设置为new_int8，并把控制交给1#线程，启动多个线程的并发执行。0#线程是一个比较特殊的线程，它在创建的时候没有使用create来创建，而是在系统初始化后直接创建的，因它对应的程序段为main函数中的一段，所以也直接使用整个系统的堆栈，而不再创建时为私有堆栈分配额外的空间；同样，撤销的时也不需要释放私有堆栈的空间，所以也没有over()函数而是

4、直接撤销，从这方面来看，它是一个系统线程。此外，在启动多个线程并发执行过程后，0#线程将系统控制权转交出去，直至系统中其他进程都不具备执行条件时，它才有可能重新得到CPU，从这方面看，0#线程相当于是一个空转线程，最后，0#线程还担负着一个特别的使命：等待系统中所有其他的线程的完成，此时，它将直接撤销自己并恢复原来的时钟中断服务程序，从此终止整个多任务系统。a.线程的创建和撤销线程的创建过程关键就是对私有堆栈和TCB初始化的过程，其过程如下：i， 为新线程分配一空闲的线程控制块ii， 为新线程的私有堆栈分配内存空间（因为对等线程共享程序段和数据段空间，所以创建线程时不必像创建进程那样再为程序段

5、和数据段分配内存空间）iii， 初始化新线程的私有堆栈，即按CPU调度时现场信息的保存格式布置堆栈。iv， 初始化线程控制块，即填入线程的外部标识符，设置好线程私有堆栈的始址，段址和栈顶指针，将线程的状态置为就绪状态。v， 最后，返回新线程的内部标识符vi， 线程的内存映像如下：线程的撤销过程中，一个关键的地方是在初始化线程私有堆栈时 需要将over()的入口地址压入线程的私有堆栈中，这样做的好处是：当线程所对应的函数正常结束时，over()函数的入口地址将最为函数的返回地址被弹出至CS,IP寄存器，那么控制将自动转向over(),从而使对应的线程被自动撤销，并重新进行CPU调度。b.线程的调

6、度引起CPU调度原因主要是有三种情况：时间片到时，线程执行完毕或正在执行的线程因等待某种事件而不能继续执行。由这些原因，调度程序可以通过两个函数分别处理不同原因引起的调度：New_int8()函数主要是处理因时间片到时引起的调度该调度可以通过截取时钟中断（int 08）来完成；Swtch()函数主要是处理因其他原因引起的调度；New_int8()函数因为是通过截取时钟中断来实现，可以知道其是属于系统调度，由于涉及到系统调度的函数 都是需要对DOS状态进行判断，以防止出现系统数据混乱等情况的发生（从Dos的不可重入性来得出），而Swtch()函数是处理因其他原因引起的调度，所以它所涉及到的仅仅是

7、用户级的函数调度，没有涉及到系统级的函数调度，因此Swtch()函数不需要对Dos状态进行判断。对于线程的两种调度函数的过程，因其相似，给出New_int8()函数的执行过程图,如下：需要主要的是：新的时钟中断处理程序不能太长，否则系统效率将大大下降甚至使系统无法正常工作；在新的时钟中断处理程序必须调用系统原来的INT 08H，否则将影响磁盘马达的关闭和系统的计时，另外，我们还主要依赖原来的INT 08H向中断控制器发中断结束指令（EOI）;c.线程的阻塞与唤醒线程的阻塞：主要是当某一线程需要阻塞的时候，将其插入阻塞队列中，等待唤醒进程唤醒，所以其过程为：首先，将线程的状态置为阻塞态，然后将线

8、程插入指定的阻塞队列末尾，并重新进行CPU调度。线程的唤醒：主要是唤醒阻塞队列里面的线程，所以其过程是：把阻塞队列头上的第一个线程的TCB取下来，并将其状态改为就绪状态，等待CPU调度.d.线程的同步与互斥在这个系统中是采用记录型信号量机制来实现同步与互斥的，实现的方法：采用P ,V操作，设置两个信号量：一个为互斥信号量，一个为临界资源数目；e.利用消息缓冲队列的线程间通信线程间的通信，关键采用send()与receive()来实现，通过发送一个文本信息来显示通信的过程，其过程为：send()函数：消息的发送者需要提供接收者的标识符，消息的长度以及消息正文的起始地址等信息，然后在发送原语里申请

9、一空闲的消息缓冲区，用相应的信息来装配该消息缓冲区，并把它插入到接收者的消息队列中去。Receive()函数：消息的接受者必须给出发送者的标识符，接受区的起始地址等信息，然后从自己的消息队列中取得相应的发送者发送来的消息缓冲区，将消息正文复制到接受区中，并释放相应的消息缓冲区。（2）程序的流程图：三、程序实现代码：#include <alloc.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <dos.h> #define FINISHED

10、0 #define RUNNING 1 #define READY 2 #define BLOCKED 3 #define NTCB 10 #define NTEXT 20 #define NBUF 5 #define NSTACK 1024 #define GET_INDOS 0x34 #define GET_CRIT_ERR 0x5d06 char far *indos_ptr = 0; char far *crit_err_ptr = 0; int timecount = 0; int TL; int current = -1; int n = 0; typedef int (far *

11、codeptr)(void); void interrupt(*old_int8)(void); /* 记录型信号量 */ typedef struct int value; struct TCB *wq; semaphore; semaphore mutex = 1, NULL; semaphore mutexfb = 1, NULL; semaphore sfb = NBUF, NULL; semaphore empty = NBUF, NULL; semaphore full = 0, NULL; /* 消息缓冲区 */ struct buffer int id; int size; c

12、har textNTEXT; struct buffer *next; bufNBUF, *freebuf; struct TCB unsigned char *stack; unsigned ss; unsigned sp; char state; char nameNTEXT; struct buffer *mq; semaphore mutex; semaphore sm; struct TCB *next; tcbNTCB; struct int_regs unsigned bp, di, si, ds, es, dx, cx, bx, ax, ip, cs, flags, off,

13、seg; ; int intbufNBUF, buftemp; int in = 0, out = 0; void over(); void destroy(int id); void wait(semaphore *sem); void signal(semaphore *sem); void block(struct TCB *qp); void wakeupFirst(struct TCB *qp); void send(char *receiver, char *a, int size); int receive(char *sender, char *b); void InitDos

14、(void) union REGS regs; struct SREGS segregs; regs.h.ah = GET_INDOS; intdosx(&regs, &regs, &segregs); indos_ptr = MK_FP(segregs.es, regs.x.bx); if(_osmajor < 3) crit_err_ptr = indos_ptr + 1; else if(_osmajor = 3 && _osminor = 0) crit_err_ptr = indos_ptr - 1; else regs.x.ax = G

15、ET_CRIT_ERR; intdosx(&regs, &regs, &segregs); crit_err_ptr = MK_FP(segregs.ds, regs.x.si); /* DosBusy(): 函数功能是获得Indos标志及严重错误标志的值，判断是否dos忙； */ /* 如果返回值是1，表示dos忙； */ /* 如果返回值是0，表示dos不忙； */ /* 如果返回值是-1，表示还没有调用InitDos() */ int DosBusy(void) if(indos_ptr && crit_err_ptr) return (*indo

16、s_ptr | *crit_err_ptr); else return -1; /* InitDos() hasn't been called */ /* 初始化tcb */ void initTCB() int i; for(i = 0; i < NTCB; i+) 0 = '0' tcbi.stack = NULL; tcbi.state = FINISHED; tcbi.mq = NULL; tcbi.mutex.value = 1; tcbi.mutex.wq = NULL; tcbi.sm.value = 0; tcbi.sm.wq =

17、 NULL; tcbi.next = NULL; void f1(void) long i,j,k; for(i=0;i<10;i+) putchar('a'); for(j=0;j<1000;j+) for(k=0;k<100;k+); void f2(void) long i,j,k; for(i=0;i<8;i+) putchar('b'); for(j=0;j<1000;j+) for(k=0;k<100;k+); void f3(void) long i,j,k; for(i=0;i<6;i+) putchar

18、('c'); for(j=0;j<1000;j+) for(k=0;k<100;k+); void f4() int i; for(i = 0; i < 10; i+) wait(&mutex); n+; printf(" %d", n); signal(&mutex); sleep(1); void f5() int i; for(i = 0; i < 5; i+) wait(&mutex); n-; printf(" %d ", n); signal(&mutex); sleep

19、(1); void prdc() int tmp, i; for(i = 1; i <= 10; i+) tmp = i ; printf("prdc %dn", tmp); wait(&empty); wait(&mutex); intbufin = tmp; in = (in + 1) % NBUF; /*printf("in: %dn", in);*/ signal(&mutex); signal(&full); void cnsm() int tmp, i; for(i = 1; i <= 10; i+

20、) wait(&full); wait(&mutex); tmp = intbufout; out = (out + 1) % NBUF; /*printf("out: %dn", out);*/ signal(&mutex); signal(&empty); printf("Out %d: %dn", i, tmp); sleep(2); void sender(void) int i,j; char a10; loop: for(i=0;i<10;i+) strcpy(a,"message")

21、; a7='0'+n; a8=0; send("receiver",a,strlen(a); printf("sender:Message "%s" has been sentn",a); n+; receive("receiver",a); if (strcmp(a,"ok")!=0) printf("Not be committed,Message should be resended!n");/*接收进程没确认,需重新发送消息*/ goto loop;

22、else printf("Committed,Communication is finished!n");/*发送者得到接收者的确认,通信结束*/ void receiver(void) int i,j,size; char b10; for(i=0;i<10;i+) b0=0; while(size=receive("sender",b)=-1); printf("receiver: Message is received-"); for(j=0;j<size;j+) putchar(bj); printf("

23、n"); strcpy(b,"ok"); send("sender",b,3);/* 发送确认消息 */ int create(char *name, codeptr code, int stck) struct int_regs far *r; int i, id = -1; for(i = 0; i < NTCB; i+) if(tcbi.state = FINISHED) id = i; break; if(id = -1) return -1; disable(); tcbid.stack = (unsigned char *)m

24、alloc(stck); r = (struct int_regs *)(tcbid.stack + stck); r-; tcbid.ss=FP_SEG(r); tcbid.sp=FP_OFF(r); r->cs = FP_SEG(code); r->ip = FP_OFF(code); r->es = _DS; r->ds = _DS; r->flags = 0x200; r->seg = FP_SEG(over); r->off = FP_OFF(over); tcbid.state = READY; strcpy(, nam

25、e); enable(); void interrupt swtch() int loop = 0; disable(); tcbcurrent.ss = _SS; tcbcurrent.sp = _SP; if(tcbcurrent.state = RUNNING) tcbcurrent.state = READY; while(tcb+current.state != READY && loop+ < NTCB - 1) if(current = NTCB) current = 0; if(tcbcurrent.state != READY) current = 0;

26、 _SS = tcbcurrent.ss; _SP = tcbcurrent.sp; tcbcurrent.state = RUNNING; timecount = 0; enable(); void destroy(int id) disable(); free(tcbid.stack); tcbid.stack = NULL; tcbid.state = FINISHED; printf("nProcess %s terminatedn", ); 0 = '0' enable(); void over() dest

27、roy(current); swtch(); int finished() int i; for(i = 1; i < NTCB; i+) if(tcbi.state != FINISHED) return 0; return 1; void free_all(void) int i; for(i=NTCB;i>=0;i-) if(tcbi.stack) 0='0' tcbi.state=FINISHED; free(tcbi.stack); tcbi.stack=NULL; void interrupt new_int8() (*old_int8

28、)(); timecount+; if(timecount < TL) return ; if(DosBusy() return ; swtch(); void wait(semaphore *sem) struct TCB *qp; disable(); sem->value-; if(sem->value < 0) qp = &(sem->wq); block(qp); enable(); void signal(semaphore *sem) struct TCB *qp; disable(); qp = &(sem->wq); sem

29、->value+; if(sem->value <= 0) wakeupFirst(qp); enable(); void block(struct TCB *qp) int id; struct TCB *tcbtmp; id = current; tcbid.state = BLOCKED; if(*qp) = NULL) (*qp) = &tcbid; else tcbtmp = *qp; while(tcbtmp->next != NULL) tcbtmp = tcbtmp->next; tcbtmp->next = &tcbid;

30、tcbid.next = NULL; swtch(); void wakeupFirst(struct TCB *qp) struct TCB *tcbtmp; if(*qp) = NULL) return ; tcbtmp = *qp; *qp = (*qp)->next; tcbtmp->state = READY; tcbtmp->next = NULL; void initBuf() int i; for(i = 0; i < NBUF - 1; i+) bufi.next = &bufi+1; bufi.next = NULL; freebuf = &

31、amp;buf0; struct buffer *getbuf() struct buffer *buff; buff = freebuf; freebuf = freebuf->next; return buff; void insert(struct buffer *mq, struct buffer *buff) struct buffer *temp; if(buff = NULL) return ; buff->next = NULL; if(*mq = NULL) *mq = buff; else temp = *mq; while(temp->next != N

32、ULL) temp = temp->next; temp->next = buff; void send(char *receiver, char *a, int size) struct buffer *buff; int i, id = -1; disable(); for(i = 0; i < NTCB; i+) if(strcmp(receiver, ) = 0) id = i; break; if(id = -1) printf("Error: Receiver not exist.n"); enable(); return ;

33、 wait(&sfb); wait(&mutexfb); buff = getbuf(); signal(&mutexfb); buff->id = current; buff->size = size; buff->next = NULL; strcpy(buff->text, a); wait(&tcbid.mutex); insert(&tcbid.mq, buff); signal(&tcbid.mutex); signal(&tcbid.sm); enable(); struct buffer *remo

34、v(struct buffer *mq, int sender) struct buffer *buff, *p, *q; q = NULL; p = *mq; while(p->next != NULL) && (p->id != sender) q = p; p = p->next; if(p->id = sender) buff = p; if(q = NULL) *mq = buff->next; else q->next = buff->next; buff->next = NULL; return buff; else

35、 return NULL; int receive(char *sender, char *b) int i, id = -1; struct buffer *buff; disable(); for(i = 0; i < NBUF; i+) if(strcmp(sender, ) = 0) id = i; break; if(id = -1) enable(); return -1; wait(&tcbcurrent.sm); wait(&tcbcurrent.mutex); buff = remov(&(tcbcurrent.mq), id)

36、; signal(&tcbcurrent.mutex); if(buff = NULL) signal(&tcbcurrent.sm); enable(); return -1; strcpy(b, buff->text); wait(&mutexfb); insert(&freebuf, buff); signal(&mutexfb); signal(&sfb); enable(); return buff->size; void main() int select = -1; InitDos(); initTCB(); old_i

37、nt8 = getvect(8); strcpy(, "main"); tcb0.state = RUNNING; current = 0; while(select != 0) do clrscr(); printf("0. Exitn"); printf("1. First come first serven"); printf("2. Time slicen"); printf("3. Change TL, see what would changen"); printf

38、("4. Exclusively assessn"); printf("5. Producer and consumer problemn"); printf("6. Message buffer communicationn"); scanf("%d", &select); while(select < 0 | select > 7); switch(select) case 1: create("f1", (codeptr)f1, NSTACK); create(&quo

39、t;f2", (codeptr)f2, NSTACK); clrscr(); printf("ncreate f1 and f2n"); printf("f1 prints 10 an"); printf("f2 prints 8 bn"); swtch(); getch(); break; case 2: TL = 1; printf("Time slice = 1nn"); getch(); create("f1", (codeptr)f1, NSTACK); create(&qu

40、ot;f2", (codeptr)f2, NSTACK); create("f3", (codeptr)f3, NSTACK); clrscr(); printf("ncreate f1, f2, f3n"); printf("f1 prints 10 an"); printf("f2 prints 8 bn"); printf("f3 prints 6 cn"); setvect(8, new_int8); swtch(); getch(); break; case 3: print

41、f("Enter new time slice: "); scanf("%d", &TL); printf("Time slice = %dnn", TL); getch(); create("f1", (codeptr)f1, NSTACK); create("f2", (codeptr)f2, NSTACK); create("f3", (codeptr)f3, NSTACK); clrscr(); printf("ncreate f1, f2, f3n"); printf("f1 prints 10 an"); printf("f2 prints 8 bn