nachos实验1-3

发表于 | 更新于 | 分类于

ProJ1: Build athread system for kernel processes

实验要求

In this project，

The only packageyou will submit is nachos.threads, so don’t add any source files to any otherpackage.

The autograderwill not call ThreadedKernel.selfTest() or ThreadedKernel.run(). If there isany kernel initialization you need to do, you should finish it beforeThreadedKernel.initialize() returns.

There are somemandatory autograder calls in the KThread code. Leave them as they are.

实验分析

Phase1分析：在这一阶段，我们主要实现nachos的代码部分。

1)阅读并理解nachos系统的线程部分。nachos系统实现了线程fork，为同步实现了信号量。同时提供了锁和利用信号量实现的条件变量。

2)可添加适当的类或代码，补充并完善Thread，实现合理正确的同步代码。

Task1.1 KThread.join()

实验要求：

实现KThread的join方法，注意其它的线程不必调用join()，但是如果 join()被调用的话，也只能被调用一次。对 join()第二次调用的执行结果是没有定义的，即使第二次调用者和第一个不同。无论有没有被 join，一个进程都必须正常结束。

实验分析：

线程调用了join，即把时间片从当前线程手中抢了过来。主要作用是使当前线程阻塞。因此join方法需要一个等待队列，存放因其调用而存放的前当前线程。同时，在调用者结束时，要释放（唤醒）自己等待队列中的线程。

例如，在a线程中调用b.join不过是让a排在了b的后面。

在实现过程中需要关中断，避免因时钟中断引起的调度的发生。

实验实现：

数据结构：

一个Threadqueue，用作等待队列。

1
public ThreadQueue JoinQueue=null;

关键代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void join() {
    Lib.debug(dbgThread, "Joining to thread: " + toString());
	Lib.assertTrue(JoinCount==0);//join只可调用一次
	Lib.assertTrue(this != currentThread);
	JoinCount++;
	 boolean intState = Machine.interrupt().disable();//关中断，notice时钟中断
	 if(this.JoinQueue==null){
		 JoinQueue = ThreadedKernel.scheduler.newThreadQueue(true);//若没有新建，则进行新建。
	 }
    if (status != statusFinished&status != statusBlocked){
    	JoinQueue.acquire(this);
    	JoinQueue.waitForAccess(currentThread);//将当前线程加入到等待队列里
    	KThread.sleep();//当前线程睡眠
    }
    Machine.interrupt().restore(intState);//恢复中断
    }

finish方法（把等待队列中的线程唤醒）

在finish中添加以下代码

1
2
3
4
5
6
7
8
9
if(currentThread.JoinQueue!=null){
	
	KThread x =currentThread.JoinQueue.nextThread();//唤醒等待队列中的所有线程
	while(x!=null) 
	{ 
		x.ready();
            x=currentThread.JoinQueue.nextThread();
	}
}
测试代码:
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
public class join1_1 {
	
	public static void JoinTest(){
		KThread a=new KThread(new Runnable(){//新建线程a
			@Override
			public void run() {
				// TODO 自动生成的方法存根
				for (int i = 0; i < 3; i++) {
					System.out.println("a线程执行第"+i+"次");
					
				}
				
			}
			
		});
		
		KThread b=new KThread(new Runnable(){//新建线程b

			@Override
			public void run() {
				// TODO 自动生成的方法存根
				System.out.println("b0在运行");
				System.out.println("b1在运行");
				System.out.println("a插队b");
				a.join();//a调用join
				for (int i = 2; i < 5; i++) {
					
					System.out.println("b"+i+"在运行");

					
				}
				
			}
			
		});
		
		b.fork();
		a.fork();
		

	}
}
测试结果:

test1

Task1.2 Condition

实验要求：

直接实现条件变量，通过中断的开启与关闭提供原子性。我们提供一个用信号量的示例实现。
你的工作是提供一个对等的实现，而不直接使用信号量（你也可以使用锁，即使他们间接使用信号量）。 一旦完成，您将有两选择实现相同的功能。 您的第二个条件变量的实现必须在类nachos.threads.Condition2中。

实验分析：

由于对条件变量和信号量有些遗忘，在做这个实验时，又读了《操作系统的设计与实现》，以期对这些有更深的理解。

这本书在实现管程的过程中提到了条件变量：

管程提供了一种实现互斥的简便途径，但这还不够。我们还需要一种办法以使得进程在无法继续运行时被阻塞。在生产者－消费者问题中，很容易将针对缓冲区满和缓冲区空的测试放到管程的过程中，但是生产者在发现缓冲区满的时候如何阻塞？

解决方法在于引入条件变量(condition variables)，及相关的两个操作：WAIT和SIGNAL。当一个管程过程发现它无法继续时（例如，生产者发现缓冲区满），它在某些条件变量上执行WAIT，如full。这个动作引起调用进程阻塞。它也允许另一个先前被挡在管程之外的进程现在进入管程。另一个进程，如消费者，可以通过对其伙伴正在其上等待的一个条件变量执行SIGNAL来唤醒正在睡眠的伙伴进程。为避免管程中同时有两个活跃进程，我们需要一条规则来通知在SIGNAL之后该怎么办。

