KING

charpter 8 Main Memory

• background

  • address binding内存绑定

    • 在三个时间发生
      • 编译时间
        • 如果内存地址确定，那么就生成absolute的代码：如果内存的起始地址改变了，代码就要重新编译
      • 载入时间
        • 如果内存地址再编译时间不是确定的，就要生成relocatable(可重定位)的代码
      • 执行时间
        • 如果进程能够重一个内存段移动到另外一个内存段，那么就把绑定地址延迟到run time。需要硬件支持

  • logical and physical address space逻辑地址和物理地址

    • logical address
      • CPU生成的地址，也就是虚拟地址
    • physical address
      • 内存单元看见的地址
      • 加载到寄存器中的地址
    • 不同
      • 在编译时间和载入时间logical地址和physical地址一样
      • 在执行时间的时候不一样
  • Memory management Unit(MMU)
    • 用于映射虚拟地址到物理地址
    • 因为真实的程序用的都是逻辑地址
  • dynamic linking动态链接
    • 和动态加载的不同在于
      • 不是把加载延迟到运行时，而是将连接延迟到运行时
    • 常用于系统库
  • dynamic loading动态加载
    • 一个子程序只有在调用时才被加载，所有子程序都以可重定位的形式保存在磁盘上。
    • 优点：
      • 不用的子程序不会被装入内存
• swapping交换空间
  • 内存需要在内存中来执行
  • 但是进程可以暂时从内存中交换出来到备份储存上，在执行的时候再调回内存
  • 交换时间的主要消耗是在传输时间
• contiguous memory allocation连续内存分配必考
  • 动态内存分配
    • 首次适应
    • 最佳适应
    • 最差适应
• segmentation分段
  • a segment is a logical unit
    • 比如
      • main program
      • procedure
      • function
      • method
      • object
      • common lock
      • stack
      • array
  • 外部碎片
    • 放不进内存的块
    • 因为内存被用完了，剩下的空间大小不足
      • 因此本来要放进去的块，放不进去了
  • 内部碎片
    • 内存空间剩下的那些一点点的空间，放不下其他的块
    • 这些小小的空间就是内部碎片
• paging分页
  • 进程的块也叫页

  • 把页平均分成一定数量的页

    • 这样分配空间的时候可以更充分地利用空间
    • 并且不会有外部碎片，只会有内部碎片

  • page table

    • use to translate logical to physical address
    • address is devided into
      • page number
      • page offset
    • implementaion
      • PTBR 页表基寄存器
        • point to page to table
      • PRLR 页长寄存器
        • indicate size of the page table
      • TLB 翻译后备缓冲器
        • 又叫关联内存
        • special fast-lookup cache
  • effective memory-access time 有效内存访问时间
    • EAT = 内存映射反应时间命中率 + （1-命中率）（内存映射反应时间+额外时间）
  • valid-invalid bit
    • 用于保护
    • valid的意思是要找的页在进程的逻辑地址空间里面
    • invalid的意思是是不在

charpter 9 virtual memory

• background
  • 因为程序执行的时候只需要一部分程序在内存里面
  • 把user的逻辑内存从物理内存里面分离出来
  • 进程中所有寄存器访问的地址都是逻辑地址，这些逻辑地址在运行的时候被转换成物理地址
  • 效果
    • 主存中保留多个进程
    • 进程可以比主存的全部空间还大

• demand paging

  • lazy swapper
    • 只有在需要的时候才把页调进主存
      • 可以造成更少的I/O
      • 更少的内存使用
      • 更快的速度
      • 更多的用户
  • 如果页已经在内存里面了，那么这个页就是valid
    • 否则就是invalid(造成page fault，因为是对无效地址的访问)

• page replacement

  • FIFO
    • 每次换第一个
  • opt
    • 淘汰离现在最长时间后再访问的页
  • LRU
    • 把离现在最远没有调用的换掉
• allocation of frame
  • equal allocation
    • 在n个进程之间分配m个frame
      • 那么就是平均每个进程一个平均值m/n
  • proportional allocation
    • gloabl replacement
    • local replacement
• thrashing
  • 频繁的把页调出去又调进来，导致严重的性能问题

  • working-set model

  • page fault frequency

charpter 10 Mass-storage structure

• disk structure
  • logical block
    • disk drive被addressed做一位数组的逻辑块
      • 这些块是传输的最小单元
  • CLV
  • CAV
• disk attachment
  • host attached storage accessed through I/O ports talking to I/O busses
