第1页 / 共43页
第2页 / 共43页
第3页 / 共43页
第4页 / 共43页
第5页 / 共43页
第6页 / 共43页
第7页 / 共43页
第8页 / 共43页
Nachos 操作系统课程设计.doc
一、内核线程调度策略设计
设计目标：
设计背景：
1.1为Nachos添加按动态优先数调度策略
设计算法说明：
设计内容和步骤：
新的设计的实验内容和步骤：
以上设计实验输出结果的分析：
二、Hoare条件变量的设计与实现
设计目标：
设计背景：
1.1实现Hoare样式的管程
设计算法说明：
设计内容和步骤：
新的设计的实验内容和步骤：
以上设计实验输出结果的分析：
三、实现系统调用与内存管理
设计目标：
设计背景：
1.1 实现fork，exec，exit与join系统调用
设计算法说明：
设计内容和步骤：
1.2 实现内存管理
设计算法说明：
设计内容和步骤：
以上设计实验输出结果的分析：
四、文件系统
设计目标：
设计背景：
1.1实现二级索引
设计算法说明：
设计内容和步骤：
新的设计的实验内容和步骤：
以上设计实验输出结果的分析：
本设计的创新点：
本设计存在的问题和没达到的功能：
设计的体会、收获和总结
操作系统课程设计报告
2009-12-25
文件组织：
实验 1 位于 nachos-3.4.1 项目
实验 2 位于 nachos-3.4.2 项目
实验 3 位于 nachos-3.4.3 项目
实验 4 位于 nachos-3.4.4 项目
以上代码位于 code 文件夹
输出位于 output 文件夹。
目录
一、内核线程调度策略设计.........................................................................................3
设计目标：.....................................................................................................................3
设计背景：.....................................................................................................................3
1.1 为 Nachos 添加按动态优先数调度策略.................................................................3
设计算法说明：.............................................................................................................4
设计内容和步骤：.........................................................................................................4
新的设计的实验内容和步骤：.....................................................................................7
以上设计实验输出结果的分析：.................................................................................8
二、Hoare 条件变量的设计与实现..............................................................................8
设计目标：.....................................................................................................................8
设计背景：.....................................................................................................................8
1.1 实现 Hoare 样式的管程.........................................................................................10
设计算法说明：...........................................................................................................10
设计内容和步骤：.......................................................................................................10
新的设计的实验内容和步骤：...................................................................................18
以上设计实验输出结果的分析：...............................................................................18
三、实现系统调用与内存管理...................................................................................18
设计目标：...................................................................................................................18
设计背景：...................................................................................................................18
1.1 实现 fork，exec，exit 与 join 系统调用..............................................................19
设计算法说明：...........................................................................................................19
设计内容和步骤：.......................................................................................................20
1.2 实现内存管理........................................................................................................24
设计算法说明：...........................................................................................................24
设计内容和步骤：.......................................................................................................25
以上设计实验输出结果的分析：...............................................................................38
四、文件系统...............................................................................................................40
设计目标：...................................................................................................................40
设计背景：...................................................................................................................40
1.1 实现二级索引.........................................................................................................40
设计算法说明：...........................................................................................................40
设计内容和步骤：.......................................................................................................40
新的设计的实验内容和步骤：...................................................................................42
以上设计实验输出结果的分析：...............................................................................42
本设计的创新点：.......................................................................................................43
本设计存在的问题和没达到的功能：.......................................................................43
设计的体会、收获和总结...........................................................................................43
一、内核线程调度策略设计
设计目标：
在 Nachos 系统中实现按优先数调度线程
研究各种调度策略算法的实现，
分析各种调度算法的性能。
设计背景：
从 Nachos 系统的基本内核./threads/scheduler.cc 文件中可以看出 Nachos 系统
的基本内核实现了先进先出的调度策略。
调度类 Scheduler 管理着一个就绪队列 list。它的成员函数 ReadyToRun (current
Thread)将当前线程挂入该队列的队尾：
Scheduler::ReadyToRun (Thread *thread)
{
DEBUG('t', "Putting thread %s on ready list.\n", thread->getName());
thread->setStatus(READY);
readyList->Append((void *)thread);
}
它的另一成员函数FindNextToRun()则从list队首摘出一个就绪线程准备运行：
Thread *
Scheduler::FindNextToRun ()
{
return (Thread *)readyList->Remove();
}
这从基本内核执行的输出中可以得到验证：
*** thread 0 looped 0 times
*** thread 1 looped 0 times
*** thread 0 looped 1 times
*** thread 1 looped 1 times
*** thread 0 looped 2 times
*** thread 1 looped 2 times
*** thread 0 looped 3 times
*** thread 1 looped 4 times
1.1 为 Nachos 添加按动态优先数调度策略
设计算法说明：
采用静态优先数先给定一个线程的基本优先级，该优先数可以在创建一个线
程的时候指定，范围在 0 到 100 之间，数值越小优先级越低。
动态优先数计算方法为：
初始值 = 静态优先数
执行线程每 Tick + 10
就绪线程每 Tick - 1
唤醒线程 - 5
当执行线程动态优先数为 0 时重新计算就绪队列动态优先数：
按降序调整就绪队列优先级，从就绪队列首选择新的执行线程。
设计内容和步骤：
1、 将 thread 目录下的所有文件拷贝到 lab2 中，并修改其 Makefile.local 文件。
INCPATH += -I../lab2 -I../machine
2、 在 Thread 类中增加一个变量用于记录优先级并增加相应的构造函数与访
问函数。
void setPriority(int p){this->priority = p;}
void increPriority(int in){
if(this->priority + in < Max && this->priority + in > Min){
this->priority += in;
}
else{
if(in > 0){
this->priority = Max;
}
else{
this->priority = Min;
}
}
}
int getPriority(){return priority;}
private:
int priority;
Thread::Thread(char* threadName,int p)
{
name = threadName;
stackTop = NULL;
stack = NULL;
status = JUST_CREATED;
priority = 0;
priority = p;
#ifdef USER_PROGRAM
space = NULL;
#endif
}
3、 在 Scheduler 类中增加一个方法用于为整个就绪队列中的所有线程改变优
先级
void ThreadLowPri(_int arg){ Thread *t = (Thread *)arg; t->increPriority(-1);}
Scheduler::AddAll(){
readyList->Mapcar((VoidFunctionPtr) ThreadLowPri);
}
4、 在 interrupt::OneTick 中改变优先级
scheduler->AddAll();
currentThread->increPriority(10);
if(currentThread->getPriority() == Max){
yieldOnReturn = TRUE;
}
5、 更改相应的加入就绪队列与从就绪队列中取一个线程运行的方法 s
void
Scheduler::ReadyToRun (Thread *thread)
{
}
DEBUG('t', "Putting thread %s on ready list.\n", thread->getName());
thread->setStatus(READY);
readyList->SortedInsert((void *)thread,thread->getPriority());
//----------------------------------------------------------------------
// Scheduler::FindNextToRun
//
//
Return the next thread to be scheduled onto the CPU.
If there are no ready threads, return NULL.
// Side effect:
//
Thread is removed from the ready list.
//----------------------------------------------------------------------
Thread *
Scheduler::FindNextToRun ()
{
Thread* thread = (Thread *)readyList->Remove();
if(thread){
thread->increPriority(-5);
}
return thread;
}
6、 修改 Thread::Yield()方法，使得在选取下一个线程运行的时候包括当前线程
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);
}
(void) interrupt->SetLevel(oldLevel);
7、 修改测试类
void
SimpleThread(_int which)
{
}
int num;
for (num = 0; num < 5; num++) {
interrupt->SetLevel(IntOff);
printf("*** thread %d looped %d times\n", (int) which, num);
interrupt->SetLevel(IntOn);
}
printf("thread %d exit---------------------------------\n",(int) which);
//----------------------------------------------------------------------
// ThreadTest
//
//
Set up a ping-pong between two threads, by forking a thread
to call SimpleThread, and then calling SimpleThread ourselves.
//----------------------------------------------------------------------
void
ThreadTest()
{
DEBUG('t', "Entering SimpleTest");
Thread *t1 = new Thread("forked thread1",10);
Thread *t2 = new Thread("forked thread2",20);
Thread *t3 = new Thread("forked thread3",30);
Thread *t4 = new Thread("forked thread4",40);
Thread *t5 = new Thread("forked thread5",50);
t1->Fork(SimpleThread, 1);
t2->Fork(SimpleThread, 2);
t3->Fork(SimpleThread, 3);
t4->Fork(SimpleThread, 4);
t5->Fork(SimpleThread, 5);
}
新的设计的实验内容和步骤：
重新执行../lab2中的make然后运行，运行结果如下：
*** thread 1 looped 0 times
*** thread 1 looped 1 times
*** thread 1 looped 2 times
*** thread 2 looped 0 times
*** thread 2 looped 1 times
*** thread 2 looped 2 times
*** thread 2 looped 3 times
*** thread 2 looped 4 times
thread 2 exit---------------------------------
*** thread 3 looped 0 times
*** thread 3 looped 1 times
*** thread 3 looped 2 times
*** thread 4 looped 0 times
*** thread 4 looped 1 times
*** thread 4 looped 2 times
*** thread 4 looped 3 times
*** thread 4 looped 4 times
thread 4 exit---------------------------------
*** thread 1 looped 3 times
*** thread 1 looped 4 times
thread 1 exit---------------------------------
*** thread 3 looped 3 times
*** thread 3 looped 4 times
thread 3 exit---------------------------------
*** thread 5 looped 0 times
*** thread 5 looped 1 times
*** thread 5 looped 2 times
*** thread 5 looped 3 times
*** thread 5 looped 4 times
thread 5 exit---------------------------------
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
Ticks: total 400, idle 10, system 390, user 0
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0
Cleaning up...
以上设计实验输出结果的分析：
主线程首先执行后放弃CPU，T1优先级最低排在队首先被选中。主线程由于优先
级最高被排在队列尾。T1线程放弃CPU，当前T2在队首先被选中。这样依次进行，
直到所有的线程招待结束。
二、Hoare 条件变量的设计与实现
设计目标：
在 nachos 中实现 Hoare 样式的条件变量
使用 Hoare 样式的条件变量，实现生产者、消费者问题
使用 Hoare 样式的条件变量，实现哲学家就餐问题，要求避免死锁与饥饿
设计背景：
在 nachos，已经实现了 Mesa 样式的管程，其类声明如下：
class Condition {
public:
Condition(char* debugName);
// initialize condition to
// "no one waiting"
~Condition();
// deallocate the condition
char* getName() { return (name); }
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
