OS

分时技术

主机以很短的“时间片”为单位,把 CPU 轮流分配给各个终端使用,直到全部作业被运行完。

CPU 的态

内核态

能够访问所有资源和执行所有指令

管理程序/OS内核

用户态

仅能访问部分资源,其它资源受限

用户程序

用户态与内核态之间的转换

临界资源 一次只允许一个进程独立访问的资源。

临界区 进程中访问临界资源的程序段。

系统调用

操作系统内核为应用程序提供的服务或函数。

访问临界区的方法:硬件方法 软件方法:锁 信号量

锁机制 设置“标志”表示临界资源是否可用。上锁 开锁 原语 原子性操作,不可中断

信号灯

进程管理

进程:非正式定义:运行中的程序。

进程的机器状态——程序在运行时可以读取或更新的内容:

内存、寄存器、打开的文件列表。

进程状态:

运行 running

就绪 ready

阻塞 blocked

进程调度

条件变量

当某些 condition 不满足时,线程可以把自己加入队列,waiting 该 condition。另外某个线程,当改变 condition 时,可以唤醒一个或多个线程(通过在 condition 上 signal,让 TA 们继续执行。

调用 wait 和 signal 时要持有锁。

生产者/消费者(有界缓冲区)问题

Mesa 语义。总是使用 while 循环。

信号量

二值信号量(锁)

信号量用作条件变量

生产者/消费者(有界缓冲区)问题

哲学家就餐问题

修改某个或某些哲学家的取餐叉顺序。

死锁

互斥:线程对于需要的资源进行互斥的访问。

持有并等待:线程持有了资源,同时又在等待其它资源。

非抢占:线程获得的资源不能被抢占。

循环等待:线程之间存在一个环路,环路上每个线程都额外持有一个资源,而这个资源又是下一个线程要申请的。

死锁的预防

循环等待

也许是最实用和最常用的,就是让代码不会产生循环等待。最直接的方法是获取锁的时候提供一个全序关系。如规定先申请 L1 锁,再申请 L2 锁。在复杂的难以做到全序的系统中,可以使用偏序。

持有并等待

通过原子地抢锁来避免。需要先获得 prevention 锁。

非抢占

trylock

可能会引起活锁,可以在循环等待的时候,先随机等待一个时间,再重复整个动作,可以降低线程间的重复循环干扰。

互斥

完全避免互斥。使用无等待(wait-free)的数据结构。如比较并交换 CAS。

通过调度避免死锁

检查和恢复

基于锁的并发数据结构

可扩展的计数——懒惰计数器 sloppy counter

线程:是操作系统调度的最小单元。一个进程中可以创建多个线程,每个线程都有各自的程序计数器、堆栈和局部变量等属性,可以访问共享的内存变量。

同步和 P-V 操作