操作系统

发表于 更新于 分类于 阅读次数： Disqus： 本文字数： 4.2k 阅读时长 ≈ 4 分钟

操作系统

  • 什么是操作系统?

  • OS 大致是管理控制整个计算机系统软硬件资源,进行组织调度,为用户和其他软件提供接口的程序集和.

  • 操作系统的四大特征

    • 并发,微观串行宏观并发.分时.
    • 共享,允许同一设备多个进程使用,互斥共享,同时访问.
    • 虚拟,OS的设备可能并不存在实体,仅为虚拟化而来.虚拟化cpu 虚拟内存等
    • 异步,多个进程并发执行,其执行的过程是用户不可控的.

  • 操作系统的发展历史

    • 单道批处理系统,自动性,自动装载作业.顺序性,作业写入内存的顺序来自于在磁带(存储)的顺序.单道性,一次内存仅存在一个作业.缺点是 较快的 cpu 可能等待低速的 io .
    • 多道批处理系统,多道,允许内存装载多个作业.宏观上并行,微观上串行.用户不能控制计算机.
    • 分时操作系统,cpu时间分片,分配给各个作业,造成宏观上作业独享cpu的假象.用户交互较好,但是一些场合并不适用.
    • 实时操作系统,硬实时,某个动作必须限时完成.软实时,非强制性完成.
    • 网络和分布式操作系统,各个资源共享,多个计算机的协同.

  • 大内核与微内核区别

    • 将各种模块全部集中在一块的内核,相对较复杂,模块间通信迅速.
    • 微内核将各个模块拆分,仅有一个模块运行在内核态,复杂性低,但内核态用户态切换频繁,有性能损失.