由此我们知道，条件变量是与对共享资源的原子操作有关。在没有资源时（条件不满足），条件变量使进程沉睡，在有资源时（条件满足），条件变量再唤醒进程。

在我看来，条件变量代表资源有没有，进而使进程沉睡苏醒，而信号量可以表示资源有多少，当信号量值最大为1，信号量只有两个状态，也可以表示资源有没有，这时它和条件变量作用相同。（Condition1即为这般实现）。

实验实现：

因为条件变量帮助线程实现沉睡苏醒，因此需要有一个队列，来存储线程。同样需要一个锁，实现原子操作。

主要数据结构：

1
2
private Lock conditionLock;
private Queue<KThread> waitQueue;

Sleep（）方法，在条件不满足（没有资源）时，帮助线程沉睡。

1
2
3
4
5
6
7
8
9
10
   public void sleep() {//资源没有，沉睡
Lib.assertTrue(conditionLock.isHeldByCurrentThread());

boolean preState = Machine.interrupt().disable();//关中断,信号量不需要是因为信号量内有
 waitQueue.offer(KThread.currentThread());//将当前线程加入到waitQueue中
conditionLock.release();//释放锁，表示不占用资源了,
   KThread.sleep();//当前进程进入睡眠
   conditionLock.acquire();//线程苏醒时再次拿到锁
Machine.interrupt().restore(preState);//恢复中断
   }

Wake（）方法，唤醒wait队列中的一个线程

1
2
3
4
5
6
7
8
9
10
11
public void wake() {//资源拥有时，统一的唤醒操作
Lib.assertTrue(conditionLock.isHeldByCurrentThread());
boolean status=Machine.interrupt().disable();//关中断
KThread thread = waitQueue.poll();
if (thread != null) {
    thread.ready();
    
}

Machine.interrupt().restore(status);
   }

Wakeall（）方法，利用wake方法，唤醒wait队列中所有线程

1
2
3
4
5
6
7
8
9
10
   public void wakeAll() {
Lib.assertTrue(conditionLock.isHeldByCurrentThread());
boolean status=Machine.interrupt().disable();//关中断
while(waitQueue.peek()!=null){
	wake();
	//将waitQueue中的所有线程均唤醒
}
       
Machine.interrupt().restore(status);
   }
测试代码：

测试代码采用了类似生产者和消费者模型的形式。

主要逻辑：

a[资源有无，资源内容]。

线程a1——》有无资源？若无-》沉睡-》若有-》修改资源。

线程a2——》有无资源？若无-》沉睡-》若有-》修改资源。

线程a3——》有无资源？若无-》产生资源-》唤醒a1/a2。

代码实现：

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
public class Condition21_2 {
	Lock  lock = new Lock();
	Condition2 con = new Condition2(lock);
	int array[]={0,0};//数组，第一个数表示资源有无，第二个数表示资源内容
	public Condition21_2(){
		
	}
	public  void condition2test(){
		KThread a1=new KThread(new Runnable(){

			@Override
			public void run() {
				// TODO 自动生成的方法存根
				lock.acquire();
				if(array[0]==0){
					System.out.println("线程a1进入睡眠");
					con.sleep();
				}
				if(array[0]>0){//有资源
					array[1]-=500;//消费行为
					System.out.println("线程a1苏醒");
					System.out.println("线程a1修改变量值为" +array[1]);
					
				}
				
				lock.release();
			}
			
		}) ;
		KThread a2=new KThread(new Runnable(){

			@Override
			public void run() {
				// TODO 自动生成的方法存根
				lock.acquire();
				if(array[0]==0){
					System.out.println("线程a2进入睡眠");
					
					con.sleep();
				}
				if(array[0]>0){//有资源
					array[1]-=500;//消费行为
					System.out.println("线程a2苏醒");
					System.out.println("线程a2修改变量值为" +array[1]);
					
				}
				
				lock.release();
			}
			
		}) ;
		KThread a3=new KThread(new Runnable(){

			@Override
			public void run() {
				// TODO 自动生成的方法存根
				lock.acquire();//共享变量，应当加上互斥锁
				if(array[0]==0){
					array[1]=1000;//消费行为
					System.out.println("线程a3修改变量值为" +array[1]);
					array[0]++;
					System.out.println("唤醒所有线程");
					con.wakeAll();
				}
				lock.release();
			}
			
		});
		a1.fork();
		a2.fork();
		a3.fork();
		
	}
}
运行结果:

test2

Task1.3 Alarm

实验要求：

完成Alarm类，通过实现waitUntil方法。一个线程调用waitUntil来挂起直到时间到达now+x,在实际中可用于光标闪烁等。这里并不需要到时间后线程被立刻唤醒，只需它们等待过最少的那个时间即可。不需要新建额外的线程，只需要修改waitUntil方法和计时器的中断处理器。WaitUntil方法不局限于一个线程，任意数量的线程可调用并被挂起。

