第一章《绪论》

#控制和管理整个计算机系统的硬件和软件资源，并合理地组织、调度计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境的程序集合。

#提供一个计算机用户与计算机硬件系统之间的接口；控住和管理计算机的硬件和软件资源；合理的组织计算机系统的工作流程。

#①并发：某个时间段内有多个程序可以运行，需要OS管理和调度        #（并行性：在某个时间点多个程序可以运行/并发性：在某个时间段内有多个程序可以运行）#②共享：“同时”访问；互斥共享 ：同时对一个资源只有一个程序可以访问，但可以通过隔离成两块，达到“同时”访问#③虚拟：把一个物理上的实体变为若干个逻辑上的对应物，让每个用户都觉得有一个计算机专门为他服务#④异步：程序的执行不是一贯到底，而是走走停停，向前推进的速度不可预知；只要运行环境相同，OS需要保证程序运行的结果也要相同

#①处理器管理：#②储存器管理：#③设备管理：#④文件管理：#⑤用户接口：

#①批处理操作系统：用户脱机使用计算机，作业是程批处理的，系统内多道程序并发执行，交互能力差。#②分时操作系统：  可以让多个用户同时使用计算机，人机交互性较强，具有每个用户独立使用计算机的独立性，系统响应及时。#③实时操作系统：  多个用户通过终端同时共享一台主机，这些终端连接在主机上，用户可以同时与主机进行交互操作而互不干扰。能对控制对象做出及时反应，可靠性高，响应及时，但是资源利用率低。#④其他操作系统：  嵌入式系统、集群系统、网络操作系统、分布式操作系统

#① 内核态：OS运行中，CPU处的高权限的状态，OS可以执行任何CPU提供的任何指令或调用I/O。#   用户态：APP执行中，CPU处的一个较低权限的状态。不能直接访问特殊的机器指令和I/O#② 中断：也称外中断，指来自CPU执行指令以外的事件的发生。#（如设备发出的I/O中断，表示设备输入/输出处理已经完成，希望处理机能够向设备发一下个输入/输出请求，同时让完成输入/输出后的程序继续运行。）#   异常：也称外中断，指来自CPU执行指令以内的事件的发生。#（如程序的非法操作码，地址越界，算法溢出等指令引起的事件）#③ 系统调用：用户在程序中调用操作系统所提供的一些子功能，系统调用可以被看做是特殊的公共子程序。

#①模块组合结构：系统的模块根据它们完成的功能进行结构组合，协同完成整个系统的功能。#②层次结构：    系统的模块根据它们调用次序排列成若干层，使得功能模块只存在单向调用和单向依赖。#③微内核结构：  内核中只留下一些最基本的功能，而将其他服务尽可能的从内核中分离出去，用若干个运行在用户态下的进程来实现（C/S模式）

第二章《进程管理》

#进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。

#线程是进程内一个相对独立的、可调度的执行单元。线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈)但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。

#①包含关系：一个程序至少有一个进程,一个进程至少有一个线程。#②调度：在同一进程中，线程的切换不会引起进程的切换。在不同的进程中进行线程切换，将会引起进程切换。#③拥有资源：进程是拥有资源的基本单位，而线程不拥有资源，但线程可以访问其隶属进程的系统资源。#④并发性：进程之间可以并发，同一进程内的多个线程之间也可以并发执行。#⑤系统开销：进程比线程创建和撤销消耗的资源大。

#进程的三种基本状态#①就绪状态：进程已经获得了除了处理器以外的所有资源，一旦获得处理器就可以立即执行。#②执行状态（运行状态）：一个进程获得必要的资源并正在CPU上执行。#③阻塞状态（等待状态）：正在执行的进程由于发生某事件而暂时无法执行下去（如等待I/O完成）#进程状态的相互转换#1.就绪状态-->执行状态：一个进程被进程调度程序选中。#2.执行状态-->阻塞状态：请求并等待某个事件发生。#3.执行状态-->就绪状态：时间片用完或者在抢占式调度中有更高优先级的进程。#4.阻塞状态-->就绪状态：进程等待某个条件发生。##总结：<1>进程不能从阻塞状态-->执行状态（原因），也不能从就绪状态-->-->阻塞状态。#      <2>只有从执行状态-->阻塞状态才是主动行为（因事件而主动调用阻塞原语），其他都是被动的。#      <3>一个具体的进程在任何一个指定的时刻必须且只能处于一种状态。

