哲学家就餐问题的算法实现

*** 作系统并发和互斥：哲学家进餐问题和理发师问题

1． 哲学家进餐问题：

(1) 在什么情况下5 个哲学家全部吃不上饭？

考虑两种实现的方式，如下：

A.

算法描述：

void philosopher(int i) /*i：哲学家编号，从0 到4*/

{

while (TRUE) {

think( )/*哲学家正在思考*/

take_fork(i)/*取左侧的筷子*/

take_fork((i+1) % N)/*取左侧筷子；％为取模运算*/

eat( )/*吃饭*/

put_fork(i)/*把左侧筷子放回桌子*/

put_fork((i+1) % N)/*把右侧筷子放回桌子*/

}

}

分析：假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左侧筷子，

等一会儿，又同时拿起左侧筷子，如此这般，永远重复。对于这种情况，即所有的程序都在

无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。

B．

算法描述：

规定在拿到左侧的筷子后，先检查右面的筷子是否可用。如果不可用，则先放下左侧筷子，

等一段时间再重复整个过程。

分析：当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷

子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子……如此

这样永远重复下去。对于这种情况，所有的程序都在运行，但却无法取得进展，即出现饥饿，

所有的哲学家都吃不上饭。

(2) 描述一种没有人饿死（永远拿不到筷子）算法。

考虑了四种实现的方式（A、B、C、D）：

A．原理：至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释

放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以下将room 作为信号量，只允

许4 个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入

餐厅的哲学家进入room 的等待队列，根据FIFO 的原则，总会进入到餐厅就餐，因此不会

出现饿死和死锁的现象。

伪码：

semaphore chopstick[5]={1，1，1，1，1}

semaphore room=4

void philosopher(int i)

{

while(true)

{

think()

wait(room)//请求进入房间进餐

wait(chopstick[i])//请求左手边的筷子

wait(chopstick[(i+1)%5])//请求右手边的筷子

eat()

signal(chopstick[(i+1)%5])//释放右手边的筷子

signal(chopstick[i])//释放左手边的筷子

signal(room)//退出房间释放信号量room

}

}

B．原理：仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。

方法1：利用AND 型信号量机制实现：根据课程讲述，在一个原语中，将一段代码同时需

要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。当

某些资源不够时阻塞调用进程由于等待队列的存在，使得对资源的请求满足FIFO 的要求，

因此不会出现饥饿的情形。

伪码：

semaphore chopstick[5]={1，1，1，1，1}

void philosopher(int I)

{

while(true)

{

think()

Swait(chopstick[(I+1)]%5,chopstick[I])

eat()

Ssignal(chopstick[(I+1)]%5,chopstick[I])

}

}

方法2：利用信号量的保护机制实现。通过信号量mutex对eat（）之前的取左侧和右侧筷

子的 *** 作进行保护，使之成为一个原子 *** 作，这样可以防止死锁的出现。

伪码：

semaphore mutex = 1

semaphore chopstick[5]={1，1，1，1，1}

void philosopher(int I)

{

while(true)

{

think()

wait(mutex)

wait(chopstick[(I+1)]%5)

wait(chopstick[I])

signal(mutex)

eat()

signal(chopstick[(I+1)]%5)

signal(chopstick[I])

}

}

C． 原理：规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子而偶数号

的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即

五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获

得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲

学家会较先可以吃饭，因此不会出现饿死的哲学家。

伪码：

semaphore chopstick[5]={1，1，1，1，1}

void philosopher(int i)