• disk scheduling
  • access latency
    • = Average access time = average seek time + average latency
  • seek time
    • 寻道时间
    • 约等于seek distance
  • rotational latency
  • bandwidth
    • byte 传输的总数
  • algorithm
    • 比如有queue:98，183，37，122，14，124，65，67 -start from 53
    • FCFS
      • 从头加到尾
      • 所以执行队列
        • 53，98，183，37，122，14，124，65，67
    • SSTF
      • 最常用
      • 把绝对值离起点最近点依次加入
      • 所以执行队列
        • 首先排序
          • 14，37，65，67，98，122，124，183
        • 然后找离起点绝对值最小的
          • 53，65，67，37，14，98，122，124，183
    • SCAN
      • 先把数组排序
      • 然后从左扫到右，然后再从右扫到左
      • 所以执行队列
        • 首先排序
          • 14，37，65，67，98，122，124，183
        • 53，37，14，0，65，67，98，122，124，183，255
    • C-SCAN
      • 先把数组排序
      • 然后从左扫到右，然后再从头扫到尾
      • 所以执行队列
        • 首先排序
          • 14，37，65，67，98，122，124，183
        • 53，65，67，98，122，124，183，255，0，14，37
    • LOOK
      • 先把数组排序
      • 然后从左扫到右，然后再从右扫到左
      • 执行队列不含有0和255
        • 53，37，14，65，67，98，122，124，183
    • C-LOOK
      • 先把数组排序
      • 然后从左扫到右，然后再从头扫到尾
      • 53，65，67，98，122，124，183，14，37
• disk management
  • low level formatting
    • physical formatting
    • divide a disk into sectors that the disk controller can read and write
    • 把disk分成几个sector
  • bootstrap被存储在ROM里面

• swap-space management

  • 虚拟内存使用磁盘空间来作为内存的extension
  • 因为虚拟内存的使用是
    • 程序只有一部分在内存里面，其他的部分都放在磁盘上
    • 只有在需要使用其他部分的时候才会把哪些部分放进内存

• RAID structure

  • redundant array of inexpensive disks

  • reliability

    • 通过redundancy是的多个disk drives提供可靠性

  • MTTF

    • mean time to failure

  • MTTR

    • mean time to repair
    • exposure time when another failure could cause data loss
  • data striping
    • 把一组disk用作一个存储单元
  • bit-level
  • block-level

charpter 11 file system interface

• file concept

  • file attribute

    • name
    • id
    • type
    • date
    • size
    • protection

  • file operation

    • read
    • write
    • execute
    • delete
    • create
    • seek
    • open
    • close
  • file type
    • data
      • numeric
      • charactor
      • binary
    • program

• access method

  • sequential access顺序访问
    • 一个记录接着一个记录的访问
    • 常用于文件读写
  • direct access直接访问
    • 文件由固定长度的逻辑记录组成，允许任何程序按照任意顺序进行快速读和写
    • 基于文件的磁盘模式
    • 常用语数据库
• directory and disk structure
  • single level directory
    • 相当于单层map
      • <command,file>
  • two level directory
    • 每个用户都有自己的文件目录
    • 相当于双层map
      • 第一层变成<user,command>
      • 第二层变成<command,file>
• tree structure directory
  • general graph directory
    • 其实和双层很像，前两层一样
      • 第三层开始多了很多别的命令的map
• file system mounting
  • mount point
    • 文件系统使用之前必须要mount
    • 也就是说目录结构要建立在多个分区上就必须安装这些分区来使其可用
    • mount point 通常是空目录
      • 用于安装文件系统
      • e.g unix常常安装在/home
        • 这样访问这个文件系统的目录结构的时候
          • 只要加上这个/home前缀就可以了

charpter 12 file system implementation

• file system structure
  • 文件结构
    • 逻辑存储单元
    • 相关信息的收集
  • 文件系统依赖磁盘
  • 磁盘提供random access和inplace write
  • file control block
    • 记录文件信息
  • device driver
  • layer file system
    • 应用程序->逻辑文件系统->文件组织模块->基本文件系统->I/O控制->设备
• file system implementation
  • 使用多个磁盘和内存结构
    • boot control block
      • 包括系统冲该分区引导操作系统所需要的信息
    • partition control block
      • 包括分区的详细信息
  • VFS
    • 虚拟文件系统允许使用同样的系统调用API来使用不同类型的文件系统
• directory implementation -使用线性表和hash表来指向数据块

