进程与线程

概念

进程
1. 由进程控制块PCB，程序段，数据段组成
2. 进程的五种状态及切换
3. 子进程被撤销时会把资源还给父进程，撤销父进程后所有的子进程也会被撤销
4. 创建新进程的操作
  1. 分配唯一的进程标识号与空白PCB
  2. 分配资源，若资源不足则处于就绪态
  3. 初始化PCB
  4. 插入就绪队列等待调度
5. 进程的高级通信 - 共享存储、消息传递、管道通信
线程
1. 基本的CPU单元、程序执行流的最小单位，是被系统独立调度和分配的基本单位
2. 线程的三种实现方式
  1. 用户级 - 特点是在用户态即可完成，但是进程中只有一个线程可被执行
  2. 核心级 - 内核能同时调度同一进程内多个线程，但是需要从用户态切换到内核态
  3. 组合方式 - 反正就是结合两点
CPU调度
1. 可以进行调度的事件
  1. 创建新进程
  2. 进程正常结束或异常终止
  3. 进程阻塞
  4. I/O设备完成后，原先等待I/O的进程由阻塞态变为就绪态
2. 不能进行调度的事件
  1. 处理中断
  2. 完全屏蔽中断的原子操作
3. 用户级线程切换在同一进程内进行,仅需少量的机器指令；内核级别的线程的线程切换需要完整上下文切换。修改内存映像，导致了若干数量级的延迟
4. 周转时间
  1. 周转时间 = 完成时间 - 到达时间
  2. 带权周转时间 = 周转时间 / 作业实际运行时间
5. 多级反馈队列调度算法
  1. 设置多个就绪队列并赋予不同的优先级
  2. 优先级越高的队列时间片越大
  3. 每个队列内都采用FCFS，进程在某个队列内时间片用完后，进入下一个队列末尾，直到最后一个队列运行时间片轮转算法
  4. 按队列优先级调度，只有上层队列为空时才调用下层队列的进程

同步与互斥

临界区的同步机制 - 空闲让进，忙则等待，有限等待，让权等待
互斥锁与信号量的概念
P操作表示申请一个资源、V操作表示释放一个资源

生产者消费者问题伪代码

semaphore mutex=1;//临界区互斥信号量
semaphore empty=n;//空闲缓冲区
semaphore full=0;//缓冲区初始为空

producer () {//生产者进程
   while (1) {
      produce an item in nextp;//生产数据
      P(empty);(要用什么，P一下）//获取空缓冲区单元
      P(mutex);(互斥夹紧）//进入临界区
      add nextp to buffer;(行为）//数据放入缓冲区
      V(mutex);(互斥夹紧）//离开临界区，释放互斥信号量
      V(full);(提供什么，v一下）//满缓冲区数加1
   }
}

consumer () {//消费者进程
   while (1) {
      P (full) ;//获取满缓冲区单元
      P (mutex) ;//进入临界区
      remove an item from buffer;//从缓冲区中取出数据
      V (mutex) ;//离开临界区，释放互斥信号量
      V (empty) ;//空缓冲区数加1
      consume the item;//消费数据
   }
}

注意进程中两个P操作的顺序不能反

读者写者问题伪代码

int count=0;
semaphore mutex=1;//保护更新count时候的互斥
semaphore rw=1;//保证读写者互斥访问
semaphore w=1;//实现写优先
writer () {
   while (1) {
      P (w) ;
      P (rw) ;
      writing;
      V (rw) ;
      V (w) ;
   }
}

reader () {
／／读者进程
   while (1) {
      P (w) ; 
      P (mutex) ;
      if (count==0)
         P (rw) ;
      count++;
      V (mutex) ;
      V (w) ;
      reading;
      P (mutex) ;
      count--;
      if (count==0)
         V (rw) ;
      V (mutex) ;
   }
}

死锁
1. 产生条件 - 互斥、不可剥夺、请求并保持、循环等待
2. 死锁的避免 - 银行家算法
  1. 检查申请值是否超过所需值
  2. 检查申请值是否超过可用值
  3. 尝试分配后检查是否处于安全状态，即剩下的满足某一个所全部需要的
3. 死锁的检测 - 资源分配图无法完全化简即为存在死锁
4. 死锁的解除 - 资源剥夺法、撤销进程法，进程回退法

混淆

进程和线程的区别
1. 调度 - 线程的上下文切换低于进程。同一进程内线程的切换不会切换进程，反之不成立
2. 并发性 - 引入线程后进程可以并发执行
3. 资源 - 线程不拥有系统资源
4. 独立性 - 进程有独立的资源空间，同一进程内线程共享资源和空间
5. 系统开销 - 进程创建系统开销更大
五种调度算法
1. 先来先服务 - FCFS
2. 短作业优先 - SJF
3. 高响应比优先调度算法 - 响应比 = （等待时间 + 要求服务时间） / 要求服务时间
4. 优先级调度算法 - 分为抢占式和非抢占式
5. 时间片轮转调度算法 - RR