操作系统笔记

计算机操作系统概述

1. 概述

        操作系统 ( $Operating\ \ System$, $OS$ ) 是指控制和管理整个计算机系统的硬件和软件资源,以提供给用户和其他软件方便的接口和环境的程序集合,是计算机系统中最基本的系统软件。没有任何软件支持的计算机称为裸机。裸机在最里层,外面是操作系统。
        操作系统是计算机系统资源的管理者:

        操作系统还提供了用户接口:

        计算机系统中,通常CPU执行两种不同性质的程序:一种是操作系统内核程序,另一种是用户自编程序或者系统外层的应用程序。对于操作系统而言,前者是后者的管理者。内核程序可以执行一些特权指令,如I/O、中断、管理程序状态字寄存器等,出于安全考虑,这些程序不能被用户直接使用。操作系统在实现上划分了核心态(管态)和用户态(目态)以严格区分两类程序。
        内核是计算机上配置的底层软件,大多数操作系统的内核包括四个方面的内容:

        从上述内容可知,核心态指令包括系统调用类指令和一些针对时钟、中断和原语的操作指令。
        操作系统不允许用户程序实现核心态的功能,而它们又必须使用这些功能。因此,需要实现核心态和用户态之间的转换。在实际操作系统中,CPU运行上层程序时的唯一转换途径是通过中断或异常。当中断或异常发生时,运行用户态的CPU会立即进入核心态,这是通过硬件实现的(例如用一个特殊寄存器表示)。
        中断 ( $Interruption$ ) 指来自CPU执行指令以外的事件的发生,如设备I/O中断、时钟中断等。访管指令是一条可以在用户态下执行的指令,用于产生一个中断,称为访管中断,系统会根据访管指令的操作数执行对应的访管中断处理程序。异常 ( $Exception$ ),也称为陷入 ( $Trap$ ) ,指来自CPU执行指令内部的事件的发生,如程序的非法操作码、地址越界、内存缺页以及专门的陷入指令等。对异常的处理一般要依赖于当前程序的运行现场,并且异常不能被屏蔽,一旦出现应立即处理。
        系统调用是用户在程序中调用操作系统提供的一些子功能,可以把系统调用看作是特殊的公共子程序。在用户程序中,凡是与资源有关的操作,都必须通过系统调用向操作系统提出服务请求,并由操作系统代为完成。系统调用大致可以分为如下几类:

        用户通过操作系统运行上层程序,上层程序依赖于操作系统的底层管理程序提供服务支持。当需要管理程序服务时,系统通过硬件中断机制进入核心态;当程序运行出现异常时,系统通过异常处理机制进入核心态。当管理程序结束时,用户程序继续运行,通过之前中断处理程序或者异常处理程序保存的中断现场,返回断点处继续执行。

2. 进程和线程

2.1 进程

        在多道程序环境下,多个程序可以并发执行,为此引入了进程 ( $Process$ )。为了使参与并发执行的程序能够独立地执行,操作系统为之配置了一个专门的数据结构称为进程控制块 ( $Process\ \ Control\ \ Block$, $PCB$ )。系统利用PCB来描述进程的基本情况和运行状态,进而实现对进程的控制和管理。程序段、相关数据段和PCB构成了进程实体,进程实体是静态的,但是进程是动态的。进程创建实质上是创建PCB,撤销实质上是撤销PCBPCB是进程存在的唯一标志。PCB通常包含以下内容:

进程描述信息 进程控制和管理信息 资源分配清单 处理机相关信息
进程标识符 ( PID ) 进程当前状态 代码段指针 通用寄存器值
用户标识符 ( UID ) 进程优先级 数据段指针 地址寄存器值
代码运行入口地址 堆栈段指针 控制寄存器值
程序的外存地址 文件描述符 标志寄存器值
进入内存时间 键盘 状态字
处理机占用时间 鼠标
信号量使用

        进程通常有五种状态:

        进程可以创建另一个进程,此时创建者称为父进程,子进程可以继承父进程所拥有的资源。操作系统创建一个进程的过程如下(创建原语):

  1. 为新进程分配一个唯一的进程标识号,并申请一个空白的PCBPCB数量是有限的),申请失败则创建失败;
  2. 为进程分配资源,包括为程序和数据、以及用户栈分配内存(在PCB中体现),如果资源不足,会进入阻塞状态;
  3. 初始化PCB,包括初始化标志信息、处理机状态信息、处理机控制信息以及进程优先级等;
  4. 如果就绪队列未满,将新进程插入就绪队列中,等待时间片调度。

        正在执行的进程如果某些期待的事件未发生,如请求系统资源失败、等待操作完成,系统会执行阻塞原语,将进程由运行状态变为阻塞状态。进程的阻塞是一种主动行为,只有处于运行中的进程才能转为阻塞状态。阻塞原语的执行过程如下:

  1. 找到进程标识号对应的PCB
  2. 保护进程运行现场,将其转为阻塞状态;
  3. 将该PCB插入到相应事件的等待队列中。

        唤醒原语的执行过程如下:

  1. 在等待队列中找到相应进程的PCB
  2. PCB从等待队列中移出,将其转为就绪状态;
  3. PCB插入就绪队列中,等待调度程序调度。

        引起进程终止的事件有:正常结束,即完成任务后的准备退出运行,和异常结束,即运行过程中发生异常事件导致程序无法继续运行。终止进程的过程如下:

  1. 找到进程标识号对应的PCB,读取进程状态;
  2. 如果进程处于执行状态,终止进程执行;
  3. 若进程存在子进程,终止其所有子进程的执行;
  4. 将进程拥有的资源归还给父进程或者操作系统;
  5. PCB从所在队列的链表中删除。

        通常进程的创建、撤销以及要求系统设备完成I/O操作都是利用系统调用进入内核,再由内核中相应的处理程序完成的。进程切换也是在内核的支持下完成的,所以进程是与内核紧密相关的。进程切换的过程如下:

  1. 保存处理机上下文,包括程序计数器和其他寄存器;
  2. 更新PCB
  3. PCB移入相应的队列,如就绪队列或者某个事件的阻塞队列;
  4. 找到下一个要执行的进程,更新PCB
  5. 更新内存管理的数据结构;
  6. 恢复处理机上下文。

        进程间通信是指进程之间的信息交换,PV操作是低级通信方式,而高级通信方式能够以较高速率传输大量数据。高级通信方法主要有以下三种:

  1. 共享存储:进程间一块可以直接访问的共享空间,通过同步互斥工具控制读写,实现信息交换。低级的共享方式是基于数据结构的共享,而高级的共享方式是基于存储区的共享,操作系统负责提供共享空间和互斥工具,用户负责实现读写指令;
  2. 消息传递:进程间的数据交换以消息为单位,系统提供发送和接受两个原语。根据是否存在中间件,可以分为直接和间接两种方式。直接通信方式直接把消息发送到接收进程的消息缓冲队列上,间接通信方式则把消息发送到某个中间实体中,典型代表是电子邮箱;
  3. 管道通信:管道用于连接一个读进程和一个写进程,写进程以字符流形式将大量数据送入管道,读进程则从管道中读取数据。管道必须提供三方面的协调能力:互斥、同步和确定对方存在。

2.2 线程

        线程可以减小程序在并发执行时付出的开销,提高操作系统的并发性能。线程的最直接理解就是“轻量级进程”,它是CPU的基本执行单元,是程序执行的最小单元,由线程ID、程序计数器、寄存器集合和堆栈组成。线程是进程中的一个实体,是系统独立调度和分派的基本单位,只拥有一些运行中必不可少的资源,共享其所在进程的全部资源。线程可以创建和撤销另一个线程,同一个进程中的线程可以并发执行。线程具有就绪、阻塞和运行三个状态。在多线程操作系统中,线程作为独立运行(或调度)的基本单位。此时,进程的执行实际上指的是进程中的某个线程正在执行。
        线程的引入提高了系统的并发性和吞吐量。并且由于线程只持有一些必不可少的资源,所以在创建和撤销过程中的系统开销更小。类似地,在进行进程切换时,要涉及到当前进程CPU环境的保存以及新调度进程CPU环境的设置,而线程就只需要保存和设置少量寄存器内容即可。并且由于线程共享进程资源,所以线程之间的同步和通信非常容易实现。
        线程的实现可以分为两类:用户级线程 ( $User-Level\ \ Thread$, $ULT$ ) 和内核级线程 ( $Kernel-Level\ \ Thread$, $KLT$ )。用户级线程中,有关线程管理的所有工作都交由应用程序完成,内核察觉不到线程的存在。内核级线程中,线程管理的所有工作都交由内核完成,应用程序没有进行线程管理的代码,只有一个到内核级线程的编程接口。内核为进程及其内部的每个线程维护上下文信息。有些系统同时支持用户级线程和内核级线程,由此产生了不同的线程模型:

2.3 调度

        在多道程序系统中,进程的数量往往多于处理机的个数。处理机调度是对处理机进行分配,就是从就绪队列中按照某个算法选择一个进程并将处理机分配给它运行。一个作业从提交开始直到完成,往往要经历以下三级调度:

        系统内核负责进程调度和进程切换,当请求调度事件发生后,才会运行进程调度程序,当调度了新的就绪进程后,才会进行进程切换。通常有两种进程调度方式:

        操作系统中存在多种调度算法,有的调度算法适用于作业调度,有些适用于进程调度,还有的两者都适用。

2.3.1 FCFS

        先来先服务 ( $FCFS$ ) 调度算法是最简单的调度算法,既适用于作业调度也适用于进程调度。该算法会每次从后备作业队列或者进程就绪队列中选择最先进入该队列的一个或几个作业/进程,为它们分配资源。该算法属于非抢占算法,虽然实现简单,但是效率低,对长作业有利,适合CPU繁忙型作业,不利于I/O繁忙型作业。

2.3.2 SJF/SPF

        最短作业优先 ( $SJF$ )/ 最短进程优先 ( $SPF$ ) 调度算法是对短作业/进程优先调度的算法,即每次从后备队列/就绪队列中选择一个或几个估计运行时间最短的作业,为它们分配资源。该算法对长作业不利,容易出现饥饿现象,但是平均等待时间、平均周转时间最少。

2.3.3 优先级调度算法

        优先级调度算法会每次从后备队列/优先队列中选择一个或几个优先级最高的作业/进程,并为它们分配资源。根据新的更高优先级进程能否抢占正在执行的进程,可以将调度算法分为非抢占式优先级调度算法和抢占式优先级调度算法。根据进程创建后优先级是否可以改变,可以将进程优先级分为静态优先级和动态优先级。

2.3.4 高响应比优先调度算法

        高响应比优先调度算法适用于作业调度,在每次进行作业调度时,先计算后备作业中每个作业的响应比,从中选出响应比最高的作业运行。计算公式为:

$$ 响应比R_{\rho} = \frac{等待时间+要求服务时间}{要求服务时间} $$

2.3.5 时间片轮转调度算法

        时间片轮转调度算法适用于分时系统,系统会将所有就绪进程按照达到时间的先后顺序排成一个队列,按照FCFS原则,从队列中选择一个进程分配一个时间片。在时间片结束后,进程需要释放处理机给下一个就绪的进程,被剥夺的进程会返回到就绪队列的末尾重新排队。

2.3.6 多级反馈队列调度算法

        多级反馈队列调度算法设置多个就绪队列,并为各个队列设置不同的优先级,同时每个队列中进程执行时间片的大小也不同,优先级更高的队列时间片越小。每当一个新进程进入内存后,会先将它放入一级队列的末尾,按照时间片轮转算法调度。如果一个进程未在时间片结束后完成,将会进入二级队列的末尾……如此下去,会一直降到 $n$ 级队列。只有上级队列为空的时候,调度程序才会调度下级队列中的进程。多级反馈队列调度算法既可以兼顾多方面的系统目标,也不需要事先估计进程的执行时间。

