抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

操作系统课程笔记

请设置文章作者

发布于：Jan 1, 2000
次浏览

进程管理

  • 并发proc特点
    • 执行顺序不确定
    • todo
  • 进程定义
    • todo
  • 进程组成
    • 程序段
    • 数据段
    • PCB

PCB信息

  • 标识
    • proc标识
    • 父标识
    • 用户标识
    • 等
  • 现场信息
    • reg信息
    • 堆栈指针
    • 等
  • 控制信息
    • proc状态
    • 调度信息
    • DS信息
      • 数据结构：如父指针
    • 队列信息
      • pcb地址，如运行队列
    • 位置信息
      • 内存位置
    • 通信信息
      • 消息队列
    • 等

proc基本状态

最基本的，可细化的状态

  • 运行
  • 就绪
    • 就绪态不能到等待态，要运行才能控制
  • 阻塞(等待)
    • 等待态不能直接到达运行态，要先就绪
  • 进程控制语：原语
    • 机器指令构成的程序段的自己，控制proc执行
    • 不可分割

proc调度

  • proc调度时机
    • proc执行完
    • IO等原因
    • 执行某原语
    • 被抢占
    • 时间用完
  • proc调度算法
    • todo

临界资源

共享资源，但一次应该只能有一个proc使用

  • 互斥：对临界资源的竞争
  • 同步： 有合作任务的proc直接需要同步，如p2需要p1的结果才能进行，则p1制约p2
  • 临界区(Critical Section, CS)
    • 进程中涉及到临界资源的 程序段 称为临界区，一次只能有一个proc进入临界区，进程间互斥，退出临界区或换别的proc进入

信号量与PV操作

信号量(semaphore) 用于表示资源实体(多少可用)，是与队列有关的整型变量，其取值只能由PV操作改变

1
2
3
4
5
6
7
8
9
10
11
12
13
struct semaphore{
    int value;   // 表示剩余资源
    Queue queue; // 表示等待队列
};

P(S){
    S.value--;  // 先--才能把要申请资源的proc记录上
    if(S<0) 放队列;
}
V(S){
    S.value++;
    if(P<=0) 唤进程;
}

注意pv操作是先 +- 资源再判断

  • P：申请资源，value-1，减1后value<0，表示资源已被占用，放入等待队列
    • 小于0就记录了有多少想用但没能用，0刚好用完
  • V：释放资源，value+1，加1后value<=0，表示有proc在等待队列等待该资源，唤醒一个proc
    • 归还资源后还不大于0，说明还有proc想资源
  • 共用sem：常用于实现资源互斥，初值value设为1，有PV操作
  • 私用sem：常用于进程间同步，初值设为0或n，一个proc中只有P或V操作，剩下的P或V操作在另一个proc完成

经典同步互斥模型：设进程p1, p2, p3。缓冲区b1, b2，容量都为1，即只能存一份数据。p2需要等待p1将结果写入b1，p3需要等待p2将结果写入b2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
信号量S1, S2表示缓冲区的读。Sb1, Sb2表示缓冲区的写。Sm1，Sm2表示锁
初值：S1=S2=0, Sb1=Sb2=1, Sm1=Sm2=1

p1          p2          p3
------------ loop -------------
P(Sb1)      P(S1)       P(S2)
P(Sm1)      P(Sm1)      P(Sm2)
写入b1      读b1        读b2
V(Sm1)      V(Sm1)      V(Sm2)
V(S1)       V(Sb1)      V(Sb2)
            P(Sb2)
            P(Sm2)
            写b2
            V(Sm2)
------------ loop -------------
           
p2要等于p1处理的结果，因此p1没处理完时p2申请读缓冲区P(S1)将会进入等待队列
待p1发出可读V(S1)后p2才会执行
p3同理

当p1执行完一个循环，想要执行下一个循环时，如果发现p2还没读取缓冲区数据，则P(Sb1)会让其进入等待队列

todo读写者问题

管程

为了让开发者在互斥逻辑的设计中解脱，引入管程。管程是一种编程语言构件，进入管程的互斥由 编译器 负责，用户无需关心如何实现互斥。

  • 缺点：
    • 只有几种编程语言支持，兼容性不好
    • 无法解决同步问题

进程间相互作用

进程通信

  • 按数据多少分
    • 低级通信，只传状态或整型数值，信息量少
    • 高级通信，能传大批量数据
  • 按通信方式分
    • 直接通信，信息直接给发送方
    • 间接通信，通过接收双方之外的共享结构传递

共享内存

