进程与线程
PCB-进程控制块
进程标识符
处理机状态
进程调度信息
目的--为了使参与执行的每个程序独立运行
作用
- 作为独立运行基本单位的标志
- 提供进程管理所需要的信息
- 提供进程调度需要的信息
- 实现与其他进程同步的通信
- 实现间断性方式
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
过程
- 妈妈向儿子发送是否吃饭请求，然后等待回应
- P(eat)操作
- eat变成-1
- 儿子发送吃饭回应，然后发送是否做饭请求，然后等待回应
- V(eat)操作，P(cook)操作
- eat变成0，cook变成-1
- 妈妈收到做饭回应，执行做饭，然后发送做饭回应
- V(cook)操作
- cook变成0
- 儿子收到做饭的回应，被唤醒，开始吃饭
分析
首先，需要一个先执行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设备)有效
问题：五个哲学家在桌子上思考，吃饭，桌子上有一只筷子，两只筷子才能吃饭，尽快可能思考合理的方案
网上的四种方案
- 全拿一边的叉子，人人没饭吃
- 一个人拿左右两个，导致每次只能一个人吃饭
- 按偶数或奇数来选择吃饭的人，可以每次两人吃饭
- 添加一个条件，需要满足，左边和右边的人都没有进餐，那么这位哲学家可以进餐，进餐完通知其他哲学家。
读者，写者
读者-写者的问题描述：
- 「读-读」允许：同一时刻，允许多个读者同时读
- 「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写
- 「写-写」互斥：没有其他写者时，写者才能写
三种方案
- 读者优先
- 设置变量：读者的人数，控制写操作的信号量，控制写操作互斥的信号量
- 写者优先
- 读者的人数，控制读操作的信号量，控制读操作互斥的信号量，写者的人数，控制写操作的信号量，控制写操作互斥的信号量
- 公平
例题-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);
}
