操作系统复习

第一章 引论

体系结构图

1、什么是操作系统？定义，特点，功能

定义：操作系统其实是一个软件，是底层复杂多样的硬件和软件操作的抽象，同时也是资源的管理者，管理与合理利用计算机资源。即操作系统是一个控制和管理计算机硬件与软件资源，合理地组织计算机进行工作以及方便用户使用的大型程序。

特点：

    ①并发：指的是多个应用进程在单核CPU上运行，一段时间交替运行多个程序。

    ②共享：系统的计算机硬件和软件资源可以给多个程序共同使用。

    ③虚拟，将一个物理的实体变成多个逻辑的对应物。

    ④异步：也称为不确定性，即在多道环境下（现代的操作系统基本都是多道环境），每个程序执行的时间，执行的顺序是不确定的。

功能：①进程与线程、②内存管理、③文件系统、④输入/输出管理

操作系统功能图

2、计算机的两种运行状态及特点

①内核态（也称管态）：内核态可使用所有CPU指令（类似root用户的角色）

②用户态（也称目态）：用户态执行指令有范围，即只能执行部分安全指令。通常用户程序就是工作在用户态，用户程序要使用特权指令时需要向操作系统提出申请。

两种状态

从用户态切换到内核态的情况

触发条件：系统功能调用（即操作系统提供给应用程序的接口）、外部中断、异常。三者满足其一就会发生状态切换，其中系统功能调用结束后会从内核态切换回用户态。

目态到管态这一过程的切换是由硬件来完成的，中间会产生中断，这个中断叫作“访管中断”。

中断系统一般由硬件和软件构成

3、系统功能调用的概念

系统功能调用就是用户在程序中使用“访管指令”访问操作系统提供的子功能集合，是操作系统提供给用户程序的接口。

4、各类操作系统的特点

批处理操作系统：和用户无交互，允许多个用户把多个作业提交给计算机集中处理。

分时操作系统：和用户有交互，每个处于就绪队列的进程都会被分配一个时间片（时间片=用户所能忍耐的时间/最大用户数），分时操作系统的特点：多路性、交互性、独立性、及时性。现常用于桌面系统。

实时操作系统：具有“及时性”和“可靠性”，要求操作系统能及时响应外部事件的请求，并能在规定时间内完成对事件的处理，常用于导弹系统这种。

分布式操作系统：多台电脑通过网络连接来共同处理一件任务。

分时与多任务处理的区别：分时指的是多个用户同时访问一台机器，而多任务处理指的是一个用户处理多个任务。

第二章  进程与线程

1、并发与并行概念

并发：指的是多个事件在同一时间间隔内交替执行

并行：指的是多个事件在同一时刻发生

2、进程的5个状态及转换条件

状态图

3、创建进程和fork函数

在windows系统下，创建进程使用的是系统调用CreateProcess()函数，若创建成功则返回true，否则返回false；在linux系统下，创建进程使用的是系统调用fork()函数，若子进程创建失败则返回-1，若创建成功则返回2个值，一个是子进程返回0，一个是子进程返回pid（进程id）。

fork()函数：是一个系统调用，程序中使用fork()函数可以创建和父进程一模一样的子进程出来，子进程使用父进程的栈，数据段，堆以及执行文本段的拷贝。虽然虚拟空间和父进程不一样，但是物理空间是一样的。（是暂时的，因为刚开始创建没什么区别，但当父进程发生改变了，就给子进程创建一个新的物理空间）

进程控制块PCB（Process Control Block）是进程存在的唯一标志。一个进程由程序、数据集合、PCB构成。

引入进程：是为了处理并发；引入线程：是为了提高并发性

4、进程与程序的关系和区别

关系：进程是程序的运行，而程序是进程的基础。

区别：①进程是动态的，而程序是静态的。②进程有生命周期，而程序只是指令的集合，不具有生命周期。③一个程序可以对应多个进程，而一个进程只能对应一个程序。

5、创建线程

