哲学家就餐问题等

一、经典的IPC问题

哲学家就餐问题

问题描述:

5个哲学家围绕一张圆桌而坐，每个哲学家面前都有一盘通心粉，由于通心粉很滑，所以需要两把叉子才能夹住。相邻两个盘子之间有一把叉子。哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两把叉子,思考时则同时将两把叉子放回原处。

如何保证哲学家们的动作有序进行?如:

• 不出现相邻者同时要求进餐;
• 不出现有人永远拿不到叉子。

为了避免死锁，和只能让一个哲学家进餐的状态，我们可以使用下面的方法。

使用一个数组state跟踪每一个哲学家是在进餐，思考还是饥饿状态（正在试图拿叉子），一个哲学家只有在两个邻居都没有进餐时才允许进入进餐状态。

第i个哲学家由宏LEFT和RIGHT定义。比如i为2，则LEFT为1，RIGHT为3。

#define N           5                   #define N           5                   /*哲学家数目*/
#define LEFT        (i + N - 1) % N     /*i的左邻居编号*/
#define RIGHT       (i + 1) % N         /*i的右邻居编号*/
#define THINKING    0                   /*哲学家在思考*/
#define HUNGRY      1                   /*哲学家试图拿起叉子*/
#define EATING      2                   /*哲学家进餐*/
typedef int seamphore;                  /*信号量是一种特殊的整型数据*/
int state[N];                           /*数组用来跟踪记录每位哲学家的状态*/
seamphore mutex = 1;                    /*临界区的互斥*/
seamphore s[N];                         /*每个哲学家一个信号量*/

void philosopher(int i)                 /*i：哲学家编号，从0到N-1*/
{
    while(TRUE){                    /*无限循环*/
    }
}

void take_forks(int i)                  /*i：哲学家编号，从0到N-1*/
{    
    down(&mutex);                   /*进入临界区*/
    state[i] = HUNGRY;              /*记录哲学家i处于饥饿的状态*/
    test(i);                        /*尝试获取2把叉子*/
    up(&mutex);                     /*离开临界区*/
    down(&s[i]);                    /*如果得不到需要的叉子则阻塞*/
}    

void put_forks(i)                       /*i：哲学家编号，从0到N-1*/
{
    down(&mutex);                   /*进入临界区*/
    state[i] = THINKING;            /*哲学家已就餐完毕*/
    test(LEFT);                     /*检查左边的邻居现在可以吃吗*/
    test(RIGHT);                    /*检查右边的邻居现在可以吃吗*/
    up(&mutex);                     /*离开临界区*/
}

void test(i)                            /*i：哲学家编号，从0到N-1*/
{
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING){
        state[i] = EATING;
        up(&s[i]);
    }
}

该程序使用了一个信号量数组，每个信号量对应一个哲学家，这样在所需的叉子被占用时，想进餐的哲学家就被阻塞。

二、进程与线程书后习题

1.有没有可能发生阻塞到运行，就绪到阻塞的转换？

1. 从阻塞到运行的状态是可以的，假设某个进程在I/O上阻塞，而且I/O就此结束，如果此时CPU是空闲的话，这个进程就可以从阻塞状态直接转换到运行态。
2. 而从就绪态转换到阻塞态是不可能的，因为一个就绪的进程是不会做诸如I/O这些会产生阻塞的事，只有运行的进程才能被阻塞。

4.内核使用单独堆栈的原因

1. 你不会希望由于一些写的不好的用户程序没有被分配到足够多的堆栈空间而导致系统崩溃。
2. 如果内核把数据保留在用户空间，然后从系统调用返回，那么一个恶意用户就有可能使用这些数据查找关于其他进程的信息。

5. 多个程序能够并行运行，比它们顺序执行完成的要快。假设有两个作业同时开始执行，每个需要10分钟的CPU时间。如果顺序执行，那么最后一个作业需要多长时间可以完成？如果并行执行又需要多长时间？假设I/0等待占50%。

