多任務(wù)系統(tǒng)課程設(shè)計杭電

1、操作系統(tǒng)課程設(shè)計報告小組編號： 小組成員： 一、課程設(shè)計概述：1、題目：基于DOS的多任務(wù)系統(tǒng)的實(shí)現(xiàn)2、實(shí)現(xiàn)內(nèi)容：（1）設(shè)計目的： 通過對線程（和進(jìn)程）的創(chuàng)建和撤銷，CPU的調(diào)度，同步機(jī)制，通信機(jī)制的實(shí)現(xiàn)，以達(dá)到以下目的： a. 加深對線程和進(jìn)程概念的理解，明確進(jìn)程和程序的區(qū)別。b.深對CPU調(diào)度過程（現(xiàn)場保護(hù)，CPU的分派和現(xiàn)場的恢復(fù)）的理解。c.進(jìn)一步認(rèn)識并執(zhí)行的概念，明確順序執(zhí)行和并發(fā)執(zhí)行的區(qū)別。d.加深對臨界資源，臨界區(qū)，信號量以及同步機(jī)制的理解。e.加深對消息緩沖通信的理解。（2）內(nèi)容要求：a.用C語言完成線程的創(chuàng)建和撤銷，并按優(yōu)先權(quán)加時間片輪轉(zhuǎn)算法對多線程進(jìn)行調(diào)度。b.改變時間片的

2、大小，觀察結(jié)果的變化，c.假設(shè)兩個線程共用同一軟件資源（如某以變量，或者某以數(shù)據(jù)結(jié)構(gòu)），請用記錄型信號量來實(shí)現(xiàn)對它的互斥訪問。d.假設(shè)有兩個線程共享一個可以存放5個整數(shù)的緩沖，一線程不停地計算1至50的平方，并將結(jié)構(gòu)放入緩沖中，另一個線程不斷地從緩沖中取出結(jié)果，并將它們打印出來，請用記錄型信號量實(shí)現(xiàn)這一生產(chǎn)者和消費(fèi)者的同步問題。e.實(shí)現(xiàn)消息緩沖通信，并與3，4中的簡單通信進(jìn)行比較。二、設(shè)計思路（主要算法描述、程序流程圖等）： （1）程序的設(shè)計思想以及各個功能的實(shí)現(xiàn)思想：該程序主要是分5大塊內(nèi)容：線程的創(chuàng)建和撤銷，線程的調(diào)度，線程的同步與互斥，線程的阻塞與喚醒，利用消息緩沖隊列的線程間的通信。由

3、這五大塊功能來完成的基于DOS的多任務(wù)系統(tǒng)的實(shí)現(xiàn)。在這個系統(tǒng)中，首先先由main函數(shù)進(jìn)行一些初始化工作，然后直接創(chuàng)建0#線程對應(yīng)于main函數(shù)，再由0#線程調(diào)用create創(chuàng)建1#，2#線程分別對應(yīng)與函數(shù)f1(),f2()，最后將系統(tǒng)的中斷服務(wù)程序設(shè)置為new_int8，并把控制交給1#線程，啟動多個線程的并發(fā)執(zhí)行。0#線程是一個比較特殊的線程，它在創(chuàng)建的時候沒有使用create來創(chuàng)建，而是在系統(tǒng)初始化后直接創(chuàng)建的，因它對應(yīng)的程序段為main函數(shù)中的一段，所以也直接使用整個系統(tǒng)的堆棧，而不再創(chuàng)建時為私有堆棧分配額外的空間；同樣，撤銷的時也不需要釋放私有堆棧的空間，所以也沒有over()函數(shù)而是

4、直接撤銷，從這方面來看，它是一個系統(tǒng)線程。此外，在啟動多個線程并發(fā)執(zhí)行過程后，0#線程將系統(tǒng)控制權(quán)轉(zhuǎn)交出去，直至系統(tǒng)中其他進(jìn)程都不具備執(zhí)行條件時，它才有可能重新得到CPU，從這方面看，0#線程相當(dāng)于是一個空轉(zhuǎn)線程，最后，0#線程還擔(dān)負(fù)著一個特別的使命：等待系統(tǒng)中所有其他的線程的完成，此時，它將直接撤銷自己并恢復(fù)原來的時鐘中斷服務(wù)程序，從此終止整個多任務(wù)系統(tǒng)。a.線程的創(chuàng)建和撤銷線程的創(chuàng)建過程關(guān)鍵就是對私有堆棧和TCB初始化的過程，其過程如下：i， 為新線程分配一空閑的線程控制塊ii， 為新線程的私有堆棧分配內(nèi)存空間（因?yàn)閷Φ染€程共享程序段和數(shù)據(jù)段空間，所以創(chuàng)建線程時不必像創(chuàng)建進(jìn)程那樣再為程序段