在内存中指定一块区域用来共享存储，各进程可以申请一个存储段，并申请时提交 关键字 。系统根据关键字返回，查找/分配，然后将该存储区映射到进程的逻辑空间，此后进程可以直接访问共享内存。

使用共享内存时需要注意同步互斥的问题

消息传递

通过系统的发送(Send)原语和接收(Receive)原语，实现进程间通信。发送原语将消息挂到接收进程的消息队列末尾。接收进程用接收原语从消息队列头取走消息。

信箱

信箱是用来对一定数量的消息进程缓存，每个信箱用标识符区分。一个信箱可以被多个进程共享，实现消息的广播发送。

管道pipe

管道是一种共享文件 模式，基于文件系统，以 先进先出 的方式实现消息单向 传递。

UNIX系统管道的创建通过pipe()函数实现。该函数返回分别用于读、写操作的 文件描述符 fd[0], fd[1]。读管道时，利用fd[0]文件描述符从管道读取字节，写管道时，利用fd[1]向管道写。

1
2
3
4
5
6
+----------------------------------+
read(fd[0])    <--      write(fd[1])
+----------------------------------+

读写读写
0是读，1是写
  • 如果要双向通信需要定义两个管道
  • 只适用于父子进程间通信

观察下面一段程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int main(){
    char father[] = {"message from father"};
    char child[] = {"message from child"};
    char buff[50];
    int chan1[2], chan2[2];
    int pid;

    pipe(chan1);
    pipe(chan2);
    while((pid=fork())==-1);   // 如果fork返回-1，一直尝试创建，直达创建子进程成功

    if(pid){  // pid>0表示是父进程执行，pid=子进程pid
        close(chan1[0]);
        close(chan2[1]);
        write(chan1[1], father, strlen(father));
        close(chan1[1]);
        read(chan2[0], buff, 50);
        printf("father process: %s\n", buff);
    }else{   // 否则子进程执行
        close(chan1[1]);
        close(chan2[0]);
        read(chan1[0], buff, 50);
        printf("child process: %s\n", buff);
        write(chan2[1], child, strlen(child));
        close(chan2[1]);
    }
}

上述程序中，涉及的知识点：

  • fork()
    • 返回值大于0，表示父进程在执行，返回值为子进程pid
    • 返回值等于0，表示子进程在执行
    • 返回值小于0，表示出错
    • 在fork时子进程会拷贝父进程，拷贝父进程的资源、PCB、状态等
    • 之后再申请资源，都是在各自进程PCB上相互独立的操作
  • 父子进程中的close()只是关闭了 当前进程对资源的使用状态，而不是关闭共享的管道
    • 一旦子进程创建，它就与父进程独立开来了，可以认为状态独立，但是资源 指向 的都是同一个，所以是同一个管道，可以用共享资源通信
  • 父子进程同步
    • 可以使用wait()和waitfor()函数，会等待某个子进程终止，然后返回子进程pid

线程

如果以进程作为调度的基本单位，则进程间调度的工作量将会很大(如很多资源来回切换)，开销较大。

因此以 线程 作为调度的基本单位，调度不再是进程间调度，而是进程内的 线程间的调度 。

一个进程内部可以有多个线程，在多线程环境下一个进程打开的资源在 线程间共享，使得线程间调度不再不用资源来回切换，只需要记录线程的上下文，大大降低了开销。

不同于进程间的共享，进程间共享是生成子进程前的资源共享，生成子进程后各自申请的自己将相互独立。而线程将的资源随时都是共享的。

多线程模型可以看成这么一个结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 多线程模型：一个进程中的内容
|-----|
| PCB |
|-----|
同一份资源、状态

|--------------|
| 用户地址空间 |
|--------------|

多个共享
|------------|  |------------|  |------------|
| 线程控制块 |  | 线程控制块 |  | 线程控制块 |
|------------|  |------------|  |------------|
| 用户栈     |  | 用户栈     |  | 用户栈     |
| 核心栈     |  | 核心栈     |  | 核心栈     |
|------------|  |------------|  |------------|

线程的实现机制

线程的实现有用户级线程(ULT)和内核级线程(KLT)

用户级线程

  • 应用程序完成所有线程的管理，只需提供线程库即可在任意系统执行
  • 内核感知不到ULT的存在
  • 线程切换不需要内核态
  • 调度是由程序定
  • 优点
    • 应用程序完成所有线程的管理，只需提供线程库即可在任意系统执行
    • 开销较KLT小
  • 缺点
    • 由于内核感知不到ULT，所以当一个ULT阻塞时会将进程阻塞，从而进程的所有线程阻塞
      • 因为处理器是分配给进程的

ULT