#调度：实现进程的并发执行。##①高级调度（作业调度）：按一定原则从外存上处于后备状态的作业中挑选一个（或多个）作业，给他们分配内存、输入/输出设备等必要的资源，并建立相应的进程，以使他们获得竞争处理器的权利。#②中级调度（内存调度）：进程在内存和外存对换区之间换进换出，提高内存利用率和系统吞吐量。#③低级调度（作业调度）：按照某种方法和策略从就绪队列中选取一个进程，将处理器分配给它。

#①CPU利用率：应尽可能使CPU 保持“忙”状态，使这一资源利用率最髙。#②系统吞吐量：表示单位时间内CPU完成作业的数量。#③响应时间：指从用户提交请求到系统首次产生响应所用的时间。#④周转时间：是指从作业提交到作业完成所经历的时间。包括作业等待、在就绪队列中排队、在处迤机上运行以及进行输入/输出操作所花费时间的总和。#⑤作业周转时间 = 作业完成时间 - 作业提交时间。#⑥平均周转时间：指多个作业周转时间的平均值。  平均周转时间 = (作业1的周转时间 + … + 作业 n 的周转时间) / n#⑦带权周转时间：指作业周转时间与作业实际运行时间的比值。带权周转时间= 作业周转时间 /作业实际运行时间#⑧平均带权周转时间：指多个作业带权周转时间的平均值。#⑨等待时间：指进程处于等处理机状态时间之和（衡量一个调度算法优劣常常只需简单地考察等待时间）。等待时间=开始时间—提交时间

#①先来先服务(FCFS)调度算法（作业调度+进程调度）：按照进程进入就绪队列的先后次序来分配处理器。#②短作业优先(SJF)调度算法（作业调度+进程调度）：把处理器分配给最快完成的作业/进程。#③优先级调度算法（作业调度+进程调度）：把处理器分配给优先级最高的进程。#④时间片轮转调度算法（进程调度）：时间片轮转调度算法主要适用于分时系统，时间片的大小对系统性能的影响很大。时间片的长短通常由以下因素确定：系统的响应时间、就绪队列中的进程数目和系统的处理能力。（时间片：CPU分配给各个程序的时间，每个线程被分配一个时间段）#⑤高响应比优先调度算法（作业调度）：在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。#⑥多级反馈队列调度算法（进程调度）（集合了前几种算法的优点）：时间片轮转调度算法和优先级调度算法的综合和发展，通过动态调整进程优先级和时间片大小，兼顾多方面的系统目标。

#进程同步：在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步的概念。##临界资源：一次仅允许一个进程使用的资源。也叫互斥资源#临界区：  进程中用于访问临界资源的代码，又称临界段。##同步（直接制约关系）：为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。#互斥（间接制约关系）：当一个进程进入临界区使用临界资源时，另一个进程必须等待, 当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

#1、软件方法：#            1) 算法一：单标志法。#            2) 算法二：双标志法先检查。#            3) 算法三：双标志法后检查。#            4) 算法四：Peterson’s Algorithm。#2、硬件方法：            #            1) 中断屏蔽方法#            2) 硬件指令方法

#信号量机构是一种功能较强的机制，可用来解决互斥与同步的问题，它只能被两个标准的原语wait(S)和signal(S)来访问，也可以记为“P操作”（wait）和“V操作（signal）”##原语：指完成某种功能且不被分割不被中断执行的操作序列，通常可由硬件来实现完成不被分割执行特性的功能。##①整型信号量被定义为一个用于表示资源数目的整型量S，该机制并未遵循“让权等待” 的准则，而是使进程处于“忙等”的状态#②记录型信号量是不存在“忙等”现象的进程同步机制。除了需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L，用于链接所有等待该资源的进程，记录型信号量是由于釆用了记录型的数据结构得名。##①利用信号量实现同步：#②利用信号量实现互斥：