5、和數(shù)據(jù)段分配內(nèi)存空間）iii， 初始化新線程的私有堆棧，即按CPU調(diào)度時現(xiàn)場信息的保存格式布置堆棧。iv， 初始化線程控制塊，即填入線程的外部標(biāo)識符，設(shè)置好線程私有堆棧的始址，段址和棧頂指針，將線程的狀態(tài)置為就緒狀態(tài)。v， 最后，返回新線程的內(nèi)部標(biāo)識符vi， 線程的內(nèi)存映像如下：線程的撤銷過程中，一個關(guān)鍵的地方是在初始化線程私有堆棧時 需要將over()的入口地址壓入線程的私有堆棧中，這樣做的好處是：當(dāng)線程所對應(yīng)的函數(shù)正常結(jié)束時，over()函數(shù)的入口地址將最為函數(shù)的返回地址被彈出至CS,IP寄存器，那么控制將自動轉(zhuǎn)向over(),從而使對應(yīng)的線程被自動撤銷，并重新進(jìn)行CPU調(diào)度。b.線程的調(diào)

6、度引起CPU調(diào)度原因主要是有三種情況：時間片到時，線程執(zhí)行完畢或正在執(zhí)行的線程因等待某種事件而不能繼續(xù)執(zhí)行。由這些原因，調(diào)度程序可以通過兩個函數(shù)分別處理不同原因引起的調(diào)度：New_int8()函數(shù)主要是處理因時間片到時引起的調(diào)度該調(diào)度可以通過截取時鐘中斷（int 08）來完成；Swtch()函數(shù)主要是處理因其他原因引起的調(diào)度；New_int8()函數(shù)因?yàn)槭峭ㄟ^截取時鐘中斷來實(shí)現(xiàn)，可以知道其是屬于系統(tǒng)調(diào)度，由于涉及到系統(tǒng)調(diào)度的函數(shù) 都是需要對DOS狀態(tài)進(jìn)行判斷，以防止出現(xiàn)系統(tǒng)數(shù)據(jù)混亂等情況的發(fā)生（從Dos的不可重入性來得出），而Swtch()函數(shù)是處理因其他原因引起的調(diào)度，所以它所涉及到的僅僅是

7、用戶級的函數(shù)調(diào)度，沒有涉及到系統(tǒng)級的函數(shù)調(diào)度，因此Swtch()函數(shù)不需要對Dos狀態(tài)進(jìn)行判斷。對于線程的兩種調(diào)度函數(shù)的過程，因其相似，給出New_int8()函數(shù)的執(zhí)行過程圖,如下：需要主要的是：新的時鐘中斷處理程序不能太長，否則系統(tǒng)效率將大大下降甚至使系統(tǒng)無法正常工作；在新的時鐘中斷處理程序必須調(diào)用系統(tǒng)原來的INT 08H，否則將影響磁盤馬達(dá)的關(guān)閉和系統(tǒng)的計時，另外，我們還主要依賴原來的INT 08H向中斷控制器發(fā)中斷結(jié)束指令（EOI）;c.線程的阻塞與喚醒線程的阻塞：主要是當(dāng)某一線程需要阻塞的時候，將其插入阻塞隊列中，等待喚醒進(jìn)程喚醒，所以其過程為：首先，將線程的狀態(tài)置為阻塞態(tài)，然后將線

8、程插入指定的阻塞隊列末尾，并重新進(jìn)行CPU調(diào)度。線程的喚醒：主要是喚醒阻塞隊列里面的線程，所以其過程是：把阻塞隊列頭上的第一個線程的TCB取下來，并將其狀態(tài)改為就緒狀態(tài)，等待CPU調(diào)度.d.線程的同步與互斥在這個系統(tǒng)中是采用記錄型信號量機(jī)制來實(shí)現(xiàn)同步與互斥的，實(shí)現(xiàn)的方法：采用P ,V操作，設(shè)置兩個信號量：一個為互斥信號量，一個為臨界資源數(shù)目；e.利用消息緩沖隊列的線程間通信線程間的通信，關(guān)鍵采用send()與receive()來實(shí)現(xiàn)，通過發(fā)送一個文本信息來顯示通信的過程，其過程為：send()函數(shù)：消息的發(fā)送者需要提供接收者的標(biāo)識符，消息的長度以及消息正文的起始地址等信息，然后在發(fā)送原語里申請

9、一空閑的消息緩沖區(qū)，用相應(yīng)的信息來裝配該消息緩沖區(qū)，并把它插入到接收者的消息隊列中去。Receive()函數(shù)：消息的接受者必須給出發(fā)送者的標(biāo)識符，接受區(qū)的起始地址等信息，然后從自己的消息隊列中取得相應(yīng)的發(fā)送者發(fā)送來的消息緩沖區(qū)，將消息正文復(fù)制到接受區(qū)中，并釋放相應(yīng)的消息緩沖區(qū)。（2）程序的流程圖：三、程序?qū)崿F(xiàn)代碼：#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; /* 消息緩沖區(qū) */ 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(): 函數(shù)功能是獲得Indos標(biāo)志及嚴(yán)重錯誤標(biāo)志的值，判斷是否dos忙； */ /* 如果返回值是1，表示dos忙； */ /* 如果返回值是0，表示dos不忙； */ /* 如果返回值是-1，表示還沒有調(diào)用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");/*接收進(jìn)程沒確認(rèn),需重新發(fā)送消息*/ goto loop;

22、else printf("Committed,Communication is finished!n");/*發(fā)送者得到接收者的確認(rèn),通信結(jié)束*/ 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);/* 發(fā)送確認(rèn)消息 */ 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