操作系统

1、进程、线程 及其区别

进程是具有一定功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源调度和分配的基本单位。系统可以为每个进程分配不同的内存空间。

线程是进程的实体，是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位。系统不会为线程分配内存空间，线程组之间共享资源。

一个进程可以有多个线程，多个线程也可以并发执行。

2、线程同步方式：

互斥量 Synchronized/Lock：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问

信号量 Semphare：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量

事件(信号)，Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作

3、进程同步有哪几种机制。

原子操作、信号量机制、自旋锁管程、会合、分布式系统

临界资源：一次仅允许一个进程使用的共享资源

临界区：使用临界资源的那一部分程序

4、进程间的通信的几种方式

管道：半双工的通信方式，数据只能单向流动，而且只能在有血缘关系的进程间使用，进程的血缘关系通常是指父子进程关系。 

信号：是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生；

信号量：进程间传递信号的一个整数值，在信号量上只有三种操作进行：初始化、递减、增加（都是原子操作）

消息队列：消息队列是消息的链接表，它克服了上两种通信方式中信号量有限的缺点，具有写权限得进程可以按照一定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息；

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

套接字：这是一种更为一般得进程间通信机制，它可用于网络中不同机器之间的进程间通信，应用非常广泛。

总结：进程通信方式：管道、共享内存、信号量、信号、套接字

线程通信方式：信号量、信号、锁机制（互斥锁、排他锁、读写锁）

5、什么是死锁？死锁产生的条件？

在两个或者多个并发进程中，如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗的讲就是两个或多个进程无限期的阻塞、相互等待的一种状态。

死锁的产生条件：

3必要：互斥、占有且等待、不可抢占

1充分：循环等待

【互斥：一次只有一个进程可以使用一个资源，其他进程不能访问已分配给其他进程的资源

占有且等待：当一个进程等待其他进程时，继续占有已经分配的资源

不可抢占：不能强行抢占进程已占有的资源

循环等待：存在一个封闭的进程链，使得每个进程至少占有此链中下一个进程所需的一个资源。即若干进程之间形成一种头尾相接的环形等待资源关系 】

死锁预防：破坏四个条件，有一个条件不成立，则不会产生死锁。

死锁避免：进程启动拒绝、资源分配拒绝（又称为银行家算法，要求满足 Cij-Aij<=Vj，需求的资源-已分配的资源，即还需的资源<=未分配的资源）

6、进程的状态：新建态、就绪态、运行态、阻塞态、终止态

线程状态：就绪态、运行态、阻塞态

7、分页和分段有什么区别？

段是信息的逻辑单位，它是根据用户的需要划分的，因此段对用户是可见的 ；页是信息的物理单位，是为了管理主存的方便而划分的，对用户是透明的。

段的大小不固定，有它所完成的功能决定；页大大小固定，由系统决定

段向用户提供二维地址空间；页向用户提供的是一维地址空间

段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制。                                                                                                                                                                                                     

8、单处理器的选择调度策略：

FCFS、轮转、SPN（最短进程优先）、SRT（最短剩余时间优先）、HRRN（最高响应比优先）、反馈

9、磁盘调度策略：

