操作系统 (OS; Operating System)
操作系统指控制和管理计算机系统的硬件和软件资源,并合理组织和调度计算机的作业和资源分配的程序的集合,是最基本的系统软件。操作系统的主要目标为实现方便性、有效性、可扩充性和开放性。
操作系统实现对计算机资源的抽象,提供用户与计算机硬件系统间的接口,其内核具有的两大功能如下:资源管理功能和支撑功能。资源管理功能指管理处理机、存储器、文件、设备等计算机系统资源;支撑功能的内容如下。
- 中断 (Interrupt):中断分为由外部设备引起的外中断,和来自 CPU 内部的内中断,又称陷入 (Trap),中断处理程序需要保存被中断进程的 CPU 环境并转入相应的设备处理程序,还需要恢复 CPU 现场,且这两个过程必须关中断;
- 时钟 (Clock):内核中有大量的函数都是基于时间驱动的;
- 原语 (Primitive):原语即由若干指令组成,用于完成一定功能的原子操作。
操作系统的主要功能如下:进程管理;存储器管理;I/O 管理;文件管理。
操作系统的基本特性如下。
- 并发 (Concurrence):多个事件在同一时间间隔内发生,对有限物理资源的强制性使用,进程的引入实现并发执行,极大提高资源利用率,增加系统吞吐量;
- 共享 (Sharing):系统中的资源可供内存中多个并发执行的进程共同使用,又称资源复用,共享的方式有互斥共享方式 (临界资源等) 和同时访问方式 (磁盘设备、磁盘文件等);
- 虚拟 (Virtual):通过某种技术将一物理实体变为若干逻辑对应物,利用设备为某个用户服务的空闲转去服务其他用户,以提高资源利用率,如时分复用技术 (虚拟处理机、虚拟设备等) 和空分复用技术 (虚拟磁盘、虚拟存储器等);
- 异步 (Asynchronism):进程推进的速度不可预知。
其中并发和共享互为条件,二者都是操作系统的最基本特性。
操作系统的两种处理机状态如下。
- 内核态 (Kernel Mode):运行操作系统程序,操作硬件,能访问所有的内存空间和对象,其所占有的处理器是不允许被抢占的;
- 用户态 (User Mode):运行用户程序,进程所能访问的内存空间和对象受到限制,其所处于占有的处理器是可被抢占的。
通常,用户态切换至内核态的途径有系统调用、异常和中断等;内核态切换至用户态可通过设置程序状态字 (PSW; Program Status Word) 的方式。
未配置操作系统的计算机采用人工操作的方式对计算机进行操作,用户独占计算机,且 CPU 等待人工操作,计算机资源利用率严重降低,即所谓人机矛盾。后来引入脱机输入/输出 (Off-Line I/O) 方式,即程序和数据的输入/输出是在脱离主机的情况下进行的,减少了 CPU 的等待时间,且提高了 I/O 速度。
操作系统的发展历程可分为批处理系统、分时系统、实时系统、网络和分布式系统等。
图形用户界面 (GUI; Graphical User Interface) 可使用户基于各种输入设备操控图形对象,而每种图形对象都对应一种计算机任务、指令或现实世界对象等。现在的计算机大部分都具有图形用户界面。
批处理系统 (Batch Processing System)
批处理系统可分为如下两类。
- 单道批处理系统 (Simple Batch Processing System):解决人机矛盾和 CPU 与 I/O 设备速度不匹配的矛盾,但系统资源得不到充分的利用;
- 多道批处理系统 (Multiprogramming Batch Processing System):资源利用率高,系统吞吐量大,但平均周转时间长且无交互能力。
分时系统 (Time-Sharing System)
分时系统使多个用户通过各自终端以共享使用一台计算机。分时系统实现的关键问题如下:及时接收,措施如在系统中设置多路卡,用缓冲区暂存命令;及时处理,措施如作业直接进入内存,分短时间片轮转运行。
实时系统 (Real-Time System)
实时系统可及时响应外部事件,在规定的时间内完成对该事件的处理,并控制所有实时任务协调一致地运行。实时系统的进程调度,通常抢占式优先级高者优先。
实时任务可分为如下两类:允许失误的软实时系统 (Soft Real-Time System);较为严格的硬实时系统 (Hard Real-Time System)。
进程管理 (Process Management)
多任务处理操作系统的必要功能。
进程 (Process)
进程即系统进行资源分配和调度的独立单位。进程的特征如下:进程具有动态性,即进程的实质是进程实体的执行过程,有别于程序的静态性;进程具有并发性,即多个进程实体同存于内存中,且能在一段时间内同时运行;此外进程还具有独立性和异步性。
进程的基本状态如下。
- 新生 (New);
- 就绪 (Ready):分配到除 CPU 外的所有必要资源;
- 执行 (Running):已获得 CPU,正在运行;
- 阻塞 (Blocked):又称等待 (Waiting),即等待某一事件而无法执行;
- 终结 (Terminated)。
进程控制块 (PCB; Process Control Block) 描述一个进程及其与其他进程和系统资源的关系,是用于刻画一个进程在各个时期所处状态的数据结构。进程控制块是进程存在于系统的唯一标识。
进程控制块记载的内容如下:进程标识符,即由创建者提供的外部标识符和整数的内部标识符;处理机状态,包括通用寄存器 (用于在中断时保存现场)、程序计数器、程序状态字和用户栈指令等;进程调度信息;进程控制信息。
进程实体包含进程控制块,程序段和数据段。
进程控制是进程管理中最基本的功能,一般由操作系统内核中的原语实现。
进程控制的相关原语
进程控制的相关原语如下。
- 创建 (Create):申请空白 PCB 并分配资源和初始化,插入就绪队列;
- 终止 (Destroy):检索 PCB,结束并置调度标志为真,终止其子孙进程,归还资源给父进程或系统,最后将 PCB 从所在队列中移除;
- 阻塞 (Block):由于 I/O 请求、申请缓冲区失败等原因释放 CPU,阻塞的进程仍处于内存中;
- 唤醒 (Wakeup):撤销阻塞状态;
- 挂起 (Suspend):由于负荷调节的需要等原因释放 CPU,挂起的进程通过「对换」技术被换出;
- 激活 (Active):撤销挂起状态。
临界资源 (Critical Resources) 又称独占资源,指一段时间内只允许一个进程访问的资源,如某些物理设备 (打印机、磁带机等),以及栈、变量等。临界区 (Critical Section) 则是访问临界资源的代码片段。
中断屏蔽 (Interrupt Mask) 或称关中断,是当一个进程正在使用临界资源时,防止其他进程再进入临界区访问的最简单方法。中断屏蔽的缺点如下:易被滥用;长时间中断屏蔽将影响效率;不适用于多处理机系统下对临界资源的互斥访问。
进程间通信 (IPC; Inter-Process Communication) 即至少两个进程间传送数据或信号的一些技术或方法。为协调进程间的相互制约关系,引入进程同步 (Process Synchronization) 的概念,即令并发执行的进程按一定规则共享系统资源,使程序执行具有可再现性。
主要的 IPC 方法如下:文件 (File);信号量 (Semaphore);管道 (Pipe);管程 (Monitor);共享存储器系统 (Shared-Memory System);消息传递系统 (Message Passing System)。其中,信号量机制由戴克斯特拉提出,是卓尔有效的进程同步工具,包括如下部分。
- P(Proberen):P 原语表示「尝试」,即申请资源;
- V(Verhogen):V 原语表示「升高」,即释放资源。
互斥锁 (Mutex) 是防止同时访问共享资源的程序对象,用于实现对临界资源的独占式处理,是特殊的二值型信号量。可见互斥是同步的特殊情况。
信号量机制的改进
计数信号量 (Counting Semaphore) 又称整型信号量,使用 s
表示资源数目,P 原语的部分可用如下两段操作类比。
而 V 原语的部分即与如下操作类似。
此外,可在计数信号量的基础上,加入进程链表连结所有阻塞进程以实现记录。此时,P 原语的部分类似如下操作。
1 2
| s->value--; if(s->value < 0) block(s->list);
|
V 原语的部分类似如下操作。
1 2
| s->value++; if(s->value <= 0) wakeup(s->list);
|
二进制信号量 (Binary Semaphore) 又称与型信号量,s
的取值只有 0 和 1,即将进程在整个过程中需要的所有资源一次性分配。
信号量集 (Semaphore Set) 的改进即多个信号量的集合,且增设对资源的需求值和资源的分配下限。
管程机制中,使用条件变量 (Conditional Variable) 以区别不同的等待原因。令 x
为条件变量的记号,则 x.wait()
的形式将调用此原语的进程阻塞于 x
条件队列,而 x.signal()
即唤醒 x
中的队首进程。
信号量机制和管程机制的对比
信号量机制和管程机制的对比如下。
信号量机制 |
分散式同步机制: 共享变量、信号量操作分散在 整个系统或各个进程中 |
高效且灵活 |
可读性差、正确性不易保证 且不易修改 |
管程机制 |
集中式同步工具: 共享变量及相关操作集中在 同一个模块中 |
可读性好、正确性可保证 且易于修改 |
不甚灵活、效率略低 |
经典的 IPC 问题及其基于信号量的解答如下。
生产者-消费者问题 (Producer-Consumer Problem):又称有限缓冲问题 (Bounded-Buffer Problem),描述共享固定大小缓冲区的两个进程在实际运行时的情况,注意下述解答的头两行 P()
语句不能颠倒位置,否则可能引起死锁;
1
| Semaphore empty = N, full = 0, mutex = 1;
|
1 2 3 4 5
| P(empty); P(mutex);
V(mutex); V(full);
|
1 2 3 4 5
| P(full); P(mutex);
V(mutex); V(empty);
|
读者-写者问题 (Reader-Writer Problem):描述多个进程尝试访问同一个共享资源的情况,下述是「读者优先」的解答,此外,独木桥问题是读者-写者问题的衍生,可转换为两类读者的问题;
1 2
| Semaphore mutex = 1, c_mutex = 1; int counter = 0;
|
1 2 3 4 5 6 7 8 9
| P(c_mutex); if(counter == 0) P(mutex); counter++; V(c_mutex);
P(c_mutex); counter--; if(counter == 0) V(mutex); V(c_mutex);
|
睡眠理发师问题 (Sleeping Barber Problem):由戴克斯特拉提出,其解决的关键是互斥锁。
1 2 3
| #define N 5 Semaphore mutex = 1, customer = 0, barber = 0; int waiting = 0;
|
1 2 3 4 5 6 7 8 9
| P(mutex); if(waiting < N) { waiting++; V(customer); V(mutex); P(barber); } else { V(mutex); }
|
1 2 3 4 5
| P(customer); P(mutex); waiting--; V(barber); V(mutex);
|
线程 (Thread)
线程是调度的最小单位,会被频繁地调度和切换。引入线程旨在减少程序并发执行时所付出的时空开销,使得并发粒度更细,并发性更好。
C++11 的线程可见此处。
线程的实现方式如下。
- 内核支持线程 (KST; Kernel Supported Thread):又称内核线程,是轻量级进程 (LWP; Light Weight Process);
- 用户级线程 (ULT; User Level Thread):又称用户线程,用户进程中的一个实体,内核意识不到用户线程的存在。
用户线程与内核线程的组合方式,即多线程模型 (Multithreading Model) 的实现方式如下。
- 多对一模型 (Many-to-One Model):将用户线程映射到一个内核线程,若一个线程在访问内核时阻塞,则整个进程都会阻塞;
- 一对一模型 (One-to-One Model):将每一个用户线程映射到一个内核线程,并发功能更好,但创建一个用户线程就要创建一个相应的内核线程,开销大;
- 多对多模型 (Many-to-Many Model):将许多用户线程映射到同样数量或更少数量的内核线程,若一个线程阻塞,内核可调度至另一线程执行。
调度 (Scheduling)
调度即分配所需资源的方法,进行调度工作的程序称调度器 (Scheduler)。
批处理系统环境中,进程又称为作业 (Job),一个比程序更广泛的概念,包含程序、数据和作业说明书;分时系统环境中,进程又称为任务 (Task)。批处理系统环境是以作业为基本单位由辅存调入内存的。
处理机调度的层次即调度器的类型如下。
- 高级调度 (High Level Scheduling):又称长程调度或作业调度,决定辅存中的哪些作业调入内存,主要用于多道批处理系统,而分时、实时系统中不设置;
- 低级调度 (Low Level Scheduling):又称短程调度或进程调度,决定就绪队列中的哪个进程获得处理机,是最基本的一种调度,操作系统必须配置;
- 中级调度 (Intermediate Scheduling):又称内存调度,将暂时不运行的进程挂起以提高内存利用率。
处理机调度算法的共同目标如下:资源利用率;公平性,即避免「饥饿」现象;平衡性,即使处理机和各种外设能经常忙碌;策略强制执行。
调度算法汇总
调度算法总结如下。
- 先来先服务 (FCFS; First-Come First-Served):非抢占的调度方式,系统开销最小,有利于长作业和处理机繁忙的作业,但响应时间可能很高、不利于短作业和倾向 I/O 的进程;
- 短作业优先 (SJF; Short Job First):非抢占的调度方式,平均周转时间最短,有利于短作业而不利于长作业,但必须预知作业运行时间,人机无法交互且未考虑作业紧迫程度;
- 最高响应比优先 (HRRN/HRN; Highest Response Ratio Next):非抢占的调度方式,其中响应比属动态优先权,定义为响应时间和要求服务时间之比,而响应时间为等待时间与要求服务时间之和,HRRN 可兼顾长短两种作业,但每次调度必须计算响应比,显然会增加系统开销;
- 时间片轮转 (RR; Round Robin) 是抢占的调度方式,相对公平,且短时间片有利于短作业,但不能保证及时响应,时间片轮转算法的关键是时间片长短的选择,时间片太短将增加系统开销,而时间片太长算法将退化为 FCFS;
- 最高优先权优先 (HPF; Highest Priority First) 是抢占的调度方式,可使紧迫型作业能得到优先处理,其中优先级可分为静态优先级和动态优先级两种类型;
- 多级反馈队列 (Multilevel Feedback Queue) 是抢占的调度方式,有利于倾向 I/O 的进程且不必估计进程执行时间,可满足终端型用户和长、短批处理作业用户的需要。
实时调度 (Real Time Scheduling) 使用的方法有最早截止时间优先 (EDF; Earliest Deadline First) 和最低松弛度优先 (LLF; Least Laxity First) 等。其中松弛度 (Laxity) 是任务紧急的程度,定义如下。
松弛度 必须完成时间 任务本身运行时间 当前时间
周转时间 (TAT; Turn-Around Time) 指从作业提交至作业完成的时间间隔。平均周转时间 (ATT; Average Turn-Around Time) 常用于评估处理机调度算法的性能优劣。
死锁 (Deadlock)
两个或两个以上的进程因竞争彼此资源而造成的阻塞现象,一组死锁的进程中,每一进程都在等待只有其他进程才能引发的事件。竞争不可抢占资源或可消耗资源、进程推进顺序不当等,都是产生死锁的原因。
预防死锁需要破坏死锁的四个必要条件之一,内容如下。
- 互斥 (Mutual Exclusion):该条件无法破坏;
- 保持和请求 (Hold and Wait):当一个进程在请求资源时,不能持有不可抢占的资源;
- 不可抢占 (No Preemption):当一个进程提出新的资源请求不能满足时,必须释放已持有的所有资源;
- 循环等待 (Circular Wait):对所有类型资源线性排序,规定每个进程必须按序号顺序请求资源。
对于破坏保持和请求的条件,有如下两种协议:一次申请运行所需的全部资源,但会使资源严重浪费,且进程经常发生「饥饿」现象;允许一个进程只获取运行初期所需的资源,便能够开始运行,是对第一种协议的改进。
对于破坏不可抢占的条件,可规定当提出新的资源请求不能满足时,必须释放已保持的所有资源。
对于破坏循环等待的条件,可对所有类型资源线性排序,规定每个进程必须按序号顺序请求资源。
银行家算法 (Banker's Algorithm) 是避免死锁的著名算法,由戴克斯特拉提出。银行家在客户申请的贷款数量不超过自己拥有的最大值时,都应尽量满足客户的需要。在银行家算法中,银行家就好比操作系统,资金就是资源,客户就相当于要申请资源的进程。
安全状态 (Safe State) 指系统能按某种推进顺序,为每个进程分配资源,直至满足每个进程对资源的最大需求,使每个进程都可顺利完成。银行家算法在资源分配前进行判断,若分配不会使系统处于不安全状态,才进行资源分配。
检测死锁利用死锁定理,即一组进程为死锁的充分条件是,当且仅当该组进程的资源分配图不可完全化简,即不能使所有进程结点都孤立。解除死锁的方式有剥夺资源和撤销资源分配的进程等。
存储器管理 (Memory Management)
对计算机内存资源的分配和使用的技术,其功能如下:内存空间的分配与回收;逻辑地址到物理地址的转换;内存空间的扩充,即虚拟内存的应用;存储保护,即防止内存地址越界。
程序的执行需要经过编译、链接和装入等步骤。其中装入 (Loading) 即将模块置于主存。程序的装入可分为如下几种方式。
- 绝对装入 (Absolute Loading):编译后即产生物理地址;
- 可重定位装入 (Relocation Loading):即静态重定位,地址变换在装入时一次完成;
- 动态运行时装入 (Dynamic Run-Time Loading):即动态重定位,增设重定位寄存器,使地址变换在程序真正执行时才进行。
程序的链接可分为如下几种方式。
- 静态链接 (Static Linking):事先链接且不再拆开;
- 装入时动态链接 (Load-Time Dynamic Linking):装入时链接;
- 运行时动态链接 (Run-Time Dynamic Linking):将某些模块的链接推迟至程序执行时。
连续分配方式汇总
连续分配方式总结如下。
- 单一分区 (Single Partition):内存划分为系统区和用户区,可使用后者全部空间,是最简单的连续分配方式,适用于单用户、单任务的操作系统,只有分配和回收两种操作,易于管理,但极易造成内存浪费;
- 固定分区 (Fixed Partition):在系统初启时将内存划分为若干分区,分区大小可以各不相等,可通过分区说明表实现,易于实现且开销小,但会产生内存碎片造成浪费,且分区总数固定会限制并发执行的程序数目;
- 动态分区 (Dynamic Partition):装入时建立分区,根据作业需求分配大小,可通过分区空闲表、空闲分区链和请求表实现,在其基础上引入「紧凑」技术,即可移动内存中作业的位置,将原来多个小分区拼接为大分区,称为可重定位分区 (Relocatable Partition),可重定位分区消除内存碎片,提高内存利用率,但提高了硬件成本,且「紧凑」时花费处理机时间。
动态分区分配算法汇总
动态分区分配算法总结如下。
- 首次适应 (FF; First Fit):空闲分区链按首地址递增的顺序组织,释放存储区不改变空闲区在表中的位置,且能保证高地址空间的空闲较大,但低地址空间容易产生碎片,进而降低主存空间利用率;
- 循环首次适应 (NF; Next Fit):由 FF 演变而来,从上次分配的分区起查找,可通过设置起始查询指针实现,可使空闲区分配更均匀,从而减少查询时的开销,但会导致缺乏较大的空闲区;
- 最佳适应 (BF; Best Fit):空闲分区链按容量递增的顺序组织,不至于浪费较大的空闲区,但分配后残余空闲区总是最小的,因此会留下许多碎片;
- 最坏适应 (WF; Worst Fit):空闲分区链按容量递减的顺序组织,查询效率高,分配后残余空闲区可能大,且不会有很多碎片,但会分割大的空闲区。
离散分配方式有分页存储管理、分段存储管理和段页式存储管理 (先分段再分页,各取所长)。
页 (Page)
页是进程逻辑地址空间,块 (Block) 与之大小相同,但是内存物理地址空间。页内碎片即进程最后一页装不满一块形成的不可利用的碎片。
页表 (Page Table) 是一种数据结构,实现「页号-物理块号」的地址映射,转换进行的场所成为地址变换机构。系统为每一进程建立一个页表,页表的长度和首地址存于 PCB 中。占用 CPU 的进程,其页表必须驻于内存。
有效访问时间 (EAT; Efficient Access Time) 指从发出访问请求至取出数据的时间,计算式如下。
其中,为一次内存访问所需的时间。
快表 (TLB; Translation Lookaside Buffer) 又称页表缓存或转译后备缓存,是 CPU 的一种缓存,用于改进逻辑地址到物理地址的转译速度。引入快表后,有效访问时间的计算式如下。
其中:为一次内存访问所需的时间;为查找快表的时间;为命中率。
页的总结如下:页数是信息的物理单位,分页是系统管理的需要;页的大小固定且由系统决定;分页的作业地址空间是一维的,只需一个记忆符即可表示一个地址;分页有内部碎片,无外部碎片;分页不易实现共享和动态链接。
段 (Segment)
段是作业按逻辑关系的划分。段可有数据段 (DS; Data Segment) 和代码段 (CS; Code Segment) 等。
段的总结如下:段是信息的逻辑单位,分段是用户的需要;段的长度不固定且取决于程序;分段的作业地址空间是二维的,需要给出段名和段内地址;分段有外部碎片,无内部碎片;分段容易实现共享和动态链接。
虚拟内存 (Virtual Memory)
虚拟内存只适用于离散分配技术,属于高速缓存技术,基于局部性原理。装入时,只需装入一部分就可以启动;执行时,当访问的信息不在内存,则由操作系统将其调入内存,将暂时不用的程序和数据换出至外存,即对换 (Swapping)。对换根据执行的基本单位不同可有如下类型:进程;页;段。
文件区占磁盘空间的大部分,访问频率低,采用离散分配方式;而对换区占磁盘空间的小部分,操作频率高,采用连续分配方式。
虚拟内存的三大特征为多次行、对换性和虚拟性。多次性是最重要的特征,多次性和对换性建立于离散分配的基础上,多次性和虚拟性则以对换性为基础。
页面置换算法汇总
页面置换算法总结如下。
- 最佳置换算法 (OPT; Optimal):可保证最低的缺页率,但需要预知调入页,是无法实现的算法,但可作为衡量优劣的标准;
- 先进先出 (FIFO; First In First Out):可通过总指向内存中最早调入页面的替换指针实现,会产生贝莱迪异常 (Belady's Anomaly),即物理页数增多反而缺页率上升的现象,原因是 FIFO 的置换特征与进程访问内存的动态特征是矛盾的;
- 最近最久未使用 (LRU; Least Recently Used):可通过位移寄存器实现,访问物理块时将对应寄存器最高位置 1,每隔一定时间右移,淘汰最长时间未使用的页面即淘汰位移寄存器中值最小的;
- 最少使用 (NFU/LFU; Not/Least Frequently Used):同样通过位移寄存器实现,但淘汰一定时间内是用最少的页面,即淘汰位移寄存器中置 1 位最少的;
- 时计 (Clock):又称最近未使用 (NRU; Not Recently Used) 算法,是 LRU 和 FIFO 的折衷,通过判断访问位决定淘汰页面,访问位为 1 时置 0,访问位为 0 时淘汰,将各页面的访问位连结为环形链表,重复修改、后移而实现,改进型的时计算法考虑修改位,以尽量淘汰未被修改的页面。
抖动 (Thrashing) 指从内存中换出某页,又请求换入改页。预防抖动的方式如下:采用局部置换策略;将工作集 (在时间间隔内进程要访问的页面的集合) 算法融入处理机调度;利用准则调节缺页率 (为缺页之间的平均时间;为平均缺页服务时间);选择暂停优先级最低的进程。
I/O 管理 (I/O Management)
I/O 设备的控制方式如下。
- 轮询 (Polling);
- 中断 (Interrupt);
- 直接存储器访问 (DMA; Direct Memory Access) 方式:设备和内存间的数据通路可使成块地传送数据而无需处理机的干预,提高了 CPU 利用率;
- I/O 通道 (I/O Channel):又称 I/O 地址 (I/O Address),是 I/O 专用的特殊处理机,具有执行 I/O 指令的能力,该方式是 DMA 方式的发展,可进一步减少处理机的干预。
设备无关性 (Device Independence) 将逻辑设备名映射至物理设备名,通过逻辑设备表 (LUT; Logical Unit Table) 实现。
假脱机技术 (SPOOLing; Simultaneous Peripheral Operating Online) 是指在联机情况下实现的同时外围操作,将独占设备改为共享设备,可提高 I/O 速度,实现虚拟设备功能。
文件管理 (File Management)
操作系统引入文件管理的目的是实现对文件的「按名存取」。
文件 (File) 是由创建者定义的,具有文件名的一组有逻辑意义信息的相关元素的集合。文件控制块 (FCB; File Control Block) 是用于描述和控制文件的数据结构,是文件存在的标识,包括文件基本信息、存取控制信息和使用信息等。
文件目录 (File Directory) 即文件控制块的有序集合,是文件名与辅存空间中物理地址的对应关系。打开文件的操作即将指定的文件目录内容复制到主存的活动文件表。
计算机存储文件之前,首先需要将存储介质格式化 (Formatting),以将盘片划分为轨道,进一步将轨道分为扇区,或称为簇。文件的不同部分分散在不相邻的簇中,通常会导致驱动器性能下降,碎片整理 (Defragment) 重新排列磁盘的文件以使它们存储在相邻的簇中,进而使驱动器恢复最佳性能。