nachos线程优先级调度边创建边调度

nachos线程优先级调度边创建边调度是指在nachos操作系统中，当一个线程被创建时，它的优先级就已经被确定了。然后，操作系统会根据线程的优先级来进行调度，优先级高的线程会先被执行。这种方式可以提高系统的响应速度和效率，使得高优先级的任务能够更快地得到处理。同时，nachos还支持动态调整线程的优先级，以适应不同的应用场景。

相关问题

在NachOS-4.1中（1）在NachOS线程描述中增加调度优先级的数据成员，并完善就绪队列管理的成员方法； （2）实现基于优先级的FCFS调度； （3）调度时，线程的产生和调度须同时进行，并且要构建它们的线程家族树。在那个文件修改，怎么修改，如何输出，代码怎么写

在NachOS-4.1中，需要修改的文件是threads/thread.h和threads/thread.cc。

首先，在thread.h中，需要添加一个名为priority的数据成员，用于存储线程的优先级：

class Thread {
  private:
    // ...
    int priority; // 线程的优先级
    // ...
};

然后，在thread.cc中，需要实现就绪队列的管理成员方法，包括线程的插入、删除和查找操作。这里我们使用一个数组readyList来表示就绪队列，每个元素表示一组具有相同优先级的就绪线程：

static List<Thread *> *readyList; // 就绪队列数组

void Thread::InsertToReadyList() {
  // 根据线程的优先级找到对应的就绪队列
  List<Thread *> *queue = readyList[priority];
  // 将线程插入到就绪队列的末尾
  queue->Append(this);
}

void Thread::RemoveFromReadyList() {
  // 根据线程的优先级找到对应的就绪队列
  List<Thread *> *queue = readyList[priority];
  // 将线程从就绪队列中删除
  queue->Remove(this);
}

Thread *Thread::FindNextToRun() {
  // 从优先级最高的就绪队列开始查找
  for (int i = 7; i >= 0; i--) {
    List<Thread *> *queue = readyList[i];
    if (!queue->IsEmpty()) {
      // 返回队列中的第一个线程
      return queue->RemoveFront();
    }
  }
  return NULL;
}

在实现基于优先级的FCFS调度时，可以在系统初始化时为每个就绪队列创建一个列表，并将其保存到readyList数组中。然后，在scheduler.cc中，需要修改Scheduler::Run()方法，以便在线程调度时选择优先级最高的就绪线程：

void
Scheduler::Run (Thread *nextThread)
{
    Thread *oldThread = currentThread;

    ASSERT(kernel->interrupt->getLevel() == IntOff);
    if (nextThread != NULL) {
        readyList->Remove(nextThread);
        nextThread->setStatus(RUNNING);
    }
    currentThread = nextThread;
    currentThread->numInstr = 0;

    if (oldThread->space != currentThread->space) {	// address space to change
        oldThread->space->Clear();
        currentThread->RestoreUserState();     // set the kernel's page table
        currentThread->space->Activate();	// activate the user's page table
    }

    oldThread->CheckOverflow();		    // check if the old thread
					    // had an undetected stack overflow

    if (stats)
        stats->numContextSwitches++;
    if (debug)
        printf("Switching from thread \"%s\" to thread \"%s\"\n",
                oldThread->getName(), nextThread->getName());

    // 根据线程的优先级找到对应的就绪队列
    int priority = currentThread->getPriority();
    List<Thread *> *queue = readyList[priority];
    // 将当前线程插入到就绪队列
    if (oldThread->getStatus() == RUNNING) {
        queue->Append(oldThread);
        oldThread->setStatus(READY);
    }

    // 选择优先级最高的就绪线程进行调度
    nextThread = currentThread = FindNextToRun();
    if (nextThread == NULL) {
        printf("No threads ready or runnable, and no pending interrupts.\n");
        Print();
        // 等待中断发生
        while (true);
    }

    // 切换到下一个线程
    DEBUG('t', "Switching from thread \"%s\" to thread \"%s\"\n",
          oldThread->getName(), nextThread->getName());
    ASSERT(nextThread->getStatus() == READY);
    nextThread->setStatus(RUNNING);

    // 保存当前线程的状态并切换到下一个线程的上下文
    currentThread = nextThread;
    currentThread->numInstr = 0;
    currentThread->RestoreUserState();
    currentThread->SaveState();

    // 如果当前线程是新创建的线程，则调用它的Start()方法
    if (currentThread->isNew) {
        currentThread->isNew = false;
        currentThread->Start();
    }

    // 继续执行当前线程
    kernel->interrupt->Enable();
    currentThread->Run();
}

