October 10, 2014

关于进程的问题

哲学家就餐问题等

一、经典的IPC问题

哲学家就餐问题

问题描述:

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

dinner

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

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

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

使用一个数组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.有没有可能发生阻塞到运行，就绪到阻塞的转换？

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

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

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

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

顺序执行的时候，因为I/O频率为50%，CPU时间为10分钟，所以每个作业需要20分钟，则最后一个作业需要40分钟来完成。
并行执行时，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，所以有时间剩余，系统可调用。