2.4 同步

        虽然多个进程可以共享系统中的各种资源,但是许多资源一次只能被一个进程使用,我们称之为临界资源,如打印机等。对于临界资源的访问必须互斥进行,访问临界资源的代码称为临界区。同步是指为了完成某种任务而建立的两个或多个进程,因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系就是它们之间的相互合作。互斥亦称间接制约关系。当一个进程进入临界区使用临界资源时,另一个进程必须等待,直到当前进程退出临界区。
        临界区互斥的基本实现方法分为软件实现方法和硬件实现方法。软件实现方法通过一个或多个标志位判断是否存在其他进程正在访问临界区。硬件实现方法需要通过计算机提供的特殊硬件指令实现,该指令允许对一个字中的内容进行检测和修正,或者对两个字的内容进行交换等,典型的有中断屏蔽法,即在进入临界区时屏蔽中断(CPU只在发生中断时进行进程切换),或者通过 $TestAndSet$ 和 $CompareAndSwap$ 这些硬件指令实现。
        信号量机制可以用来解决互斥与同步的问题,只能被两个标准原语 $wait$ 和 $signal$ 来访问,也可以记为 $P$ 操作和 $V$ 操作。
        管程是由一组数据以及定义在数据之上的对这组数据的操作组成的软件模块,这组操作能初始化并改变管程中的数据和同步进程。管程由三部分组成:

        局部于管程的数据只能被局部于管程的过程所访问。一个进程只有通过调用管程内的过程才能进入管程访问共享数据,且每次只允许一个进程在管程内执行某个内部过程。
        死锁是指多个进程因竞争资源造成的互相等待。死锁产生的必要条件有:

        要防止死锁,需要破坏上述四个条件中的任意一个,或者能够检测死锁的发生并进行恢复。破坏产生死锁的四个必要条件的方式称为死锁预防,在资源分配的过程中用某种方式防止系统进入不安全状态称为死锁避免,而通过检测机制及时检测死锁发生然后采取措施称为死锁检测。死锁预防和死锁避免属于事先预防策略,实现起来较简单,但是效率低。而死锁避免的实现较为复杂。
        死锁预防只需要破坏死锁产生的四个必要条件之一即可:

        死锁避免是在资源动态分配的过程中防止系统进入不安全状态。通常系统会维护一张资源分配表,在新请求进来时计算分配是否会进入不安全状态。典型的算法有银行家算法。
        如果系统在资源分配时不采取任何措施,则应该提供死锁检测和解除手段。系统死锁可以通过资源分配图来描述,当且仅当 $S$ 状态的资源分配图是不可完全简化的时候, $S$ 就是死锁。当检测出死锁的时候,就要采取相应的措施,主要方法有资源剥夺法:挂起某些死锁进程并释放它们持有的资源;撤销进程法:强制撤销部分、甚至全部死锁进程并释放它们的资源,可以按照优先级或者撤销代价的顺序进行;进程回退法:让一个或多个进程回退到足以回避死锁的状态,在回退的过程中进程会自愿释放资源,系统需要保持进程的历史信息并设置还原点。

