杭電操作系統(tǒng)實驗基于DOS的多任務系統(tǒng)的實現(xiàn)

1、操作系統(tǒng)課程設計報告小組編號： 小組成員：一、課程設計概述1、 題目：基于dos的多任務系統(tǒng)的實現(xiàn)2、 實現(xiàn)內(nèi)容（1）用c語言完成線程的創(chuàng)建和撤消，并按先來先服務方式對多個線程進行調(diào)度。（2）將線程調(diào)度算法修改為時間片輪轉(zhuǎn)算法，實現(xiàn)時間片輪轉(zhuǎn)調(diào)度。（也可以結(jié)合優(yōu)先權(quán)，實現(xiàn)優(yōu)先權(quán)加時間片輪轉(zhuǎn)算法的線程調(diào)度。）（3）改變時間片的大小，觀察結(jié)果的變化。思考：為什么時間片不能太小或太大。（4）假設兩個線程共用同一軟件資源（如某一變量，或某一數(shù)據(jù)結(jié)構(gòu)），請用記錄型信號量來實現(xiàn)對它的互斥訪問。（5）假設有兩個線程共享一個可存放個整數(shù)的緩沖，其中一個線程不停地計算至的平方，并將結(jié)果放入緩沖中，另一個線程不斷

2、地從緩沖中取出結(jié)果，并將它們打印出來，請用記錄型信號量實現(xiàn)這一生產(chǎn)者和消費者的同步問題。（6）實現(xiàn)消息緩沖通信，并與4、5中的簡單通信進行比較。二、 設計思路（主要算法描述、程序流程圖等）：1、程序的設計思想：該程序主要是分5大塊內(nèi)容：線程的創(chuàng)建和撤銷，線程的調(diào)度，線程的同步與互斥，線程的阻塞與喚醒，利用消息緩沖隊列的線程間的通信。由這五大塊功能來完成的基于dos的多任務系統(tǒng)的實現(xiàn)。在這個系統(tǒng)中，首先先由main函數(shù)進行一些初始化工作，然后直接創(chuàng)建0#線程對應于main函數(shù)，再由0#線程調(diào)用create創(chuàng)建1#，2#線程分別對應與函數(shù)f1(),f2()，最后將系統(tǒng)的中斷服務程序設置為new_i

3、nt8，并把控制交給1#線程，啟動多個線程的并發(fā)執(zhí)行。0#線程是一個比較特殊的線程，它在創(chuàng)建的時候沒有使用create來創(chuàng)建，而是在系統(tǒng)初始化后直接創(chuàng)建的，因它對應的程序段為main函數(shù)中的一段，所以也直接使用整個系統(tǒng)的堆棧，而不再創(chuàng)建時為私有堆棧分配額外的空間；同樣，撤銷的時也不需要釋放私有堆棧的空間，所以也沒有over()函數(shù)而是直接撤銷，從這方面來看，它是一個系統(tǒng)線程。此外，在啟動多個線程并發(fā)執(zhí)行過程后，0#線程將系統(tǒng)控制權(quán)轉(zhuǎn)交出去，直至系統(tǒng)中其他進程都不具備執(zhí)行條件時，它才有可能重新得到cpu，從這方面看，0#線程相當于是一個空轉(zhuǎn)線程，最后，0#線程還擔負著一個特別的使命：等待系統(tǒng)中所

4、有其他的線程的完成，此時，它將直接撤銷自己并恢復原來的時鐘中斷服務程序，從此終止整個多任務系統(tǒng)。2、 主要算法描述用c語言來描述，一個最簡單的tcb的數(shù)據(jù)結(jié)構(gòu)可以表示如下： /* 狀態(tài)碼常量定義 */ /* null0not assigned */ #define finished 0 /*表示線程處于終止態(tài)或tcb是空白狀態(tài)*/ #define running 1 /*表示線程處于運行態(tài)*/ #define ready 2 /*表示線程處于就緒態(tài)*/ #define blocked 3 /*表示線程處于阻塞態(tài)*/ struct tcb unsigned char *stack; /* 線程堆