1. 顺序执行的时候，因为I/O频率为50%，CPU时间为10分钟，所以每个作业需要20分钟，则最后一个作业需要40分钟来完成。

2. 并行执行时，CPU的利用率为1-0.5²，这意味着每分钟每个作业在并行时实际获得用于处理的CPU时间是0.75/2 = 0.375分钟，所以为了执行完需要10分钟的CPU时间的工作，每个作业必须运行10/0.375≈26.67分钟。又因为是并行的，相当于两个作业同时完成，因此是26.67分钟。

7.如果创建一个多线程进程，若子进程得到全部父进程线程的副本，会出现问题。假如原有线程之一正在等待键盘输入，现在则成为两个线程在等待键盘输入，每个进程有一个。在单线程进程中也会发生这种问题吗？
不会。如果单线程进程在键盘上阻塞，就不能创建子进程。

8.在多线程Web服务器中，如果读取文件的唯一途径是正常的阻塞read系统调用，那么Web服务器应该使用用户级线程还是内核级线程，为什么？
用内核级线程。
当一个工作线程从磁盘读取一个网页时，它就会被阻塞。如果使用了用户级线程，那这个动作就会阻塞整个进程，那么多线程就没有意义了。所以就应该使用内核级线程，这样在一些线程阻塞时就不会影响其他线程。

11.为什么线程要通过调用thread_yield自愿放弃CPU？毕竟，由于没有周期性的时钟中断，线程可以不交回CPU。
进程中的线程通常是相互协作而不是相互独立的，如果放弃是对应用程序的有利需要的话，那么线程将放弃CPU。毕竟通常都是一个程序员写所有的代码。

12.线程可以被时钟中断抢占吗？如果可以，什么情形下可以？如果不可以，为什么不可以？
用户级线程不可以被时钟剥夺，除非整个进程的时间片被用完。内核级的线程可以单独地被剥夺。在后一种情况中，如果一个线程运行太久，那么时钟会终端当前的进程，因此当前的线程也被中断。内核可以自由地从同一个进程中选取其他线程运行。

13.对使用单线程文件服务器和多线程服务器读取文件进行比较。假设所需要的数据都在高速缓存中，花费15ms获得工作请求，分派工作，并处理其余必要工。如果在三分之一时间时，需要一个磁盘操作，要另外花费75ms，此时该线程进入睡眠。在单线程情形下服务器每秒可以处理多少个请求？如果是多线程呢？

• 在单线程的情况下，cache命中需要15ms，没命中需要90ms。那加权平均时间为2/3x15 + 1/3x90，因此平均请求时间为40ms，所以服务器一秒可以处理25个请求。
• 对于一个多线程服务器，所有的磁盘等待都是重叠的，所以每个请求花费15ms，所以服务器可以每秒处理200/3个请求。

14.在用户空间实现线程，其最大的优点是什么？最大的缺点是什么？

• 用户级线程包可以在不支持线程的操作系统上实现

• 允许每个进程有自己定制的调度算法

• 如何实现阻塞系统调用

• 如果一个线程开始运行，那么在该线程中的其他线程就不能运行，除非第一个线程自动放弃CPU。

• 最大的优点是效率。No traps to the kernel are needed to switch threads.

• 最大的缺点是如果一个线程发生阻塞，那整个进程就阻塞了。

38.运行在CTSS上的一个进程需要30个时间片完成。该进程必须被调入多少次，包括第一次（在该进程运行之前）？
第一次得到1个时间片。随后获得2,4,8,15个时间片，因此必须经过5次交换。

41.一个软实时系统有4个周期时间，其周期分别为50ms，100ms，200ms和250ms。假设这4个事件分别需要35ms，20ms，10ms和x ms的CPU时间。保持系统可调度的最大x值是多少？
所使用的CPU的片断为35/50 + 20/100 + 10/200 + x/250。为了使得进程可调度，必须是总和小于1。因此，x必须小于12.5ms。

42.请解释为什么两级调度比较常用？
当内存太小不能载入所有就绪进程时，就需要使用两级调度。某些进程被载入内存，并且从中选择一个运行。内存中进程会随着时间调整。这种算法容易实现也非常有效，另外，时间片轮转调度并不管进程是否在内存中。

