1、精品杭电赵伟华操作系统课程设计指导书操作系统实验和课程设计总要求 遵守机房纪律，服从机房调度。 实验与课程设计的设计和上机调试要求独立完成，不能拷贝。 上机前，努力准备上机内容，并预先作一些情况分析。 仔细观察上机时出现的各种现象，记录上机的结果。 认真书写实验和课程设计报告。报告中应包括：实验和课程设计的目的及要求、程序的设计思想及框图、程序的调试中遇到的问题的分析、程序的清单和结果分析以及程序的不足之处及修改方案。程序要带注释。 实验一 使用动态优先数的进程调度算法的模拟 一目的 通过这一实验加深对进程、进程控制块和进程调度的理解，并通过动态优先数算法加深对进程调度算法的理解。 二要求 用
2、语言来实现有（假设为）个进程的进程调度算法。 每个用来标识进程的进程控制块用结构来描述，包括以下字段： （）进程标识数id：整型（）。 （）进程优先数priority：整型（优先数越大的进程，优先权越高）。 （）进程已占用的时间cputime：整型（初值为）。 （）进程还需占用的时间alltime ：整型（进程运行完毕时变为）。 （）进程的阻塞时间startblock：整型（即当进程再运行startblock个时间片后，进程将进入阻塞状态。） （）进程被阻塞的时间blocktime：整型（即已阻塞的进程再等待blocktime个时间片后，将转换成就绪态。） （）进程状态state：整型（0-f
3、inished；1-running；2-ready ；3-blocked）。 （）队列指针next：指向结构的指针，用来将排成队列。 优先数改变的原则： （）进程在就绪队列中呆一个时间片，优先数增加。 （）进程每运行一个时间片，优先数减。 为了清楚地观察诸进程的调度过程，程序应将每个时间片内的进程的情况显示出来，参照的具体格式如下： RUNNING PROG: i READY_QUEUE: -id1-id2 BLOCK_QUEUE: -id3-1d4 = ID 0 1 2 3 4 PRIORITY P0 P1 P2 P3 P4 CPUTIME C0 C1 C2 C3 C4 ALLTIME A0
4、 A1 A2 A3 A4 STARTBLOCK T0 T1 T2 T3 T4 BLOCKTIME B0 B1 B2 B3 B4 STATE S0 S1 S2 S3 S4 三初始值 ID 0 1 2 3 4 PRIORITY 9 38 30 29 0 CPUTIME 0 0 0 0 0 ALLTIME 3 3 6 3 4 STARTBLOCK 2 -1 -1 -1 -1 BLOCKTIME 3 0 0 0 0 STATE READY READY READY READY READY 四备注 以上所有时间都以时间片为单位，并假设个进程都是在开始调度时同时到达的。 五思考 这里采用的两条优先数改变原则
5、各有什么理由？ 实验二 遍历MS_DOS系统的MCB链 一补充知识 MS_DOS控制的RAM空间分为操作系统区和暂驻程序区（TPA）。操作系统区位于RAM的底部，其中有中断向量表、 操作系统全部及其表格和缓冲区等信息；RAM 中操作系统之上的其余部分为TPA区，该区域为可动态分配的内存。 TPA中的每个内存块的大小都以节（16字节）为单位，而且必须以节为边界，故每个内存块的起始地址可以xxxx:0000来表示，其中xxxx为段地址。 TPA中的每个内存块前都有一个相应的内存控制块MCB，它占一节长，DOS 通过这些MCB来管理内存。用户可以通过DOS的系统功能调用来申请或释放其中的一块内存。M
6、CB的结构如下： 字节：标识字符，“”（5AH）表示最后一个内存块；“”（4DH）表示非最后一个内存块。 字节：内存块的所有者名，如果内存块为空闲的，则它的值为0000h，否则它的值为所有者进程的程序段前缀（PSP）的段址。 字节：它控制的内存块的大小（以节为单位）， 这一大小并不包括MCB本身占用的那一节。 字节：保留未用。 字节：在DOS4.X以上的版本中，为所有者程序的文件名。该名字仅包含在所有者程序的PSP所在的内存块前的MCB中，否则，这个字节将被忽略。 第一个MCB总是用来控制DOS自身数据段的，它的所有者名通常为0008h。 它的段址位于DOS内存变量表中偏移值为处。通过52h系
7、统功能调用，我们可以从返回的ES:BX中得到DOS内存变量表的指针，所以从ES:BX-2处就得到第一个MCB的段地址。 若一个MCB的标识字节为Z,表示它是最后一个MCB；否则若它的标识字节为M,表示它后面还有其他的MCB，本MCB的段地址加上它所控制的内存块的大小(字节3-4的内容),再加上（MCB本身所占的一节内存）， 得到的值即下一个MCB的段地址。这样，我们可以看出，所有的内存块都通过MCB按起始地址从小到大隐式地连成一个链，我们不妨称它为MCB链。 DOS的49h号系统功能调用是用来释放由MCB控制的一个内存块的： 入口：ES要释放的内存块的起始段址。 出口：C0，释放成功；C1，释
8、放失败，AX错误码。 释放时先检查要释放的内存块前一节是否为一个合法的MCB (标识字节为或Z),“”），若合法，则将该MCB的所有者名改为0000h，即它所控制的内存块为空闲块。 DOS的48h号系统功能调用是用来分配内存的： 入口：BX要求分配的内存块大小（以节为单位）。 出口：若进位位C0，分配成功，AX分配到的内存块的段址，BX分配的内存块的大小（节数）；若C1，分配失败，AX为错误玛，BX最大可用块的大小。 分配时，从MCB链头起顺序查找，每碰到一个空闲块（MCB中所有者为0000h 的块）时，先进行空闲块的合并（因为，内存释放时没进行空闲块的合并），然后判断该空闲块是否能满足要求，
9、若能满足要求则将它分配出去，否则继续查找。分配时有可能产生另一个小的空闲块。 从上可以看出，该算法与标准的首次适应算法类似，故称它为合并首次适应算法。它与标准的首次适应算法的不同之处只在于，在释放内存块时，它不进行空闲块的合并，而把空闲块的合并工作放到内存分配时来做，其余之处与标准的首次适应算法完全相同。 在DOS 3.0以上版本中， 内存分配的策略还有最佳适应法（分配满足要求的最小可用内存块）和最后适应法（从高地址到低地址分配满足要求的最高的足够大的内存块）。DOS的58H号系统功能调用是用来取或置分配策略的： 入口：置分配策略时，AH58h，AL01，BX策略码 00合并首次适应法 01最
10、佳适应法 02最后适应法。 取分配策略时，入口：AH58h，AL0。 出口：成功时，进位标志0，AX策略码（对取分配策略）； 失败时，进位标志置，AX错误码。 二目的 通过对MS_DOS的MCB链的遍历，熟悉MS_DOS的内存管理， 并进一步了解使用动态分区分配方式的内存分配和释放的过程。 三要求 用语言来显示MCB链的信息，显示的格式可参照以下格式： *seg*flag*owner* size * progname * 253* M* 8* 704( 11264)* * 514* M* 8* 4( 64)* * 519* M* 51a* 164( 2624)* COMMAND * 5be*
11、M* 0* 4( 64)* free * 5c3* M* 51a* 96( 1536)* * 624* M* 632* 12( 192)* * 631* M* 632* 4740( 75840)* MCB *18b6* Z* 0*34441(551056)* free 以上表示内存的TPA中有个内存块，其中有两个空闲块：05be:0000 开始的4节（64字节）长的内存块，18b6:0000开始的34441 节（551056 字节）长的内存块；两个被COMMAND使用的内存块：0519:0000开始的164节长及05c3:0000开始的96节长的内存块；两个被MCB程序使用的内存块：0624:
12、0000开始的12节长和0631: 0000开始的4740节长的内存块；还有两个内存块是DOS自身数据段使用的（其MCB的所有者为0008)。 用48h号系统功能调用和49h号系统功能调用来申请和释放一系列的内存块，观察申请和释放过程中MCB链的变化过程。 通过58h号系统功能调用改变分配策略，重复， 并对三种分配策略进行比较。 四提示和主要数据结构 编程时要用到文件dos.h中的内容。 在C中用intdosx()来实现DOS的系统功能调用。 MCB的数据结构如下： typedef struct unsigned char flag; unsigned owner; unsigned size
13、; unsigned char unused3; unsigned char progname8; MCB; 程序段例子 /* 取得第一个MCB的地址 */ MCB far *get_first_mcb(void) union REGS reg; struct SREGS seg; unsigned far *tempp; segread(&seg); /* 把当前段寄存器的值取到结构变量seg中 */ /* 执行52h号DOS系统功能调用 */ reg.h.ah=0x52; intdosx(®,®,&seg); /* ES:BX-2单元中有第一个MCB的段地址，将该单元的地址赋给
14、tempp */ tempp=(unsigned far *)MK_FP(seg.es,reg.x.bx-2); /* 返回第一个MCB的地址 */ return(MCB far *)MK_FP(*tempp,0); 实验三 PC_DOS磁盘空间的分配和文件的物理结构 一补充知识 PC_DOS的磁盘空间分配 PC_DOS的3.5寸双面双密度软盘每面有80个磁道，每道有18个扇区， 每个扇区有512字节；而文件所占磁盘空间以簇为单位，每簇大小为1扇区。它的盘空间分配情况如下： 绝对扇区号 长度（区） 内容 引导记录 根 目 录 用户文件区 文件目录项的内容 PC_DOS磁盘空间中从第19个绝对扇
15、区开始的14个扇区是文件的根目录区，其中每个根目录项占32个字节，一个512字节的扇区刚好放16个根目录项， 所以根目录区中最多可建立224个根目录项（即根目录下最多只能有224个子目录）。而子目录是作为文件处理的，它的目录项不占根目录区，而只作为文件的内容存放在用户文件区中，所以它的目录项个数（即子目录下的文件个数）仅受磁盘空间的限制。 目录项的格式如下： 0 7 8 A B C F 文 件 名 类型名属性 未 用 未 用 时间日期簇 号 文件长度 10 15 16 17 18 19 1A 1B 1C 1F 文件名：占8个字节，包含一个已建立文件的文件名。若名字的长度小于8个字符，则右边用空
16、白填充。其中，第一个字节表示目录项的状态： 00h从未用过的目录项。 E5h已删除文件的目录项。 2Eh子目录标记项。 其它文件名的首字符。 类型名：即文件的扩展名，占3个字节。 属性：占一个字节，其含义为： 7 6 5 4 3 2 1 0 更改位子目录卷标位系 统隐 含只 读 其中，隐含、系统和子目录文件不能用一般的目录操作检索；只读文件只能读不能写；卷标位为表示该目录项记录着这张盘的卷名；更改位在文件修改后置。 时间和日期：记录文件建立或修改的时间和日期。 簇号：分配给该文件的磁盘空间的第一簇的簇号。 文件长度：以字节为单位的文件的长度。 文件的物理结构与空闲盘区的管理 PC_DOS文件存
17、储空间的管理以簇为单位，簇的大小由盘的类型决定，对于3. 5存软盘，簇的大小是512字节（即1个扇区）。 PC_DOS文件的物理结构是显式链接结构，分配给一文件的第一盘簇的簇号登记在它的目录项中，而分配给该文件的所有其它盘簇的簇号是存放在一张显式的链接表，即文件定位表（FAT表）中的，每簇占一FAT表表项。而FAT 表表项的大小取决于磁盘空间的大小，对于3.5存盘，每个FAT表表项占12位（1.5个字节）。 FAT表是一简单的线性表，每个表项占1.5个字节，其中的内容用来说明该簇对应的磁盘区是空闲的还是真在使用。FAT表的头两项用来表示磁盘的类型，对于3.5存盘，它的值为“F0F”、“FFF”
18、。从第三个表项开始表示盘簇的分配状态，它们的含义为： 000 该盘簇为空闲盘簇。 FF8-FFF 该簇是分配给文件的最末一簇。 FF0-FF7 该簇为保留的簇（FF7表示该簇是一个坏簇）。 XXX 分配给文件的下一簇的簇号。 从上可以看出，PC_DOS空闲盘区的情况也是登记在FAT表中的（所有的值为0的FAT表项所对应的盘簇均为空闲盘簇）。在为文件分配盘空间时， 是一个簇一个簇地分配的，系统在FAT表中从头依次查找空闲的表项，并把对应的盘簇分配给文件，最后分配给文件的盘簇可能是连续的，也可能是分散的。 例子 假如，有一3.5存软盘，用“dir /a”命令，结果为： Volume in driv
19、e A is OS Directory of A:par IO SYS 40470 03-10-93 6:00a MSDOS SYS 38138 03-10-93 6:00a COMMAND COM 52925 03-10-93 6:00a DBLSPACE BIN 51214 03-25-93 6:00a FILE1 DOC 15084 08-08-95 12:58p 5 file(s) 197831 bytes 1257984 bytes free它的根目录区的内容为：Disp - Hex codes - ASCII VALUE 0000 49 4f 20 20 20 20 20 20 5
20、3 59 53 27 00 00 00 00 IO SYS.0001 00 00 00 00 00 00 00 30 6a 1a 02 00 16 9e 00 00 .0j.0002 4d 53 44 4f 53 20 20 20 53 59 53 27 00 00 00 00 MSDOS SYS.0003 00 00 00 00 00 00 00 30 6a 1a 52 00 fa 94 00 00 .0j.R.0004 43 4f 4d 4d 41 4e 44 20 43 4f 4d 20 00 00 00 00 COMMAND COM .0005 00 00 00 00 00 00 00
21、 30 6a 1a 9d 00 bd ce 00 00 .0j.0006 44 42 4c 53 50 41 43 45 42 49 4e 27 00 00 00 00 DBLSPACEBIN.0007 00 00 00 00 00 00 00 30 79 1a 05 01 0e c8 00 00 .0y.0008 4f 53 20 20 20 20 20 20 20 20 20 28 00 00 00 00 OS (.0009 00 00 00 00 00 00 a9 69 08 1f 00 00 00 00 00 00 .i.0010 46 49 4c 45 31 20 20 20 44
22、4f 43 20 00 00 00 00 FILE1 DOC .0011 00 00 00 00 00 00 52 67 08 1f 6a 01 ec 3a 00 00 .Rg.j.:.0012 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 .0013 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 .0014 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 .而第一个FAT表的内容为：Disp - Hex codes - ASCII VALUE 0
23、000 f0 ff ff 03 40 00 05 60 00 07 80 00 09 a0 00 0b .0001 c0 00 0d e0 00 0f 00 01 11 20 01 13 40 01 15 60 . .0002 01 17 80 01 19 a0 01 1b c0 01 1d e0 01 1f 00 02 .0003 21 20 02 23 40 02 25 60 02 27 80 02 29 a0 02 2b ! .#.%.).+0004 c0 02 2d e0 02 2f 00 03 31 20 03 33 40 03 35 60 .-./.1 .3.50005 03 37
24、 80 03 39 a0 03 3b c0 03 3d e0 03 3f 00 04 .7.9.;.=.?.0006 41 20 04 43 40 04 45 60 04 47 80 04 49 a0 04 4b A .C.E.G.I.K0007 c0 04 4d e0 04 4f 00 05 51 f0 ff 53 40 05 55 60 .M.O.Q.S.U0008 05 57 80 05 59 a0 05 5b c0 05 5d e0 05 5f 00 06 .W.Y._.0009 61 20 06 63 40 06 65 60 06 67 80 06 69 a0 06 6b a .c.
25、e.g.i.k0010 c0 06 6d e0 06 6f 00 07 71 20 07 73 40 07 75 60 .m.o.q .s.u0011 07 77 80 07 79 a0 07 7b c0 07 7d e0 07 7f 00 08 .w.y.0012 81 20 08 83 40 08 85 60 08 87 80 08 89 a0 08 8b . .0013 c0 08 8d e0 08 8f 00 09 91 20 09 93 40 09 95 60 . .0014 09 97 80 09 99 a0 09 9b c0 09 ff ef 09 9f 00 0a .0015
26、a1 20 0a a3 40 0a a5 60 0a a7 80 0a a9 a0 0a ab . .0016 c0 0a ad e0 0a af 00 0b b1 20 0b b3 40 0b b5 60 . .0017 0b b7 80 0b b9 a0 0b bb c0 0b bd e0 0b bf 00 0c .0018 c1 20 0c c3 40 0c c5 60 0c c7 80 0c c9 a0 0c cb . .0019 c0 0c cd e0 0c cf 00 0d d1 20 0d d3 40 0d d5 60 . .0020 0d d7 80 0d d9 a0 0d d
27、b c0 0d dd e0 0d df 00 0e .0021 e1 20 0e e3 40 0e e5 60 0e e7 80 0e e9 a0 0e eb . .0022 c0 0e ed e0 0e ef 00 0f f1 20 0f f3 40 0f f5 60 . .0023 0f f7 80 0f f9 a0 0f fb c0 0f fd e0 0f ff 00 10 .0024 01 21 10 03 41 10 ff 6f 10 07 81 10 09 a1 10 0b .!.A.o.0025 c1 10 0d e1 10 0f 01 11 11 21 11 13 41 11 15 61 .!.A.a0026 11 17 81 11 19 a1 11 1b c1 11 1d e1 11 1f 01 12 .0027 21 21 12 23 41 12 25 61 12 27 81 12 29 a1 1