{

while(true)

{

think()

if(i%2 == 0) //偶数哲学家，先右后左。

{

wait (chopstick[ i + 1 ] mod 5)

wait (chopstick[ i])

eat()

signal (chopstick[ i + 1 ] mod 5)

signal (chopstick[ i])

}

Else //奇数哲学家，先左后右。

{

wait (chopstick[ i])

wait (chopstick[ i + 1 ] mod 5)

eat()

signal (chopstick[ i])

signal (chopstick[ i + 1 ] mod 5)

}

}

D．利用管程机制实现（最终该实现是失败的，见以下分析）：

原理：不是对每只筷子设置信号量，而是对每个哲学家设置信号量。test()函数有以下作

用：

a. 如果当前处理的哲学家处于饥饿状态且两侧哲学家不在吃饭状态，则当前哲学家通过

test()函数试图进入吃饭状态。

b. 如果通过test()进入吃饭状态不成功，那么当前哲学家就在该信号量阻塞等待，直到

其他的哲学家进程通过test()将该哲学家的状态设置为EATING。

c. 当一个哲学家进程调用put_forks()放下筷子的时候，会通过test()测试它的邻居，

如果邻居处于饥饿状态，且该邻居的邻居不在吃饭状态，则该邻居进入吃饭状态。

由上所述,该算法不会出现死锁，因为一个哲学家只有在两个邻座都不在进餐时，才允

许转换到进餐状态。

该算法会出现某个哲学家适终无法吃饭的情况，即当该哲学家的左右两个哲学家交替

处在吃饭的状态的时候，则该哲学家始终无法进入吃饭的状态，因此不满足题目的要求。

但是该算法能够实现对于任意多位哲学家的情况都能获得最大的并行度，因此具有重要

的意义。

伪码：

#define N 5 /* 哲学家人数*/

#define LEFT (i-1+N)%N /* i的左邻号码 */

#define RIGHT (i+1)%N /* i的右邻号码 */

typedef enum { THINKING, HUNGRY, EATING } phil_state/*哲学家状态*/

monitor dp /*管程*/

{

phil_state state[N]

semaphore mutex =1

semaphore s[N]/*每个哲学家一个信号量，初始值为0*/

void test(int i)

{

if ( state[i] == HUNGRY &&state[LEFT(i)] != EATING &&

state[RIGHT(i)] != EATING )

{

state[i] = EATING

V(s[i])

}

}

void get_forks(int i)

{

P(mutex)

state[i] = HUNGRY

test(i)/*试图得到两支筷子*/

V(mutex)

P(s[i])/*得不到筷子则阻塞*/

}

void put_forks(int i)

{

P(mutex)

state[i]= THINKING

test(LEFT(i))/*看左邻是否进餐*/

test(RIGHT(i))/*看右邻是否进餐*/

V(mutex)

}

}

哲学家进程如下：

void philosopher(int process)

{

while(true)

{

think()

get_forks(process)

eat()

put_forks(process)

}

}

2.理发师问题：一个理发店有一个入口和一个出口。理发店内有一个可站5 位顾客的站席

区、4 个单人沙发、3 个理发师及其专用理发工具、一个收银台。新来的顾客坐在沙发上等

待；没有空沙发时，可在站席区等待；站席区满时，只能在入口外等待。理发师可从事理

发、收银和休息三种活动。理发店的活动满足下列条件：

1）休息的理发师是坐地自己专用的理发椅上，不会占用顾客的沙发；

2）处理休息状态的理发师可为在沙发上等待时间最长的顾客理发；

3）理发时间长短由理发师决定；

4）在站席区等待时间最长的顾客可坐到空闲的理发上；

5）任何时刻最多只能有一个理发师在收银。

试用信号量机制或管程机制实现理发师进程和顾客进程。

原理：

(1)customer 进程：

首先检查站席区是否已满（stand_capacity）,若满选择离开，否则进入站席区，即进入

理发店。在站席区等待沙发的空位（信号量sofa），如果沙发已满，则进入阻塞等待队列，

直到出现空位，在站席区中等待时间最长的顾客离开站席区（stand_capacity）。坐到沙

发上，等待理发椅(barber_chair)，如果理发椅已满，则进入阻塞等待队列，直到出现

空位，在沙发上等待时间最长的顾客离开沙发（释放信号量sofa）。坐到理发椅上，释放

准备好的信号（customer_ready），获得该理发师的编号（0~1 的数字）。等待理发师理

发结束（finished[barber_number]）。在离开理发椅之前付款（payment），等待收据

(receipt)，离开理发椅（leave_barberchair）。最后离开理发店。

这里需要注意几点：

a) 首先是几个需要进行互斥处理的地方，主要包括:进入站席区、进入沙发、进入理发椅