3. 内存

        内存管理 ( $Memory\ \ Management$ ) 是操作系统设计中最重要和最复杂的内容之一。创建进程首先要将程序和数据装入内存,将用户源程序变为可在内存中执行的程序,通常需要以下几个步骤:

        程序的链接有三种方式:

        内存的装入模块在装入内存时同样有三种方式:

        在编译完成后,每个目标模块都是从 $0$ 号单元开始,称为该模块的相对地址(或逻辑地址)。当链接程序将各个模块链接为一个完整的可执行程序时,链接程序会顺序依次按照各个模块的相对地址构成同一个的从 $0$ 号单元开始编址的逻辑地址空间。物理地址空间是内存中物理单元的集合,它是地址转换的最终地址,进程在运行时执行指令和访问数据最后都要通过物理地址从主存中获取,将逻辑地址转换为物理地址的过程称为地址重定位。
        内存分配前,需要保护操作系统不受用户进程的影响,同时保护用户进程不受其他用户进程的影响。通过采用重定位寄存器和界地址寄存器来实现这种保护。重定位寄存器包含最小的物理地址值,界地址寄存器含逻辑地址值。每个逻辑地址值必须小于界地址寄存器,否则就会发生地址越界。如果未发生地址越界,就会加上重定位寄存器的值,映射成物理地址,再交由内存单元。当CPU调度程序选择进程执行时,派遣程序会初始化重定位寄存器和界地址寄存器。
        内存的分配方式有连续分配方式和非连续分配方式。连续分配方式指为一个用户程序分配一个连续的内存空间,包括:

        非连续分配允许一个程序分散地装入到不相邻的内存分区中,根据分区大小是否固定可以分为分段或者分页管理方式。在分页管理方式中,根据是否要将作业的所有页面都装入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。
        分页存储方式将内存空间划分为大小相等且固定的块,每个进程也以块为单位进行划分,进程在执行过程中以块为单位依次申请内存中的块空间。进程中的块称为页 ( $Page$ ),内存中的块称为页帧 ( $Page\ \ Frame$ ),外存也以同样的单位划分,直接称为块 ( $Block$ )。进程在执行过程中需要申请内存空间,就是为每个页面分配内存中可用的页帧。分页的地址结构包含两部分,页号和页偏移量。系统会为每个进程建立一张页表,一般存放在内存中,记录页号对应的内存中的物理块。系统中通常会设置一个页表寄存器 ( $PTR$ ),存放页表在内存的起始地址和长度,在进程执行时设置。在地址变换中通常还会设置一个具有并行查找能力的告诉缓冲存储器,称为快表或者联想寄存器 ( $TLB$ ),存放部分页表项。在设置了快表后,地址的转换过程会优先在快表中查找,如果没有找到,才会在页表中查找,并且会将这次查找结果存在快表中。由于页表存储在内存中,并且页面大小较小,所以会导致页表过大的问题,而且通常一个进程运行时只需要小部分的页面,由此提出了二级页表的概念。二级页表将一级页表的空间进行地址映射,即将一级页表划分为若干个等大的区域,这样在进程执行的过程中,只需要将二级页表映射的那一块页表区域调入内存即可。由二级页表进一步延伸,可以建立多级页表。
        分段存储方式按照用户进程中的自然段划分逻辑空间,每段从 $0$ 开始编址,并分配一段连续的地址空间(段内连续,段间不连续)。逻辑地址由段号和段偏移量组成。在分页系统中,逻辑地址的页号和页偏移量对用户透明,但在分段系统中,段号和段偏移量必须由用户显式提供,在高级语言中由编译器完成。每个进程都有一个逻辑空间与内存空间映射的段表,每个段表项对应进程的一个段,包括段号、段长和起始地址。为了实现从逻辑地址到物理地址的映射,系统中设置了一个段表寄存器,存放段表的起始地址和长度。在分段系统中,段共享是通过两个段表中相应表项指向被共享段的同一个物理副本实现的。
        段页式存储方式结合了分页和分段,首先将作业的地址空间分为若干个段,每个段都有自己的段号,然后再将段分为固定大小的页。内存的空间管理仍和分页存储方式一样,将其分为若干个固定大小的页帧。作业的逻辑地址分为三部分:段号、页号和页偏移量。系统为每个进程建立一张段表,每个分段有一张页表。系统中还有一个段表寄存器,记录段表起始地址和段表长度。
        在程序装入时,可以将程序的一部分装入内存,在执行过程中,当访问的信息不在内存时,再将它们调入内存。另一方面,操作系统也可以将内存中暂时不使用的内存换出到外存上。这样,操作系统好像提供了一个比实际大得多的内存,称为虚拟内存。虚拟内存需要建立在非连续分配的基础上,因此只适用于分段和分页存储管理方式。请求分页系统建立在基本分页系统的基础上,为了支持虚存而增加了请求调页和页面置换功能。为了支持请求分页,操作系统除了需要一定容量的内存和外存之外,还需要有页表机制、缺页中断机制和地址变换机制。
        请求分页系统在作业运行之前不要求调入全部内存,因此如何发现和解决缺页是一个基本问题。为此,页表项中新增了四个字段,分别为状态位,用于标识该页是否调入内存;访问字段,记录本页在一段时间内被访问的次数或者最近有多久未被访问;修改位:标识该页在调入内存后是否被修改;外存地址:通常是外存上的物理块号,用于调入页面时提供参考。每当要访问的页面在内存中不存在时,就会产生一个缺页中断,此时进程将会被阻塞。如果内存中存在空闲块,就会将页面装入该块,并修改页表,否则就会执行页面置换算法。常见的页面置换算法有:

        使用了虚拟内存技术后,进程不需要将所有页都读到内存。但是操作系统需要决定每个进程在内存中驻留的页面的数量,称为驻留集的大小。通常有三种策略:

        在调入页面的时候,除了只调入需要的页面外,系统也可以一次调入若干个相邻的页面,但是需要预测哪些页面会被使用。这种策略主要用于进程的首次调入,由用户指定调入页面。
        请求分页系统的外存可以分为文件区和对换区两个部分。对换区通常采用连续分配方式,文件区采用离散分配方式,因此对换区的I/O速度会更快。如果对换区空间足够,进程运行前可以把文件先从文件区复制到对换区;如果对换区空间不足,则优先将可能被修改的部分放入对换区;还可以使用UNIX方式,即将文件放在文件区,把运行过被换出的页面放入对换区。

