画布 1
操作系统期末
  大题
    地址变换
      理论知识
        bit<Byte(字节）<KB<MB<GB
简写bit<B<K<M<G
1K=2^10B
1M=2^10K
....
1B=8bit
        十六进制,十进制,二进制互转
          十转二
            一直对商除2求余，最后的商为0时，把余数加在一起即可
          二转十
          十转十六
            同理，除16求余
          十六转十
            同理
      分段式内存管理
        分段式内存管理没有划分内存，而是划分了程序，把程序分成若干个段，塞入内存
        段表
          段表记录每个段在内存中的信息
            段号：第几段
            段基址：该段在物理内存中的起始地址
            段长：这个段的实际长度，段内偏移量应该小于这个值，否则越界
        虚拟地址=(段号,段内偏移量)
          虚拟地址=段号*段长+段内偏移量
        计算公式：物理地址=段内偏移量+段基址
          段内偏移量=虚拟地址-相邻的整数低地址
        例题
      分页式内存管理
        计算页号和页内偏移量
          例题
          分页式内存管理把内存划分成等大小的页面，通过页表将逻辑地址映射到物理地址。
每个页面都会给定一个页面大小
注，逻辑地址里的每一页有页号，对应的，物理地址里的每一页叫页框号
          页号用于标识是第几页，页内偏移量标识在这一页什么位置。因此只需要知道页号和页内偏移量，就可以知道逻辑地址对应的物理地址了
          公式：逻辑地址=页号*页面大小 + 页内偏移量
            页号P=逻辑地址A/页面大小L
            页内偏移量W=A%L
          二进制求法：若页面大小为2^4字节，二进制数往左移4位，剩余2位表示页号，4位表示页面偏移量
若页面大小为2^3字节，二进制数往左移3位，剩余3位表示页号，3位表示页面偏移量
        计算内存访问时间
          什么是TLB？
            访问数据时，会根据页表查询物理地址，才能拿到数据，这样速度很慢；因此引入了快表TLB，其记录常用数据，使得无需查询页表即可直接拿到数据
            原理
            TLB访问的各个情况
              TLB命中且无缺页错误
                即在内存中也在TLB中
              TLB未命中但无缺页错误
                意味着访问的页面在内存中，但是不在TLB中
              TLB未命中且有缺页错误
                意味着访问的页面既不在内存中也不在TLB中
如果题目说明要更新TLB，则需要花费20ms
              TLB命中但有缺页错误
                这种情况不可能存在，因为如果TLB命中，就说明内存中必然有对应的页面，这样TLB才能够形成
          例题
              因为访问页表和访问数据，都是一次内存访问，因此均耗时50ns
则第一题在无TLB下用时100ns
第二题50*75%+100*25%=62.5ns
              若TLB命中，则访问时间为1ns
              若TLB不命中但无缺页，则访问时间为2ns
              若TLB不命中且缺页，则访问时间为20002ns
20%*10%=2%,即有2%的可能发生缺页错误
且题目给出分页磁盘的平均访问和传输时间，若发生缺页，则需要从磁盘中将对应的页读入内存，这也是更新TLB所需要的时间
        单级页表
          如何计算需要多少页表项/页表条目？
            有多少页，就需要多少页表项/页表条目
            逻辑地址=页号+页面偏移量
这里的+号指的是二进制的位拼接
页面偏移量的最大值即为页面大小
          例题
              32位逻辑地址，共2^32字节
而页面大小4KB，共2^12字节
则一共需要2^20个页面，即2^20个页表条目
        多级页表
          程序每次创建时，都会创建它的页表，如果使用单级页表，那么即使一个程序并没有使用很多资源，但也要为它分配一张完整的页表，浪费空间
          多级页表真正解决的问题是：不使用连续的大块内存存储页表。即使程序只使用了几个页面，也不需要为它分配一张完整的页表，只需要动态分配它需要的内存就好了
      如何计算逻辑地址和物理地址需要多少位？
        如何求所需位数？
          如果N = 2^k，则需要k位
        逻辑地址=页号+页内偏移量
          于是逻辑地址所需的位号=页号需要多少位+页内偏移量需要多少位
        物理地址=物理帧号+页内偏移量
          于是物理地址所需的位号=帧号需要多少位+页内偏移量需要多少位
        例题
            逻辑地址共256=2^8页，于是页号需要8位
每页大小4KB=2^12B,则页内偏移量需要12位
一共20位
            物理地址共64=2^6个页框，也是页框需要6位
物理框大小=页大小=4KB=2^12 B，则页内偏移量需要12位，共18位
        如何根据位数求需要多少空间？
          如32位的虚拟地址，需要2^32字节，即4G
    页面置换求缺页次数
      为什么会发生缺页？
        因为程序的虚拟空间认为自己拥有很大的连续内存空间，但实际物理内存有限，不能同时容纳所有程序的所有页面。当物理内存中没有程序需要的页时，就发生了缺页
        如何解决
          把"不常用"的页面暂时放到磁盘上，只把"常用"的页面放在内存中
      什么是页面置换？
        把页面从内存中置换到磁盘上，把磁盘上的页面换到内存中
      三种置换算法
        先进先出FIFO
          最先进入内存的页面最先换出
        最近最少使用LRU
          最长时间没有被访问的页面最先被换出
              这样的列表
往左数，看页框中已有的数字谁距离我要填的数字最远，就替换谁
        最优置换Optimal
          将来最长时间不会被访问的页面最先被换出
              同样的列表
从要填的数字往右数，看页框中已有的数字，谁距离我要填的数字最远，就替换谁
      例题
            a.可以转为十进制计算，也可以用十六进制计算
原理仍然是页号P=逻辑地址A/页面大小L,
页内偏移量W=A%L
但由于页大小为4096=0x1000字节，比较特殊
（举例：0x20/0x10=0x2,0xE12C/0X1000=0XE)
则0xE12C的页号为0xE,页面偏移量为0x12C
物理地址=页号*页面大小+页面偏移量
            b.
    磁盘位示图
          (字号,位号)对应一个盘块号
