第三章进程、作业、线程管理
(2)
3.3 并发进程
一,进程的并发性
二,进程的互斥和同步
三,信号量
四,进程间的通信
五,进程的死锁现化操作系统的两个主要特征是多道程序设计和分布处理，而并发是这两个特征的基础，也是操作系统的设计基础一,进程的并发性
进程在执行过程中，不同运行阶段进程使用不同的系统资源，有着交替、重叠执行的可能性。正是因为多道程序系统中进程的相对执行速度不可预测，给系统也就带来了一些困难。
这里主要针对单处理器而言，而多处理的情况比复杂
1、并发的存在给系统带来的要求
1)操作系统必须记下诸进程
2)操作系统必须为每个进程分配和释放各类资源
3）操作系统必须保护每个进程的数据和物理资源，避免其他进程的无意干涉
4）操作系统的结果必须与执行速度无关，
即不会出现与时间有关的错误
2、进程间的相互制约关系
基于进程间相互知道对方是否存在的程度分三种可能：
1）、进程之间不知道对方
2）、进程间接知道对方
3）、进程直接知道对方
3、进程中的资源竞争
当并发进程竞争使用同一个资源时，它们相互之间会发生冲突，而竞争进程间没有任何信息交换，却可能影响到竞争进程的一些行为。
饿死：因得不到运行所需的资源，而处于长期等待，
临界资源：对一个不可共享的资源；在执行过程中，每个需要使用此资源时都要给其发命令，接收状态信息，
发送数据和接收数据的资源
临界区：使用临界资源的那段程序就称为程序的临界区。
注：对临界资源的访问必须满足互斥要求
4、进程间通过共享的合作
通过共享进行合作的进程间相互不确切知道对方的情况下进行交互。如诸进程可能访问同一个共享的变量、文件或数据库，进程在使用修改这些数据时，并不涉及到其他进程，但是它们知道其他进程也可能访问同一数据。
因此系统的控制机制必须要能确保共享数据的完整性。
5、进程间通过通信合作
当进程通过通信进行合作时，各个进程都参与其他进程的连接，而通信就是给其提供同步和协调各种活动的方法。
通常通信可以被描述成由各种类型的消息组成。
二,进程的互斥和同步
并发进程管理的主要任务是：使并发执行的诸进程之间能有效的共享资源和相互合作，从而使程序的执行具有可再现性。
1、进程互斥
当并发的进程要竞争使用某些临界资源时，为了提供互斥的支持，必须满足以下要求：
空闲让进：无进程处于临界区中
忙则等待：
有限等待,要避免出现“死等”即“饿死”
让权等待：要避免出现“忙等”
请大家注意区分死锁、活锁和饿死等概念
一些可以满足这些互斥条件方法：
软件方法：让希望并发的进程认为都需要与另一个进程合作，以实施互斥。
硬件支持：这种方法会涉及到使用专门的机器指令。
语言支持：即在操作系统或程序设计上提供某种级别的支持。
2、互斥
Dekker算法：
1）第一种尝试
给共享的互斥资源保留一个标记为 sign的全局存储器单元，希望使用这一临界资源的进程在进入临界区前必须首先检查
sign的内容。如果 sign的值等于该进程的进程号时，则该进程就可处于临界区，
否则必须等待。
忙等：其实就是死锁
如第 I号进程的程序代码段如下：
…………
While (sing !=I) ; /*什么都不做 */
/*临界区 */
Sign=s;/*s为等待此资源的一个进程的进程号 */
………………
2）、第二种尝试
/*进程 0*/
……
While (flag[1])/*延迟 */;
Flag[0]=-1;/*赋值为真 */
/*临界区 */
Flag[0]=0;/*赋值为假 */
……
/*进程 1*/
……
While (flag[0])/*延迟 */;
Flag[1]=-1;/*赋值为真 */
/*临界区 */
Flag[1]=0;/*赋值为假 */
……
会导致死锁
3）第三种尝试
/*进程 0*/
……
Flag[0]=-1;
While (flag[1])
{flag[0]=0;
/*延迟 */;
Flag[0]=-1;
}
/*临界区 */
Flag[0]=0;
……
/*进程 1*/
……
Flag[1]=-1;
While (flag[0])
{flag[1]=0;
/*延迟 */;
Flag[1]=-1;
}
/*临界区 */
Flag[1]=0;
……
4)Dekker算法
Int flag[2]={0,0},sign=1;
Void main( )
{parbegin (p0( ),p1( ));
/*结构 parbegin的含义是挂起主程序的执行，开始并发执行进程 P0和 P1*/
}
Void P0( )
{……
Flag[0]=-1;
While(flag[1])
If(sign==1)
{flag[0]=0;
While(sign==1) ;
Flag[0]=-1;
}
/*临界区 */
Sign=1;
Flage[0]=0;
……
}
Void P1( )
{……
Flag[1]=-1;
While(flag[0])
If(sign==0
{flag[1]=0;
While(sign==01) ;
Flag[1]=-1;
}
/*临界区 */
Sign=0;
Flage[1]=0;
……
}
Perterson算法
Int flag[2]={0,0},sign;
Void main( )
{ parbegin (P0( ),P1());}
和 Dekker算法一样，全局数组变量 flag表示每个进程关于互斥的位置，
全局变量 sign
解决同进程的冲突问题，但是它将对这两个变量的检测和放置更有效的结合起来，
Void P0 ( )
{……
Flag[0]=-1;
Sign=1;
While (flag[1]&&
sign==1);
/*临界区 */
Flag[0]=0;
……
}
Void P1 ( )
{……
Flag[1]=-1;
Sign=1;
While
(flag[0]&&sign==0);
/*临界区 */
Flag[1]=0;
……
}
3、互斥（用硬件支持的方法）
1）中断禁用（即在临界区段前后加上禁止和启用中断就可以了）
这种方式简单易实现，但是处理却被限制成只能交替执行程序，降低了执行的效率。而且在多处理器的系统中却是无法保证诸进程在其他处理器上的互斥执行了。
2）专门的机器指令
test和 set 指令
exchange指令可能会产生饿死、死锁现象
Test和 set指令
Boolean testset(int bolt)
{ if (bolt==0) { bolt; return ture; }
else return false;
}
Const int N=进程数
Int bolt=0;
Void main()
{ parbegin (P(1),P(2),……,P(N)); }
Void P(int I)
{……
While (! Testset(bolt));
/*临界区 */
Bolt=0;
……
}
Exchange指令
Void exchange (int reg,int mem)
{ int temp;
temp=mem;mem=reg;reg=temp;
}
Const int N=进程数；
Int bolt=0;
Void main() {parbegin(P(1),P(2),…,P(N));}
Void p(int I)
{int key=1;
……
While(key!=0) exchange(key,bolt);
/*临界区 */
Exchage(key,bolt);
……
}
机器指令方法的特点：
优点：适用于单处理器和多处理器的系统上的任何数目的并发进程；简单、易懂、容易证明；只要给每个临界区定义自已的变量，就可用于支持多个临界区的并进程。
缺点：使用的是忙等，可能饿死
可能死锁
4、进程同步
1）、并发进程间间接和直接的相互制约关系的区别：
间接制约大都是以竞争资源或共享临界资源引起的，
是互斥关系；
直接制约主要是诸并发进程之间的合作引起的是同步关系
进程同步：是在某些进程未获得合作进程发来消息之前，进程阻塞，消息到来之方可继续执行的进程合作关系
2）概念：是在某些进程未获得合作进程发来消息之前，进程得阻塞，消息到来之后方可继续执行的进程合作关系称为进程 同步。
进程同步就是为了并发进程之间能够正确的交换信息，以便达到协调步伐的目的，对进程操作的时间顺序所加的某种限制。
合作进程就是通过在执行进度上彼此协调，以完成相关的操作。
5,windows2000的进程互斥与同步
1）内核同步
2）执行体同步 互斥是保证了各进程能正确的使用不支持共享的资源。同样互斥对于紧耦合的支持对称多处理的操作系统来说尤为重要，相同的系统代码能同时在多个处理器上运行，共享存储在共用内存中的某些数据。
因此必须提供一种体制，
防止两个线程同时修改同一个结构。
1）内核同步
内核临界区：是修改共用数据结构的代码段
（只有在内核能保证线程以互斥方式访问这些数据结构时操作系统才能正常工作）
对是中断的处理：通过把处理器的“中断请求级”提高到任意潜在的访问全局数据的中断资源使用的最高级来达到这个目的。
自旋锁：一个与共用数据结构有关的锁机制处理器 A
Do {尝试获得 DPC
队列的自旋锁； }while(不成功）
处理器 B
Do {尝试获得 DPC
队列的自旋锁； }while(不成功）
Begin
从队列移出 DPC
end
Begin
从队列移出 DPC
end
释放 DPC队列中的自旋锁释放 DPC队列中的自旋锁自旋锁
DPC DPC
自旋锁的使用
2）执行体同步在多处理环境下，在内核之外的执行体软件同样需要同步访问共用数据结构，自旋锁只是部分满足了执行体对同步机制的需要，这是因为在自旋锁上等等待，实际上处理器暂停，通常自旋锁只可在下列严格的环境使用：
1、被保护的资源必须被快速访问，并且没有与其它代码有复杂的交互作用。
2、临界区代码不能换出内存，不能引用可分页数据，不能调用外部程序，包括系统服务，不能生成中断或异常情况。
三,信号量
1、信号量的基本概念
2、用信号量实现进程互斥
3、用信号量实现进程同步
4、经典进程同步实例
1、信号量的基本概念
信号量 S：
1）是一个整型变量，而且初值是非负数
2）对信号量仅能实施 PV操作
3）对每一个信号量，都对应有一个等待队列
4） S>0表示可用资源的数量,S<0表示进程的申请不能被满足，其绝对值就是等待使用此资源的进程数
P(S)原语操作
1)将 S值减 1
2)若 S<0表明资源已经分配完了，则进程阻塞，
将它插到该信号量的等待队列中，调度另一个就绪进程运行。
3）若 S>=0表明有资源提供给进程使用，则当前进程继续运行
V(S)原语操作
1）将 S值加 1
2）若 S<=0表明有进程在等待，则要其相应的等待队列中，调一个进程为插入就绪队列中。
如果是剥夺方式 的进程管理，还需进行进程调度
3）若 S>0表明无其他进程等待此资源，则当前进程继续运行。
2、用信号量实现进程互斥
利用 P,V操作和信号量来解决互斥时，
只要将这些进程共享共一个公用信号量 S，
并赋初值为 1。
利用互斥信号量实现进程互斥可以描述如下：
Const int N=进程数；
Semaphore S=1;
Void main ( )
{ parbegin (P(1),P(2),……,P(N));}
Void P(int I)
{……
P(S);
/*临界区 */
V(S);
……
}
作业：
一个小河上有一座独木桥，每次只允许一个人通过，现在河的东西两岸各有一个要过桥，如果把每一个过桥的人看作一个进程，请用 PV操作实现管理。
3、用信号量实现进程同步
1),int S=0;
Void mian( )
{parbegin(P1(),P2());}
Void P1()
{……V(S);}
Void P2( )
{P(s);
……
}
2),Int S2=0,S3=0;
Void main( )
{ parbegin (P1(),P2( ),P3());}
Void P1( )
{……V(s2);V(s3);}
Void P2( )
{P(S2); ……}
Void P3( )
{P(s3);……}
3）,Int S1=0,S2=0;
Void main ( )
{parbegin(P1(),P2(),P3());}
Void P1()
{……V(S1);}
Void P2( )
{……V(S2) ； }
Void P3( )
{P(S1);P(S2);……}
4),Int S1=0,int S2=1；
Void main( )
{parbegin(CP(),IOP());}
Void CP( )
{while(计算未完成）
{得到一个计算结果；
P(S2);
将数据送入 buf;
V(S1);
}
通过分析可知,CP进程和 IOP
进程必须用以下同步规则：
一、当 CP进程把计算结果送入
buf时,IOP进程才能从 buf中取出结果打印，即当 buf内有信息时,IOP进程才能动作，否则必等待。
二、当 IOP进程把 buf中的数据取出打印后,CP进程才能把下一个计算结果数据送入 buf中，
即只有当 buf为空时,CP进程才能将计算结果送入 buf中，否则必须等待。
为了遵循这一同步规则，两个进程在并发执行时必须通信，
进行同步操作。
Void IOP ( )
{while(打印未完成 )
{P(S1);
从 buf中取出数据； V（ S2）；
将数据在打印机上输出；
}
}
4、经典进程同步实例
1)、生产者 — 消费者问题
在计算机系统中，每个进程都申请和释放系统中的各种不同类型的软、硬资源，
系统中使用某一类资源的进程被称为此类资源的消费者，而把释放同类资源的进程称为此类资源的生产者。
生产者 — 消费者问题描述了一组生产者向一组消费者提供新产品，它们通过共享一组缓冲区联系起来。类似上述的单缓冲的打印问题，是它的一扩充。
生产者和消费者是相互等效的，生产者向缓冲池中投放消息，消费者从获取消息。他们之间满足以下条件：消费者要想取消息时，有界缓冲池中至少要有一个缓冲区是满的；生产者要想发送消息时，有界缓冲池中至少要有一个缓冲区是空的。
根据分析用 P,V操作实现生产者 — 消费者之间的同步，需定义三个信号量：
Mutex:用以保证生产者和消费者进程之间的互斥，初值为 1
Empty:表示有界缓冲池中可用缓冲区的个数，初始值为 N。
Full:表示有界缓冲池中多少个缓冲区中有消息，初始值为 0。
Int mutex=1;
Int empty =N;
Int full=0;
Void main( )
{parbegin(producer( ),consumer());}
Void producer( )
{while(生产未完成）
{ 生产一个产品；
P(empty);P(mutex);
将产品到缓冲区；
V(full);V(mutex);
}
}
Void consumer( )
{ while (还要继续消费）
{ P(full);P(mutex);
从缓冲区中取一个产品；
V(empty);V(mutex);
消费产品；
}
}
2）、读者 — 作者问题
定义：有一个许多进程共享的数据区，这个数据区可以是一个文件或者主存的一块空间，甚至可以是一组处理器。有一些只读取这个数据区的进程 read和一些只往数据区中写数据的进程 write。而必须满足以下条件：任意多的读进程可以同时读这个文件；一次只有一个写进程可以往文件中写；如果一个写进程正在往文件中写，要禁止任何其他读或写进程操作此文件。
Mutex:用来控制实现读者和作者之间的互斥关系，初值为 1。
Readercount:用来记录读者个数。
X：用来实现对 readercount进行操作时的正确性，即计数的正确性。
Y：用来实现对 writercount进行操作时的正确性，即防止两个作者同时进行修改。
Rsem:用来当有读者进入时，防止作者修改；当有作者想要修改或正在修改时，
防止其他作者的进入修改或其他读者的进入
同步方式一：
Int mutex=1,x=1;
Int rsem=1,y=1,z=1;
Int readercount=0,writercount=0;
Void write( );
Void read( );
Void main( )
{parbegin(read( ),write( ));}
Void read( )
{P(z); P(rsem); P(x);
Readercount ++;
If(readercont==1)
P(mutex); V(x); V(rsem);
V(z);
读文件 ;
P(x)；
Readercount--;
If(readercount==0)
V(mutex);V(x);
}
Void write( )
{P(y);
Writercount++;
If(writercount==1)
P(rsem); V(y);P(mutex);写文件 ;V(mutex);
P(y);
Writercount--;
If(writercount==0)
V(rsem);
V(y);
}
改进型的读者和作者同步方式二：
Int mutex=1,x=1,rsem=1;
Int readercount=0;
Void main( )
{
Parbegin(read( ),write( ));
}
这个变量在这里主要作用：当作者想修改时，保证不能让不在阅读的读者的进入。
也保证了作者具有优先权
Void read ( )
{P(rsem); P(x);
Readercount++;
If(readercount==1)
P(mutex);V(x);V(rsem);读文件； P(x)；
Readercount--;
If(readercount==0)
V(mutex);
V(x);
}
Void write( )
{ P(rsem); P(mutex);
写文件 ;
V(mutex);
V(rsem);
}
四,进程间的通信
进程通信就是指进程间的信息交换。
低级通信方式,P,V
高级通信方式：共享存储器系统、管道通信系统和消息传递系统。
1、共享存储器系统
1）基于共享数据结构的通信方式：进程之间能够通过某种类型的数据结构交换信息。这种通信方式效率低，只适于传递小批量信息。
2）基于共享存贮区的通信方式：即在存贮器中划出一块共享的存贮区，诸进程间可通过对共享存贮区中的数据进行读或写操作来实现通信。
2、管道通信系统
管道通信系统是一种基于原有文件系统形成的一种通信方式，即是利用共享文件夹来实现进程间的通信的。这个共享文件就是管道。
其工作是以先进先出为顺序的单向通信方式。
读进程写进程写入 读出
为了协调通信双方，管道通信机制必须提供以下三个方面的协调能力。
1）互斥：当一个进程正对管道进行读或写数据时，另一进程必须等待。
2）同步：当写进程把一定数据写入管道后便阻塞等待，直到读进程取走数据后才能将写进程唤醒；当读进程在读空管道时也应阻塞等待，直到写进程将消息写入管道后才能将读进程唤醒。
3）对方是否存在：只有在确定进程通信的双方都存在时，方可进行通信。
3、消息传递系统
在消息传递系统中，进程的数据交换以消息为单位，程序员利用系统提供的一组通信命令来实现，消息传递系统可以分为：
１）、消息缓冲通信
２）、信箱通信
１）、消息缓冲通信
发送原语,主要工作是请求分给一个消息缓冲区,然后将消息正文传送到该缓冲区中,并向缓冲区中填写消息头，再将该消息缓冲区挂到接收进程的消息链上。
接收原语的主要工作是把消息链上的消息逐个读入到接收进程的接收区并进行处理。
消息缓冲是一种直接通信方式，即一个进程直接发送一个消息给接收进程。在通信时，发送进程采用发送原语向接收进程发送一个消息，
而接收进程则采用接收原语接收来自发送进程的一个消息。
消息：就是一组信息；
消息的格式：取决于消息机制的以及运行环境。
一种常用的格式：消息由消息头和消息体组成，消息头对消息加以说明，如消息的源和目标的标识符、长度、类型和一些控制信息等，是固定长度的；而消息体则是消息本身，是可变长的。
一个进程可以与多个进程通信，它可以向多个进程发送消息，也可以接收来自多个不同的机关进程发送来的消息。如果进程在一段时间内收到多条消息又来不及处理，就可将这些消息组织成消息队列。为此相应的进程控制块也要有：互斥访问消息队列的信号量、
消息数目和消息队列首指针。
消息缓冲通信方式具体实现是通过一对发送和接收原语来实现的：
发送原语的实现：
Send(receiver,message)
{向系统申请一个消息缓冲区；
将消息 message中的消息复制到消息缓冲区中；
P(S);
将消息缓冲区插入到 receiver接收进程的消息队列中；
V(so);
}
接收原语：
Receive(source,message)
{P(so);
P(s);
将消息队列中发送者为 source的消息缓冲区移出队列；
V（ S）
将消息缓冲区的消息复制到 message中；
用消息传递方式也可以解决有界缓冲池的生产者 — 消息费者问题。利用消息传递能力，可以同时传递信号和数据。
Int N=缓冲池的大小；
Int capacity=缓冲区容量；
Strust 消息结构 NULL=空消息；
Void main( )
Create_mailbox(produce_space);
Create_mailbox(consume_space);
For(int I=1;I<=N;I++)
Send(produce_space,null);
Parbegin(producer( ),consumer( ));}
Void producer( )
{message pmsg;
Receive(produce_space,pmsg);
Pmsg=生产者生产的消息；
Send(consume_space,pmsg);
}
Void consumer ( )
{message cmsg;
Receive(consume_space,cmsg);
取出消息进行消息费；
Send(produce_space,null);
}
２）、信箱通信
信箱的概念及工作方式的描述：
信箱是一种数据结构，可以用于存放信件。信箱通信是一种间接通信方式，当一个进程（发送进程）要与另一进程
（接收进程）通信时，可由发送进程创建一个链接两个进程的信箱，通信时发送进程只须把它的信件投入信箱，接收进程就在任何时候取走信件而不会丢失。
信箱的格式：
信箱逻辑上分成信箱头和信箱体；
信箱头中存放有关信箱的描述。
信箱体由若干格子组成，每格存放一封信件，格子的数目和大小在创建信箱时确定。
信件的传递可以是单向的，也可以双向的。
单向信箱通信方式：
只要信箱中有空格，发送进程便可向信箱中投递信件，若所有格子都已装满，
则发送进程或者等待，或者继续执行，
待有空格时再发送。类似地，只要格子中装有信件，接收进程便能取出一封信件。若信箱为空，接收进程或者等待，
或者继续执行。
双向通信方式：
信箱中既有发送进程发出信件，也有接收进程的回答信件。
上溢：由于发送进程和接收进程是以各自独立的速度向前推进的，当发送进程发送信件的速度超过接收进程的接收速度时，会产生上溢
下溢：接收进程向空信箱索取信件
问题的解决：这就需要两个进程同步，当信箱满时发送进程应等待，直至信箱有空格时再发送；对接收进程，当信箱空时，它也应等待，
直至信箱中有信件时，再接收。
五,进程的死锁
１、产生死锁的原因和必要条件
２、死锁的预防
３、死锁的避免
４、死锁的检测和解除
１、产生死锁的原因和必要条件
产生死锁的原因：
系统资源不足、进程推进顺序不当
产生死锁的必要条件：
互斥条件
不剥夺条件
部分分配条件
环路分配条件
２、死锁的预防
要想防止死锁的发生，只需破坏死锁的四个必要条件之一即可：
１）、破坏互斥条件
２）、破坏不剥夺条件
３）、破坏部分分配条件
４）、破坏环路条件
３、死锁的避免
在预防死锁的方法中所采取的几种策略，
总的来说都是增加较强的限制条件，虽然实现起来较简单，但却严重地损害了系统性能。死锁的避免方法中，所施加的限制条件较弱，同时把系统的状态分为安全状态和不安全状态，只要能使系统处于安全状态便可避免死锁的发生。
１）、安生与不安全状态
若在某一时刻，系统能按某种顺序如Ｐ １ Ｐ ２ …… Ｐ n
来为每个进程分配其所需要的资源，直至最大需求量，
每个进程都可顺利的完成，则称此时的系统状态为安全状态，序列Ｐ １ Ｐ ２ …… Ｐ n为安全序列。若某一时刻系统中不存在这样的一个安全序列，则称此时刻的系统状态为不安全状态。
在避免死锁的方法中，允许进程动态申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，便将资源分配给进程，否则进程等待。虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免死锁状态。
２）、利用很行家算法避免死锁
该算法就是检查申请者对各类资源最大需求量如果系统现存的各类资源可以满足当前它对各类资源的最大需求量时，
就满足当前的申请。换言之，仅当申请者可以在一定时间内无条件地归还它所申请的全部资源时，才能把资源分配给它。
例：有三个进程 P1P2P3，系统只具有 10
个同类资源。当前的分配情况是 P1P2P3
分别已分配得到资源数为 4,2,2，还需要资源数为 4,2,7，按照一种怎样的推进方式才可以避免死锁？
由上可以看出，银行家算法来分配资源是不会产生死锁的。因为分配资源时，
每次分配后总存在着一个进程，如果让它单独执行下去，必然可以获得它所需要的全部资源。也就是说此进程可以正常结束，而它结束后可以归还资源又能满足其他申请者的需要。
４、死锁的检测和解除
死锁的预防策略保守的，是通过限制访问资源和在进程上强加约束来解决死锁的。而且在很多情况下，被限制的情况并不一定就会产生死锁。故有些系统中并不在进程分配资源时采取任措施，而只是周期的检测是不发生了死锁，
出现死锁是再解除。
1）、死锁的检测
2）、死锁的解除
1）、死锁的检测
发现死锁的原理：是考察某一时刻系统状态是否合理，即是否存在一组可以实现的系统状态，能使所有进程都得到它们申请的资源而运行结束。
检测死锁的基本思想是：获得某时刻 t系统中各类可利用资源的数目向量 w(t)，对于系统中的一组进程 P1P2……P n，找出那些对各资源请求数目均小于系统现在所拥有的各类资源数目的进程，则这些进程都能获得所需全部资源并运行结束释放所占有的全部资源，将这些进程从进程组删除，从而使可用资源数目增加，然后对剩下的进程又做上述考察。如果进程组中所有进程都被删除了，则说此时的系统是安全的，否则，认为系统会发生死锁。
2）、死锁的解除
一旦检测到死锁，就需要某种策略来解除死锁。
撤消进程法：一种是取消所有的死锁进程，这是操作系统中最常用的一种方法；
二是连续取消死锁进程直到不再存在死锁。选择取消的进程顺序是基于最小代价原则。
资源剥夺法：连续剥夺资源直到不再存在死锁。资源的剥夺也要基于最小代价原则。
最小代价原则一般采用取消以下几种进程
目前为止消耗的处理器时间最少的
目前为止产生的输出最少的
预计剩下的时间最长的
目前为止分配的资源总数最少的
优先级最低的
例,假定系统有同类资源 12个，有 3个进程
P1,P2,P3来共享，已知 P1,P2,P3所需的资源的总数 8,6,9，它们申请资源的次序如下表。系统采用银行家算法为它们分配资源。问：
①哪次申请分配会使系统进入不安全状态？
②执行完序号为 6的申请后，各进程的状态和各进程已占有的资源数是什么？
序号 进程 申请资源数
1 P1 4
2 P2 4
3 P3 2
4 P1 1
5 P3 2
6 P2 2
…… …… ……
3.4 线程管理
一,线程的概念
二,线程的特性
三,windows2000线程的调度一,线程的概念
0、线程的引入
1、线程的概念
2、线程的分类
3、线程与进程的比较
0、线程的引入
（ 1） 创建进程 。 系统在创建进程时,必须为之分配其所必需的,除处理机以外的所有资源 。 如内存空间,I/O设备以及建立相应的 PCB结构 。
（ 2） 撤消进程 。 系统在撤消进程时,又必须先对这些资源进行回收操作,然后再撤消 PCB结构 。
（ 3） 进程切换 。 在对进程进行切换时,
由于要保留当前进程的 CPU环境和设置新选中进程的 CPU环境,为此需花费不少处理机时间
1、线程的概念
线程是比进程更小的活动单位，它是进程中的一个执行路径。
一个进程可以有多条执行路径即线程。
这样，在一个进程内部就有多个可以独立活动的单位，可以加快进程处理的速度，进一步提高系统的并行处理能力。
对线程有如下的描述：
1）、线程是进程中的一条执行路径
2）、线程有自已私有的堆栈和处理机执行环境。
3）、线程与父进程共享分配给父进程的主存及其他资源。
4）线程是单个进程所创建的许多个同时存在的线程中的一个。
步骤 读取数据 修改数据 写入数据读第 1个记录修改第 1个记录写入第 1个记录读第 2个记录修改第 2个记录写入第 2个记录读第 3个记录修改第 3个记录写入第 3个记录数据修改程序在进程模型下执行
进程中的所有线程共享该进程的状态和资源，
它们驻留在同一块地址空间中，并且可以访问到相同的数据。当一个线程改变了共享的信息时，其他线程访问这些信息时能够知道它变化后的结果。因此可以看出线程如下优点：
1）、在一个已有进程中创建一个新线程比创建一个全新进程所需的时间少。
2）、终止一个线程比终止一个进程花费的时间少。
3）、线程间切换比进程切换花费的时间少
4）、线程提高了不同执行程序间通信的效率。
2、线程的分类
1）用户级线程：
在一个纯用户线程的软件中，有关线程管理的所有工作都由应用程序完成，内核没有意识到线程的存在。任何应用程序可以通过使用线程库设计成多线程程序。
线程库是用于用户级线程管理的一个例程包，
它包含用于创建和销毁线程、在线程间传递消息和数据、调度线程执行及保存和恢复线程上下文等的代码。
用户级线程的所有活动发生在用户空间中并且在一个进程内，内核不知道这些活动。内核继续以进程为单位进行调度，并具给进程指定一个执行状态。
2）、内核级线程
在一个纯内核级线程的软件中，有关线程管理的所有工作都是由内核完成的，应程序部分没有进行线程管理的代码，只有一个到内核线程设施的应用程序编程接口。
任何应用程序都可以设计成多线程程序，所有线程都在一个进程里。
内核为该进程及其线程保存整个上下文环境信息，调度是由内核基于线程的基础完成的。内核可以同时把同一个进程中的多个线程调度到多个处理中；如果进程中的一个线程被阻塞，
内核可以调度一个进程中的另一个线程；而且内核例程自身也是可以使用多线程的。
使用用户级线程比使用内核级线程的优点：
1）、线程切换不需要内核模式特权
2）、调度算法可以去适应应用程序，
3）、用户线程可以在任何操作系统中运行，
不需要对底层内核进行修改以支持用户级线程。
线程库是一组供所有应用程序共享的应用级实用程序。
使用用户级线程比使用内核级线程的缺点：
1）、当用户级线程执行一个系统调用时，
不仅这个线程会被阻塞，进程中所有线程都会阻塞。
2）、在用户线程中，一个应程序不能利用多处理技术，内核一次只把一个进程分配给一个处理器，即一个进程中只有一个线程可以执行。
3、线程与进程的比较
1,调度,在传统的操作系统中,拥有资源的基本单位和独立调度,分派的基本单位都是进程 。
2,并发性,在引入线程的操作系统中,不仅进程之间可以并发执行,而且在一个进程中的多个线程之间亦可并发执行,因而使操作系统具有更好的并发性,从而能更有效地使用系统资源和提高系统吞吐量 。
3,拥有资源,不论是传统的操作系统,还是设有线程的操作系统,进程都是拥有资源的一个独立单位,它可以拥有自己的资源 。
4,系统开销,由于在创建或撤消进程时,系统都要为之分配或回收资源,如内存空间,I/O设备等 。 因此,操作系统所付出的开销将明显地大于在创建或撤消线程时的开销 。
二,线程的特性
1、线程的状态
2、线程数据结构
3、线程相关的函数
1,线程的状态
1）、就绪：可以被调度执行
2）、备用：处于备用状态的线程是某一特定处理器的下一个执行对象
3）、运行：一旦调度程序对线程执行完环境切换，线程就进入备用状态开始执行。
4）、等待：当线程被一个事件阻塞、为了同步自愿等待或者一个环境子系统指引它把自身挂起时，该进程进入等待状态。
5）、转换：在线程准备执行而其内核堆栈被调出内存之外，线程进入转换状态。
6）、终止：线程执行完 (或强制性终止 )就进入终止状态。
2、线程数据结构
线程是由线程块代表的，线程块通常包括线程 ID、进程标识、动态优先级、基本优先级、线程处理仿射、线程执行、
警告状态、各种性能计数器、终止端口、
线程退出状态及线程环境块指针。
线程环境块 TEB包括：线程 ID、堆栈信息、异常列表、临界区计数、当前位置及其他信息。
3、线程相关的函数
1)CreateThread:创建新线程
2)CreateRemoteThread:在另一个进程中创建线程
3)ExitThread:正常的结束线程的执行
4)terminatethread:终止线程
5)GetExitCodeThread:获得另一个线程的退出代码
6)GetThreadTime:返回另外一个线程的定时信息
7)Get/SetThreadContext:返回或更改线程的处理器寄存器
8)GetThreadSelectorEntry:返回另一个线程的描述符表项下一页三,windows2000线程的调度
1,windows调度概述
2、线程的优先级
3、时间片
4、调度方案
1,windows调度概述
Windows2000实现一个优先级驱动，可抢先的调度系统，即总是运行优先级最高的就绪就程。当一个线程被选择运行，
它将运行一段时间 (时间片），线程在运行时间内没有执行完时得让出；当有较高优先级的线程准备运行时，也得让出处理器。
Windows2000调度代码在内核中实现，散布在发生调度相关事件的内核中。线程调度发生在 DPC调度一级，它可由以下任何一个事件触发：
1）、线程由就绪变为执行
2）、由于线程的时间片结束
3）、系统调用或者 windows2000自身改变
4）、正在运行的线程的处理器相似性的改变
在以上每个事件发生时,windows2000必须决定下一个要执行的是哪一个线程。在 windows2000选择运行一个新的线程，将对它进行“环境切换”。
环境切换：是保存与正在运行的线程相关的非永久性的机器状态，加载另一个线程的非永久性状态并开始执行新线程的进程。
2、线程的优先级
Windows2000大在内部使用 32个线程优先级，可分为三个部分：
1）,16个实时级别（ 16~31）
2）,15个变量级别（ 1~15）
3）,1个系统级别（ 0），为清零页线程保留
线程优先级是从两个不同的角度分配：
Win32API：是依据在创建进程时分配的优先等级来组织进程。
Windows2000内核：是依据进程中各个线程的相对优先级来组织进程。
线程优先级的确定：
线程启动时就继承进程的基本优先级，
它可以使用 Task Manager来改变，
也可以使用 win32函数 setprocessPriority
来改变。
一个进程只能有一个单一的优先级，每个线程却具有两个优先级值：当前优先级和基本优先级。
虽然 windows2000具有被称作“实时”的优先级，但它并不是真正的实时操作系统，它并不提供保证中断的等待时间。
3、时间片
时间片：是在 windows2000检查具有相同优先级的其他线程是否应该开始运行之前，一个线程开始的一段时间。
每个线程都有一个时间片值来代表时间片结束之前线程可运行的时间片长度。
Windows2000professional上线程启动的时间片值为 6
Windows2000server上线程启动的时间片值为 36
其时间片值较大的原因是为了减少环境切换的时间。通过具有较长的时间片，作为客户请求的结果而被唤醒的服务器的应用程序有足够的时间完成请求并在它的时间片结束之前恢复到等待状态
每当时钟中断发生时，时钟中断例程都会从线程的时间片中减去一个固定值（ 3）。如果没有剩余的线程时间片，那么将触发时间片结束处理，而另一个线程就可能被选择去运行。故在,
Win 2000professional，线程运行 2个时钟间隔；
Win 2000server上线程将运行 12个时钟间隔。
4、调度方案
单处理器中常用的调度方案：
1）自愿切换
2）抢先
3）时间片结束
4）终止多处理器系统调度方案
1）、理想处理器和最后处理器
2）、为就绪线程选择处理器
3）、选择线程在指定的处理器上运行
4）、在多处理器系统中,windows2000
并不是总选择优先级最高的有线程在给定的处理器上运行。
(2)
3.3 并发进程
一,进程的并发性
二,进程的互斥和同步
三,信号量
四,进程间的通信
五,进程的死锁现化操作系统的两个主要特征是多道程序设计和分布处理，而并发是这两个特征的基础，也是操作系统的设计基础一,进程的并发性
进程在执行过程中，不同运行阶段进程使用不同的系统资源，有着交替、重叠执行的可能性。正是因为多道程序系统中进程的相对执行速度不可预测，给系统也就带来了一些困难。
这里主要针对单处理器而言，而多处理的情况比复杂
1、并发的存在给系统带来的要求
1)操作系统必须记下诸进程
2)操作系统必须为每个进程分配和释放各类资源
3）操作系统必须保护每个进程的数据和物理资源，避免其他进程的无意干涉
4）操作系统的结果必须与执行速度无关，
即不会出现与时间有关的错误
2、进程间的相互制约关系
基于进程间相互知道对方是否存在的程度分三种可能：
1）、进程之间不知道对方
2）、进程间接知道对方
3）、进程直接知道对方
3、进程中的资源竞争
当并发进程竞争使用同一个资源时，它们相互之间会发生冲突，而竞争进程间没有任何信息交换，却可能影响到竞争进程的一些行为。
饿死：因得不到运行所需的资源，而处于长期等待，
临界资源：对一个不可共享的资源；在执行过程中，每个需要使用此资源时都要给其发命令，接收状态信息，
发送数据和接收数据的资源
临界区：使用临界资源的那段程序就称为程序的临界区。
注：对临界资源的访问必须满足互斥要求
4、进程间通过共享的合作
通过共享进行合作的进程间相互不确切知道对方的情况下进行交互。如诸进程可能访问同一个共享的变量、文件或数据库，进程在使用修改这些数据时，并不涉及到其他进程，但是它们知道其他进程也可能访问同一数据。
因此系统的控制机制必须要能确保共享数据的完整性。
5、进程间通过通信合作
当进程通过通信进行合作时，各个进程都参与其他进程的连接，而通信就是给其提供同步和协调各种活动的方法。
通常通信可以被描述成由各种类型的消息组成。
二,进程的互斥和同步
并发进程管理的主要任务是：使并发执行的诸进程之间能有效的共享资源和相互合作，从而使程序的执行具有可再现性。
1、进程互斥
当并发的进程要竞争使用某些临界资源时，为了提供互斥的支持，必须满足以下要求：
空闲让进：无进程处于临界区中
忙则等待：
有限等待,要避免出现“死等”即“饿死”
让权等待：要避免出现“忙等”
请大家注意区分死锁、活锁和饿死等概念
一些可以满足这些互斥条件方法：
软件方法：让希望并发的进程认为都需要与另一个进程合作，以实施互斥。
硬件支持：这种方法会涉及到使用专门的机器指令。
语言支持：即在操作系统或程序设计上提供某种级别的支持。
2、互斥
Dekker算法：
1）第一种尝试
给共享的互斥资源保留一个标记为 sign的全局存储器单元，希望使用这一临界资源的进程在进入临界区前必须首先检查
sign的内容。如果 sign的值等于该进程的进程号时，则该进程就可处于临界区，
否则必须等待。
忙等：其实就是死锁
如第 I号进程的程序代码段如下：
…………
While (sing !=I) ; /*什么都不做 */
/*临界区 */
Sign=s;/*s为等待此资源的一个进程的进程号 */
………………
2）、第二种尝试
/*进程 0*/
……
While (flag[1])/*延迟 */;
Flag[0]=-1;/*赋值为真 */
/*临界区 */
Flag[0]=0;/*赋值为假 */
……
/*进程 1*/
……
While (flag[0])/*延迟 */;
Flag[1]=-1;/*赋值为真 */
/*临界区 */
Flag[1]=0;/*赋值为假 */
……
会导致死锁
3）第三种尝试
/*进程 0*/
……
Flag[0]=-1;
While (flag[1])
{flag[0]=0;
/*延迟 */;
Flag[0]=-1;
}
/*临界区 */
Flag[0]=0;
……
/*进程 1*/
……
Flag[1]=-1;
While (flag[0])
{flag[1]=0;
/*延迟 */;
Flag[1]=-1;
}
/*临界区 */
Flag[1]=0;
……
4)Dekker算法
Int flag[2]={0,0},sign=1;
Void main( )
{parbegin (p0( ),p1( ));
/*结构 parbegin的含义是挂起主程序的执行，开始并发执行进程 P0和 P1*/
}
Void P0( )
{……
Flag[0]=-1;
While(flag[1])
If(sign==1)
{flag[0]=0;
While(sign==1) ;
Flag[0]=-1;
}
/*临界区 */
Sign=1;
Flage[0]=0;
……
}
Void P1( )
{……
Flag[1]=-1;
While(flag[0])
If(sign==0
{flag[1]=0;
While(sign==01) ;
Flag[1]=-1;
}
/*临界区 */
Sign=0;
Flage[1]=0;
……
}
Perterson算法
Int flag[2]={0,0},sign;
Void main( )
{ parbegin (P0( ),P1());}
和 Dekker算法一样，全局数组变量 flag表示每个进程关于互斥的位置，
全局变量 sign
解决同进程的冲突问题，但是它将对这两个变量的检测和放置更有效的结合起来，
Void P0 ( )
{……
Flag[0]=-1;
Sign=1;
While (flag[1]&&
sign==1);
/*临界区 */
Flag[0]=0;
……
}
Void P1 ( )
{……
Flag[1]=-1;
Sign=1;
While
(flag[0]&&sign==0);
/*临界区 */
Flag[1]=0;
……
}
3、互斥（用硬件支持的方法）
1）中断禁用（即在临界区段前后加上禁止和启用中断就可以了）
这种方式简单易实现，但是处理却被限制成只能交替执行程序，降低了执行的效率。而且在多处理器的系统中却是无法保证诸进程在其他处理器上的互斥执行了。
2）专门的机器指令
test和 set 指令
exchange指令可能会产生饿死、死锁现象
Test和 set指令
Boolean testset(int bolt)
{ if (bolt==0) { bolt; return ture; }
else return false;
}
Const int N=进程数
Int bolt=0;
Void main()
{ parbegin (P(1),P(2),……,P(N)); }
Void P(int I)
{……
While (! Testset(bolt));
/*临界区 */
Bolt=0;
……
}
Exchange指令
Void exchange (int reg,int mem)
{ int temp;
temp=mem;mem=reg;reg=temp;
}
Const int N=进程数；
Int bolt=0;
Void main() {parbegin(P(1),P(2),…,P(N));}
Void p(int I)
{int key=1;
……
While(key!=0) exchange(key,bolt);
/*临界区 */
Exchage(key,bolt);
……
}
机器指令方法的特点：
优点：适用于单处理器和多处理器的系统上的任何数目的并发进程；简单、易懂、容易证明；只要给每个临界区定义自已的变量，就可用于支持多个临界区的并进程。
缺点：使用的是忙等，可能饿死
可能死锁
4、进程同步
1）、并发进程间间接和直接的相互制约关系的区别：
间接制约大都是以竞争资源或共享临界资源引起的，
是互斥关系；
直接制约主要是诸并发进程之间的合作引起的是同步关系
进程同步：是在某些进程未获得合作进程发来消息之前，进程阻塞，消息到来之方可继续执行的进程合作关系
2）概念：是在某些进程未获得合作进程发来消息之前，进程得阻塞，消息到来之后方可继续执行的进程合作关系称为进程 同步。
进程同步就是为了并发进程之间能够正确的交换信息，以便达到协调步伐的目的，对进程操作的时间顺序所加的某种限制。
合作进程就是通过在执行进度上彼此协调，以完成相关的操作。
5,windows2000的进程互斥与同步
1）内核同步
2）执行体同步 互斥是保证了各进程能正确的使用不支持共享的资源。同样互斥对于紧耦合的支持对称多处理的操作系统来说尤为重要，相同的系统代码能同时在多个处理器上运行，共享存储在共用内存中的某些数据。
因此必须提供一种体制，
防止两个线程同时修改同一个结构。
1）内核同步
内核临界区：是修改共用数据结构的代码段
（只有在内核能保证线程以互斥方式访问这些数据结构时操作系统才能正常工作）
对是中断的处理：通过把处理器的“中断请求级”提高到任意潜在的访问全局数据的中断资源使用的最高级来达到这个目的。
自旋锁：一个与共用数据结构有关的锁机制处理器 A
Do {尝试获得 DPC
队列的自旋锁； }while(不成功）
处理器 B
Do {尝试获得 DPC
队列的自旋锁； }while(不成功）
Begin
从队列移出 DPC
end
Begin
从队列移出 DPC
end
释放 DPC队列中的自旋锁释放 DPC队列中的自旋锁自旋锁
DPC DPC
自旋锁的使用
2）执行体同步在多处理环境下，在内核之外的执行体软件同样需要同步访问共用数据结构，自旋锁只是部分满足了执行体对同步机制的需要，这是因为在自旋锁上等等待，实际上处理器暂停，通常自旋锁只可在下列严格的环境使用：
1、被保护的资源必须被快速访问，并且没有与其它代码有复杂的交互作用。
2、临界区代码不能换出内存，不能引用可分页数据，不能调用外部程序，包括系统服务，不能生成中断或异常情况。
三,信号量
1、信号量的基本概念
2、用信号量实现进程互斥
3、用信号量实现进程同步
4、经典进程同步实例
1、信号量的基本概念
信号量 S：
1）是一个整型变量，而且初值是非负数
2）对信号量仅能实施 PV操作
3）对每一个信号量，都对应有一个等待队列
4） S>0表示可用资源的数量,S<0表示进程的申请不能被满足，其绝对值就是等待使用此资源的进程数
P(S)原语操作
1)将 S值减 1
2)若 S<0表明资源已经分配完了，则进程阻塞，
将它插到该信号量的等待队列中，调度另一个就绪进程运行。
3）若 S>=0表明有资源提供给进程使用，则当前进程继续运行
V(S)原语操作
1）将 S值加 1
2）若 S<=0表明有进程在等待，则要其相应的等待队列中，调一个进程为插入就绪队列中。
如果是剥夺方式 的进程管理，还需进行进程调度
3）若 S>0表明无其他进程等待此资源，则当前进程继续运行。
2、用信号量实现进程互斥
利用 P,V操作和信号量来解决互斥时，
只要将这些进程共享共一个公用信号量 S，
并赋初值为 1。
利用互斥信号量实现进程互斥可以描述如下：
Const int N=进程数；
Semaphore S=1;
Void main ( )
{ parbegin (P(1),P(2),……,P(N));}
Void P(int I)
{……
P(S);
/*临界区 */
V(S);
……
}
作业：
一个小河上有一座独木桥，每次只允许一个人通过，现在河的东西两岸各有一个要过桥，如果把每一个过桥的人看作一个进程，请用 PV操作实现管理。
3、用信号量实现进程同步
1),int S=0;
Void mian( )
{parbegin(P1(),P2());}
Void P1()
{……V(S);}
Void P2( )
{P(s);
……
}
2),Int S2=0,S3=0;
Void main( )
{ parbegin (P1(),P2( ),P3());}
Void P1( )
{……V(s2);V(s3);}
Void P2( )
{P(S2); ……}
Void P3( )
{P(s3);……}
3）,Int S1=0,S2=0;
Void main ( )
{parbegin(P1(),P2(),P3());}
Void P1()
{……V(S1);}
Void P2( )
{……V(S2) ； }
Void P3( )
{P(S1);P(S2);……}
4),Int S1=0,int S2=1；
Void main( )
{parbegin(CP(),IOP());}
Void CP( )
{while(计算未完成）
{得到一个计算结果；
P(S2);
将数据送入 buf;
V(S1);
}
通过分析可知,CP进程和 IOP
进程必须用以下同步规则：
一、当 CP进程把计算结果送入
buf时,IOP进程才能从 buf中取出结果打印，即当 buf内有信息时,IOP进程才能动作，否则必等待。
二、当 IOP进程把 buf中的数据取出打印后,CP进程才能把下一个计算结果数据送入 buf中，
即只有当 buf为空时,CP进程才能将计算结果送入 buf中，否则必须等待。
为了遵循这一同步规则，两个进程在并发执行时必须通信，
进行同步操作。
Void IOP ( )
{while(打印未完成 )
{P(S1);
从 buf中取出数据； V（ S2）；
将数据在打印机上输出；
}
}
4、经典进程同步实例
1)、生产者 — 消费者问题
在计算机系统中，每个进程都申请和释放系统中的各种不同类型的软、硬资源，
系统中使用某一类资源的进程被称为此类资源的消费者，而把释放同类资源的进程称为此类资源的生产者。
生产者 — 消费者问题描述了一组生产者向一组消费者提供新产品，它们通过共享一组缓冲区联系起来。类似上述的单缓冲的打印问题，是它的一扩充。
生产者和消费者是相互等效的，生产者向缓冲池中投放消息，消费者从获取消息。他们之间满足以下条件：消费者要想取消息时，有界缓冲池中至少要有一个缓冲区是满的；生产者要想发送消息时，有界缓冲池中至少要有一个缓冲区是空的。
根据分析用 P,V操作实现生产者 — 消费者之间的同步，需定义三个信号量：
Mutex:用以保证生产者和消费者进程之间的互斥，初值为 1
Empty:表示有界缓冲池中可用缓冲区的个数，初始值为 N。
Full:表示有界缓冲池中多少个缓冲区中有消息，初始值为 0。
Int mutex=1;
Int empty =N;
Int full=0;
Void main( )
{parbegin(producer( ),consumer());}
Void producer( )
{while(生产未完成）
{ 生产一个产品；
P(empty);P(mutex);
将产品到缓冲区；
V(full);V(mutex);
}
}
Void consumer( )
{ while (还要继续消费）
{ P(full);P(mutex);
从缓冲区中取一个产品；
V(empty);V(mutex);
消费产品；
}
}
2）、读者 — 作者问题
定义：有一个许多进程共享的数据区，这个数据区可以是一个文件或者主存的一块空间，甚至可以是一组处理器。有一些只读取这个数据区的进程 read和一些只往数据区中写数据的进程 write。而必须满足以下条件：任意多的读进程可以同时读这个文件；一次只有一个写进程可以往文件中写；如果一个写进程正在往文件中写，要禁止任何其他读或写进程操作此文件。
Mutex:用来控制实现读者和作者之间的互斥关系，初值为 1。
Readercount:用来记录读者个数。
X：用来实现对 readercount进行操作时的正确性，即计数的正确性。
Y：用来实现对 writercount进行操作时的正确性，即防止两个作者同时进行修改。
Rsem:用来当有读者进入时，防止作者修改；当有作者想要修改或正在修改时，
防止其他作者的进入修改或其他读者的进入
同步方式一：
Int mutex=1,x=1;
Int rsem=1,y=1,z=1;
Int readercount=0,writercount=0;
Void write( );
Void read( );
Void main( )
{parbegin(read( ),write( ));}
Void read( )
{P(z); P(rsem); P(x);
Readercount ++;
If(readercont==1)
P(mutex); V(x); V(rsem);
V(z);
读文件 ;
P(x)；
Readercount--;
If(readercount==0)
V(mutex);V(x);
}
Void write( )
{P(y);
Writercount++;
If(writercount==1)
P(rsem); V(y);P(mutex);写文件 ;V(mutex);
P(y);
Writercount--;
If(writercount==0)
V(rsem);
V(y);
}
改进型的读者和作者同步方式二：
Int mutex=1,x=1,rsem=1;
Int readercount=0;
Void main( )
{
Parbegin(read( ),write( ));
}
这个变量在这里主要作用：当作者想修改时，保证不能让不在阅读的读者的进入。
也保证了作者具有优先权
Void read ( )
{P(rsem); P(x);
Readercount++;
If(readercount==1)
P(mutex);V(x);V(rsem);读文件； P(x)；
Readercount--;
If(readercount==0)
V(mutex);
V(x);
}
Void write( )
{ P(rsem); P(mutex);
写文件 ;
V(mutex);
V(rsem);
}
四,进程间的通信
进程通信就是指进程间的信息交换。
低级通信方式,P,V
高级通信方式：共享存储器系统、管道通信系统和消息传递系统。
1、共享存储器系统
1）基于共享数据结构的通信方式：进程之间能够通过某种类型的数据结构交换信息。这种通信方式效率低，只适于传递小批量信息。
2）基于共享存贮区的通信方式：即在存贮器中划出一块共享的存贮区，诸进程间可通过对共享存贮区中的数据进行读或写操作来实现通信。
2、管道通信系统
管道通信系统是一种基于原有文件系统形成的一种通信方式，即是利用共享文件夹来实现进程间的通信的。这个共享文件就是管道。
其工作是以先进先出为顺序的单向通信方式。
读进程写进程写入 读出
为了协调通信双方，管道通信机制必须提供以下三个方面的协调能力。
1）互斥：当一个进程正对管道进行读或写数据时，另一进程必须等待。
2）同步：当写进程把一定数据写入管道后便阻塞等待，直到读进程取走数据后才能将写进程唤醒；当读进程在读空管道时也应阻塞等待，直到写进程将消息写入管道后才能将读进程唤醒。
3）对方是否存在：只有在确定进程通信的双方都存在时，方可进行通信。
3、消息传递系统
在消息传递系统中，进程的数据交换以消息为单位，程序员利用系统提供的一组通信命令来实现，消息传递系统可以分为：
１）、消息缓冲通信
２）、信箱通信
１）、消息缓冲通信
发送原语,主要工作是请求分给一个消息缓冲区,然后将消息正文传送到该缓冲区中,并向缓冲区中填写消息头，再将该消息缓冲区挂到接收进程的消息链上。
接收原语的主要工作是把消息链上的消息逐个读入到接收进程的接收区并进行处理。
消息缓冲是一种直接通信方式，即一个进程直接发送一个消息给接收进程。在通信时，发送进程采用发送原语向接收进程发送一个消息，
而接收进程则采用接收原语接收来自发送进程的一个消息。
消息：就是一组信息；
消息的格式：取决于消息机制的以及运行环境。
一种常用的格式：消息由消息头和消息体组成，消息头对消息加以说明，如消息的源和目标的标识符、长度、类型和一些控制信息等，是固定长度的；而消息体则是消息本身，是可变长的。
一个进程可以与多个进程通信，它可以向多个进程发送消息，也可以接收来自多个不同的机关进程发送来的消息。如果进程在一段时间内收到多条消息又来不及处理，就可将这些消息组织成消息队列。为此相应的进程控制块也要有：互斥访问消息队列的信号量、
消息数目和消息队列首指针。
消息缓冲通信方式具体实现是通过一对发送和接收原语来实现的：
发送原语的实现：
Send(receiver,message)
{向系统申请一个消息缓冲区；
将消息 message中的消息复制到消息缓冲区中；
P(S);
将消息缓冲区插入到 receiver接收进程的消息队列中；
V(so);
}
接收原语：
Receive(source,message)
{P(so);
P(s);
将消息队列中发送者为 source的消息缓冲区移出队列；
V（ S）
将消息缓冲区的消息复制到 message中；
用消息传递方式也可以解决有界缓冲池的生产者 — 消息费者问题。利用消息传递能力，可以同时传递信号和数据。
Int N=缓冲池的大小；
Int capacity=缓冲区容量；
Strust 消息结构 NULL=空消息；
Void main( )
Create_mailbox(produce_space);
Create_mailbox(consume_space);
For(int I=1;I<=N;I++)
Send(produce_space,null);
Parbegin(producer( ),consumer( ));}
Void producer( )
{message pmsg;
Receive(produce_space,pmsg);
Pmsg=生产者生产的消息；
Send(consume_space,pmsg);
}
Void consumer ( )
{message cmsg;
Receive(consume_space,cmsg);
取出消息进行消息费；
Send(produce_space,null);
}
２）、信箱通信
信箱的概念及工作方式的描述：
信箱是一种数据结构，可以用于存放信件。信箱通信是一种间接通信方式，当一个进程（发送进程）要与另一进程
（接收进程）通信时，可由发送进程创建一个链接两个进程的信箱，通信时发送进程只须把它的信件投入信箱，接收进程就在任何时候取走信件而不会丢失。
信箱的格式：
信箱逻辑上分成信箱头和信箱体；
信箱头中存放有关信箱的描述。
信箱体由若干格子组成，每格存放一封信件，格子的数目和大小在创建信箱时确定。
信件的传递可以是单向的，也可以双向的。
单向信箱通信方式：
只要信箱中有空格，发送进程便可向信箱中投递信件，若所有格子都已装满，
则发送进程或者等待，或者继续执行，
待有空格时再发送。类似地，只要格子中装有信件，接收进程便能取出一封信件。若信箱为空，接收进程或者等待，
或者继续执行。
双向通信方式：
信箱中既有发送进程发出信件，也有接收进程的回答信件。
上溢：由于发送进程和接收进程是以各自独立的速度向前推进的，当发送进程发送信件的速度超过接收进程的接收速度时，会产生上溢
下溢：接收进程向空信箱索取信件
问题的解决：这就需要两个进程同步，当信箱满时发送进程应等待，直至信箱有空格时再发送；对接收进程，当信箱空时，它也应等待，
直至信箱中有信件时，再接收。
五,进程的死锁
１、产生死锁的原因和必要条件
２、死锁的预防
３、死锁的避免
４、死锁的检测和解除
１、产生死锁的原因和必要条件
产生死锁的原因：
系统资源不足、进程推进顺序不当
产生死锁的必要条件：
互斥条件
不剥夺条件
部分分配条件
环路分配条件
２、死锁的预防
要想防止死锁的发生，只需破坏死锁的四个必要条件之一即可：
１）、破坏互斥条件
２）、破坏不剥夺条件
３）、破坏部分分配条件
４）、破坏环路条件
３、死锁的避免
在预防死锁的方法中所采取的几种策略，
总的来说都是增加较强的限制条件，虽然实现起来较简单，但却严重地损害了系统性能。死锁的避免方法中，所施加的限制条件较弱，同时把系统的状态分为安全状态和不安全状态，只要能使系统处于安全状态便可避免死锁的发生。
１）、安生与不安全状态
若在某一时刻，系统能按某种顺序如Ｐ １ Ｐ ２ …… Ｐ n
来为每个进程分配其所需要的资源，直至最大需求量，
每个进程都可顺利的完成，则称此时的系统状态为安全状态，序列Ｐ １ Ｐ ２ …… Ｐ n为安全序列。若某一时刻系统中不存在这样的一个安全序列，则称此时刻的系统状态为不安全状态。
在避免死锁的方法中，允许进程动态申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，便将资源分配给进程，否则进程等待。虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免死锁状态。
２）、利用很行家算法避免死锁
该算法就是检查申请者对各类资源最大需求量如果系统现存的各类资源可以满足当前它对各类资源的最大需求量时，
就满足当前的申请。换言之，仅当申请者可以在一定时间内无条件地归还它所申请的全部资源时，才能把资源分配给它。
例：有三个进程 P1P2P3，系统只具有 10
个同类资源。当前的分配情况是 P1P2P3
分别已分配得到资源数为 4,2,2，还需要资源数为 4,2,7，按照一种怎样的推进方式才可以避免死锁？
由上可以看出，银行家算法来分配资源是不会产生死锁的。因为分配资源时，
每次分配后总存在着一个进程，如果让它单独执行下去，必然可以获得它所需要的全部资源。也就是说此进程可以正常结束，而它结束后可以归还资源又能满足其他申请者的需要。
４、死锁的检测和解除
死锁的预防策略保守的，是通过限制访问资源和在进程上强加约束来解决死锁的。而且在很多情况下，被限制的情况并不一定就会产生死锁。故有些系统中并不在进程分配资源时采取任措施，而只是周期的检测是不发生了死锁，
出现死锁是再解除。
1）、死锁的检测
2）、死锁的解除
1）、死锁的检测
发现死锁的原理：是考察某一时刻系统状态是否合理，即是否存在一组可以实现的系统状态，能使所有进程都得到它们申请的资源而运行结束。
检测死锁的基本思想是：获得某时刻 t系统中各类可利用资源的数目向量 w(t)，对于系统中的一组进程 P1P2……P n，找出那些对各资源请求数目均小于系统现在所拥有的各类资源数目的进程，则这些进程都能获得所需全部资源并运行结束释放所占有的全部资源，将这些进程从进程组删除，从而使可用资源数目增加，然后对剩下的进程又做上述考察。如果进程组中所有进程都被删除了，则说此时的系统是安全的，否则，认为系统会发生死锁。
2）、死锁的解除
一旦检测到死锁，就需要某种策略来解除死锁。
撤消进程法：一种是取消所有的死锁进程，这是操作系统中最常用的一种方法；
二是连续取消死锁进程直到不再存在死锁。选择取消的进程顺序是基于最小代价原则。
资源剥夺法：连续剥夺资源直到不再存在死锁。资源的剥夺也要基于最小代价原则。
最小代价原则一般采用取消以下几种进程
目前为止消耗的处理器时间最少的
目前为止产生的输出最少的
预计剩下的时间最长的
目前为止分配的资源总数最少的
优先级最低的
例,假定系统有同类资源 12个，有 3个进程
P1,P2,P3来共享，已知 P1,P2,P3所需的资源的总数 8,6,9，它们申请资源的次序如下表。系统采用银行家算法为它们分配资源。问：
①哪次申请分配会使系统进入不安全状态？
②执行完序号为 6的申请后，各进程的状态和各进程已占有的资源数是什么？
序号 进程 申请资源数
1 P1 4
2 P2 4
3 P3 2
4 P1 1
5 P3 2
6 P2 2
…… …… ……
3.4 线程管理
一,线程的概念
二,线程的特性
三,windows2000线程的调度一,线程的概念
0、线程的引入
1、线程的概念
2、线程的分类
3、线程与进程的比较
0、线程的引入
（ 1） 创建进程 。 系统在创建进程时,必须为之分配其所必需的,除处理机以外的所有资源 。 如内存空间,I/O设备以及建立相应的 PCB结构 。
（ 2） 撤消进程 。 系统在撤消进程时,又必须先对这些资源进行回收操作,然后再撤消 PCB结构 。
（ 3） 进程切换 。 在对进程进行切换时,
由于要保留当前进程的 CPU环境和设置新选中进程的 CPU环境,为此需花费不少处理机时间
1、线程的概念
线程是比进程更小的活动单位，它是进程中的一个执行路径。
一个进程可以有多条执行路径即线程。
这样，在一个进程内部就有多个可以独立活动的单位，可以加快进程处理的速度，进一步提高系统的并行处理能力。
对线程有如下的描述：
1）、线程是进程中的一条执行路径
2）、线程有自已私有的堆栈和处理机执行环境。
3）、线程与父进程共享分配给父进程的主存及其他资源。
4）线程是单个进程所创建的许多个同时存在的线程中的一个。
步骤 读取数据 修改数据 写入数据读第 1个记录修改第 1个记录写入第 1个记录读第 2个记录修改第 2个记录写入第 2个记录读第 3个记录修改第 3个记录写入第 3个记录数据修改程序在进程模型下执行
进程中的所有线程共享该进程的状态和资源，
它们驻留在同一块地址空间中，并且可以访问到相同的数据。当一个线程改变了共享的信息时，其他线程访问这些信息时能够知道它变化后的结果。因此可以看出线程如下优点：
1）、在一个已有进程中创建一个新线程比创建一个全新进程所需的时间少。
2）、终止一个线程比终止一个进程花费的时间少。
3）、线程间切换比进程切换花费的时间少
4）、线程提高了不同执行程序间通信的效率。
2、线程的分类
1）用户级线程：
在一个纯用户线程的软件中，有关线程管理的所有工作都由应用程序完成，内核没有意识到线程的存在。任何应用程序可以通过使用线程库设计成多线程程序。
线程库是用于用户级线程管理的一个例程包，
它包含用于创建和销毁线程、在线程间传递消息和数据、调度线程执行及保存和恢复线程上下文等的代码。
用户级线程的所有活动发生在用户空间中并且在一个进程内，内核不知道这些活动。内核继续以进程为单位进行调度，并具给进程指定一个执行状态。
2）、内核级线程
在一个纯内核级线程的软件中，有关线程管理的所有工作都是由内核完成的，应程序部分没有进行线程管理的代码，只有一个到内核线程设施的应用程序编程接口。
任何应用程序都可以设计成多线程程序，所有线程都在一个进程里。
内核为该进程及其线程保存整个上下文环境信息，调度是由内核基于线程的基础完成的。内核可以同时把同一个进程中的多个线程调度到多个处理中；如果进程中的一个线程被阻塞，
内核可以调度一个进程中的另一个线程；而且内核例程自身也是可以使用多线程的。
使用用户级线程比使用内核级线程的优点：
1）、线程切换不需要内核模式特权
2）、调度算法可以去适应应用程序，
3）、用户线程可以在任何操作系统中运行，
不需要对底层内核进行修改以支持用户级线程。
线程库是一组供所有应用程序共享的应用级实用程序。
使用用户级线程比使用内核级线程的缺点：
1）、当用户级线程执行一个系统调用时，
不仅这个线程会被阻塞，进程中所有线程都会阻塞。
2）、在用户线程中，一个应程序不能利用多处理技术，内核一次只把一个进程分配给一个处理器，即一个进程中只有一个线程可以执行。
3、线程与进程的比较
1,调度,在传统的操作系统中,拥有资源的基本单位和独立调度,分派的基本单位都是进程 。
2,并发性,在引入线程的操作系统中,不仅进程之间可以并发执行,而且在一个进程中的多个线程之间亦可并发执行,因而使操作系统具有更好的并发性,从而能更有效地使用系统资源和提高系统吞吐量 。
3,拥有资源,不论是传统的操作系统,还是设有线程的操作系统,进程都是拥有资源的一个独立单位,它可以拥有自己的资源 。
4,系统开销,由于在创建或撤消进程时,系统都要为之分配或回收资源,如内存空间,I/O设备等 。 因此,操作系统所付出的开销将明显地大于在创建或撤消线程时的开销 。
二,线程的特性
1、线程的状态
2、线程数据结构
3、线程相关的函数
1,线程的状态
1）、就绪：可以被调度执行
2）、备用：处于备用状态的线程是某一特定处理器的下一个执行对象
3）、运行：一旦调度程序对线程执行完环境切换，线程就进入备用状态开始执行。
4）、等待：当线程被一个事件阻塞、为了同步自愿等待或者一个环境子系统指引它把自身挂起时，该进程进入等待状态。
5）、转换：在线程准备执行而其内核堆栈被调出内存之外，线程进入转换状态。
6）、终止：线程执行完 (或强制性终止 )就进入终止状态。
2、线程数据结构
线程是由线程块代表的，线程块通常包括线程 ID、进程标识、动态优先级、基本优先级、线程处理仿射、线程执行、
警告状态、各种性能计数器、终止端口、
线程退出状态及线程环境块指针。
线程环境块 TEB包括：线程 ID、堆栈信息、异常列表、临界区计数、当前位置及其他信息。
3、线程相关的函数
1)CreateThread:创建新线程
2)CreateRemoteThread:在另一个进程中创建线程
3)ExitThread:正常的结束线程的执行
4)terminatethread:终止线程
5)GetExitCodeThread:获得另一个线程的退出代码
6)GetThreadTime:返回另外一个线程的定时信息
7)Get/SetThreadContext:返回或更改线程的处理器寄存器
8)GetThreadSelectorEntry:返回另一个线程的描述符表项下一页三,windows2000线程的调度
1,windows调度概述
2、线程的优先级
3、时间片
4、调度方案
1,windows调度概述
Windows2000实现一个优先级驱动，可抢先的调度系统，即总是运行优先级最高的就绪就程。当一个线程被选择运行，
它将运行一段时间 (时间片），线程在运行时间内没有执行完时得让出；当有较高优先级的线程准备运行时，也得让出处理器。
Windows2000调度代码在内核中实现，散布在发生调度相关事件的内核中。线程调度发生在 DPC调度一级，它可由以下任何一个事件触发：
1）、线程由就绪变为执行
2）、由于线程的时间片结束
3）、系统调用或者 windows2000自身改变
4）、正在运行的线程的处理器相似性的改变
在以上每个事件发生时,windows2000必须决定下一个要执行的是哪一个线程。在 windows2000选择运行一个新的线程，将对它进行“环境切换”。
环境切换：是保存与正在运行的线程相关的非永久性的机器状态，加载另一个线程的非永久性状态并开始执行新线程的进程。
2、线程的优先级
Windows2000大在内部使用 32个线程优先级，可分为三个部分：
1）,16个实时级别（ 16~31）
2）,15个变量级别（ 1~15）
3）,1个系统级别（ 0），为清零页线程保留
线程优先级是从两个不同的角度分配：
Win32API：是依据在创建进程时分配的优先等级来组织进程。
Windows2000内核：是依据进程中各个线程的相对优先级来组织进程。
线程优先级的确定：
线程启动时就继承进程的基本优先级，
它可以使用 Task Manager来改变，
也可以使用 win32函数 setprocessPriority
来改变。
一个进程只能有一个单一的优先级，每个线程却具有两个优先级值：当前优先级和基本优先级。
虽然 windows2000具有被称作“实时”的优先级，但它并不是真正的实时操作系统，它并不提供保证中断的等待时间。
3、时间片
时间片：是在 windows2000检查具有相同优先级的其他线程是否应该开始运行之前，一个线程开始的一段时间。
每个线程都有一个时间片值来代表时间片结束之前线程可运行的时间片长度。
Windows2000professional上线程启动的时间片值为 6
Windows2000server上线程启动的时间片值为 36
其时间片值较大的原因是为了减少环境切换的时间。通过具有较长的时间片，作为客户请求的结果而被唤醒的服务器的应用程序有足够的时间完成请求并在它的时间片结束之前恢复到等待状态
每当时钟中断发生时，时钟中断例程都会从线程的时间片中减去一个固定值（ 3）。如果没有剩余的线程时间片，那么将触发时间片结束处理，而另一个线程就可能被选择去运行。故在,
Win 2000professional，线程运行 2个时钟间隔；
Win 2000server上线程将运行 12个时钟间隔。
4、调度方案
单处理器中常用的调度方案：
1）自愿切换
2）抢先
3）时间片结束
4）终止多处理器系统调度方案
1）、理想处理器和最后处理器
2）、为就绪线程选择处理器
3）、选择线程在指定的处理器上运行
4）、在多处理器系统中,windows2000
并不是总选择优先级最高的有线程在给定的处理器上运行。