实验分析：

这里让我们实现一个让线程睡眠一段时间后再苏醒的机制。因此会需要一个等待队列，存放睡眠的线程，同时也需要存放它们对应的苏醒时间，以在必要时进行唤醒。

与 Alarm 类有关的是 machine.Timer 类，它在大约每 500 个时钟，滴答使调用回调函数(由 Timer.setInterruptHandler 函数设置)。因此, Alarm类的构造函数中首先要设置该回调函数 Alarm.timerInterrupt()。方法在每一次 timer 产生时间中断时遍历队列，检查队列中的时间状态，当线程到了等待的时间就把线程从队列中取出放入就绪队列。

waitUntil（）方法主要让线程睡眠并存储线程和其睡眠时间。它使用了一个队列可以存放线程以及唤醒时间。每次调用时，把当前线程和唤醒时间加入队列，等待唤醒。这里使用LinkedList，方便遍历，移出。

系统响应中断的时机：

(1) 中断由中断关闭到中断开启时（即原来是disabled，当执行Interrupt.enable()时，或Interrupt. setStatus(true)时。

(2) Nachos的CPU执行完一条Nachos应用程序指令

上述两种情况下，触发Interrupt.tick()方法对Nachos的时钟进行增量（第一种情况增10，第二种情况增1）。tick()触发checkIfDue()，检查目前有无到期的中断，有则响应所有到期的中断

实验实现:

数据结构：一个列表，用于存放线程及其沉睡时间。

1
LinkedList<Waiter> Wa;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Waiter {
	KThread kt=null;
	long time=0;
	public Waiter(KThread kt,long time){
		this.kt=kt;
		this.time=time;
	}
	public KThread getKt() {
		return kt;
	}
	public void setKt(KThread kt) {
		this.kt = kt;
	}
	public long getTime() {
		return time;
	}
	public void setTime(long time) {
		this.time = time;
	}
}

WaitUntil方法，让线程沉睡一定时间。

1
2
3
4
5
6
7
8
9
   public void waitUntil(long x) {
   	boolean preStatus = Machine.interrupt().disable(); //系统关中断
   	long wakeTime = Machine.timer().getTime() + x; //确定唤醒的时间
   	Waiter x2 = new Waiter(KThread.currentThread(),wakeTime);
   	KThread.currentThread().waketime=wakeTime;
   	Wa.offerLast(x2); //将线程加入到等待队列上
	KThread.sleep();//当前线程进入睡眠
	Machine.interrupt().restore(preStatus);
}

TimerInterrupt（）方法，在固定时间将线程唤醒。

在这里，我犯过一个错误，开始的时候，我并不是用linkedlist存，而是用队列queue存，由于放入的顺序并没有按苏醒时间排列，因此不能很好的提出所需线程。后来便换了灵活的linkedlist。这里应该算犯了逻辑错误。

1
2
3
4
5
6
7
8
9
10
11
public void timerInterrupt() {
	boolean preState = Machine.interrupt().disable();//关中断
    for(int i=0;i<Wa.size();i++ ){//这里很不合适用while的话，因为不是每一次都需要把线程拿出来的！！！
	   if(Wa.get(i).getTime()<= Machine.timer().getTime())//当苏醒时间<当前时间
    	{
    	Wa.get(i).getKt().ready();//线程进入就绪状态
    	Wa.remove(i);
    	}
    }
    Machine.interrupt().restore(preState);//恢复中断
}
测试代码:
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
public class Alarm1_3 {

	public  static void alarmTest(){
		Alarm x=new Alarm();
		
		
		KThread a1=new KThread(new Runnable(){

			@Override
			public void run() {
				// TODO 自动生成的方法存根
				System.out.println("a1线程开始运行……");
				System.out.println("a1线程运行第1次");
				System.out.println("a1线程进入休眠||时间为："+Machine.timer().getTime()+"||应在"+(Machine.timer().getTime() + 800)+"醒来.");
				x.waitUntil(800); //让a1睡眠；
				System.out.println("唤醒线程：a1"+"||时间为："+Machine.timer().getTime());
				for(int i=2;i<=4;i++){
					System.out.println("a1线程运行第"+i+"次");
				}
			}
			
		});
		a1.setName("a1");
		KThread b1=new KThread(new Runnable(){

			@Override
			public void run() {
				// TODO 自动生成的方法存根
				System.out.println("b1线程开始运行……");
				System.out.println("b1线程运行第1次");
				System.out.println("b1线程运行第2次");
				System.out.println("b1线程休眠||时间为："+Machine.timer().getTime()+"||应在"+(Machine.timer().getTime() + 340)+"醒来.");
				x.waitUntil(340); //让b1睡眠；
				System.out.println("唤醒线程：b1"+"||时间为："+Machine.timer().getTime());
				for(int i=3;i<=4;i++){
					System.out.println("线程b1正在运行第"+i+"次循环");
				}
			}
			
		});
		a1.setName("a1");
		b1.setName("b1");
		a1.fork();
		b1.fork();
		
		
		
	}
}
实验结果:

test3