• allocation method

  • disk block给文件的分配方法
  • 连续分配
    • continguous allocation
    • 每个文件使用一个集合的连续块
  • 链式分配
    • 每个文件都有一个链表的block
  • index分配
    • 每个文件都有他自己的index block

• free space management

  • 文件系统使用free space list 来跟踪可以使用的block
  • bit vector
  • bit map
  • Grouping
  • counting

• efficiency and performance

  • 效率
    • 取决于所使用的磁盘分配和目录管理算法
    • 首先是只要是磁盘就会有一定的空间用来存索引节点
      • 因为索引会加快查询
  • 性能
    • 增加复杂的index

• recovery

  • consistency checking
    • compare data in directory structure with data block on disk and try to fix inconsistencies
    • 慢而且容易失败
  • 用系统程序备份数据
  • 用备份恢复系统程序

• log structured file system

  • 用来记录每个metadata的更新

• NFS

  • 一个用来通过网络远程access file的软件系统

charpter 13 I/O system

• I/O hardware

  • basic

    • port端口
      • 设备的连接点
    • bus总线
      • 直接共享连接
    • controller控制器
      • 操作port，bus，device的电子元件
    • I/O指令控制设备

  • SCSI

    • SCSI总线控制器常常是纤维和计算机相连接的独立线路板或者主机适配器

  • memory mapped I/O

    • 内存映射I/O
      • 设备数据和指令寄存器映射到处理器的地址空间
      • 例如，PC可以用I/O指令来控制一些设备，并且使用内存映射I/O来控制其他设备

  • I/O port register

  • polling轮询
    • 主机和控制器之间的交互完成协议需要握手
    • 过程
      • 首先忙等待读取忙bit
      • 然后如果接到下一个命令，就清除忙bit
      • 然后通过命令寄存器里面的命令就绪bit来表示其意愿
• interrupt
  • 设备控制器通过catch中断并且dispatch到中断处理程序
  • 中断处理程序通过处理设备来清除中断
  • 终端也可以用与异常处理
• DMA
  • 直接内存访问
  • direct memory access
  • 用于避免对大规模数据移动使用I/O
  • 这样无需cpu的帮助也可以把地址放到总线然后开始传输
• Kernal I/O subsystem
  • I/O scheduing
    • 有一些I/O请求通过设备队列来排序
    • 有一些操作系统使用公平式的
    • 有一席实现服务质量
  • buffering
    • 在设备之间传输数据的时候把数据存在内存里面
    • 为了解决以下两种情况
      • 设备速度不一样
      • 设备传输大小不一样

安全

• goal of protection

  • 确保每个对象的访问都是正确的，没有越权访问

• principal of protection

  • 最低优先级准则
    • 给程序分配他所需要的最低优先级

• domain of protection

  • domain:set of access right

    • 等于user id
    • 在文件系统之间交换

  • domain：可以含有user, process, procedure

  • access-right: <object-name, right-set>

• accesss matrix

  • 行：domain
  • 列：object
  • Access(i,j)：在domain(i)中的process能够对object(j)使用的operation set
• implementation of the access matrix
  • 用(sparse)稀疏矩阵实现
  • option1
    • global table
      • 三元式<domain, object, right-set>
  • option2
    • access list
      • 每一列是一个object
      • 然后每个object含有一个list<domain, right-set>
• access control
  • 使用access matrix 来控制用户的访问权限
  • 要对process设置privilage
  • capacity list
  • access list
• security problem
  • 资源和访问是否在所有情况下使用正确
  • man in the middle attack
    • 接入sender和receiver的信息传输
      • 更改传输的信息
  • four level of security problem
    • physical
    • operating system
    • human
    • network
• program threat

  • trojan horse

    • 木马
    • 一个误用自身环境的代码段

  • trap door

    • 后门
    • 在程序中留一个只有他自己可以使用的漏洞
  • logic bomb
    • 在某种特殊情况下才会激发的安全隐患
  • virus
    • 在正常软件中嵌入的代码段
    • 用来感染别的电脑
• system an network threat
  • worm
    • 通过繁殖机制破坏系统性能的进程
      • 大量繁殖导致操作系统耗尽资源
      • 然后瘫痪系统
  • morris internet worm
    • 一个字符串查询finger，超出分配给输入的缓冲，并且覆写栈
• crytography as a security tool
  • RSA工作方式
    • 加密用公钥
    • 解密用私钥
  • 同步加密
  • 异步加密
• user authentication
  • 密码
  • biometric