进程

  • 进程线程概念和区别

    • 进程是资源分配的基本单位,PCB(Process Control Block)描述进程基本信息和运行状态,进程创建撤销都是对PCB操作
    • 线程是cpu调度的基本单位,一般一个进程至少有一个或多个线程,android中则对应主线程.
    • 区别:
      • 进程是资源分配的基本单位,线程不拥有资源,但线程可以访问进程的资源.
      • 线程的调度更轻量,同一进程下线程切换不会引起进程切换.
      • 线程可以读取同一进程的数据(需要信号量等同步),进程间通信一般需要ipc.

  • 进程的状态切换

    • 新建->就绪->运行->终止. 因为io等事件 运行->阻塞,事件结束后 阻塞->就绪.就绪和运行可以相互转换(更高优先级的调度等)

  • 进程调度的算法

    • 批处理系统
      • 先到先来,不利于短作业
      • 短作业优先,饿死长作业.
      • 最短剩余时间
    • 交互系统
      • 时间片轮转(先到先来),时间片过短开销到,时间片过长响应不及时.
      • 优先级调度,按照进程优先级调度,相对的等待时间越长优先级越高.
      • 多级反馈队列.
        • 多级就绪队列,第一个优先级最高,时间片最小,第二队列优先级齐次,时间片x2….
        • 新作业扔到第一队列,执行完就算,执行不完,扔到第二级..依次扔下去.
        • 只有上面一级的队列执行完毕才执行下一级队列.
        • 优点是:短作业相对优先,长作业不会一直得不到执行.

  • 进程同步

    • 临界区: 单一资源可以被多个进程共享,但单一资源只能一次被一个进程访问.->临界资源.访问临界资源的代码称为临界区.
    • 同步: 完成任务对进程执行顺序有要求.
    • 互斥: 对资源竞争关系,一次只能有一个进程访问资源.
    • 信号量: 整型变量,只能被 P操作 和 V 操作两个原语访问,可以用来解决互斥和同步问题.
      • 若信号量只能取 0 或 1 那么就称为互斥量.
    • 管程: 信号量代码很复杂,把这部分代码独立出来就是管程.

  • 经典同步问题

    • 生产者/消费者问题

      • 信号量,一个互斥量,加锁上锁,两个信号量指示缓存区剩余和已有数量.ps 上锁必须要在检查信号量之后,否则会形成死锁.

    • 哲学家进餐问题

      • 5个哲学家围绕一个圆桌,每两个哲学家中间有一个筷子,进餐需要用两根筷子,一次只能拿一根,如何避免哲学家饿死?
      • 解决1: 引入一个服务生,每次就餐向服务生申请筷子.服务生知道如何分配筷子.
      • Chandy/Misra解法: 不要服务生了,把筷子分配给相应的哲学家,先吃的人先吃,之后没资源的人只给一张餐券,拿着这张餐券先占用那支叉子

    • 读者写者问题: 允许多进程读数据,只允许一个写,且读写互斥.

      • 解决1: 一个整形信号量标识当前读进程数量,一个互斥量标明读/写互斥.写进程只能在没有读者时写.
      • 解决2: 解决1容易饿死写进程,再增加个信号量标明是否当前有写进程请求,有写请求,后续读进程等待,直到写进程写完为止.

  • 进程间通信

    • 管道: 一般特指无名管道,可以看成特殊的文件,在各种 shell 中常用.
    • 命名管道: FIFO 位置与路径相关,
    • 消息队列: 发消息,接收消息,带个id 没什么特别的.
    • 信号量/共享内存: 使用的好,效率最高.信号量是加锁解锁.
    • 套接字: 进程间通信,一般是不同机器之间,也能用在同一机器上.

  • 死锁的条件

    • 死锁大概是几个进程你等着我,我等着你,直到天荒地老.
    • 互斥条件,资源只能被一个进程访问.
    • 占用/等待,已经得到某个资源的进程还能申请新的资源.
    • 不可抢占,分配给进程的资源只能等待该进程释放.
    • 环路等待,两个或两个以上进程组成环路,互相等待资源.

  • 处理死锁

    • 鸵鸟策略,处理死锁的代价高昂,那我不处理了.仅仅忽略.
    • 死锁检测与恢复,试图检测死锁并恢复.
      • 针对单一资源检查资源分配图,深度优先遍历检测到环即为死锁.
      • 多资源..待补充
      • 死锁恢复,无非是1.抢占资源.2,回滚资源申请.3,干脆杀进程.
    • 从死锁的条件入手,避免死锁发生.
      • 互斥: 以打印机为例,虚拟个打印机,可以给多个进程同时访问,其实是写入了缓存区,真正访问打印机的只有打印机的守护进程.
      • 等待/占有: 进程启动前一次性申请全部资源,资源不到位,不启动.
      • 不可抢占: 换成能抢占.
      • 环路等待: 给系统资源编号,进程只能按照编号请求资源.这样限制了新设备的增加.
    • 从分配入手.如果现在系统剩余资源还是能够满足某个进程所可能需要的最大量,那称为安全状态,此时不会发生死锁.反之称为不安全状态,有可能发生死锁.
      • 银行家算法,把系统资源比作银行的资本,进程申请资源比作客户申请贷款.银行家(系统)要保证本金处于安全状态.
        • 单资源的银行家算法比较好理解.不再赘述.
        • 多资源的银行家算法
          • 引用一张github 的图 多个资源的银行家算法
          • 图中涉及到 5 个进程,4 个资源.E 总资源 P 已分配资源 A 可用资源.EPA 均为向量,对应4个资源的坐标轴.A = (1020) 表示4个资源分别还剩下 1/0/2/0.
          • 检查算法
            • 确保右边矩阵始终要存在一行小于等于 A ,没有则表明系统处于不安全状态,可能死锁.
            • 若找到这一行,将对应的进程模拟终止,将已分配的资源模拟回收.
            • 重复直到所有进程都可以被打上模拟终止的标签,说明此时处于安全状态.
          • 如果没有通过检查,则应该拒绝分配资源.