内核级线程

  • 所有线程有内核管理
  • 没有线程库，有内核提供API
  • 内核维护进程和线程的上下文，线程间切换需要内核支持
  • 优点
    • 多处理器下内核可以同时调度一个进程中的多个线程(可感知的)
    • 阻塞是在线程的阻塞
  • 缺点
    • 线程切换需要内核支持，开销较大

KLT

ULT和KLT结合

同时使用ULT和KLT，CPU先分配给内核线程，再由内核线程分配给用户级线程。一个进程可以分配多个KLT。因此实现一个线程阻塞时同一个进程的其他线程还可进行

UNIX进程模型

UNIX进程由三部分组成：proc结构(常驻内存的PCB)，数据段(执行时用到的数据)，正文段(程序代码)。进程加载时系统创建相应的数据和堆栈段，并加入一些进程控制信息。

其中proc表和text表是常驻内存的。

  • 每个进程对应proc表中的一个表项
  • text表存放共享正文段的起始块号 ，可以让若干进程共享
  • 数据段由进程系统数据区、数据栈和用户堆栈组成
    • 进程系统数据区属于内核态，由user和核心栈组成
      • user是进程扩充控制块，是对proc内容的补充，需要时才调入内存
      • 核心栈是进程进入核心态时，系统使用的栈

进程调度

UNIX采用动态优先数调度算法，优先数计算规则如为：进程优先级为0~127之间的整数， 优先数越大，优先级越低 ，计算公式为：

1
p_pri = p_cpu/2 + PUSER + p_nice + NZERO
  • PUSER和NZERO是系统设置
  • p_cpu表示该进程最近一次cpu连续使用的时间，使用时间p_cpu增加，优先级降低
  • p_nice可以由用户设置

死锁

死锁就像两个过独木桥的人，同时站在桥中央，两个人都等待对方让路

死锁产生与系统资源数，资源分配策略，进程申请资源的时机等多个因素有关，解决死锁问题需要全方位考虑

产生死锁的4的必要条件

  • 资源独占，互斥使用
  • 非剥夺式，资源不可抢占
    • 即使进程处于阻塞态，它所占有的资源也不能被其他进程使用，其他进程需要等它释放
  • 零散请求
    • 申请资源不是集中性的一次申请所有资源， 进程在已经占用资源的情况下，又申请资源得不到满足时，并不会释放已占用的资源
  • 循环等待，等待资源的进程形成了一个封闭的环路

由于是产生死锁的必要条件，因此打破之一就能防止死锁

产生死锁的实例

P,V操作不当

设两资源S1，S2，初值都是0

1
2
3
T1          T2
P(S2)       P(S1)
V(S1)       V(S2)

资源申请顺序不当

同样两资源S1，S2，初值是1

1
2
3
4
5
6
7
T1                  T2
P(S1)               P(S2)
申请扫描仪器        申请打印机
P(S2)               P(S1)
申请打印机          申请扫描仪
V(S1)               V(S2)
V(S2)               V(S1)

环路死锁

1
2
3
4
5
6
     S2
T1   ->   T2
 ^        |  S1
 |S1      v
T1   <-   T1
     S2

若T1P(S1)成功后调度到T2，且T2成功P(S2)，这种情况将会发生死锁。而若执行顺序改变，将可能避免死锁

  • 零散请求

资源分配不当因此死锁

设系统有9个资源，4个进程。每个进程需要4个资源才能完成执行。现若每个进程分配2个资源，系统还剩1个资源，谁都无法完成执行，导致死锁。

显然，如果顺序适当是可以避免死锁的

临时资源的死锁

解决死锁的方案

  • 鸵鸟策略
    • 不加理会，认为处理死锁的代价是比死锁产生的代价高
  • 不让死锁发生
    • 静态策略：进程创建时为其分配所有资源
      • 有效，易于实现。但资源浪费，所有进程都满足最大资源数时才能执行
    • 动态策略：进程执行时改变资源的分配情况
      • 资源利用率高，但实现复杂
  • 让死锁发生
    • 死锁发生后事后补救

死锁的预防