4. 文件

        在系统运行时,计算机以进程为基本单位进行资源的调度和分配;而在用户进行I/O时,基本单位是文件 ( $File$ )。操作系统提供了文件系统 ( $File\ \ System$ ) 实现对文件的管理,如访问文件、修改文件、保存文件和删除文件等。文件的结构包括:

  1. 数据项:分为基本数据项和组合数据项,前者用于描述一个对象的某种属性的一个值,是原子数据;后者由多个基本数据项组成;
  2. 记录:记录是一组相关的数据项的集合,用于描述一个对象在某方面的属性;
  3. 文件:文件是创建者定义的一组相关信息的集合,逻辑上可分为有结构文件和无结构文件。有结构文件由一组相似记录组成,而无结构文件由字符流或者字节流组成。

        文件具有一定的属性,通常有:

        文件信息保存在目录结构中,目录结构保存在外存上,当需要使用时再调入内存。
        文件系统支持对文件进行一些基本操作:

        因为许多文件操作都涉及为给定文件搜索相关目录条目,所以许多系统要求在首次使用文件时通过系统调用 $open$ 将文件属性从外存拷贝到内存打开文件表 ( $open-file\ \ table$ ) 中,并将条目索引返回给用户。当用户需要文件操作时,通过索引可以直接访问指定文件,避免了搜索操作。通常,打开文件表中的条目还有一个文件打开计数器 ( $Open\ \ Count$ ),用于记录多少进程打开了该文件。当计数器为 $0$ 时,代表文件不再被使用,此时系统就会回收文件的内存空间,包括打开文件表中的对应条目,如果文件被修改过,还会将文件写回外存,最后释放文件的文件控制块 ( $File\ \ Control\ \ Block$, $FCB$ )。每个打开文件表的条目都有如下关联信息:

        文件的逻辑结构是从用户的角度出发看到的文件的组织形式,物理结构是从实现的角度出发看到的文件的组织形式,又称为文件的存储结构。按照逻辑结构,文件有无结构文件和有结构文件两种类型。无结构文件是最简单的文件组织形式,按照顺序组织成记录并累积保存,以字节或字符为单位,适用于对基本信息单位操作不多的文件,如源程序文件、目标代码文件等;有结构文件按记录的组织形式可以分为:

        文件目录包含文件有关的信息,包括属性、位置和所有权等,目录管理通过树形结构实现。为了实现目录管理,操作系统中引入了文件控制块。文件控制块是用来存放控制文件需要的各种信息的数据结构,FCB的有序集合就是文件目录,一个FCB就是一个文件目录项。每当创建一个新文件的时候,系统就会分配一个FCB并存放在文件目录中,成为文件目录项。FCB主要包括:

        在检索文件目录时,只需要使用文件名,因此有的系统,如UNIX,使用了文件名和描述信息分开的方法。文件描述信息单独形成一个称为索引结点的数据结构,简称为 $i$ 结点。文件目录的每个目录项由文件名和指向该文件对应的 $i$ 结点的指针形成。
        在文件目录上进行的基本操作包括:

        在操作时,需要考虑以下集中目录结构:

        在读取文件之前,必须先通过路径名找到对应的目录项。目录实现的基本方式有线性表和哈希表两种:

        文件共享使得多个用户可以共享同一文件,系统只需要保存文件的一份副本。如果系统不支持文件共享,那么就需要该文件的每个用户都拥有各自的副本。常用的两种文件共享方式有:

        文件保护通过口令保护、加密保护和访问控制等方式实现。其中,口令保护和加密保护是为了防止用户文件被他人存取或窃取,而访问控制则用于控制用户对文件的访问方式。对文件的保护可以从限制对文件的访问类型中出发,可以控制的访问类型主要有:读、写、执行、添加、删除和列表清单(列出文件名和文件属性)。此外还有重命名、复制、编辑等,这些高层功能可以通过低层系统调用实现,保护可以在低层提供。
        解决访问控制最常用的方法是根据用户身份进行控制,最普通的方法是为每个文件和目录增加一个访问控制列表 ( $Access-Control\ \ List$, $ACL$ ),规定每个用户名及其所允许的访问类型。优点是可以使用复杂的访问方法,缺点是长度无法估计,可能导致复杂的空间管理,精简的访问列表可以解决这个问题。精简的访问列表采用拥有者、组和其他三种用户类型,这样只需要使用三个域列出访问表中这三类用户的访问权限即可。拥有者在创建文件时,系统会将拥有者、所属组名列在FCB中。
        口令是指用户在建立文件时提供一个口令,系统在FCB上附上相应口令,用户请求访问时必须提供相应口令,优点是时间和空间开销低,缺点是口令存在系统内部,不够安全。密码则是用户对文件进行加密,用户访问时需要使用密钥,优点是保密性强,缺点是需要进行编码和解码,提高了访问开销。
        文件分配对应于文件的物理结构,指如何为文件分配磁盘块,常见的分配方式有:

        磁盘 ( $Disk$ ) 是由表面涂有磁性物质的金属或塑料构成的圆形盘片,通过一个称为磁头的导体线圈从磁盘中存取数据。磁盘的盘面上的数据存储在一组同心圆中,称为磁道,每个磁道与磁头一样宽。磁道又可以划分为几百个扇区,每个扇区固定存储大小 ( 通常为 $512B$ ),一个扇区称为一个块。相邻磁道及相邻扇区之间通过一定的间隙分开,避免精度错误。磁盘安装在磁盘驱动器中,由磁头臂、主轴和用于I/O的电子设备组成,多个盘片垂直堆叠,形成磁盘组,每个盘面对应一个磁头,所有磁头固定在一起,与磁盘中心距离相同且一起移动。扇区是磁盘可寻址的最小存储单位,磁盘地址使用柱面号、盘面号和扇区号表示。
        一次磁盘读写操作由寻道时间、延迟时间和传输时间决定。寻道时间指将磁头移到指定磁道所需的时间,延迟时间指磁头定位到某一磁道的扇区所需的时间,传输时间指从磁盘读出或向磁盘写入数据所经历的时间。常用的磁盘调度算法有:

        一个新的磁盘只是一个含有磁性记录材料的空白盘,在进行存储之前必须先分成扇区以便磁盘控制器能进行读写,这个过程称为低级格式化 ( 物理分区 )。每个扇区的数据结构通常由头、数据区域和尾组成,头尾包含了一些磁盘控制器所使用的信息。为了使用磁盘存储文件,操作系统还需要将自己的数据结构记录在磁盘上:第一步将磁盘分为由一个或多个柱面组成的分区,第二步对物理分区进行逻辑格式化,即创建文件系统。计算机启动时需要运行一个初始化程序,用于初始化CPU、寄存器、设备控制器和内存等,接着启动系统。初始化程序通常保存在ROM中,为了避免修改代码需要改变ROM的问题,通常在ROM中只保留很小部分,并将完整功能保存在磁盘的启动块上。启动块位于磁盘的固定位置上,拥有启动块的磁盘称为启动磁盘或者系统磁盘。

5. I/O

        设备管理的主要任务之一是控制设备和内存或处理机之间的数据传送,外围设备和内存之间的输入/输出控制方式有四种:

        Linux系统提供了 $5$ 种I/O处理模型:

操作系统笔记