....

semaphore full=0;                      //满缓冲区数目 semaphore empty=n;                     //空缓冲区数目  semaphore mutex=1;                     //对有界缓冲区进行操作的互斥信号量  producer ()                            //生产者进程{                                while(true)    {          produce an item put in nextp;  //生产数据（nextp为临时缓冲区）          P(empty);                      //申请一个空缓冲区          P(mutex);                      //申请使用缓冲池         add nextp to buffer;           //将数据放入缓冲池          V(mutex);                      //缓冲池使用完毕,释放互斥信号量          V(full);                       //增加一个满缓冲区      }  }    consumer ()                            //消费者进程{      while(true)    {          P(full);                       //申请一个满缓冲区          P(mutex);                      //申请使用缓冲池          remove an item from buffer;    //从缓冲区中取出数据          V (mutex);                     //缓冲池使用完毕,释放互斥信号量          V (empty) ;                    //增加一个空缓冲区          consume the item in nextc;     //消费数据      }  }

....

semaphore rmutex=1;              //初始化信号量rmutex，保证对于readcount的互斥访问semaphore mutex=1;               //初始化信号量mutex， 保证对于数据区的写互斥 int readcount=0;                 //用于记录读者数量，初始为0  reader ()                        //读者进程 {       while(true)                  //循环执行这段代码    {          P (rmutex) ;             //申请readcount的使用权限          if (readcount==0)        //如果此为第一个读者，要阻止写者进入              P(mutex);          readcount++;             //读者计数器加1          V (rmutex) ;             //释放readcount的使用权限，允许其他读者使用          reading;                 //进行读操作          P (rmutex) ;             //申请readcount的使用权限，要对其进行操作         readcount--;             //读者计数器减1          if (readcount==0)        //如果没有读者了，则允许写者进入              V(mutex) ;          V (rmutex) ;             //释放readcount的使用权限，允许其他读者使用    }  }  writer ()                        //写者进程 {       while (true)    {          P(mutex);                //申请对数据区进行访问          Writing;                 //进行写操作         V(mutex) ;               //释放数据区，允许其他进程读写      }  }

semaphore mutex = 1;         //初始化mutex， 用于控制互斥访问数据区  semaphore rmutex=1;          //初始化rmutex，用于读者互斥访问readcount semaphore wmutex=1;          //初始化wmutex，用于存在写者时禁止新读者进入 int readcount = 0;           //用于记录当前的读者数量，初始为0   reader ()                    //读者进程{        while (true)    {          P (wmutex) ;         //检测是否有写者存在，无写者时进入          P (rmutex);          //申请使用readcount            if (readcount==0)    //如果此为第一个读者，要阻止写者进入              P(mutex);          readcount++;         //读者计数器加1          V (rmutex) ;         //释放readcount的使用权限，允许其他读者使用          V(wmutex);           //恢复wmutex         reading;             //读操作          P (rmutex) ;         //申请readcount的使用权，要对其进行操作         readcount--;         //读者计数器减1            if (readcount==0)    //如果没有读者，则释放数据区，允许写者进入              V(mutex);                V (rmutex);          //释放recount的使用权，允许其他读者使用    }  }  writer()                     //读者进程{      while(true)    {          P(wmutex);           //检测是否有其他写者存在，无写者时进入          P(mutex);            //申请对数据区进行访问          writing;             //写操作          V(mutex);            //释放数据区，允许其他进程读写          V(wmutex);           //恢复wmutex            }  }

