最近在读现代操作系统，原计划呢是读一章，然后把每章的习题刷一边。但是，读完后才发现，章节习题60%都做不出来，这真的很让人沮丧。

但是，想想还是试图去吧自己所读到，所理解的东西记录下来。聊剩余无嘛，对吧？直接进入正题。

什么是进程？什么是线程？为什么操作系统要设计多进程（多线程）？设计多进多(线程)是为了解决什么问题？进程间通信问题(IPC)？进程(线程)同步问题？各种调度算法的实现？

1.进程:

(1)解释:作业？以我的理解，通俗来说进程即我们个人计算机的一道程序软件。

(2)进程状态：运行，就绪，阻塞。

(3)进程的实现：为了维护进程，操作系统维护一张表，即进程表（process table），也成为进程控制块（process control block）。该表包涵了进程状态重要信息，包括程序计数器，堆栈指针，内存分配状况，所打开的文件状态，帐号和调度信息，以及其他进程油运行态转换为就绪态或阻塞态时必须保存的信息，从而保证改进成能再次启动，就像从未中断过一样。

2.线程

线程可分为内核级线程和用户级线程。所以顾名思义，内核级线程由操作系统内核管理，用户级线程油她所属的进程管理。那么什么是线程呢？线程依附与进程，即通常一个操作系统的中多道进程，而每个进程中则有多个线程。

3.为什么操作系统要设计多线程(多线程)呢？

这个问题似乎不那么恰当。但是通俗来说，进程有时可以分为IO密集型和计算密集型(CPU密集型)，试想，当一个进程为IO密集型进程，而另一个进程为CPU密集型，

CPU密集型进程倘若必须等待IO密集型进程执行完毕才能执行，这是对CPU的利用率不要太低啊？举个例子：当我们在日常使用office文档，当我们在进行剪辑操作时，就像笔者现在这样，我们想从网络上下载资料，如果必须等我们执行完office进程后才能执行下载资料这个进程(而实际情况是我们在前台编辑office，后台下载进程可以从感觉上的同时进行)，这样使用效率未免就太低了。那么多线程呢？我们举个例子，我们使用Android设备上的APP时，通常图形渲染和网络(或者IO)请求都不再同一个线程，假设她们同属一个线程，当图形渲染到一半的时候执行网络请求，而此时网络请求又因为网络问题无法执行完毕，那么图形是不是永远也无法渲染完毕？

4。进程间通信(IPC)

进程之间是要互相通信的。不妨回忆一下，我们使用的诸多APP是不是都有分享这一功能，但是每个APP不都是运行着自己的代码吗？为什么我们点击分享却能够唤醒例如短信，微信，微博这个进程呢？着难道不就是进程间通信吗？

4.1进程通信通常有三个问题：

(1)一个进程如何把信息传给另一个进程

(2)确保两个或多个进程在关键活动中不会出现交叉

(3)这与进程的状态顺序有关。例如一个编辑进程，一个打印进程，是不是打印进程必须等待编辑进程结束才能打印相关内容？

同时不得不说，上述三个问题同样对线程有效，不过因为线程通常共享一个地址空间，所以第一个问题对线程而言比较容易，

4.2竞争条件：

两个或多个进程读写共享某些数据，而最后的结果取决于进程的精确时序，成为竞争条件。假设有两个打印进程打印一个文件队列。当一个进程打印完毕后就将其置为空。当进程A打印到第三个文件是CPU认为进程A已经运行足够多的时间，现在让进程B打印第三个文件，当B打印完后A打印发现此时第三个文件为空，这种情况时有发生。

4.3临界区

怎么避免竞争条件？实际上涉及任何共享内存，共享数据，共享资源的情况都会引发类似的错误，要避免这种问题，就要用到互斥，即确保当一个进程使用共享变量或资源时，其他进程不能做相同的操作。我们把共享内存进行访问的程序片段成为临界区。如果我们适当安排使两个进程不能同时处于临界区，就能避免竞争条件问题。

然而，对于一个好的解决方案应该满足一下四点：

(1)任何两个进程不能同时位于临界区

(2)不应对CPU的速度和数量做任何假设

(3)临界区外的进程不得阻塞其他进程

(4)不能使进程无限期等待进入临界区

4.4避免多个进程同时进入临界区的解决方案(忙等待互斥)以及算法实现

(1)屏蔽中断：即当一个进程进入临界区就立即屏蔽所有中断，CPU将不会切换到其他进程，当进程离开临界区之前在打开中断。当然，这种解决方案的弊端显而易见，在单CPU中，若一个进程屏蔽中断后未打开，那么操作系统将因此终止；在多CPU中，屏蔽中断仅仅对执行disable指令的CPU有效，其他CPU仍继续运行，并且可以访问共享内存。

