定义

  • PCB(系统分配用来描述进程信息)：PID(唯一标识)、UID(用户)、状态、优先级、资源分配清单(程序(数据)段指针、键盘、鼠标)、处理机相关信息(各种寄存器值。进程切换时记录运行情况。如程序计数器值等)

  • 程序段、数据段

  • 多个进程组织方式：链表、数组

状态

  • 创建 -> 就绪(处理机×其他√) <-> 运行((处理机√其他√)) -> 终止
  • 运行 ->(主动) 阻塞(处理机×其他×) ->(被动) 就绪

进程控制

用原语实现进程状态转换

  1. 更新PCB信息(修改进程状态标志、运行环境保存到PCB、从PCB恢复)
  2. 将PCB插入合适队列
  3. 分配/回收资源

进程通信

  • 共享存储：设置一个共享空间，互斥访问
  • 管道通信：设置一个特殊的共享文件(管道)，其实就是一个缓冲区。半双工、互斥、没写满不能读，没读空不能写
  • 消息传递：传递结构化消息(消息头/消息体)，系统提供"发送/接受原语"

线程

CPU执行单元，调度的基本单位，进程作为除CPU外的资源分配基本单位

  • 同进程线程切换，不需要切换进程环境
  • 多线程模型：用户级线程-内核级线程(处理机分配单位) 多(开销小)对多(并发高)

处理机调度

  • 高级(作业)调度：后备队列(外存)->内存，发生频率最低，无->创建态->就绪态
  • 中级(内存)调度：挂起队列(外存)->内存，发生频率中等，挂起态->就绪态 (阻塞挂起->阻塞态)
  • 低级(进程)调度：就绪队列(内存)->CPU，发生频率最高，就绪态->运行态

调度时机

  • 主动(非抢占式)：进程正常终止、异常终止、阻塞（I/O）
  • 被动(抢占式)：时间片用完、更紧急(I/O中断)、更高优先级进程进入就绪队列
  • 不能调度：中断、进程在系统内核临界区(锁住的内核数据结构需要尽快操作完释放)、原语

调度算法

  • 先来先服务(FCFS) + 短作业优先(SJF) = 高响应比优先(HRRN)
  • 时间片轮转(RR) + 优先级调度 = 多级反馈队列

进程同步(先后)、互斥(临界资源)

  • 进程互斥四部分：进入区(检查是否可进入和上锁) -> 临界区(访问临界资源) -> 退出区(解锁) -> 剩余区(其余代码)
  • 原则：空闲让进、忙则(有限(饥饿)、让权(CPU))等待

互斥软件实现方法

  • 单标志法：进入区只检查，不上锁，退出区转交。不遵循空闲让进原则
  • 双标志先检查法：进入区先检查后上锁，退出区解锁。不遵循忙则等待原则
  • 双标志后检查法：进入区先上锁后检查，退出区解锁。不遵循空闲让进、有限等待原则
  • peterson算法：进入区主动争取-主动谦让-检查对方是否想进、己方是否谦让。不遵循让权等待原则

互斥硬件实现方法

  • 中断屏蔽方法：使用“开/关中断”指令实现。只适用于单处理机、操作系统内核进程
  • TestAndSet(TS指令/TSL指令)、Swap指令(XCHG指令)：old记录是否已被上锁，再将lock设为true，检查临界区是否已被上锁，若已上锁循环重复前几步

信号量机制

  • 整型信号量：用数值表示资源数(S)。
    • P：while(S<=0); S=S-1;
    • V：S=S+1;
    • 不满足让权等待
  • 记录型信号量(semaphore)S：剩余资源数(value) + 等待队列(L)
    • P(S)：S.value–; if(S.value<0) block(S.L);
    • V(S)：S.value++; if(S.value<=0) wakeup(S.L);
    • 进程互斥：信号量初值为1，P->临界区->V
    • 进程同步(保证一前一后)、前驱关系：信号量初值为0，在每个前操作之后执行V，在每个后操作之前执行P。从前后事件角度考虑

互斥同步问题

生产者-消费者问题

 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

semaphore mutex=1;//缓冲区互斥
semaphore empty=n;//空闲缓冲区同步，等生产者放
semaphore full=0;//非空缓冲区同步，等消费者取

producer(){
    while(1){
        生产一个产品;
        P(empty);//消耗一个空闲缓冲区
        P(mutex);
        把产品放入缓冲区;
        V(mutex);
        V(full);//增加一个非空缓冲区
    }
}

consumer(){
    while(1){
        P(full);//消耗一个非空缓冲区
        P(mutex);
        从缓冲区取出一个产品;
        V(mutex);
        V(empty);//增加一个空闲缓冲区
        使用产品;
    }
}

读者-写者问题

允许读-读

 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
28
29
30
31
32
33
34

semaphore rw=1;//文件互斥访问
int count=0;//记录几个读进程在访问文件
semaphore mutex=1;//对count互斥
semaphore w=1;//实现写优先

writer(){
    while(1){
        P(w);
        P(rw);
        写;
        V(rw);
        V(w);
    }
}

reader(){
    while(1){
        P(w);

        P(mutex);
        if(count==0) P(rw);
        count++;
        V(mutex);

        V(w);

        读;

        P(mutex);
        count--;
        if(count==0)V(rw);
        V(mutex);
    }
}

哲学家进餐问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex=1;//互斥取筷子
Pi(){//i号哲学家进程
    while(1){
        P(mutex);
        P(chopstick[i]);//拿左
        P(chopstick[(i+1)%5]);//拿右
        V(mutex);
        吃;
        V(chopstick[i]);//放左
        V(chopstick[(i+1)%5]);//放右
        思考;
    }
}

管程

synchronized

死锁

  • 预防死锁(破坏四个条件)：互斥、不剥夺、请求和保持、循环等待
  • 避免死锁(银行家算法)：检查需求，试探分配，检查安全序列(剩余资源能满足某个进程需求)
  • 检测和解除：用资源分配图(进程/资源节点)检测。解除：资源剥夺、终止进程、进程回退