（计算机基础 核心知识）操作系统

1.进程的状态与状态转换

就绪 执行 阻塞

挂起和激活

进程在运行时有三种基本状态：就绪态、运行态和阻塞态。

1. 运行（running）态：进程占有处理器正在运行的状态。进程已获得CPU，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态； 在多处理机系统中，则有多个进程处于执行状态。
2. 就绪（ready）态：进程具备运行条件，等待系统分配处理器以便运行的状态。 当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行，进程这时的状态称为就绪状态。在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。
3. 阻塞（wait）态：又称等待态或睡眠态，指进程不具备运行条件，正在等待某个时间完成的状态。

各状态之间的转换：

1. 就绪→执行 处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态转变成执行状态。
2. 执行→就绪 处于执行状态的进程在其执行过程中，因分配给它的一个时间片已用完而不得不让出处理机，于是进程从执行状态转变成就绪状态。
3. 执行→阻塞 正在执行的进程因等待某种事件发生而无法继续执行时，便从执行状态变成阻塞状态。
4. 阻塞→就绪 处于阻塞状态的进程，若其等待的事件已经发生，于是进程由阻塞状态转变为就绪状态。

挂起（Suspended）状态是一种进程状态，表示进程暂时停止执行，但仍然保留在内存中或被交换出到磁盘。挂起状态通常分为两种：

1. 就绪挂起（Ready Suspended）：进程在内存之外（通常在磁盘上），一旦被调入内存即可进入就绪状态，等待CPU时间片。
2. 阻塞挂起（Blocked Suspended）：进程被阻塞并且已被调出内存，等待某个事件完成后可以重新进入内存并变为阻塞状态。

2.join，detach函数

join方法的作用是阻塞主进程（挡住，无法执行join以后的语句），专注执行多线程

Join的作用是众所周知的，阻塞直到线程执行完毕

# coding: utf-8
# 测试多线程中join的功能
import  threading, time 
def  doWaiting(): 
     print  'start waiting1: '  +  time.strftime( '%H:%M:%S' )  +  "\n" 
     time.sleep( 3 ) 
     print  'stop waiting1: '  +  time.strftime( '%H:%M:%S' )  +  "\n"
def  doWaiting1(): 
     print  'start waiting2: '  +  time.strftime( '%H:%M:%S' )  +  "\n"  
     time.sleep( 8 ) 
     print  'stop waiting2: ' , time.strftime( '%H:%M:%S' )  +  "\n" 
tsk  =  []   
thread1  =  threading.Thread(target  =  doWaiting) 
thread1.start() 
tsk.append(thread1)
thread2  =  threading.Thread(target  =  doWaiting1) 
thread2.start() 
tsk.append(thread2)

print  'start join: '  +  time.strftime( '%H:%M:%S' )  +  "\n"  
for  tt  in  tsk:
     tt.join()
        
print  'end join: '  +  time.strftime( '%H:%M:%S' )  +  "\n"
start waiting1:  22 : 54 : 09
 
start waiting2:  22 : 54 : 09
 
start join:  22 : 54 : 09
 
stop waiting1:  22 : 54 : 12
 
stop waiting2:   22 : 54 : 17
 
end join:  22 : 54 : 17
 
Process finished with exit code  0

可以看到，两个线程并行执行，进程1在3s后结束，进程2在8s后结束，然后回到主进程，执行打印「end join」

public class IOText {
    public static void main(String[] args) throws IOException, InterruptedException {
        Father fa=new Father();
        fa.start();

    }
}