死锁的预防策略是以破坏死锁产生的必要条件为目的的，对资源的申请加以限制。

  • 破坏”互斥”条件
    • todo 对所有资源进行spooling操作
    • 分析：
  • 破坏”不可剥夺”条件
    • 进程申请的资源得不到满足时，进程可以回收请求，转去做其他工作
      • 法1：申请资源得不到满足时，释放已经占用的资源。如还没用完，则以后申请
      • 法2：优先级高的进程可以强迫优先级低的进程释放资源
    • 分析：
      • 需要保存”资源使用”的现场，以便以后申请恢复。需要更多的时间空间
      • 只适用于处理机和储存器资源
  • 破坏”零散请求”条件
    • 静态分配策略，一个进程所需的所有资源都得到满足才能执行
    • 分析：
      • 资源利用率低，如只在开始用以下也要等到进程结束才释放
  • 破坏”循环等待”条件
    • 系统根据一定的策略给资源编号，进程必须从小到大的顺序申请资源，并进程占有的资源号小于申请的资源号才能申请
    • 分析：
      • 按照资源编号的顺序使用资源可能与实际资源的使用顺序不同，使得先申请的资源因暂时不用而闲置很久

死锁的避免

死锁的避免策略是用 动态的办法判断 资源和系统的使用情况，在分配之前判断是否会发生死锁，如果会发生死锁则不予分配资源。

  • 安全状态：多个进程动态申请资源时，系统按某种顺序分配资源，最终可以顺利完成
    • 安全状态一定不会发生死锁
  • 不安全状态：不存在一种分配顺序使得每个进程都能顺利完成
    • 不安全状态不一定会死锁，但死锁一定处于不安全状态

单项资源的银行家算法

银行家算法是一种 资源分配时 避免死锁的方法。

假设资源数(银行家的资金)为10，现有4个进程(客户)a、b、c、d分别需要资源数4、5、6、7。假设他们处于如下状态：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<用户名> <已用资金> <最大资金> <仍需资金>

剩余资金：4
|---|---|---|---|
| a | 1 | 4 | 3 |
| b | 2 | 5 | 3 |
| c | 1 | 6 | 5 |
| d | 2 | 7 | 5 |
|---|---|---|---|

如果先分配给a，a可以顺利执行，a释放资源

剩余资金：5
|---|---|---|---|
| a | - | - | - |
| b | 2 | 5 | 3 |
| c | 1 | 6 | 5 |
| d | 2 | 7 | 5 |
|---|---|---|---|

接下来先分配给谁都能够顺利执行

但是如果先分配给c，c不但不能顺利执行，剩余资源也用完了，导致处于不安全状态。其他顺同理。

多项资源的银行家算法

类似单项资源的情况，把一个进程所需的所有类型的资源的数量以向量的形式组织，每个向量视作份需求，则有退化成但资源模式。

如：资源R1、R2、R3、R4分别表示5台打印机、7个手写板、8台扫描仪、9个读卡器。5个进程T1、T2、T3、T4、T5。设某时刻剩余资源和设备所需处于如下状态:

1
2
3
4
5
6
7
8
9
10
11
12
13
avaliable = (2, 2, 1, 2)  // 因为可能别的子系统还在用，把整个满足的部分给出去了，剩下这点

<进程，所需>
|------|----|----|----|----|
| Proc | R1 | R2 | R3 | R4 |
| T1   | 2  | 3  | 1  | 0  |
| T2   | 1  | 1  | 0  | 3  |
| T3   | 1  | 2  | 1  | 0  |
| T4   | 0  | 3  | 2  | 0  |
| T5   | 0  | 3  | 2  | 0  |
|------|----|----|----|----|

显然安全的顺序可以是：T3->...->...

死锁的检测和解除

资源分配图
  • 规定
    • 方框表示资源R
      • $W_j$表示资源j总数
    • 圆圈表示进程P
    • 方框指向圆圈表示分配给进程资源
    • 圆圈指向方框表示进程申请资源
  1. 分配的资源数不应大于资源总数

$$\sum_j (R_i, P_j) \le W_j$$

  1. 任意进程对资源是申请和以分配的和不应大于W

$$(R_i, P_j) + (R_j, P_i) \le W_j$$

死锁检测与化简

todo

    1. 无环路则没死锁，有则下一步
    1. 环路中涉及的R只有一个资源则死锁。否则下一步
    1. 化简资源分配图
      • 找到未死锁的进程，释放其资源，去掉其所有有向边，如此反复直至无法再化简
      • 若化简后都成孤立节点：可完全化简
        • 不可完全化简则死锁
临时资源的死锁检查

对于临时资源，进程不必释放它，如管道中的消息。

  • 规定
    • 圆圈表示进程P
    • 方框表示资源R，一个原点表示该资源的单个资源
    • 方框指向圆圈表示进程产生资源(“资源向进程申请”)
    • 圆圈指向方框表示进程申请资源

todo

死锁解除
  • 重启
  • 撤销(kill)进程
  • 剥夺资源
  • 进程回退

存储管理

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://github.com/66ring/2000/01/01/Major/OS/OS_course/

os

评论