Good Morning Everyone!!!
软件课程设计III 指导老师:王晓峰、邹建伟
课程设计目的
操作系统是一门实践性很强的课程。如 果只学习操作系统原理(概念)而不进 行操作系统的具体设计实践,是很难真 正掌握操作系统这门课程的精髓
会写程序、写好程序
2.62
2016年9月 ©2015邹建伟制作 版权所有
课程设计实践平台
Windows 2000/XP/Vista/7/8/10 Linux*
使用的编程语言:C/C++
3.62
2016年9月 ©2015邹建伟制作 版权所有
相关内容
进程、线程的创建与使用 存储管理
I/O管理
文件系统
系统安全
4.62
2016年9月 ©2015邹建伟制作 版权所有
核心内容
线程
– 多核处理器
– “常规”而不是“先进”工作
SMP
CPU
CPU
系统总线
5.62
2016年9月 ©2015邹建伟制作 版权所有
内存
时间、地点安排
学分:2学分,必修。如果不通过,只能重修, 没有补考。
软件课程设计答疑及答辩时间:第8~13周 (10月10日~11月18日)
– 每周三下午2:00~4:30邹建伟老师答疑及答辩 – 每周五下午2:00~4:30王晓峰老师答疑及答辩
提交作业截止时间:
– 2016年11月16(邹建伟老师的学生)/18(王晓峰
老师的学生)日下午5:00之前。
答疑、交报告及答辩地点:计算机学院机房
6.62
2016年9月 ©2015邹建伟制作 版权所有
课程设计的要求(20%) 1.认真、独立(非小组)完成实践内容
2.按时、按要求提交源程序、测试数据和 课程设计报告 (包含以下4项):
– 1程序源代码
– 2测试数据
– 3实践报告Word文档
– 4软件课程设计III成果资料封面(Word文 档)
7.62
2016年9月 ©2015邹建伟制作 版权所有
实践报告要求
1基本信息
2实践内容简要描述
3实践报告主要内容
4实践结果
5实践体会
6附件:参考文献
详见“实践报告要求 .pdf”
8.62
2016年9月 ©2015邹建伟制作 版权所有
成绩评定
成绩评定方式:
– 自评与教评行结合
– “良”以上需要答辩(质疑),发现COPY即 为“不及格”,评定为优良的同学需要妥善保 管你的成果。
– 评优的比例为全部学生数的20%以下,先来 先得, “中”以“及格”的区别以学习态度、任 务完成情况、代码质量和文档规范程度加以 区分。评中或及格的同学无需当面答辩。
9.62
2016年9月 ©2015邹建伟制作 版权所有
提交
将封面、报告、源程序及测试数据打包 COPY到实验室指定的电脑中。
– 具体要求详见“老师的要求” 文档
10.62
2016年9月 ©2015邹建伟制作 版权所有
课程设计目的
(1) 了解Windows操作系统的基本结构 (2) 了解Windows操作系统的“对象”
(3) 学会在Win32环境下,创建进程和 线程
(4) 学会在Win32环境下,采用不同的 “对象”解决临界区问题和有限缓冲区问题
(5) 实现P、V操作
11.62
2016年9月 ©2015邹建伟制作 版权所有
相关操作系统理论知识
进程和线程
同步和互斥机制及实现方法
临界区
Dijkstra的信号量机制
– 利用二值信号量实现信号量的方法
设备文件* 12.62
2016年9月 ©2015邹建伟制作 版权所有
单线程和多线程进程
13.62
2016年9月 ©2015邹建伟制作 版权所有
进程与线程的区别
14.62
2016年9月 ©2015邹建伟制作 版权所有
线程的实现方法
– 用户级线程
内核仅支持进程模型,不支持线程
模型(以进程为调度单位)
– UNIX、Linux:POSIX 1003.1C
– 内核级线程
内核不仅支持进程模型,同时也支 持线程模型(以进程为资源分配单 位,以线程为调度单位 )
15.62
2016年9月 ©2015邹建伟制作 版权所有
多线程模型
多对一:用户级线程
一对一:每个用户级线程都对应一 个核心级线程(内核级线程),如 Windows、Solaris、OS/2等
多对多:一个或多个用户级线程都 对应一个核心级线程(内核级线 程),如Solaris版本9及以前的版 本
16.62
2016年9月 ©2015邹建伟制作 版权所有
17.62
2016年9月 ©2015邹建伟制作 版权所有
一对一模型
Windows 2000/XP的构成
18.62
2016年9月 ©2015邹建伟制作 版权所有
Windows环境子系统
提供Windows应用程序接口,为应用程
序提供服务。
– 基于Windows环境程序开发角度来理解: Windows环境子系统提供API(32/64)函数 调用
Win32子系统动态连接库(如: KERNEL32.DLL、USER32.DLL、 GD132.DLL和Advapi32.DLL)实现 Win32API函数。
19.62
2016年9月 ©2015邹建伟制作 版权所有
Windows API
Windows 应用程序编程接口(Windows application programming interface,Windows API)是为在Windows操作系统上运行的应用 程序合法使用计算机资源而提供一组可被应用 程序调用的函数集合。
依据不同性质的应用程序,Windows提供多种层次、 多种形式的调用界面。
– C/C++ – C#
– VB
– 等等
20.62
2016年9月 ©2015邹建伟制作 版权所有
Windows API
Windows API是Microsoft为Windows操作系统 家族(包括Windows 10 、Windows 8、 Windows 7、Windows Vista、、Windows XP、 Windows 2000、Windows Millennium Edition (Me)、Windows98、Windows95、Windows Sever 家族、Windows CE和Windows phone) 定义的编程接口,但是在这个家族中不同种类 的操作系统上实现的可能只是这个Windows API的不同子集。
Windows API的32位版称为Win32 API。
21.62
2016年9月 ©2015邹建伟制作 版权所有
Windows API
在Windows API中,定义了上万个函数调用接 口,这些函数目前微软将他们划分为以下几大
主要类别:
– Windows and Windows Phone
– MicrosoftAzure
– Office
– Development Tools and Languages – Server and Enterprise
– Services 22.62
2016年9月 ©2015邹建伟制作 版权所有
Windows API
Microsoft的Platform Software Development Kit(SDK)文档,是描述 Windows API的官方文档。这个文档可以 在http://msdn.microsoft.com上免费访问, 也可以在Microsoft为了方便程序员编程 而发布的各级别Microsoft Developer Network(MSDN)找到。
23.62
2016年9月 ©2015邹建伟制作 版权所有
Windows的对象 对象描述资源
– 当一个应用程序从操作系统获得资源时,资源 总是以某个(某种)对象的形式体现出来,或 者说某个(某种)对象呈现了某种系统资源的 状况。
应用程序通过使用环境子系统实现的对象 来使用系统资源。
– 如:同步操作并影响线程调度。调度对象包括 内核线程、互斥体(Mutex)、事件(Event)、 内核事件对、信号量(Semaphore)、定时器和 可等待定时器
25.62
2016年9月 ©2015邹建伟制作 版权所有
执行体对象
执行体对象和对象服务是环境子系统用于构建 其对象和其它资源的基础。
执行体对象对于环境子系统来说是机制, Windows环境子系统使用执行体对象导出它自
己的对象集合,其中许多对象直接对应于执行
体对象。
执行体对象只能通过Windows API合法使用
在核心态空间实现,所以有些资料称其为内核 对象,下面所述的“内核对象”即为“执行体 对象”的同义语
实现对资源的两级保护
26.62
2016年9月 ©2015邹建伟制作 版权所有
主要的执行体对象:
– Oject directory
– Symbolic link
– Process
– Thread
– Job
– Section
– File
– Access Token
– Event
– Semaphore
– Mutant
– Timer
– IoCompletion
– Key
– Profile
– WindowStation
– Desktop:
27.62
2016年9月 ©2015邹建伟制作 版权所有
执行体对象
使用对象
– Create
输入参数:对象名、安全属性及其它参数 输出参数:对象句柄(handle)和对象ID
– 通过句柄使用对象
– 获得已创建对象的句柄: Open
创建对象
28.62
2016年9月 ©2015邹建伟制作 版权所有
Handle、Handle表和Handle描 述符
handle是一个存在于用户空间下的数据结 构,通过它来访问NT 执行体内的一个数 据结构——handle表。handle表中的一个 表项称为一个handle描述符,handle描述 符是用来记录内核对象相关信息的数据 结构。
29.62
2016年9月 ©2015邹建伟制作 版权所有
Handle、Handle表和Handle描 述符
30.62
2016年9月 ©2015邹建伟制作 版权所有
安全属性
Create
31.62
2016年9月 ©2015邹建伟制作 版权所有
安全属性
如果系统安全机制认可了请求的访问权 限,它会返回一个访问权限集合,对象 管理器会将这个权限集合保存到这个进 程之handle表中的handle描述符中。以后, 当这个进程中的线程使用这个handle时, 在内核代码使用这个handle描述符去访问 对象之前,会把线程提交的访问权限集 合与存储在handle表的权限集合进行对比, 以决定是否允许线程访问该对象。
32.62
2016年9月 ©2015邹建伟制作 版权所有
Win 32中与进程控制有关的主 要API函数
CreateProcess OpenProcess ExitProcess
CloseHandle
33.62
2016年9月 ©2015邹建伟制作 版权所有
创建进程的方法
参见例子sm1
34.62
2016年9月 ©2015邹建伟制作 版权所有
任务1 命令解释器的实现(10%) 将batch文件中所列的应用程序启动运行
(批处理)
提交的程序名:ex1
测试数据(batch文件中的内容 for Windows 10):
C:\windows\notepad.exe
C:\windows\system32\calc.exe
C:\windows\write.exe
35.62
2016年9月 ©2015邹建伟制作 版权所有
Win32中与线程控制有关的主要 API函数
CreateThread
ExitThread
Sleep
SuspendThread ResumeThread
36.62
2016年9月 ©2015邹建伟制作 版权所有
线程编程模型
37.62
2016年9月 ©2015邹建伟制作 版权所有
创建线程的方法
参见sm2、sm3、sm4和sm5
38.62
2016年9月 ©2015邹建伟制作 版权所有
协作线程—兄弟问题 设置竞争条件 :
– 定义两个全局变量:accnt1和 accnt2,初值 都为零;
– 创建两个线程acc1和acc2:
(1)获得一个随机数;
(2)从accnt1减去这个随机数;
(3)将这个随机数加到accnt2中;
(4)正确的话,accnt1+accnt2=0
– 参见:sm6(该程序代码目前是不正确的,
即不能保证 accnt1+accnt2=0 )
39.62
2016年9月 ©2015邹建伟制作 版权所有
任务2:(20%)
用软件方法解决上述临界区问题—兄弟问题,
即要求修改sm6,实现 accnt1+accnt2=0 。 提交的程序名:ex2
采用的算法可选择: – Peterson算法:
参考文献[1]:7.2.1.3 Algorithm 3 ( Peterson算法)
参考文献[2]:6. 3 Peterson算法 – Dekker算法:
参考文献[1]: Exercises 7.4 参考文献[2]: Exercises 6.1
40.62
2016年9月 ©2015邹建伟制作 版权所有
Peterson算法
boolean flag[2]; //初值false int turn;
do {
flag [i]= true;
turn = j;
while (flag [j] and turn == j) ;
临界区; flag [i] = false;
剩余区; } while (1);
41.62
2016年9月 ©2015邹建伟制作 版权所有
使用Windows对象解决临界区问 题
Windows执行体对象:
– 互斥对象(Mutex)
– 事件对象(Event)
– 信号量对象(Semaphore)
Windows子系统对象
– 临界区(Critical Section)
42.62
2016年9月 ©2015邹建伟制作 版权所有
事件对象(Event)
事件对象相当于”触发器”,可通知一个或 多个线程某事件的出现,称为“有信号状 态”。
事件有两种状态:
– 有信号状态:等待的事件已出现 – 无信号状态:等待的事件未出现
43.62
2016年9月 ©2015邹建伟制作 版权所有
事件对象(Event)
事件是一种实现线程同步的机制。事件 提供了一个重要的附加性能,即当一个 事件变成有信号状态时,可以从一个等 待队列中同时释放一个或多个线程。
44.62
2016年9月 ©2015邹建伟制作 版权所有
事件对象(Event)
事件可分为两类:
自动重置(清除)事件:一旦事件成为有信号 状态且被处理后(通过调用 WaitForSingleObject或WaitForMultipleObject函 数),将自动恢复到无信号状态;
人工重置(清除)事件:事件成为有信号状态 且被处理后(通过调用WaitForSingleObject或 WaitForMultipleObject函数),不会自动恢复 到无信号状态,即依然保持在有信号状态,除 非人工设置为无信号状态(通过调用 ResetEvent函数)。
45.62
2016年9月 ©2015邹建伟制作 版权所有
事件对象(Event)
相关API包括:
CreateEvent创建一个事件对象,返回对象句柄;
OpenEvent返回一个已存在的事件对象的句柄,用于后 续访问;
SetEvent和PulseEvent设置指定事件对象为有信号状态;
ResetEvent设置指定事件对象为无信号状态;
ReleaseEvent销毁事件对象,释放事件对象占用的资源
使用事件对象的例子:sm4
46.62
2016年9月 ©2015邹建伟制作 版权所有
互斥对象(Mutex)
互斥对象的语义类似互斥信号量,用于实现一
个资源在一个时刻只能被一个线程使用
相关Win32 API函数:
– CreateMutex创建一个互斥对象,返回对象句柄;
– OpenMutex返回一个已存在的互斥对象的句柄,用 于后续访问;
– ReleaseMutex销毁互斥对象,释放互斥对象占用的 资源;
47.62
2016年9月 ©2015邹建伟制作 版权所有
信号量对象(Semaphore)
信号量对象的取值在0到指定最大值之间,
用于限制并发访问的线程数 相关Win32 API函数:
– CreateSemaphore创建一个信号量对象,指 定最大值和初值,返回对象句柄;
– OpenSemaphore 返回一个已存在的信号量对 象的句柄,用于后续访问;
– ReleaseSemaphore销毁信号量对象,释放信
号量对象占用的资源;
48.62
2016年9月 ©2015邹建伟制作 版权所有
同步等待对象
对于上述同步对象,Windows API提供了 两个统一的等待信号操作函数:
– WaitForSingleObject在指定的时间内等待单 个指定对象
– WaitForMultipleObjects在指定的时间内等待 多个制定对象;
49.62
2016年9月 ©2015邹建伟制作 版权所有
临界区(Critical Section) 只能用于在同一进程内使用的临界区,
同一进程内各线程对它的访问是互斥进 行的。把变量说明为 CRITICAL_SECTION类型,就可作为临 界区使用。
50.62
2016年9月 ©2015邹建伟制作 版权所有
临界区(Critical Section)
相关Win32 API函数:
– InitializeCriticalSection对临界区对象进行初始化;
– EnterCriticalSection等待进入临界区的授权,得到授 权后该函数返回;
– TryEnterCriticalSection非等待方式申请进入临界区 的授权;申请失败时,返回0;
– LeaveCriticalSection释放临界区的使用权;
– DeleteCriticalSection释放与临界区对象相关的所有
系统资源。 51.62
2016年9月 ©2015邹建伟制作 版权所有
使用临界区和互斥对象的例子
读者-写者问题:读者优先,参看sm5
W riter
wait(Wmutex); write;
signal(Wmutex);
参见sm5
wait(Rmutex);
if (Rcount == 0)
wait(Wmutex); ++Rcount;
signal(Rmutex); read;
wait(Rmutex); –Rcount;
if (Rcount == 0)
signal(Wmutex); signal(Rmutex);
Reader
52.62
2016年9月 ©2015邹建伟制作 版权所有
任务3 (20%)
使用上述Win32所提供的同步对象中的任 意一种解决兄弟问题,使用其中一种完 成即可。
题目:使用Win32所提供的同步对象解决 兄弟问题
提交程序名:ex3
53.62
2016年9月 ©2015邹建伟制作 版权所有
任务4 (15%)
用Win32所提供的同步对象解决有限缓冲
区问题 (生产者-消费者问题)
– 写一个多线程实现C/C++语言程序:一些线 程负责找出某个数据范围的素数,并放到一 个数组中,另一些线程负责将数组中的素数 按次序取出,并显示出来。
– 要求定义一个全局变量的数组:int prime[9] 用于存放找到的待显示的素数,要理解成 “环形缓冲区”。
54.62
2016年9月 ©2015邹建伟制作 版权所有
任务4:生产者-消费者问题(the producer-consumer problem)
55.62
©20015 邹建伟制作 版权所有
任务4:生产者-消费者问题(the producer-consumer problem)
• 生产者:
• wait (empty);
• wait (mutex);
• buffer[in]=x;
• in=(in+1)%N;
• signal (mutex);
• signal (full);
消费者:
– wait(full);
– wait(mutex);
– nextc=buffer[out]; – out=(out+1)%N;
– signal(mutex);
– signal(empty);
57.62
任务4 (15%)
提交程序名ex4
测试数据文件名:ex4.dat
测试数据示例 : – 1 W 10 100
– 2 W 1 10 – 3D 3 0
说明:线程ID、线程角色(D-显示结果线程、 W-找素数线程)、搜寻素数的范围或显示素数 的个数(此时,仅“D”后面的第一个数字有效, 第二个数字必定为0)
58.62
2016年9月 ©2015邹建伟制作 版权所有
任务4 (15%) 要求:
– 使用“生产者-消费者”算法
找素数线程每次只能放入一个素数 显示线程每次只能取一个素数
– 该题目的难点在于:
找素数线程如何知道显示线程已经结束(如果结束它自身
也要结束,此时缓冲区是满的)
显示线程如何知道找素数线程已经结束(如果结束它自身
也要结束,此时缓冲区是空的)
– 可以将找素数线程和显示线程分别在两个不同的进
程中实现或在一个进程内实现
59.62
2016年9月 ©2015邹建伟制作 版权所有
任务5 (15%)
用Win32所提供的同步对象实现你自己的 P、V操作,并使用它们并解决读者-写着 问题。
使用信号量对象或事件对象来实现比较 方便
参考算法:参考文献[1]:7.4.4 Binary Semaphores
提交程序名:ex5
60.62
2016年9月 ©2015邹建伟制作 版权所有
使用二进制信号量实现信号量
binary-semaphore S1, S2; //初值:S1=1,S2=0 int C;//初值:资源数目
wait(或P)操作: wait(S1);
C – -;
if (C < 0) {
signal(S1); } wait(S2);
signal(S1);
signal (或V)操作: wait(S1);
C ++;
if (C <= 0)
signal(S2);
else
signal(S1);
61.62
2016年9月
©2015邹建伟制作 版权所有
参考文献
[1] Abraham Silberschatz ,Peter Baer Galvin and Greg Gagne. Operating System Concepts ,6th Edition(影印版). 北京: 高等教育出版社. 2002
[2] Abraham Silberschatz ,Peter Baer Galvin and Greg Gagne. Operating System Concepts ,Seventh Edition(影印版). 北 京:高等教育出版社. 2007
62.62
2016年9月 ©2015邹建伟制作 版权所有