和付款几个地方。

b) 通过barber_chair 保证一个理发椅上最多只有一名顾客。但这也不够，因为单凭

baber_chair 无法保证一名顾客离开理发椅之前，另一位顾客不会坐到该理发椅上，

因此增加信号量leave_barberchair，让顾客离开理发椅后，释放该信号，而理发

师接收到该信号后才释放barber_chair 等待下一位顾客。

c) 在理发的过程中，需要保证是自己理发完毕，才能够进行下面的付款、离开理发椅的活

动。这个机制是通过customer 进程获得给他理发的理发师编号来实现的，这样，当

该编号的理发师释放对应的finished[i]信号的时候，该顾客才理发完毕。

d) 理发师是通过mutex 信号量保证他们每个人同时只进行一项 *** 作（理发或者收款）。

e) 为了保证该顾客理发完毕后马上可以付款离开，就应该保证给该顾客理发的理发师在理

发完毕后马上到收银台进入收款 *** 作而不是给下一位顾客服务。在伪码中由以下机制实

现：即顾客在释放离开理发椅的信号前，发出付款的信号。这样该理发师得不到顾客的

离开理发椅的信号，不能进入下一个循环为下一名顾客服务，而只能进入收款台的收款

*** 作。直到顾客接到收据后，才释放离开理发椅的信号，离开理发椅，让理发师释放该

理发椅的信号，让下一位等待的顾客坐到理发椅上。

(2)barber 进程

首先将该理发师的编号压入队列，供顾客提取。等待顾客坐到理发椅坐好(信号量

customer_ready)，开始理发，理发结束后释放结束信号（finished[i]）。等待顾客

离开理发椅（leave_barberchair）（期间去收银台进行收款活动），释放理发椅空闲信

号(barber_chair)，等待下一位顾客坐上来。

(3)cash（收银台）进程

等待顾客付款(payment),执行收款 *** 作，收款 *** 作结束，给付收据（receipt）。

信号量总表：

信号量 wait signal

stand_capacity 顾客等待进入理发店 顾客离开站席区

sofa 顾客等待坐到沙发 顾客离开沙发

barber_chair 顾客等待空理发椅 理发师释放空理发椅

customer_ready 理发师等待，直到一个顾客坐

到理发椅

顾客坐到理发椅上，给理发师

发出信号

mutex 等待理发师空闲，执行理发或

收款 *** 作

理发师执行理发或收款结束，

进入空闲状态

mutex1 执行入队或出队等待 入队或出队结束，释放信号

finished[i] 顾客等待对应编号理发师理

发结束

理发师理发结束，释放信号

leave_barberchair 理发师等待顾客离开理发椅 顾客付款完毕得到收据，离开

理发椅释放信号

payment 收银员等待顾客付款 顾客付款，发出信号

receipt 顾客等待收银员收、开具收据收银员收款结束、开具收据，

释放信号

伪码：

semaphore stand_capacity=5

semaphore sofa=4

semaphore barber_chair=3

semaphore customer_ready=0

semaphore mutex=3

semaphore mutex1=1

semaphore finished[3]={0,0,0}

semaphore leave_barberchair=0

semaphore payment=0

semaphore receipt=0

void customer()

{

int barber_number

wait(stand_capacity)//等待进入理发店

enter_room()//进入理发店

wait(sofa)//等待沙发

leave_stand_section()//离开站席区

signal(stand_capacity)

sit_on_sofa()//坐在沙发上

wait(barber_chair)//等待理发椅

get_up_sofa()//离开沙发

signal(sofa)

wait(mutex1)

sit_on_barberchair()//坐到理发椅上

signal(customer_ready)

barber_number=dequeue()//得到理发师编号

signal(mutex1)

wait(finished[barber_number])//等待理发结束

pay()//付款

signal(payment)//付款

wait(receipt)//等待收据

get_up_barberchair()//离开理发椅

signal(leave_barberchair)//发出离开理发椅信号

exit_shop()//了离开理发店

}

void barber(int i)

