00-错题-大题

进程与线程

进程调度

对于进程调度的题目，甘特图是一种非常重要的简化手段。

01

$周转时间 = 作业完成时间 - 作业提交时间$ 。
$\overset{―}{周转时间} = \frac{周转时间_{1} + 周转时间_{2} + \dots + 周转时间_{i}}{i}$
$带权周转时间 (W_{i}) = \frac{周转时间}{作业实际运行时间}$ .

FIFO 的情况如下图所示：

平均周转时间= $\frac{30 + (50 - 10) + (55 - 20) + (65 - 30)}{4} = 35$ .

平均带权周转时间= $\frac{(\frac{30}{30}) + (\frac{40}{20}) + (\frac{35}{5}) + (\frac{35}{10})}{4} = 3.375$ .

SJF 的情况如下图所示：
image.png|700

平均周转时间= $\frac{30 + (35 - 20) + (45 - 30) + (65 - 10)}{4} = 28.75$ .

平均带权周转时间= $\frac{(\frac{30}{30}) + (\frac{15}{5}) + (\frac{15}{10}) + (\frac{55}{20})}{4} = 2.0625$ .

02

由于进程采用的是抢占式优先级调度算法，所以当优先级更高的作业进入时，就会挤压掉优先级低的进程。而又由于题目中提到我们是两道作业的批处理系统，所以内存中可以允许两个作业同时存在。
image.png|500

### 进程调度和作业调度的区别

作业调度是把程序从外存中调入内存的过程；而进程调度全程是在内存中运行的；
作业调度是建立就绪队列的过程，而进程调度是分配CPU资源（执行）的过程；

在上述例子中，A首先调入内存，并被分配CPU执行，当到了8点20时，B进入内存（此时内存中，共有两个作业，必须等待两个作业执行完成后，才能调入其他作业）。
由于B的优先级高于A，所以B先执行，执行完毕后，B退出内存，此时又两个作业等待进入内存，所以由作业调度算法可知，D首先被调入内存。
A的优先级大于D，所以A先执行，执行完毕后，C被调入内存；
C的优先级大于D，C先执行；
D执行；

由以上分析可知，非抢占式进入内存的时间、周转时间为：

job	到达时间	进入内存时间	结束时间	周转时间
A	8:00	8:00	9:10	70
B	8:20	8:20	8:50	30
C	8:30	9:10	10:00	90
D	8:50	8:50	10:20	90
平均带权周转时间				2.2625
平均周转时间				70

非抢占式也是同理了。

image.png|500

job	到达时间	进入内存时间	结束时间	周转时间
A	8:00	8:00	8:40	40
B	8:20	8:20	9:10	50
C	8:30	9:10	10:00	90
D	8:50	8:50	10:20	90
平均带权周转时间				2.2417
平均周转时间				67.5

03

这里只写 RR 算法，因为其他算法，上题中都有写过。

job	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
1	1					1			1		1		1		1	1	1	1	1
2		1	-
3			1				1	-
4				1	-
5					1			1		1		1		1	-

PV 操作

多线程问题的解题步骤

分析问题中存在的同步（happens before）与互质（mutex）关系；
有几对同步关系就有几个信号量。至于互斥关系也是一种同步关系；
假如A happens before B，那么就需要B先进行V操作，然后A需要先P再进行相应的工作；

为了显示方便，我简化了 api：