在windows系统下，创建线程使用的是系统调用CreateThread()函数，而linux系统下，创建线程使用的是系统调用pthread_create()函数。

6、进程与线程的关系和区别

关系：一个进程包含多个线程，进程就相当于一个容器，线程无法脱离进程独立存在。

区别：进程是计算机资源分配的基本单位，而线程是CPU调度的基本单位。

7、多道程序设计概念以及CPU利用率

多道程序支持一段时间内多个程序交替执行，即并发。多道程序设计提高了CPU的利用率。

8、临界区及竞争条件

临界区：对共享资源进行访问的代码程序片段。

竞争条件：多个进程同时读写某些共享资源，而最后的结果取决于精确时序。

互斥：指的是进程之间的间接制约关系，当一个进程进入临界区使用临界资源时，另一个进程必须等待。只有当使用临界资源的进程退出临界区后，这个进程才会解除阻塞状态。（比如进程B需要访问打印机，但此时进程A占有了打印机，进程B会被阻塞，直到进程A释放了打印机资源,进程B才可以继续执行）

9、互斥的解决方案

有忙等待、睡眠与唤醒（信号量Semaphore）、互斥量（Mutex）、生产者与消费者问题 这几类解决方案

忙等待

    ①锁变量：首先设置一个全局变量用于所有线程共享（int turn=0），在进入临界区之前用while(turn)不断测试turn的值，当turn=0时表示此时没有线程使用临界区，所以把turn设置为1，之后进入临界区。对于其他进程而言，此时while(turn)这一行是成立的，所以其他线程会一直卡在这里忙等待直到测试到turn=0的时候才可以进入临界区。当处于临界区的线程完成临界区的资源访问时就把turn设置为0，表示当前临界区没有线程访问了，此时while(turn)这个条件不成立，其他线程当中就可以任意一个进入临界区，之后再进行同样的操作验证全局变量turn。  不过这个方法并不能完全解决临界区访问的问题（比如第一个线程在turn的值为0时跳过了while(turn)的验证进入临界区，当访问完临界区资源后，此时在把turn设置为1之前，线程切换为第二个线程，而这时turn的值还没修改过来（仍然为0），于是第二个线程会跳过while(turn)的验证进入临界区，这个时候就达不到对临界区的访问控制了。这个turn也变成了竞争条件，但凡是共享的数据都可能成为竞争条件。）

    ②严格轮换法（也称为自旋锁）：同样需要设置一个变量用来识别当前该哪个线程执行了，我们假设有3个线程，他们的线程id我们用tid = 0;和tid = 1;和tid = 2;表示，并设置一个排队号turn（可以这样想，现在有一个浴室（临界区），一次只能进一个人（一个人即一个线程），当浴室中有人在使用的时候其他人需要在外面排队，每个人都有一个排队序号（共享变量）），一开始turn为0，表示线程0可以先进入临界区，其他两个线程只能卡在while循环那里，当线程0完成临界区的访问之后就把turn改成下一个排队号（理解为线程0已经用完浴室了，他出来之后就该轮到线程1进入浴室），而此时线程2依然卡在while循环那里，因为线程1要进入临界区了。严格轮换法按字面意思理解就是严格按顺序轮着来，线程0执行完就轮到线程1，然后线程2，线程3，……  这种算法也有一个问题，那就是如果线程0访问完临界区之后把turn改成1，这时候临界区只有线程1有资格访问，而线程2只能卡在while循环那里，但是线程1目前还不打算进入临界区，他还在执行其他的代码，那么线程2就只能在那里一直等待了，这样就造成了一个效率的问题。（或者说算法的性能问题）

    ③Peterson算法：这个算法就很巧妙地解决了互斥问题，它设置了一个锁turn，当turn==process时表示进程process对访问临界区感兴趣，同时把数组元素interested[process]设置为true，具体的过程看下图代码。巧妙在于while的判断上（while(turn==process && interested[other]=TURE);），比如进程0先执行到while前一行代码，进程0切换到进程1，此时进程1在执行过程中会把turn修改为1，而当前process还是0，于是while(turn==process)就不成立了，则直接让进程0访问临界区，反观进程1的while判断，目前turn==process是成立了，而此时进程0仍在访问临界区资源，则iinterested0]为TRUE也是成立的，于是进程1就一直被卡在while这里忙等待了，知道进程0完成临界区的访问把interested[1]设置为FALSE，进程1才能临界区。