FIFO、优先级、SSTF(最短服务时间优先）、SCAN、C-SCAN、N-step-SCAN、FSCAN

【FCFS(先来先服务，队列实现，非抢占的)：先请求CPU的进程先分配到CPU

SJF(最短作业优先调度算法)：平均等待时间最短，但难以知道下一个CPU区间长度

优先级调度算法(可以是抢占的，也可以是非抢占的)：优先级越高越先分配到CPU，相同优先级先到先服务，存在的主要问题是：低优先级进程无穷等待CPU，会导致无穷阻塞或饥饿；解决方案：老化

时间片轮转调度算法(可抢占的)：队列中没有进程被分配超过一个时间片的CPU时间，除非它是唯一可运行的进程。如果进程的CPU区间超过了一个时间片，那么该进程就被抢占并放回就绪队列。

多级队列调度算法：将就绪队列分成多个独立的队列，每个队列都有自己的调度算法，队列之间采用固定优先级抢占调度。其中，一个进程根据自身属性被永久地分配到一个队列中。

多级反馈队列调度算法：与多级队列调度算法相比，其允许进程在队列之间移动：若进程使用过多CPU时间，那么它会被转移到更低的优先级队列；在较低优先级队列等待时间过长的进程会被转移到更高优先级队列，以防止饥饿发生。】

10、线程分类：

用户级线程：线程管理工作由应用程序完成

内核级线程：线程管理工作由内核完成

11、虚拟内存分页，页面置换策略：

FIFO先进先出算法：在操作系统中经常被用到，比如作业调度（主要实现简单，很容易想到）；

LRU（Least recently use）最近最少使用算法：根据使用时间到现在的长短来判断；

LFU（Least frequently use）最少使用次数算法：根据使用次数来判断；

OPT（Optimal replacement）最优置换算法：理论的最优，理论；就是要保证置换出去的是不再被使用的页，或者是在实际内存中最晚使用的算法。

12、局部性原理

(1). 时间上的局部性：最近被访问的页在不久的将来还会被访问；

(2). 空间上的局部性：内存中被访问的页周围的页也很可能被访问。

应用：Cache 高速缓存机制（在处理器和内存之间提供一个容量小、速度快的存储器）

13、虚拟内存

如果存在一个程序，所需内存空间超过了计算机可以提供的实际内存，那么由于该程序无法装入内存所以也就无法运行。单纯的增加物理内存只能解决一部分问题，但是仍然会出现无法装入单个或者无法同时装入多个程序的问题。但是可以从逻辑的角度扩充内存容量，即可解决上述两种问题。

基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。

14、同样可以实现互斥，互斥锁和信号量有什么区别？

答：信号量用在多线程多任务同步的，一个线程完成了某一个动作就通过信号量告诉别的线程，别的线程再进行某些动作（大家都在semtake的时候，就阻塞在哪里）。

而互斥锁是用在多线程多任务互斥的，一个线程占用了某一个资源，那么别的线程就无法访问，直到这个线程unlock，其他的线程才开始可以利用这 个资源。比如对全局变量的访问，有时要加锁，操作完了，在解锁。有的时候锁和信号量会同时使用的”

也就是说，信号量不一定是锁定某一个资源，而是流程上的概念，比如：有A,B两个线程，B线程要等A线程完成某一任务以后再进行自己下面的步骤，这个任务 并不一定是锁定某一资源，还可以是进行一些计算或者数据处理之类。而线程互斥量则是“锁住某一资源”的概念，在锁定期间内，其他线程无法对被保护的数据进 行操作。在有些情况下两者可以互换。

区别：

作用域上 

信号量：进程间或线程间（linux仅线程间的无名信号量pthread semaphore） 

互斥锁：线程间。

上锁时 

信号量：只要信号量的value大于0，其他线程就可以sem_wait成功，成功后信号量的value减一。若value值不大于0，则sem_wait使得线程阻塞，直到sem_post释放后value值加一，但是sem_wait返回之前还是会将此value值减一。 

互斥锁：只要被锁住，其他任何线程都不可以访问被保护的资源。

15、阻塞式：如果当前工作未完成，当前线程会被挂起，直到完成。

非阻塞式：如果当前工作未完成，不会阻塞当前线程

同步和异步通常用来形容一次方法调用。

同步方法调用一旦开始，调用者必须等到方法调用返回后，才能继续后续的行为。

异步方法调用更像一个消息传递，一旦开始，方法调用就会立即返回，调用者就可以继续后续的操作。而，异步方法通常会在另外一个线程中，“真实”地执行着。整个过程，不会阻碍调用者的工作。

16、什么是缓冲区溢出？有什么危害？其原因是什么？

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

危害有以下两点：

程序崩溃，导致拒绝额服务；跳转并且执行一段恶意代码

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

17、并发问题：2个或多个事件在同一时间间隔内发生，微观上是串行，宏观上并行

并发问题主要是互斥和同步

1、信号量

2、互斥

（1）信号量 semwait和semSignal成对存在，

互斥时：位于同一进程，临界区的前后；

同步时：交错出现于2个合作进程内。

（2）生产者/消费者问题

3、管程：一个或多个过程、一个初始化序列和局部数据组成的软件模块。

管程通过使用条件变量提供对同步的支持：cwait(c)   csignal(c)

4、消息传递   同步

5、读者/写者问题：多读少写。可以同时读，只能一个，此时不能读。

18、局部性原理

(1). 时间上的局部性：最近被访问的页在不久的将来还会被访问；

(2). 空间上的局部性：内存中被访问的页周围的页也很可能被访问。

19、线程可以分为两类：

用户级线程(user level thread)：对于这类线程，有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在。用户级线程的好处是非常高效，不需要进入内核空间，但并发效率不高。

内核级线程(kernel level thread)：对于这类线程，有关线程管理的所有工作由内核完成，应用程序没有进行线程管理的代码，只能调用内核线程的接口。内核级线程的好处是，内核可以将不同线程更好地分配到不同的CPU，以实现真正的并行计算。