计算机操作系统实验教程.pdf

计算机操作系统实验教程 计算机操作系统实验教程 徐 慧 中国矿业大学（北京）机电与信息工程学院计算机系 二 0 0 四年四月 实验简介实验简介.2 实验一实验一 进程管理进程管理.3 一、实验目的.3 二、实验预备内容.3 三、实验内容.3 四、预备知识.3 五 实验指导.4 实验二实验二 进程间的通信进程间的通信.5 一、实验目的.5 二、实验预备内容.5 三、实验内容.5 四、实验预备知识.5 五、实验指导.9 实验三实验三 存储管理存储管理.10 一、实验目的.10 二、实验内容.10 三、实验预备知识.10 四、实验指导.13 实验四实验四 文件系统设计文件系统设计.14 一、实验目的.14 二、实验内容.14 三、实验提示.14 四、实验指导.14 1实验简介 实验简介 1学时：16 学时 2先修课程：计算机导论 ，高级语言程序设计，数据结构 3课程性质：专业基础必修课 4适合专业：计算机科学与技术 5内容简介：操作系统上机课程通 Linux 操作系统各自的编程接口，提供编程实例，由此加深学生对操作系统工作原理的领会和对操作系统实现方法的理解，并且使学生在程序设计方面得到基本的训练。上机课程主要针对课本重点内容，以提高学生的动手能力，加深学生对相关的内容的理解而展开的实验课程。在 Linux 环境下提供了关于操作系统的命令接口程序 shell 的编制、存储管理相关内容的实路、作业调研系统以及虚拟磁盘文件系统管理 4 个实验。实验环境是基于 Linux 操作系统的。在计算机软硬件课程的设置上，它起着承上启下的作用。其特点是概念多、较抽象和涉及面广，其整体实现思想和技术又往往难于理解。6参考书：张尧学，史美林 计算机操作系统课程设计实验指导 清华大学出版社 2000 年 2实验一 进程管理 实验一 进程管理 一、实验目的一、实验目的(1)加深对进程概念的理解,明确进程的程序的区别;(2)可进一步认识并发执行的实质;(3)分析进程争用资源的现象,学习解决进程互斥的方法;(4)了解 LINUX 系统中进程通信的进本原理;二、二、实验预备内容实验预备内容(1)阅读 LINUX 的 sched.h 源码文件,加深对进程管理概念的理解;(2)阅读 LINUX 的 fork.c 源码,分析进程的创建过程;三、三、实验内容实验内容(1)进程创建 编写一段程序,使用系统调用 fork()创建两个子进程.(2)进程的控制 修改以编写的程序,将每个进程输出一个字符改为输出一句话,观察程序执行时屏幕上出现的现象;(3)编写一段程序实现软中断;(4)进程的管道通信;四、四、预备知识预备知识 现代操作系统的重要特点是程序的并发执行，及系统所拥有的资源被共享和系统用户随机地使用系统。采用一个什么样的概念，来描述计算机程序的执行过程和作为资源分配的基本单位才能充分反映操作系统的执行并发、资源共享及用户随机的特点呢？这个概念就是进程。1进程的概念 1.1 进程的定义 进程是一个具有一定功能的程序关于某个数据集合的一次运行活动。进程是操作系统动态执行的基本单元，在传统的操作系统设计中，进程既是基本的分配单元，也是基本的执行单元。1.2 进程划分的原则 3进程大小的“分割”设计，因不同的操作系统设计者而异。进程分得太大，极端情况就变成顺序执行的计算机，也就失去了并发性，也就降低了系统资源；但另一极端，进程分得太小，CPU 为多个用户或一个用户的多个任务服务时，开销急剧增大。因为，在进程间的时空转换及工作量将大大增 1.3 进程的五个基本特征 1动态性 进程是程序在并发系统的一次执行，一个进程有一个从产生到消失的生命期；2并发性 正是为了描述程序在并发系统内执行的动态特征才引入了进程，没有并发就没有进程；3独立性 每个进程的程序都是相对独立的顺序程序，可以按自己的方向和速度独立地向前推进；4制约性 进程之间的相互制约，主要表现在互斥地使用资源和相关进程之间必要的同步和通讯；5结构性 进程=PCB（进程控制块）+程序+数据集合。五五 实验指导实验指导 参考 P82 4实验二 进程间的通信 实验二 进程间的通信 一、实验目的一、实验目的 了解和熟悉 LINUX 支持的消息通信机制,共享存储区以及信息量机制。二、实验预备内容二、实验预备内容 阅读 LINUX 系统的 mdg.c,sem.c 和 shm.c 等源码文件,熟悉 LINUX 的三种通信机制。三、实验内容三、实验内容 (1)消息的创建,发送和接受;使用系统调用 msgget(),msgsnd(),msgrev(),以及 msgctl()编制一长度为 1k 的消息发送和接受程序;观察上面程序,说明控制消息队列系统调用 msgctl()在此起什么作用。(2)共享存储区的创建,附接和断接 使用系统调用 shmget(),shmget(),sgmdt(),shmctl(),编制一个与上述功能相同的程序。(3)比较上述(1),(2)两种消息通信机制中数据传输的时间。四、实验预备知识四、实验预备知识 进程通信 1:进程的同步与互斥 进程同步（1）进程同步的定义 进程同步是进程间共同完成一项任务是直接发生相互作用的关系，也就是说，这些具有伙伴关系的进程在执行时间次序上必须遵循确定的规律。(2）进程同步的例子 SPOOLing 系统中的输入功能可以由两个进程 A 和 B 完成，进程 A 负责从读卡机上把卡片上的信息读到一个缓冲区中，进程 B 负责把该缓冲 区中的信息进行加工并写 5到外存输入井中。要实现两者的协同工作，两个进程必须满足如下的制约关系：只有当缓冲区的内容取空时，进程 A 才能向其中写入新信息；只有当缓冲区写满时，进程 B才能从中取出内容作进一步加工和转送工作。可见，在缓冲区内容区空时，今晨 B 不应该继续运行，需要等待进程 A 向其中送入新的信息；反之，当缓冲区中的信息尚未取走时，进程 A 应等待，防止把原有的信息冲掉，造成丢失信息的结果。进程 A 和进程 B 就是一种同步关系。2 进程互斥 进程互斥的定义 一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。进程的互斥是因为对同一物理资源的竞争而产生的相互制约关系。进程互斥的例子 两个进程使用一台打印机 3 临界资源和临界区 我们包一次只允许一个进程使用的资源称为临界资源，而把在每个进程中访问临界资源的程序段称为临界区。要进入临界区的若干个进程必须满足如下关系：一次只允许一个进程进入临界区。任何时候，处于临界区的进程不得多于一个。进入临界区的进程要在有限的时间内退出。如果不能进入自己的临界区，则应让出处理机资源。4.同步、互斥机制的实现及应用 用锁操作原语实现互斥 （1）实现 为共享资源设置一把锁 W=0 表示共享资源（分配表）可用；W=1 表示共享资源（分配表）不可用，已有一进程访问。用类 ALGOL 语言编程如下：加锁原语 LOCK（W）L:if W=0 then W:=1 else goto L:（说明：测试和设置指令；循环等待该资源释放）6开锁原语 UNLOCK（W）W：=0 （2）局限性 只要有一个进程由于执行 LOCK（W）而进入临界区，则其它进程在检查锁状态时都将反复执行 LOCK（W）原语，从而导致处理机繁忙。现在一般采用硬件指令来解决互斥进入临界区问题。5.信号量及 P、V 操作原语 P、V 操作是荷兰科学家 E.W.Dijkstra 在 1965 年提出的一种解决同步、互斥问题的更通用的方法，并在 THE 操作系统中得以实现。P 是荷兰语发信号的开头字母，V 是等待的开头字母。(1)信号量 信号量，也叫信号灯，一般是由两个成员组成的数据结构，其中一个成员 S 是整型变量，表示该信号量的值，另一个成员 Q 是指向 PCB 的队列。=（S，Q）信号量的值与相应资源的使用状态有关。当它的值0 时，它表示可用资源的数量；当它的值=0 说明当前进程 q 有资源可执行；S0，则该进程继续运行；如果 S=0，则释放信号队列上的第一个 PCB（即信号量指针所指向的 PCB）所对应的进程（把阻塞态改为就绪态），执行 V 操作的进程继续运行。6.用 P、V 原语实现进程互斥 用 P、V 原语实现两并发进程 PA，PB 互斥的描述如下：设 sem 为互斥信号量，其取值范围为（1，0，-1）。其中 sem=1 表示进程 PA，PB 都未进入临界区 S，sem=0 表示进程 PA 或 PB 已进入临界区 S，sem=-1 表示进程 PA 和 PB 中，一个进程已进入临界区，而另一个进程等待进入临界区。描述：PA：P(sem)V(sem).PB：P(sem)V(sem 7生产者消费者问题 把并发进程的同步和互斥问题一般化，可以得到一个抽象的一般模型，即生产者消费者问题。计算机系统中，每个进程都申请使用和释放各种不同类型的资源，这些资源即可以是象外设、内存及缓冲区等硬件资源，也包括临界区、数据、例程等软件资源。我们把系统中使用某一类资源的进程称为该资源的消费者，而把释放同类资源的进程称为该资源的生产者。设有若干个生产者进程 P1，P2，.PN，若干个消费者进程 C1，C2，CM，它们通过一个有界缓冲池联系起来。8为了描述生产者消费者问题，可以设置若干个信号量（semaphore）:full,empty 和 mutex。其中 mutex 是互斥信号量，full,empty 是同步信号量。编程示意如下：semaphore full=0;semaphore empty=0;semaphore mutex=1;/*生产者*/P(empty);P(mutex);/*送数据入缓冲区某单元*/V(mutex);V(full);/*消费者*/P(full);P(mutex);/*取缓冲区中某单元数据*/V(mutex);V(empty);说明：（1）它是一个同步问题（a）消费者想要接收一个数据时，有界缓冲区中至少有一个单元是满的；（b）生产者想要发送一个数据时，有界缓冲区至少有一个是空的。（2）它是一个互斥问题 由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进程必须互斥执行。五五、实验指导、实验指导 参考实验课本 P90 9实验三 存储管理 实验三 存储管理 一、实验目的一、实验目的 通过请求页式存储管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求式页式存储管理的页面置换算法 二、实验内容二、实验内容 (1)通过随机数产生一个指令序列,共 320 条指令.指令的地址按下述原则生成:50%的指令是顺序执行的;25%的指令是均匀分布在前地址部分;25%的指令是均匀分布在后地址部分;(2)将指令序列变换为页地址流 设:页面大小为 1k;用户内存容量为 4 页到 32 页;用户虚存容量为 32k;(3)计算并输出下述各种算法在不同内存容量下的命中率 先进先出算法(FIFO);最近最少使用算法(LRR);最佳淘汰算法(OPT);最少访问页面算法(LFR);最近最不经常使用算法(NUR);三、实验预备知识三、实验预备知识 1请求页式存储管理 分区存储管理尽管实现方式简单，但存在着严重的碎片问题使得内存的利用率不高。再者，分区管理时，由于各作业或进程对应不同的分区以及在分区内各作业或进程连续存放，进程的大小仍受分区大小或内存可用空间的限制。为此提出了页式存储管理。10页式存储管理可分为静态页式管理和动态页式管理，而动态页式管理又分为请求页式管理和预调入页式管理。本章介绍动态页式管理的请求页式管理。实现原理：1划分实页 将物理内存划分成位置固定、大小相同的“块”（实页面）。其特点是：分页是为了管理，物理内存没有按用户作业分区的概念，分页仅仅是为了信息管理构造用，为了便于提高工作效率；用户不可见，物理内存也没有真正隔离，即“虚拟”的隐分页，一页中的地址必须连续；分页是一种物理划分而不是逻辑划分单位，因此，页的共享有困难。2划分虚页 将用户逻辑地址空间也分成同样大小的页面，成为虚拟空间的虚 页面，其特点是：用户可用地址大小受物理地址大小以及地址总线的限制；虚页号可大于实页号；从概率来看有半页浪费，因为可能遇到只有一个字节也要占一 页。3建立页表 建立页表，有时称为页面表或页面映射表（PMT）。每个作业一张，按虚页号进行登记，其基本的内容有特征位（表示该页是否在内存、实页号以及对应外存的地址.4地址变换 将虚页面的逻辑地址转化为实页面的物理地址，在程序执行时改变为物理地址，属于作业的动态重定位，一般由地址转换机构（硬件）完成。5页表的设计 分区存储管理技术提供三种表格进行存储管理，分别为存储分块表、作业表和页表。1存储分块表 11 整个系统一张，记录整个内存的使用情况，如，内存目前空白块总块数以及指向第一空白块的指针。主要有位示图和空白块链两种方法。2作业表 整个系统一张，每个作业占一个表项.2请求淘汰换页算法 1分页存储管理要解决的问题 分页存储管理只让进程或作业的部分程序和数据驻留在内存中，因此，在执行过程中，不可避免地会出现某些虚页不在内存中的问题。请求页式管理必须解决的两个基本问题是：1.怎样发现这些不在内存中的虚页；2.怎样处理这种情况（采用何种方法把所缺的页调入内存，以及当内存中没有空闲页面时怎么办），1 的解决是通过在页表中设置中断位及虚页在外存中的始址来处理的；2 的解决就涉及到淘汰换页算法。请求淘汰换页算法：（1）先进先出算法（first input first output,FIFO）先进入内存的页面先淘汰。实现是在页表中登记进入的次序，并将各个已分配的页面按分配时间顺序连接起来，组成 FIFO 队列。优点是实现简单，缺点是遇到常用的页效率低下，并可能产生 Belady 现象（所谓 Belady 现象是指分配的页面数增多，缺也次数反而增加的现象）。(2)循环检测法 让循环多的页面留驻内存，计算机采用记录页面住留内存期间对该页的访问时间，t 为该页上一次访问时间，T 为该页第二次访问时间，选用相对时间（t-T）最大的淘汰。优点是适合循环多的大程序；缺点是系统开销大。(3)最近最少使用页面先淘汰（least recently useed,LRU）该算法的基本思想是：当要淘汰某页时，选择离当时时间最近的一段时间内最久没有使用过的页面先淘汰。该算法的出发点是，如果某页被访问了，则可能它马上还要被访问，或者反过来说，如果某页面很长时间未被访问，则它在最近一段时间也不会被访问。LRU 的实现是一件十分困难的事情，我们一般采用它的近似算法。(4)最不经常使用的页面先淘汰（least frequent used,LFU）12该算法在需要淘汰某一页时，首先淘汰到当前时间为止，被访问次数最少的那一页。这只要在页表中给每一页增设一个访问计数器即可实现。每当该页被访问时，访问计数器加 1，而发生一次缺页中断时，则淘汰计数值最小的那一页，并将所有的计数器清零。（5）最近没有使用的页面先淘汰（not used recently,NUR）它是上述算法的一种简化，利用在页表中设置一个访问位即可实现，当某页被访问时，访问位置“1”，否则访问位置“0”当需要淘汰一页时，从那些访问位为“0”的页中选一页进行淘汰。系统周期性地对所有访问位清零。(6)随机数淘汰页面算法（random replacement algorithm）在系统设计人员无法确定那些页的访问概率较低时，随机地选择某个用户的页面进行淘汰也是一种方法。(7)最优淘汰算法（optimal replacement algorithm,OPT）它是一种理想的淘汰算法，系统预测作业今后要访问的页面，淘汰页是将来不被访问的页面或者最长时间后才能被访问的页面。这种算法是无法实现的，因为它要求必须预先知道每个进程的访问串。四、实验指导四、实验指导 参考:P 9 3 13实验四 文件系统设计 实验四 文件系统设计 一、实验目的一、实验目的 通过一个简单多用户文件系统的设计,加深理解文件系统的内部功能以及内部设计.二、实验内容二、实验内容 为 LINUX 系统设计一个简单的二级文件系统.要求做到一下几点:(1)可以实现下列几条指令 Login Dir Create Delete open Close Read write (2)列目录时要列出文件,物理地址,保护码和文件长度;(3)原文件可以进行读写保护;三、实验提示三、实验提示 (1)首先应确定文件系统的数据结构:主目录,子目录以及活动文件.(2)用户创建的文件,可以编号存储与磁盘上.如:FILE0,FILE1,FILE2并以记号作为物理地址,在目录中进行登记 四、实验指导四、实验指导 参考 P103 14 计算机操作系统实验讲义 二 0 0 四年四月印 计算机操作系统实验讲义 二 0 0 四年四月印 15