Nachos實驗1實作執行緒id、限制執行緒數和更改調度演算法（按優先級調度）
一、理解Nachos執行緒的運行及調度原理
Nachos實驗主要是為了使我們深入的理解作業系統結構，Nachos也是一個作業系統，但是它很簡便，我們可以很容易的對它進行改動；通過對Nachos的實驗來增加我們對作業系統的理解，當前這個實驗主要是通過我們實作Nachos執行緒id和優先級調度來對作業系統行程和執行緒的理解，Nachos里面主要分為內核執行緒（例如main執行緒）和用戶執行緒，主要通過主執行緒來操作，例如新建和調度執行緒，其實對于增加執行緒id和限制最大執行緒數，只要了解行程的實作原理，看代碼也會非常的容易理解，這樣就會非常簡單了，
對于理解這次實驗代碼，我認為，需要看thread.h、thread.cc、scheduler.h、scheduler.cc、List.h、List.cc、main.h、main.cc，對于main.h和main.cc，只需要知道在運行Nachos的時候加-K命令（“./nachos -K”）就會進入執行緒測驗就行了，
二、增加執行緒ID和最大執行緒數
在增加實作執行緒id和最大執行緒數時，thread類的建構式盡量不要改動，只需再重構一個構造方法，因為之前的建構式可能在Nachos的其他類里會呼叫它，所以我們不能再之前的建構式里構造，這樣才不會打亂原系統的正確性，所以需要增加一個建構式Thread(char* debugName,int priority);至于int priority先不用管，這是之后優先級調度需要用到的引數，不影響我們使用這個建構式
1.增改class thread，增加執行緒id成員和一些需要用到的成員方法
#define MAX_SIZE 128//最大執行緒數
//pk陣列主要記錄執行緒號被使用的狀態
//下標位執行緒號，陣列對應值位執行緒號狀態
//對應值為0時，表示該執行緒號沒有執行緒占用
//對應值為1時，表示該執行緒號被占用
static int pk[MAX_SIZE]={0};
static int threadMAX = 0;//記錄執行緒數
class Thread {
private:
// NOTE: DO NOT CHANGE the order of these first two members.
// THEY MUST be in this position for SWITCH to work.
int *stackTop; // the current stack pointer
void *machineState[MachineStateSize]; // all registers except for stackTop
int tid;
public:
Thread(char* debugName);//原建構式 // initialize a Thread
~Thread(); //解構式 // deallocate a Thread
// NOTE -- thread being deleted
// must not be running when delete
// is called
// basic thread operations
Thread(char* debugName,int priority);//新建構式
int getTid(){return this->tid;};//獲得執行緒id
void Fork(VoidFunctionPtr func, void *arg); //將執行緒加入就緒佇列
// Make thread run (*func)(arg)
void Yield(); //打斷當前執行緒，運行就緒佇列里的執行緒
// Relinquish the CPU if any
// other thread is runnable
void Sleep(bool finishing);//將當前執行緒阻塞
// Put the thread to sleep and
// relinquish the processor
void Begin(); // Startup code for the thread
void Finish(); //執行緒運行結束
// The thread is done executing
void CheckOverflow(); // Check if thread stack has overflowed
void setStatus(ThreadStatus st) { status = st; }//設定執行緒狀態
char* getName() { return (name); }//獲取執行緒名字
void Print() { cout << name; }//列印執行緒名字
void SelfTest(); //測驗方法 // test whether thread impl is working
private:
// some of the private data for this class is listed above
int *stack; // Bottom of the stack
// NULL if this is the main thread
// (If NULL, don't deallocate stack)
ThreadStatus status; // ready, running or blocked
char* name;
void StackAllocate(VoidFunctionPtr func, void *arg);
// Allocate a stack for thread.
// Used internally by Fork()
// A thread running a user program actually has *two* sets of CPU registers --
// one for its state while executing user code, one for its state
// while executing kernel code.
int userRegisters[NumTotalRegs]; // user-level CPU register state
public:
void SaveUserState(); // save user-level register state
void RestoreUserState(); // restore user-level register state
AddrSpace *space; // User code this thread is running.
};
2.在thread.cc里面增加我們需要的功能，切記，我們是新增建構式，不是在原建構式更改！！
Thread::Thread(char* threadName)//原建構式，不要更改它
{
name = threadName;
stackTop = NULL;
stack = NULL;
status = JUST_CREATED;
for (int i = 0; i < MachineStateSize; i++) {
machineState[i] = NULL; // not strictly necessary, since
// new thread ignores contents
// of machine registers
}
space = NULL;
}
Thread::Thread(char* threadName,int priority)//新建構式
{
if(++threadMAX > MAX_SIZE){//限制執行緒數
cout<<"最大執行緒數:"<<MAX_SIZE<<"!!!"<<endl;
ASSERT(threadMAX<=MAX_SIZE);
}
int j;
for(j=0;j<MAX_SIZE;j++){//設定id
if(pk[j]==0){
this->tid = j+1;
pk[j] = 1;
break;
}
}
name = threadName;
stackTop = NULL;
stack = NULL;
status = JUST_CREATED;
for (int i = 0; i < MachineStateSize; i++) {
machineState[i] = NULL; // not strictly necessary, since
// new thread ignores contents
// of machine registers
}
space = NULL;
}
3.增改解構式
Thread::~Thread()
{
DEBUG(dbgThread, "Deleting thread: " << name);
pk[tid -1] = 0;//執行緒id撤銷
threadMAX--;//執行緒數減一
ASSERT(this != kernel->currentThread);
if (stack != NULL)
DeallocBoundedArray((char *) stack, StackSize * sizeof(int));
}
4.在測驗函式增改測驗代碼
void Thread::SelfTest()
{
DEBUG(dbgThread, "Entering Thread::SelfTest");
/*Thread *t = new Thread("forked thread");
t->Fork((VoidFunctionPtr) SimpleThread, (void *) 1);
kernel->currentThread->Yield();
SimpleThread(0);*/
Thread *t[130];
for(int i = 0;i < 130;i++){
t[i] = new Thread("執行緒",1);
cout<<t[i]->getName()<<t[i]->getTid()<<endl;
}
}
測驗：
make
./nachos -K
…
…
實作執行緒id和限制最大數的所有增改原始碼thread.h和thread.cc，下載鏈接：下載
三、實作更改Nachos執行緒調度，按優先級調度
對于按優先級調度，我的想法是，因為創建一個執行緒之后，需要加入就緒佇列就能運行，Fork方法就實作了將執行緒（readyList）加入就緒佇列里的功能，還有Yield方法的功能是打斷當前正在運行的執行緒，運行就緒佇列里的執行緒，再將被打斷的執行緒加入就緒佇列，而加入就緒佇列是呼叫的是Schedule類里的ReadyToRun(Thread *thread)方法，ReadyToRun方法實作了將執行緒加入在就緒佇列里的隊尾，就是一個先進先調度的調度機制，我經歷了無數次錯誤之后，最后把思想集中在了加入就緒佇列時按照執行緒優先級加入佇列，實作如下（這是接著之前執行緒id做的）：
1.增改thread.h檔案，增加優先級成員
#define MAX_SIZE 128 //最大執行緒數
//pk陣列主要記錄執行緒號被使用的狀態
//下標位執行緒號，陣列對應值位執行緒號狀態
//對應值為0時，表示該執行緒號沒有執行緒占用
//對應值為1時，表示該執行緒號被占用
static int pk[MAX_SIZE]={0};
static int threadMAX = 0;//記錄執行緒數
class Thread {
private:
// NOTE: DO NOT CHANGE the order of these first two members.
// THEY MUST be in this position for SWITCH to work.
int *stackTop; // the current stack pointer
void *machineState[MachineStateSize]; // all registers except for stackTop
int tid;//執行緒id
int priority;//執行緒優先級,值越大優先級越高
public:
Thread(char* debugName);//原建構式 // initialize a Thread
~Thread(); //解構式 // deallocate a Thread
// NOTE -- thread being deleted
// must not be running when delete
// is called
// basic thread operations
Thread(char* debugName,int priority);//新建構式
int getTid(){return this->tid;};//獲得執行緒id
int getPriority(){return priority;};//獲得執行緒優先級
void Fork(VoidFunctionPtr func, void *arg); //將執行緒加入就緒佇列
// Make thread run (*func)(arg)
void Yield(); //打斷當前執行緒，運行就緒佇列里的執行緒
// Relinquish the CPU if any
// other thread is runnable
void Sleep(bool finishing);//將當前執行緒阻塞
// Put the thread to sleep and
// relinquish the processor
void Begin(); // Startup code for the thread
void Finish(); //執行緒運行結束
// The thread is done executing
void CheckOverflow(); // Check if thread stack has overflowed
void setStatus(ThreadStatus st) { status = st; }//設定執行緒狀態
char* getName() { return (name); }//獲取執行緒名字
void Print() { cout << name; }//列印執行緒名字
void SelfTest(); //測驗方法 // test whether thread impl is working
private:
// some of the private data for this class is listed above
int *stack; // Bottom of the stack
// NULL if this is the main thread
// (If NULL, don't deallocate stack)
ThreadStatus status; // ready, running or blocked
char* name;
void StackAllocate(VoidFunctionPtr func, void *arg);
// Allocate a stack for thread.
// Used internally by Fork()
// A thread running a user program actually has *two* sets of CPU registers --
// one for its state while executing user code, one for its state
// while executing kernel code.
int userRegisters[NumTotalRegs]; // user-level CPU register state
public:
void SaveUserState(); // save user-level register state
void RestoreUserState(); // restore user-level register state
AddrSpace *space; // User code this thread is running.
};
2.增改thread.cc檔案
Thread::Thread(char* threadName)//內核執行緒創建
{ int j;
for(j=0;j<2;j++){//設定id
if(pk[j]==0){
this->tid = j-1;
pk[j] = 1;
break;
}
}
priority = 100000;
name = threadName;
stackTop = NULL;
stack = NULL;
status = JUST_CREATED;
for (int i = 0; i < MachineStateSize; i++) {
machineState[i] = NULL; // not strictly necessary, since
// new thread ignores contents
// of machine registers
}
space = NULL;
}
Thread::Thread(char* threadName,int priority)
{
if(++threadMAX > MAX_SIZE){//限制執行緒數
cout<<"最大執行緒數:"<<MAX_SIZE<<"!!!"<<endl;
ASSERT(threadMAX<=MAX_SIZE);
}
int j;
for(j=2;j<MAX_SIZE;j++){//設定id
if(pk[j]==0){
this->tid = j-1;
pk[j] = 1;
break;
}
}
this->priority = priority;
name = threadName;
stackTop = NULL;
stack = NULL;
status = JUST_CREATED;
for (int i = 0; i < MachineStateSize; i++) {
machineState[i] = NULL; // not strictly necessary, since
// new thread ignores contents
// of machine registers
}
space = NULL;
}
Thread::~Thread()
{
DEBUG(dbgThread, "Deleting thread: " << name);
pk[tid + 1] = 0;
threadMAX--;
ASSERT(this != kernel->currentThread);
if (stack != NULL)
DeallocBoundedArray((char *) stack, StackSize * sizeof(int));
}
3.增改List.h檔案,增加成員方法
template <class T>
class List {
public:
List(); // initialize the list
virtual ~List(); // de-allocate the list
virtual void Prepend(T item);// Put item at the beginning of the list
virtual void Append(T item); // Put item at the end of the list
T Front() { return first->item; }
// Return first item on list
// without removing it
T RemoveFront(); // Take item off the front of the list
void Remove(T item); // Remove specific item from list
bool IsInList(T item) const;// is the item in the list?
unsigned int NumInList() { return numInList;};
// how many items in the list?
bool IsEmpty() { return (numInList == 0); };
// is the list empty?
void Apply(void (*f)(T)) const;
// apply function to all elements in list
virtual void SanityCheck() const;
// has this list been corrupted?
void SelfTest(T *p, int numEntries);
// verify module is working
void setNumInList(int numInList){this->numInList = numInList;}//設定佇列元素個數
ListElement<T>* getfirst(){return first;};//get頭指標
ListElement<T>* getlast(){return last;};//get尾指標
void setfirst(ListElement<T> *first){this->first = first;};//設定頭結點
void setlast(ListElement<T>* last){this->last = last;};//設定尾結點
protected:
ListElement<T> *first; // Head of the list, NULL if list is empty
ListElement<T> *last; // Last element of list
int numInList; // number of elements in list
friend class ListIterator<T>;
};
4.增改schedule.h檔案，增加成員方法
class Scheduler {
public:
Scheduler(); // Initialize list of ready threads
~Scheduler(); // De-allocate ready list
void ReadyToRun(Thread* thread);
// Thread can be dispatched.
Thread* FindNextToRun(); // Dequeue first thread on the ready
// list, if any, and return thread.
void Run(Thread* nextThread, bool finishing);
// Cause nextThread to start running
void CheckToBeDestroyed();// Check if thread that had been
// running needs to be deleted
void Print(); // Print contents of ready list
// SelfTest for scheduler is implemented in class Thread
void ReadyToRunPriority(Thread* thread); //將執行緒按優先級加入就緒佇列
private:
List<Thread *> *readyList; // queue of threads that are ready to run,
// but not running
Thread *toBeDestroyed; // finishing thread to be destroyed
// by the next thread that runs
};
5.增改schedule.cc檔案（實作ReadyToRunPriority方法）
void Scheduler::ReadyToRunPriority(Thread *thread){
//將執行緒thread按優先級加入就緒佇列
ASSERT(kernel->interrupt->getLevel() == IntOff);
DEBUG(dbgThread, "Putting thread on ready list: " << thread->getName());
thread->setStatus(READY);
ASSERT(!readyList->IsInList(thread));//斷言
ListElement<Thread *> *element = new ListElement<Thread *>(thread);//創建新結點
if(readyList->IsEmpty()){
//當就緒佇列為空時,直接加入佇列
readyList->setfirst(element);
readyList->setlast(element);
readyList->setNumInList(readyList->NumInList()+1);
}else{
//遍歷就緒佇列
//當執行緒優先級大于就緒佇列結點所對應執行緒優先級時
//將element插入在所對應結點之前
if(thread->getPriority() > readyList->getfirst()->item->getPriority()){
element->next = readyList->getfirst();
readyList->setfirst(element);
readyList->setNumInList(readyList->NumInList()+1);
}else{
ListElement<Thread *> *pre = readyList->getfirst();
ListElement<Thread *> *ptr = pre->next;
while(ptr != NULL){
if(thread->getPriority() > ptr->item->getPriority()){
element->next = ptr;
pre->next = element;
readyList->setNumInList(readyList->NumInList()+1);
break;
}else{
pre = ptr;
ptr = ptr->next;
}
}
if(ptr == NULL){
element->next = NULL;
pre->next = element;
readyList->setlast(element);
readyList->setNumInList(readyList->NumInList()+1);
}
}
}
}
6.在thread.cc里更改Fork方法
void
Thread::Fork(VoidFunctionPtr func, void *arg)
{
Interrupt *interrupt = kernel->interrupt;
Scheduler *scheduler = kernel->scheduler;
IntStatus oldLevel;
DEBUG(dbgThread, "Forking thread: " << name << " f(a): " << (int) func << " " << arg);
StackAllocate(func, arg);
oldLevel = interrupt->SetLevel(IntOff);
scheduler->ReadyToRunPriority(this);//將執行緒按優先級加入就緒佇列
// ReadyToRun assumes that interrupts
// are disabled!
(void) interrupt->SetLevel(oldLevel);
}
7.在thread.cc里增改Yield方法
void
Thread::Yield ()
{
Thread *nextThread;
IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);
ASSERT(this == kernel->currentThread);
DEBUG(dbgThread, "Yielding thread: " << name);
/*nextThread = kernel->scheduler->FindNextToRun();
if (nextThread != NULL) {
kernel->scheduler->ReadyToRun(this);
kernel->scheduler->Run(nextThread, FALSE);
}*/
kernel->scheduler->ReadyToRunPriority(this);//將當前執行緒按優先級加入就緒佇列
nextThread = kernel->scheduler->FindNextToRun();
if (nextThread != NULL) {
kernel->scheduler->Run(nextThread, FALSE);
}
(void) kernel->interrupt->SetLevel(oldLevel);
}
7.在thread.cc里增改SimpleThread方法（可改可不改）
static void
SimpleThread(int which)
{
int num;
for (num = 0; num < 4; num++) {
cout << "*** thread " << which<< " looped " << num << " times\n";
kernel->currentThread->Yield();
}
//kernel->currentThread->Yield();
}
8.在thread.cc里增改測驗方法
下面會用到C語言函式庫的srand()和time()函式，需要增加頭檔案#include “time.h"和#include"stdlib.h”，記得加上去，不然會報錯
void
Thread::SelfTest()
{
DEBUG(dbgThread, "Entering Thread::SelfTest");
/*Thread *t = new Thread("forked thread");
t->Fork((VoidFunctionPtr) SimpleThread, (void *) 1);
kernel->currentThread->Yield();
SimpleThread(0);*/
/* Thread *t[130];
for(int i = 0;i < 130;i++){
t[i] = new Thread("執行緒",1);
cout<<t[i]->getName()<<t[i]->getTid()<<endl;
}*/
Thread *t[4];
for(int i = 0;i < 4;i++){
srand(time(NULL)+i);
t[i] = new Thread("執行緒",rand()%10+1);
cout<<t[i]->getName()<<threadMAX<<" tid:"<<t[i]->getTid()<<" priority:"<<t[i]->getPriority()<<endl;
t[i]->Fork((VoidFunctionPtr) SimpleThread, (void *)threadMAX);
}
}
測驗
本次Nachos實驗實作的所有增改原始碼的所有原始碼，下載鏈接：下載
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/224834.html
標籤：其他
上一篇：停一停先別劃走！吊打全網的MySQL進階面試突擊，吃透最少阿里P7
下一篇：搜外七巧板-小程式開發者接入