semaphore mutex = 1;         //初始化mutex， 用于控制互斥访问数据区  semaphore rmutex=1;          //初始化rmutex，用于读者互斥访问readcount semaphore wmutex=1;          //初始化wmutex，用于存在写者时禁止新读者进入 semaphore readable=1;        //初始化readable，用于表示当前是否有写者 int readcount = 0;           //用于记录当前的读者数量，初始为0   int writecount = 0;          //用于记录当前的写者数量，初始为0   reader ()                    //读者进程{        while (true)    {          P (readable) ;       //检测是否有写者存在，若没有，则占用，进行后续操作          P (rmutex);          //占用rmutex，准备修改readcount            if (readcount==0)    //如果此为第一个读者，则占用数据区              P(mutex);          readcount++;         //读者计数器加1          V (rmutex) ;         //释放rmutex，允许其他读者访问readcount        V (readable);        //释放readable，允许其他读者或者写者占用         reading;             //读操作          P (rmutex) ;         //占用rmutex，准备修改readcount         readcount--;         //读者计数器减1            if (readcount==0)    //若为最后一个读者，则释放数据区            V(mutex);                V (rmutex);          //释放rmutex，允许其他读者访问readcount    }  } writer(){      while(true)    {          P(wmutex);           //占用rmutex，准备修改writecount          if (writecount==0)   //若为第一个写者，则阻止后续读者进入            P(readable);        writecount++;        //写者计数器加1        V(wmutex);           //释放wmutex，允许其他写者修改writecount         P(mutex);            //等当前正在操作的读者或者写者完成后，占用数据区          writing;             //写操作          V(mutex);            //写完，释放数据区          P(wmutex) ;          //占用wmutex，准备修改writecount        writecount--;        //写者计数器减1        if (writecount==0)   //若为最后一个写者，则允许读者进入            V(readable);        V(wmutex);           //释放wmutex，允许其他写者修改writecount             }  }

semaphore chopstick[5] = {
    1,1,1,1,1};   //初始化信号量  Philosopher(int=i)                      //i=1,2,3,4,5;i号哲学家的进程{       while(true)    {          思考;        想吃饭;        if(i%2!=0)                      //判断是否为奇数号哲学家        {                               //若为奇数号哲学家，则先拿左边筷子            P (chopstick [i]) ;                       P (chopstick[ (i+1) %5]) ;                 进餐;              V(chopstick[i] ) ;          //放回左边筷子              V(chopstick[ (i+l)%5]) ;    //放回右边筷子          }                else                            //若为偶数号哲学家，则先拿左边筷子        {            P (chopstick[ (i+1) %5]) ;              P (chopstick [i]) ;             进餐;            V(chopstick[ (i+l)%5]) ;              V(chopstick[i] ) ;         }    } }

....

int waiting=0;               //顾客数量，包括正在理发的，最大为n+1semaphore mutex=1;           //用于互斥操作watingsemaphore bchair=1;          //代表理发椅的信号量semaphore wchair=1;          //代表凳子的信号量semaphore ready=finish=0;    //用于同步理发师与顾客的信号量barber()                     //理发师进程{    while(true)    {        P(ready);            //有顾客坐在理发椅上准备好了        理发;                        V(finish);           //理发完毕，提醒顾客离开    }}customer()                   //顾客进程{    P(mutex);                //申请使用waiting变量    if(waiting <=n)          //如果还有空位置（包括理发椅和凳子），就留下    {        waiting++;           //顾客人数+1        V(mutex);            //允许其他顾客使用waiting变量    }    else                     //如果没有位置了    {        V(mutex);            //允许其他顾客使用waiting变量        离开;                //顾客离开，顾客进程结束，不再继续执行    }    P(wchair);               //先找一个空凳子坐下    P(bchair);               //再等待理发椅空闲后座上理发椅    V(wchair);               //释放刚才坐的凳子    V(ready);                //告诉理发师自己准备好了    P(finish);               //等待理发完成    V(bchair);               //释放理发椅    P(mutex);                //申请使用waiting变量    waiting--;                 //顾客人数-1     V(mutex);                 //允许其他顾客使用waiting变量}

