《操作系统结构分析》实验指导书
南京邮电大学计算机学院
信息安全系 2007.10
目 录
第1部分 Linux简明操作手册 ................................................................................ 1
1.1 登录服务器（在Windows远程登录Linux服务器） ............................. 1
1.1.1 登录FTP服务器 ............................................................................... 1 1.1.2 使用putty程序登录远程服务器 ..................................................... 1 1.2 vi简易手册 .................................................................................................. 1 1.3 gcc简易手册 ............................................................................................... 2
1.3.1 gcc简述 ............................................................................................. 2 1.3.2 gcc的基本用法和选项 ..................................................................... 3 1.3.3 如何用gcc进行代码调试 ................................................................ 4 1.3.4 gcc的错误类型及对策 ..................................................................... 7
第2部分 实验部分................................................................................................... 9
2.1 实验一 进程的创建与管道通信实验 ...................................................... 9
2.1.1 实验目的............................................................................................ 9 2.1.2 实验环境............................................................................................ 9 2.1.3 实验原理............................................................................................ 9 2.1.4 实验内容.......................................................................................... 10 2.1.5 实验任务.......................................................................................... 10 2.2 实验二 进程的同步和互斥实验 ............................................................ 13
2.2.1 实验目的.......................................................................................... 13 2.2.2 实验环境.......................................................................................... 13 2.2.3 实验原理.......................................................................................... 13 2.2.4 实验内容.......................................................................................... 15 2.2.5 实验任务.......................................................................................... 15 2.3 实验三 内存管理算法实验 .................................................................... 19
2.3.1 实验目的.......................................................................................... 19 2.3.2 实验环境.......................................................................................... 19 2.3.3 实验原理.......................................................................................... 19 2.3.4 实验内容.......................................................................................... 20 2.3.5 实验任务.......................................................................................... 20 2.4 实验四 Linux文件系统模拟实验 ......................................................... 22
2.4.1 实验目的.......................................................................................... 22 2.4.2 实验环境.......................................................................................... 22 2.4.3 实验原理.......................................................................................... 22 2.4.4 实验内容.......................................................................................... 24 2.4.5 实验任务.......................................................................................... 25 2.5 实验五 Windows 进程同步实验 ........................................................... 26
2.5.1 实验目的.......................................................................................... 26 2.5.2 实验环境.......................................................................................... 26 2.5.3 实验原理.......................................................................................... 26 2.5.4 实验内容.......................................................................................... 28 2.5.5 实验任务.......................................................................................... 28
第3部分 实验报告................................................................................................. 29
第1部分 Linux简明操作手册
1.1 登录服务器（在Windows远程登录Linux服务器） 1.1.1 登录FTP服务器
登陆步骤：
1、点击“开始”→“运行”，输入“cmd” 回车后进入COMMAND命令行状态；
2、输入命令：ftp HostIP （HostIP：10.20.79.10）；
3、输入学号为用户名，密码亦为学号，成功后出现“ftp>”提示符； 4、练习使用操作命令：
1) ls ：列出当前目录下所有的文件和目录
2) put FilePath\\FileName：上传本地文件至服务器目录 3) get FileName ：下载指定的文件名至运行ftp命令的目录中（注意文件名 的大小写）
4) ? [command]：列出当前可用的命令名称，或列出指定命令的使用方法 5) 使用公用帐号public(密码也是public) 登录后可以下载到远程登录终端程序putty.exe和本实验指导书。
1.1.2 使用putty程序登录远程服务器
登陆步骤：
1、在windows环境里直接双击putty.exe图标；
2、输入远程服务器地址：10.20.79.10，并用学号进行登录，密码相同。登录成功后会出现类似提示符“[学号@localhost学号]$”；
用Windows自带的telnet程序也可完成登陆过程，但是该程序运行和使用不如putty方便和稳定，所以推荐使用putty程序，telnet的使用过程与putty相似。
1.2 vi简易手册
vi是Linux中使用频率最高的文字编辑工具，一般我们就用他来编写源代码。此工具的使用习惯和方式与Windows有较大区别，希望多加练习。
vi分为两种状态，即命令状态和编辑状态，在命令状态下，所键入的字符系统均作命令来处理，如：q代表退出，而编辑状态则是用来输入文字资料的。当你进入vi时，会首先进入命令状态。
要进入vi，直接在系统提示符下键入vi <文件名>，当你键入的文件名是已有文件时，则系统自动打开此文件，否则将建立一个新文件。这时你将会看到屏
1
幕左边会出现波浪线~，这就代表该行是空的，没有任何文字，这时系统正在命令状态，按键盘上的a键或i键即可切换到编辑状态，下面就是一些功能键的说明，有些键在某些版本的vi中可能不被支持。
===========================================================
说明 功能键
===========================================================
向下翻一页 Page Down 向上翻一页 Page Up 删除光标所在位置字符 Delete 删除光标所在位置前面的字符 Backspace 移动光标 ←↑↓→
===========================================================
返回命令状态只需按“ESC” 键，存盘需在命令状态下完成，按：w按后回车即完成了存盘工作，而退出vi返回到Linux的命令是“：q”，这两个命令也可以组合使用，如“：wq”代表存盘退出。退出但不保存命令是“：q!” 。
1.3 gcc简易手册 1.3.1 gcc简述
Linux系统下的gcc（GNU C Compiler）是GNU推出的功能强大、性能优越的多平台编译器，是GNU的代表作品之一。gcc编译器能将C、C++语言源程序、汇程式化序和目标程序编译、连接成可执行文件，如果没有给出可执行文件的名字，gcc将生成一个名为a.out的文件。在Linux系统中，可执行文件没有统一的后缀，系统从文件的属性来区分可执行文件和不可执行文件。而gcc则通过后缀来区别输入文件的类别，下面我们来介绍gcc所遵循的部分约定规则。
.c为后缀的文件，C语言源代码文件
.a为后缀的文件，是由目标文件构成的档案库文件 .C，.cc或.cxx 为后缀的文件，是C++源代码文件 .h为后缀的文件，是程序所包含的头文件
.i 为后缀的文件，是已经预处理过的C源代码文件 .ii为后缀的文件，是已经预处理过的C++源代码文件 .m为后缀的文件，是Objective-C源代码文件 .o为后缀的文件，是编译后的目标文件 .s为后缀的文件，是汇编语言源代码文件
.S为后缀的文件，是经过预编译的汇编语言源代码文件
虽然我们称gcc是C语言的编译器，但使用gcc由C语言源代码文件生成可执行文件的过程不仅仅是编译的过程，而是要经历四个相互关联的步骤∶预处理(也称预编译，Preprocessing)、编译(Compilation)、汇编(Assembly)和连接(Linking)。
命令gcc首先调用cpp进行预处理，在预处理过程中，对源代码文件中的文
2
件包含(include)、预编译语句(如宏定义define等)进行分析。接着调用cc1进行编译，这个阶段根据输入文件生成以.o为后缀的目标文件。汇编过程是针对汇编语言的步骤，调用as进行工作，一般来讲，.S为后缀的汇编语言源代码文件和汇编、.s为后缀的汇编语言文件经过预编译和汇编之后都生成以.o为后缀的目标文件。当所有的目标文件都生成之后，gcc就调用ld来完成最后的关键性工作，这个阶段就是连接。在连接阶段，所有的目标文件被安排在可执行程序中的恰当的位置，同时，该程序所调用到的库函数也从各自所在的档案库中连到合适的地方。
1.3.2 gcc的基本用法和选项
gcc的基本语法是：
gcc [options] [filenames]
其中options就是编译器所需要的参数，filenames给出相关的文件名称，下面就是几种常用的选项参数。
-c，只编译，不连接成为可执行文件，编译器只是由输入的.c等源代码文件生成.o为后缀的目标文件，通常用于编译不包含主程序的子程序文件。
-o output_filename，（小写o）确定输出文件的名称为output_filename，同时这个名称不能和源文件同名。如果不给出这个选项，gcc就给出预设的可执行文件a.out。
-g，产生符号调试工具(GNU的gdb)所必要的符号资讯，要想对源代码进行调试，我们就必须加入这个选项。
-O，（大写O）对程序进行优化编译、连接，采用这个选项，整个源代码会在编译、连接过程中进行优化处理，这样产生的可执行文件的执行效率可以提高，但是，编译、连接的速度就相应地要慢一些。
-O2，比-O更好的优化编译、连接，当然整个编译、连接过程会更慢。 -I dirname，将dirname所指出的目录加入到程序头文件目录列表中，是在预编译过程中使用的参数。C程序中的头文件包含两种情况∶
A)#include
B)#include “myinc.h”
其中，A类使用尖括号(< >)，B类使用双引号(“ ”)。对于A类，预处理程序cpp在系统预设包含文件目录(如/usr/include)中搜寻相应的文件，而对于B类，cpp在当前目录中搜寻头文件，这个选项的作用是告诉cpp，如果在当前目录中没有找到需要的文件，就到指定的dirname目录中去寻找。在程序设计中，如果我们需要的这种包含文件分别分布在不同的目录中，就需要逐个使用-I选项给出搜索路径。
-L dirname，将dirname所指出的目录加入到程序函数档案库文件的目录列表中，是在连接过程中使用的参数。在预设状态下，连接程序ld在系统的预设路径中(如/usr/lib)寻找所需要的档案库文件，这个选项告诉连接程序，首先到-L指定的目录中去寻找，然后到系统预设路径中寻找，如果函数库存放在多个目录下，就需要依次使用这个选项，给出相应的存放目录。
-l name，在连接时，装载名字为“libname.a”的函数库，该函数库位于系
3
统预设的目录或者由-L选项确定的目录下。例如，-lm表示连接名为“libm.a”的数学函数库。
1.3.3 如何用gdb进行代码调试
Linux包含了一个叫gdb的GNU调试程序。gdb是一个用来调试C和 C++程序的强力调试器。它使你能在程序运行时观察程序的内部结构和内存的使用情况. 以下是gdb所提供的一些功能：
1、它使你能监视你程序中变量的值。
2、它使你能设置断点以使程序在指定的代码行上停止执行。 3、它使你能一行行的执行你的代码。
在命令行上键入gdb并按回车键就可以运行gdb了，如果一切正常的话， gdb 将被启动并且你将在屏幕上看到类似的内容：
GDB is free software … Copyright 1995 Free Software Foundation， Inc.
当你启动gdb后，你能在命令行上指定很多的选项，你也可以以下面的方式来运行gdb：
gdb
当你用这种方式运行gdb，你能直接指定想要调试的程序。这将告诉gdb装入名为fname的可执行文件。你可以参考gdb指南页或在命令行上键入gdb -h得到一个有关这些选项的说明的简单列表。
为调试编译代码(Compiling Code for Debugging) ，为了使gdb正常工作，你必须使你的程序在编译时包含调试信息。调试信息包含你程序里的每个变量的类型和在可执行文件里的地址映射以及源代码的行号。gdb利用这些信息使源代码和机器码相关联。在编译时用 -g 选项打开调试选项。
gdb支持很多的命令使你能实现不同的功能。 这些命令从简单的文件装入到允许你检查所调用的堆栈内容的复杂命令，下表列出了你在用gdb调试时会用到的一些命令。
基本gdb命令
file 装入想要调试的可执行文件。 kill 终止正在调试的程序。 list 列出产生执行文件的源代码的一部分。 next 执行一行源代码但不进入函数内部。 step 执行一行源代码而且进入函数内部。 run 执行当前被调试的程序 quit 终止 gdb watch 使你能监视一个变量的值而不管它何时被改变。 break 在代码里设置断点， 这将使程序执行到这里时被挂起。 make 使你能不退出 gdb 就可以重新产生可执行文件。 shell 使你能不离开 gdb 就执行 UNIX shell 命令。
gdb 应用举例
被调试的程序相当的简单，但它展示了gdb的典型应用。下面列出了将被调
4
试的程序。这个程序被称为greeting，它显示一个简单的问候，再用反序将它列出。
#include
The string is hello there
The string printed backward is
输出的第一行是正确的， 但第二行打印出的东西并不是我们所期望的。 我们所设想的输出应该是：The string printed backward is ereht olleh 。由于某些原因，my_print2函数没有正常工作。让我们用gdb看看问题究竟出在哪儿，先键入如下命令： gdb greeting 注意： 记得在编译 greeting 程序时把调试选项打开。 如果你在输入命令时忘了把要调试的程序作为参数传给 gdb ， 你可以在 gdb 提示符下用 file 命令来载入它： (gdb) file greeting 这个命令将载入greeting可执行文件就象你在gdb命令行里装入它一样。这时你能用gdb的run命令来运行greeting了。当它在gdb里被运行后结果大约会象这样： (gdb) run Starting program： /root/greeting
5
The string is hello there The string printed backward is Program exited with code 041 这个输出和在 gdb 外面运行的结果一样。问题是，为什么反序打印没有工作? 为了找出症结所在，我们可以在 my_print2 函数的 for 语句后设一个断点， 具体的做法是在 gdb 提示符下键入 list 命令三次， 列出源代码： (gdb) list (gdb) list (gdb) list 技巧： 在 gdb 提示符下按回车健将重复上一个命令。 第一次键入 list 命令的输出如下： 1 #include
6
gdb 将作出如下的响应： Breakpoint 1 at 0x139： file greeting.c， line 24 现在再键入 run 命令， 将产生如下的输出： Starting program： /root/greeting The string is hello there Breakpoint 1， my_print2 (string = 0xbfffdc4 \greeting.c ：24 24 string2[size-i]=string[i] 你能通过设置一个观察string2[size - i] 变量的值的观察点来看出错误是怎样产生的， 做法是键入： (gdb) watch string2[size - i] gdb 将作出如下回应： Watchpoint 2： string2[size - i] 现在可以用next命令来一步步的执行for循环了： (gdb) next 经过第一次循环后， gdb告诉我们string2[size - i] 的值是 `h`。gdb用如下的显示来告诉你这个信息： Watchpoint 2， string2[size - i] Old value = 0 `\\000' New value = 104 `h' my_print2(string = 0xbfffdc4 \：23 23 for (i=0; i 这个值正是期望的。 后来的数次循环的结果都是正确的。 当i=10时， 表达式string2[size - i]的值等于`e`， size - i的值等于1， 最后一个字符已经拷到新串里了。
如果你再把循环执行下去， 你会看到已经没有值分配给string2[0]了， 而它是新串的第一个字符， 因为malloc函数在分配内存时把它们初始化为空(null)字符。所以string2的第一个字符是空字符。这解释了为什么在打印 string2 时没有任何输出了。
现在找出了问题出在哪里， 修正这个错误是很容易的。你得把代码里写入 string2的第一个字符的的偏移量改为size - 1 而不是size。这是因为 string2 的大小为12，但起始偏移量是 0，串内的字符从偏移量0到偏移量10，偏移量11为空字符保留。为了使代码正常工作有很多种修改办法。 一种是另设一个比串的实际大小小1的变量，具体解法略。
1.3.4 gcc的错误类型及对策
gcc编译器如果发现源程序中有错误，就无法继续进行，也无法生成最终的可执行文件。为了便于修改，gcc给出错误资讯，我们必须对这些错误资讯逐个进行分析、处理，并修改相应的语言，才能保证源代码的正确编译连接。gcc给出的错误资讯一般可以分为四大类，下面我们分别讨论其产生的原因和对策。
7
第一类∶C语法错误
错误资讯∶文件source.c中第n行有语法错误(syntex errror)。这种类型的错误，一般都是C语言的语法错误，应该仔细检查源代码文件中第n行及该行之前的程序，有时也需要对该文件所包含的头文件进行检查。有些情况下，一个很简单的语法错误，gcc会给出一大堆错误，我们最主要的是要保持清醒的头脑，不要被其吓倒，必要的时候再参考一下C语言的基本教材。
第二类∶头文件错误
错误资讯∶找不到头文件head.h(Can not find include file head.h)。这类错误是源代码文件中的包含头文件有问题，可能的原因有头文件名错误、指定的头文件所在目录名错误等，也可能是错误地使用了双引号和尖括号。
第三类∶档案库错误
错误资讯∶连接程序找不到所需的函数库，例如∶ ld： -lm： No such file or directory
这类错误是与目标文件相连接的函数库有错误，可能的原因是函数库名错误、指定的函数库所在目录名称错误等，检查的方法是使用find命令在可能的目录中寻找相应的函数库名，确定档案库及目录的名称并修改程序中及编译选项中的名称。
第四类∶未定义符号
错误资讯∶有未定义的符号(Undefined symbol)。这类错误是在连接过程中出现的，可能有两种原因∶一是使用者自己定义的函数或者全局变量所在源代码文件，没有被编译、连接，或者干脆还没有定义，这需要使用者根据实际情况修改源程序，给出全局变量或者函数的定义体；二是未定义的符号是一个标准的库函数，在源程序中使用了该库函数，而连接过程中还没有给定相应的函数库的名称，或者是该档案库的目录名称有问题，这时需要使用档案库维护命令ar检查我们需要的库函数到底位于哪一个函数库中，确定之后，修改gcc连接选项中的-l和-L项。
8
第2部分 实验部分
2.1 实验一 进程的创建与管道通信实验 2.1.1 实验目的
了解Linux的基本命令，掌握在Linux下C/C++语言编辑、编译、运行的过程，掌握进程的创建，掌握使用管道进行进程间通信。
2.1.2 实验环境
硬件：PC机和Linux服务器
软件：Linux操作系统，putty软件
2.1.3 实验原理
1、进程的创建。在Linux下，fork()是用于创建进程的库函数，它的调用会产生一个与父进程相同的子进程，唯一不同之处在于他们的进程id(即pid)。
unsigned int sleep(unsigned int seconds); 3、管道。管道是Linux支持的最初Unix IPC形式之一，具有以下特点： （1）管道是半双工的，数据只能向一个方向流动；需要双方通信时，需要建立起两个管道；
（2）只能用于父子进程或者兄弟进程之间（具有亲缘关系的进程）；
（3）单独构成一种独立的文件系统：管道对于管道两端的进程而言，就是一个文件，但它不是普通的文件，它不属于某种文件系统，而是自立门户，单独构成一种文件系统，并且只存在与内存中。
数据的读出和写入：一个进程向管道中写的内容被管道另一端的进程读出。
9
写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据。 管道的创建： #include
管道的读写规则：
管道两端可分别用描述字fd[0]以及fd[1]来描述，需要注意的是，管道的两端是固定了任务的。即一端只能用于读，由描述字fd[0]表示，称其为管道读端；另一端则只能用于写，由描述字fd[1]来表示，称其为管道写端。如果试图从管道写端读取数据，或者向管道读端写入数据都将导致错误发生。一般文件的I/O函数都可以用于管道，如close、read、write等等。 //从文件描述符fildes中读出指定字节的数据到buf指向的缓冲区中 ssize_t read(int fildes ， void * buf ， size_t nbytes); //向文件描述符fildes写入指定字节的由buf指向的缓冲区数据 ssize_t write(int fildes ， const void * buf ， size_t nbytes); 2.1.4 实验内容
练习使用Linux的基本命令，熟悉Linux环境和vi的使用方法，练习在Linux下编辑、编译、调试和支行C/C++语言的技巧。
编程实现创建1个子进程，父进程等待子进程先执行，并分别打印出父子进程的pid是多少。
运用Linux平台下进程的创建以及进程间的管道通信技术，编码实现两个父子进程通过管道交换一个变量值。
2.1.5 实验任务
1、练习使用Linux的常用命令。
ls ：列出当前目录的所有文件和目录； cd ：进入某一个目录时使用，“.. /” 表示上一级目录，“./” 表示当前目录；
tar 解压缩 tar xf name.tar
tar zxf name.tar.gz
10
tar zxf name.tar.z ps 查看进程
cat 查看文件内容 cp 拷贝
mkdir 创建目录 logout 重新登录
vmstat 查看cpu使用情况 vmstat interval [count] renice 改变运行的进程的优先级 su 切换用户 who 查看用户 passwd 改变口令 pwd 当前目录
rmdir 删除目录，目录为空 rm 删除目录
more 同cat 一屏一屏滚动 wc 查看文件的信息 df 磁盘空间 free 内存空间
man 查看命令的具体用法 pstree 显示进程树
netstat 检查网络连接的状态，路由表和其他信息 ping 同dos的ping tree 显示树状目录
which 显示指令完整路径
mv 用于移动文件和重命名文件 find查找文件，功能强大 env显示所有环境变量
2、熟悉vi的使用方式，编写一程序创建出一子进程，并使用sleep函数让父进程等待子进程先运行完毕。最后打印出父子进程的pid分别是多少。
3、实现父子进程间的管道通信。示例代码如下： /************** * readtest.c * **************/ #include
11
char* p_wbuf; int r_num; int cmd; memset(r_buf,0,sizeof(r_buf)); memset(w_buf,0,sizeof(r_buf)); p_wbuf=w_buf; if(pipe(pipe_fd)<0) { printf(\ return -1; } if((pid=fork())==0) { printf(\ close(pipe_fd[1]); sleep(3);//确保父进程关闭写端 r_num=read(pipe_fd[0],r_buf,100); printf( \num is %d the data read from the pipe is %d\\n\ close(pipe_fd[0]); exit(); } else if(pid>0) { close(pipe_fd[0]);//read strcpy(w_buf,\ if(write(pipe_fd[1],w_buf,4)!=-1) printf(\ close(pipe_fd[1]);//write printf(\ sleep(10); } }
12
2.2 实验二 进程的同步和互斥实验 2.2.1 实验目的
理解进程间的同步、互斥机制，掌握将其运用至现实问题的能力。
2.2.2 实验环境
硬件：PC机和Linux服务器
软件：Linux操作系统，putty软件
2.2.3 实验原理
多进程的系统中避免不了进程间的相互关系。本讲将介绍进程间的两种主要关系―同步与互斥，然后着重讲解解决进程同步的几种机制。
进程互斥是进程之间发生的一种间接性作用，一般是程序不希望的。通常的情况是两个或两个以上的进程需要同时访问某个共享变量。我们一般将发生能够问共享变量的程序段成为临界区。两个进程不能同时进入临界区，否则就会导致数据的不一致，产生与时间有关的错误。解决互斥问题应该满足互斥和公平两个原则，即任意时刻只能允许一个进程处于同一共享变量的临界区，而且不能让任一进程无限期地等待。
进程同步是进程之间直接的相互作用，是合作进程间有意识的行为典型的例子是公共汽车上司机与售票员的合作。
只有当售票员关门之后司机才能启动车辆，只有司机停车之后售票员才能开车门。司机和售票员的行动需要一定的协调。同样地，两个进程之间有时也有这样的依赖关系，因此我们也要有一定的同步机制保证它们的执行次序。
信号量是实现同步互斥机制的一种手段。信号量，正如字典中所定义的，是一种机械的信号设备或者是采用的可视信号方式。
使用信号量机制为计算机软件提供同步这种概念最早是由荷兰数学家E.W.Dijkstra在1965年提出的。Dijkstra最初的工作定义了两种信号操作，等待和发信号（这与铁路的例子相关联）。这两个操作被称为P和V操作。P操作就
13
是等待，会递减信号值，如果信号值大于0；而V操作就是发信号，会递增信号值。P和V起源于荷兰语中的“尝试”和“增长”。P来源于Probeer，意思就是尝试或试图；而V来源于Verhoog，意思就是增长。P减少信号计数，V则增长信号计数。
信号机制为资源访问提供了一种同步方法，这些资源通常被多个进程共享。它们可以作为二进制锁来拒绝访问，或者作为计数器来使用；它们用来对有限的共享资源的进行访问管理，因此信号量的初始化值为共享资源的数量。每当一个进程需要一个资源的时候，信号量的值减少。当进程结束释放资源后，信号量的值增加。当前没有可用资源的话，空信号量值会传递给调用进程，而调用进程会阻塞，直到占用资源的进程结束并释放了资源为止。
Solaris中的信号量机制（System V信号量）的实现考虑到了信号量集合，这意味着唯一的信号量标识符能够获取多个信号量。信号量标识符包括一个信号量还是一组信号是由semget()系统调用在生成信号时决定的。Semget()的第二个参数决定信号量的数量，这将与semget()返回的信号量标识符相关联。信号量机制的系统调用也考虑到对信号量集合的操作，例如开发人员能用一个semctl()或semop()调用，接触到信号量集合中的所有信号量。用这种方法处理信号量集合，程序开发会变得容易一些。
System V信号量的函数主要有下面几个： ＃i nclude
14
如果sem_op大于0，那么操作将sem_op加入到信号量的值中，并唤醒等待信号增加的进程。 如果小于0，说明要申请资源，则函数判断信号量的值加上这个负值，如果结果为0唤醒等待信号量为0的进程，如果小与0函数阻塞，如果大于0，那么从信号量里面减去这个值并返回。 操作标志sem_flg在此实验中取0。 2.2.4 实验内容
运用Linux平台下的进程间同步和互斥机制，设计实现一个生产者进程和一个消费者进程通过共享内存交换数据，并能达到以下要求。
问题描述：一个仓库可以存放K件物品。生产者每生产一件产品，将产品放入仓库，仓库满了就停止生产。消费者每次从仓库中去一件物品，然后进行消费，仓库空时就停止消费。
题目所设的共享文件即为仓库，生产者和消费者进程均可以是多个，同学们可尝试这种更为复杂的情况应该如何编码。
2.2.5 实验任务
1、要求绘出生产/消费者模型，并使用PV操作写出伪代码。
2、使用System V信号量机制实现这个模型。更详细的介绍请直接在Linux下查询联机帮助。以下是本实验的实例代码，仅作参考。 #include
//共享内存中的结构 15
int main() { int shmid; char* shmPtr; //共享内存id //指向共享内存首地址的指针 SHAREBUFFER* pSharebuffer; //共享内存结构体指针 int product = 0; //产品值，生产一件自加1 int semid; //信号集id struct sembuf mutex,empty,full; //三个信号量的控制变量 int i; // //创建或打开一个键值为KEY的信号量集合，包含3个信号量，并返回一个信号量集合id // if ((semid = semget(KEY,3,IPC_CREAT|0660)) == -1) { printf(\ return -1; } /********************************************************* * 初始化信号量的初值 * 第0个信号量用于互斥，初值为1 * 第1个信号量用于生产者，初值为MAX_BUFFER_SIZE * 第2个信号量用于消费者，初值为0 * arg是用于给信号量赋值的一个中间过渡变量，不必理会 *********************************************************/ union semun arg[3]; arg[0].val = 1; arg[1].val = MAX_BUFFER_SIZE; arg[2].val = 0; for(i=0;i<3;i++) //赋值语句，因为信号是核心 semctl(semid,i,SETVAL,arg[i]); 对象，所以要使用特殊的系统调用赋值 for(i=0;i<3;i++) printf(\= %d\\n\
16
semval(%d) 间清0 // //创建或打开一个键值为KEY的共享内存块，并返回它的id // if ((shmid = shmget(KEY,sizeof(SHAREBUFFER),IPC_CREAT)) < 0) { printf(\ return -1; } // //将共享内存映射到进程空间里，并返回共享内存首地址 // if((shmPtr = (char*)shmat(shmid,0,0)) == (void*)-1) { printf(\ return -1; } memset((void*)shmPtr,0,sizeof(SHAREBUFFER)); //将共享内存空 pSharebuffer = (SHAREBUFFER*)shmPtr; // //下面开始向ShareBuffer中生产产品 // while(1) { empty.sem_num = 1; //指操作哪个信号量 empty.sem_op = -1; //要对信号量的值作减1操作 empty.sem_flg = 0; //控制标识符 semop(semid,&empty,1); //P(empty) pSharebuffer->buffer[pSharebuffer->writer] = product; for(i=0;i<3;i++) printf(\semval(%d) = %d\\n\ printf(\the product into buffer[%d] = %d;\\n\
17
product++; mutex.sem_num = 0; mutex.sem_op = -1; mutex.sem_flg = 0; semop(semid,&mutex,1); //P(mutex) pSharebuffer->writer = (pSharebuffer->writer + 1) % MAX_BUFFER_SIZE; mutex.sem_num = 0; mutex.sem_op = 1; mutex.sem_flg = 0; semop(semid,&mutex,1); //V(mutex) full.sem_num = 2; full.sem_op = 1; full.sem_flg = 0; semop(semid,&full,1); //V(full) sleep(1); //调节一下生产速度^_^ } return 0; }
18
2.3 实验三 虚存管理算法实验 2.3.1 实验目的
掌握虚拟存储管理的原理，掌握虚存管理中的页面置换算法，学会分析各种页面置换算法的优劣以及内存页框数量对算法的影响。
2.3.2 实验环境
硬件：PC机和Linux服务器
软件：Linux操作系统或Windows操作系统，putty软件，VC++6.0软件
2.3.3 实验原理
分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。
1、调页策略
（1）何时调入页面
如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页的效率更高效一些。但如果调入的一批页面中的大多数都未被访问，则又是低效的。可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。如果预测较准确，那么，这种策略显然是很有吸引力的。但目前预调页的成功率仅为50%。且这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。
（2）请求调页策略
当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便即提出请求，由OS将其所需页面调入内存。由请示调页策略所确定调入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中，大多采用此策略。但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘I/O的启用频率。
2、页面调入过程
每当程序所要访问的页面未在内存时， 便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外在原物理 块后，如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。
19
3、页面置换算法
在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确定。以下分别是三个算法的设计思想。
OPTIMAL：最佳置换算法。其所选择的被淘汰页面，将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。
FIFO：先进先出置换算法。该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。
LRU：最近最久未使用置换算法。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间T，当须淘汰一个页面时，选择现有页面中其T值最大的给予淘汰。
CLOCK：分简单CLOCK置换算法和改进型CLOCK算法。LRU算法是较好的一种算法，而由于LRU在硬件上要求较多，在实际应用中多采用LRU的近似算法。CLOCK算法就是用得较多的一种LRU近似算法。
2.3.4 实验内容
在Linux/Windows环境下，对给定的可用内存页面数和进程访问逻辑页号的序列，实现FIFO、LRU和CLOCK算法置换，并分别计算缺页中断率。
通过改变空闲页框数，记录各种算法产生的缺页中断次数，将数据表示在曲线图上，比较各种算法的优劣。
2.3.5 实验任务
1、随机生成一个进程访问的逻辑页号列表，要求不少于100个页号，把这些页号存入文件page.txt。
每 千 次 访 问的 缺 页 中 断 数
40 35 30 25 20 15 10 5 0 0
? ? ? ?
? ?
? FIFO
? Clock fffCCLO LRU ?
?
? ? ?
? ? 8
?
? ? 10
1 3
分配的页框数
5
20
2、编程分别实现FIFO、LRU和CLOCK算法，每次调用算法前要求用户输入页框数量，每种算法最后都需要给出页面的置换顺序以及缺页中断次数，并把缺页数记录在如上所示的曲线图上。
3、不断地改变页框数，完成这张曲线图，并且做出简短的小结，用于分析页框数对缺页率的影响。
21
2.4 实验四 简单文件系统模拟实验 2.4.1 实验目的
理解操作系统的文件系统组成以及基本原理，利用这些知识模拟出一个FAT格式的文件系统，学有余力者可以进一步模拟ext2格式的文件系统。
2.4.2 实验环境
硬件：PC机和Linux服务器 软件：Linux操作系统
2.4.3 实验原理
文件系统指文件存在的物理空间，Linux系统中每个分区都是一个文件系统，都有自己的目录层次结构。Linux会将这些分属不同分区的、单独的文件系统按一定的方式形成一个系统的总的目录层次结构。一个操作系统的运行离不开对文件的操作，因此必然要拥有并维护自己的文件系统。
Linux文件系统使用索引节点来记录文件信息，作用像windows的文件分配表。
索引节点是一个结构，它包含了一个文件的长度、创建及修改时间、权限、所属关系、磁盘中的位置等信息。一个文件系统维护了一个索引节点的数组，每个文件或目录都与索引节点数组中的唯一一个元素对应。系统给每个索引节点分配了一个号码，也就是该节点在数组中的索引号，称为索引节点号。
Linux文件系统将文件索引节点号和文件名同时保存在目录中。所以，目录只是将文件的名称和它的索引节点号结合在一起的一张表，目录中每一对文件名称和索引节点号称为一个连接。
对于一个文件来说有唯一的索引节点号与之对应，对于一个索引节点号，却可以有多个文件名与之对应。因此，在磁盘上的同一个文件可以通过不同的路径去访问它。
可以用ln命令对一个已经存在的文件再建立一个新的连接，而不复制文件的内容。
连接有软连接和硬连接之分，软连接又叫符号连接。它们各自的特点是： 硬连接：原文件名和连接文件名都指向相同的物理地址。目录不能有硬连接；硬连接不能跨越文件系统（不能跨越不同的分区）。文件在磁盘中只有一个拷贝，节省硬盘空间；由于删除文件要在同一个索引节点属于唯一的连接时才能成功，因此可以防止不必要的误删除。
符号连接：用ln -s命令建立文件的符号连接。符号连接是linux特殊文件的一种，作为一个文件，它的数据是它所连接的文件的路径名。类似windows下的快捷方式。可以删除原有的文件而保存连接文件，没有防止误删除功能。
22
接下去我们看看本指导书将要采用的用例―FAT。作为一种文件名称，FAT（File Allocation Table，文件分配表）自1981年问世以来，已经成为一个计算机术语。由于时代的原因，包括Windows、MacOS以及多种Unix版本在内的大多数操作系统均对FAT提供支持。 这是MS-DOS和最早期的Windows 95操作系统中使用的磁盘分区格式。它采用16位的文件分配表，是目前获得操作系统支持最多的一种磁盘分区格式，几乎所有的操作系统都支持这种分区格式，从DOS、Windows 95、Windows OSR2到现在的Windows 98、Windows Me、Windows NT、Windows 2000、Windows XP都支持FAT16，但只支持2GB的硬盘分区成为了它的一大缺点。FAT16分区格式的另外一个缺点是：磁盘利用效率低（具体的技术细节请参阅相关资料）。为了解决这个问题，微软公司在Windows 95 OSR2中推出了一种全新的磁盘分区格式——FAT32。
FAT中的每个表项都对应了磁盘中每一块的分配状况，FAT的表项位数决定了最大可表示的磁盘容量。FAT16表示最多支持216个块(或簇)。FAT表项的可能值为：
0x00：表示对应块空闲
0xFF：表示对应块为文件的最后一块 其它值：表示该文件的下一块的块号
文件目录里记录了文件的控制信息，每一个目录项(FCB)都对应一个文件，用户要操作文件时总是先查询目录找出FCB，然后才能读取文件内容。 简单文件系统示范： 1、虚拟磁盘结构
#define MAX_DISK_SIZE 256 u_char g_disk[MAX_DISK_SIZE]
定义每一个磁盘块大小为16字节，所以系统最多存放16个物理块内容。 规定FAT表总占用第0块，使用8位的FAT表项，所以第0块共有16个FAT表项，目录表占用第1至4块，每个目录项(FCB)占16个字节，因此系统最多支持4个文件。由于0~5块被系统占用，FAT的第0~5字节应为0xFF，故系统最大支持块数量为10块。
2、系统数据结构 /************************************************************* FAT结构 使用1个字节（8位）表示一个块号 cluster值： 0x00 : 空闲 0xFF : 文件的最后一块 其它值 : 文件的下一块块号 *************************************************************/ typedef struct _tagfat { u_char cluster; } FAT,*PFAT,**PPFAT; /*********************************************************** 文件控制块结构（16字节）
23
f_name : 文件名，最长8个字符，注意要留一个字符保存’\\0’，故文件名最长7个字符 f_size : 文件长度 f_firstblock : 文件的起始块号 ********************************************************/ typedef struct _tagfcb { char f_name[8]; int f_size; int f_firstblock; } FCB,*PFCB,**PPFCB; 3、文件删除原理。删除一个文件时需要做两件事：
（1）把文件占用的块号对应的FAT项清0x00。例如被删除的文件占用了第7块物理块，那么要将FAT的第7字节置0x00(原本为0xFF)
（2）把目录表中的相应项中的文件名第一个字节置0xE5
由此看出，使用FAT的文件系统删除文件时并不清除文件占用的物理块内容，这也给反删除文件带来了可能。在目录项中，文件名的第一个字节很关键，如果是0xE5的话则说明该目录项空闲可以存放一个文件信息，否则说明已被占用。
2.4.4 实验内容
在内存中模拟一简单的文件系统，可以完成文件的创建和索引功能。问题的描述如下：
1、遵循FAT格式使用内存模拟一个文件系统，并实现以下命令接口： （1）新建文件，格式：mkfile filename filecontent filename：文件名 filecontent：文件内容(字符) 实现按FAT格式写FAT表和目录表，以及文件内容。 （2）列出文件，格式：dir 列出目录里所有的文件信息和虚拟磁盘信息。 （3）显示文件内容，格式：type filename filename：文件名 在目录项中查找文件名所在块号，并把文件内容打印在屏幕上。
（4）删除文件：del filename filename：文件名 将文件删除，回收虚拟磁盘空间。
（5）退出文件系统：quit
2、本指书仅将给出一个文件系统格式范例，同学们可以在此基础上进行改进，如：可以使用文件来模拟文件系统，可以实现多级的目录结构，模拟ext2格式的Linux文件系统等。
24
2.4.5 实验任务
1、按照指导书所述的简单文件系统说明，将其编码实现，效果图如下：
2、自行完成Linux的ext2文件系统的模拟原型系统。
25
2.5 实验五 Windows进程同步实验 2.5.1 实验目的
进一步理解进程间的同步、互斥机制，掌握在Windows操作系统下运用的能力。
2.5.2 实验环境
硬件：PC机
软件：Windows操作系统，VC++ 6.0软件
2.5.3 实验原理
本实验的理论知识与实验二相同，只不是实验平台有所变化。这也意味着要使用Windows所支持的信号量函数来进行编码实现，所以学习Windows的信号量实现机制是本实验的重点。
微软件提供了以下信号量函数供我们使用： CreateSemaphore(); //创建一个信号量 OpenSemaphore(); //打开一个已经创建的信号量 ReleaseSemaphore(); //释放对信号量的所有权 HANDLE CreateSemaphore( LPSECRUITY_ATTRIBUTES lpSemaphoreAttributes, LONG lInitialCount, LONG lMaximumCount, LPCTSTR lpName ); lpSemaphoreAttributes安全属性指针。 lInitialCount为初始有多少信号量有信号（即可以被线程捕获以启动线程的数量）。这个值必须大于等于1，并且小于lMaximumCount。lMaximumCount是一共创建多少个信号量，显然要大于0。 对于信号量，我们可以这么来理解它的工作方式。系统内部有一个信号量计数器，它表示有多少信号量可以使用，一旦被其它线程捕获，则减一，如果有线程释放了信号量，则这个计数器加一。当计数器为0时，没有线程能被启动，将一直等到有其它线程释放信号量为止。 lpName为信号量的名字，基本上这个作用也只在多进程间有用。 HANDLE OpenSemaphore( DWORD dwDesiredAccess, // access flag 26
BOOL bInheritHandle, // inherit flag LPCTSTR lpName // pointer to semaphore-object name ); 作为打开这类函数之前已经看到很多了，一般用在多进程间，线程中用不太到。 BOOL ReleaseSemaphore( HANDLE hSemaphore, // handle of the semaphore object LONG lReleaseCount, // amount to add to current count LPLONG lpPreviousCount // address of previous count ); hSemaphore为信号量对象的句柄，一般是CreateSemaphore()或者OpenSemaphore()的返回值。 lReleaseCount为准备返还给信号量计数器的信号数量。以实例9的情况为例，读线程应该返还2个信号量，而写线程则分别返还一个信号量。 lpPreviousCount存放返还前信号量计数器的值，如果不需要这个值可以设为NULL。 本实验要学习的第二个内容是进程间如何通过DLL共享内存。Windows能够将同时使用同一个动态链接库的应用程序分开。不过，有时却不太令人满意。您可能希望写一个DLL，其中包含能够被不同应用程序或者同一个程序的不同例程所共享的内存。这包括使用共享内存。共享内存实际上是一种内存映像文件。
让我们测试一下，这项工作是如何在程序STRPROG（「字符串程序（string program）」）和动态链接库STRLIB（「字符串链接库（string library）」）中完成的。STRLIB有三个输出函数被STRPROG呼叫，我们只对此感兴趣，STRLIB中的一个函数使用了在STRPROG定义的callback函数。
STRLIB是一个动态链接库模块，它储存并排序了最多256个字符串。在STRLIB中，这些字符串均为大写，并由共享内存维护。利用STRLIB的三个函数，STRPROG能够添加字符串、删除字符串以及从STRLIB获得目前的所有字符串。STRPROG测试程序有两个菜单项（「Enter」和「Delete」），这两个菜单项将启动不同的对话框来添加或删除字符串。STRPROG在其显示区域列出目前储存在STRLIB中的所有字符串。
下面这个函数在STRLIB定义，它将一个字符串添加到STRLIB的共享内存。 EXPORT BOOL CALLBACK AddString (pStringIn)
参数pStringIn是字符串的指针。字符串在AddString函数中变成大写。如果在STRLIB的列表中有一个相同的字符串，那么此函数将添加一个字符串的复本。如果成功，AddString传回「TRUE」（非0），否则传回「FALSE」（0）。如果字符串的长度为0，或者不能配置储存字符串的内存，或者已经储存了256个字符串，则传回值将都是FALSE。
STRLIB函数DeleteString()从STRLIB的共享内存中删除一个字符串。 EXPORT BOOL CALLBACK DeleteString (pStringIn)
另外，参数pStringIn是一个字符串指针。如果有多个相同内容字符串，则删除第一个。如果成功，那么DeleteString传回「TRUE」（非0），否则传回「FALSE」（0）。传回「FALSE」表示字符串长度为0，或者找不到相同内容的字符串。
27
STRLIB函数使用了呼叫程序中的一个callback函数，以便列出目前储存在STRLIB共享内存中的字符串：
EXPORT int CALLBACK GetStrings (pfnGetStrCallBack, pParam) 在呼叫程序中，callback函数必须像下面这样定义：
EXPORT BOOL CALLBACK GetStrCallBack (PSTR pString, PVOID pParam) GetStrings的参数pfnGetStrCallBack指向callback函数。直到callback函数传回「FALSE」（0），GetStrings将为每个字符串都呼叫一次GetStrCallBack。GetStrings传回传递给callback函数的字符串数。pParam参数是一个远程指针，指向程序写作者定义的数据。
2.5.4 实验内容
运用进程同步互斥原理、Windows的信号量和共享内存机制以及动态链接库原理，设计一个生产消费程序模型。具体要求：
1、设计两个Windows控制台应用程序，生产程序不断向共享内存拷贝数据并打印信息，消费程序不断从共享内存读取数据并打印出来。
2、两程序通过DLL共享内存，当共享内存满时生产程序停止拷贝，当共享内存为空时消费程序停止读取。
2.5.5 实验任务
1、实验运行的结果与实验二一致，只不过本实验要求在Windows平台下完成。
2、请使用Windows提供的信号量机制编制两个应用程序分别代表生产者和消费者，并且用DLL模拟仓库，让两进程通过DLL共享内存数据以完成题意。
28
第3部分 实验报告
3.1 实验报告格式
实验报告内容：包括实验名称、目的、任务（以简洁明了的叙述说明本次实验的任务和目标）；实验内容、 实验过程描述（包括算法分析过程以及源程序、运行结果等）； 分析和体会（包括实验结果分析，程序设计与调试过程所遇到的问题，问题解决中得到的经验和体会，进一步改进的设想）。具体格式见下表。
实验报告以文本形式递交。实验报告要书写规范、文字简练、语句通顺、图表清晰。
实 验 报 告
实验名称 实验类型 实验学时 指导教师 实验时间 一、 实验目的和要求 二、实验环境(实验设备) 三、实验原理及内容 实验小结（包括问题和解决方法、心得体会、意见与建议等）
29