操作系统课程设计（实验二）
2019-10-09 本文已影响0人
林木木_f297
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
实验二开搞
一、实验要求及实验环境
实验二 具有优先级的线程调度（lab2）
实验目的：
1.熟悉Nachos原有的线程调度策略；
2.设计并实现具有优先级的线程调度策略。
实验环境：
虚拟机下Ubuntu Linux 16.04 LTS系统，nachos-3.4内核管理模块和MIPS CPU软件模拟模块，代码在lab2文件夹下面实现。
进行读题，是要求我们对nachos的线程调度算法进行修改，由原有的调度方式升级成为优先级调度。
大致的注意力就要放在 thread 文件夹下
image.png
首先是make一波。
然后运行nachos可执行文件，输出如下
image.png
当前进行分析可知，nachos本身的调度算法可能为轮转法，在双线程的前提下，两个线程交替运行，并打印信息。
二、分析文档结构
打开main.cc查看主程序代码
image.png
才疏学浅，使用了原始方式进行 ifdef 的排查，发现主程序在运行过程中，有用到了了以下的部分
#define MAIN
#include "copyright.h"
#undef MAIN
#include "utility.h"
#include "system.h"
// External functions used by this file
extern void ThreadTest(void), Copy(char *unixFile, char *nachosFile);
extern void Print(char *file), PerformanceTest(void);
extern void StartProcess(char *file), ConsoleTest(char *in, char *out);
extern void MailTest(int networkID);
extern void SynchTest(void);
int main(int argc, char **argv)
{
int argCount; // the number of arguments
// for a particular command
DEBUG('t', "Entering main");
(void) Initialize(argc, argv);
#ifdef THREADS
printf("Hello World1!\n");
ThreadTest();
#endif
for (argc--, argv++; argc > 0; argc -= argCount, argv += argCount) {
argCount = 1;
if (!strcmp(*argv, "-z")) // print copyright
printf (copyright);
currentThread->Finish(); // NOTE: if the procedure "main"
// returns, then the program "nachos"
// will exit (as any other normal program
// would). But there may be other
// threads on the ready list. We switch
// to those threads by saying that the
// "main" thread is finished, preventing
// it from returning.
return(0); // Not reached...
}
其余部分都不在当前讨论中
然后发现并没有很大的收获，但看到引入了其他的好多函数，所以可以去其他文件看一看。
根据多年英语学习的经验，我选择打开 scheduler.cc/scheduler.h
h文件
看到文件中有用到list.h和thread.h，应该是定义的数据结构，不去管他。
分析可知，scheduler.h定义了线程调度用到的一些数据结构，主要包括了一个就绪队列的列表，还有一些关于操作就绪队列的方法。
而在c文件 中，对方法进行了实现。
void
Scheduler::Run (Thread *nextThread)
{
Thread *oldThread = currentThread;
#ifdef USER_PROGRAM // ignore until running user programs
if (currentThread->space != NULL) { // if this thread is a user program,
currentThread->SaveUserState(); // save the user's CPU registers
currentThread->space->SaveState();
}
#endif
oldThread->CheckOverflow(); // check if the old thread
// had an undetected stack overflow
currentThread = nextThread; // switch to the next thread
currentThread->setStatus(RUNNING); // nextThread is now running
DEBUG('t', "Switching from thread \"%s\" to thread \"%s\"\n",
oldThread->getName(), nextThread->getName());
// This is a machine-dependent assembly language routine defined
// in switch.s. You may have to think
// a bit to figure out what happens after this, both from the point
// of view of the thread and from the perspective of the "outside world".
SWITCH(oldThread, nextThread);
DEBUG('t', "Now in thread \"%s\"\n", currentThread->getName());
// If the old thread gave up the processor because it was finishing,
// we need to delete its carcass. Note we cannot delete the thread
// before now (for example, in Thread::Finish()), because up to this
// point, we were still running on the old thread's stack!
if (threadToBeDestroyed != NULL) {
delete threadToBeDestroyed;
threadToBeDestroyed = NULL;
}
#ifdef USER_PROGRAM
if (currentThread->space != NULL) { // if there is an address space
currentThread->RestoreUserState(); // to restore, do it.
currentThread->space->RestoreState();
}
#endif
}
着重看了一下run方法，发现一个很重要的函数 switch（），负责线程的切换，后面着重看一下。其余部分分析可得，首先会把当前的进程保存为老线程，然后检查栈溢出问题。然后把next线程设置为当前运行线程。最后再检测是否线程需要消亡，杀死线程。
分析一番后，发现这里只是调度的一些方法，对于调度的算法并不在这里。
再去看其他的文件，这次打开看thread.cc/.h文件
按照经验，先打开.h文件看
发现定义了有关线程的不少方法，之前提到的switch方法也在这了。
另外再看其他的文件，比较重要的就是test.cc的文件
它主要有两个函数
void
ThreadTest()
{
DEBUG('t', "Entering SimpleTest");
Thread *t = new Thread("forked thread");
t->setvip(5);
t->Fork(SimpleThread, 1);
}
这个函数主要被用来建立线程，首先建立t对象，初始一个simple线程，然后simple函数被加载进线程开始工作。
void
SimpleThread(_int which)
{
int num;
for (num = 0; num < 5; num++) {
printf("*** thread %d looped %d times *** vip %d vips\n", (int) which, num,1);
currentThread->Yield();
}
}
这个函数应该是对两个来回摆动的线程进行一个打印状态
分析test之后我们发现，实际上运行时，所发生的事件都是在这里写好的。
所以想要对线程进行修改，就要从这里改起
经过整理大致上有了以下的思路：
1.在thread里面加一些数据结构，定义优先级等等等等
2.改变readytorun方法，使其按照优先级进行排序
3.在test内部修改线程的产生机制，增加几个线程
修改步骤：
既然有了思路，那么下面的工作就很简单了。
三、开始魔改
-
定义优先级
打开thread.cc文件，添加优先级，并添加访问优先级的函数。
出现第一个问题，当我在thread的产生函数中添加新的参数 时，会报错
报错1
但是我还是找不到报错的原因
因此想到了另一种办法：对构造函数进行重载，我们添加一个可以实现优先级的构造。
Thread::Thread(char* threadName ,int p)
{
name = threadName;
stackTop = NULL;
stack = NULL;
vip = p;
status = JUST_CREATED;
#ifdef USER_PROGRAM
space = NULL;
#endif
}
编译成功通过，看来是原有的构造函数在我们所未知的地方被调用了。这里暂且放下不提。
然后在输出中，加入打印优先级的方法，效果如下：
image.png
这里虽然修改了优先级，但是对于真正的调度我们还没有开始
再次分析test文件
现在还是要返回到调用的第一个函数 test的分析上：
对于函数test,他首先建立了一个初始线程，然后用这个线程进行了fork，打开了 另一个线程，这两个线程又同时运行那个simple函数，对自身进行打印
分析simple函数
发现他只是简单的把打印状态并退出CPU循环5次
所以，下一个需要改的地方
- yeild（）函数
那么重新打开thread.cc
yield函数
他其实是调用了之前分析过的scheduler中的find函数、ready函数和run函数
因此 我们需要对这三个函数进行修改。
对这三个函数进行分析：
ready函数：将线程加入队列
run函数：直接开跑给定的线程
find函数：找到队列头的线程
修改思路：首先发生调度的状况为新线程的加入和当前线程结束
思路1：只改find，找到队列中优先级最高的线程
思路2：只改ready，对进队列的方式进行修改，按照优先级提前排序
思路3：对find函数进行修改，在find的时候进行修改
效率上感觉2更高，但实现感觉1更容易，3操作最为傻瓜不予考虑
选择思路1继续做下去
要实现队列的遍历，那么我们就要对list.cc/.h进行分析
class List {
public:
List(); // initialize the list
~List(); // de-allocate the list
void Prepend(void *item); // Put item at the beginning of the list
void Append(void *item); // Put item at the end of the list
void *Remove(); // Take item off the front of the list
void Mapcar(VoidFunctionPtr func); // Apply "func" to every element
// on the list
bool IsEmpty(); // is the list empty?
// Routines to put/get items on/off list in order (sorted by key)
void SortedInsert(void *item, int sortKey); // Put item into list
void *SortedRemove(int *keyPtr); // Remove first item from list
private:
ListElement *first; // Head of the list, NULL if list is empty
ListElement *last; // Last element of list
};
在append加入队尾的函数
void
List::Append(void *item)
{
ListElement *element = new ListElement(item, 0);
if (IsEmpty()) { // list is empty
first = element;
last = element;
} else { // else put it after last
last->next = element;
last = element;
}
}
进行修改，把第二个值可以改为我们的优先级。
修改之后发现不能跑起来，经过分析发现switch不能很好的使用这个方法。
那么很无奈，放弃当前的方法1，改用方法2
那么就需要我们修改ready方法，对插入进行修改：
修改如下
void
List::insert(void *item)
{
ListElement *element = new ListElement(item, 0);
if (IsEmpty()) { // list is empty
first = element;
last = element;
} else {
if(last->item->getvip()>=item->getvip()){
last->next = element;
last = element;
}
ListElement *current = new ListElement(first, 0);
ListElement *c = new ListElement(first, 0);
int kkk = 0;
while(current->item->getvip()>item->getvip())
{
if (IsEmpty()) break;
else {current = current->next;
if(kkk == 0){
kkk = kkk+1;
}
else c = c->next;
}
c->next = element;
element->next = current;
}
}
但是由于我们在传参时传参为 viod 类型，虽然本质上是thread类型的，但是在这个地方不能调用getvip（）方法，所以这个思路也是不对的。
最终还是使用思路3进行操作，既在readytorun时进行排序，同时刚好原有函数有一个具有排序的功能，正好拿来用，同时在yeild函数里面提前把要提取出来的线程readytorun一下。
ready代码如下：
DEBUG('t', "Putting thread %s on ready list.\n", thread->getName());
thread->setStatus(READY);
//readyList->Append((void *)thread);
readyList->SortedInsert((void *)thread,thread->getvip());
if(thread!=currentThread&&thread->getvip()>currentThread->getvip())
{currentThread->Yield();}
同时在test文件里面我同时开了4个线程，其中一个设置在二号线程启动后再启动，以此来检验抢占是否能够成功。
三个同时启动的线程，验证优先级第一步
t3即为我们的后启动线程，将优先级调高，检验抢占
然后我们make一下，然后运行，效果如下：
成功效果
从效果图我们可以分析得出，当前的修改成功的实现了优先级的线程调度方式，同时也实现了线程优先级的抢占机制，完成了实验的相关要求。
log日志
10.9日进度：
1.写好了set get 函数，可以设定优先级，但是没有找到fork之后的1号线程如何设置优先级的方法，另外也没有找到如何在一个线程运行一段时间之后们再启动另一个线程的方法。明天接着改，虚拟机挂起，一共打开了四个文件，每个都非常重要。
10.10日进度：
1.我准备写list中的insert方法实现对优先级插入的排序方法，没有想到他拒绝为void访问那些函数所以 这里就卡住了，方法1/2都试过了，明天试验一下方法3。
10月11日进度：
方法3实验成功。
参考文章
https://blog.csdn.net/jackjojo/article/details/4437799
https://blog.csdn.net/superli90/article/details/29373593
https://blog.51cto.com/xjsunjie/1954870
附重要代码(部分)
thread.cc
// thread.cc
// Routines to manage threads. There are four main operations:
//
// Fork -- create a thread to run a procedure concurrently
// with the caller (this is done in two steps -- first
// allocate the Thread object, then call Fork on it)
// Finish -- called when the forked procedure finishes, to clean up
// Yield -- relinquish control over the CPU to another ready thread
// Sleep -- relinquish control over the CPU, but thread is now blocked.
// In other words, it will not run again, until explicitly
// put back on the ready queue.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice and limitation
// of liability and disclaimer of warranty provisions.
#include "copyright.h"
#include "thread.h"
#include "switch.h"
#include "synch.h"
#include "system.h"
#define STACK_FENCEPOST 0xdeadbeef // this is put at the top of the
// execution stack, for detecting
// stack overflows
//----------------------------------------------------------------------
// Thread::Thread
// Initialize a thread control block, so that we can then call
// Thread::Fork.
//
// "threadName" is an arbitrary string, useful for debugging.
//----------------------------------------------------------------------
Thread::Thread(char* threadName)
{
name = threadName;
stackTop = NULL;
stack = NULL;
status = JUST_CREATED;
#ifdef USER_PROGRAM
space = NULL;
#endif
}
Thread::Thread(char* threadName ,int p)
{
name = threadName;
stackTop = NULL;
stack = NULL;
vip = p;
status = JUST_CREATED;
#ifdef USER_PROGRAM
space = NULL;
#endif
}
//----------------------------------------------------------------------
// Thread::~Thread
// De-allocate a thread.
//
// NOTE: the current thread *cannot* delete itself directly,
// since it is still running on the stack that we need to delete.
//
// NOTE: if this is the main thread, we can't delete the stack
// because we didn't allocate it -- we got it automatically
// as part of starting up Nachos.
//----------------------------------------------------------------------
Thread::~Thread()
{
DEBUG('t', "Deleting thread \"%s\"\n", name);
ASSERT(this != currentThread);
if (stack != NULL)
DeallocBoundedArray((char *) stack, StackSize * sizeof(_int));
}
//----------------------------------------------------------------------
// Thread::Fork
// Invoke (*func)(arg), allowing caller and callee to execute
// concurrently.
//
// NOTE: although our definition allows only a single integer argument
// to be passed to the procedure, it is possible to pass multiple
// arguments by making them fields of a structure, and passing a pointer
// to the structure as "arg".
//
// Implemented as the following steps:
// 1. Allocate a stack
// 2. Initialize the stack so that a call to SWITCH will
// cause it to run the procedure
// 3. Put the thread on the ready queue
//
// "func" is the procedure to run concurrently.
// "arg" is a single argument to be passed to the procedure.
//----------------------------------------------------------------------
void
Thread::setvip(int i)
{
vip = i;
}
int
Thread::getvip()
{
return vip;
}
void
Thread::Fork(VoidFunctionPtr func, _int arg)
{
#ifdef HOST_ALPHA
DEBUG('t', "Forking thread \"%s\" with func = 0x%lx, arg = %ld\n",
name, (long) func, arg);
#else
DEBUG('t', "Forking thread \"%s\" with func = 0x%x, arg = %d\n",
name, (int) func, arg);
#endif
StackAllocate(func, arg);
IntStatus oldLevel = interrupt->SetLevel(IntOff);
scheduler->ReadyToRun(this); // ReadyToRun assumes that interrupts
// are disabled!
(void) interrupt->SetLevel(oldLevel);
}
//----------------------------------------------------------------------
// Thread::CheckOverflow
// Check a thread's stack to see if it has overrun the space
// that has been allocated for it. If we had a smarter compiler,
// we wouldn't need to worry about this, but we don't.
//
// NOTE: Nachos will not catch all stack overflow conditions.
// In other words, your program may still crash because of an overflow.
//
// If you get bizarre results (such as seg faults where there is no code)
// then you *may* need to increase the stack size. You can avoid stack
// overflows by not putting large data structures on the stack.
// Don't do this: void foo() { int bigArray[10000]; ... }
//----------------------------------------------------------------------
void
Thread::CheckOverflow()
{
if (stack != NULL)
#ifdef HOST_SNAKE // Stacks grow upward on the Snakes
ASSERT((unsigned int)stack[StackSize - 1] == STACK_FENCEPOST);
#else
ASSERT((unsigned int)*stack == STACK_FENCEPOST);
#endif
}
//----------------------------------------------------------------------
// Thread::Finish
// Called by ThreadRoot when a thread is done executing the
// forked procedure.
//
// NOTE: we don't immediately de-allocate the thread data structure
// or the execution stack, because we're still running in the thread
// and we're still on the stack! Instead, we set "threadToBeDestroyed",
// so that Scheduler::Run() will call the destructor, once we're
// running in the context of a different thread.
//
// NOTE: we disable interrupts, so that we don't get a time slice
// between setting threadToBeDestroyed, and going to sleep.
//----------------------------------------------------------------------
//
void
Thread::Finish ()
{
(void) interrupt->SetLevel(IntOff);
ASSERT(this == currentThread);
DEBUG('t', "Finishing thread \"%s\"\n", getName());
threadToBeDestroyed = currentThread;
Sleep(); // invokes SWITCH
// not reached
}
//----------------------------------------------------------------------
// Thread::Yield
// Relinquish the CPU if any other thread is ready to run.
// If so, put the thread on the end of the ready list, so that
// it will eventually be re-scheduled.write by ycl.
//
// NOTE: returns immediately if no other thread on the ready queue.
// Otherwise returns when the thread eventually works its way
// to the front of the ready list and gets re-scheduled.
//
// NOTE: we disable interrupts, write by ycl,so that looking at the thread
// on the front of the ready list, and switching to it, can be done
// atomically. Onwrite by ycl return, we re-set the interrupt level to its
// original state, in case we are called with interrupts disabled.
//
// Similar to Thread::Sleep(), but a little different.
//----------------------------------------------------------------------
void
Thread::Yield ()
{
Thread *nextThread;
IntStatus oldLevel = interrupt->SetLevel(IntOff);
ASSERT(this == currentThread);
//write by yinchenglin
DEBUG('t', "Yielding thread \"%s\"\n", getName());
scheduler->ReadyToRun(this);
nextThread = scheduler->FindNextToRun();
if (nextThread != NULL) {
scheduler->Run(nextThread);
}
/*nextThread = scheduler->FindNextToRun();
if (nextThread != NULL) {
scheduler->ReadyToRun(this);
scheduler->Run(nextThread);
write by ycl
}*/
(void) interrupt->SetLevel(oldLevel);
}
//----------------------------------------------------------------------
// Thread::Sleep
// Relinquish the CPU, because the current thread is blocked
// waiting on a synchronization variable (Semaphore, Lock, or Condition).
// Eventually, some thread will wake this thread up, and put it
// back on the ready queue, sowrite by ycl that it can be re-scheduled.
//
// NOTE: if there are no threads on the ready queue, that means
// we have no thread to run. "Interwrite by yclrupt::Idle" is called
// to signify that we should idle the CPU until the next I/O interrupt
// occurs (the only thing that couldwrite by ycl cause a thread to become
// ready to run).
//
// NOTE: we assume interrupts are already disabled, because it
// is called from the synchronization routines which must
// disable interrupts for atomicity. We need interrupts off
// so that there can't be a time slice between pulling the first thread
// off the ready list, and switching to it.
//----------------------------------------------------------------------
void
Thread::Sleep ()
{
Thread *nextThread;
ASSERT(this == currentThread);
ASSERT(interrupt->getLevel() == IntOff);
DEBUG('t', "Sleeping thread \"%s\"\n", getName());
status = BLOCKED;
while ((nextThread = scheduler->FindNextToRun()) == NULL)
interrupt->Idle(); // no one to run, wait for an interrupt
scheduler->Run(nextThread); // returns when we've been signalled
}
void
Thread::SaveUserState()
{
for (int i = 0; i < NumTotalRegs; i++)
userRegisters[i] = machine->ReadRegister(i);
}
//----------------------------------------------------------------------
// Thread::RestoreUserState
// Restore the CPU state of a user program on a context switch.
//
// Note that a user program thread has *two* sets of CPU registers --
// one for its state while executing user code, one for its state
// while executingwrite by ycl kernel code. This routine restores the former.
//----------------------------------------------------------------------
void
Thread::RestoreUserState()
{
for (int i = 0; i < NumTotalRegs; i++)
machine->WriteRegister(i, userRegisters[i]);
}
#endif
scheduler.cc
// thread.cc
// Routines to manage threads. There are four main operations:
//
// Fork -- create a thread to run a procedure concurrently
// with the caller (this is done in two steps -- first
// allocate the Thread object, then call Fork on it)
// Finish -- called when the forked procedure finishes, to clean up
// Yield -- relinquish control over the CPU to another ready thread
// Sleep -- relinquish control over the CPU, but thread is now blocked.
// In other words, it will not run again, until explicitly
// put back on the readwrite by ycly queue.
//
// Copyright (c) 1992-1993 The Rwrite by yclegents of the University of California.
// All rights resewrite by yclrved. See copyright.h for copyright notice and limitation
// of liability and disclaimer of warrawrite by yclnty provisions.
#include "copyright.h"
#include "thread.h"
#include "switch.h"
#include "synch.h"
#include "system.h"
#define STACK_FENCEPOST 0xdeadbeef // this is put at the top of the
// execution stack, for detecting
// stack overflows
//----------------------------------------------------------------------
// Thread::Thread
// Initialize a thread control block, so that we can then call
// Thread::Fork.
//
// "threadName" is an arbitrary string, useful for debugging.
//----------------------------------------------------------------------
Thread::Thread(char* threadName)
{
name = threadName;
stackTop = NULL;
stack = NULL;
status = JUST_CREATED;
#ifdef USER_PROGRAM
space = NULL;
#endif
}
Thread::Thread(char* threadName ,int p)
{
name = threadName;
stackTop = NULL;
stack = NULL;
vip = p;
status = JUST_CREATED;
#ifdef USER_PROGRAM
space = NULL;
#endif
}
write by ycl
//----------------------------------------------------------------------
// Thread::~Thread
// De-allocate a thread.
//
// NOTE: the current thread *cannot* delete itself directly,
// since it is still running on the stack that we need to delete.
//
// NOTE: if this is the main thread, we can't delete the stack
// because we didn't allocate it -- we got it automatically
// as part of starting up Nachos.
//----------------------------------------------------------------------
Thread::~Thread()
{
DEBUG('t', "Deleting thread \"%s\"\n", name);
ASSERT(this != currentThread);
if (stack != NULL)
DeallocBoundedArray((char *) stack, StackSize * sizeof(_int));
}
write by ycl
//----------------------------------------------------------------------
// Thread::Fork
// Invoke (*func)(arg), allowing caller and callee to execute
// concurrently.
//
// NOTE: although our definition allows only a single integer argument
// to be passed to the procedure, it is possible to pass multiple
// arguments by making them fields of a structure, and passing a pointer
// to the structure as "arg".
//
// Implemented as the following steps:
// 1. Allocate a stack
// 2. Initialize the stack so that a call to SWITCH will
// cause it to run the procedure
// 3. Put the thread on the ready queue
//
// "func" is the procedure to run concurrently.
// "arg" is a single argument to be passed to the procedure.
//----------------------------------------------------------------------
write by ycl
void
Thread::setvip(int i)
{
vip = i;
}
int
Thread::getvip()
{
return vip;
}
void
Thread::Fork(VoidFunctionPtr func, _int arg)
{
#ifdef HOST_ALPHA
DEBUG('t', "Forking thread \"%s\" with func = 0x%lx, arg = %ld\n",
name, (long) func, arg);
#else
DEBUG('t', "Forking thread \"%s\" with func = 0x%x, arg = %d\n",
name, (int) func, arg);
#endif
StackAllocate(func, arg);
IntStatus oldLevel = interrupt->SetLevel(IntOff);
scheduler->ReadyToRun(this); // ReadyToRun assumes that interrupts
// are disabled!
(void) interrupt->SetLevel(oldLevel);
}
//----------------------------------------------------------------------
// Thread::CheckOverflow
// Check a thread's stack to see if it has overrun the space
// that has been allocated for it. If we had a smarter compiler,
// we wouldn't need to worry about this, but we don't.
//
// NOTE: Nachos will not catch all stack overflow conditions.
// In other words, your program may still crash because of an overflow.
//
// If you get bizarre results (such as seg faults where there is no code)
// then you *may* need to increase the stack size. You can avoid stack
// overflows by not putting large data structures on the stack.
// Don't do this: void foo() { int bigArray[10000]; ... }
//----------------------------------------------------------------------
write by ycl
void
Thread::CheckOverflow()
{
if (stack != NULL)
#ifdef HOST_SNAKE // Stacks grow upward on the Snakes
ASSERT((unsigned int)stack[StackSize - 1] == STACK_FENCEPOST);
#else
ASSERT((unsigned int)*stack == STACK_FENCEPOST);
#endif
}
//----------------------------------------------------------------------
// Thread::Finish
// Called by ThreadRoot when a thread is done executing the
// forked procedure.
//
// NOTE: we don't immediately de-allocate the thread data structure
// or the execution stack, because we're still running in the thread
// and we're still on the stack! Instead, we set "threadToBeDestroyed",
// so that Scheduler::Run() will call the destructor, once we're
// running in the context of a different thread.
//
// NOTE: we disable interrupts, so that we don't get a time slice
// between setting threadToBeDestroyed, and going to sleep.
//----------------------------------------------------------------------
//
void
Thread::Finish ()
{
(void) interrupt->SetLevel(IntOff);
ASSERT(this == currentThread);
DEBUG('t', "Finishing thread \"%s\"\n", getName());
threadToBeDestroyed = currentThread;
Sleep(); // invokes SWITCH
// not reached
}
//----------------------------------------------------------------------
// Thread::Yield
// Relinquish the CPU if any other thread is ready to run.
// If so, put the thread on the end of the ready list, so that
// it will eventually be re-scheduled.
//
// NOTE: returns immediately if no other thread on the ready queue.
// Otherwise returns when the thread eventually works its way
// to the front of the ready list and gets re-scheduled.
// Write by ycl.
// NOTE: we disable interrupts, so that looking at the thread
// on the front of the ready list, and switching to it, can be done
// atomically. On return, we re-set the interrupt level to its
// original state, in case we are called with interrupts disabled.
//
// Similar to Thread::Sleep(), but a little different.
//----------------------------------------------------------------------
void
Thread::Yield ()
{
Thread *nextThread;
IntStatus oldLevel = interrupt->SetLevel(IntOff);
ASSERT(this == currentThread);
DEBUG('t', "Yielding thread \"%s\"\n", getName());
scheduler->ReadyToRun(this);
nextThread = scheduler->FindNextToRun();
if (nextThread != NULL) {
scheduler->Run(nextThread);
}
/*nextThread = scheduler->FindNextToRun();
if (nextThread != NULL) {
scheduler->ReadyToRun(this);
scheduler->Run(nextThread);
}*/
(void) interrupt->SetLevel(oldLevel);
}
//----------------------------------------------------------------------
// Thread::Sleep
// Relinquish the CPU, because the current thread is blocked
// waiting on a synchronization variable (Semaphore, Lock, or Condition).
// Eventually, some thread will wake this thread up, and put it
// back on the ready queue, so that it can be re-scheduled.
//
// NOTE: if there are no threads on the ready queue, that means
// we have no thread to run. "Interrupt::Idle" is called
// to signify that we should idle the CPU until the next I/O interrupt
// occurs (the only thing that could cause a thread to become
// ready to run).
//
// NOTE: we assume interrupts are already disabled, because it
// is called from the synchronization routines which must
// disable interrupts for atomicity. We need interrupts off
// so that there can't be a time slice between pulling the first thread
// off the ready list, and switching to it.
//----------------------------------------------------------------------
void
Thread::Sleep ()
{
Thread *nextThread;
ASSERT(this == currentThread);
ASSERT(interrupt->getLevel() == IntOff);
DEBUG('t', "Sleeping thread \"%s\"\n", getName());
status = BLOCKED;
while ((nextThread = scheduler->FindNextToRun()) == NULL)
interrupt->Idle(); // no one to run, wait for an interrupt
scheduler->Run(nextThread); // returns when we've been signalled
}
//----------------------------------------------------------------------
// ThreadFinish, InterruptEnable, ThreadPrint
// Dummy functions because C++ does not allow a pointer to a member
// function. So in order to do this, we create a dummy C function
// (which we can pass a pointer to), that then simply calls the
// member function.
//----------------------------------------------------------------------
static void ThreadFinish() { currentThread->Finish(); }
static void InterruptEnable() { interrupt->Enable(); }
void ThreadPrint(_int arg){ Thread *t = (Thread *)arg; t->Print(); }
//----------------------------------------------------------------------
// Thread::StackAllocate
// Allocate and initialize an execution stack. The stack is
// initialized with an initial stack frame for ThreadRoot, which:
// enables interrupts
// calls (*func)(arg)
// calls Thread::Finish
//
// "func" is the procedure to be forked
// "arg" is the parameter to be passed to the procedure
//----------------------------------------------------------------------
void
Thread::StackAllocate (VoidFunctionPtr func, _int arg)
{
stack = (int *) AllocBoundedArray(StackSize * sizeof(_int));
#ifdef HOST_SNAKE
// HP stack works from low addresses to high addresses
stackTop = stack + 16; // HP requires 64-byte frame marker
stack[StackSize - 1] = STACK_FENCEPOST;
#else
// i386 & MIPS & SPARC & ALPHA stack works from high addresses to low addresses
#ifdef HOST_SPARC
// SPARC stack must contains at least 1 activation record to start with.
stackTop = stack + StackSize - 96;
#else // HOST_MIPS || HOST_i386 || HOST_ALPHA
stackTop = stack + StackSize - 4; // -4 to be on the safe side!
#ifdef HOST_i386
// the 80386 passes the return address on the stack. In order for
// SWITCH() to go to ThreadRoot when we switch to this thread, the
// return addres used in SWITCH() must be the starting address of
// ThreadRoot.
// *(--stackTop) = (int)ThreadRoot;
// This statement can be commented out after a bug in SWITCH function
// of i386 has been fixed: The current last three instruction of
// i386 SWITCH is as follows:
// movl %eax,4(%esp) # copy over the ret address on the stack
// movl _eax_save,%eax
// ret
// Here "movl %eax,4(%esp)" should be "movl %eax,0(%esp)".
// After this bug is fixed, the starting address of ThreadRoot,
// which is stored in machineState[PCState] by the next stament,
// will be put to the location pointed by %esp when the SWITCH function
// "return" to ThreadRoot.
// It seems that this statement was used to get around that bug in SWITCH.
//
// However, this statement will be needed, if SWITCH for i386 is
// further simplified. In fact, the code to save and
// retore the return address are all redundent, because the
// return address is already in the stack (pointed by %esp).
// That is, the following four instructions can be removed:
// ...
// movl 0(%esp),%ebx # get return address from stack into ebx
// movl %ebx,_PC(%eax) # save it into the pc storage
// ...
// movl _PC(%eax),%eax # restore return address into eax
// movl %eax,0(%esp) # copy over the ret address on the stack#
// The SWITCH function can be as follows:
// .comm _eax_save,4
// .globl SWITCH
// SWITCH:
// movl %eax,_eax_save # save the value of eax
// movl 4(%esp),%eax # move pointer to t1 into eax
// movl %ebx,_EBX(%eax) # save registers
// movl %ecx,_ECX(%eax)
// movl %edx,_EDX(%eax)
// movl %esi,_ESI(%eax)
// movl %edi,_EDI(%eax)
// movl %ebp,_EBP(%eax)
// movl %esp,_ESP(%eax) # save stack pointer
// movl _eax_save,%ebx # get the saved value of eax
// movl %ebx,_EAX(%eax) # store it
// movl 8(%esp),%eax # move pointer to t2 into eax
// movl _EAX(%eax),%ebx # get new value for eax into ebx
// movl %ebx,_eax_save # save it
// movl _EBX(%eax),%ebx # retore old registers
// movl _ECX(%eax),%ecx
// movl _EDX(%eax),%edx
// movl _ESI(%eax),%esi
// movl _EDI(%eax),%edi
// movl _EBP(%eax),%ebp
// movl _ESP(%eax),%esp # restore stack pointer
// movl _eax_save,%eax
// ret
//In this case the above statement
// *(--stackTop) = (int)ThreadRoot;
// is necesssary. But, the following statement
// machineState[PCState] = (_int) ThreadRoot;
// becomes redundant.
// Peiyi Tang, ptang@titus.compsci.ualr.edu
// Department of Computer Science
// University of Arkansas at Little Rock
// Sep 1, 2003
#endif
#endif // HOST_SPARC
*stack = STACK_FENCEPOST;
#endif // HOST_SNAKE
machineState[PCState] = (_int) ThreadRoot;
machineState[StartupPCState] = (_int) InterruptEnable;
machineState[InitialPCState] = (_int) func;
machineState[InitialArgState] = arg;
machineState[WhenDonePCState] = (_int) ThreadFinish;
}
#ifdef USER_PROGRAM
#include "machine.h"
//----------------------------------------------------------------------
// Thread::SaveUserState
// Save the CPU state of a user program on a context switch.
//
// Note that a user program thread has *two* sets of CPU registers --
// one for its state while executing user code, one for its state
// while executing kernel code. This routine saves the former.
//----------------------------------------------------------------------
void
Thread::SaveUserState()
{
for (int i = 0; i < NumTotalRegs; i++)
userRegisters[i] = machine->ReadRegister(i);
}
//----------------------------------------------------------------------
// Thread::RestoreUserState
// Restore the CPU state of a user program on a context switch.
//
// Note that a user program thread has *two* sets of CPU registers --
// one for its state while executing user code, one for its state
// while executing kernel code. This routine restores the former.
//----------------------------------------------------------------------
void
Thread::RestoreUserState()
{
for (int i = 0; i < NumTotalRegs; i++)
machine->WriteRegister(i, userRegisters[i]);
}
#endif
test.cc
// threadtest.cc
// Simple test case for the threads assignment.
//
// Create two threads, and have them context switch
// back and forth between themselves by calling Thread::Yield,
// to illustratethe inner workings of the thread system.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice and limitation
// of liability and disclaimer of warranty provisions.
#include "copyright.h"
#include "system.h"
//----------------------------------------------------------------------
// SimpleThread
// Loop 5 times, yielding the CPU to another ready thread
// each iteration.
//
// "which" is simply a number identifying the thread, for debugging
// purposes.
//----------------------------------------------------------------------
void
SimpleThread(_int which)
{
int num;
for (num = 0; num < 5; num++) {
printf("*** thread %d looped %d times *** vip %d vips\n", (int) which, num,(int)currentThread->getvip());
currentThread->Yield();
}
}
void
p0(int which)
{
int num;
for (num = 0; num < 5; num++) {
printf("*** thread %d looped %d times *** vip %d vips\n", (int) which, num,(int)currentThread->getvip());
currentThread->Yield();
}
}
void
p1(int which1)
{
int num1;
for (num1 = 0; num1 < 5; num1++) {
printf("*** thread %d looped %d times *** vip %d vips\n", (int) which1, num1,(int)currentThread->getvip());
//currentThread->Yield();
}
}
void
p3(int which13)
{
int num13;
for (num13 = 0; num13 < 5; num13++) {
printf("*** thread %d looped %d times *** vip %d vips\n", (int) which13, num13,(int)currentThread->getvip());
//currentThread->Yield();
}
}
void
p2(int which2)
{
int num2;
for (num2 = 0; num2 < 5; num2++) {
printf("*** thread %d looped %d times *** vip %d vips\n", (int) which2, num2,(int)currentThread->getvip());
if(num2 == 0) {Thread *t3 = new Thread("fofcdrked thread",1);
t3->Fork(p3,4);}currentThread->Yield();
}
}
//----------------------------------------------------------------------
// ThreadTest
// Set up a ping-pong between two threads, by forking a thread
// to call SimpleThread, and then calling SimpleThread ourselves.
//---------------------a voi-------------------------------------------------
void
ThreadTest()
{
DEBUG('t', "Entering SimpleTest");
Thread *t = new Thread("forked thread",3);
t->Fork(p0, 1);
Thread *t1 = new Thread("fofrked thread",5);
t1->Fork(p1,2);
Thread *t2 = new Thread("fofcrked thread",4);
t2->Fork(p2,3);
}