自旋锁方法图 Peterson方法图

睡眠与唤醒（信号量Semaphore）：睡眠与唤醒可以使用系统调用来做，系统为我们开发者提供了互斥问题的解决方案，也就是P、V操作。P、V操作之间的就是临界区代码。

P操作：也称为down操作，执行P操作则信号量-1，如果此时信号量>=0时，则继续往下执行，否则就一直卡在P操作等待一个V操作来唤醒。

V操作：也称为up操作，执行V操作则信号量+1，如果此时信号量>0时，则继续往下执行，否则就一直卡在V操作；若<0则唤醒被信号量阻塞的进程。

注意：执行P操作后如果信号量>=0不成立，则会卡在P操作。当有V操作唤醒的时候就不会在P操作再做判断了，而是直接往下执行。

在Windows中信号量初始化semaphore = CreateSemaphore（0,1,1,0）;【第二个参数表示信号量初值，第三个参数比表示信号量的最大值】，P操作使用WaitForSingleObject（semaphore,-1）;，而V操作使用ReleaseSemaphore（semaphore,1,0）;。在Linux中信号量初始化sem_init（&semaphore,0,1）;【第三个参数表示信号量初值】，P操作使用sem_wait（&semphore）;，而V操作使用sem_post（&semphore）;。

信号量使用的三要素：初值、P操作、V操作。

互斥量（Mutex）：互斥量是专门用来控制互斥事件的，与上面信号量的流程是完全一样的，因为mutex就是信号量的一种特殊情况。比如有2个线程要进入临界区，这时候我们需要控制一次只能有一个线程访问临界区，使用mutex，当有一个线程先访问到mutex的P操作之后，另一个线程会被卡在P操作那里，因此只有临界区的线程结束对临界区的访问并执行了V操作，卡在P操作的另一个线程才会有机会进入临界区。

mutex是专门用来做互斥事件控制的，虽然semaphore也可以做互斥，但未免有点小题大做，semaphore一般做同步控制比较多。

在Windows中互斥量的初始化mutex = createMutex（0,0,0）;,P操作使用WaitForSingleObject（mutex,-1）;，而V操作使用ReleaseMutex（mutex）;。在Linux中互斥量的初始化pthread_mutex_init（&mutex,0）;,P操作使用pthread_mutex_lock（&mutex）;，V操作使用pthread_mutex_unlock（&mutex）;。

生产者与消费者问题：生产者与消费者有一个共同的缓冲区，生产者负责往里面放数据，消费者负责往里面取数据。生产者一旦生产了数据就可以让消费者取，当缓冲区满了，生产者就不能往里面放东西了，就睡眠（sleep（）），直到消费者从缓冲区中取出数据才唤醒生产者（只要缓冲区没有满生产者就可以往里面放）。同样的当缓冲区中空了，消费者就不能取数据了，就睡眠（sleep（）），直到生产者往缓冲区中放了数据才唤醒消费者（只要缓冲区有东西就可以在里面取）。

生产者与消费者

10、进程调度算法（只考虑非抢占式）、周转时间、平均周转时间

先来先服务：先到达的进程优先执行。

短作业优先：在某时刻若有多个进程都已经到达了，则让服务时间最短的优先执行。

高响应比优先：在某时刻若有多个进程都已经到达了，则计算这些进程的响应比【响应比 = （等待时间 + 服务时间）/服务时间】，响应比大的先执行。

计算周转时间、平均周转时间上。（周转时间=结束时间-到达时间。平均周转时间=所有进程的周转时间/所有进程个数。）

操作系统复习