{

while(true)

{

wait(mutex1)

enqueue(i)//将该理发师的编号加入队列

signal(mutex1)

wait(customer_ready)//等待顾客准备好

wait(mutex)

cut_hair()//理发

signal(mutex)

signal(finished[i])//理发结束

wait(leave_barberchair)//等待顾客离开理发椅信号

signal(barber_chair)//释放barber_chair 信号

}

}

void cash() //收银

{

while(true)

{

wait(payment)//等待顾客付款

wait(mutex)//原子 *** 作

get_pay()//接受付款

give_receipt()//给顾客收据

signal(mutex)

signal(receipt)//收银完毕，释放信号

}

}

分析：

在分析该问题过程中，出现若干问题，是参阅相关资料后才认识到这些问题的隐蔽性和严重

性的,主要包括：

（1）在顾客进程，如果是在释放leave_barberchair 信号之后进行付款动作的话，很

容易造成没有收银员为其收款的情形， 原因是： 为该顾客理发的理发师收到

leave_barberchair 信号后，释放barber_chair 信号，另外一名顾客坐到理发椅上，

该理发师有可能为这另外一名顾客理发，而没有为刚理完发的顾客收款。为解决这个问题，

就是采取在释放leave_barberchair 信号之前，完成付款 *** 作。这样该理发师无法进入

下一轮循环为另外顾客服务，只能到收银台收款。

（2）本算法是通过给理发师编号的方式，当顾客坐到某理发椅上也同时获得理发师的编号，

如此，当该理发师理发结束，释放信号，顾客只有接收到为其理发的理发师的理发结束信号

才会进行付款等 *** 作。这样实现，是为避免这样的错误，即：如果仅用一个finished 信

号量的话，很容易出现别的理发师理发完毕释放了finished 信号，把正在理发的这位顾

客赶去付款,而已经理完发的顾客却被阻塞在理发椅上的情形。当然也可以为顾客进行编

号，让理发师获取他理发的顾客的编号，但这样就会限制顾客的数量，因为finished[]

数组不能是无限的。而为理发师编号，则只需要三个元素即可。

3.参考文献：

左金平 计算机 *** 作系统中哲学家进餐问题探究。

参考教材 *** 作系统—内核与设计原理

前言

1 引言 1

1．1 什么是 *** 作系统? 3

1．1．1 所有延长机器的作业系统 4

1．1．2 作为一个资源管理器的作业系统 6

1．2 *** 作系统的历史 7

1．2．1 第一代（1945年至1955年）真空管 7

1．2．2第二代（1955年至1965年）晶体管和批处理系统 8

1．2．3 第三代（1965年至1980年）的集成电路 10

1．2 4 第四代（1980年至今）个人电脑 15

1．3计算机硬件检查 19

l．3．1处理器 19

1．3．2内存 23

1．3．3 磁盘 26

1．3．4 胶带 27

1．3．5 I/O设备 27 (I/O即输入输出)

1．3．6总线 30

1 3．7启动计算机 33

1．4 *** 作系统动物园 33

1．4．1大型机 *** 作系统 34

1．4．2 服务器 *** 作系统34

1．4．3多处理器的 *** 作系统 34

1．4．4个人电脑 *** 作系统 35

1．4．5掌上电脑 *** 作系统 35

1．4．6 嵌入式 *** 作系统． 35

1．4．7 传感器节点的 *** 作系统 36

1．4．8 实时 *** 作系统 36

1．4．9 智能卡 *** 作系统 37

1．5 *** 作系统的概念 37

1．5．1 流程 38

1．5．2 地址空间 40

1．5．3文件 40

1．5．4输入/输出 43

1．5．5保护 44

1．5．6 壳牌 44

1．5．7系统发育个体发育重演 46

1．6 系统调用 49

1．6．1 流程管理系统调用 52

1．6．2文件管理系统调用 56

1．6．3 目录管理系统调用 57

1．6．4杂项系统调用 58

1．6．5 在Windows的Win32 API 59

1．7 *** 作系统结构 62

1．7．1单片系统 62

1．7．2分层系统 63

1．7．3微内核 64

1．7．4 客户 - 服务器模型 67

1．7．5 虚拟机 67

1．7．6 出的内核 71

1．8 根据C的WORLD 72

