Docs by JrHimself

外观

进程管理 ​

进程 ​

进程是程序的一次执行过程，是系统进行资源调度和分配的一个独立单位。

特征 ​

  1. 结构特征：对于其结构特征，进程=程序+数据+PCB。
    • 静态描述：程序和数据集合
    • 动态描述：进程控制块PCB
  2. 动态性：由于进程是程序的一次执行过程，具有生命期，创建产生，调度执行，等待得到资源阻塞，撤销消亡。
  3. 并发性：依赖于 PCB，共享资源让进程间相互约束、相互依赖。
  4. 独立性：进程是系统进行资源调度和分配的独立单位，独立运行、独立获得资源。
  5. 异步性 / 间断性：不可预知的速度

基本状态 ​

若划分成三种，可以看成就绪、执行、阻塞。

image.png

加上创建和终止，就是五种。

image.png

进一步细化，还有被换出内存的挂起状态。当进程被挂起时称它为静止的，反之是活动的。

image.png

五状态进程模型和七状态进程模型：

image.png

image.png

进程管理中的数据结构 PCB ​

同一状态的 PCB 链接成队列，不同的队列表示不同状态。进程管理的索引依靠不同状态的索引表，索引表中存放了相应PCB的地址。

进程控制 ​

进程管理中最基本的功能。用于创建一个新进程、终止已完成或因出现某事件而使其无法进行下去的进程、或负责进程运行中的状态转换。

由构成操作系统内核的各种原语实现。阻塞、唤醒一般由OS实现，而挂起、激活可由用户干预。

进程的并发性反映在对资源的竞争而产生的相互约束上。

进程同步 ​

使并发进程有效地共享资源和相互合作，从而使程序执行具有可再现性。

并发进程间的制约关系 ​

  • 互斥关系：进程间排他使用资源（间接相互制约）
  • 同步关系：进程间按某种时序执行（直接相互制约）

临界资源 ​

凡以互斥方式使用的共享资源都称为临界资源，一次只允许一个进程使用。进程访问临界资源的代码称为临界区。

准则 ​

  • 空闲让进：无进程处于临界区内时，可让一个申请进入该临界区的进程进入。
  • 忙则等待：临界区有进程，申请进入的进程必须等待。
  • 有限等待：进程进入临界区请求必须在有限时间满足。
  • 让权等待：等待（不能）进入临界区的进程必须立即释放 CPU。

信号量机制 ​

信号量是资源的数量。定义：

c
Semaphore s;

不要拼错

原语 ​

原语具有严格的不可分割性，执行过程中不允许中断。

  • wait 操作（P 操作）：减 1 操作，申请分配一个单位的资源。
    • wait(s) - 对信号量 s 进行 wait 操作。
  • signal 操作（V 操作）：加 1 操作，释放一个单位的资源。
    • signal(s) - 对信号量 s 进行 signal 操作。

整型信号量 ​

即将 Semaphore 定义为一非负整数。

对应的操作描述：

  1. wait(s)：如果无可用资源，空转

    c
    while (s <= 0);
s -= 1;

    问题在于空转操作违反了“让权等待”原则，严重拖累了CPU执行效率。

  2. signal(s)

    c
    s += 1;

记录型信号量 ​

c
struct {
	int value; // 资源数目
	struct process_control_block *list; // 阻塞队列
} Semaphore;

Semaphore* s;

对应的操作描述：

  1. wait(s)

    c
    s->value--;
if (s->value < 0)
	block(s->list);

  2. signal(s)

    c
    s->value++;
if (s->value <= 0)
	wakeup(s->list);

其中，s->value 代表资源可用数量，或小于 0 时代表等待队列等待该资源的进程数。其初始值是资源数目。

AND 型信号量 ​

当多个进程需要获得相同的多个资源时，容易产生死锁。使用 AND 信号量集机制，可以保证进程一次性获得所需的全部资源，从而避免死锁。这种机制允许进程在一个原子操作中请求多个资源，只有当所有请求的资源都可用时，才会分配资源给进程。

Swait 定义：

c
Swait（S1，S2，… Sn ）{
	while(TRUE){
		if (S1 ≥1 && … && Sn ≥ 1){
			for (i=1;i<n;i++) Si--; 
			break;
		} else{
			Place the process in the waiting queue associated with the first 
			Si ＜1, and set the program counter of this process to the beginning 
			of SP operation 
		}
	}
}

对应的 Ssignal 操作定义如下：

c
Ssignal（S1，S2，… Sn）{
	while(TRUE){
		for (i=1;i<=n;i++) {
			Si++; 
			Remove all the process waiting in the queue associated with Si 
			into the ready queue.
		}
	}
}

一般信号量集机制 ​

Si, ti, di

信号量机制的应用 ​

实现进程互斥 ​

设置一个初值为1的信号量 mutex，其wait、signal操作出现在同一进程临界区的头和尾部

描述前趋关系 ​

同一信号量的wait、signal操作出现在不同进程，互发信号

考试 ​

  1. 先定义信号量和初值；
  2. 写清各个进程和其过程；
  3. 加上 wait 和 signal；
  4. 检查。

考虑解决同步问题，然后检查是否有共享资源、处理进程互斥。

管程机制 ​

管程 → 管理程序（monitor）

定义：一个数据结构和在该数据结构上能被并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。

image.png

条件变量 ​

请求临界资源不能满足时，使用条件变量说明等待原因。

c
Condition x, y;
x.wait(); // 将执行进程挂到与 x 对应的等待队列上
x.signal(); // ...

应用 ​

  1. 变量声明；
  2. 定义过程；
  3. 初始化变量。

高级通信 ​

信号量机制是一种低级通信，效率低、对用户不透明。高级通信反之。

  1. 共享存储器系统；
  2. 消息传递系统；
  3. 管道通信系统。

消息传递通信 ​

  1. 直接通信

    c
    Send(receiver, message);
Receive(sender, message);

  2. 间接通信

    c
    Send(mailbox, message);
Receive(mailbox, message);

消息缓冲队列通信机制 ​

  1. 消息缓冲区

    c
    typedef struct message_buffer {
		int sender;
		int size;
		char* text;
		struct message_buffer* next;
} message_buffer;

  2. PCB

    c
    typedef struct process_control_block {
		...
		struct message_buffer* mq; // message queue
		Semaphore mutex;
		Semaphore sm;
		...
} PCB;

线程 ​

线程作为调度和分派的基本单位，基本上不拥有资源。只有少量资源，但共享其所属进程所拥有的全部资源。