public class ThreadUtils {
    public static final int MAX_TIME = 1000000;
    public static void sleep(int mills) {
        try {
            Thread.sleep(mills);
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }

    public static void P(Semaphore semaphore) {
        try {
            semaphore.acquire();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }

    public static void V(Semaphore semaphore) {
        semaphore.release();
    }

    public static void createFn(Runnable runnable) {
        new Thread(runnable).start();
    }
}

Producer and Consumer

一组生产者进程和一组消费者进程共享一个初始为空、大小为 n的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。

互斥关系：生产者和消费者只能有一个访问缓冲区。

同步关系：

消费者，只有当缓冲区不为 null 的时候，才可以消费；
生产者，只有缓冲区不为 full 的时候，才可以生成；

故而，设计两个同步信号量 empty 和 full，互斥信号量 mutex。其中 empty 对应消费者进程，初值表示缓冲区可以消费的资源数量；而 full 对应生产者进程，初值表示缓冲区可以生产的容量。

#define MAXN = 5

sem_t empty = 0, full = MAXN, mutex = 1;

void producer()
{
	while (1) {
		P(full);
		
		P(mutex);
		// produce something
		V(mutex);
		
		V(empty);
	}
}

void consumer()
{
	while (1) {
		P(empty);
		
		P(mutex);
		// consume something
		V(mutex);

		V(full);
	}
}

Producer and Consumer Plus

桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。

互斥关系：盘子不能允许同时放水果。但是允许同时拿水果，放和拿不冲突。

同步关系：

dad happens before daughter。所以设置一个信号量 apple 表示盘子中能拿的苹果的数量；
mom happens before son。设置信号量 orange，表示能拿的橙子的数量；
plate happens before dad and mom。设置信号量 plate，表示桌子上是否能放水果。1 表示可以，0 表示不可以；

注意题干中，有“只有当盘子为空的时候，才可以放水果”。所以，这就意味着，盘子里只要有一个水果，就不能放了。所以，不能忘记了第三个同步关系；
如果我们只用三个信号量，第一条实际上预示了dad和daughter，mom和son必须是连续执行的，也就是说，dad一把东西放到桌子上，那么daughter就应该拿走；

Java 版本：

public class DayAndMom {
    static final Semaphore plate = new Semaphore(1);
    static final Semaphore apple = new Semaphore(0);
    static final Semaphore orange = new Semaphore(0);

    public static void main(String[] args) {
        Thread dad = new Thread(() -> {
            while (true) {
                ThreadUtils.P(plate);
                Assert.isTrue(plate.availablePermits() == 0);
                ThreadUtils.V(apple);
            }
        });
        Thread mom = new Thread(() -> {
            while (true) {
                ThreadUtils.P(plate);
                Assert.isTrue(plate.availablePermits() == 0);
                ThreadUtils.V(orange);
            }
        });
        Thread son = new Thread(() -> {
            while (true) {
                Assert.isTrue(orange.availablePermits() < 2);
                ThreadUtils.P(orange);

                ThreadUtils.V(plate);
            }
        });
        Thread daughter = new Thread(() -> {
            while (true) {
                Assert.isTrue(apple.availablePermits() < 2);
                ThreadUtils.P(apple);

                ThreadUtils.V(plate);
            }
        });

        dad.start();
        mom.start();
        son.start();
        daughter.start();
    }
}

Reader And Writer

有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程 (读进程或写进程) 同时访问共享数据时则可能导致数据不一致的错误。因此要求：

允许多个读者可以同时对文件执行读操作；

只许一个写者往文件中写信息；

一写者在完成写操作之前不允许其他读者或写者工作；

执行写操作前，应让已有的读者和写者全部退出。

互斥关系：写者之间是互斥的，写者和读者之间是互斥的。临界资源是文件。

同步关系：

对于读者，必须检查是否有写者在写；
对于写者，也必须检查是否写者在写，读者在读；

我们可以设置变量 count 表示当前读者的数量，如果当前读者数量为 0，则可以写；如果，当前读者不为 0，则不可以写。

当同步关系依赖于线程的数量关系时，可以设置一个临界资源（本题中为count）来表示线程的数量；
读者写者的关键特征就是有一个互斥访问的计数器count；

实现的 Java 代码如下：

public class ReaderAndWriter {
    static final Semaphore rw = new Semaphore(1);
    static final Semaphore mutex = new Semaphore(1);
    static int count = 0;

    public static void main(String[] args) {
        for (int i = 0; i < 3; i++) {
            ThreadUtils.createFn(new Writer());
            ThreadUtils.createFn(new Reader());
        }
    }
}


class Reader implements Runnable {
    @Override
    public void run() {
        for (int i = 0; i < ThreadUtils.MAX_TIME; i++) {
            ThreadUtils.P(ReaderAndWriter.mutex);
            if (ReaderAndWriter.count == 0) {
                ThreadUtils.P(ReaderAndWriter.rw);
            }
            ReaderAndWriter.count++;
            ThreadUtils.V(ReaderAndWriter.mutex);

            Assert.isTrue(ReaderAndWriter.rw.availablePermits() == 0);

            ThreadUtils.P(ReaderAndWriter.mutex);
            ReaderAndWriter.count--;
            if (ReaderAndWriter.count == 0) {
                ThreadUtils.V(ReaderAndWriter.rw);
            }
            ThreadUtils.V(ReaderAndWriter.mutex);
        }
    }
}

class Writer implements Runnable {
    @Override
    public void run() {
        for (int i = 0; i < ThreadUtils.MAX_TIME; i++) {
            ThreadUtils.P(ReaderAndWriter.rw);
            // 如果当前有读者
            Assert.isTrue(ReaderAndWriter.count == 0);
            ThreadUtils.V(ReaderAndWriter.rw);
        }
    }
}

Philosopher eating

一张圆桌边上坐着 5 名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭，如图 2.12 所示。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。若筷子已在他人手上，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。

互斥关系：两个哲学家不能拿起同一个筷子。

同步关系：当哲学家缺少筷子的时候，必须旁边的哲学家用餐完毕。

对哲学家进行编号 0-4，对筷子进行编号为 0-4，对于 i 号哲学家，左边的筷子为 i，右边的筷子为 $(i + 4) % 5$ 。

如果我们粗暴的直接按照以下方式实现，那么就会出现死锁，试想一下，当所有哲学家都拿到了左边的筷子，那么就不会有哲学家进餐了, 此时就会出现死锁；

static Runnable phi(int i) {
        return () -> {
            for (int j = 0; j < ThreadUtils.MAX_TIME; j++) {
                ThreadUtils.P(chops[i]);
                ThreadUtils.P(chops[(i + 4) % 5]);
                System.out.println("eat by " + Thread.currentThread());
                ThreadUtils.V(chops[i]);
                ThreadUtils.V(chops[(i + 4) % 5]);
            }
        };
    }

也就是说死锁会发生在五个哲学家同时进餐的时候，所以我们要尝试打破这个条件即可解决死锁的问题；

解决这个问题有两种方法：

保证同一时刻最多只有四个哲学家可以进餐；
让第一个哲学家拿右边的筷子就可以打破这个死锁；
只有当哲学家有两个筷子的时候，才拿起筷子；

第一个哲学家拿右边的筷子

	static final Semaphore[] chops = new Semaphore[5];

    public static void main(String[] args) {
        for (int i = 0; i < chops.length; i++) {
            chops[i] = new Semaphore(1);
        }

        for (int i = 0; i < 5; i++) {
            ThreadUtils.createFn(phi1(i));
        }

    }
    
	static Runnable phi(int i) {
        return () -> {
            for (int j = 0; j < ThreadUtils.MAX_TIME; j++) {
                if (i > 0) {
                    ThreadUtils.P(chops[i]);
                    ThreadUtils.P(chops[(i + 4) % 5]);
                } else {
                    ThreadUtils.P(chops[(i + 4) % 5]);
                    ThreadUtils.P(chops[i]);
                }
                System.out.println("eat by " + Thread.currentThread());
                ThreadUtils.V(chops[i]);
                ThreadUtils.V(chops[(i + 4) % 5]);
            }
        };
    }

只有两个筷子的时候才拿筷子

	static final Semaphore[] chops = new Semaphore[5];
    static final Semaphore mutex = new Semaphore(1);

	static Runnable phi2(int i) {
        return () -> {
            while (true) {
                ThreadUtils.P(mutex);

                ThreadUtils.P(chops[i]);
                ThreadUtils.P(chops[(i + 4) % 5]);
                log.info("phi: {} get left: {} and right: {}", i, i, (i + 4) % 5);
                ThreadUtils.V(chops[i]);
                ThreadUtils.V(chops[(i + 4) % 5]);

                ThreadUtils.V(mutex);
            }
        };
    }

只有四个哲学家能够进餐

只允许四个哲学家进餐，于是我们可以将这四个哲学家数量视为一种，视为一种同步关系。所以设计一个信号量 num 表示当前还有几个哲学家可以进餐。

    static final Semaphore[] chops = new Semaphore[5];
    static final Semaphore num = new Semaphore(4);

	static Runnable phi3(int i) {
        return () -> {
            while (true) {
                ThreadUtils.P(num);

                ThreadUtils.P(chops[i]);
                ThreadUtils.P(chops[(i + 4) % 5]);
                log.info("phi: {} get left: {} and right: {}", i, i, (i + 4) % 5);
                ThreadUtils.V(chops[i]);
                ThreadUtils.V(chops[(i + 4) % 5]);

                ThreadUtils.V(num);
            }
        };
	}

Smoker

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但耍卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放到桌子上，挑有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉已完成，此时供应者就会将另外两种材料放到桌上，如此重复（让三个抽烟者轮流地抽烟）。

互斥关系：抽烟的行为并不互斥。但是供应者和其中一个抽烟者的行为必须是连续的。也就是说，只要供应者开始提供了烟，那么其他抽烟者就和这个供应者互斥。抽烟者之间是必定互斥的。

同步关系：抽烟者必须等到供应者提供了制定材料才可以进行抽烟。

对于 smoker 1，需要等待纸和水；
对于 smoker 2，需要等待烟草和水；
对于 smoker 3，需要等待烟草和纸；

难点在于供应者是如何做到制定两种材料的，使得能够让三个抽烟者轮流抽烟，而不会产生饥饿现象。

可以循环提供，设置一个共享变量 circle：

如果 $c i r c l e % 3 = 0$ 。提供纸和水；
如果 $c i r c l e % 3 = 1$ 。提供烟草和水；
如果 $c i r c l e % 3 = 2$ 。提供烟草和纸；

下面先给出一个错误的算法。

public class Smoker {
    static final Semaphore tobacco = new Semaphore(0);
    static final Semaphore paper = new Semaphore(0);
    static final Semaphore water = new Semaphore(0);
    static final Semaphore mutex = new Semaphore(1);
    static int circle;

    public static void main(String[] args) {
        ThreadUtils.createFn(smoker1());
        ThreadUtils.createFn(smoker2());
        ThreadUtils.createFn(smoker3());
        ThreadUtils.createFn(provider());
    }

    static Runnable smoker1() {
        return () -> {
            while (true) {
                ThreadUtils.P(paper);
                ThreadUtils.P(water);
                log.debug("smoker1 smoke.....");

                ThreadUtils.V(mutex);
            }
        };
    }
    static Runnable smoker2() {
        return () -> {
            while (true) {
                ThreadUtils.P(tobacco);
                ThreadUtils.P(water);
                log.debug("smoker2 smoke.....");

                ThreadUtils.V(mutex);
            }
        };
    }
    static Runnable smoker3() {
        return () -> {
            while (true) {
                ThreadUtils.P(tobacco);
                ThreadUtils.P(paper);
                log.debug("smoker3 smoke.....");

                ThreadUtils.V(mutex);
            }
        };
    }

    static Runnable provider() {
        return () -> {
            while (true) {
                ThreadUtils.P(mutex);
                log.info("provider: to: {}, pa:{}, wa:{}", tobacco.availablePermits(), paper.availablePermits(), water.availablePermits());
                if (circle % 3 == 0) {
                    ThreadUtils.V(paper);
                    ThreadUtils.V(water);
                } else if (circle % 3 == 1) {
                    ThreadUtils.V(tobacco);
                    ThreadUtils.V(water);
                } else {
                    ThreadUtils.V(paper);
                    ThreadUtils.V(tobacco);
                }
                circle = (circle + 1) % 3;
            }
        };

    }

}

如果我们将提供者的这段代码 ThreadUtils.P(mutex);，放到开头，是不会成功的，会造成死锁的问题。

死锁的原因出在当provider获取了mutex之后，需要smoker手动释放，而如果此时smoker也被阻塞，那么就会造成死锁。

我们举例说明这种情况，为了阐述方便，我们将provider线程简写为p，将smoker线程简写为s1, s2, s3：

假如某个时刻，p提供了tobacco和paper，但是s2拿了tobacco、s1拿了paper，此时本应当进行的s3就会因为拿不到tobacco而一直被阻塞，从而不释放mutex，使得p也被阻塞。形成死锁的局面。这属于死锁的必要条件之二——保持并持有。

产生这个死锁的根本原因就是其他线程拿了本不该拿（如果只有一个资源存在就不应该拿）的东西。所以，如果能够一起分配这两个资源，就可以很好的避免这个死锁。

根据上述的问题，我们可以重新设计信号量，将获取 papper 和 water 设计为信号量 a，tobacco 和 water 设计为信号量 b，tobacco 和 paper 设计为 c，这样就可以实现资源的统一获取了。

public class Smoker {
    static final Semaphore a = new Semaphore(0);
    static final Semaphore b = new Semaphore(0);
    static final Semaphore c = new Semaphore(0);
    static final Semaphore mutex = new Semaphore(1);
    static int circle;

    public static void main(String[] args) {
        ThreadUtils.createFn(smoker1());
        ThreadUtils.createFn(smoker2());
        ThreadUtils.createFn(smoker3());
        ThreadUtils.createFn(provider());
    }

    static Runnable smoker1() {
        return () -> {
            while (true) {
                ThreadUtils.P(a);
                log.debug("smoker1 smoke.....");

                ThreadUtils.V(mutex);
            }
        };
    }

    static Runnable smoker2() {
        return () -> {
            while (true) {
                ThreadUtils.P(b);
                log.debug("smoker2 smoke.....");

                ThreadUtils.V(mutex);
            }
        };
    }

    static Runnable smoker3() {
        return () -> {
            while (true) {
                ThreadUtils.P(c);
                log.debug("smoker3 smoke.....");

                ThreadUtils.V(mutex);
            }
        };
    }

    static Runnable provider() {
        return () -> {
            while (true) {
                log.info("provider...");
                ThreadUtils.P(mutex);
                if (circle % 3 == 0) {
                    ThreadUtils.V(a);
                } else if (circle % 3 == 1) {
                    ThreadUtils.V(b);
                } else {
                    ThreadUtils.V(c);
                }
                circle = (circle + 1) % 3;
            }
        };
    }
}

信箱机制

分析题意可知， $p_{0}, p_{1}, m_{0}$ 之间互为生产者消费者模式，而 $p_{0}, p_{1}, m_{1}$ 也互为生产者消费者模式。所以，肯定有四对同步关系，分别是：

$p_{0}$ 必须等到 $m_{0}$ 有产品才可以取走；设置信号量 m0emp
$p_{1}$ 的生产必须要 $m_{0}$ 不为满；设置信号量: m0full
$p_{1}$ 必须等到 $m_{1}$ 有产品才可以取走；设置信号量 m1emp
$p_{0}$ 的生产必须要 $m_{1}$ 不为满；设置信号量 m1full

故而对于线程 $p_{0}, p_{1}$ 要同时完成生产和消费的任务，我们的实现代码如下:

    static final Semaphore m0Emp = new Semaphore(2);
    static final Semaphore m0full = new Semaphore(0);
    static final Semaphore m1Emp = new Semaphore(0);
    static final Semaphore m1full = new Semaphore(3);
    static final Semaphore mutex_0 = new Semaphore(1);
    static final Semaphore mutex_1 = new Semaphore(1);

    public static void main(String[] args) {
        ThreadUtils.createFn(p0());
        ThreadUtils.createFn(p1());
    }

    static Runnable p0() {
        return () -> {
            while (true) {
                ThreadUtils.P(m0Emp);

                ThreadUtils.P(mutex_0);
                log.info("m0 take 1");
                ThreadUtils.V(mutex_0);

                ThreadUtils.V(m0full);
                ThreadUtils.P(m1full);

                ThreadUtils.P(mutex_1);
                log.info("m1 put 1");
                ThreadUtils.V(mutex_1);

                ThreadUtils.V(m1Emp);
            }
        };
    }

    static Runnable p1() {
        return () -> {
            while (true) {
                ThreadUtils.P(m1Emp);

                ThreadUtils.P(mutex_1);
                log.info("m1 take 1");
                ThreadUtils.V(mutex_1);

                ThreadUtils.V(m1full);
                ThreadUtils.P(m0full);

                ThreadUtils.P(mutex_0);
                log.info("m0 put 1");
                ThreadUtils.V(mutex_0);
                
                ThreadUtils.V(m0Emp);
            }
        };
    }

Internship on computer

如果把两个同学看成一个整体，那么这个问题就转化为了生产者和消费者的问题了。老师是消费者，需要检查电脑这个资源是否还存在，同学是生产者，霸占电脑的行为相当于生产了资源。

@Slf4j
public class InternshipOnComputer {
    static final int n = 2;
    static final int m = 1;
    static final Semaphore pcFull = new Semaphore(2 * m);
    static final Semaphore pcEmp = new Semaphore(0);
    static final Semaphore mutex = new Semaphore(1);

    public static void main(String[] args) {
        ThreadUtils.createFn(teacher());
        for (int i = 0; i < n; i++) {
            ThreadUtils.createFn(group(i));
        }
    }

    static Runnable teacher() {
        return () -> {
            while (true) {
                ThreadUtils.P(pcEmp);

                ThreadUtils.P(mutex);
                log.info("teacher check group");
                ThreadUtils.V(mutex);

                ThreadUtils.V(pcFull);
            }
        };
    }

    static Runnable group(int id) {
        return () -> {
            while (true) {
                ThreadUtils.P(pcFull);

                ThreadUtils.P(mutex);
                log.info("group: {} has taken one pc", id);
                ThreadUtils.V(mutex);

                ThreadUtils.V(pcEmp);
            }
        };
    }
}

死锁的避免-银行家算法

银行家的算法的核心思想就是添加一个管理员的角色，根据当前系统拥有的资源，决定是否应该分配资源给线程或者进程，如果资源不足，就推迟分配；如果资源足够，就直接分配。这样，可以避免线程抢到了不应该的资源从而造成死锁。

首先，我们定义一个抽象矩阵 matrix，横轴表示进程，竖轴表示资源，实现三个实体矩阵：

Max 矩阵：表示每个进程 i 对资源 j 的最大需求（总需求量）；
Allocation 矩阵：表示每个进程已分配的资源；
Need 矩阵：表示每个进程接下来还需要多少资源；
我们可以很好的推导出三个矩阵的关系：Need = Max - Allocation。

再定义一个序列（向量）Available，表示当前系统中的资源数量；

我们再定义请求向量 $R e q u e s t_{i} [j] = k$ 。表示进程 i 需要请求资源 j，k 个。

算法步骤

先进行资源检查。假如当前请求的资源量超过了该进程所需的资源量，则报错；否则进入步骤2。即检查 $R e q u e s t_{i} [j] <= N e e d [i, j]$ 。
如果发现请求的资源量大于系统的剩余资源量（没有资源进行分配），则让改进程等待；否则进入3。即检查 $R e q u e s t_{i} [j] <= A v a i l a b l e [j]$ 。
然后系统尝试把资源分配给进程，改变相关矩阵的数值。即改变Available、Allocation、Need的值；
进行安全性检测，如果安全，则确认分配资源，否则回退这次资源的分配，让进程进入等待状态；

安全性算法

安全性算法就是判断是否存在一个进程调度序列使得能够在现有的系统资源内完成执行。

假设当前的进程持有资源Allocation，那么该进程执行完毕后会释放这些资源。所以随着线程不断的正常调度运行，系统资源会呈现增加的趋势。

如果在调度的过程中，发现当前的当前系统无法提供给任一线程（进程）足够的资源，就认为是不安全的。

01

image.png|600

（1）安全序列很好求，可以目测出来，P0->P3->P4->P1->P2。肯定是安全的；
（2）我们首先尝试把资源分配给 P 2 进程，进行安全性检查，此时的资源分配情况变为了；


Process	Allocation	Need	Available
P0	0032	0012	0400
P1	1000	1750
P2	2576	1134
P3	0332	0652
P4	0014	0656
然而，在尝试资源分配后，剩余的资源已经不足以维持进程的执行了，会造成死锁，所以，不能分配。

死锁相关

01

假设，船和车都是一直尝试前进的。

显然，船离 A 100 米的时候 A 吊起，那么其实公路上的车就会开始堆积，如果在船完全通过 B 之前，车流就堆积到了 B 上（挤满了 AB 之间的公路），就会造成死锁的现象。

解决的方法也很好办，如果 AB 之间的公路已经满员了，就不能允许其他车再上 B 桥了。

内存管理

请求分页

01

对于一个请求分页系统，假定内存访问时间为200ns，而平均缺页故障的服务时间为8ms，请回答：
（1）如果1000次访问内存引起一次缺页故障，数据的有效访问时间是多少？
（2）如果有效访问时间要比访问内存慢少于10%，即有效访问时间在200ns和200ns*（1+10%）之间，那么大约多少次内存访问会出现一次缺页故障？

要解决这些问题，我们可以使用有效访问时间（EAT）的公式：

E A T = (1 - p) \times 内存访问时间 + p \times 缺页故障服务时间

其中 $p$ 是缺页故障的概率。

（1）计算有效访问时间

给定条件是，1000 次访问内存引起一次缺页故障，所以 $p = \frac{1}{1000}$ 。内存访问时间是 200 ns，缺页故障服务时间是 8 ms，我们需要将这两个时间单位统一，通常我们将它们都转换为纳秒：

8 m s = 8 \times 10^{6} n s

现在我们可以计算 EAT：

\begin{aligned} E A T & = (1 - \frac{1}{1000}) \times 200 n s + \frac{1}{1000} \times 8 \times 10^{6} n s \\ E A T & = (999 / 1000) \times 200 n s + (1 / 1000) \times 8 \times 10^{6} n s \\ E A T & = 199.8 n s + 8000 n s \\ E A T & = 8199.8 n s \end{aligned}

所以，数据的有效访问时间是 8199.8 ns。

（2）计算允许的最大缺页故障概率

我们想要 EAT 比内存访问时间慢不超过 10%，即：

\begin{aligned} E A T & \leq 200 n s + 10 % \times 200 n s \\ E A T & \leq 200 n s + 20 n s \\ E A T & \leq 220 n s \end{aligned}

我们将这个条件代入 EAT 的公式，解出 $p$ ：

\begin{aligned} 220 n s & \geq (1 - p) \times 200 n s + p \times 8 \times 10^{6} n s \\ 220 n s & \geq 200 n s - 200 n s \times p + 8 \times 10^{6} n s \times p \\ 20 n s & \geq 8 \times 10^{6} n s \times p - 200 n s \times p \\ 20 n s & \geq p \times (8 \times 10^{6} n s - 200 n s) \\ p & \leq \frac{20 n s}{8 \times 10^{6} n s - 200 n s} \\ p & \leq \frac{20}{8 \times 10^{6} - 200} \end{aligned}

计算 $p$ 的值：

p \leq \frac{20}{7999800} p \leq 2.50031254 \times 10^{- 6}

现在我们知道了缺页故障的概率，我们可以计算出平均多少次内存访问会出现一次缺页故障：

缺页故障间隔 = \frac{1}{p} 缺页故障间隔 \approx \frac{1}{2.50031254 \times 10^{- 6}} 缺页故障间隔 \approx 399992

所以，大约每 399992 次内存访问会出现一次缺页故障，以保持有效访问时间在 200 ns 至 220 ns 之间。

02-2012 统考真题

某请求分页系统的局部页面置换策略如下：

系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。

假设不考虑其它进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的 <虚拟页号，访问时刻> 是：<1, 1>、<3, 2>、<0, 4>、<0, 6>、<1, 11>、<0, 13>、<2, 14>。请回答下列问题。
（1）访问 <0, 4> 时，对应的页框号是什么？说明理由。
（2）访问 <1, 11> 时，对应的页框号是什么？说明理由。
（3）访问 <2, 14> 时，对应的页框号是什么？说明理由。
（4）该策略是否适合于时间局部性好的程序？说明理由。

（1）4 <5，说明是第一次扫描，所以对应的页框应该顺序分配，为 21.
（2）32
注意看 <0, 6> 这个访问，由于在第一轮扫描中，我们也访问了 0 号页，所以 0 号页维持页框 21 不动。由于在进程中的页框 32、 15 没有被访问，所以被重新放回空闲页框尾部，第二轮结束时，链表为：41->32->15。
当我们尝试在第三轮访问 1 号页是，由于在第一轮中已经访问过，所以就直接把该页放回驻留集中，所以 1 号页对应的还是 32 号页框。
此时的链表为 41->15

<0, 13> 的访问不变对应的是 21 号页框。

（3）41
<2,14> 从来没有被访问过，所以直接从空闲页框链表首部取出一个页框分配给 2 号页。所以对应的页框为 41.

（4）
适合。这种方法保存了一定的页框和页的对应关系，在一定程序上避免了页框的重新分配，提高了效率。什么情况下，需要重新分配页框呢？只有在某轮中没有访问过某个页面，才有可能回收那个页面的页框（如果请求了新的页，并且该页框正好位于链表首部，才会被重新分配）。

根据以上分析，可以推断，假如一个页面访问的时间很频繁，那么就算该页退出了驻留集，之后还是有很大概率再直接返回驻留集中，很好的适应了时间局部性。

03-2009 统考真题

请求分页管理系统中，假设某进程的页表内容如下表所示：


页号	页框（Page Frame）号	有效位（存在位）	磁盘地址
0	101H	1	33AH
1	－	0	326H
2	254H	1	776H
3	－	0	120H

页面大小为4 KB，一次内存的访问时间是100 ns，一次快表（TLB）的访问时间是10 ns，换入一个页面的平均时间为 $10^{8}$ ns（已含更新TLB和页表的时间）。进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略（假设TLB初始为空，地址转换时先访问TLB，再访问页表；有效位为0表示页面不在内存）。

（1）依次访问上述三个虚地址：2362H、1565H、25A5H，各需多少访问时间？给出计算过程。

（2）基于上述访问序列，计算1565H的物理地址，并说明理由。

（1）
逻辑地址分为两部分，一是页号，二是偏移量，我们首先要确定页号，由于页面大小为 4 KB，~~所以总共有 12 位页号~~（页地址占低 12 位）。故而，偏移地址都是最后一位。

2362H 对应的页号为 2，磁盘块的地址为 776，偏移量为 2，所以地址为 778 H。先访问了 TLB 再访问了页表和主存所以时间为： $10 + 100 + 100 = 210 n s$ .
1565H 对应的页号为 1，访问的页面不在内存和快表中，产生缺页中断，耗时 $10^{8}$ ns，更新了 TLB 和页表，故总时间为 $(10 + 100 + 10^{8}) + (10 + 100) = 10^{8} + 220 n s$ .

25A5H 对应页号为 2，该页已经在 TLB 中，所以直接形成物理地址= $776 H + 5 H = 781 H$ 。由于只访问了一次 TLB 和主存，所以时间为 $10 + 100 = 110 n s$ 。

（2）
再产生缺页中断的时候，应该选择一页进行替换。由于 0 号页面并没有访问，所以应该淘汰 0 号位，将该外存的数据进行替换。

物理地址= $页框 + 偏移地址$ （注意这里的+表示拼接的意思），故为 101565H。

分页存储管理中的页表与虚拟内存管理中请求分页管理的页表的结构有什么区别，为什么一个用的是物理块号，一个用的是页框呢？为什么物理地址的计算方式一个是 $b * L + o f f s e t$ ，一个是页框拼接上offset呢？

将内存空间分为一个个大小相等的分区（比如：每个分区4KB），每个分区就是一个“页框”（Page Frame 页框=页帧=内存块=物理块=物理页面）。每个页框有一个编号，即“页框号”（页框号=页帧号=内存块号=物理块号=物理页号）。
所以上述的页框号，就是物理块号，计算过程是一样的，我们可以稍微计算一下，不论是按照拼接还是按照第一种计算方式答案都是一样的。
如何推导？拼接实际上意味着，页框号先向左位移 $\log_{2} L$ 位再与偏移地址相加。由于偏移地址的位数一定小于等于左移位数，所以从视觉上就像是相加一样。以本题为例， $101_{16} * 2048_{10} + 565_{16} = 101565 H$ .

页表

01

某进程程序长度为8KB，分页管理系统中的页长度为2KB，如果该进程分配内存后的页表如下表所示，求程序中逻辑地址为3840的物理地址。

页号	块号
0	5
1	3
2	4
3	7

容易求出对应的页号为 1，偏移量为 1792.

物理地址= $块号 * 块大小 + 偏移量 = 3 * 2048 + 1792 = 7936$ .

物理地址= $块号 * 块大小 + 偏移量$ ；

段表

01

物理地址= $b a s e + 偏移量$ .

（1）：219+430 = 649
（2）：2300+10=2310
（3）：2311
（4）：不合法，不能访问
（5）：1727
（6）：越界

页面置换算法

对于页面置换算法的计算题，都要画一张表格解决！

01

由于，内存块为 3 或者 5 的时候，其计算方法都差不多，所以这里就只展示内存块为 3 的情况。

LRU	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
b 1	1	1	1	4	4	4	5	5	5	1	1	1	7	7	7	2	2	2	2	2
b 2		2	2	2	2	2	2	6	6	6	6	3	3	3	3	3	3	3	3	3
b 3			3	3	3	1	1	1	2	2	2	2	2	6	6	6	1	1	1	6
					0						0				0			0	0

FIFO	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
b 1	1	1	1	4	4	4	4	6	6	6	6	3	3	3	3	2	2	2	2	6
b 2		2	2	2	2	1	1	1	2	2	2	2	7	7	7	7	1	1	1	1
b 3			3	3	3	3	5	5	5	1	1	1	1	6	6	6	6	6	3	3
缺页否					0						0				0			0

OPT	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
b 1	1	1	1	1	1	1	1	1	1	1	1	3	3	3	3	3	3	3	3	6
b 2		2	2	2	2	2	2	2	2	2	2	2	7	7	7	2	2	2	2	2
b 3			3	4	4	4	5	6	6	6	6	6	6	6	6	6	1	1	1	1
缺页否					0	0			0	0	0			0	0			0	0	0

02

由于页面的大小为 100 字，所以每次访问的页面为 $\frac{d}{100}$ 。从而得到页面的访问序列为 $0, 0, 1, 1, 0, 3, 1, 2, 2, 4, 4, 3$ 。

又由于基本可用内存为 200 字，所以总共有两块。

FIFO	0	0	1	1	0	3	1	2	2	4	4	3
b 1	0	0	0	0	0	3	3	3	3	4	4	4
b 2			1	1	1	1	1	2	2	2	2	3
缺页否		0		0	0		0		0		0

LRU	0	0	1	1	0	3	1	2	2	4	4	3
b 1	0	0	0	0	0	0	1	1	1	4	4	4
b 2			1	1	1	3	3	2	2	2	2	3
缺页否		0		0	0

OPT	0	0	1	1	0	3	1	2	2	4	4	3
b 1	0	0	0	0	0	3	3	3	3	3	3	3
b 2			1	1	1	1	1	2	2	4	4	4
缺页否		0		0	0		0		0		0	0

03

若每页可以存放 200 个整数，那么就可以存放两行数据，所以对于程序 A 来说，总共有 100 行，那么就会有 50 次的缺页。

而程序 B，由于存放顺序不同，即每次只存放两个数就要切换到下两行存取，所以缺页次数为 5000 次。

100 个整数也是同理的。

文件

文件的物理地址计算

01

很明显，这是混合索引结构。包含直接索引块，多级间接索引块。

总共有 10 个直接地址块，也就是当文件大小不超过 10 KB 时，就可以直接在直接地址中访问到地址。访问方法是 $\frac{文件偏移量}{盘块大小}$ 。

一次间接如何被访问到？只有当 $⌊ \frac{文件偏移值}{盘块大小} ⌋ \geq 10$ 时（超过直接地址），才有可能访问到一次间接。一次间接存储着 1 KB 大小的索引表，由于每个盘块号为 4 B，所以总共有 256 个块。也就是说当 $10 \leq ⌊ \frac{文件偏移量}{盘块大小} ⌋ \leq 256 + 10$ 时，是进入一次间接的。

同理，对于二次间接，总共有 256 个一级索引表，每个索引表又对应了 256 的块，所以，访问范围为:

266 < ⌊ \frac{文 件 偏 移 量}{盘 块 大 小} ⌋ \leq 10 + 256 + 256^{2} = 65802

对于（1），答案为 $⌊ \frac{8000}{1024} ⌋ = 7 余 832$ .所以我们找到 101 块偏移量为 832 的地址就是我们要访问的数据。

对于（2），由于 $⌊ \frac{13000}{1024} ⌋ = 12$ 且 $13000 % 1024 = 712$ . 由上，访问一次间接，访问到 954 号块，偏移量为 712 字节。

对于（3）， $⌊ \frac{350000}{1024} ⌋ = 341$ 且 $35000 % 1024 = 816$ . 访问二次间接。先访问到一级索引表 (341-10-256)=75，说明访问 0 号索引表， $75 % 256 = 75$ ，访问 0 号索引表的 75 位置，也就是 333 块中的 816 字节。

文件系统

01

（1）
采用分解法前：
不难计算得知，总共需要 32 个盘块存储这些 FCB。最好的情况下，我们只需要一次就可以访问到，最坏的情况，则需要 32 次，所以平均次数为 $⌈ \frac{1 + 32}{2} ⌉ = 17$ .

采用分解法后，总共需要 5 个盘块存储第一部分，然后查找到后再通过这个盘块找到其余部分。所以，根据文件名查找到文件的访问磁盘次数为 $⌈ \frac{1 + 5}{2} ⌉ = 3$ ，根据内部号访问到其他数据则需要 $3 + 1 = 4$ 次。

（2）
根据（1）的计算过程，要想访问磁盘数量减小，需要满足的条件为：

\begin{aligned} \frac{1 + n}{2} & > \frac{1 + m}{2} + 1 \\ ⟹ m & < n - 2 \end{aligned}

02

由题可知，位示图的矩阵大小为 $8 * 32$ 。
所以，根据公式可知， $i = ⌊ \frac{b - 1}{32} ⌋ + 1 = 4$ ， $j = (b - 1) % 32 + 1 = 4$ .

I/O

磁盘

我实现了四种磁盘调度算法，如下所示：

import json
from typing import List, Set, Dict, Tuple


def read():
    with open('request_queue.json', encoding='utf-8') as f:
        return json.load(f)


re_arr: List[int] = read()['queue']
cur_index = read()['cur']
min_v = read()['min']
max_v = read()['max']


def fcfs():
    cur = cur_index
    ans = 0
    for re in re_arr:
        ans += abs(cur - re)
        cur = re
    return ans


def sstf():
    cur = cur_index
    ans = 0
    min_v = 1e9
    for i in range(0, len(re_arr)):
        min_v = min(re_arr, key=lambda x: abs(x - cur))
        print(f'min_v: {min_v}')
        ans += abs(cur - min_v)
        cur = min_v
        re_arr.remove(min_v)
    return ans


def scan(seq: bool = True):
    """

    :param seq: 一开始扫描的顺序, 递增or递减
    :return:
    """
    ans: int = 0
    re_arr.sort()
    index = 0
    # find value larger than or equals cur_index.
    for i in range(0, len(re_arr)):
        if re_arr[i] >= cur_index:
            index = i
            break

    cur = cur_index
    if seq:
        re_arr.append(max_v)
        for i in range(index, len(re_arr)):
            print(f'cur: {cur}')
            ans += abs(re_arr[i] - cur)
            cur = re_arr[i]

        for i in range(index - 1, -1, -1):
            print(f'cur: {cur}')
            ans += abs(re_arr[i] - cur)
            cur = re_arr[i]

        print(f'cur: {cur}')
    else:
        re_arr.insert(0, min_v)
        index = index - 1
        for i in range(index, -1, -1):
            ans += abs(re_arr[i] - cur)
            cur = re_arr[i]

        for i in range(index, len(re_arr)):
            ans += abs(re_arr[i] - cur)
            cur = re_arr[i]

    print(f'sorted arr: {re_arr}')
    return ans


def cscan(seq: bool = True):
    ans: int = 0
    re_arr.sort()
    cur = cur_index
    re_arr.insert(0, min_v)
    re_arr.append(max_v)

    # find value larger than or equals cur_index.
    index = 0
    for i in range(0, len(re_arr)):
        if re_arr[i] >= cur_index:
            index = i
            break

    if seq:
        for i in range(index, len(re_arr)):
            print(f'cur: {cur}')
            ans += abs(re_arr[i] - cur)
            cur = re_arr[i]

        for i in range(0, index):
            print(f'cur: {cur}')
            ans += abs(re_arr[i] - cur)
            cur = re_arr[i]

        print(f'cur: {cur}')
    else:
        index -= 1
        for i in range(index, -1, -1):
            print(f'cur: {cur}')
            ans += abs(re_arr[i] - cur)
            cur = re_arr[i]

        for i in range(len(re_arr) - 1, index, -1):
            print(f'cur: {cur}')
            ans += abs(re_arr[i] - cur)
            cur = re_arr[i]

    print(f'cur: {cur}')
    print(f'sorted arr: {re_arr}')
    return ans


if __name__ == '__main__':
    print(f"request list: {re_arr}")
    print(f'cur_index: {cur_index}')
    print(f'ans: {cscan()}')

{
  "cur": 143,
  "min": 0,
  "max": 199,
  "queue": [
    86,
    147,
    91,
    177,
    94,
    150,
    102,
    175,
    130
  ]
}

01

磁盘旋转周期为 20 ms，也就是划过一个区域的时间为 5 ms，由于还有处理程序，所以读取一个区域的时间为 10 ms（不包括寻道的时间）。

假设磁头一开始准备读取 A 块，那么 A 块读完需要 10 ms，接着磁头在这 10 ms 内转到了 C 块，只能选择重新转到 B 块读取，所以先花费了 15 ms 移动到 B，然后花 10 ms 读取 B 块。同理，接下来的每次顺序读取都会花费 $5 * 3 + 10$ 的时间。所以最后的时间为 $10 + 25 * 3 = 85 m s$ .

要优化时间，就只能把 B 放到 C 的位置上去了，如下图所示：

A：10 ms
B：10 ms
C：5+10 ms
D：10 ms

总共 45 ms。

02

由于我直接用算法实现了，所以直接略过。

03

由于我直接用算法实现了，所以直接略过。