43.一个实时系统需要处理两个语音通信，每个运行5ms，然后每次突发消耗1ms CPU时间，加上25帧/秒的一个视频，每一帧需要20ms的CPU时间。这个系统是可调度的吗？
每个语音通信每秒运行200次并且每次突发消耗1ms，所以每个语音通信需要200ms每秒或者两个需要400ms每秒。视频每秒运行25次并且每次消耗20ms，一共是500ms每秒。它们每秒一共消耗900ms，所以有时间剩余，系统可调用。

当计算机系统是多道程序设计系统时，通常就会有多个进程或者线程同时竞争CPU。只要有两个或者多个进程处于就绪状态，这种情况就会发生。如果此时只有一个CPU可用，那么就必须选择下一个要运行的进程。

在操作系统中完成选择工作的这一部分称为调度程序，该程序使用的算法称为调度算法。

一、何时调度

• 在创建一个新进程后，需要决定是运行父进程还是运行子进程。
• 在一个进程退出时必须做出调度决策。
• 当一个进程阻塞在I/O和信号量上或由于其他原因阻塞时，必须选择另一个进程运行。
• 在一个I/O中断发生时，必须做出调度决策。
• 在分时系统中，当一个时钟中断发生时。

二、调度算法

1.先来先服务FCFS(first-come first-served)

这是最简单的调度算法,按先后顺序调度。

• 按照作业提交或进程变为就绪状态的先后次序,分派CPU;
• 当前作业或进程占用CPU,直到执行完或阻塞,才出让CPU(非抢占方式)。
• 在作业或进程唤醒后(如I/O完成),并不立即恢复执行,通常等到当前作业或进程出让CPU。最简单的算法。

FCFS的特点

• 比较有利于长作业,而不利于短作业。
• 有利于CPU繁忙的作业,不利于I/O繁忙的作业。

2.最短作业优先SJF(shortest job first)

这是对FCFS算法的改进，目的是为了缩短平均周转时间。

对预计执行时间短的作业(进程)优先分派处理机。通常后来的短作业不抢先正在执行的作业。

SJF的特点

优点:

• 比FCFS改善平均周转时间和平均带权周转时间,缩短作业的等待时间;
• 提高系统的吞吐量;

  缺点:

• 对长作业非常不利,可能长时间得不到执行;
• 未能依据作业的紧迫程度来划分执行的优先级;
• 难以准确估计作业(进程)的执行时间,从而影响调度性能。

3.轮转调度

一种最古老、最简单、最公平且使用最广的算法是轮转调度。每个进程被分配一个时间段，称为时间片，即允许该进程在该时间段内运行。

1. 如果在时间片结束时该进程还在运行，则将剥夺CPU并分配给另一个进程。
2. 如果该进程在时间片结束前阻塞或结束，则CPU立即进行切换。

时间片长度变化的影响

• 过长->退化为FCFS算法,进程在一个时间片内都执行完,响应时间长。
• 过短->用户的一次请求需要多个时间片才能处理完,上下文切换次数增加,响应时间长。

时间片长度的确定

1. 系统的响应时间: T(响应时间) = N(进程数目) * q(时间片)
2. 就绪进程的数目: 数目越多,时间片越小
3. 系统的处理能力: 应当使用户输入通常在一个时间片内能处理完,否则使响应时间,平均周转时间和平均带权周转时间延长。

4.优先级调度

基本思想：每个进程被赋予一个优先级，允许优先级最高的可运行进程先运行。

优先级又被分为静态优先级和动态优先级。

静态优先级

创建进程时就确定,直到进程终止前都不改变。通常是一个整数。依据:

• 进程类型(系统进程优先级较高)
• 对资源的需求(对CPU和内存需求较少的进程,优先级较高)
• 用户要求(紧迫程度和付费多少)

动态优先级

在创建进程时赋予的优先级,在进程运行过程中可以自动改变,以便获得更好的调度性能。如:

• 在就绪队列中,等待时间延长则优先级提高,从而使优先级较低的进程在等待足够的时间后,其优先级提高到可被调度执行;
• 进程每执行一个时间片 就降低其优先级 从而一个进程持续执行时,其优先级降低到出让CPU。

三、线程调度

当若干进程都有多个线程时，就存在两个层次的并行：线程和进程。

在这样的系统中调度处理有本质差别，这取决于所支持的是用户级线程还是内核级线程（或者两者都支持）。

用户级线程

因为内核不知道有线程的存在，所以内核还是像以前一样操作，选取一个进程，假设为A，并给予A以时间片控制。A中的线程调度程序决定哪个线程运行，假设为A1。

由于多道线程并不存在时钟中断，所以这个线程可以随意运行多长时间，如果该线程用完了进程的所有时间片，内核就会选择另外一个进程运行。

在进程A终于又一次运行时，线程A1会接着运行。该线程会继续耗费A进程的所有时间，直到它完成工作。并且这种行为不会影响到其他的进程。

现在考虑A线程每次CPU计算的工作比较少的情况，例如在50ms的时间片里有5ms的计算工作。于是，每个线程运行一会儿，然后把CPU交回给线程调度程序。

这样在内核切换到进程B之前，就会有序列A1,A2,A3,A1,A2,A3,A1,A2,A3,A1。如下图所示。

内核级线程

内核选取一个特定的线程运行，它不用考虑该线程属于哪个进程（如果有必要它也可以这样做）。内核对被选择的线程赋予一个时间片，如果超出了时间片就会强行挂起这个线程。

一个线程在50ms的时间片内，5ms之后被阻塞，在30ms的时间段中，线程的顺序会是A1,B1,A2,B2,A3,B3。如下图所示。

用户级线程和内核级线程之间的差别在于性能。

• 用户级线程的线程切换需要少量的机器指令；

• 内核级线程需要完整的上下文切换，修改内存印象，使高速缓存失效，这导致了若干数量级的延迟。

另一方面，在使用内核级线程时，一旦线程阻塞在I/O上就不需要像在用户级线程中那样将整个进程挂起。

进程经常需要与其他进程通信，所以我们就来讨论一些关于进程间通信(Inter Process Communication, IPC)的问题。

一、竞争状态(race condition)

• 两个或多个进程对同一共享数据同时进行读写操作，而最后的结果是不可预测的，它取决于各个进程具体运行情况。
• 在同一时刻，只允许一个进程访问该共享数据，即如果当前已有一个进程正在使用该数据，那么其他进程暂时不能访问。这就是互斥的概念。

那么为了避免竞争状态，我们就需要互斥，也就是当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作。这样就引入了临界区的概念。

二、临界区

临界区的定义：

每个进程中访问临界资源的那段代码称为临界区。
临界资源指的是一次只允许一个进程使用的资源称为临界资源，例如打印机、变量。

所以如果我们能通过适当的安排，使得两个进程不可能同时处于临界区中，就能避免竞争状态。

尽管这样的要求避免了竞争状态，但它还不能保证使用共享数据的并发进程能够正确和高效地进行协作。所以对于一个好的解决方案，需要满足一下4个：

1. 任何两个进程都不能同时进入临界区;
2. 不应对CPU的速度和数量做任何假设;
3. 临界区外运行的进程不得阻塞其他进程;
4. 不得使进程无限期等待进入临界区。

三、同步机制应遵循的准则

1.空闲让进

• 临界自愿处于空闲状态,允许进程进入临界区
• 临界区内仅有一个进程执行

2.忙则等待

• 临界区有进程正在执行其中的代码,所有其他进程则不可以进入临界区

3.有限等待

• 对要求访问临界区的进程 应在保证在有限时间内进入自己的临界区,避免死等。

4.让权等待

• 当进程不能进入自己的临界区时,应立即释放处理机,避免忙等。

四、实现互斥的方案

1.屏蔽中断

