操作系统
操作系统
一、 操作系统概述
操作系统定义：是计算机系统最基本、最重要的系统软件，是其它软件的支撑软件。它控制和管理计算机系统的硬件和软件资源，合理组织计算机工作流程，并为用户使用计算机提供公共的和基本的服务。它有以下两个主要目标：
高效性：操作系统允许以更加高效的方式使用计算机系统资源。
方便性：操作系统使得用户使用计算机更加方便
计算机系统的组成：
运算器、存储器、控制器、输入设备，输出设备
操作系统与计算机系统：
单用户操作系统—>具有并行能力的计算机系统
操作系统的发展过程：
简单计算机系统（无操作系统）、单道批处理系统、多道批处理系统、分时系统、实时系统
单道批处理系统
单道程序工作示意图
多道程序工作示意图
操作系统的主要功能：
处理机管理
存储管理
设备管理
文件管理
用户接口
处理机管理：
进程控制：基本功能是创建和撤销进程、控制进程状态之间的转换
进程同步：进程同步是指系统对并发执行的进程进行协调，使它们能有条不紊的运行
进程通信：进程通信是指相关进程之间的信息交换
进程调度：指按照一定的调度算法在等待执行的进程中选出其中一个，并为其分配CPU、设置运行环境，使其投入运行
存储管理：
内存分配：为每道程序分配必要的内存空间，提高存储器的利用率，减少空间浪费，在实现内存分配时，可采取静态和动态两种方式
内存保护：内存保护的主要任务是确保每道程序都只在自己的内存空间里运行，防止因一道程序的错误而干扰其它程序，也绝不允许用户程序随意访问操作系统的程序和数据
地址映射：把目标程序中的逻辑地址转换成为内存空间中的物理地址
内存扩充：内存扩充是借助虚拟存储技术，在不增加物理内存空间的前提下，从逻辑上对内存进行扩充，使系统能够运行内存需求量比实际内存更大的作业，或是让更多的作业能够并发执行
设备管理：
缓冲管理：缓冲是指在内存中划出来用作暂时存放信息的一部分区域。在CPU和I/O设备之间设置缓冲区，则可以有效缓解速度不匹配的矛盾，提高CPU的利用率，从而提高系统吞吐量
设备分配：根据用户所请求的设备类型、数量，按照一定分配算法对设备进行分配
设备处理：设备处理程序又称为设备驱动程序，其基本任务是由CPU向设备控制器发出I/O命令，启动指定的I/O设备、完成用户规定的I/O操作，并对设备发来的中断请求进行及时响应和处理。
虚拟设备管理：虚拟设备也称逻辑设备，是指操作系统通过设备虚拟技术，把每次仅供一个进程使用的独享设备改造成能被多个用户使用的设备
文件管理 ：
文件存储空间管理：一些当前需要使用的系统文件和用户文件，都必须放在可随机存取的磁盘上。为此，必须由操作系统统一对文件的存储空间进行管理，提高存储空间的利用率，同时也提高文件系统的存取速度
目录管理：目录又称文件目录，是用来描述系统中所有文件基本情况的一个表。为了使用户能够方便的在外存上找到自己所需的文件，系统会为每个文件建立一个目录项。在不同的系统中，目录有着不同的组织方式
文件读写管理：对文件进行读写操作，是文件管理必须具备的最基本的操作。该功能可以根据用户的请求，从外存指定区域把指定数量的信息读入到内存指定的用户区或系统区，或将指定数量的信息从内存写入外存指定区域。
文件保护：为了防止系统中的文件被非法窃取和破坏，必须提供有效的存取控制机制
文件系统的安全性：是指文件系统避免因软件或硬件故障而造成信息破坏的能力
用户接口：
命令接口：为了便于用户直接或间接控制自己的作业，操作系统向用户提供了命令接口。用户可以通过该接口向作业发出命令，以控制作业的运行。
程序接口：该接口是为用户程序在执行过程中访问系统资源而设定的，是用户程序取得操作系统服务的唯一途径。程序接口是由一组系统调用组成，每当应用程序要求操作系统提供某种类型的服务时，便调用具有相应功能的系统调用。
图形接口：采用图形化的操作界面，用非常容易识别的图标将系统的各种命令直观、逼真的表示出来，用户通过简单的点击鼠标，借助菜单、对话框，就可以完成对应用程序和文件的操作，极大的方便了用户的使用。
操作系统结构：
单体、模块化、可扩展内核、层次结构
操作系统的特性 ：并发、共享、虚拟和异步
并发性：是指在一段时间内有多道程序同时在计算机内运行
共享性：互斥共享，是指该类资源的分配必须以作业（或进程）为单位，在一个作业（或进程）没有运行完之前，另一个作业（或进程）不得使用该类资源；“同时”共享，是指多个作业（或进程）可“同时”使用该类资源，这里的“同时”和并发性中的“同时”有着相同的含义
虚拟性：操作系统的虚拟性是指操作系统使用某种技术，将物理上的一个资源或设备变成逻辑上的多个资源或设备。虚拟出来的东西不过是用户的“错觉”，并不是客观存在的东西
异步性：操作系统的异步性又称之为不确定性，不是说操作系统本身的功能不确定，也不是说在操作系统控制下运行的用户程序的结果是不确定的。异步性指在操作系统控制下的多个作业的执行顺序和每个作业的执行时间是不确定的，即进程是以人们不可预知的速度向前推进
操作系统的新特征：微内核体系结构、多线程、对称多处理、分布式操作系统、面向对象设计
二、中断
中断的基本概念
所谓中断，就是指CPU在执行一个程序时，对系统发生的某个事件（程序自身或外界的原因引起的）会做出的一种反应，即CPU暂停正在执行的程序，保留当前程序的运行现场后自动转去处理相应的事件，处理完该事件后，又返回到之前的程序断点，继续执行被中断的程序。
中断的特点：随机性、可恢复性、自动性
中断优先级：硬件故障中断>自愿性中断>程序性中断>外部中断>输入/输出中断
中断的响应过程
- 发现中断源
保护和恢复现场：现场是指在中断的那一时刻能确保程序继续运行的有关信息。 为了确保被中断的程序能从恢复点继续运行，必须在该程序重新运行之前，把保留的该程序的现场信息从主存中送至相应的各个寄存器当中，把完成这些工作称为恢复现场。
中断响应：中断响应是当CPU发现已有中断请求时，终止现行程序的执行，并自动引出中断处理程序的过程。 当发生中断事件时，中断系统必须立即将程序断点的现场信息存放到主存约定单元进行保存，用于中断返回时恢复现场使用。中断响应的实质就是交换用户程序和相应中断处理程序的指令执行地址和处理器状态，以达到保存断点和自动执行中断处理程序的目的。
中断的处理过程
保护现场和传递参数
对现场进行保护，包括对断点的保护和对通用寄存器以及状态寄存器的保护。
执行相应的中断服务程序
针对响应的中断事件，执行处理该事件的中断服务程序。
恢复现场并退出中断
执行完中断处理程序，系统要返回到之前的断点处继续执行，所以要将先前保存的断点信息重新加载进系统的各个寄存器当中，并将中断屏蔽字还原，这一过程称为恢复现场。
三、 进程和线程
程序的顺序执行及其特征：
通常可以把一个应用程序分成若干个程序段，各程序段之间必须按照某种先后次序顺序执行，仅当前一程序段（操作）执行完后，才能执行后继程序段（操作）。
特征：顺序性、封闭性、可再现性
程序的并发执行及其特征：
为了提高计算机的利用率、处理速度和系统的吞吐量，并行处理技术和并发程序设计技术在计算机中已经得到了广泛应用，成为了现代操作系统的基本特征之一。
特征：异步性、失去封闭性、不可再现性
进程的概念及其特征：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
程序和进程之前的区别和联系：
程序是完成特定任务的一组指令的结合，可以永久保存，具有静态性；
进程是程序在某一数据结构上的一次执行过程，是系统进行资源分配和调度的基本单位，具有动态性；
一个进程可以包含多个程序，一个程序也可以被多个进程执行。
进程状态：
两状态模型
包含运行态（Running）和非运行态（Not running）两种进程状态
创建了一个新进程之后，它会以非运行态加入到系统中，等到操作系统为其分派处理器
当前处于运行态的进程会不时地中断，由系统中的分派器选择处于非运行状中的某一个进程运行
五状态模型
包括就绪态（Ready）、运行态（Running）、阻塞态（Blocked）、新建态（New）和终止态（Terminate）
进程状态描述：
（1）新建态：刚刚创建的新进程，通常是指进程控制块已经创建，但还没有加载到系统内存中的进程。
（2）就绪态：进程等待系统为其分派处理器，而此时处理器被其它进程占据，所以该状态进程不能执行，但已经具备了除处理器之外的进程执行所需要的所有条件。
（3）运行态：进程已获得所需资源并占据处理器，处理器正在执行该进程。
（4）阻塞态：也称为等待态、挂起态或睡眠态，进程在等待某个事情的发生而暂时不能运行，例如等待某个I/O操作的完成。
（5）终止态：进程或者因为执行结束或者因为被撤销而从可执行进程组中退出。
引入挂起状态
对于内存中的多个进程，处理器依次选中运行，当一个进程正在等待I/O事件发生时，处理器转移到另一个进程。但是，处理器的速度比I/O要快很多，有可能内存中所有进程都在等待I/O事件的完成，导致处理器处于空闲状态。
引入挂起（Suspend）的概念：内存中没有就绪的进程时，系统将内存中处于阻塞的进程换出到外存中的挂起队列，而将外存中的就绪进程激活，换入到内存
进程控制块
进程控制块（Process control block, PCB）是操作系统用来记录进程状态和相关信息，控制进程运行的数据结构，是进程的唯一标识符
进程控制
进程控制是进程管理中最基本的功能
在操作系统中，不同功能都是通过执行各种原语（Primitive）操作实现
原语是由若干条指令构成、可完成特定功能的程序段
线程简介
在操作系统中引入进程的目的，是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量。
在操作系统中再引入线程，则是为了减少程序在并发执行时所付出的时空开销，使操作系统具有更好的并发性。
通常把调度和分派的基本单位称做线程或轻量级进程（Light weight process, LWP）,而把资源分配的基本单位称做进程或者任务。
多线程
进程在任一时刻只有一个执行控制流，通常将这种结构的进程称为单线程进程（Single threaded process）。
多线程进程（Multiple threaded process）——同一进程中设计出多条控制流，并且满足：
（1）多控制流之间可以并行执行；
（2）多控制流切换不需通过进程调度；
（3）多控制流之间可以通过内存直接通信联系，从而降低通信开销。
线程实现与线程模型
用户级线程（User level thread, ULT）
线程管理的所有工作都由应用程序完成，内核意识不到线程的存在。
内核级线程（Kernel level thread, KLT）
线程管理的所有工作都是由内核完成，应用程序并没有参与其中。即无论是用户进程中的线程，还是系统进程中的线程，他们的创建、终止和切换等也是依靠内核，在内核空间实现的。
组合方式
同一个进程内的多个线程可以同时在多处理器上并行执行，而且一个线程被阻塞时，同一进程内的其它线程可以调度运行，并不需要阻塞整个进程。所以，组合方式多线程机制能够结合KLT和ULT两者的优点，并克服了其各自的不足。
线程模型
多对一模型
一对一模型
多对多模型
并发原理：临界资源、临界区等多种术语
临界区：是一段程序代码，进程将在此代码中访问共享的资源，当另一个进程已经在该代码中运行时，则该进程不能在这段代码中执行
竞争 ：多个进程在访问一个共享数据时，结果依赖于它们执行的相对时间，这种关系称为竞争
同步：系统中有一些相互合作、协同工作的进程，它们之间的相互联系称为进程的同步
互斥：多个进程因争用临界区内的共享资源而互斥的执行，即当一个进程在临界区访问共享资源时，其它进程不能进入该临界区访问任何共享资源
死锁：两个或两个以上的进程因其中的每个进程都在等待其它进程执行完毕而不能继续执行，这样的情形称为死锁
饥饿：是指一个可运行的进程虽然能继续执行，但被调度程序无限期的忽视而不能执行的情况
硬件同步
TestAndSet指令实现互斥的示例如下： |
信号量机制
整型信号量
Dijkstra把整型信号量s定义成一个用于表示资源数目的整型变量。进程通过信号量传送信号，利用两个特殊的操作发送和接收信号。
signal(s)：通过信号量s传送信号
wait(s)： 通过信号量s接收信号
如果相应的信号仍然没有发送，则进程被挂起，直到发送完为止。
wait()操作定义如下 |
记录型信号量
整型信号量机制没有满足让权等待的原则，可能使进程处于饥饿的忙等状态。
假设s为一个记录型数据结构，其中一个分量为整形量value，另一个为信号量队列queue。value通常是一个具有非负初值的整型变量，queue是一个初始状态为空的进程队列，当一个进程必须等待信号量时，就加入到进程队列中去。
wait和signal操作定义如下：
wait(s)：信号量s减l，若结果小于0，则调用wait(s)的进程被设置成等待信号量s的状态。
signal(s)：将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程。
记录型信号量数据结构定义如下： |
二元信号量
假设s为一个记录型数据结构，其中一个分量为value，它仅能取值0和1，另一个分量为信号量队列queue。
一个二元信号量的值只能是0或者1
typedef struct{ |
利用信号量实现进程互斥
多个进程互斥地访问某临界资源，只需为该资源设置互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区置于wait(mutex)和signal(mutex)操作之间即可。
Semaphore mutex = 1; |
利用信号量实现前趋关系
还可利用信号量来描述程序或语句之间的前趋关系。设有两个并发执行的进程P1和P2。P1中有语句S1；P2中有语句S2。我们希望在S1执行后再执行S2。为实现这种前趋关系，只需使进程P1和P2共享一个公用信号量S，并赋予其初值为0，将signal(S)操作放在语句S1后面，而在S2语句前面插入wait(S)操作，即
在进程P1中，用S1；signal(S)；
在进程P2中，用wait(S)；S2；
由于S被初始化为0，这样，若P2先执行必定阻塞，只有在进程P1执行完S1； signal(S)；操作后使S增为1时，P2进程方能成功执行语句S2
管程机制
管程是由一个或多个过程、一个初始化序列和数据组成的软件模块，是一种程序设计语言结构成分，具有和信号量同等的表达能力。进程可以通过调用管程实现对资源的请求和释放。
cwait和csignal操作意义：
（1）cwait(c)操作：正在调用管程过程的进程因条件c没有满足而被阻塞或者挂起，则调用cwait操作将自己插入到条件变量c的等待进程队列中。与此同时，被阻塞进程释放管程，直到条件c发生改变，其它进程可以调用管程。
（2）csignal(c)操作：正在调用管程的进程检测到条件c发生了改变，则调用csignal操作重新唤醒一个因条件c而被阻塞或者挂起的进程。如果等待进程队列中有多个进程，则选择其中一个唤醒，否则继续执行原进程。
三个经典的进程同步问题
生产者-消费者问题
问题描述
假设有n个生产者和m个消费者，连接在一个有k个公用缓冲区的有界缓冲上，pi表示生产者进程，cj表示消费者进程。 满足：
只要缓冲区未满，生产者pi即可将生产的产品放 入空闲缓冲区中
只要缓冲区不为空，消费者进程cj就可从缓冲区从取走并消耗产品
用信号量解决生产者-消费者问题
利用互斥信号量mutex实现多个进程对公用缓冲区的互斥使用，初始化为1
利用信号量empty和full分别记录公用缓冲区中空缓冲区和满缓冲区的个数，分别初始化为k和0。
int nextin = 0, nextout = 0; |
读者-写者问题
问题描述
有一个多个进程共享的数据区，我们把只要读该数据区的进程记为Reader进程（读者），把只要往数据区中写数据的进程记为Writer进程（写者）。满足：
允许多个读者同时执行读操作
一次只能有一个写者可以执行写操作
如果一个写者在执行写操作，则其它任何读者都不能执行读操作
用信号量解决读者-写者问题
利用互斥信号量wmutex实施读者与写者在读写时的互斥，
设置整型变量readercount用于记录正在读的进程个数
计数变量readercount本身是可以被多个读者访问的临界资源，设置互斥信号量mutex控制多个读者对readercount的修改
semaphore mutex = 1, wmutex = 1; |
哲学家就餐问题
问题描述
有五位哲学家，用一生来思考和吃饭。他们围坐在一张圆桌旁边，桌子中央有一大碗米饭，桌上还有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，当某位哲学家进行思考时，他不与其它哲学家交互。当他感觉到饥饿时，便试图拿起与其左右最靠近他的筷子。满足：
一个哲学家每次只能拿起一只筷子，且他不能从其他哲学家手里拿筷子
只有在他拿到两只筷子时才能进餐
semaphore chopstick[5] = {1,1,1,1,1}; |
消息传递
消息传递（Message passing）作为当前应用最为广泛的一种进程间通信机制，为进程间信息传递和交换的实现提供了很好的保障
消息是一组信息，由消息头和消息体组成。
send(destination, message)
receive(source, message)
四、处理机调度
调度简介
计算机系统中，处理器和内存资源会出现供不应求的情况，特别是多个I/O设备与主机交互，作业不断进入系统，或者是多个批处理作业在磁盘的后备队列中等待进入内存的情况。操作系统在管理有限的资源的同时，需要考虑如何选取进入内存的作业，如何分配有限的处理器资源给多个进程等重要问题。处理器的调度正是处理器和内存资源调度和分配相关的工作。
高级调度：对象是作业，又称作业调度、长调度
低级调度：对象是进程，又称进程调度、短调度
中级调度：中级调度介于高级调度和低级调度之间。该调度根据进程状态决定辅存和主存之间的进程对换。主存资源紧缺时，将暂时不能运行的进程换出，进程转为挂起状态；主存资源空闲，并且进程满足运行条件时，再将进程调回主存。对主存的利用和系统吞吐率都有很大的提升。
在上述三种调度中，进程调度是操作系统最核心的部分，运行频率最高，因此把它称为短程调度。为避免进程调度占用太多的CPU时间，进程调度算法不宜太复杂。作业调度往往是发生在一个(批)作业运行完毕，退出系统，而需要重新调入一个(批)作业进入内存时，故作业调度的周期较长，大约几分钟一次，因此把它称为长程调度。在纯粹的分时或实时操作系统中通常不需要作业调度。中级调度的运行频率基本上介于上述两种调度之间。一些功能完善的操作系统为了提高主存利用率和作业吞吐率，会引入中级调度。
调度算法
先来先服务调度算法
先来先服务算法（First Come First Served， FCFS）按照作业/进程进入队列的先后顺序进行挑选，先进入的将优先进行后续步骤。该算法既可用于高级调度，也可用于低级调度。当在高级调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在低级调度中采用该算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。该算法比较有利于长作业(进程)，而不利于短作业(进程)。
短作业优先调度算法
短作业优先调度算法（shot job first, SJF）按照进入系统的作业所要求的CPU运行时间的长短为挑选依据，优先选取预计计算时间最短的作业。可以分别用于高级调度和低级调度。
短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。SJF调度算法能有效地降低作业的平均等待时间，提高系统吞吐量。
优先级算法
优先级算法根据事先设定好的进程的优先级来选取就绪队列中优先级最高的进程投入运行。在运行过程中，如果就绪队列中出现优先级更高的进程，则根据系统的策略：抢占式或非抢占式进行调度
非抢占式：当前进程继续运行直到完成；或出现需要等待的事件放弃处理机，再调度优先级高的进程运行。
抢占式：当前进程占用的处理机被立即剥夺，将处理机分配给优先级高的进程，使之运行。只要高优先级的进程出现，无论当前进程完成与否，都必须立即停止，重新将处理机分配给新到的优先权最高的进程。抢占式的优先级调度算法能更好地满足紧迫作业的要求。
时间片轮转算法
时间片轮转算法将CPU分配给就绪队列中的第一个进程，每次分配一个时间片。但时间片耗尽时，如果进程未完成，则让出处理机，转到就绪队列的队尾，等待下一轮的时间片的分配。
系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把处理机分配给队首进程，并令其执行一个时间片。当执行的时间片用完时发出中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证系统能在给定的时间内响应所有用户的请求。
在时间片轮转算法中，时间片的大小对系统性能有很大的影响
选择很小的时间片将有利于短作业，因为它能较快地完成，但会频繁地发生中断、进程上下文的切换，从而增加系统的开销
选择太长的时间片，使得每个进程都能在一个时间片内完成，时间片轮转算法便退化为FCFS算法，无法满足交互式用户的需求
一个较为可取的大小是时间片略大于一次典型的交互时间，这样可使大多数进程在一个时间片内完成
高响应比优先算法
最高响应比优先算法同时兼顾作业的等待时间和处理时间，做有效的协调和折中，既能照顾短作业的调度，同时也不会让长作业等待的时间超出合理的范围。
几种算法比较
先来先服务：只考虑作业等待时间，忽视作业计算时间。
短作业优先：考虑作业预计的计算时间，忽视作业的等待时间。
最高响应比：综合前两种算法的优点：既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。缺点：计算每个作业的响应比需要耗费一定的时间，性能比短作业优先算法略差。
如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以一定的速率提高，则长作业在等待一定的时间后，必然有机会分配到处理机。
高响应比调度算法：
如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业
当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而实现的是先来先服务
对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机
资源
计算机系统中存在一些只能被一个进程所使用的资源，如磁带机、打印机等独占设备。
两个进程同时进入临界区会导致数据错误或者系统错误。所以操作系统需要控制进程独立对这些临界资源进行访问。
对资源的访问需要以下步骤：申请，访问，归还。如果某一个进程申请资源的时候，资源正在被其他进程使用，则该申请的进程需要等待。
资源可以分成如下两类：
可剥夺性资源，是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺。如：处理机和内存。优先权高的进程可以剥夺优先权低的进程的处理机。内存区可由存储器管理程序把一个进程从一个存储区移到另一个存储区，此即剥夺了该进程原来占有的存储区。甚至可将一个进程从内存调出到外存上。
不可剥夺性资源，当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。
死锁产生的原因和必要条件
死锁的定义：所谓死锁 (Deadlock)，是指多个进程因竞争资源而造成的一种僵局(Deadly-Embrace)，若无外力作用，这些进程将永远不能再向前推进。
死锁产生的必要条件
互斥: 进程对所分配到的资源必须独立使用，即在一段时间内某资源只由一个进程占用，不能共享。如果此时还有其它进程请求该资源，则请求者只能等待，直至占有该资源的进程使用完毕，对资源进行释放。
请求和保持：进程已经持有了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已获得的其它资源保持继续持有。
不可剥夺: 在未使用完之前，不能剥夺进程已获得的资源，只能在使用完时由自己释放。
循环等待：在发生死锁时，必然存在一个进程和进程之间等待相互资源的环形链。使得链中每个进程的资源需求都得不到满足。
死锁的表示方法和判定
根据SRAG的定义，可以使用以下规则判定死锁
如果SRAG中无环路，则系统不会死锁。
如果SRAG中有环路，且处于此环中的每类资源只有一个，如图4.7(c)所示，则系统出现死锁。此时，环是系统存在死锁的充分必要条件。
如果SRAG中有环路，但是处于此环中的每类资源的个数不全为1，如图4.7(d)所示，则系统不一定会发生死锁。此时，环只是产生死锁的必要条件而不是充分条件。
系统存在死锁状态的充要条件是当且仅当系统的SRAG是不可完全简化的。如果资源满足某个进程的要求，则在SRAG中消去此进程的所有请求边和分配边，使其成为孤立结点。对所有进程执行该操作。如果所有进程都成为孤立结点，则称该图是可完全简化的；否则称该图是不可完全简化的。
死锁预防
破坏“请求和保持”条件
请求：将对资源的申请放在进程运行之前一次性进行，得到了所需所有资源的进程在整个运行期间不会再提出资源要求，从而破坏了请求条件。
分配：在分配资源时，只要有一种资源不能满足某进程的要求，即使其它所需的各资源都空闲，也不分配给该进程，而让该进程等待。由于在该进程的等待期间，它并未占有任何资源，因而破坏了保持条件。
破坏“不剥夺”条件
进程逐个地提出对资源的要求。 当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。 已经占有的资源，在运行过程中会被暂时地释放掉，从而破坏了“不剥夺”条件。
破坏“环路等待”条件
系统将所有资源按类型分成不同等级进行排列，并赋予不同的等级号。例如，资源a序号为1，资源b的序号为2，资源c的序号为3，…。所有进程对资源的请求必须严格按照资源序号递增的次序提出，这样，在所形成的资源分配图中，不可能再出现环路，破坏了“环路等待”条件。 这种方法称为有序资源分配法。
死锁避免
死锁的预防会牺牲系统的并发性能和资源的利用率，死锁避免通过合理的资源分配确保不会出现循环等待的条件，除了能够避免死锁，还能够支持进程的并发及资源的合理使用。并且死锁避免的过程是动态的，没有强制和预先设置的规则。
银行家算法
基本思想：先判断系统是否处于安全状态，然后试探性地接受一个进程的资源请求，试探性分配资源，计算分配之后剩余的可用资源是否能满足系统中其他进程的需要，并且是否有进程能够获取足够多的资源来完成进程，释放资源。
如果考虑了完成进程的资源释放和其他进程的需求，能够最终使得每个进程都能够顺利完成，则将真正实施该进程的分配需求；否则，说明系统将处于不安全状态，不会真正实施该分配需求，等待其他进程的资源申请。
死算检测和恢复
在资源分配的时候考虑一定的限制，对死锁的预防和避免与一定的效果，但是资源的充分共享方面又会有所欠缺。与之相对应的解决方案是考虑死锁的检测和恢复，不影响资源的合理使用和分配。
当系统为进程分配资源时，没有采取任何限制性措施，那么系统必须检测系统内部是否出现死锁情况：
保存有关资源的请求和分配信息；
提供一种算法通过这些信息来检测系统是否已进入死锁状态。
相关难点在于：何时以何种频率运行检测死锁的算法。
运行太频繁会浪费CPU的处理时间，运行太稀疏又会导致系统内部死锁情况长时间不能被发现。
当发现有进程死锁时，必须立即把它们从死锁状态中恢复出来。
死锁恢复方法
取消所有的死锁进程；
让每个死锁进程回退到某些安全性检查的时间点之前，并重新启动所有进程；
连续取消死锁进程直到不再存在死锁；
连续抢占资源直到不再存在死锁。
五、内存管理
概述
内存
主存储器简称内存或主存，是计算机系统中的主要部件，用于保存进程运行时的程序和数据，也称可执行存储器。
寄存器
寄存器具有与处理机相同的速度，故对寄存器的访问速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容量不可能做得很大。
高速缓冲存储器
高速缓存是现代计算机结构中的一个重要部件，它是介于寄存器和存储器之间的存储器，主要用于备份主存中较常用的数据，以减少处理机对主存储器的访问次数，这样可大幅度地提高程序执行速度。高速缓存容量远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器。
磁盘缓存
由于目前磁盘的I/O速度远低于对主存的访问速度，为了缓和两者之间在速度上的不匹配，而设置了磁盘缓存，主要用于暂时存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数。但磁盘缓存与高速缓存不同，它本身并不是一种实际存在的存储器，而是利用主存中的部分存储空间暂时存放从磁盘中读出(或写入)的信息。主存也可以看作是辅存的高速缓存，因为，辅存中的数据必须复制到主存方能使用，反之，数据也必须先存在主存中，才能输出到辅存。
地址重定位
一个逻辑地址空间的程序装入到物理地址空间时，由于两个空间不一致，需要进行地址变换，称为地址重定位。
此时，相对地址空间（也称为逻辑地址空间）通过地址重定位机构转换到绝对地址空间（也称为物理地址空间）。
单一连续、固定分区、可变化分区分配
单一连续分区存储管理
这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。
在单道程序环境下，当时的存储器管理方式是把内存分为系统区和用户区两部分，系统区仅提供给OS使用，它通常是放在内存的低址部分。而在用户区内存中，仅装有一道用户程序，即整个内存的用户空间由该程序独占。这样的存储器分配方式被称为单一连续分配方式。
固定分区管理
固定分区式分配是最简单的一种可运行多道程序的存储管理方式。这是将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业，这样，把用户空间划分为几个分区，便允许有几道作业并发运行。
当某一分区空闲时，便可以从外存的后备作业队列中选择一个适当大小的作业装入该分区，当该作业结束时，又可再从后备作业队列中找出另一作业调入该分区。
划分分区的方法
(1) 分区大小相等(指所有的内存分区大小相等)。
(2) 分区大小不等。将内存划分出多个较小的分区，适量的中等分区和少量的大分区。 内存分配
为了便于内存分配，通常将分区按其大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)
可变分区管理（动态分区管理）
固定分区分配是最早的多道程序存储管理方式，由于每个分区的大小固定，必然会造成存储空间的浪费。
可变分区分配是指在系统运行的过程中根据作业对内存的实际需要，动态地为之分配内存空间的一种分区方法。
可变分区分配是在作业装入和处理过程中建立的分区，并使分区的大小与作业的大小相等。
分区的个数和大小不是固定不变的，而是根据装入的作业动态地划分。
分区分配算法
首次适应算法
该算法要求分区链以地址递增的次序链接。内存分配时，从链首开始顺序查找，直至找到一个能满足其大小要求的空闲区为止。然后，再按照作业的大小，从该区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲链中。
该算法倾向于优先利用内存中低址部分的空闲区，高址部分的很少利用，从而保留了高址部分的大空闲区，为以后到达的大作业分配大的内存空间创造了条件。但低址部分留下许多难以利用的很小的空闲区 ，每次查找又都从低址部分开始，这样，增加了查找开销。
最佳适应算法
“最佳”的含义是指每次为作业分配内存时，总是把既能满足要求又是最小的空闲分区分配给作业，避免“大材小用”。为加速查询，该算法要求将所有的空闲区按其大小以递增的顺序链接成一空闲区链。这样，第一次找到的满足要求的空闲区，必然是最优的。
孤立地看，这似乎是最佳的，但从宏观上看却不一定。因为每次分配后所切割下的剩余部分，总是最小的，在存储器中会留下许多难以利用的小空闲区。
最差适应算法
由于最坏适应分配算法选择空闲分区的策略正好与最佳适应算法相反：它在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用，以至于存储器中缺乏大的空闲分区，故把它称为是最坏适应算法。
该算法要求将所有空闲分区，按容量从大到小的顺序，形成一空闲分区链，查找时，只要看第一个分区能否满足作业要求即可。
循环首次适应算法
由首次适应算法演变而来，分配内存时，不再每次从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间。
为实现该算法，应设置一起始查询指针，并采用循环查找方式。该算法能使内存中的空闲分区分布得更均匀，减少查找空闲分区的开销，但这会缺乏大的空闲分区。
快速适应算法
该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表的表头指针。
该算法在搜索空闲分区时分二步：第一步是根据进程长度从索引表中找到能容纳它的最小空闲区链表；第二步是从链表中取下第一块进行分配。
优点：查找效率高。另外在进行空闲分区分配时，不会对任何分区产生分割，能保留大的空闲分区，同时也不会产生内存碎片。
缺点：在分区归还时算法比较复杂，系统开销较大。该算法在分配空闲分区时是以进程为单位，一个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少地存在一定的浪费。空闲分区划分越细，浪费越严重，整体上会造成可观的存储空间浪费，这是典型的以空间换时间的作法。
哈希算法
哈希算法是利用哈希快速查找的优点，以及空闲分区在可利用空闲分区表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。 进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。
伙伴系统
该算法规定，无论已分配分区或空闲分区，其大小均为2的k次幂(k为整数，l≤k≤m)，其中2l表示分配的最小块的尺寸，2m表示分配的最大的块的尺寸。通常， 2m是可供分配的整个内存的大小。
（1）开始时，可用于分配的整个空间被看成是一个大小为2m的块；
（2）如果请求的大小s满足2m-1 < s <= 2m ，则分配整个空间；否则，该块被分成两个大小相等的伙伴，均为2m-1 ，如果有2m-2 < s <= 2m-1 ，则给该请求分配两个伙伴中的一个，否则，其中的一个伙伴被继续分成两半。这个过程一直持续直到产生大于或等于s的最小块，并将其分配。
页、块、页表、地址结构、分页地址变换、快表
如果离散分配的基本单位是页，则称为分页存储管理方式；如果离散分配的基本单位是段，则称为分段存储管理方式。
分页存储管理方式。 该方式是将用户程序的地址空间划分成若干个固定大小的区域（称为页或页面）；相应地，内存空间也被划分成若干个物理块，页和块的大小相等，典型大小为1KB。这样，用户程序的任意页可放在内存的任一块。
分段存储管理方式。 该方式是把用户程序的地址空间分成若干个大小不等的段，每段可定义一组相对完整的逻辑信息。进行存储分配时，以段为单位，段在内存中可以不邻接。
段页式存储管理方式。 分页和分段两种存储管理方式相结合的产物。
页面和物理块
(1) 页面。分页存储管理是将内存分成大小固定的若干块，一般每一块的大小为1KB、2KB或4KB，每个这样的内存块称为页或物理块。将逻辑空间划分成若干个页，并为每页加以编号，从第0页开始，第1页，第2页，……。同时，将内存的物理地址空间划分成若干个块，同样为它们加以编号。进程分配内存时，将进程中的若干个页分别装入到多个可以不相邻的物理块中。会产生“页内碎片”。
(2) 页面大小。 过小，一方面可以减小内存碎片，另一方面会使进程占用较多页面，导致进程页表项过长，占用大量内存；过大，会使页内碎片增大。
页表
在进行存储分配时，允许将进程的各个页离散地存储在内存中不同的物理块中，但系统应能保证进程的正确运行。
页表中至少应包含以下信息：
(1) 页号：进程各页的序号；
(2) 物理块号：进程各页对应存放在内存中的物理块的块号。
地址变换过程
地址变换机构的基本任务是实现逻辑地址到物理地址的转换。由于页内地址与块内物理地址是一一对应的，故无须再转换。因此地址变换机构的任务，实际上是将逻辑地址中的页号，转换为内存中的物理块号。又因为页面映射表的作用就是用于实现从页号到物理块号的变换，所以地址变换任务是借助于页表来完成的。
页表的功能可以由一组专门的寄存器来实现，一个页表项用一个寄存器。但现代计算机系统大多都将页表驻留在内存，并设置一个页表寄存器PTR(Page-Table Register)，用于存放页表在内存的始址和页表的长度。
进程要访问某个逻辑地址中的数据时。
（1）分页地址机构自动地将有效地址分为页号和页内地址两部分；
（2）再以页号为索引去检索页表；
（3）将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是从中得到该页的物理块号，将之装入物理地址寄存器中；
（4）同时再将有效地址寄存器中的页内地址直接送入物理地址寄存器的块内地址字段中。
快表
由于页表作为数据本身是存放在内存中的，这使CPU在每存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量W拼接，以形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据(或向此地址中写入数据)。因此，采用这种方式将使计算机的处理速度降低近1/2。可见，以此高昂代价来换取存储器空间利用率的提高，是得不偿失的。
为提高地址变换速度，可在地址变换机构中增设一个称为快表的高速缓冲存储器，用以存放当前访问的页表项。
此时地址变换过程是：CPU给出有效地址后，地址变换机构自动地将页号P送入快表高速缓存，并与其中的所有页号比较，若有与此相匹配的页号，则直接读出该页所对应的物理块号，送物理地址寄存器。若未找到，则再访问内存中的页表，找到后，把从页表项中读出的物理块号送地址寄存器；同时将此页表项存入快表。若快表已满，OS须找到一个老的且已被认为不再需要的页表项将它换出。
假如查找快表需要20ns，访问内存需要100ns，那么总的访问时间是120ns。如果不能在快表中找到该页表项，那么必须先访问位于内存中的页表得到相应的物理块号(花费120ns)，然后再访问内存(花费100ns)，总共需要220ns。则：
EAT＝0.85×(20+100)＋(1-0.85)×(20+200)＝135ns
两级页表、多级页表
两级页表
对于要求连续的内存空间来存放页表的问题，可以利用将页表进行分页，并离散的将各个页面分别存放在不同的物理块中的办法来加以解决，同样也要为离散分配的页表再建立一张页表，称为外层页表(Outer Page Table) ，在每个页表项中记录了页表页面的物理块号。
多级页表
随着64位机器的普及，两级页表会出现外部页表非常大，要占用相当大的内存空间的问题。
可以采用三级或三级以上页表的方式，将原来两级页表中的外部页表再进行分页，然后利用第二级的外层页表来映射页表之间的关系。
多级页表类似于多级目录。
UNIX系统中使用了三级页表来实现地址映射。
段、段表、地址结构、分段地址变换
动态分区分配方式中，系统为整个进程分配一个连续的内存空间。而在分段式存储管理系统中则以段为单位分配内存，每段分配一个连续的内存区域，但各段之间不要求连续。
其内存的分配和回收类似于动态分区分配方式，但两者之间也有不同。在分段存储管理系统中，一个作业可以有多个段，这些段允许离散地存放在内存的不同分区当中，而分区存储管理方式则要求整个作业存放在一个内存分区中。
段表
作业的一个段被分配一个连续的分区，而进程中的各个段可以离散地放入内存中不同的分区中，为能从物理内存中找出每个逻辑段所对应的位置，在系统中为每个进程建立一张段映射表，简称段表。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址（基址）和段的长度（段长）。段表可以存放在一组寄存器中，更常见的是存放在内存中。
分页和分段的区别
分页和分段系统有许多相似之处，但在概念上二者完全不同：
(1) 页是信息的物理单位，仅仅是出于系统管理的需要；段是信息的逻辑单位，其目的是满足用户的需要。
(2) 页的大小固定且由系统确定，一个系统只能有一种大小的页面；段的长度不固定，决定于用户所编写的程序；
(3) 分页的作业地址空间是一维的；分段的作业地址空间是二维的。
(4) 通常分段的段内空间会比分页的页面空间大，因此段表会比页表短。
段页式存储管理
基本原理
段页式系统的基本原理是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。在段页式系统中，其地址结构由段号、段内页号及页内地址三部分所组成
为实现从逻辑地址到物理地址的变换，系统需同时配置段表和页表，段表的内容是页表始址和页表长度，这与分段式系统不同。
地址变换过程
在段页式系统中，为了便于实现地址变换，需要配置一个段表寄存器，其中存放段表始址和段表长度。进行地址变换时按如下步骤进行：
(1) 通过段表寄存器将段号与段表长度进行比较，如果未越界则查找段表在内存中的位置，否则越界中断；
(2) 访问段表，将页表长度与页号进行比较，如果未越界则根据段号查找页表所在的位置；
(3) 访问页表，根据页号查找该页所在的物理块号；
(4) 将物理块号和地址结构中的页内地址相加，形成内存单元的物理地址。
基本原理：局部性原理、虚拟存储器
局部性原理
程序运行时存在的局部性现象，很早就已被人发现，但直到1968年，P.Denning才真正指出：程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域。
局限性又表现在下述两个方面：
(1) 时间局限性。程序中的某条指令被执行，不久后会再次执行；某个数据被访问，不久后将再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。 (2) 空间局限性。 程序访问了某个存储单元，不久后，其附近的存储单元也将被访问。
虚拟存储器
基于局部性原理可知，应用程序在运行之前没有必要将之全部装入内存，而仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。
局部性原理是实现虚拟存储管理的理论基础。
所谓虚拟存储器是指仅把作业的一部分装入内存便可运行的存储器系统，是具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。虚拟存储器的逻辑容量由系统的寻址能力和外存容量之和所决定，与实际的内存容量无关。
虚拟存储特征
(1) 多次性：是指一个作业被分成多次来调入内存，即作业运行时不需将其全部装入内存，只需将当前要运行的那部分程序和数据装入，以后运行到某些部分时再将其调入。 (2) 对换性：是指允许作业中的程序和数据，在作业运行过程中换进、换出。
(3) 虚拟性：是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。
虚拟性以多次性和对换性为基础，多次性和对换性以离散分配为基础。
请求分页存储管理
每当所要访问的页面不在内存时，便要产生一次缺页中断，请求OS将所缺之页调入内存。缺页中断虽要经历与一般中断相同的几个步骤，但它是一种特殊的中断，与一般中断的区别主要是：
(1) 在指令执行期间产生和处理中断信号。通常CPU都是在一条指令执行完后去检查是否有中断请求到达。有则响应，无则继续执行下一条指令。而缺页中断是在指令执行期间，发现所要访问的指令和数据不在内存时产生和处理的。
(2) 一条指令在执行期间，可能产生多次缺页中断。这时硬件机构应能保存多次中断时的状态，并保证最后能返回到中断前产生缺页中断的指令处，继续执行。
页面置换算法：最佳置换、FIFO、LRU、第二次机会、CLOCK 置换
请求分页存储管理系统性能分析：缺页率、抖动、页面大小
缺页率的影响因素: 1) 页面大小；2) 进程分配物理块的数目；3) 页面置换算法；4) 程序固有特性。
假设使用了“快表”以提高访问内存的速度，则CPU访问内存所花费的时间由以下3个部分组成：
(1) 页面在“快表”时的存取时间，只需1个读写周期时间；
(2) 页面不在“快表”而在页表时的存取时间，需要2个读写周期时间；
(3) 页面既不在“快表”也不在页表时，发生缺页中断处理的时间。
缺页中断处理的时间又有3个部分组成：
(1) 缺页中断服务时间；
(2) 页面传送时间，包括：寻道时间、旋转时间和数据传送时间。
(3) 进程重新执行时间。
置换算法的好坏将直接影响系统的性能，不适当的算法可能导致进程发生“抖动” (Thrash-ing)。即刚被换出的页很快又被访问，需重新调入。为此，又需再选一页调出；而此刚被换出的页，很快又被访问，因而又需将它调入。如此频繁地更换页面，以至一个进程在运行中，将把大部分时间花在完成页面置换的工作上，我们称该进程发生了“抖动”。 抖动现象分为局部抖动和全局抖动两种类型。抖动现象如下两种类型：
1) 局部抖动：进程采用局部置换策略，产生缺页时，只能置换自身拥有的某个页面，而不能置换其它进程的页面
2) 全局抖动：由进程之间的相互作用引起的，若进程采用的是全局置换策略，当一个进程发生缺页中断时，需要从其它进程那里获取物理块，从而导致这些进程在运行中需要物理块，产生了缺页中断时，又需要从其它进程那里获取物理块。
页面大小的选择
页面大小的选择涉及到内部碎片、页表大小、页面失效率的高低等诸多问题
页面越小，内部碎片就越少，内存利用率就越高，但同时就会产生较大的页表，占用较大的内存空间；
页面过大，会导致页面在内外存之间传输时间的增加，从而降低了系统的有效访问时间；
页面较小，内存中包含的页面数就较多，相应的，缺页率就会较低，但随着页面的增大，缺页率也会随之升高，当页面大小超过进程的大小时，缺页率又开始下降。
选择最优的页面大小需要在这几个互相矛盾的因素之间权衡利弊。另外，页面的大小还与主存的大小、程序设计技术和程序结构以及快表等因素有关。
请求分段存储管理
请求分段存储管理系统是在分段存储管理系统的基础上增加了请求调段功能和段置换功能后所形成的分段虚拟存储管理系统。由于作业的各段是根据请求被装入内存的，因此，这种存储管理也称为请求分段存储管理。
请求分段存储管理系统把作业的所有分段的副本都存放在外存中，当作业被调度投入执行时，先把当前需要的—段或几段装入内存。在执行过程中，出现缺段中断时，再把存储在外存上的段交换至内存，以此实现请求分段存储管理。
六、设备管理
概述
I/O系统控制方式
程序直接控制方式
中断控制方式
DMA控制方式
通道控制方式
通道类型
磁盘简述
磁盘调度：FCFS,SSTF,SCAN,C-SCAN,N步扫描，F-SCAN
七、文件管理
概述
物理结构
顺序结构
链接结构
索引结构
直接文件
哈希文件
文件控制块
索引节点
目录查询
文件共享：符号链接实现共享、索引节点实现共享
文件安全：存取控制矩阵、存取控制表、用户权限表、口令方法
十、系统安全
逻辑炸弹、缓冲区溢出、SQP注入
逻辑炸弹：逻辑炸弹是指在特定逻辑条件得到满足时实施破坏的计算机程序。可能造成计算机数据丢失、计算机无法从硬盘或软盘引导，甚至导致整个系统瘫痪，并出现物理损坏的虚假现象。
逻辑炸弹触发时的特定条件称为逻辑诱因。
逻辑炸弹的危害：直接破坏计算机软件产品的使用者的计算机数据。
引发连带的社会灾难，包括直接或间接的损失，如企业亏损、资料丢失、科学研究的永久性失败、当事人承受精神打击、刑事犯罪等。
缓冲区溢出：是指当计算机向缓冲区内填充数据位数时超过了缓冲区本身的容量，使得溢出的数据覆盖在合法数据上。理想的情况是，程序检查数据长度、同时不允许输入超过缓冲区长度的字符；然而绝大多数程序都会假设数据长度总是与所分配的储存空间相匹配，这就为缓冲区溢出现象的发生埋下了隐患。
利用缓冲区溢出攻击，可以导致程序运行失败、系统宕机、重新启动等后果。更严重的是，可以利用它执行非授权指令，甚至可以取得系统特权进而执行某些非法操作。
SQL注入：是对数据库进行攻击的常用手段之一。
它利用现有应用程序可以将SQL命令注入到后台数据库引擎执行的能力，通过在Web表单、域名输入或页面请求的查询字符串等内容中输入恶意的SQL语句得到一个存在安全漏洞的网站的数据库，最终达到欺骗服务器执行恶意SQL命令的目的。
SQL注入攻击通过构建特殊的输入作为参数传入Web应用程序，而这些输入多为SQL语法里的一些组合，通过执行SQL语句进而执行攻击者所需的操作，其发生原因主要是程序没有过滤用户输入的数据，致使非法数据侵入系统。
SQL注入可分为平台层注入和代码层注入。前者由不安全的数据库配置或数据库平台的漏洞所致；后者主要是由于程序员对输入未进行细致过滤，从而执行了非法的数据查询。
特洛伊木马、计算机病毒、蠕虫、rootkit
特洛伊木马： 没有复制能力，其特点是伪装成一个实用工具或者一个可爱的游戏，诱使用户将其安装在PC或者服务器上。
在不经意间，特洛伊木马可能对使用者的计算机系统产生破坏，或窃取数据特别是使用者的各种账户及口令等重要且需要保密的信息，甚至直接控制计算机系统。一个完整的特洛伊木马套装程序包含两个部分：服务端（服务器部分）和客户端（控制器部分）。植入对方计算机的是服务端，而攻击者正是利用客户端进入运行了服务端的计算机。
计算机病毒： 是指编制者在计算机程序中插入的、破坏计算机功能或者破坏数据、影响计算机使用并且能够自我复制的一组计算机指令或恶意的程序代码。
与生物病毒不相同的是，计算机病毒不是自然存在的生命体，而是某些人利用计算机软件或硬件固有的脆弱性编制出来的，其本质是一组指令集或程序代码。病毒能通过某种途径长期潜伏在计算机的存储介质（或程序）中，当达到某种条件时即被激活；同时，它还可以通过修改其他程序将自己的精确拷贝或者可能演化的形式植入其他程序中，从而感染更多程序。
计算机病毒的特点
传染性是病毒的基本特征，是指计算机病毒在一定条件下可以自我复制，能对其它文件或系统进行一系列非法操作，并使之成为新的传染源。
繁殖性：计算机病毒可以将与自身完全相同的副本植入其他程序或者存储介质的特定区域，使每一个受感染程序都同时包含病毒的一个克隆体。是否具备繁殖、感染的特征，是判断某一段程序为计算机病毒的首要条件。
潜伏性：计算机病毒的潜伏性是指计算机病毒依附于其他载体寄生的一种能力，这使侵入的病毒可以潜伏在系统中直到条件成熟才会发作。
破坏性：所有的计算机病毒都是可执行程序，所以他们对计算机系统而言必然存在一个共同的危害，就是一旦执行便会占用系统资源，严重时会降低计算机系统工作效率。
隐蔽性：计算机病毒通常具有很强的隐蔽性，这是计算机病毒难以被查杀的一个重要原因。
可触发性：病毒因某个事件或数值的出现，诱使病毒实施感染或进行攻击的特性称为可触发性。
计算机病毒、特洛伊木马与逻辑炸弹的比较
在计算机程序中，病毒、木马与逻辑炸弹是常见的三种破坏手段，它们相互联系又各有区别。三者的共性在于它们都对计算机系统产生危害。
病毒是通过自我复制进行传播的计算机程序，自我复制是其基本特性，但它的破坏机制却不是必备的，所以现实中也存在一些只传染复制而不实施恶性破坏的、所谓的“良性”病毒。
木马虽然也是一种程序，但它只具备破坏性却不能完成自我复制。典型木马程序是以“冒充”来作为传播手段的，这同病毒在新目标中植入自己的副本这种“繁殖”方式显而易见存在差别。
逻辑炸弹一般隐含在具有正常功能的软件内部，并不像典型的木马程序那样仅仅只是模仿程序的外表而没有真正的程序功能。
蠕虫
所谓蠕虫，又被称为蠕虫病毒，其实是一种结合了蠕虫特性与病毒机理（技术特点）的产物。目前主流的定义认为，蠕虫是一种能够利用系统漏洞通过网络进行自我传播的恶意程序。
蠕虫同时集成了蠕虫和病毒两者的特征，从而使其自身更加强大、传播能力也更强，它还有一个显著特点是不一定需要附着在其他程序上而可以独立存在。当形成规模与传播速度相当快时，蠕虫攻击会极大地消耗网络资源，从而导致大面积网络拥塞甚至瘫痪。
蠕虫分为主机蠕虫与网络蠕虫。其中，主机蠕虫完全包含在它们运行的计算机中，并且使用网络的连接将自身拷贝到其他的计算机中。主机蠕虫在完成自身的拷贝加入到另外的主机之后，就会终止自身的行为。
如果根据攻击目的进行划分，蠕虫又可以分成两类：一类是面对大规模计算机网络发动拒绝服务的计算机蠕虫，另一类则是针对个人用户的执行大量垃圾代码的计算机蠕虫。
蠕虫由两部分组成：一个主程序和一个引导程序。主程序一旦在电脑中建立就会去收集与当前电脑联网的其它主机信息。随后，主程序会尝试利用系统缺陷去在这些远程计算机上建立其引导程序。
rootkit
rootkit一词最早出现在Unix系统中。系统入侵者为了取得系统管理员级的root权限或为了清除被系统记录的入侵痕迹，会重新汇编一些软件工具，这些工具就被称为kit。由此rootkit可以视作一项技术。
一种公认的定义认为：rootkit是指其主要功能为隐藏其他程式进程的软件，它可能是一个或多个软件的组合。从其定义不难看出，rootkit是一种特殊的恶意软件，其功能是在安装目标上隐藏自身及指定的文件、进程或网络链接等信息。目前，rootkit更多的是指那些被作为驱动程序加载到操作系统内核中的恶意软件。
通常情况下，rootkit总是和木马、后门等其他恶意程序结合使用。rootkit通过加载特殊的驱动、修改系统内核，进而达到隐藏信息的目的。
rootkit是一种奇特的程序，它具有隐身功能。无论是作为文件存在的静止时刻，还是作为进程存在的活动时刻都不会被察觉。
这一特性恰是一些人梦寐以求的——不论是计算机黑客，还是计算机取证人员。前者可以在入侵后置入rootkit，秘密窥探敏感信息或等待时机、伺机而动；后者则可以利用rootkit实时监控嫌疑人的不法行为，这不仅帮助搜集证据还有利于采取及时行动。