ECE650-final review
1 User Space/Kernel Interaction
1.1 operating system services
- accounting – 根据用户或流程跟踪资源的使用情况
- protection & security – 保护独立进程; 用户安全
1.2 Interrupts
- 定义: 发送给处理器的输入信号，表示需要立即处理某一事件
- 它是一个request，要求处理器中断当前的执行，并切换到一个特定的事件处理代码
- 中断是通过实现委托delegation和异步asynchronicity来避免busy-wait机制的一个例子
来源
- hardware interrupts: 处理器外部设备发送的电子信号，如磁盘控制器或外设peripherals(e.g. 按下按键)
- software interrupts: 作为软件执行的结果而发出
普通中断:一些指令被设计用来调用操作系统，例如当它们被用来与设备驱动程序交互时
Exception:某些情况下，如程序执行错误会导致中断(如除零)，操作系统将被调用来处理它
classification
handle
- HW: 请求主处理器接管,发现（jump to interrupt service routine），处理
- CPU内部 – under the hood
- handle multiple requests ：通过polling投票（busy-wait，但在HW支持下完成）
- Interrupt controller：IPC -中断可编程控制器，一个特殊的硬件组件
1.3 exceptions
classification
- 处理器检测到：CPU在执行指令时检测到异常情况
- 故障faults:可以纠正，一旦纠正，程序可以恢复。示例:page faults
- Aborts:严重错误，如硬件故障。如果发生这种情况，进程将终止。
- 可编程序异常programmable exceptions：通常称为软件中断，用于实现系统调用和调试(也称为TRAPS)
1.4 signals – from SW to SW
- 用于通知进程事件(包括异常):进程之间或进程与内核之间IPC通信的基本形式
- 本质上是一种软件模拟中断机制的方法
- 包括同步和异步
handle
- 每个signal有默认的handler，kernel来run；也可以override来user-defined
1.5 system calls
- 类似于中断interrupt机制
- 系统调用会导致“trap”指令的执行，Trap将控制转移到interrupt vector中的一个位置，中断向量位置跳转到trap处理程序代码
- Trap处理程序代码改变到主管执行模式保存进程状态(如寄存器，pc)，就像一个上下文切换
- 参数通常通过间接传递，例如，寄存器将一个内存地址存储到一个内存块中，which包含参数值
- 内核执行系统调用
- 恢复用户执行模式
- ’ Return from Interrupt '执行以恢复用户进程
2 Process Management & Scheduling
- OS通过Process Control Block (PCB)跟踪管理进程
操作系统保存的每个进程的数据结构(对象)，包含: 进程状态，程序计数器，CPU寄存器，scheduling信息(例如，优先级，调度队列指针)-内存信息(例如，页表指针)，accunting信息(例如，CPU时间，进程ID)， I/O信息(例如，打开的文件列表，I/O设备) - 多线程进程：扩展PCB以存储每个线程的信息
- 由于硬件限制，可能会有更多的进程对比HW可以执行的：
至少1个HW线程(单CPU，单核)。几个SW线程通过时间切片+上下文切换并行运行
4核CPU: 4 HW线程，即真正的并行 - 具有多线程cpu的架构：
SMT -Simultaneous Multi-threading；每个单核CPU提供2个HW线程；与多核CPU的性能不一样 - OS scheduling queues：
OS使用队列结构来调度：PCBs链表
新创建的进程被放置在一个“new job”队列中，准备执行的进程被放置在“ready队列”中。
当前占用HW线程的进程被称为“running”；无法执行的进程，如正在等待的进程，被放置在“event队列”中，例如:由于页面故障等待磁盘，等待从键盘输入I/O - process states
- context switch time是性能overhead开销，取决于处理器中寄存器的数量和HW支持
- CPU sharing：
两个主要目标：1. 细粒度的CPU共享fine grained sharing of CPU提供并行性的假象(并发执行)；2.效率：CPU处理和I/O活动之间交替；CPU突发bursts:快速； I/O爆发bursts:慢，在I/O完成时切换到另一个进程
- First Come, First Serve (FCFS or FIFO)
无优先non- preemptive的调度策略（Job在CPU上保持，直到它完成。即非常大的时间片）
易于设计和实现（FIFO的PCBs），从上下文切换没有开销，但某些指标可能存在不良行为（等待时间、周转时间、响应时间），variability易变性导致不良行为（CPU burst时间和CPU与I/O混合的可变性） - Shortest Job First (SJF)
另一个非抢占式调度程序（Job在它完成之前一直保持在CPU上），最佳减少平均等待时间
有时直接实现(batch job schedulers批处理作业调度程序)（用户请求的运行时限制用作作业执行时间）
可以是抢占式or非抢占式：非抢占式（任务保持在CPU上，直到完成CPU burst），抢占式（一个加入Ready队列的新进程会导致调度器再次运行，并可能进行上下文切换
- SJP —— Preemptive
工作要求必须准确知道，可能会导致饥饿starvation；处理器的更多开销（上下文切换，用于管理优先级的额外数据结构） - Earliest Deadline First Preemptive (EDF): 如果新任务到达的截止日期早于当前执行任务的截止日期，则发生抢占
如果CPU利用率低于100%，所有的截止日期都能满足;如果系统过载会发生多米诺效应
- Priority Scheduling（抢占/非抢占）, Round-Robin Scheduling(抢占式，长wait time)，Multi-Level Queue Scheduling，Multi-Level Feedback Queue Schedule
3 Protection & Security
3.1 protection
- Protection是一种机制，Policies may adapt and change over time (or between different applications)，allow flexibility
- least privilege原则，用户、进程等总是拥有完成预期任务所需的对资源和特权的最低访问级别
操作系统设计为此提供支持：提供给应用程序的系统调用和服务使用细粒度fine-grained权限和控制，根据需要启用和禁用授予应用程序的权限，也适用于用户(单独的帐户，权限)
- 进程对对象的操作权限分为静态和动态
通过两种方式实现动态权利：1. 通过一种机制来更改对象的访问权限（使用chmod修改执行权限）2. 通过一种切换subject的机制（创建具有所需访问权限的新subject，例如，用户/管理员模式(sudo命令)） - access matrix
基本访问矩阵允许定义并执行access control policy，但只能是静态的
提供动态的right: 1. subject switching(添加access matrix entries来强制“switch”操作权限,例如:sudo, setuid); 2. 允许对访问矩阵项进行有控制的修改(示例:chmod、谷歌硬盘共享设置)
implementation: 1. global table – List of <subject, object, rights> tuples; 2. access list – Maintain a list per object with <subject, rights> (column-based)
3.2 security
- 保护用于internal users，security与外部环境有关:
如果安全受到威胁，保护就会被破坏; 只有当用户的行为符合预期时，保护才能正常工作 - terminology:
THREAT: 任何能够对计算资产(数据/信息)造成伤害的东西(例如利用程序中的漏洞的人)
ATTACK: 一次破坏安全的尝试
EXPLOIT: 成功的攻击
MALWARE恶意软件：任何故意设计的软件，以损害计算机，服务器，客户端，或计算机网络 - security violation的种类：
保密违反confidentiality breach: 数据盗窃,例如信用卡、账户信息;很常见的目标
诚信违反Integrity breach: 未经授权的代码或数据修改，例如改变银行帐户的余额
可用性侵犯availability breach: 破坏数据,例如删除客户帐户信息或破坏网站或会议室(如ZOOM)
服务盗窃theft of service: 未经授权的资源使用，例如免费访问Netflix
拒绝服务denial of service: 防止系统的合法使用，例如ping的战争! - domains of security measures:
Physical: 需要确保计算机系统所在站点的安全,只有授权的管理员/用户才能进行物理访问
Human awareness: social engineering 可能会欺骗授权用户执行无意的安全漏洞; 钓鱼获取信息，执行恶意代码
操作系统: 防止意外或有意破坏的机制
网络: 保护网络传输的数据不被拦截或篡改 - threats的种类包括：对running programs的威胁（Trojan Horse，Backdoor，Logic Bomb，Stack (or Buffer) Overflow，Viruses），对system和network resources的威胁（Port Scanning，Worms，Bots，Denial of Service，Rootkits）
4 I/O Handling
- Processor interface to I/O devices
处理器芯片有几种类型的I/O连接(物理引脚!): 用于连接PCIe总线bus, 用于连接内存memory总线, 其他专用I/O to chip(例如power)
- device controllers
处理器与目标设备的控制器交互，处理器可以发送命令/数据(或接收)
控制器包含命令/数据寄存器，处理器与这些寄存器通信的两种方式：1. 专用的I/O指令，传输bit到I/O端口地址；2. Memory mapped I/O:控制器寄存器映射到mem地址（标准的load/store指令可以写入寄存器，如图形控制器具有较大的内存映射空间用于像素数据）
通常至少4个寄存器：
Command: 由主机写入，表示要执行的命令
** Data-in** 数据导入(到处理器)
Data-out数据输出(来自处理器)
Status: 设备的状态，如设备忙、数据准备好、错误等 - Processor-device interaction：handshade protocol握手协议
- 主机在状态寄存器中读取一个busy bit，直到设备空闲
- 主机set write bit在命令寄存器，写入数据到data-out
- Host在命令寄存器中设置command ready bit
- 控制器检测到command ready bit set & set busy bit
- 控制器读取命令寄存器;看到命令;does I/O with device
- 控制器清除command ready bit; 清除status寄存器中的error & busy bits
- 使用interrupt mechanism来提高performance：通知CPU设备状态的变化，no busy-wait
- 另一个performance问题：shakehands意味着来自处理器的严格控制——处理器监控status bit(或interrupt)，通过data-in/data-out寄存器一次以字节bytes或words的形式移动数据
但一些设备通常用于一次传输大数据块，例如磁盘、网络，PI/O（programmed I/O）太耗时了 - Direct Memory Access（DMA）：
专用的HW engine或logic：处理器写DMA命令到内存缓冲区（指向src和dest地址的指针，要传输的字节数），处理器写DMA command block的地址给DMA控制器，DMA engine operates on memory & handshakes with device
DMA与device控制器interacts：当有数据可以传输时，设备assert DMA-request；DMA控制器获得总线bus控制（在bus上放置适当的request address，assert DMA-acknowledge wire），设备控制器将数据放到总线上
完成时，DMA控制器产生一个CPU interrupt
- Device drivers：对I/O子系统尽可能隐藏特定于设备的controller细节（操作系统易于开发和维护，设备厂商可遵循通用接口）
设备驱动程序软件通常是特定于操作系统OS-specific的，不同操作系统的接口标准不同
几个不同的设备类别, 根据不同的设备特点：block I/O如硬盘、光驱，character-stream I/O如键盘、鼠标、serial port串口、modem调制解调器，memory-mapped file内存映射文件如显卡video card（frame buffer），network sockets网络套接字如Ethernet，WiFi NIC - 同步性Synchronicity in I/O
阻塞blocking: 进程在发出阻塞的IO系统调用时挂起, 从就绪队列移动到等待队列, IO完成后移回就绪队列
非阻塞Non-blocking(reads): 进程不等待数据(return任何准备好的数据-可能没有)，例如用户界面接收键盘鼠标输入
异步Asynchronous：IO调用立即返回 & I/O操作启动，进程通过稍后的interrupt得知I/O完成；可以通过使用select()实现，等待时间为0，如果任何source已经准备好数据，则后跟read() - OS kernel services for I/O：Scheduling of I/O requests；Buffering；Caching；Spooling假脱机；Device Reservation；Error Handling；Protection of I/O
- double buffering model
- spool：为具有固有顺序的设备保存数据的缓冲区类型，无法接受交叉interleaving服务请求
5 File Systems
- 磁盘是一种随机访问内存
- File systems abstractions
5.1 File
- File是secondary存储上已命名的数据集合，用户只通过文件与二级存储进行交互
file可以表示许多不同类型的信息：可执行程序，数据库，电子表格，文字处理文档，文本文件……
文件中信息的组织取决于其类型。例如，文本文件vs对象文件vs可执行文件 - attributes属性：name、ID(文件系统内unique number)、类型、存储设备上的位置、大小、access control protection
- 文件操作需要找到文件：文件通常通过搜索文件名的“directory”来找到（一个文件名的目录条目将指向它的磁盘位置），OS通过保持一个open-file table来优化这个（所有打开文件的信息），文件打开后，可以通过ID来reference，例如，文件描述符file descriptor，指向open-file table中的position
- File system directory：用于管理系统文件的symbol table,存储有关文件的元数据(名称、磁盘位置、文件类型等)
当文件被打开，搜索，创建，删除，重命名，或遍历目录时，使用文件系统目录
FS directory的可能organization:
single-level:所有文件必须有一个不同的名称
two-level: 例如，每个用户一个文件directory，用户文件在里面
Tree structure: 熟悉的大部分操作系统，真实文件名为——文件名+通过目录树到达该文件的path - implemant directory需要从file location映射到device storage blocks
将文件名映射为指向文件数据块的指针，使用list，hash table - directory as list
- directory as hash table
5.2 Disk allocation:
- Contigouous allocation连续分配：每个文件占用磁盘上一组连续的块
- Linked allocation：解决连续分配的缺点，文件占用a linked list of磁盘块, 单个文件的块可以位于磁盘上的任何位置
目录存储指向第一个块和最后一个块的块指针，每个块存储指向下一个块位置的指针，用户无法使用指针，但在空间方面有overhead开销
File-Allocation Table (FAT) file system：每个disk block一个entry(按块号索引), 文件的目录条目包含FAT中开始块的指针。FAT中的每个条目都存储了一个指向文件下一个条目的指针，实质上，FAT将所有的块指针组合在一起(不需要将它们放在块中)，优点是FAT可以被缓存，改进随机文件访问行为
- Indexed allocation: 解决linked allocation的random access problem，将block pointers聚集在一个index block中（类似于分布式FAT），每个文件都关联一个index block(指向file blocks的指针list, 第i个index block pointer指向文件的第i个块)
关于文件创建: 分配index block; 所有指针都设为NULL
写入文件(如果需要一个新的块): 从空闲空间manager获取块, 在下一个NULL索引块条目中存储块地址
- Hybrid indexed allocation – UNIX/Linux
使用ext3 -在Linux中经常使用的 third extended file system
Directory entry data structure称为inode, 一个inode有几个字段(文件模式，所有者，时间戳timestamps，size(block count)，包含15个指针的index block(前12个点直接指向文件数据block, 一个single-indirect指针, 一个doubly-indirect指针，一个triply-indirect指针
优势: 小文件适合直接索引指针, 更大的文件越来越多地利用间接索引列表
- 日志 Journaling in file systems:
Ext3和ext4引入了日志记录, 日志是一种激发事务系统transactional systems to facilitate file system recovery after a failure的机制 - Free space的管理：删除其他文件后，需要重新使用磁盘空间存放新文件。
系统维护一个列表来跟踪空闲块（创建文件从空闲列表中删除一些块，删除文件将一些块添加到空闲列表中）
Free list实现选项：位图bit map，链表，grouping，counting
6 Virtual Memory Management
- 物理内存可以存在于不同的层次结构: 允许运行比物理内存大的程序
- MMU (Memory Management Unit): 将逻辑virtual地址转换为物理地址的硬件（在操作系统控制下）
- Mapping address spaces
- OS memory virtualization by simple re-mapping
Stores a base memory address for each program, the “Base_Register”
Stores the size of largest addressable location for each program/process, the
“Limit_Register”
- 内存的层次结构：内存是根据响应时间分层的；最快的内存在顶部，最慢的在底部
- non-contiguous physical memory：物理内存划分为固定大小的block(frames), 虚拟地址空间也分为same-size blocks(PAGES), 由处理器生成的地址有两部分(page number, Page offset(byte address within the page)）。
一个表存储每个virtual page的physical frame number, called PAGE TABLE (PT), - Paging mechanism
addressable physical space的最大大小: 如果每个PT条目有4个字节(32位)，页面大小是4KB(12位)，那么总的可寻址内存由2^32 * 2^12 = 2^44的物理内存位置组成 - 使用硬件解决方案缓存PT条目：
Cache PT是TLB-Translation Lookaside Buffer(通常是一个完全associative cache)：虚拟到物理页面转换的cache，一个虚拟地址的TLB miss需要单独的mem access
TLB可以存储拥有page address的进程ID：这样，它可以缓存数据从多个进程page tables和同时服务多个进程(效率更高)，扩展进程地址空间隔离的保护机制(更好的保护) - hierarchical page tables
- Inverted page table：在memory中每个physical page frame一个entry, 每个条目提供它存储的logic页面(和PID), 寻找虚拟到物理的页面映射需要搜索(可能是倒排页表中的每个条目!)
search time: 使用hash inverted page tables来解决
hash input key是logical page number, 每个哈希表value都是a list of physical frames(包含frame number，PID，指向下一个列表的指针(用于chaining，以防key collisions)
在TLB miss的情况下(希望如此)，减少了搜索倒排页表中散列项的额外内存访问的成本 - demand paging：将pages引入memory as needed
pages在mem和disk之间的移动（这是操作系统的一个管理功能）
- TLB hit
many CPUs have multi-level TLB cache hierarchy
- TLB miss + page table hit
需要访问的software page table structures(page Table entry valid bit is set)
可以通过SW完成(trap到OS)
为了TLB miss而将上下文切换到操作系统会增加很大的开销, 这就是为什么大多数架构都有一个特殊的HW支持(page table walker)
entry加载到TLB中，用于将来的translation
- Page fault
导致trap进入OS(肯定需要I/O操作)，OS启动disk操作来检索page
OS指定一个physical memory frame来存储该page: 任意一个free frame(例如通过一个free-frame list), 或者必须选择valid frame从内存中“驱逐evict”并写回disk(当某个“valid”bit变成“invalid” bit时)
OS修改page table entry: 设置valid bit、PID字段、physical frame
OS从trap返回(像从interrupt返回)来重新执行指令 - Page replacement
swap: e.g. evicted page moves from DRAM to DISK, new page from DISK to DRAM
优化：在硬件中为每个memory frame保留一个dirty bit: 只有当它是dirty的时候才将page写回disk，否则，可以简单地用new page data覆盖该frame(显著减少磁盘I/O时间)
将被驱逐的dirty page写回专用disk swap space - FIFO policy
- LRU policy
stack of page frames, each page access moves it a page to top, remove element at the bottom - LFU policy
- Swap space：
硬盘的专用部分, 不作为文件系统的一部分（单独分区，没有常规文件可以存储在那里）
swap space的主要功能是在实际RAM已满且需要更多空间时，将磁盘空间替换为RAM内存
用于存储移动到内存或从内存移出的pages，比file system portion更快或更有效 - Trashing
swap的频率随着内存使用的增加而增加
系统繁忙的读写，而不是执行有用的指令, CPU利用率低
平均内存访问时间等于磁盘访问时间 --> illosion breaks: 内存看起来像磁盘一样慢，而磁盘看起来像内存一样快
添加更多进程，thrashing会变得更糟