在单处理器系统中，最简单的方法是使每个进程在刚刚进入临界区后立即屏蔽所有中断，并在就要离开之前打开中断。
屏蔽中断后，时钟中断也会被屏蔽。
CPU只有在发生时钟中断或其他中断时才会进行进程切换，这样，在屏蔽中断后CPU就不会被切换到其他进程。

2.锁变量

假设有一个共享变量，初始值为0。当一个进程想进入临界区时，它就会首先测试这把锁。
如果锁的值为0，则该进程就将其设置为1并进入临界区。
如果锁的值已经为1，那么进程就一直等待直到锁的值为0.
所以0就表示临界区内没有进程，1表示已经有某个进程进入临界区。

3.严格轮换法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

while(TRUE){
	while(turn != 0)
			critical_region();	/*循环*/
	turn = 1;
	noncritical_region();
}
```  

>a)  

```C
while(TRUE){
	while(turn != 1)
			critical_region();	/*循环*/
	turn = 0;
	noncritical_region();
}

```  

>b)  

### 4.Peterson解法
在进入临界区前，各个进程使用其进程号0或1作为参数来调用enter_region。该调用在需要时将使进程等待，直到能安全地进入临界区。在完成对共享变量的操作后，进程将调用leave_region，表示操作已完成，若其他进程希望进入临界区，则现在就可以进入。  

```C
#define FALSE 0
#define TRUE  1
#define N     2                                                  /*进程数量*/
                                                                   
int turn;                                                        /*现在轮到谁？*/
int interested[N];                                               /*所有值初始化为0(FALSE)*/

void enter_region(int process)                                   /*进程是0或1*/
{
    int other;                                                   /*其他进程号*/
    
    other = 1 - process;                                         /*另一方进程*/
    interested[process] = TRUE;                                  /*表明所感兴趣的*/
    turn = process;                                              /*设置标志*/
    while(turn == process && interested[other] == TRUE);         /*空语句*/
}

void leave_region(int process)                                   /*进程：谁离开？*/
{
    interested[process] = FALSE;                                 /*表示离开临界区*/
}

五、生产者-消费者问题

生产者-消费者问题又称为有界缓冲区问题。两个进程共享一个公共的固定大小的缓冲区。

其中一个是生产者，将消息放入缓冲区；另一个是消费者，从缓冲区中取出消息。

而问题在于当缓冲区已满，而此时生产者还想向其中放入一个新的数据项的情况。其解决方法是让生产者睡眠，待消费者从缓存区中取出一个或多个数据项时再唤醒它。

当消费者试图从缓冲区中取数据而发现缓冲区为空时，消费者就睡眠，直到生产者向其中放入一些数据时再将其唤醒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