内存

  • 虚拟内存是什么?

    • 程序对内存的需求增长,总是比内存本身增长快得多.虚拟内存顾名思义,系统为了方便管理,将内存分成了很多大小一致的块(称为页),每一个页即可以映射到物理内存也可以不映射,这样假设原来物理内存只有 32K,那系统全部页的大小可以有 64K,多出来的部分就是虚拟内存.虚拟内存对应的页一般存放在磁盘中.
    • 当程序运行时,没有在实际内存的页会发生缺页中断,系统会通过页面置换算法,将一部分暂时用不到的内存,挪到磁盘,将程序运行对应的页从磁盘写入内存.

  • 分页分段的区别?

    • 分页是从系统角度,将内存分成固定大小的块(页),方便系统对内存的管理,减少内存碎片.
    • 分段是从程序角度,将整个程序不同的部分分到不同的地址空间,(高级语言这个过程由编译器完成),分段方便了程序的保护.
    • 分段的做法是把每个表分成段,一个段构成一个独立的地址空间.每个段的长度可以不同,并且可以动态增长.
    • 现在操作系统都是混合的段页式管理内存.

  • 分页地址映射是怎么实现的?

    • 分页系统地址映射
    • 页表(Page table)存储着页(程序地址空间)和页框(物理内存空间)的映射表.
    • 虚拟地址分为两个部分,第一个是存储的页面号,另一个是存储的偏移量.
    • 图中存放了 16 个页,需要 4bit 索引,虚拟地址 0010 000000000100,对应页表编号为 2-110 ,页表最后一位代表这一页是否在内存中,这里是 1 在内存中,所以最后得到的物理内存 110 000000000100.

  • 常见的页面置换算法?

    • 程序运行需要的页面不在内存时,会发生缺页中断,系统会将一部分不常访问的内存挪到磁盘,以腾出空间.页面置换算法就是决定要将那些页挪到磁盘.目标是缺页率最低.(缺页中断最少)
    • OPT: 一个理论上的算法,将最长时间不再访问的页面挪到磁盘…但是现在还无法预测那些页会长时间不再访问..因此只是理论…
    • LRU: 最近最久未使用.需要记录过去页的使用情况,一个实现是将页串成一个链表,最新访问的在前,这样每次回收都回收最末尾的页.但这样的代价很高.
    • NRU: 最近未使用,每个页有两个状态位,R M .页面访问 R = 1,页面修改 M = 1,R 会定时清零.这样就建立了一个优先级,优先回收 R=0 M=1 的页面.最后回收 R=1 M=0 的页面.还不够智能.
    • FIFO: 跟队列的 FIFO 一样,最先回收的是最先进入的页面…非常不适合的算法..
    • 第二次机会?,算是对 FIFO 的改进.增加一个标志位 R ,页面被访问或修改时 R=1.回收时,从链表最后开始 R=0 又老又不访问,回收.R=1 把页扔到链表头..再回来继续搜索.
    • 第二次访问还是有个问题,移动页的成本还是高..这跟单链表实现有关,,所以..换成循环链表就好了…把头指针指向后挪一位..

磁盘

  • 简单介绍一下磁盘结构?

    • 一个机械硬盘可能又几张碟.
    • 一张碟是一个盘面.
    • 一个完整环形是一个磁道.
    • 一个完成的扇形是几何扇区
    • 磁道上面的一段弧是一个磁道扇区,磁道扇区是磁盘最小的存储单位.现在一般是 4k.
    • 磁头是读数据,主轴带动磁盘旋转.

  • 磁盘的调度?

    • 影响磁盘读取的从机械角度看无非是3点.
      • 找到特定扇区,盘面的旋转时间.
      • 再找到特定的磁道,磁头移动的寻道时间.
      • 实际读取和传输数据的时间.
    • 实际上寻道时间最长,因此磁盘调度主要围绕寻道优化.
    • FCFS: 先到先来,非常简单..但是完全没有优化,平均寻道时间不算理想.
    • SSTF: 最短寻道时间,每次调度只取队列里面寻道最短的,这样平均寻道时间最短,但有可能存在饿死特定请求的情况.(类比进程调度的短作业优先)
    • SCAN: 电梯算法,跟电梯一样,一次从楼下到楼顶.再从楼顶到到楼底.一次只移动一个方向,直到这个方向没有其他请求为止.这样寻道时间肯定比 SSTF 长了但是没有饿死请求了.
    • C-SCAN: SCAN 有一个问题是有一个请求距离磁头比较远,而且方向还相反,这样就需要等待很久.C-SCAN 就一个方向,每次都只从起始端开始,就一个方向,转到直到这个方向上剩余磁道没有其他请求为止,再迅速返回起始端.这样算是对 SCAN 的一个改进.
相关文章