首页 > 代码库 > 计算机操作系统学习笔记_5_进程管理 -- 同步与互斥
计算机操作系统学习笔记_5_进程管理 -- 同步与互斥
进程管理
--同步与互斥
一、进程同步与互斥的基本概念
1.基本概念
在多道程序系统中,由于进程,各进程之间有两种形式的制约关系:
(1)间接相互制约– 源于资源共享 -互斥。
(2)直接相互制约– 源于进程合作 -同步。
进程同步:主要源于进程合作,为进程之间的直接制约关系。
进程互斥:主要源于资源共享,是进程之间的间接制约关系。
临界资源:一次只允许一个进程使用的资源称为临界资源,如打印机、公共变量等。
临界区:在每个进程中,访问临界资源的那段程序称为临界区。
2.同步机制应遵循的准则
(1)空闲则进:当临界区空闲时,进程可以立即进入,以便有效地利用临界资源。
(2)遇忙等待:当已有进程进入其临界区时,其它进程必须等待,以保证互斥。
(3)有限等待:对要求进入的进程,应在有限的时间内使之进入,以免陷入“死等”。
(4)让权等待:对于等待的进程,它必须立即释放处理机,以避免进程忙等。
二、实现临界区互斥的基本方法
1.用软件实现的同步互斥机制
(1)算法一:单标志法
(2)算法二:双标志法先检查
(3)算法三:双标志法后检查
(4)算法四:Peterson’sAlgorithm
2.进程互斥的硬件方法
(1)检测和设置(TS)指令
(2)swap指令(或exchange指令)该指令的作用是交换两个字(字节)的内容
三、 信号量
1.对信号量S进行 P操作,记为P(S),处理过程如下
--S.Q; //表示申请一个资源
if (S.Q < 0) //表示没有空闲资源
{
调用进程进入等待队列 S.Q;
阻塞调用进程;
}
<style type="text/css">p { margin-bottom: 0.25cm; line-height: 120%; }</style>
2.对信号量S进行 V操作,记为V(S),处理过程如下
++S.Q; //表示释放一个资源
if (S.Q <= 0) //表示有进程处于阻塞状态
{
从等待队列 S.Q 中取出一个进程 P;
进程 P 进入就绪队列;
}
<style type="text/css">h3.western { font-family: "Liberation Sans",sans-serif; }h3.cjk { font-family: "微软雅黑"; }h3.ctl { font-family: "AR PL UMing CN"; }p { margin-bottom: 0.25cm; line-height: 120%; }</style>
四、 管程
一个管程定义了一个数据结构和能为并发进程所运行的一组操作,这组操作能同步进程和改变管程中的数据。
管程由三部分组成:
局部于管程的共享数据说明;
对该数据结构进行操作的一组过程;
对局部于管程的数据设置初始值的语句。
五、 经典的同步与互斥问题
1.生产者-消费者问题
用C语言和信号量机制描述生产者-消费者问题的程序如下:有界缓冲区的大小为100。
#define N 100 //有界缓冲区大小
typedef int semaphore; //定义信号量
semaphore mutex = 1; //临界区互斥信号量
semaphore empty = N; //空闲缓冲区
semaphore full = 0; //缓冲区初始化为空
void producer(void)
{
int item; //局部变量
while(1)
{
item = produce_item(); //生产数据
P(empty); //获取空数据槽
P(mutex); //获得进入临界区的信号量
insert_item(item); //将数据放入缓冲池
V(mutex); //释放互斥量
V(full); //数据量加一
}
}
void consumer(void)
{
int item; //局部变量
while(1)
{
P(full); //获取数据槽
P(mutex); //获得进入临界区的信号量
item = remove_item(); //将数据从缓冲池读出
V(mutex); //释放互斥量
V(empty); //数据量减一,即空槽加一
consume_item(item); //消费数据
}
}
<style type="text/css">p { margin-bottom: 0.25cm; line-height: 120%; }</style>
2.读者-写者问题
设置互斥信号量wmutex表示写者间、读者和写者间互斥,用readcount变量来记录读者数,由于readcount是读者间共享变量,属于临界资源,它也需互斥,为此,又增设互斥信号量rmutex。程序如下:
typedef int semaphore; //定义信号量
semaphore rmutex = 1; //读者计数器的互斥量
semaphore wmutex = 1; //写-写,读-写互斥量
int readcount = O; //读者计数器
void reader(void) //读者进程
{
while (1) //进程被调度
{
P(rmutex); //取得读者计数器的互斥量
readcount = readcount + 1; //进来一个读者,读者数量加一
if (readcount == 1) //如果是第一个读者,取得读-写互斥量
P(wmutex);
V(rmutex); //释放读者计数器的互斥量
read_data_base(); //读数据
P(rmutex); //读者读完数据要离开,先取得读者计数器的互斥量
readcount = readcount – 1; //读者数量减一
if(readcount == O) //如果是最后一个离开的读者,释放读-写互斥量
V(wmutex);
V(rmutex); //释放读者计数器的互斥量
use_dataread(); //读者使用数据
}
}
void writer(void) //写者进程
{
while (1) //进程得到调度
{
think_up_data();//写者产生数据
P(wmutex); //获得写-写,读-写操作互斥量
write_data_base(); //写入数据库
V(wmutex); //释放写-写,读-写操作互斥量
}
}
<style type="text/css">p { margin-bottom: 0.25cm; line-height: 120%; }</style>
3.哲学家进餐问题-解决办法
(1)至多只允许四个哲学家同时进餐,以保证至少有一个哲学家可以获得二只筷子:
typedef int semaphore; //定义信号量
semaphore chopstick[5]= {1,1,1,1,1}; //初始化信号量
semaphore eating = 4; //仅允许四个哲学家可以进餐
void philosopher(int i) //第 i 个哲学家的程序
{
while(1)
{
thinking(); //工作之一
P(eating); //请求进餐,若是第五个则先挨饿
P(chopstick[i]); //请求左手边的筷子
P(chopstick[(i+1)%5]); //请求右手边的筷子
eating(); //进餐
V(chopstick[(i+1)%5]); //释放右手边的筷子
V(chopstick[i]); //释放左手边的筷子
V(eating); //释放信号量给其他挨饿的哲学家
}
}
<style type="text/css">p { margin-bottom: 0.25cm; line-height: 120%; }</style>
(2)另一种解决方法,仅当哲学家的左、右两支筷子均可用时,才允许他拿起筷子进餐。
typedef int semaphore; //定义信号量
semaphore chopstick[5]= {1,1,1,1,1}; //初始化信号量
semaphore mutex = 1; //设置取筷子的信号量
void philosopher(int i) //第 i 个哲学家的程序
{
while(1)
{
thinking();
P(mutex); //在取筷子前获得互斥量
P(chopstick[i]);
P(chopstick[(i+1)]%5);
V(mutex); //释放互斥量
eating();
V(chopstick[(i+1)]%5);
V(chopstick[i]);
}
}
<style type="text/css">p { margin-bottom: 0.25cm; line-height: 120%; }</style>
(3)规定奇数号哲学家先拿起其左边筷子,然后再去拿右边筷子;而偶数号哲学家则相反。程序代码如下:
typedef int semaphore; //定义信号量
semaphore chopstick[5]= {1,1,1,1,1}; //初始化信号量
void philosopher(int i) //第 i 个哲学家的程序
{
while(1)
{
thinking();
if(i%2 == 0) //偶数哲学家,先右后左
{
P(chopstick[i+1]%5);
P(chopstick[i]);
eating();
V(chopstick[i+1]%5);
V(chopstick[i]);
}
else //奇数哲学家,先左后右
{
P(chopstick[i]);
P(chopstick[i+1]%5) ;
eating();
V(chopstick[i]);
V(chopstick[i+1]%5);
}
}
}计算机操作系统学习笔记_5_进程管理 -- 同步与互斥