#define N 100                                      /*缓冲区中的槽数目*/
int count = 0;                                     /*缓冲区中的数据项数目*/
void producer(void)
{
    int item;
    
    while(TRUE){                                   /*无限循环*/
        item = produce_item();                     /*产生下一新数据项*/
        if(count == N)  sleep();                   /*如果缓冲区满了，就进入休眠状态*/
        insert_item(item);                         /*将新数据项放入缓冲区中*/
        count = count + 1;                         /*将缓冲区的数据项计数器增1*/
        if(count == 1）  wakeup(consumer);        
    }
}

void consumer(void)
{
    int item;
    
    while(TRUE){                                   /*无限循环*/
        if(count == 0)  sleep();                   /*如果缓冲区空，则进入休眠状态*/
        item = remove_item();                      /*从缓冲区中取出一个数据项*/
        count = count - 1;                         /*将缓冲区的数据项计数器减1*/
        if(count == N - 1)  wakeup(producer);      /*缓冲区满吗？*/
        consume_item(item);                        /*打印数据项*/
    }
}
```  
这里还是有可能会出现竞争状态，其原因是对count的访问未加限制。  

我们来看这样一个情况：缓冲区为空，消费者刚刚读取count的值发现它为0，此时调度程序决定暂停消费者而唤醒生产者。生产者向缓冲区中加入一个数据项，count加1。现在count的值变成1了，它推断由于count刚刚为0，所以消费者一定在睡眠，于是生产者调用**wakeup**来唤醒消费者。  

但此时消费者并没有睡眠，所以这个**wakeup**信号就会丢失，当消费者下次运行时，它将测试先前读到的count值，发现它为0，于是睡眠。而生产者迟早会填满整个缓冲区，然后睡眠，这样一来，两个进程将永远睡眠下去。  

所以现在问题的实质在于一个wakeup信号的丢失。虽然在这里我们可以加上一个**唤醒等待位**，但当问题中有三个或者更多进程时一个唤醒等待位就不够了，所以这并没有从本质上解决问题。  

## 六、信号量
E.W.Dijkstra提出一种方法，它使用一个整型变量来累计唤醒次数，供以后使用。  

这个引入的新变量类型就叫做**信号量(semaphore)**。  

一个信号量的取值可以为0（表示没有保存下来的唤醒操作）或正值（表示有一个或多个唤醒操作）。  

Dijkstra建议设立两种操作：down(P)和up(V)。  
    
    
- down
    如果信号量的值大于0，则将其值减1并继续；  
    若该值为0，则进程将睡眠。并将继续down操作。  

- up
    对信号量的值增1。  
    
    
### 用信号量解决生产者-消费者问题
#### 该方案使用了三个信号量：
- **full**   用来记录充满的缓冲槽数目；
- **empty**  记录空的缓冲槽总数；
- **mutex**  确保生产者和消费者不会同时访问缓冲区。  

full的初值为0，empty的初值为缓冲区中槽的数目，mutex初值为1。供两个或多个进程使用的信号量，其初值为1，保证同时只有一个进程可以进入临界区，称为二元信号量。如果每个进程在进入临界区前都执行一个down操作，并在刚刚退出时执行一个up操作，就能够实现互斥。  

```C
#define N 100                       /*缓冲区中的槽数目*/
typedef int semaphore;              /*信号量是一种特殊的整型数据*/
semaphore mutex = 1;                /*控制对临界区的访问*/
semaphore empty = N;                /*计数缓冲区的空槽数目*/
semaphore full  = 0;                /*计数缓冲区的满槽数目*/

void producer(void)
{
    int item;
    
    while(TRUE){                    /*TRUE是常量1*/
        item = produce_item();      /*产生放在缓冲区中的一些数据*/
        down(&empty);               /*将空槽数目减1*/
        down(&mutex);               /*进入临界区*/
        insert_item(item);          /*将新数据项放到缓冲区中*/
        up(&mutex);                 /*离开临界区*/
        up(&full);                  /*将满槽的数目加1*/
    }
}

void consumer(void)
{ 
    int item;
    
    while(TRUE){                    /*无限循环*/
        down(&full);                /*将满槽数目减1*/
        down(&mutex);               /*进入临界区*/
        item = remove();            /*从缓冲区中取出数据项*/
        up(&mutex);                 /*离开临界区*/
        up(&empty);                 /*将空槽数加1*/
        consumer_item(item);        /*处理数据项*/
    }
}

操作系统中最核心的概念就是进程：这是对正在运行程序的一个抽象。

一、进程的定义

• 进程是程序的一次执行。
• 进程 = 进程控制块 + 程序 + 数据。
• 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

二、进程的结构

一个进程中应该包括：

• 程序的代码；
• 程序的数据；
• 程序计数器中的值，用来指示下一条将运行的指令；
• 一组通用的寄存器的当前值、堆、栈；
• 一组系统资源（如打开的文件）；

三、进程的创建：4个因素

1.系统初始化。
2.执行了正在运行的进程所调用的进程创建系统调用。
3.用户请求创建一个新进程。
4.一个批处理作业的初始化。

在UNIX系统中，只有一个系统调用可以用来创建新进程：fork。

四、进程的终止：4种原因

1. 正常退出（自愿的）。
2. 出错退出（自愿的）。
3. 严重错误（非自愿）。
4. 被其他进程杀死（非自愿）。

五、进程的状态

进程有三种基本状态：

• 运行态
  该时刻进程实际占用CPU。
• 就绪态
  可运行，但因为其他进程正在运行而暂时停止。
  进程已获得除处理机外的所需资源，等待分配处理机资源，只要分配CPU就可执行。
• 阻塞态
  正在执行的进程，由于发生某种事件而暂时无法执行，便放弃处理机处于暂停状态。

1.运行→阻塞：进程为等待输入而阻塞
2.运行→就绪：调度进程选择另一个程序
3.就绪→运行：调度进程选择这个进程
4.阻塞→就绪：出现有效输入

• 在操作系统发现进程不能继续运行下去时，发生转换1。
• 系统认为一个运行进程占用处理器的时间已经过长，决定让其他进程使用CPU时间时，会发生转换2。
• 在系统已经让所有其他进程享有了它们应有的公平待遇而重新轮到第一个进程再次占用CPU运行时，会发生转换3。
• 当进程等待的一个外部事件发生时（如一些输入达到），则发生转换4。

转换2、3都是由进程调度程序引起的。

调度程序的主要工作就是决定应当运行哪个进程、何时运行以及它应该运行多长时间。

六、进程的实现

操作系统为了实现进程模型，维护着一张叫做进程表(process table)的表格，每个进程占用一个进程表项。（在学校的教材上这个进程表项叫做进程控制块PCB）。

进程控制块PCB是进程的唯一标志。

进程控制块中包含了进程状态的重要信息，包括：

• 程序计数器（PC）
• 堆栈指针
• 内存分配状态
• 所打开文件状态
• 账号和调度信息
• 优先级
• 互斥和同步机制
• …

正是这些信息保证了进程在经历了各种转换后能再次启动，就像从未被中断过一样。

七、线程

上面的内容中，我们讨论了关于进程的话题，但是在实际运用当中并不是每次都只运行一个进程的，所以我们就需要提出一个新的实体，来满足一下特性：

• 实体之间可以并发地执行；
• 实体之间共享相同的地址空间；

而进程包含了两个概念：资源拥有者和可执行单元，这个可执行单元就称为线程。

尽管线程必须在某个进程中执行，但是线程和它的进程是不同的概念，并且可以分别处理。

进程用于把资源集中到一起，而线程则是在CPU上被调度执行的实体。

在同一个进程中并行运行多个线程，是对在同一台计算机上并行运行多个进程的模拟。

1. 在前一种情形中，多个线程共享同一个地址空间和其他资源。
2. 在后一种情形下，多个进程共享物理内存、磁盘、打印机个和其他资源。

八、引入线程的目的

• 减小进程切换的开销
• 提高进程内的并发程度
• 共享资源

那么问题来了，引入进程和线程的好处分别是什么？

• 引入进程的好处
  多个程序可以并发执行，改善资源使用率，提高系统效率。
• 引入线程的好处
  减少并发程序执行时所付出的时空开销，使得并发粒度更细，并发性更好。

九、多线程的原因：

1.主要原因是，在许多应用中同时发生着多种活动，其中某些活动随着时间的推移会被阻塞，通过将这些应用程序分解成可以准并行运行的多个顺序线程，程序设计模型会变得更简单。
2.线程比进程更加轻量级，所以线程比进程更加容易（更快）创建和撤销。
3.如果存在大量的计算和大量的I/O处理，拥有多个线程允许这些活动重叠进行，从而加快应用程序的执行速度。
4.在多CPU系统中，多线程是有益的，并且真正的并行有了实现的可能。

十、线程中包括：

• 程序计数器：记录接着要执行哪一条指令。
• 寄存器：保存线程当前的工作变量。
• 堆栈：记录执行历史。

线程概念试图实现的是，共享一组资源的多个线程的执行能力，以便这些线程可以为完成某一任务而共同工作。

十一、线程的实现

在用户空间中实现线程

把整个线程包放在用户空间中，这样用户级线程包可以在不支持线程的操作系统上实现，通过这一方法就可以用函数库实现线程。

#include #include 
#include 
#include 

#define NUMBER_OF_THREADS 10

void *print_hello_world(void *tid)
{
    /*本函数输出线程的标识符，然后退出。*/
    printf("Hello World.Greetings from thread %d0", tid);
    pthread_exit(NULL);
}

int main(int argc, char const *argv[])
{
    /*主程序创建10个进程，然后退出。*/
    pthread_t threads[NUMBER_OF_THREADS];
    int status, i;

    for(i = 0; i < NUMBER_OF_THREADS; i++){
        printf("Main here.Creating thread %d0\n", i);
        status = pthread_creat(&threads[i], NULL, print_hello_world, (void *)i);

        if(status != 0){
            printf("Oops.pthread_creat return error code %d0", status);
            exit(-1);
        }
    }
    exit(NULL);
}

在内核中实现线程

内核级线程就是内核有好几个分身，一个分身可以处理一件事的意思。这用来处理非同步事件很有用, 内核可以对每个非同步事件生个分身来处理。

内核级线程的操作非常轻便,几乎没有负担,而且对内核的结构有帮助。支持内核级线程的内核称作多线程内核。

例子：Windows 95/98/NT/2000, Solaris,Tru64 UNIX,Linux

以上的内容只是对进程与线程的概念以及一些其他的基础问题做了简单的阐述，在操作系统中关于进程内容的核心知识还得是进程的调度与通信，这两个问题留到下一篇讨论。

简单解释一些容易混淆的学术性名词。

系统吞吐量

• 指系统在单位时间内所完成的总工作量

作业的周转时间

• 指从作业进入系统开始，直至其完成并退出系统为止所经历的时间

批处理

• 批处理(batch processing )就是将作业按照它们的性质分组（或分批），然后再成组（或成批）地提交给计算机系统，由计算机自动完成后再输出结果，从而减少作业建立和结束过程中的时间浪费。

批处理系统

• 单道批处理系统
  内存中永远仅有一道作业的批处理操作系统称为单道批处理系统
• 多道批处理系统
  内存中可同时存在若干道作业的批处理操作系统称为多道批处理系统
  用户所提交的作业都先存放在外存上并排成一个队列，称为”后备队列”，然后作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使他们共享CPU和系统中的各种资源。

分时系统

• 利用分时技术的一种联机的多用户交互式操作系统，每个用户可以通过自己的终端向系统发出各种操作控制命令，完成作业的运行。分时是指把处理机的运行时间分成很短的时间片，按时间片轮流把处理机分配给各联机作业使用。

实时系统

• 系统特征是将时间作为关键参数。
  能够在”指定”或者”确定”的时间内完成系统功能以及对外部或内部事件在同步或异步时间内做出响应的系统,实时意思就是对响应时间有严格要求,要以足够快的速度进行处理.分为硬实时和软实时两种。

• 硬实时：某个动作必须绝对地在规定的时刻（或规定的时间范围）发生。

• 软实时：虽然也联系着一个截止时间，但是超过了也可以接受，并且不会引起任何永久性的损害。

处理机与处理器

• 处理机：计算机系统中存储程序和数据，并按照程序规定的步骤执行指令的部件。程序是描述处理机完成某项任务的指令序列。指令则是处理机能直接解释、执行的信息单位。处理机包括中央处理器，主存储器,I/O接口。

• 处理器：即中央处理器（CPU），其功能主要是解释计算机指令以及处理计算机软件中的数据。

并行和并发

• 并行指两个或多个事件在同一时刻发生
• 并发指两个或多个事件在同一时间间隔内发生

地址空间

• 是指从某个最小值的存储位置（通常是零）到某个最大值存储位置的列表。
• 地址空间里存放可执行程序、程序的数据、程序的堆栈。

从概率的角度来看CPU的利用率

假设一个进程等待I/O操作的时间与其停留在内存中时间的比为P。当内存中同时有n个进程时，则所有n个进程都在等待I/O（此时CPU空转）的概率是p^n。CPU的利用率为：

CPU利用率 = 1 - p^n