操作系统

2025-01-12  本文已影响0人  张_何

kernel - 操作系统内部组件包括:

越靠近CPU访问速度越快
CPU ---> 寄存器 ---> 缓存1 ---> 缓存2 ---> 主存 ---> 硬盘

内存分配

连续内存分配
内存碎片问题
分区的动态分配策略
压缩式碎片整理
交换式碎片整理

非连续内存分配

硬件解决方案

进程

  1. 程序的代码
    2.程序处理的数据
    3.程序计数器中的值,指示下一条将运行的指令
    4.一组通用的寄存器的当前值, 堆,栈
  2. 一组系统资源(如打开的文件, 网络资源)
    总之,进程包含了正在运行的一个程序的所有状态信息
进程与程序的联系
  1. 程序是产生进程的基础
  2. 程序的每次运行构成不同的进程
    3.进程是程序功能的体现
  3. 通过多次执行,一个程序可对应多个进程; 通过调用关系,一个进程可以包括多个程序
进程与程序的区别
  1. 进程是动态的,程序是静态的: 程序是有序代码的集合; 进程是程序的执行,进程有核心态/用户态
  2. 进程是暂时的,程序是永久的: 进程是一个状态变化的过程,程序可以长久保存
  3. 进程与程序的组成不同: 进程的组成包括程、数据和进程控制块(即进程状态信息)
进程的特点:
  1. 动态性: 可动态地创建,结束进程
  2. 并发性: 进程可以被独立调度并占用处理机运行
  3. 独立性: 不同进程的工作不相互影响
  4. 制约性: 因访问共享数据/资源或进程间同步而产生制约

并发: 指的是一段时间内有多个程序在执行
并行: 指的是在某一时刻有多个程序在执行(需要有多个 CPU)

进程控制结构
PCB 含有以下三大类信息:
  1. 用户可见寄存器, 用户程序可以使用的数据,地址等寄存器.
  2. 控制和状态寄存器, 如程序计数器(PC), 程序状态字(PSW)
  3. 栈指针, 过程调用/系统调用/中断处理和返回时需要用到它
  1. 调度和状态信息,用于操作系统调度进程并占用处理机使用.
  2. 进程间通信信息, 为支持进程间的与通信相关的各种标识,信号,信件等,这些信息存放在接收方的进程控制块中
  3. 存储管理信息,包含有指向本进程映像存储空间的数据结构
  4. 进程所用资源,说明右进程打开,使用的系统资源,如打开的文件等
  5. 有关数据结构连接信息, 进程可以连接到一个进程队列中,或连接到相关的其他进程的 PCB
PCB 的组织方式
进程管理
进程状态

  1. 进程创建: 引起进程创建的 3 个主要事件:

  2. 系统初始化时:

  3. 用户请求创建一个新进程

  4. 正在运行的进程执行了创建进程的系统调用

  5. 进程运行: 内核选择一个就绪的进程,让它占处理机并执行

  6. 进程等待:
    在以下情况,进程等待(阻塞)

  7. 请求并等待系统服务,无法马上完成

  8. 启动某种操作,无法马上完成

  9. 需要的数据没有到达
    进程只能自己阻塞自己,因为只有进程自身才能知道何时需要等待某种事件的发生

  10. 进程唤醒:
    唤醒进程的原因

  11. 被阻塞进程需要的资源可被满足

  12. 被阻塞进程等待的事件到达

  13. 将该进程的 PCB 插入到就绪队列
    进程只能被别的进程或操作系统唤醒

  14. 进程结束
    以下四种情况下,进程结束

  15. 正常退出(自愿的)

  16. 错误退出(自愿的)

  17. 致命错误(强制性的)

  18. 被其他进程所杀(强制性的)

线程管理

上下文切换


调度

同步

硬件解决办法

软件解决办法

  1. 复杂, 需要两个进程间的共享数据项
  2. 需要忙等,浪费 CPU 时间
  3. 没有硬件保证的情况下无真正的软件解决方案
基于硬件原子操作指令的软件解决方案
  1. Test-and-Set: 首先从内存中读取值, 然后测试该值是否为 1(返回真或假),然后将内存值设置为 1
boolean TestAndSet(boolean *target) {
  boolean rv = *target;
  *target = TRUE;
  return rv;
}
  1. Exchange: 交换内存中的两个值
void Exchange(boolean *a, boolean *b) {
  boolean temp = *a;
  *a = *b;
  *b = temp;
}
  1. 适用于单处理器或者共享主存的多处理器中任意数量的进程
  2. 简单并且容易证明
    3.可以用于支持多临界区
  1. 忙等消耗处理器时间
  2. 当进程离开临界区并且多个进程在等待的时候可能导致饥饿
  3. 死锁: 如果一个底优先级的进程拥有临界区并且一个高优先级进程也需求,那么高优先级进程会获得处理器并等待临界区, 导致低优先级的线程得不到资源去释放锁

信号量

信号量解决的问题:
PV 操作
信号量
信号量使用
Class BoundedBuffer {
  mutex = new Semaphore(1); // 设置一个队 buffer 操作的信号
  fullBuffers = new Semaphore(0); // 向 buffer 中添加元素的信号, 假定 buffer 中是满的
  emptyBuffers = new Semaphore(n); // 从 buffer 中取出元素的信号, 假定 buffer 中可以存 n 个元素
}