假设从0开始编号，n为字长，(i,j)对应的盘块号为：字号*字长+位号
盘块号b=i*n + j，b对应的字号i=b/n,j=b%n
假设从l开始编号
则盘块号b=(i-l)*n,b对应的字号为
          若问位示图共需多少字
            字=磁盘块数/字长
=（磁盘容量/物理块大小）/字长
      例题
          盘块号=i*16+j
          (默认一个磁盘块=一个扇区）
每个柱面上的磁盘块数=每个柱面上的磁道数*每个磁道上的扇区数
柱面号 = 盘块号/每个柱面上的磁盘块数
磁头号 = (盘块号%每个柱面上的磁盘块数)/每个磁道上的扇区数
扇区号 = (盘块号%每个柱面上的磁盘块数)%每个磁道上的扇区数
            磁盘由n个盘片组成，盘片由n个磁道组成，扇区是磁道的一部分，柱面则是一个磁盘固定半径内的所有磁道，有多少磁道就有多少柱面
              每个盘片有两个盘面，每个盘面都有一个磁头
也就是说一个盘片有两个磁头，分别读取一个盘片的上下两面
              磁盘块就是扇区
              柱面的定义：所有磁片中半径相同的同心磁道构成"柱面"。柱面不是水平二维的，而是三维的
              所有磁头共用一个磁头臂
            盘块号/每个柱面上的磁盘块数，得到的是该盘块在第几个柱面上
盘块号%每个柱面上的磁盘块数，得到的是盘块是该柱面的第几个磁盘块
/每个磁道上的扇区数，得到该盘块在柱面的第几个磁头上
%每个磁道上的扇区数，得到该盘块在磁道的第几个扇区
          分配：由字号i和位号j求盘号b，设为1
回收：由盘号b求字号i和位号j，设为0
    磁盘移动臂调度算法
      用于计算磁头臂移动的总距离（柱面）
        FCFS先来先服务算法
          根据先后顺序访问对应的柱面
          虽然公平，但是柱面分布比较分散，效率就很低了
        SSTF最短寻找时间优先算法
          每次移动到离当前柱面最近的一个柱面
          性能较好，平均寻道时间短
但可能存在“饥饿”现象——若一直需要访问新柱面，那么距离较远的柱面可能访问不到
        SCAN算法（电梯调度算法）
          磁头从大到小，或者从小到大，到达最大值/最小值再回头一路走到对应的最小值/最大值
根据题目的要求，也可以是处理完该方向的最后请求再掉头
          性能好，不会有饥饿显现
但只在最边缘的柱面才会改变方向，且各个位置柱面的响应频率不平均
        C-SCAN算法
          类似于SCAN算法，但是到边缘时，返回到另一端的起点
          这样各柱面响应频率平均，但是会多增加一次磁头移动
    调度算法（计算周转时间）
      算法
        RR调度算法
          给定固定时间片(如1ms)，每个进程运行完1ms后跳转到下一进程，往复直到所有进程执行完毕
            RR调度算法及甘特图
        先来先服务算法FCFS
          谁先到执行谁
        短作业优先算法SJF
          谁先到执行谁，但优先执行服务时间短的
        高响应比优先算法HRRN
          谁先到执行谁，但优先执行响应比高的
          响应比=(上一进程的完成时间-此进程的到达时间+服务时间)/服务时间=(等待时间+服务时间)/服务时间
        最高优先级调度算法
          谁先到执行谁，但优先执行优先级高的
同优先级执行先到的
      概念和公式
        系统吞吐量
        周转时间=完成时间-到达时间
        带权周转时间=周转时间/服务时间
        什么是抢占式？
          例如抢占式的最高优先级调度算法
            若正在执行某进程时，进程队列里突然到达优先级最高的进场，则放弃正在执行的进程，转而执行队列中优先级最高的进程
      例题
    PV操作（程序设计题）
      信号量机制
        整型信号量
          S就是一个表示资源数目的整型信号量
        记录型信号量
          semaphore结构体是记录型信号量
            记录型信号量使用结构体，多存储了一个等待队列的指针，资源不足时就将进程挂起暂停其对CPU资源的占用，避免了忙等导致的浪费
      PV操作
        P操作是荷兰语proberen，指尝试
          测试信号量是否大于0，如果是则减1并继续，否则阻塞等待，因此函数名为wait。例如我要占用某资源，就得调用wait
        V操作是荷兰语verhogen，指增加
          将信号量加1，如果有等待的进程则唤醒一个，函数名为signal。当我释放资源后，就得调用signal
      概念
        进程调度的五种状态
          创建态：进程创建时，操作系统会进程分配资源，初始化PCB
          就绪态：创建完成后进入就绪态，虽然具备运行条件，但没有空闲的CPU，暂时不能运行
          运行态：CPU空闲时，操作系统选择就绪态的进程运行，进入运行态
          阻塞态：进程运行时在等待某个事件发生时，操作系统让其进入阻塞态暂停运行，选择另一个就绪态的进程运行，直到等待的事件发生再回归就绪态
          终止态：进程结束运行后，终止态销毁进程，回收其资源
        竞争状态
          多个进程同时访问一个共享资源，且没有同步机制进行协调，就会造成多个进程竞争一份资源的竞争状态，可能导致最终的输出错误
        临界区
          访问共享资源的代码片段，这些公共资源无法被多个线程同时访问
        互斥锁
          引入互斥锁是为了保证共享资源在同一时间只能被一个线程访问。可以解决竞争状态的问题
        进程同步
          协调多个进程间执行的工作次序，让多个进程之间按照一定的顺序或规则执行
            例如B在A后执行，D在B后执行，C在D后执行
      如何实现进程互斥？
        设置互斥信号量，初值为1
多个进程共享该信号量，每个进程执行时先调用wait，表示上锁，然后对临界资源操作；执行完后调用signal，表示释放
        加互斥锁实现，以信号量机制中的记录型信号量为例，可以这样改进
由于wait()和signal()都操作了S->value，因此存在竞争状态
      如何实现进程同步？
        信号量机制实现进程同步
例如n个进程需要依次序执行，则定义n个信号量，首个执行的进程初值为1，其他均为0.优先执行的进程先调用自身信号量的wait，执行完毕后调用下一个执行进程的signal
若规定代码6在代码2后执行，代码1在代码4后执行，则需要定义2个信号量，均初始化为0。
代码6前调用信号量62的wait，代码2后调用信号量62的signal
代码1前调用信号量14的wait，代码4后调用信号量14的signal
      经典问题
        生产者跟消费者问题
          角色和约束
            生产者进程：主要作用是生成一定量的数据放到缓冲区中，然后重复此过程
            消费者进程：在缓冲区消耗这些数据
            缓冲区：生产者和消费者两个进程共享的公共资源，属于临界资源
            约束条件
              生产者不会在缓冲区满时加入数据
              消费者不会在缓冲区空时消耗数据
              任意时刻，最多只允许一个生产者或一个消费者进入公共区域
          存在的互斥关系
            一个生产者进入缓冲区时，其他生产者和消费者不能进入
            一个消费者进入缓冲区时，其他生产者和消费者不能进入
            生产者和消费者互斥访问缓冲区
            定义一个互斥信号量即可
          存在的同步关系
            当产品放满缓冲区时，生产者必须等待，使消费者先消费
            当缓冲区为空时，消费者必须等待，使生产者先生产
            生产者与消费者对缓冲区的访问必须同步
            定义两个同步信号量，一个表示剩余空间，一个表示产品数量
          解决的方法
        读者写者问题
          角色和约束
            写者：往数据库中写入数据
            读者：从数据库中读出数据
            数据库：存储写入的数据
            约束条件
              不能有两个写者同时进行写操作
              不能同时有一个线程在读，而另一个线程在写
              多个读者可以同时读数据
          存在的互斥关系
            写者与写者互斥
            写者与读者互斥
            定义一个互斥信号量
          存在的同步关系
          解决的方法
            只定义一个rw锁，初值为1。
写者锁容易
但读者锁要特殊处理：使用count计数读者数量，由第一个读文件的读者加锁，再由最后一个读完的读者负责解锁
        哲学家用餐问题
      例题
          互斥关系
            同一时刻只能有一个读者登记或消除
            定义一个互斥信号量
          同步关系
            只有座位不为空时，读者才能进入
            只有读者不为空时，离开才能消除数据
            定义两个同步信号量，一个表示座位数量初值100.一个表示读者数量初值0
          解答
      什么是饥饿？
        某进程一直不能得到资源。短进程优先(SPF)算法中，若有源源不断的短进程进来，则长进程将一直得不到处理机，从而发生长进程"饥饿"
      什么是死锁？
        多个进程互相等待对方释放资源才能继续运行的现象。若无外力作用，将永远保持等待状态
        死锁产生的条件（同时满足）
          互斥：多个进程使用的是互斥的资源
          不抢占：进程使用资源时不会被其他进程抢占
          请求和保持条件：每个进程至少持有一个资源，但却申请新的资源，而该资源因为被占用导致进程处于等待状态
          循环等待：每个进程都持有其他进程所需的资源，但都处于等待状态不释放自己的资源
    多级索引问题
      多级索引的原理
        根据磁盘块大小y/指针大小,可以得到一个索引块能容纳的指针数量x。每个指针指向一个磁盘块
        直接索引
        一级间接索引块具有x个指针，这x个指针指向x个磁盘块，提供 x* y的容量
        二级间接索引块具有x个指针，这x个指针指向x个一级间接索引，因此提供x^2 * y的容量
        三级间接索引块具有x个指针，指向x个二级简介索引块，因此提供x^3 * y 的容量
      例题
          注意，题目给出的一二三级间接索引块，指的是文件系统中的数据结构（称为inode）。
但二级间接索引块可以指向2048个一级间接索引块，三级间接索引块可以指向2048个二级间接索引块
虽然它们都是索引块，但只有题目给出来的间接索引块才是被inode直接管辖的，是独一无二的；而它们指向的索引块是被inode间接管理的索引块，可以有很多个
          题目也给了直接索引块=12个，这是指12个隶属于inode管理的指针，而不是切实的索引块，因此它们存储的容量为12*8K
          8KB/4字节=2048个，由此得每个索引块可以容纳2048个指针
直接索引块提供的容量：12*8K=96K
一级间接索引块提供的容量：2048*8K=16M
二级间接索引块提供的容量：2048*2048*8K
三级间接索引块提供的容量：2048^3*8K
  一些概念
    操作系统局部性原理
      时间局部性：一块数据被访问，有很大概率再次被访问
        循环可以体现
      空间局部性：访问x地址，很大概率访问x地址附近的数据
        连续的数组可以体现
但a[0][0],a[1][0]不能
  自由主题