1．8．1 C语言 72

1．8．2头文件 73

1．8．3大的编程项目 74

1．8．4运行时模型75

1．9 *** 作系统上的研究 76

1．10 本书的其余部分的概要 77

1．11 公制单位 78

1．12 概要 79

2进程和线程

2．1工序83

2．1．1 过程模型 84

2．1．2 进程创建 86

2．1．3 进程终止 88

2．1．4 流程层次结构 89

2．1．5 进程国家 90

2．1．6实施流程 91

2．1．7多多建模的建模 93

2．2 螺纹 95

2．2．1线程使用情况 95

2．2．2古典的线程模型 100

2．2．3POSIX线程 104

2．2．4在用户空间中实现的线程 106

2．2．5在内核中实现的线程 109

2．2．6混合实现 110

2．2．7调度激活 111

2．2．8 d出式线程 112

2．2．9 使单线程代码中使用多线程技术 114

2．3 进程间通信 117

2．3．1静态条件 117

2．3．2关键区域 119

2．3．3忙等待的互斥 120

2．3．4 睡眠和唤醒 125

2．3．5 信号灯 128

2．3．6互斥 130

2．3．7显示器 134

2．3．8消息传递 140

2．3．9 壁垒 144

2．4 调度 145

2．4．1调度 145

2．4．2 批处理系统的调度 152

2．4．3 调度互动系统 154

2．4．4 调度实时系统 160

2．4．5政策与机制 161

2．4．6 线程调度 162

2．5经典的IPC问题 163

2．5．1 哲学家就餐问题 164

2．5．2读者和作者的问题 167

2．6 进程和线程的研究 168

2．7概要169