5、棧的起始地址 */ unsigned ss; /* 堆棧段址 */ unsigned sp; /* 堆棧指針 */ char state; /* 線程狀態(tài) ，取值可以是finished、running、ready、blocked*/ char name10; /* 線程的外部標識符 */ tcbntcb; /*ntcb系統(tǒng)允許的最多任務數(shù)*/swtch()的設計如下void interrupt swtch(void) disable(); /*關中斷*/ /* 保存現(xiàn)行堆棧的段址和棧頂指針供下次切換時用 */ ss1=_ss; /* ss1保存線程1的堆棧段址 */ sp1=_sp; /* s

6、p1保存線程1的堆棧棧頂指針 */ /* 切換堆棧 */ _ss=ss2; /* ss2是線程2的堆棧段址 */ _sp=sp2; /* ss2是線程2的堆棧的棧頂指針 */ enable(); /*開中斷*/ /* 如果返回值是1，表示dos忙；*/ /* 如果返回值是0，表示dos不忙；*/ /* 如果返回值是-1，表示還沒有調(diào)用initdos() */ int dosbusy(void) if (indos_ptr & crit_err_ptr) return(*indos_ptr | *crit_err_ptr); else return(-1); /* initdos() hasnt

7、 been called */ 創(chuàng)建線程 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); /* 獲取代碼段的段內(nèi)偏移地址 */ regs-es = fp_seg(r

8、egs); /* 附加數(shù)據(jù)段的段地址 */ regs-ds = fp_seg(regs); /* 獲取數(shù)據(jù)段的段地址 */ /* 對tcb進行初始化 */ tcbi.stack = fp; strcpy(, name); tcbi.ss = fp_seg(regs); tcbi.sp = fp_off(regs); tcbi.state = ready;return i; return -1;/* 阻塞函數(shù) */void block(struct tcb *qp) struct tcb *p; /* 1. 將線程的狀態(tài)改成阻塞態(tài) */ tcbcurrent.state = b

9、locked; /* 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調(diào)度 */ my_swtch();/* 喚醒函數(shù) */void wakeup_first(struct tcb *

10、qp) struct tcb *tp; if (*qp) = null) /* 如果阻塞隊列為空 */ return; /* 1. 把阻塞隊列頭上的第一個線程的tcb取下 */ tp = *qp; *qp = (*qp)-next; tp-next = null; /* 2. 將其狀態(tài)改為就緒態(tài) */ 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);

11、 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、 系統(tǒng)的總流程圖 new_int8()函數(shù)的執(zhí)行過程圖,如下：三、程序?qū)崿F(xiàn)代碼：#include #include #include #include #define get_indos 0x34#define get_crit_err 0x5d06#def

12、ine finished 0 /* 表示線程處于終止態(tài)或tcb是空白狀態(tài) */#define running 1 /* 表示線程處于運行態(tài) */#define ready 2 /* 表示線程處于就緒態(tài) */#define blocked 3 /* 表示線程處于阻塞態(tài) */#define ntcb 5 /* 表示系統(tǒng)允許線程的最大數(shù) */#define ntext 20 /* 消息的最大字節(jié)數(shù) */#define nbuf 5 /* 消息緩沖區(qū)的數(shù)目 */char far *indos_ptr = 0; /* indos標志的地址 */char far *crit_err_ptr = 0; /*

13、 嚴重錯誤標志的地址 */int current = 0; /* 當前線程的內(nèi)部標識符 */int timecount = 0; /* 從調(diào)度至今運行的時間 */int tl = 1; /* 時間片大小 */int sum;int buf5;int in, out;/* 記錄型信號量 */typedef struct int value; /* 信號量的值，表示空閑資源總數(shù) */ struct tcb *wq; /* 線程阻塞隊列隊首指針 */ semaphore;/* 線程控制塊 */struct tcb unsigned char *stack; /* 線程堆棧的起始地址 */ unsig

14、ned ss; /* 堆棧段址 */ unsigned sp; /* 堆棧指針 */ char state; /* 線程狀態(tài)，取值可以是finished、running、ready、blocked */ char name10; /* 線程的外部標識符 */ struct tcb *next; /* 指向下一個線程的指針 */ struct buffer *mq; /* 接收線程的消息隊列隊首指針 */ semaphore mutex; /* 接收線程的消息隊列的互斥信號量 */ semaphore sm; /* 接收線程的消息隊列的計數(shù)信號量，用于實現(xiàn)同步 */ tcbntcb;/* 線程的

15、私有堆棧，保存現(xiàn)場信息 */struct int_regs unsigned bp, di, si, ds, es, dx, cx, bx, ax, ip, cs, flags, off, seg;/* 消息緩沖區(qū) */struct buffer int sender; /* 消息發(fā)送者的內(nèi)部標識 */ int size; /* 消息長度=ntext個字節(jié) */ char textntext; /* 消息正文 */ struct buffer *next; /* 指向下一個消息緩沖區(qū)的指針 */ *freebuf; /* 空閑消息緩沖隊列 */semaphore mutexfb = 1, nu

