操作系统课程设计实验报告proj1

}

listener.sleep(); listenercount++; listener.sleep(); listenercount--;

} else {

System.out.println(Kthread.currentThread().getName() + “ 收到信

+ Wordqueue.getFirst());

息 “

}

System.out.println(); lock.release();

Machine.interrupt().restore(intStatus); return Wordqueue.poll();

2.5 Task 1.5实现优先级调度 2.5.1题目要求

通过完成实现PriorityScheduler优先级调度策略。所有的调度程序都是继承自Scheduler类，所以必须实现getPriority(), getEffectivePriority()和setPriority()方法。

2.5.2题目分析与实现方案

分析：Nachos系统已经提供了一个简单的轮转调度器，采用简单的FIFO队列进行调度。优先级调度的传统算法如下: 每个线程拥有一个优先级(在Nachos中, 优先级是一个0到7之间的整数, 默认为1)。在线程调度时, 调度程序选择一个拥有最高优先级的处于就绪状态的线程运行。这种算法的问题是可能出现“饥饿” 现象。为解决上述优先级反转问题, 需要实现一种“让出”优先级的机制(Priority Donation) 。getEffectivePriority()就是为了解决优先级翻转而设的，也就是说当出现一个优先级高的线程等待低优先级线程时，若存在另外的高优先级线程而导致低优先级线程永远不能执行的情况，该低优先

13

级线程调用该函数返回它持有的锁上等待的所有线程中优先级中最高的一个给该优先级线程，以确保它执行。

方案： 在引入优先级的同时就需要引入一个ThreadState对象，它用来把线程和优先级绑定在一起。而且内部还有一个队列用来记录等待它的线程。在 ThreadState类中增加两个LinkedList<>类表，存放PriorityQueue。一个表用来记录该线程所占用资源的优先队列，另一个表用来记录该线程所想占有的资源的优先队列。占用资源的队列作为发生优先级反转时，捐献优先级计算有效优先级的来源依据，想占有的资源的队列用来为线程声明得到资源做准备。 getEffectivePriority():计算有效优先级时，遍历等待队列中所用线程的有效优先级，找出最大的优先级。首先要在PriorityQueue类下创建个装有Kthread的LinkedList,即等待队列waitQueue,声明一个effectivePriority,遍历waitQueue,找出priority最大的那个Kthread,将它的priority赋给effectivePriority,然后返回即可。

而在队列类中最重要的就是nextThread（）方法，它返回下一个要执行的线程。这个方法通过遍历队列，计算出所有线程的有效优先级，取出有效优先级最大的线程执行。

waitForAccess()将需要等待获得资源的线程加入一个等待队列等待调度。

2.5.3关键点与难点

解决这个问题的关键是计算有效优先级，在改变优先级的时候计算。优先级在捐献之后不会丢失并可以不断传递下去。在

14

PriorityScheduler类的内部类。ThreadState类里有priority这属性，所以实现getPriority(), setPriority(), increasePriority(), decreasePriority()时直接对priority进行返回，重新赋值，修改priority的值。（注意：getPriority(), setPriority()函数内部是先调用内部类ThreadState类的同名函数，然后在这些同名函数里对priority修改）。

2.5.4实现代码

protected class ThreadState { public ThreadState(Kthread thread) { this.thread = thread;

setPriority(priorityDefault);

} public int getPriority() {

return priority; }

public int getEffectivePriority() {

return priority; }

public void setPriority(int priority) { if (this.priority == priority)

return; this.priority = priority;

}

public void waitForAccess(PriorityQueue waitQueue) {

if (waitQueue.holder != null)

if (this.priority > waitQueue.holder.priority) { waitQueue.holder.priority = this.priority;

}

waitQueue.waitQueue.add(this);

}

public void acquire(PriorityQueue waitQueue) { // implement me

Lib.assertTrue(Machine.interrupt().disabled());

15

}

}

Lib.assertTrue(waitQueue.waitQueue.isEmpty()); waitQueue.holder = this;

protected Kthread thread;

protected int priority;

public Kthread nextThread() {

}

Lib.assertTrue(Machine.interrupt().disabled()); // implement me

if (waitQueue.isEmpty())

return null; int max_priority = 0; int index = 0; int m = 0;

for (Iterator I = waitQueue.iterator(); i.hasNext();) { }

ThreadState nextState = waitQueue.remove(index); if (holder != null) { }

holder = nextState;

ThreadState o = (ThreadState) i.next(); if (o.priority > max_priority) { } m++;

index = m;

max_priority = o.priority;

return nextState.thread;

2.6 Task 1.6 条件变量解决过河问题 2.6.1题目要求

利用前面所学同步方法，以及条件变量解决过河问题。一群夏威夷人想要从瓦胡岛（Oahu）到摩洛凯岛（Molokai），只有一艘船，该船可载最多2个小孩或一个成人，且必须有一个开船的人（默认每个人都会开船）。设计一个解决方案，使得每个人都能从Oahu到Molokai。假设至少有两个小孩，每一个人都会划船。要为每个大人

16