最后，构建线程家族树可以在Thread::Fork()方法中实现。当一个线程fork出另一个线程时，它将成为另一个线程的父线程，而另一个线程则成为它的子线程。因此，我们可以在Thread::Fork()方法中将当前线程设置为新线程的父线程，并将新线程添加到当前线程的子线程列表中：

void Thread::Fork(VoidFunctionPtr func, void *arg) {
  // ...
  childThread->parent = currentThread; // 当前线程成为子线程的父线程
  currentThread->children->Append(childThread); // 将子线程添加到父线程的子线程列表中
  childThread->numInstr = 0;
  childThread->isNew = true;
  childThread->Fork(func, arg);
  // ...
}

输出线程家族树可以通过在Thread::Print()方法中递归输出线程的子线程列表实现：

void Thread::Print() {
  // 输出线程的基本信息
  printf("%s(p=%d)", name, priority);
  if (status == RUNNING) {
    printf(" RUNNING\n");
  } else if (status == BLOCKED) {
    printf(" BLOCKED\n");
  } else {
    printf(" READY\n");
  }
  // 输出线程的子线程列表
  ListIterator<Thread *> iter(children);
  for (; !iter.IsDone(); iter.Next()) {
    Thread *child = iter.Item();
    printf("  ");
    for (int i = 0; i < depth + 1; i++) {
      printf("  ");
    }
    printf("|-");
    child->Print();
  }
}

最后，我们可以在main.cc中创建线程并打印线程家族树：

void SimpleThread(int which) {
  for (int num = 0; num < 5; num++) {
    printf("*** thread %d looped %d times\n", which, num);
    currentThread->Yield();
  }
}

int main() {
  // 初始化系统
  kernel = new Kernel();
  kernel->Initialize();
  // 创建线程
  Thread *t1 = new Thread("thread 1", 7);
  Thread *t2 = new Thread("thread 2", 4);
  Thread *t3 = new Thread("thread 3", 2);
  Thread *t4 = new Thread("thread 4", 5);
  Thread *t5 = new Thread("thread 5", 3);
  Thread *t6 = new Thread("thread 6", 6);
  // 创建线程家族树
  t1->Fork(SimpleThread, (void *) 1);
  t2->Fork(SimpleThread, (void *) 2);
  t3->Fork(SimpleThread, (void *) 3);
  t4->Fork(SimpleThread, (void *) 4);
  t5->Fork(SimpleThread, (void *) 5);
  t6->Fork(SimpleThread, (void *) 6);
  // 输出线程家族树
  printf("Thread family tree:\n");
  t1->Print();
  // 运行系统
  kernel->Run();
  return 0;
}

在Nachos_4.1中（1）在NachOS线程描述中增加调度优先级的数据成员，并完善就绪队列管理的成员方法；

在Nachos_4.1中，可以在Thread类中增加一个整型数据成员priority，用于记录线程的调度优先级。然后可以在ReadyQueue类中增加一些方法，以便进行按优先级排序的就绪队列管理，例如：

class Thread {
  private:
    // 线程的调度优先级
    int priority;

  public:
    // 构造函数中初始化优先级为0
    Thread(char* threadName) {
        ...
        priority = 0;
    }
    ...
};

class ReadyQueue {
  private:
    // 就绪队列中的线程数组
    List<Thread*> *threads[MAX_PRIORITY];

  public:
    // 构造函数中初始化就绪队列
    ReadyQueue() {
        for (int i = 0; i < MAX_PRIORITY; i++) {
            threads[i] = new List<Thread*>;
        }
    }

    // 将线程插入到就绪队列中
    void Append(Thread* thread) {
        threads[thread->priority]->Append(thread);
    }

    // 从就绪队列中移除线程
    Thread* Remove() {
        // 从高优先级队列开始查找
        for (int i = MAX_PRIORITY - 1; i >= 0; i--) {
            if (!threads[i]->IsEmpty()) {
                return threads[i]->RemoveFront();
            }
        }
        return NULL;
    }
};

在这里，我们使用一个数组来存储不同优先级的就绪队列，每个队列都是一个线程列表。在插入和移除线程时，根据线程的优先级来操作相应的队列。同时，可以在调度器中使用这些方法，实现按照优先级进行线程调度。