进程与线程

PCB-进程控制块

进程标识符

处理机状态

进程调度信息

目的--为了使参与执行的每个程序独立运行

作用

1. 作为独立运行基本单位的标志
2. 提供进程管理所需要的信息
3. 提供进程调度需要的信息
4. 实现与其他进程同步的通信
5. 实现间断性方式

1、进程PCB包含的字段是进程ID,进程组ID,父进程和子进程,堆指针,程序计数器,调度状态(运行,就绪,阻塞),权限(允许进程的系统资源)访问),通用寄存器的内容和打开的文件。2、线程TCB包含的字段(寄存器值,堆栈指针,程序计数器,调度状态),以及一些特定值,如线程id和指向包含该线程的进程的指针。请注意,线程之间没有保护。

原语

若干条指令组成，用于完成一定功能的一个过程

特点----不可被分割，要不全做，要不全不做

举例---激活原语active，挂起原语suspend

P-C问题中，能否使生产者进程中的两条wait 原语交换顺序？为什么？

不能交换顺序，初始顺序是同步信号量在前面，互斥信号量在后面，要先判断缓冲池里有没有产品，再决定是否要进去，如果缓冲池里没有产品，wait(empty)进去了之后，signal(full)是释放信号量是无法知道的。

进程--

特征--独立异步动态并发

创建，终止

就绪，运行，阻塞（不占用cpu）--基本状态

就绪挂起，阻塞挂起

当进程进入阻塞状态时，会占用大量内存，因此采用挂起状态将阻塞和就绪的进程放入虚拟内存(硬盘)，判断是否挂起就是通过页表

状态转变：

创建和运行也可以被挂起变为就绪挂起状态

线程--TCB

线程是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只拥有一点在运行中必不可少的资源，但它可与同属一个进程的其它线程共享进程所拥有的全部资源。

进程同步与互斥

临界资源 ----一次仅允许一个进程使用的资源。

临界资源的访问

1）进入区。在进入区要检查可否进入临界区，如果可以进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。
2）临界区。进程中正在访问临界资源的那段代码，又称临界段。
3）退出区。将正在访问临界区的标志清除。
4）剩余区。代码中的其余部分。

信号量、临界区定义

• 临界区：并发进程中，每个进程访问临界资源的代码称为临界区
• 信号量

• 整型信号量：开一个整型变量S
• 记录型信号量：整型信号未实现“让权等待”，多定义一个变量list,来存储让权了的进程
• AND型信号量：多个进程共用多个临界区资源

实现同步与互斥

• 锁：加锁、解锁操作；
• 信号量：P、V 操作（wait和signal）；

同步

同步为直接制约，两个进程是有顺序的，

防止两个同时进入等待区，需满足空闲让进，忙则等待，有限等待，让权等待

互斥

互斥为简介制约，一个执行，另一个需等待，没有顺序

锁--实现互斥

在进程的操作前加锁，后去锁，也就是拍照的房间，有人在里面，外面的人就无法进行拍照。

在程序中，一个进程上锁，另一个进程会进入忙等，直到解锁后，该进程才会进入临界区，这就是忙等待锁，也就是自旋锁。

忙等时，该进程仍然占用CPU，还有一种锁在上锁时，另一个进程会进入等待队列，让出CPU，该锁叫为无等待锁，也就是互斥锁

避免死锁的一个方法银行家算法

各种锁

信号量--实现互斥

设置信号量S，

• 初值为1，表示未被占用
• 变为0，表示有一个进入
• 变为-1，表示一个进入，一个等待

单个进程变化

1-->0

P-->访问资源--->V

互斥情况，每个进程都需要先进行P操作，然后对灵界资源访问，最后执行V操作

整个信号量变化

当执行P操作，初值会变为0，表示该资源可以被分配，这时，另一个进程执行P操作，会使信号量变为-1，表示该该临界资源被占用，进程会阻塞

信号量--实现同步

设置信号量S，

• 初值为0，表示不需要
• 负数表示等待

举例子

妈妈叫儿子吃饭这个过程

初始化

• 做饭--cook=0
• 吃饭--eat=0

过程

1. 妈妈向儿子发送是否吃饭请求，然后等待回应

1. P(eat)操作

1. eat变成-1

2. 儿子发送吃饭回应，然后发送是否做饭请求，然后等待回应

1. V(eat)操作，P(cook)操作

1. eat变成0，cook变成-1

3. 妈妈收到做饭回应，执行做饭，然后发送做饭回应

1. V(cook)操作

1. cook变成0

4. 儿子收到做饭的回应，被唤醒，开始吃饭

分析

首先，需要一个先执行V操作，后执行P操作，另一个先执行P操作，后执行V操作

其次，先执行V操作可以看作是同步开启的条件

消费者-生产者

int in=0,out=0;

item buffer[n];

auto mutex=1,empty=n,full=0;

void producer{

   while(1){

       new temp;

       wait(empty);

       wait(mutex);

       buffer[in]=temp;

       in=(in+1)%n;

       signal(mutex);

       signal(full);

   }

}

 

void consumer(){

   while(1){

       wait(full);

       wait(mutex);

       int good=buffer[out];

       out=(out+1)%n;

       signal(mutex);

       signal(empty);

   }

}

同步问题

哲学家就餐--对于互斥访问有限(I/O设备)有效

问题：五个哲学家在桌子上思考，吃饭，桌子上有一只筷子，两只筷子才能吃饭，尽快可能思考合理的方案

网上的四种方案

1. 全拿一边的叉子，人人没饭吃
2. 一个人拿左右两个，导致每次只能一个人吃饭
3. 按偶数或奇数来选择吃饭的人，可以每次两人吃饭
4. 添加一个条件，需要满足，左边和右边的人都没有进餐，那么这位哲学家可以进餐，进餐完通知其他哲学家。

读者，写者

读者-写者的问题描述：

• 「读-读」允许：同一时刻，允许多个读者同时读
• 「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写
• 「写-写」互斥：没有其他写者时，写者才能写

三种方案

1. 读者优先

1. 设置变量：读者的人数，控制写操作的信号量，控制写操作互斥的信号量

2. 写者优先

1. 读者的人数，控制读操作的信号量，控制读操作互斥的信号量，写者的人数，控制写操作的信号量，控制写操作互斥的信号量

3. 公平

例题-GET,PRO,PUT

写入与取出都是先wait后signal，区别是增加空的数目还是有数据的数目

需要先设置变量

然后实现方法

GET---输入BUF1

whiel(1){

wait(empty1);

   wait(matex1);

   执行输入

   signal(matex1);

   signal(full1);

}

PRO---从BUF1取出，写入到BUF2中

whiel(1){

wait(full1);

   wait(matex1);

   执行取出

   signal(matex1);

   signal(empty1);

wait(empty2);

   wait(matex2);

   执行输入

   signal(matex2);

   signal(full2);

}

PUT--从BUF2读取并输出

whiel(1){

wait(full2);

   wait(matex2);

   执行取出

   signal(matex2);

   signal(empty2);

}