int chairs=n+1;       //为顾客准备的凳子和理发椅的数量semaphore mutex=1;    //表示等待理发的顾客数量，初始值为0semaphore ready=0;    //理发师初始状态为空闲semaphore finish=1;   //互斥信号量barber(){    while(true)    {                 //理完一个人，查看是否还有顾客        P(ready);     //看看有没有顾客，如果没有就阻塞        理发;         //        P(mutex);     //理发结束，对chairs进行操作        chairs++;     //顾客走掉，座位空余一个        V(mutex);     //允许其他进程访问chairs        V(finish);    //理发师空闲，可以为下一个顾客理发    }}customer(){    P(mutex);         //申请使用chairs变量    if(chairs >0)     //如果当前有空余座位    {        chairs--;     //占用一个座位        V(mutex);     //允许其他进程访问chairs        V(ready);     //等待理发，唤醒理发师        P(finish);    //当理发师空闲时开始理发    }    else              //没有空余座位，准备离开    {        V(mutex);     //释放mutex，允许其他进程访问chairs    }}

#管程：由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块。

#死锁：多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。##可剥夺资源：  虽然资源占有者进程需要使用该资源，但另一个进程可以强行把该资源从占有者进程处剥夺来归自己使用。#不可剥夺资源：除占有者进程不再需要使用该资源而主动释放资源，其他进程不得占有者进程使用资源过程中强行剥夺。##原因：1.对互斥资源的分配不当：只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源的竞争是不会引起死锁的。#      2.进程推进顺序不当：请求和释放资源的顺序不当，也同样会导致死锁。##必要条件：1.互斥：进程要求对所分配的资源进行排他性控制，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。#          2.不剥夺：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放)。#          3.请求与保持：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。#          4.环路等待：存在一种进程资源的循环等待链，链中每一个进程已获得的资源同时被链中下一个进程所请求。##处理策略：1.鸵鸟算法：像鸵鸟一样对死锁视而不见，即不理睬死锁。#          2.预防死锁：设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个，以防止发生死锁。#                优点：适用于做突发式处理的进程，不必进行剥夺#                缺点：效率低，进程初始化时间延长；剥夺次数过多；不便灵活申请新资源#          3.避免死锁：在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁。#                优点：不必进行剥夺#                缺点：必须知道将来的资源需求；进程不能被长时间阻塞#          4.死锁的检测及解除：无需釆取任何限制性措施，允许进程在运行过程中发生死锁。通过系统的检测机构及时地检测出死锁的发生，然后釆取某种措施解除死锁。#                优点：不延长进程初始化时间，允许对死锁进行现场处理#                缺点：通过剥夺解除死锁，造成损失##预防死锁的策略：防止死锁的发生只需破坏死锁产生的四个必要条件之一即可。#                1.破坏互斥条件：有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行#                2.破坏不剥夺条件：常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源#                3.破坏请求和保持条件：系统资源被严重浪费，而且还会导致“饥饿”现象#                4.破坏循环等待条件：编号必须相对稳定，这种按规定次序申请资源的方法，也必然会给用户的编程带来麻烦。##死锁避免的策略：在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。#                1.系统安全状态#                2.银行家算法#                  思想：避免系统进入不安全状态。在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，如果有，则先进行分配，并对分配后的新状态进行安全性检查。如果新状态安全，则正式分配上述资源，否则就拒绝分配上述资源。这样，它保证系统始终处于安全状态，从而避免死锁现象的发生。###死锁的检测及解除的策略#

#死锁：多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。#饥饿：一个就绪进程所申请的资源总是被优先于自己的其他进程占有，而始终处于不能被调度执行的状态。#饿死：当饥饿到一定程度，进程所赋予的任务即使完成也不再有实际意义，该进程被饿死。

第三章《内存管理》

#内存管理：操作系统对内存的划分和动态分配

#逻辑地址空间：面向用户和程序员的地址空间    #物理地址空间：内存中物理单元的集合，是地址转换的最终地址，进程在运行时执行指令和访问数据组以后都要通过物理地址来存取主存。#

#静态链接：在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的可执行程序，以后不再拆开。#装入时动态链接：将应用程序编译后所得到的一组目标模块，在装入内存时，釆用边装入边链接的链接方式。#运行时动态链接：在程序执行中需要该目标模块时，才对它进行的链接。其优点是便于修改和更新，便于实现对目标模块的共享。