BoundedBuffer:: Deposit(c) { // 对 buffer 进行存的操作, 相当于生产者
  emptyBuffers -> P(); // 首先判断对 emptyBuffers 进行P 操作,如果 n > 1 ,那么 n - 1 ,继续向下执行, 如果不考虑移除,理论上要执行第 n  次 P 操作 buffer 中元素才被添加满, 在执行第 n+1次P 操作的时候会睡眠
  mutex -> P(); // 向 buffer 中添加元素, 要先对 mutex 做 P操作,判断是否可以对 buffer 进行操作,如果 mutex 值为 1,说明没有其他线程在访问 buffer, 此时可以对 buffer 进行操作, 如果 mutex 为 0 ,说明别的线程在访问 buffer, 那么此时不能对 buffer 进行操作,需要等别的线程将 mutex 置为 1 的时候才可以访问
  Add c to the buffer; // 向 buffer 中添加一个元素
  mutex -> V(); // 添加完元素, 将 mutex 置为 1, 此时别的线程可以访问 buffer 了
  fullBuffers -> V(); // 向 buffer 中添加完元素后,需要将 fullBuffers 值加 1, 这样才能保证别的线程可以从 buffer 中取到元素,
}

BoundedBuffer:: Remove(c) { // 从 buffer 中取元素的操作, 相当于消费者
  fullBuffers -> P(); // 首先判断 buffer 中是否还有元素
  mutex -> P(); // 判断是否可以操作 buffer 
  Remove c from buffer; // 从 buffer 中移除一个元素
  mutex -> V(); // 操作完 buffer ,释放 buffer
  emptyBuffers -> V(); // 取出一个元素后, 对 buffer 中还可存放元素的数量+1
}
信号量的实现
class Semaphore {
  int sem;
  WaitQueue q;
}

Semaphore:: P() {
  sem--; // 首先信号量减一
  if (sem < 0) { // 如果信号量 小于 0
    Add this thread t to q; // 把当前的线程放到等待队列中去,
    block(t); // 同时线程自身睡眠
  }
}

Semaphore:: V() {
  sem++; // 首先信号量加一
  if (sem<= 0) { // 因为先 sem++了,所有当 sem = 0 的时候说明之前已经是-1了,所以如果信号量小于等于 0 说明之前已经有线程在等待了
    Remove a thread t form q; // 从等待队列中取出一个线程, 一般是 FIFO 的规则
    wakeup(t); // 唤醒该线程
  }
}

管程(Monitor)

管程实现
class Condition {
  int numWaiting = 0;
  WaitQueue q;
}

Condition:: Wait(lock) {
  numWaiting++;
  Add this thread t to q;
  release(lock); // 睡眠之前先把锁释放掉,要不然别的线程一直得不到锁
  schedule(); // need mutex
  require(lock); // 被唤醒之后需要再将获得锁
}

Condition:: Signal() {
  if(numWating > 0) {
    Remove a thread t from q;
    wakeup(t); // need mutex
    numWating--;
  }
}

class BoundedBuffer {
  Lock lock;
  int count = 0 ;
  Condition notFull, notEmpty;
}
BoundedBuffer:: Deposit(c){
  lock->Acquire(); // 进来先加锁,保证只有一个线程在操作管程
  while(count == n) notFull.Wait(&lock); // 当 buffer 中满了的时候,需要进入睡眠等待 notFull signal 唤醒
  Add c to the buffer; 
  count++;
  notEmpty.Signal(); // buffet 中添加元素成功, 唤醒等待remove 的线程
  lock->Release(); // 释放锁资源
}
BoundedBuffer:: Remove(c){
  lock->Acquire(); // 保证只有一个线程操作管程
  while(count == 0) notEmpty.Wait(&lock); // 当 buffer 中没有元素时, notEmpty 进入休眠,等待 notEmpty Signal 的唤醒
  Remove c from buffer;
  coount--;
  notFull.Signal(); // buffer 中移除元素成功,唤醒等待 deposit 的线程
  lock->Release(); // 释放锁资源
}
经典同步问题
生产消费者问题
读者写者问题

使用信号量实现多读单写

sem_wait(WriteMutex); // 相当于 P 操作
write;
sem_post(WriteMutex); // 相当与 V 操作

sem_wait(CountMutex); // 对 Rcount 的操作用互斥包起来做保护
if(Rcount == 0) 
  sem_wait(WriteMutex); // Rcount = 0 说明当前没有读者, 此时对 WriteMutex做一个 P 操作; 如果 Rcount != 0,说明当前已经有线程在执行 Reader 操作,当在执行 Reader 操作的时候,Writer 一定是进不来的,
++Rcount;  // 对 Rcount +1
sem_post(CountMutex);
read;
sem_wait(CountMutex); // 对 Rcount 的操作用互斥包起来做保护
--Rcount; // 执行完read 将Rcount -1
if(Rcount == 0) 
  sem_post(WriteMutex); // 当 Rcount = 0 时,说明所有的 read 都已经结束了,那么做一个 V 操作,使有可能等待 Write 的线程被唤醒
sem_post(CountMutex);

使用管程实现多读单写


死锁

死锁特征
  1. 互斥: 在一个时间只能有一个进程使用资源
  2. 持有并等待: 进程保持至少一个资源在等待获取其他进程持有的额外资源
  3. 无抢占: 一个资源只能被进程自愿释放,进程已经完成了它的任务之后
  4. 循环等待: 存在等待进程集合{P0,P1...,PN}, P0 正在等待 P1 所占用的资源,P1 正在等待 P2 所占用的资源,..., PN-1 在等待 PN 所占用资源,PN 正在等待 P0 所占用的资源

IPC - 进程间通信

文件系统

上一篇 下一篇

猜你喜欢

热点阅读