习题95第3章 存储管理993.1 无存储器抽象993.2 一种存储器抽象：地址空间1013.2.1 地址空间的概念1013.2.2 交换技术1033.2.3 空闲内存管理1043.3 虚拟内存1063.3.1 分页1073.3.2 页表1083.3.3 加速分页过程1093.3.4 针对大内存的页表1113.4 页面置换算法1133.4.1 最优页面置换算法1143.4.2 最近未使用页面置换算法1143.4.3 先进先出页面置换算法1153.4.4 第二次机会页面置换算法1153.4.5 时钟页面置换算法1163.4.6 最近最少使用页面置换算法1163.4.7 用软件模拟lru 1173.4.8 工作集页面置换算法1183.4.9 工作集时钟页面置换算法1203.4.10 页面置换算法小结1213.5 分页系统中的设计问题1213.5.1 局部分配策略与全局分配策略1213.5.2 负载控制1233.5.3 页面大小1233.5.4 分离的指令空间和数据空间1243.5.5 共享页面1243.5.6 共享库1253.5.7 内存映射文件1263.5.8 清除策略1273.5.9 虚拟内存接口1273.6 有关实现的问题1283.6.1 与分页有关的工作1283.6.2 缺页中断处理1283.6.3 指令备份1293.6.4 锁定内存中的页面1293.6.5 后备存储1293.6.6 策略和机制的分离1303.7 分段1313.7.1 纯分段的实现1333.7.2 分段和分页结合：multics 1343.7.3 分段和分页结合：intel pentium 1353.8 有关存储管理的研究1383.9 小结138习题139第4章 文件系统1434.1 文件1444.1.1 文件命名1444.1.2 文件结构1454.1.3 文件类型1454.1.4 文件存取1474.1.5 文件属性1474.1.6 文件 *** 作1484.1.7 使用文件系统调用的一个示例程序1484.2 目录1504.2.1 一级目录系统1504.2.2 层次目录系统1504.2.3 路径名1504.2.4 目录 *** 作1524.3 文件系统的实现1534.3.1 文件系统布局1534.3.2 文件的实现1534.3.3 目录的实现1564.3.4 共享文件1584.3.5 日志结构文件系统1594.3.6 日志文件系统1604.3.7 虚拟文件系统1614.4 文件系统管理和优化1634.4.1 磁盘空间管理1634.4.2 文件系统备份1674.4.3 文件系统的一致性1704.4.4 文件系统性能1724.4.5 磁盘碎片整理1744.5 文件系统实例1754.5.1 cd-rom文件系统1754.5.2 ms-dos文件系统1784.5.3 unix v7文件系统1794.6 有关文件系统的研究1814.7 小结181习题182第5章 输入/输出1845.1 i/o硬件原理1845.1.1 i/o设备1845.1.2 设备控制器1855.1.3 内存映射i/o 1855.1.4 直接存储器存取1875.1.5 重温中断1895.2 i/o软件原理1915.2.1 i/o软件的目标1915.2.2 程序控制i/o 1925.2.3 中断驱动i/o 1935.2.4 使用dma的i/o1945.3 i/o软件层次1945.3.1 中断处理程序1945.3.2 设备驱动程序1955.3.3 与设备无关的i/o软件1975.3.4 用户空间的i/o软件2005.4 盘2015.4.1 盘的硬件2015.4.2 磁盘格式化2115.4.3 磁盘臂调度算法2125.4.4 错误处理2145.4.5 稳定存储器2165.5 时钟2185.5.1 时钟硬件2185.5.2 时钟软件2195.5.3 软定时器2205.6 用户界面：键盘、鼠标和监视器2215.6.1 输入软件2215.6.2 输出软件2245.7 瘦客户机2335.8 电源管理2355.8.1 硬件问题2355.8.2 *** 作系统问题2365.8.3 应用程序问题2395.9 有关输入/输出的研究2395.10 小结240习题241第6章 死锁2446.1 资源2446.1.1 可抢占资源和不可抢占资源2446.1.2 资源获取2456.2 死锁概述2466.2.1 资源死锁的条件2466.2.2 死锁建模2466.3 鸵鸟算法2486.4 死锁检测和死锁恢复2486.4.1 每种类型一个资源的死锁检测2496.4.2 每种类型多个资源的死锁检测2506.4.3 从死锁中恢复2516.5 死锁避免2526.5.1 资源轨迹图2526.5.2 安全状态和不安全状态2536.5.3 单个资源的银行家算法2546.5.4 多个资源的银行家算法2546.6 死锁预防2556.6.1 破坏互斥条件2556.6.2 破坏占有和等待条件2566.6.3 破坏不可抢占条件2566.6.4 破坏环路等待条件2566.7 其他问题2576.7.1 两阶段加锁2576.7.2 通信死锁2576.7.3 活锁2586.7.4 饥饿2596.8 有关死锁的研究2596.9 小结259习题260第7章 多媒体 *** 作系统2637.1 多媒体简介2637.2 多媒体文件..2667.2.1 视频编码2667.2.2 音频编码2687.3 视频压缩2697.3.1 jpeg标准2697.3.2 mpeg标准2717.4 音频压缩2727.5 多媒体进程调度2747.5.1 调度同质进程2757.5.2 一般实时调度2757.5.3 速率单调调度2767.5.4 最早最终时限优先调度2777.6 多媒体文件系统范型2787.6.1 vcr控制功能2797.6.2 近似视频点播2797.6.3 具有vcr功能的近似视频点播2817.7 文件存放2827.7.1 在单个磁盘上存放文件2827.7.2 两个替代的文件组织策略2827.7.3 近似视频点播的文件存放2847.7.4 在单个磁盘上存放多个文件2857.7.5 在多个磁盘上存放文件2877.8 高速缓存2887.8.1 块高速缓存2887.8.2 文件高速缓存2897.9 多媒体磁盘调度2907.9.1 静态磁盘调度2907.9.2 动态磁盘调度2917.10 有关多媒体的研究2927.11 小结292习题293第8章 多处理机系统2958.1 多处理机2968.1.1 多处理机硬件2968.1.2 多处理机 *** 作系统类型3018.1.3 多处理机同步3038.1.4 多处理机调度3068.2 多计算机3098.2.1 多计算机硬件3098.2.2 低层通信软件3128.2.3 用户层通信软件3138.2.4 远程过程调用3148.2.5 分布式共享存储器3168.2.6 多计算机调度3198.2.7 负载平衡3198.3 虚拟化3218.3.1 虚拟化的条件3228.3.2 i型管理程序3228.3.3 ii型管理程序3238.3.4 准虚拟化3248.3.5 内存的虚拟化3258.3.6 i/o设备的虚拟化3268.3.7 虚拟工具3278.3.8 多核处理机上的虚拟机3278.3.9 授权问题3278.4 分布式系统3278.4.1 网络硬件3298.4.2 网络服务和协议3318.4.3 基于文档的中间件3338.4.4 基于文件系统的中间件3348.4.5 基于对象的中间件3378.4.6 基于协作的中间件3388.4.7 网格3418.5 有关多处理机系统的研究3418.6 小结342习题343第9章 安全3469.1 环境安全3479.1.1 威胁3479.1.2 入侵者3479.1.3 数据意外遗失3489.2 密码学原理3489.2.1 私钥加密技术3499.2.2 公钥加密技术3499.2.3 单向函数3509.2.4 数字签名3509.2.5 可信平台模块3519.3 保护机制3529.3.1 保护域3529.3.2 访问控制列表3539.3.3 权能3549.3.4 可信系统3569.3.5 可信计算基3579.3.6 安全系统的形式化模型3589.3.7 多级安全3589.3.8 隐蔽信道3609.4 认证3629.4.1 使用口令认证3639.4.2 使用实际物体的认证方式3679.4.3 使用生物识别的验证方式3699.5 内部攻击3709.5.1 逻辑炸d3709.5.2 后门陷阱3709.5.3 登录欺骗3719.6 利用代码漏洞3719.6.1 缓冲区溢出攻击3729.6.2 格式化字符串攻击3739.6.3 返回libc攻击3749.6.4 整数溢出攻击3759.6.5 代码注入攻击3769.6.6 权限提升攻击3769.7 恶意软件3779.7.1 特洛伊木马3789.7.2 病毒3799.7.3 蠕虫3859.7.4 间谍软件3869.7.5 rootkit 3889.8 防御3909.8.1 防火墙3919.8.2 反病毒和抑制反病毒技术3929.8.3 代码签名3959.8.4 囚禁3969.8.5 基于模型的入侵检测3979.8.6 封装移动代码3989.8.7 java安全性4009.9 有关安全性研究4019.10 小结401习题402第10章 实例研究1：linux 40510.1 unix与linux的历史40510.1.1 unics 40510.1.2 pdp-11 unix 40610.1.3 可移植的unix 40610.1.4 berkeley unix 40710.1.5 标准unix 40710.1.6 minix 40810.1.7 linux 40910.2 linux概述41010.2.1 linux的设计目标41010.2.2 到linux的接口41110.2.3 shell 41210.2.4 linux应用程序41310.2.5 内核结构41410.3 linux中的进程41610.3.1 基本概念41610.3.2 linux中进程管理相关的系统调用41810.3.3 linux中进程与线程的实现42010.3.4 linux中的调度42410.3.5 启动linux系统42610.4 linux中的内存管理42710.4.1 基本概念42710.4.2 linux中的内存管理系统调用42910.4.3 linux中内存管理的实现43010.4.4 linux中的分页43410.5 linux中的i/o系统43510.5.1 基本概念43510.5.2 网络43610.5.3 linux的输入/输出系统调用43710.5.4 输入/输出在linux中的实现43710.5.5 linux中的模块43910.6 linux文件系统44010.6.1 基本概念44010.6.2 linux的文件系统调用44210.6.3 linux文件系统的实现44410.6.4 nfs：网络文件系统44910.7 linux的安全性45310.7.1 基本概念45310.7.2 linux中安全相关的系统调用45410.7.3 linux中的安全实现45510.8 小结455习题456第11章 实例研究2：windows vista 45911.1 windows vista的历史45911.1.1 20世纪80年代：ms-dos 45911.1.2 20世纪90年代：基于ms-dos的windows 46011.1.3 21世纪：基于nt的windows 46011.1.4 windows vista 46211.2 windows vista编程46211.2.1 内部nt应用编程接口46311.2.2 win32应用编程接口46511.2.3 windows注册表46711.3 系统结构46811.3.1 *** 作系统结构46911.3.2 启动windows vista 47611.3.3 对象管理器的实现47711.3.4 子系统、dll和用户态服务48311.4 windows vista中的进程和线程48411.4.1 基本概念48411.4.2 作业、进程、线程和纤程管理api调用48711.4.3 进程和线程的实现49011.5 内存管理49411.5.1 基本概念49411.5.2 内存管理系统调用49611.5.3 存储管理的实现49711.6 windows vista的高速缓存50211.7 windows vista的输入/输出50411.7.1 基本概念50411.7.2 输入/输出api调用50411.7.3 i/o实现50611.8 windows nt文件系统50911.8.1 基本概念51011.8.2 ntfs文件系统的实现51011.9 windows vista中的安全51611.9.1 基本概念51611.9.2 安全相关的api调用51811.9.3 安全性的实现51811.10 小结519习题520第12章 实例研究3：symbian *** 作系统52212.1 symbian *** 作系统的历史52212.1.1 symbian *** 作系统的起源：psion和epoc 52212.1.2 symbian *** 作系统版本6 52312.1.3 symbian *** 作系统版本7 52312.1.4 今天的symbian *** 作系统52312.2 symbian *** 作系统概述52312.2.1 面向对象52412.2.2 微内核设计52412.2.3 symbian *** 作系统纳核52512.2.4 客户机/服务器资源访问52512.2.5 较大型 *** 作系统的特点52512.2.6 通信与多媒体52612.3 symbian *** 作系统中的进程和线程52612.3.1 线程和纳线程52612.3.2 进程52712.3.3 活动对象52712.3.4 进程间通信52712.4 内存管理52812.4.1 没有虚拟内存的系统52812.4.2 symbian *** 作系统的寻址方式52912.5 输入和输出53012.5.1 设备驱动53012.5.2 内核扩展53012.5.3 直接存储器访问53112.5.4 特殊情况：存储介质53112.5.5 阻塞i/o 53112.5.6 可移动存储器53112.6 存储系统53212.6.1 移动设备文件系统53212.6.2 symbian *** 作系统文件系统53212.6.3 文件系统安全和保护53212.7 symbian *** 作系统的安全53312.8 symbian *** 作系统中的通信53412.8.1 基本基础结构53412.8.2 更仔细地观察基础结构53512.9 小结536习题536第13章 *** 作系统设计53713.1 设计问题的本质53713.1.1 目标53713.1.2 设计 *** 作系统为什么困难53813.2 接口设计53913.2.1 指导原则53913.2.2 范型54013.2.3 系统调用接口54213.3 实现54313.3.1 系统结构54313.3.2 机制与策略54513.3.3 正交性54613.3.4 命名54613.3.5 绑定的时机54713.3.6 静态与动态结构54713.3.7 自顶向下与自底向上的实现54813.3.8 实用技术54913.4 性能55213.4.1 *** 作系统为什么运行缓慢55213.4.2 什么应该优化55213.4.3 空间-时间的权衡55313.4.4 高速缓存55413.4.5 线索55513.4.6 利用局部性55513.4.7 优化常见的情况55513.5 项目管理55613.5.1 人月神话55613.5.2 团队结构55613.5.3 经验的作用55813.5.4 没有银d55813.6 *** 作系统设计的趋势55813.6.1 虚拟化55913.6.2 多核芯片55913.6.3 大型地址空间 *** 作系统55913.6.4 联网55913.6.5 并行系统与分布式系统56013.6.6 多媒体56013.6.7 电池供电的计算机56013.6.8 嵌入式系统56013.6.9 传感节点56113.7 小结561习题561第14章 阅读材料及参考文献56314.1 进行深入阅读的建议56314.1.1 简介及概要56314.1.2 进程和线程56314.1.3 存储管理56414.1.4 输入/输出56414.1.5 文件系统56414.1.6 死锁56414.1.7 多媒体 *** 作系统56414.1.8 多处理机系统56514.1.9 安全56514.1.10 linux 56614.1.11 windows vista 56714.1.12 symbian *** 作系统56714.1.13 设计原则56714.2 按字母顺序排序的参考文献...568

---