class Father extends Thread{
    @Override
    public void run() {
        System.out.println("父亲想抽烟，摸口袋发现没烟了");
        System.out.println("拿出钱让儿子去买烟");
-
        try {
            son.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("父亲接过烟");
        System.out.println("把零钱给了儿子");
    }
}
class Son extends Thread{
    @Override
    public void run() {
        System.out.println("儿子出门去买烟");
        System.out.println("路上偶遇一家游戏厅进去玩游戏");
        for(int i=0;i<20;i++){
            try {
                Thread.sleep(1000);
                System.out.println(i+"分钟过去了");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        System.out.println("记起来要买烟");
        System.out.println("买了一包中华后回家");
        System.out.println("将烟交给父亲");
    }
}

插入到当前线程的头部

detach调用之后，目标线程就成为了守护线程，驻留后台运行，与之关联的std::thread对象失去对目标线程的关联，无法再通过std::thread对象取得该线程的控制权，由操作系统负责回收资源；主线程结束，整个进程结束，所有子线程都自动结束了！

#include <iostream>
#include <thread>
using namespace std;

void func()
{
   for(int i = -10; i > -20; i--)
    {
        cout << "from func():" << i << endl;
    }
}

int main()			//主线程
{
	cout << "mian()" << endl;
    cout << "mian()" << endl;
    cout << "mian()" << endl;
	thread t(func);	//子线程
	t.detach();		//分离子线程
	return 0;
}

可以明显看到，主线程太快了，还没等子线程运行就结束了

3.计算机开机过程

CS 为代码段寄存器，而 IP 为指令指针寄存器。

在8086机中，任意时刻，CPU将CS:IP指向的内容当作指令来执行。

其实随着x86的发展，第一条指令的地址并不是一成不变的 8086：CPU reset之后cs寄存器的值是0xFFFF，ip寄存器的值是0x0，所以形成的物理地址是0xFFFF0，这个地址就是1M往下16字节的位置 80286：CPU reset之后cs寄存器的值是0xF000，ip寄存器的值是0xFFF0，所以形成的物理地址也是0xFFFF0 80386：到了386时代一切都变了，此时在CPU reset之后cs寄存器的值仍然是0xF000，但是cs除了段选择子之外还有一个隐藏的基址寄存器，这个寄存器的值是0xFFFF0000，ip寄存器的值仍然是0xFFF0。此时的地址不在是0xF000左移4位加上0xFFF0了，而是0xFFFF0000 + 0xFFF0 = 0xFFFFFFF0。所以第一条指令是在一个很高的地址，是4G往下16字节的位置。

第一步： 当我们按下电源开关时，电源就开始向主板和其它设备供电，此时电压还不太稳定，主板上的控制芯片组会向cpu发出并保持一个reset（重置）信号，让cpu内部自动恢复到初始状态，但cpu在此刻不会马上执行指令。当芯片组检测到电源已经开始稳定供电了（当然从不稳定到稳定的过程只是一瞬间的事情），它便撤去reset信号，cpu马上就从地址ffff0h处开始执行指令，从前面的介绍可知，这个地址实际上在系统bios的地址范围内，无论是award bios还是ami bios，放在这里的只是一条跳转指令，跳到系统bios中真正的启动代码处。

第二步： 系统bios的启动代码首先要做的事情就是进行post（power－on self test，加电后自检），post的主要任务是检测系统中一些关键设备是否存在和能否正常工作，例如内存和显卡等设备。由于post是最早进行的检测过程，此时显卡还没有初始化，如果系统bios在进行post的过程中发现了一些致命错误，例如没有找到内存或者内存有问题（此时只会检查640k常规内存），那么系统bios就会直接控制喇叭发声来报告错误，声音的长短和次数代表了错误的类型。在正常情况下，post过程进行得非常快，我们几乎无法感觉到它的存在，post结束之后就会调用其它代码来进行更完整的硬件检测。

第三步： 接下来系统bios将查找显卡的bios，前面说过，存放显卡bios的rom芯片的起始地址通常设在c0000h处，系统bios在这个地方找到显卡bios之后就调用它的初始化代码，由显卡bios来初始化显卡，此时多数显卡都会在屏幕上显示出一些初始化信息，介绍生产厂商、图形芯片类型等内容，不过这个画面几乎是一闪而过。系统bios接着会查找其它设备的bios程序，找到之后同样要调用这些bios内部的初始化代码来初始化相关的设备。

第四步： 查找完所有其它设备的bios之后，系统bios将显示出它自己的启动画面，其中包括有系统bios的类型、序列号和版本号等内容

5.启动顺序 硬件自检结束后，BIOS这个时候将控制权交给下一阶段的启动程序，但是这个时候BIOS需要知道“下一个阶段要启动的程序具体放在了哪一个设备上”也就是我们平时说的BIOS下的启动顺序，但排在第一位的是优先转交的设备，这个叫做启动顺序。启动顺序，我们日常工作中可以开机进入BIOS的去调节启动设备的优先级。

6.主引导记录 BIOS按照设定好的启动顺序，将控制权交给排在第一位的存储设备，即开始从第一位设备中读取设备的MBR，并且将程序放在0x7c000的内存地址位中。MBR：存储设备中的第一个扇区，磁盘最前面的512Byte，称为“主引导扇区”（Master boot record，缩写为MBR）这个时候计算机会去读取该设备的第一个扇区，也就是读取最前面的512个字节。如果这512个字节的最后两个字节是0x55和0xAA，表明这个设备可以用于启动；如果不是，表明设备不能用于启动，BIOS会继续去找下一个设备，并将控制权转交给”启动顺序”中的下一个设备。

7.硬盘启动 这时，计算机要将控制权转交给硬盘的某个分区，但是分区又会出现几种情况：卷引导记录四个分区中，只有一个是激活的，计算机开始读取激活的第一个扇区，叫“卷引导记录"（Volume boot record，缩写为VBR）卷引导记录主要作用：告诉计算机，操作系统在这个分区，可以开始加载操作系统

8.操作系统启动 控制权转交给操作系统后，操作系统的内核被载入内存。以Linux系统为例，先载入/boot目录下面的kernel。内核加载成功后，第一个运行的程序是/sbin/init。它根据配置文件（Debian系统是/etc/initab）产生init进程。这是Linux启动后的第一个进程，pid进程编号为1，其他进程都是它的后代。然后，init线程加载系统的各个模块，比如窗口程序和网络程序，直至执行/bin/login程序，跳出登录界面，等待用户输入用户名和密码。

4.进程线程 协程 及它们区别 & 多线程模型

进程：进程是由程序段、数据段和进程控制块组成，是系统进行资源分配和调度的一个独立单元。（多线程后无法进行独立调度了）

进程控制块process control block，一个数据结构，进程存在的唯一标志. 系统通过PCB来了解进程的状态信息,以便控制和管理。

线程：线程是进程中的一个实体，是CPU调度和分派的基本单位，线程自己不拥有系统资源。

引入进程的目的是为了更好地使多道程序并发执行，以提高资源利用率和系统吞吐量，引入线程是为了减少程序在并发执行时所付出的时空开销，提高操作系统的并发性能。

比较：线程是独立调度的基本单元，进程是拥有资源的基本单元。进程的地址空间之间互相独立，同一进程的各个线程共享进程的地址空间。

一个程序至少有一个进程,一个进程至少有一个线程

线程是属于进程的，线程运行在进程空间内，同一进程所产生的线程共享同一内存空间，当进程退出时该进程所产生的线程都会被强制退出并清除。线程可与属于同一进程的其它线程共享进程所拥有的全部资源

1. 一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程依赖于进程而存在。
2. 进程在执行过程中拥有独立的地址空间，而多个线程共享进程的地址空间。（资源分配给进程，同一进程的所有线程共享该进程的所有资源。同一进程中的多个线程共享代码段（代码和常量），数据段（全局变量和静态变量），扩展段（堆存储）。但是每个线程拥有自己的栈段，栈段又叫运行时段，用来存放所有局部变量和临时变量。）
3. 进程是资源分配的最小单位，线程是CPU调度的最小单位。
4. 通信：由于同一进程中的多个线程具有相同的地址空间，使它们之间的同步和通信的实现，也变得比较容易。进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信（需要一些同步方法，以保证数据的一致性）。
5. 进程编程调试简单可靠性高，但是创建销毁开销大；线程正相反，开销小，切换速度快，但是编程调试相对复杂。
6. 进程间不会相互影响；一个进程内某个线程挂掉将导致整个进程挂掉。
7. 进程适应于多核、多机分布；线程适用于多核。

因为多线程没有内存隔离，单个线程崩溃会导致整个应用程序的退出

这句话不完全准确。协程（Coroutine）的特点并不是“一个线程执行”，而是它提供了一种不同于线程的程序执行方式。要理解协程，我们需要先区分它与线程的主要差异：

1. 执行方式和上下文切换： 线程：是操作系统能够进行调度的最小单位，具有独立的执行上下文。当操作系统进行线程切换时，涉及到上下文的保存和恢复，这是一个相对重量级的操作。协程：通常是在用户态下实现的轻量级“线程”。协程的切换是在用户空间内进行的，不需要操作系统介入，因此上下文切换的成本比线程低得多。
2. 控制方式： 线程：通常由操作系统进行抢占式调度，程序员对线程的控制粒度相对较粗。协程：它的调度完全由程序控制（协作式调度），这意味着协程的切换是在程序代码中显式进行的。
3. 资源消耗： 线程：每个线程都有自己的堆栈，线程数量过多会占用大量内存资源，并且线程切换有一定的开销。协程：相对线程来说，协程更轻量，可以在单个线程中运行多个协程，每个协程占用的资源比线程少。

总的来说，协程是一种用户态的轻量级线程，它的特点是协作式的任务切换、低开销以及高效的并发处理能力。不过，协程的执行仍然依赖于线程，但它可以在单个线程内实现多任务的并发执行。

多线程模型

1. 多对一模型。将多个用户级线程映射到一个内核级线程上。该模型下，线程在用户空间进行管理，效率较高。缺点就是一个线程阻塞，整个进程内的所有线程都会阻塞。几乎没有系统继续使用这个模型。
2. 一对一模型。将内核线程与用户线程一一对应。优点是一个线程阻塞时，不会影响到其它线程的执行。该模型具有更好的并发性。缺点是内核线程数量一般有上限，会限制用户线程的数量。更多的内核线程数目也给线程切换带来额外的负担。linux和Windows操作系统家族都是使用一对一模型。
3. 多对多模型。将多个用户级线程映射到多个内核级线程上。结合了多对一模型和一对一模型的特点。

5.线程（进程）同步方式

同步就是协同步调，按预定的先后次序进行运行。如：你说完，我再说。这里的同步千万不要理解成那个同时进行，应是指协同、协助、互相配合。线程同步是指多线程通过特定的设置（如互斥量，事件对象，临界区）来控制线程之间的执行顺序（即所谓的同步）也可以说是在线程之间通过同步建立起执行顺序的关系，如果没有同步，那线程之间是各自运行各自的！

线程互斥是指对于共享的进程系统资源，在各单个线程访问时的排它性。当有若干个线程都要使用某一共享资源时，任何时刻最多只允许一个线程去使用，其它要使用该资源的线程必须等待，直到占用资源者释放该资源。线程互斥可以看成是一种特殊的线程同步（下文统称为同步）。

通过信号量机制，整型信号量，记录型信号量，AND型信号量，信号量集

操作系统中，进程是具有不同的地址空间的，两个进程是不能感知到对方的存在的。有时候，需要多个进程来协同完成一些任务。 当多个进程需要对同一个内核资源进行操作时，这些进程便是竞争的关系，操作系统必须协调各个进程对资源的占用，进程的互斥是解决进程间竞争关系的方法。 进程互斥指若干个进程要使用同一共享资源时，任何时刻最多允许一个进程去使用，其他要使用该资源的进程必须等待，直到占有资源的进程释放该资源。 当多个进程协同完成一些任务时，不同进程的执行进度不一致，这便产生了进程的同步问题。需要操作系统干预，在特定的同步点对所有进程进行同步，这种协作进程之间相互等待对方消息或信号的协调关系称为进程同步。进程互斥本质上也是一种进程同步。 进程的同步方法：

把整型信号量定义为一个表示资源数目的整型量S，除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。

wait(S)和signal(S)操作可以描述为：

wait(S):  while S <= 0 do no-op;
      S:=S-1;
signal(S):  S:=S+1;

wait(S)和signal(S)是两个原子操作，它们在执行时是不可中断的。当一个进程在修改某信号量时，没有其他进程能同时对该信号量进行修改。

在整型信号量机制中的wait操作中，只要是信号量S<=0，就会不断地测试。因此该机制没有遵循“让权等待”准则，而是使进程处于“忙等”的状态

记录型信号量的wait(S)和signal(S)操作可以描述为：

procedure wait(S)
  var S: semaphore;
  begin
    S.value:=S.value-1;
    if S.value < 0 then block(S.L);
  end
procedure signal(S)
  var S: semaphore;
  begin
    S.value:=S.value+1;
    if S.value<=0 then wakeup(S.L);
  end

S.value的初值表示系统中某类资源的数目，被称为资源信号量。

对它每次wait操作，意味进程请求一个单位的该类资源，使得系统中可分配的该类资源数减少一个，因此描述为S.value:=S.value-1；当S.value<0时，表示资源分配完毕，因此该访问进程应调用block原语进行自我阻塞放弃处理机，并插入到信号量链表S.L中，此时S.value的绝对值表示该信号量链表中已阻塞进程的数目。可见该机制遵循了“让权等待”准则。

对信号量的每次signal操作表示执行进程释放一个单位资源，使得系统中可供分配的该类资源数增加一个，因此表示为S.value:=S.value+1。如果+1后仍然是S.value<=0，说明信号量链表中仍然有等待该资源的进程被阻塞，因此还应调用wakeup原语将S.L链表中的第一个等待进程唤醒。

如果S.value的初值为1，表示允许一个进程访问临界资源，此时的信号量转化为互斥信号量用于进程互斥。

AND型信号量（AND Semaphore）：

• AND型信号量是一种允许一组进程或线程同时等待多个信号量的高级同步机制。
• 它通常用于那些需要等待一组条件全部满足才能继续执行的场景。比如，在多元共享资源的情况下，一个进程可能需要所有必需资源都空闲才能执行。

信号量集（Semaphore Set）：

• 信号量集是多个信号量的集合，通常是整型信号量的集合，它们可以一起被分配和操作。
• 这提供了一种方便的方式，用一次系统调用来管理一组信号量，而不是分别对每个信号量进行操作。
• 信号量集常被用于有关联的多个资源的同步控制。

6.进程通信方式

管道通信

• 匿名管道( pipe )：管道是一种半双工的通信方式，而且只能在具有亲缘关系的进程间使用
• 有名管道 (named pipe) ： 有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。

注意，管道不是通道

半双工（Half-Duplex）通信是指一个通信信道上的数据传输方式，其中数据流只能在一个时间点上按一个方向传输。也就是说，在任意时刻，信息可以从A点传到B点或从B点传到A点，但这两个方向的传输不能同时进行。

消息队列通信

消息队列( message queue ) ： 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

信号量通信

信号量( semophore ) ： 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

共享内存通信

套接字通信

套接字( socket ) ： 套接口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同机器间的进程通信。

每个进程各自有不同的用户地址空间,任何一个进程的全局变量在另一个进程中都看不到，所以进程之间要交换数据必须通过内核,在内核中开辟一块缓冲区,进程A把数据从用户空间拷到内核缓冲区,进程B再从内核缓冲区把数据读走,内核提供的这种机制称为进程间通信。

不同进程间的通信本质：进程之间可以看到一份公共资源；而提供这份资源的形式或者提供者不同，造成了通信方式不同。

进程间通信又叫IPC (InterProcess Communication）是指在不同进程之间传播或交换信息。 IPC的方式通常有管道（包括无名管道和命名管道）、消息队列、信号量、共享存储、Socket。 Socket支持不同主机上的两个进程IPC。

共享内存通信

它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。

特点：

1. 共享内存是最快的一种IPC，因为进程是直接对内存进行操作来实现通信，避免了数据在用户空间和内核空间来回拷贝。
2. 因为多个进程可以同时操作，所以需要进行同步处理。
3. 信号量和共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。

7.缓冲区溢出、危害、原因

缓冲区溢出是指当计算机向缓冲区填充数据时超出了缓冲区本身的容量，溢出的数据覆盖在合法数据上

危害有以下两点：

1、程序崩溃，导致拒绝服务

2、跳转并且执行一段恶意代码（淹没了返回地址。这是栈溢出原理的核心所在，通过淹没的方式修改函数的返回地址，使程序代码执行“意外”的流程！）

原因：造成缓冲区溢出的主要原因是程序中没有仔细检查用户输入。

缓冲区溢出就好比一个杯子倒太多的水，洒出来，这叫溢出。它是一种非常普遍、非常危险的漏洞，最常出现在C/C++编写的程序中。

早期，人们还不那么重视安全的时候，往往会使用像strcpy这类不安全函数，这种函数对用户的输入不作任何检查，总之，来自不拒，那么，分配的内存空间是有限的，如果输入超长的字符串，必然会导致溢出。

缓冲区溢出中，最为危险的是堆栈溢出，因为入侵者可以利用堆栈溢出，在函数返回时改变返回程序的地址，让其跳转到任意地址，带来的危害一种是程序崩溃导致拒绝服务，另外一种就是跳转并且执行一段恶意代码，比如得到系统权限，然后为所欲为。

8.死锁产生的条件

死锁是指两个或两个以上进程在执行过程中，因争夺资源而造成的相互等待的现象

死锁：多个进程因竞争资源而造成的一种僵局即相互等待，若无外力作用，这些进程都将无法向前推进。

原因：系统资源不足，分配不当，非剥夺资源的竞争和进程不恰当的推进顺序。

产生死锁的四个必要条件：

（1） 互斥条件：一个资源每次只能被一个进程使用。进程对所分配到的资源不允许其他进程访问，若其他进程访问该资源，只能等待，直至占有该资源的进程使用完成后释放该资源。

（2） 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。进程获得一定的资源后，又对其他资源发出请求，但是该资源可能被其他进程占有，此时请求阻塞，但该进程不会释放自己已经占有的资源。

（3） 不剥夺条件:进程已获得的资源，在未完成使用之前，不可被剥夺，只能在使用后自己释放。

（4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。进程发生死锁后，必然存在一个进程-资源之间的环形链。

这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一个不满足，就不会发生死锁。

9.分页和分段

固定分区会产生内部碎片，动态分区会产生外部碎片，这两种技术对内存的利用率较低

为了避免碎片的产生提高内存的利用率引入分页。

用户程序的地址空间被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。

页表的作用是实现从页号到物理块号的地址映射。

分页系统中，CPU每次要存取一个数据，都要两次访问内存（访问页表、访问实际物理地址）。为提高地址变换速度，增设一个具有并行查询能力的特殊高速缓冲存储器，称为“联想存储器”或“快表”，存放当前访问的页表项。

将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。

分页和分段有许多相似之处,比如两者都不要求作业连续存放.但在概念上两者完全不同,主要表现在以下几个方面:

(1)页是信息的物理单位,分页是为了实现非连续分配**,以便解决内存碎片问题**,或者说分页是由于系统管理的需要.段是信息的逻辑单位,它含有一组意义相对完整的信息,分段的目的是为了更好地实现共享,满足用户的需要.

(2)页的大小固定,由系统确定,将逻辑地址划分为页号和页内地址是由机器硬件实现的.而段的长度却不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时根据信息的性质来划分

(3)分页的作业地址空间是一维的.分段的地址空间是二维的.

段页式先分段、再分页

10.进程调度策略

先来先服务调度算法：先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

短作业(进程)优先调度算法：短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。

高优先权优先调度算法：为了照顾紧迫型作业，使之在进入系统后便获得优先处理

又可进一步把该算法分成如下两种。

• 非抢占式优先权算法：在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。
• 抢占式优先权调度算法：在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i 时，就将其优先权Pi与正在执行的进程j 的优先权Pj进行比较。如果Pi≤Pj，原进程Pj便继续执行；但如果是Pi>Pj，则立即停止Pj的执行，做进程切换，使i 进程投入执行。显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。

时间片轮转法

高响应比优先调度算法：在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a 提高，则长作业在等待一定的时间后，必然有机会分配到处理机。在利用该算法时，每要进行调度之前，都须先做响应比的计算，这会增加系统开销。

多级反馈队列 设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍。 新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。 仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。 通常采用固定优先级的抢占式调度

进程调度策略的基本设计指标

1. CPU利用率
2. 系统吞吐率，即单位时间内CPU完成的作业的数量。
3. 响应时间。
4. 周转时间。是指作业从提交到完成的时间间隔。从每个作业的角度看，完成每个作业的时间也是很关键 平均周转时间带权周转时间平均带权周转时间

响应时间：从提交第一个请求到产生第一个响应所用时间。 周转时间：从作业提交到作业完成的时间间隔

周转时间=作业完成时刻-作业到达时刻；

带权周转时间=周转时间/服务时间；

平均周转时间=作业周转总时间/作业个数；

平均带权周转时间=带权周转总时间/作业个数；

11.作业调度算法

作业调度是按一定的算法从磁盘上选择资源能得到满足的作业装入内存，使作业有机会去占用处理器执行。但是，一个作业能否占用处理器，什么时间能够占用处理器，必须由进程调度来决定。所以，作业调度选中了一个作业且把它装入内存时，就应为该作业创建一个进程，若有多个作业被装入内存，则内存中同时存在多个进程，这些进程的初始状态为就绪状态，然后，由进程调度来选择当前可占用处理器的进程，进程运行中由于某种原因状态发生变化，当它让出处理器时，进程调度就再选另一个作业的进程运行。 因此，作业调度与进程调度相互配合才能实现多道作业的并行执行。

先来先服务调度算法

短作业优先

缺点： 对长作业非常不利，可能长时间得不到执行； 未能依据作业的紧迫程度来划分执行的优先级； 难以准确估计作业（进程）的执行时间，从而影响调度性能。

时间片轮转

多级反馈队列

高响应比调度算法

优先级调度算法

12.页面置换算法

进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区。

选择调出页面的算法就称为页面置换算法。

好的页面置换算法应有较低的页面更换频率，也就是说，应将以后不会再访问或者以后较长时间内不会再访问的页面先调出。

最佳置换算法(OPT)

最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。

但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。

先进先出(FIFO)页面置换算法

优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。

该算法实现简单

但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象，这是由 Belady于1969年发现，故称为Belady异常，如图3-28所示。只有FIFO算法可能出现Belady 异常，而LRU和OPT算法永远不会出现Belady异常。

(LRU)置换算法

选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。

该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。

实际上，LRU算法根据各页以前的情况，是“向前看”的，而最佳置换算法则根据各页以后的使用情况，是“向后看”的。

LRU性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。

理论上可以证明，堆栈类算法不可能出现Belady异常。

FIFO算法基于队列实现，不是堆栈类算法。

时钟(CLOCK)置换算法

为确定系统将进程运行时所缺的页面调入内存的时机，可釆取以下两种调页策略：

（1）预调页策略。

根据局部性原理，一次调入若干个相邻的页可能会比一次调入一页更高效。

但如果调入的一批页面中大多数都未被访问，则又是低效的。

所以就需要釆用以预测为基础的预调页策略，将预计在不久之后便会被访问的页面预先调入内存。

但目前预调页的成功率仅约50%。故这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。

（2）请求调页策略。

进程在运行中需要访问的页面不在内存而提出请求，由系统将所需页面调入内存。

由这种策略调入的页一定会被访问，且这种策略比较易于实现，故在目前的虚拟存储器中大多釆用此策略。

它的缺点在于每次只调入一页，调入调出页面数多时会花费过多的I/O开销。

在页面置换