2.6 线程的阻塞和唤醒
跟进程一样，正在执行的线程因为某种事件的发生而无法继续执行时，系统应允许它调用阻塞原语阻塞自己。
1．引起线程阻塞的事件
从操作系统原理课程中我们已经知道，引起进程阻塞的典型事件之一为等待I/O操作的完成：相对高速的CPU而言，I/O 设备的速度显得较慢，所以在一般情况下，一个进程在调用某类设备的设备驱动程序启动相应的I/O操作后，设备驱动程序将调用阻塞原语阻塞现行进程（即启动该I/O操作的进程），直至指定的I/O操作完成后，再由相应的I/O中断服务程序将阻塞的进程唤醒。虽然，引起线程阻塞的事件类似于进程，但在我们的实例中，由于直接使用DOS 操作系统提供的I/O功能，所以不考虑因启动I/O操作引起线程阻塞这一情况。
这里引起线程阻塞的典型事件有两个：一是并发执行的线程间竞争临界资源，如线程１与线程２共享某种软件资源（如某个变量、或缓冲区、或某个队列），为了互斥，线程１正在使用该资源时，若线程２也请求使用该资源，则线程２必须阻塞，等线程１使用完后，再唤醒线程２；二是相互合作的线程间的同步，如线程２等待接收线程１发来的消息，在线程１将消息发送来之前，线程２阻塞，直至线程１发完消息后再将线程２唤醒。
2. 阻塞与唤醒的过程
我们将所有处于阻塞状态的线程的TCB按阻塞的不同原因排成多个队列。为此，需在TCB中增加一链接字段next，以方便TCB的排队。 一个正在执行的线程因某种原因而阻塞时，必须给出因该原因而阻塞的阻塞队列的队首信息，阻塞原语应完成以下主要工作：将线程的状态改成阻塞态；将线程插入指定的阻塞队列末尾；重新进行CPU调度。
当阻塞线程所等待的事件完成后，必须唤醒相应线程。唤醒原语中同样需指出跟指定事件有关的阻塞队列队首信息。另外，有可能同时有多个线程在等待该事件完成，实例中采取的方法是唤醒阻塞队列头上的第一个线程。唤醒原语应完成以下主要工作：把阻塞队列头上的第一个线程的TCB取下来，并将其状态改为就绪态，如果系统设置了就绪队列，还应插入就像队列。
2.7 线程的同步与互斥
当多个线程并发执行时，与多个进程并发执行一样，它们可能会共享临界资源，也可能相互协作以完成总的任务，因此线程之间也存在着同步与互斥的问题，所以必须有相应的同步机制来实现线程间的同步与互斥。这里我们选择操作系统原理中介绍的记录型信号量机制来作为线程的同步机制。
记录型信号量的数据结构定义如下： typedef struct{ int value;
struct TCB *wq; } semaphore;
对信号量的P操作和V操作的描述如下：
- 26 -
void p(semaphore *sem) {
struct TCB **qp; disable();
sem->value=sem->value-1; if(sem->value<0){ qp=&(sem->wq); block(qp); }
enable(); }
void v(semaphore *sem) {
struct TCB **qp; disable();
qp=&(sem->wq);
sem->value=sem->value+1; if(sem->value<=0)
wakeup_first(qp); enable(); }
为了实现互斥，可设置一互斥信号量mutex： semaphore mutex; mutex=1;
然后，在相应的需要互斥的线程中，将临界区CS放在P(&mutex)和V(&mutex)之间。线程同步问题也同样可使用该信号量机制来解决，在这里就不再举例说明了。
在本课程设计中要求使用上面介绍的记录型信号量来实现生产者消费者问题，请同学们自行完成。
2.8 利用消息缓冲队列通信机制实现线程间通信
2.8.1 消息缓冲队列通信机制介绍
消息缓冲队列通信机制首先是由美国的Hansan提出来的，后来被广泛地应用于本地进程之间的通信中。其基本思想是根据“生产者——消费者”原理，利用内存中公用消息缓冲区实现进程间的信息交换。
在这种通信机制中，首先需要在内存中开辟若干空闲消息缓冲区，用以存放要通信的消息。每当一个进程需要向另一个进程发送消息时，便向系统申请一个空闲消息缓冲区，并把已准备好的消息复制到该缓冲区，然后把该消息缓冲区插入到接收进程的消息队列中，最后通知接收进程。接收进程接收到发送进程发来的通知后，从本进程的消息队列中摘下一消息缓冲区，取出其中的信息，然后把消息缓冲区作为空闲消息缓冲区归还给系统。系统负责管理公用消息缓冲区以及消息的传递。
2.8.2主要数据结构设计
- 27 -
1．消息缓冲区
在消息缓冲队列通信机制中，主要用到的数据结构是消息缓冲区，它可描述如下： struct buffer {
int sender; /* 消息发送者的内部标识 */ int size; /* 消息长度 <=NTEXT 个字节 */ char text[NTEXT]; /* 消息正文 */
struct buffer *next; /* 指向下一个消息缓冲区的指针 */
};
假设，系统在对消息缓冲区进行初始化时，一共设置了NBUF个空闲的消息缓冲区，为了便于管理，通常将所有空闲缓冲区插入到空闲缓冲队列freebuf中，该队列是一临界资源， 无论是发送线程发送消息时从该队列中摘下一空闲缓冲区的操作（即申请空闲缓冲区的操作），还是接收线程在消息接收完毕时归还消息缓冲区的操作，所有对该队列的操作都必须互斥地进行。为此，系统为空闲消息缓冲队列设置了一互斥信号量mutexfb，其初值为{1,NULL}；另外，当空闲缓冲队列为空时，发送线程不能再获得空闲消息缓冲区发送消息，必须阻塞等待——直到接收线程归还一个空闲消息缓冲区为止，为解决这个问题，又为空闲缓冲队列设置了一个计数信号量sfb，其初值为{NBUF,NULL}。
2．TCB中与通信有关的数据项
在利用消息缓冲队列进行线程间的通信时，除了需要设置消息缓冲区外，还需对线程控制块TCB进行扩充，在原来的TCB的基础上再增加以下字段：
struct buffer *mq; /* 接收线程的消息队列队首指针 */
semaphore mutex; /* 接收线程的消息队列的互斥信号量 */
semaphore sm; /* 接收线程的消息队列的计数信号量，用于实现同步 */
在对TCB进行初始化时，mq的初值为NULL，mutex的初值为{1,NULL}，sm的初值为{0,NULL}。
2.8.3主要函数设计
在实现消息缓冲队列通信机制时，主要设计了以下函数： 1．获取空闲缓冲区函数getbuf()
（1）函数申明原型：struct buffer *getbuf(void)
（2）功能：从空闲消息缓冲队列头上取下一空闲消息缓冲区。 （3）输入：无
（4）输出：指向所获得的空闲消息缓冲区的指针 （5）函数实现的程序描述：
struct buffer *getbuf(void)
{
struct buffer *buff; buff=freebuf;
freebuf=freebuf->next; return(buff); }
- 28 -
2．插入缓冲区到缓冲队列函数insert()
（1）函数申明原型：void insert(struct buffer **mq,struct buffer *buff) （2）功能：将buff所指的缓冲区插到*mq所指的缓冲队列末尾。 （3）输入：
mq：将要插入的缓冲队列的队首指针的指针； buff：消息缓冲区指针。 （4）输出：无
（5）函数实现的程序描述：
void insert(struct buffer **mq,struct buffer *buff)
{
struct buffer *temp;
if(buff==NULL) return; buff->next=NULL; if(*mq==NULL) *mq=buff; else
{
temp=*mq;
while(temp->next!=NULL) temp=temp->next; temp->next=buff; } }
3．发送原语send()
在发送消息时，消息的发送者必须提供接收者的标识符、消息长度及消息正文的起始地址等信息。然后在发送原语里申请一空闲的消息缓冲区，用相应的信息来装配该消息缓冲区，并将它插入到接受者的消息队列中去。
（1）函数申明原型：void send(char *receiver,char *a,int size)
（2）功能：将地址a开始的size个字节发送给外部标识符为receiver的线程。 （3）输入：
receiver：接收线程的外部标识符的指针； a：要发送的消息正文的指针； size：要发送的消息正文的长度。 （4）输出：无
（5）函数实现的程序描述：
void send(char *receiver,char *a,int size)
{
struct buffer *buff; int i,id=-1;
disable();
- 29 -
for(i=0;i /*如果接收者线程不存在，则不发送，立即返回*/ if(strcmp(receiver,tcb[i].name)==0){ id=i; break; } } if(id==-1) { printf(\ enable(); return; } /*获取空闲消息缓冲区*/ p(&sfb); p(&mutexfb); buff=getbuf(); v(&mutexfb); /*填写消息缓冲区各项信息*/ buff->id=current; buff->size=size; buff->next=NULL; for(i=0;i /*将消息缓冲区插入到接收者线程的消息队列末尾*/ p(&tcb[id].mutex); insert(&(tcb[id].mq),buff); v(&tcb[id].mutex); v(&tcb[id].sm); enable(); } 4．获取消息缓冲区函数remov() （1）函数申明原型：struct buffer *remov(struct buffer **mq,int sender) （2）功能：接收线程从它自己的消息队列中取下sender发送给它的消息缓冲区。 （3）输入： mq：接收线程的消息队列的队首指针的指针； sender：发送线程的内部标识符； （4）输出：所获得的消息缓冲区的指针 （5）函数实现的算法描述： 该函数需要完成的工作比较简单，首先在mq消息队列中查找发送线程标识符为sender的消息缓冲区，若找到则从mq所指示的消息缓冲队列中移除该消息缓冲区并返回该缓冲区，否则返回空。程序实现请同学们自己完成。 5．接收原语receive() - 30 -