(2)锁变量：设想有一个共享(锁)变量，其初始值为0,当一个进程想进入临界区，首先测试锁变量，若为0,将其设为1,然后进去临界区。若锁变量为1，则等待其变为0才可进入临界区。那么我们假设，当一个进程读出锁变量为0，而在把锁变量设为1之间，另一个进程被调度，此时锁变量为0,可进入临界区，那么将导致两个进程同时进入临界区。

(3)严格轮换法：

(4)Peterson算法

以上几种解决方法都存在忙等待问题，即当一个进程想要进入临界区之前必须先检查是否允许进入，若不允许则将等待到允许为止。这几种解法不但浪费CPU还可能引发不可预想的后果。

(5)生产者-消费者问题(界缓冲区welting)

(6)信号量：

信号量是由E.W.Dijkstra提出的一种方法，它使用一个整形变量来累计唤醒次数，供以后使用。即引入一个新的变量类型，成为信号量(semaphore)。一个信号量的取值可能为0(表示没有唤醒操作)或为正值(表示有一个或多个唤醒操作)。

Dijkstra建议设置两种操作：down和up(分别为一般化后的sleep和wakeup，课本中成为P，V原语)对一信号量执行down操作，则检查其值是否大于0.若大于0,则将其值减1,并继续；若该值为0,则进程将睡眠，此时down操作并未结束，。检查数值，修改变量以及可能发生的睡眠操作均为一个单一的，不可分割的原子操作完成。保证一旦一个信号量开始操作，则该操作完成或阻塞之前，其他进程都不可访问该信号量。up操作对信号量的值增1。如果一个或多个进程在该信号量上睡眠，无法完成一个先前的down操作，则由系统随机选择一个并允许该进程完成down操作。于是对一个有进程在其上睡眠的信号量执行一次up操作后，该信号量值仍然为0，但在其睡眠的进程却少了一个。信号量的值增1和唤醒操作同样是不可分割的。

用信号量解决生产者-消费者问题：

(7)消息传递：

说到消息传递机制不得不提Android系统中的Handler就是基于消息传递机制实现的。这里就不过多解释。在IPC中，使用两条send和receive原语。例如：

send(destination,&message);

receive(source,&massage);

前一个调用像一个给定的目标发送消息，后一个调用从一个给定的源接收消息。如果没有消息可用，则接收者可能被阻塞，直到另一条消息到达，或者带着一个错误码返回。

5。进程调度算法：

前面已经把我所理解的进程间通信问题尽可能的描述出来了。那我我们现在假设已经解决了IPC问题。现在有一个进程执行完毕并离开临界区，但是有两个以上的进程处于就绪状态等待cpu执行。这是cpu该执行哪个进程呢？这就引出了我们下面要说的进程调度算法。

5.1调度算法分类：

(1)批处理调度算法：

1.1。先来先服务：即将所有就绪状态储存在一个就绪队列中，cpu按照就绪队列调度进程。

1.2。最短作业优先：顾名思义最短作业优先调度算法的前提是可以预知进程的运行时间，然后按照运行时间短的进程优先调度的方案执行调度程序。

1.3。最短剩余时间优先：前两种调度算法都是非抢占式的，即一个进程运行过程中除了自身阻塞或者运行完毕，否则cpu不能调度其他进程。最短剩余时间优先可以理解为抢占式版本的最短作业优先。即当一个新的就绪进程运行时间比当前正在运行进程的剩余时间少时，发生cpu中断，执行新的进程。

(2)交互式调度算法

2.1。轮转调度：这是一个最古老，最简单，最公平且使用最广的调度算法。cpu为每个进程分配一个时间段，称为时间片。若当前进程在这个时间片内运行完毕或者阻塞时，cup立即切换，调度下一个进程，当前进程在时间片内为完成，cpu同样切换到下一个进程。每次切换的进程将移到队列末尾。

2.2.。优先级调度：即每个进程被赋予了一个优先级，允许优先级高的进程先调度。但是为了优先级高的进程无休止的运行下去。有两种方案：

一。调度程序可以在每个时钟中断降低当前进程的优先级，如果该动作导致次高优先的进程高于当前进程的优先级，则进行进程切换。

二。每个进程被赋予一个允许运行的最大时间片，当这个时间片用完，下一个次高优先级进程获得机会运行。

2.3。多级队列：为每一类进程设置一个优先级队列，每个队列中采用轮转调度。当前优先级队列运行完毕后才调度次高优先级队列。但是这也可能造成饥饿现象，即如果不偶尔对优先级进程调整，优先级低的队列中的进程将很难得到运行。

以上就是一些基本的调度。最后奉上经典IPC问题，哲学家就餐问题代码：