16、ll; /* 空閑消息緩沖隊列的互斥信號量 */semaphore sfb = nbuf, null; /* 空閑消息緩沖隊列的計數(shù)信號量 */semaphore mutex = 1, null;semaphore empty = 5, null;semaphore full = 0, null;typedef int (far *codeptr)(); /* 定義一個函數(shù)指針類型 */void interrupt (*old_int8)(); /* 定義一個函數(shù)指針old_int8 */void initdos(); /* 初始化dos，獲得indos標志的地址和嚴重錯誤標志的地址 */vo

17、id inittcb(); /* 初始化tcb */int dosbusy(); /* 判斷當前dos是否忙碌 */int create(char *name, codeptr code, int stacklen); /* 線程創(chuàng)建 */void destroy(int id); /* 線程撤銷 */void over(); /* 線程自動撤銷 */void interrupt new_int8(); /* 時間片到時引起的cpu調(diào)度 */void interrupt my_swtch(); /* 其他原因引起的cpu調(diào)度 */void block(struct tcb *qp); /* 插

18、入線程到阻塞隊列 */void wakeup_first(struct tcb *qp); /* 喚醒阻塞隊列隊首進程 */void p(semaphore *sem); /* 對信號量的p操作 */void v(semaphore *sem); /* 對信號量的v操作 */void initbuf(); /* 初始化消息緩沖區(qū) */struct buffer *getbuf(); /* 獲取消息空閑緩沖區(qū) */void putbuf(struct buffer *buff); /* 插入空閑消息緩沖隊列 */void insert(struct buffer *mq, struct buff

19、er *buff); /* 插入消息緩沖區(qū)到消息隊列 */struct buffer *remov(struct buffer *mq, int sender); /* 獲取消息緩沖區(qū) */void send(char *receiver, char *a, int size); /* 發(fā)送原語 */int receive(char *sender, char *b); /* 接收原語 int find(); / 尋找ready狀態(tài)線程的內(nèi)部標識符 */void tcb_state(); /* 線程狀態(tài)信息 */int finished(); /* 檢查除0#線程外的所有其他線程是否都已運行

20、*/* 初始化dos，獲得indos標志的地址和嚴重錯誤標志的地址 */void initdos() union regs regs; struct sregs segregs; /* 獲得 indos 標志的地址 */ regs.h.ah = get_indos; intdosx(®s, ®s, &segregs); /* intdosx()：turbo c的庫函數(shù)，其功能是調(diào)用dos的int21h中斷 */ indos_ptr = mk_fp(segregs.es, regs.x.bx); /* mk_fp()：不是一個函數(shù)，只是一個宏。其功能是做段基址加上偏移地址的運算，也就

21、是取實際地址。 */ /* 獲得嚴重錯誤標志的地址，代碼中用到的_osmajor、_osminor是turbo c的全程變量，其中前者為dos版本號的主要部分，后者為版本號的次要部分。 */ if (_osmajor 3) crit_err_ptr = indos_ptr + 1; /* 嚴重錯誤在indos后一字節(jié)處 */ else if (_osmajor = 3 & _osminor = 0) crit_err_ptr = indos_ptr - 1; /* 嚴重錯誤在indos前一字節(jié)處 */ else regs.x.ax = get_crit_err; intdosx(®s,

22、®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

23、= null; /* 判斷當前dos是否忙碌 */int dosbusy() if (indos_ptr & crit_err_ptr) return (*indos_ptr | *crit_err_ptr); /* 返回值是1，表示dos忙；返回值是0，表示dos不忙 */ else return -1; /* 還沒有調(diào)用initdos() */* 線程創(chuàng)建 */int create(char *name, codeptr code, int stacklen) int id; struct int_regs far *regs; disable(); /* 關中斷 */ for (id =

24、 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(); /* 關中斷 */ /* 釋放

25、私有堆?？臻g，清空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(); /* 開中斷 */*

26、 用于自動撤銷線程 */void over() destroy(current); /* 撤銷當前線程 */ my_swtch(); /* cpu調(diào)度 */* 時間片到時引起的cpu調(diào)度 */void interrupt new_int8() (*old_int8)(); /* 調(diào)用原來的時鐘中斷服務程序 */ timecount+; /* 計時 */ if (timecount tl | dosbusy() /* 時間片未到或dos正忙 */ return; my_swtch(); /* 調(diào)用my_swtch()進行重新調(diào)度 */* 其他原因引起的cpu調(diào)度 */void interrupt

27、 my_swtch() int id; disable(); /* 關中斷 */ /* 保存現(xiàn)行堆棧的段址和棧頂供下次切換時用 */ 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調(diào)度 */* 喚醒阻塞隊列隊

28、首進程 */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-; /* 空閑資源數(shù)減1 */ if (sem-value wq); block(

29、qp); /* 插入線程到阻塞隊列 */ enable(); /* 開中斷 */* 對信號量的v操作 */void v(semaphore *sem) struct tcb *qp; disable(); /* 關中斷 */ sem-value+; /* 空閑資源數(shù)加1 */ if (sem-value wq); wakeup_first(qp); /* 喚醒阻塞隊列隊首進程 */ enable(); /* 開中斷 */* 初始化消息緩沖區(qū) */void initbuf() struct buffer *bufp, *buff; int i; buff = (struct buffer *)m

30、alloc(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;/* 獲取空閑消息緩沖區(qū) */struct buffer *getbuf() struct buffer *buff; buff = freebuf; freebuf = freebuf

31、-next; /* 空閑消息緩沖隊列隊首指針指向下一個空閑緩沖區(qū) */ return buff;/* 插入空閑消息緩沖隊列 */void putbuf(struct buffer *buff) struct buffer *bufp = freebuf; if (freebuf = null) /* 若空閑消息隊列為空，隊首指向當前消息緩沖區(qū) */ freebuf = buff; else /* 否則插入隊尾 */ while (bufp-next != null) bufp = bufp-next; bufp-next = buff; buff-next = null;/* 插入消息緩沖區(qū)到

32、消息隊列 */void insert(struct buffer *mq, struct buffer *buff) struct buffer *bufp; if (buff = null) return; if (*mq) = null) /* 若消息隊列為空，隊首即為當前消息緩沖區(qū) */ (*mq) = buff; else /* 否則插入隊尾 */ bufp = (*mq); while (bufp-next != null) bufp = bufp-next; bufp-next = buff; buff-next = null;/* 從消息隊列獲取消息緩沖區(qū) */struct bu

33、ffer *remov(struct buffer *mq, int sender) struct buffer *bufp, *buff; bufp = (*mq); /* 若消息隊列隊首是sender發(fā)送的消息，則取出該消息緩沖區(qū) */ if (bufp-sender = sender) buff = bufp; (*mq) = buff-next; buff-next = null; return buff; /* 尋找發(fā)送者為sender的消息緩沖區(qū) */ while (bufp-next != null & bufp-next-sender != sender) bufp = buf

34、p-next; /* 若找不到，則返回null */ if (bufp-next = null) return null; buff = bufp-next; bufp-next = buff-next; buff-next = null; return buff;/* 發(fā)送原語 */void send(char *receiver, char *a, int size) struct buffer *buff; int i, id; disable(); /* 關中斷 */ /* 尋找接受者線程 */ for (id = 0; id sender = current; buff-size =

35、 size; for (i = 0; i size; i+, a+) buff-texti = *a; /* 將消息緩沖區(qū)插入到接收者線程的消息隊列末尾 */ 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(); /* 關中斷 */ /* 尋找發(fā)送者線程 */ for (id =

36、 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狀態(tài)線程的內(nèi)部標識符 */int find() int id; for (id = current + 1; id ntcb; id+) if (tcbid.state

37、= ready) return id; for (id = 0; id current; id+) if (tcbid.state = ready) return id; return -1;/* 線程狀態(tài)信息 */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

38、: 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

39、 = 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