#重定位：通过地址转换将逻辑地址转换为物理地址#静态重定位：将一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。作业一旦进入内存后，在整个运行期间不能在内存中移动，也不能再申请内存空间。#动态重定位：可以将程序分配到不连续的存储区中；在程序运行之前可以只装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间。#

#内存覆盖：把用户空间分成一个固定区和若干个覆盖区。首先将那些即将要访问的段放入覆盖区，其他段放在外存中，在需要调用前，系统再将其调入覆盖区，替换覆盖区中原有的段。#内存交换：把处于等待状态的程序从内存移到辅存，把内存空间腾出来，这一过程又叫换出；把准备好竞争CPU运行的程序从辅存移到内存。#

#连续分配方式：是指为一个用户程序分配一个连续的内存空间##①单一连续分配：单用户、单任务，产生内部碎片#②固定分区分配：内存分区的大小固定，产生内部碎片#③动态分区分配：产生外部碎片#        1.首次适应(First  Fit)算法：空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。#        2.下次适应(Next   Fit)算法：又称循环首次适应算法，由首次适应算法演变而成。不同之处是分配内存时从上次查找结束的位置开始继续查找。    #        3.最佳适应(Best   Fit)算法：空闲分区按容量递增形成分区链，找到第一个能满足要求的空闲分区。#        4.最坏适应(Worst  Fit)算法：又称最大适应(Largest Fit)算法，空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区，也就是挑选出最大的分区。

#非连续分配：允许一个程序分散地装入到不相邻的内存分区中##①分页存储管理方式：把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。#②分段存储管理方式：按照用户进程中的自然段划分逻辑空间。#③段页式存储管理方式：作业的地址空间首先被分成若干个逻辑段，每段都有自己的段号，然后再将每一段分成若干个大小固定的页。#

#虚拟内存技术：建立了 “内存一外存”的两级存储器的结构，利用局部性原理（时间局限性+空间局限性）实现髙速缓存。   #           1.时间局限性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问，都集中在一个较短的时期内。#           2.空间局限性：当前指令和邻近的几条命令，当前访问的数据和邻近的数据，都集中在一个较小的区域内。

#产生背景：分页存储管理方式虽然解决了内存中的外部碎片问题，但它要求将作业的所有页面一次性调入主存。当主存可用空间不足或作业太大时，这就限制一写作业进入主存运行。##概念：只要求将当前需要的一部分页面装入内存，便可以启动作业运行。在作业执行过程中，当所要访问的页面不在内存时，再通过调页功能将其调入，同时还可以通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间。除了需要一定容量的内存及外存的计算机系统，还需要有页表机制、缺页中断机构和地址变换机构。#   1.页表机制：#   2.缺页中断机构：#   3.地址变换机构：

#①最佳置换算法(OPT)：选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。#②先进先出(FIFO)页面置换算法：优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。#③最近最久未使用(LRU)置换算法：选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。#④时钟(CLOCK)置换算法：LRU算法的性能接近于OPT,但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体。#

#页面抖动：频繁的页面调度行为#工作集：在某段时间间隔内，进程要访问的页面集合。

第四章《文件管理》

#文件：具有文件名的一组相关信息的集合#文件系统：操作系统中与文件管理有关的那部分软件，以及被它们管理的文件和文件属性的集合#数据项：文件系统中最低级的数据组织形式，分为基本数据项和组合数据项#记录：已自相关的数据项的集合，用于描述一个对象在某方面的属性

#①名称：文件名称唯一，以容易读取的形式保存。#②标识符：标识文件系统内文件的唯一标签,通常为数字，它是对人不可读的一种内部名称。#③类型：被支持不同类型的文件系统所使用。#④位置：指向设备和设备上文件的指针。#⑤大小：文件当前大小（用字节、字或块表示），也可包含文件允许的最大值。#⑥保护：对文件进行保护的访问控制信息。#⑦时间、日期和用户标识：文件创建、上次修改和上次访问的相关信息，用于保护、 安全和跟踪文件的使用。

#①创建文件#②写文件#③读文件#④文件重定位（文件寻址）#⑤删除文件#⑥截断文件

#①文件逻辑结构：指用户概念中的文件，独立于物理结构，又称逻辑文件#②文件物理结构：#       1.顺序结构：是把一个逻辑上连续的记录构成的文件分配到连续的物理块中。#       2.链接结构：把文件信息存放在非连续的物理块中，每个物理块均设有一个指针指向其后续连续的另一个物理块，从而使得存放同一文件的物理块链接成一个串联队列。链接方式又分为显式链接和隐式链接。显式链接的链接指针在专门的链接表中，隐式链接的指针在存放文件信息的物理块中。#       3.索引结构：指为每个文件建立一个索引表，其中每一个表项指出文件记录所在的物理块号，表项按逻辑记录编写，顺序或按记录内某一关键字顺序排列，对于大文件，为检索方便，可以建立多级索引，还可以把文件索引表也作为一个文件，称为索引表文件。#       4.多重索引结构：一级索引，二级索引，多级索引

#文件目录：为实现“按名存取”，必须建立文件名与外存空间中的物理地址的对应关系，体现这种对应关系的数据结构称为目录。#文件目录管理基本要求（功能）：#                     1.实现“按名存取”：用户只需提供文件名，即可对文件进行存取#                     2.提高索引速度：#                     3.允许文件同名：#                     4.实现文件共享：允许不同的用户使用同一个文件。###文件目录组织形式：1.单级目录结构：在整个文件系统中只建立一张目录表，每个文件占一个目录项。#                  2.两级目录结构：单级目录很容易造成文件名称的混淆，可以考虑釆用两级方案，将文件目录分成主文件目录和用户文件目录两级。#                  3.多级目录结构（树形目录结构)：树形结构中根节点为第一级目录，非叶子节点均为目录文件，叶子节点为文件。

#文件系统是指操作系统中与文件管理有关的软件和数据的集合。#文件系统的层次结构：基本I/O控制层、基本文件系统层、基本I/O管理程序层、逻辑文件系统层#1.基本I/O控制层：#2.基本文件系统层：#3.基本I/O管理程序层：#4.逻辑文件系统层：

#在读文件前，必须先打开文件。打开文件时，操作系统利用路径名找到相应目录项，目 录项中提供了查找文件磁盘块所需要的信息。#①线性列表：#②哈希表：

#文件实现：文件的实现是依据文件的物理结构来实施的。文件的实现要使用多个磁盘和内存结构。##①外存分配方式：#           1.连续分配：#           2.链接分配：#           3.索引分配：#②文件存储空间管理：

#读写一次磁盘所需的时间可分为以下几种：#        1.设备等待：设备或总线忙，需要等候#        2.寻道时间：将读/写磁头移动到相应的柱面所花费的时间#        3.旋转延迟时间：扇区转到磁头位置所需的时间#        4.传输时间：数据写入磁盘或从磁盘读出的时间##磁盘访问时间=寻道时间+旋转延迟时间+传输时间

#①先来先服务（FCFS）调度：      根据进程请求访问磁盘的时间顺序，先来先服务。#②最短寻道时间优先（SSTF）调度：根据磁头的当前位置首先将请求队列中距磁头最短的请求为之服务。饥饿现象#③扫描算法（SCAN）调度：        也叫“电梯”算法，磁头固定从外向内然后从内向外逐柱面运动。如此往复。避免饥饿现象#④循环扫描（C-SCAN）调度：      扫描算法（SCAN）的改进，规定磁头单向移动

第五章《设备管理》

#设备管理的主要任务之一是控制设备和内存或处理机之间的数据传送，外围设备和内存之间的 I/O 控制方式有四种：#①程序访问控制方式#②中断控制方法#③DMA 方式#④通道方式

#I/O调度就是确定一个好的顺序来执行这些I/O请求。

#缓冲区：  内存划出一块存储区，专门用来临时存放输入/输出数据，这个区域成为缓冲区。#高速缓存：是可以保存数据备份的高速存储器。访问高速缓存要比访问原始数据更高效，速度更快。

#是指在多道程序环境下，利用多道程序中的一道或两道程序来模拟脱机输入输出中的外围控制机的功能，以达到“脱机”输入输出的目的。