操作系统概念老师pintos实验项目一

项目一、线ReferenceGuide（以下简称pr）函数thread_create()用以创建新的线程。当函数thread_create()返回时，线程终止。这也就是说线程从生到死都是在函数thread_create()的控制之下的，因此这个函数也就相当于线程的main()函数。完了以后，调度程序会决定哪个线程会被调度进cpu运行（如果当时没有线程，则通过函数idle()实现上下文切换的机制是threads/switch.S80x86代码实现当然，我们在本实验中入cpu的新线程的状态。中。然后这个新线程做的第一件事情就是返回函数switch_threads()。有关线程切换的内容在接下来的内

位下（关于此函数的一些详细信息可参见pr“Low-LevelKernel用来内核的器。用于配置内核的加载地址并将start.S放在内核镜像的开头。本函数极其关键，不允许做修改。（关于此函数的一些详细信息可参见pr“TheLoader”）

信息可参见pr“High-LevelKernelInitialization”）

“

内核中malloc()和()函数的简单实现（关于此函数的一些详细信息可参见pr信息可参见pr“InterruptHandling”）。进行低级中断控制的汇编代码。（关于此函数的一些详细信息可参见pr“

提供基本的同步号量变量，以及优化屏障等。这个函数在接project用到。（关于此函数的一些详细信息可参见pr“Synchronization”）。进行有关虚拟地址和页映射表操作的函数和宏定义。这个在project3在可以直中"文

有个时显

种现成的设备块类型：IDE磁盘和分区。在project2之前不需要修改本函数的内容。

中被用到，这是因为每个设备使用一个PIT的输出通道。

pintos行的第一部分就是加载程序。加载程序threads/loader.S中实现。pcBIOS载加载程序到内存中。加载程序将负责在内存中找到内核的位置，并将其加载到内存中，然后跳转到start函数。理解加载程序的具体工作并不是必要的。理解这个最好还要了解一下80x86架构。c的BOS（主硬盘（BR）。4BRs8当加载程序找到可引导的内核分区以后，它将会分区中的内容进入内存物理地址128kB处。这时，内核会在分区的始端。由于分区边界对齐约定，占用的空间可能会比所需要的大。因此加载程序不同时，标准的PCBIOS不会提供任何1MB以上内核的办法。的位置，但是内核的ELF头包含一个指向它的指针。装载机提取指针，并跳转到它指向的位置。加载程序的最后一个任务就是将控制转移到内核的始端，即threads/start.S中的start()函数。这个启动代码的第一项任务实际上是通过“询问”BIOS“PC的内存大小”获取本机的内存大小。而通过BIOS数来做到这一点只能检测64MBRAM，因pintos能利用这么多的内存。这个函数会将内存大小在全局变量init_ram_pages中。CPU始化的第一部分是使A20址线，也就CPU20的地址线。由于历史原因，计算机启动时这个地址线固定为0，这意味着试图超出1MB内存（2提高到20次幂）将会失败。pintos接下来，加载程序创建一个基本的页表。当前页表映射64MB在虚拟器的基部（从虚拟地址0） （3GB）。pintos内核只需要发生后一种映射，但有这是一个先有鸡还是先有蛋的问题，如果我们不包括前者：我们目前的虚拟地址是大致地址0x20000，在我们没打开页映射表之前加载程序不会跳转到0xc 寄存器。我们尚未具备处理在保护模式下的中断，所以我们中断。最后再调用main（）函数。main{char/*ClearBSS.*/bss_init();/*Breakcommandlineintoargumentsandparseoptions.*/argv= mand_line();argv=parse_options/*Initializeourselvesasathreadsowecanuselocks,thenenableconsolelocking.*/thread_init();console_init();/*Greetuser.printf("Pintosbootingwith%'"PRIu32"kBRAM...\n",init_ram_pages*PGSIZE/1024);/*Initializememorysystem.*/palloc_init(user_page_limit);malloc_init();paging_init/*Segmentation.*/#ifdefUSERPROGtss_init();gdt_init/*Initializeinterrupthandlers.*/intr_init();timer_init();kbd_init();input_init();#ifdefUSERPROGsyscall_init();/*Startthreadschedulerandenableinterrupts.*/thread_start();timer_calibrate();#ifdef/*Initializefilesystem.*/ide_init();locate_block_devices();printf("Boot/*Runactionsspecifiedonkernelcommandline.*/run_actions(argv);/*Finishup.*/shutdown();thread_exit();}main（）函数刚启动时，系统处于一个非常原始的状态。我们在已启动分页32保护模式下，但除此以外几乎没有任何东西是准备好了的。因此，main（）函数主要是调用其他pintos模块的初始化功能。这些通常被命名为module_init（），其中module是模块的名字，module.c中是模块的源代码，而module.h中是该模块的头文件。中。BSS是全零的，加载程序并不会把它加载到内存中。我们之需要用memset()来将其就可以了。 mand_line()来将内核命令行分成参数和解析选项，然后再调用parse_options()函数在命令行中的解析选项。(即后来在命令行上执行的指定动作。)a。a。a。和立的来（这个在后面有介绍）。之后的timer_initkbd_init()函数将分别为计时器中断处理和键盘中断处理做准备。input_init()函数将建立串口和键盘的流式输入。在projects2及之后的项目中,我们需要用exception_init()函数和syscall_init()函数处理用户的中断。切换到这个模式。最后，timer_calibrate()函数将校准计时器。通过filesys_init()函数初始化文件系统。最后，如果内核命令行中识别到了-q指令，那么调用shutdown_power_off()函数来终止模拟器运行。如果没有，main()函数将调用thread_exit()函数终止本线程，但不会影响其他线程的继续执行。1、关于pintos中的“threads/thread.h”文structthread4kB 内核 从上往下 sizeof(structthread) 0kB 给到内核栈。由于给到每个线程的页只有几个kB小，因此structthread大小控制在1kB以内。许开辟大的结构体或是非静态局部变量的大数组。需要请改用malloc()函数或者structthread成员tid_t认情况下，tid_t是一个typedef为int的类型，然后tid从1（初始线程）开始依次递增。我们可以改变tid的类型和编号的机制。的线程状态:THREAD_RUNNING线程状态在名为ready_list的双向链表中。线程状态线程正在等待的发生，比如说：锁的可用、一个中断的调用。这个线程在没有调用中继续运行。这是完成pintos中线程阻塞（等待）和非阻塞（非等待）切换的最方便的办法。线程状态:入structthreadcharstructthreaduint8_t每个线程都有一个它自己的栈来追踪它的状态。当线程处于运行状态时，CPU的堆栈指针寄存程序发生中断时,而intr_frame结构体总会在这个页的顶端（这个在后面会讲到。structthread成员int因此优先级为0最低优先级，优先级63最高优先级。Pintos供了忽略优先级的机制，但是在project1中我们需要实现优先级调度。structthread成员structlist_elem使用thread_foreach()函数可以迭代所有的线程。structthread成员structlist_elemlist_elem用来将线程连接到双向链表中的（其中既包括了就绪队列的链表，也包括了在sema_down()函数中定义的与信号量的有关的就绪队列的链表。这是因为在信号量的有关的就绪队列中并不等同于在就绪队列中，因此将两者区分开（而这一成员thread.csynch.cstructthread成员uint32_tstructthread成员unsignedAA，而TADACscre()函数将会检查正在运行的线srtedcEDACc2、关于pintos中的“threads/thread.h”文函数voidthread_init由main()函数所调用，用来初始化线程系统。它的主要作用在于为pintos的初始线程建立结构体structthread是可以实现的因为pintos加载程序总会将初始线程的栈放在页的顶端，函数thread_init()运行之前，thread_current()函数调用会发生错误因为正在运行的线程的比如说请求锁的lock_acquire()函数，因此thread_init()函数必须在thread_current()之前完成函数voidthread_start调度进cpu的线程（此线程不做任何操作。然后再使能中断。而使能中断是使能调度程序必经的一步，因为调度程序需要运行在计时器中断的基础之上，并需要通过intr_yield_on_return()函数voidthread_tick函数voidthread_print_stats函数:tid_tthread_create(constchar*name,intpriority,thread_func*func,voidthread_create()函数将为structthread结构体和栈分配一个页的空间，并初始化新线程的成员类型voidthread_funcvoid去。其中aux为这个函数的参数，也要一并传递过去。函数voidthread_block函数切换回非阻塞状态不具备执行的可能，因此我们在调用这个函数时也需要考虑到对函数voidthread_unblock(structthread函数structthread*thread_current函数:tid_tthread_tid(void)函数constchar*thread_name函数:voidthread_exit(void)NO_RETURN函数:voidthread_yield(void)程可以是原来刚刚让出cpu的线程，因此我们不能依赖这个函数来控制线程的运行时间。够与thread_action_func()函数给定的签名相匹配。函数:intthread_get_priority(void)函数intthread_get_nice函数:intthread_get_recent_cpu(void)函数:intthread_get_load_avg(void),UUU，占死。决一问UUs中使用了er重新实现timer_sleep()函数,本函数定义在devices/timer.c中.虽然这个函数已经提供了一种可能的实现，但它是“忙等待”的。它在循环检查当前时间并一直调用thread_yield()函数直到时间到。我们函数voidtimer_sleep(int64_t暂停调用线程的执行直到时间流x时钟周期。除非系统空闲，该线程不需要x时某正在执行的线程因为某种原因至少要休x而且x时钟周期后唤醒我们不建议改动这个值，因为这个值的变动会导致一些测试的fail。独立函timer_msleeptimer_usleeptimer_nsleep()已经存在。它可以休眠特定的毫秒、微秒或纳秒。需要，这些都会自动调用timer_sleep()。我们不能修改这三个函数。条线程的唤醒机制，并通过测试alarm-multiple；对综合单条多条线程的唤醒机制，并通过测试alarm-simultaneous；对不需要休眠的线程的处理，并通过测试alarm-zero；对休眠时间片异常输入的处理过测试timer.ctimer.h的同步部分，timer现在我们来timer.c件中的timer_sleep函whiletimer_elapsedstartticks)：为判断流逝的时间（start时间和调用这个函数时的系统时间();在本来我们是timer_sleep数使线程休眠相应的时间的。按照正常的做法，线程的休眠cpu一直处于“来一个线程，看时间片还没到就马上把这个线程扔回了就绪队列”的状态。在这个状态中cpu1查是否可以唤醒自己(iftime_elasped(startticks更加糟糕的是由于当前实现中操作系统直接从队列头部获取线程运行，而当前线程会被扔回read队列的头部，因此即使CPU还给操作系统(通过调用thread_yield()函数实现把当前cpu线程扔的休眠的线程阻塞起来，不要让它进入就绪队列。此时cpu空出来了，就绪队列里面也没有了这个休眠的线程，从而调度程序和cpu完全可以当这个线程“”了，从而继续干着他们的活。ASSERT(intr_get_level()==INTR_OFF);：检查此时需要将中断thread_current()->status=THREAD_BLOCKED;：将状态置为阻塞状态。schedule();：启动调度程序来进行cpu调度。数structthread*t：传入需要从非阻塞状态转换为阻塞状态的线程的指针ASSERT(is_thread(t));：检查这个指针是不是真的指向一个线程old_level=intr_disable();：中断并且返回之前的中断状态到old_level参数中ASSERTt->status==THREAD_BLOCKED);：检查所指的那个线程是不是真的处于阻塞状态list_push_back(&ready_list,&t->elem);：将这个线程链到就绪队列的尾部体而通thread_create数来新建线程并初始化其中的相关参数。因此我们需要到这个函数中进行初始化。（一定要注意thread_init数分开。thread_init数主要是要创建一个空闲的初始线程，而我thread_create数。但实际上创建这种线程是thread_start开始的，这个函数会先初始化信号thread_create数创建新线程，最后再将使能打开以进行抢占式调度。但创建新线程的主要工作还是在thread_create中进行/*CreatesanewkernelthreadnamedNAMEwiththegiveninitialPRIORITY,whichexecutesFUNCTIONpassingAUXastheargument,andaddsittothereadyqueue.Returnsthethreadidentifierforthenewthread,orTID_ERRORifcreationfails.Ifthread_start()hasbeencalled,thenthenewthreadmaybescheduledbeforethread_create()returns.Itcouldevenexitbeforethread_create()returns.Contrariwise,theoriginalthreadmayrunforanyamountoftimebeforethenewthreadisscheduled.Useasemaphoreorsomeotherformofsynchronizationifyouneedtoensureordering.Thecodeprovidedsetsthenewthread's`priority'membertoPRIORITY,butnoactualpriorityschedulingisimplemented.PriorityschedulingisthegoalofProblem1-3.*/thread_create(constchar*name,intpriority,thread_func*function,void*aux){structthreadstructkernel_thread_frame*kf;structswitch_entry_frame*ef;structswitch_threads_frame*sf;tid_ttid;enumintr_levelold_level;ASSERT(function!=/*Allocatethread.t=palloc_get_pageif(t==return/*Initializethread.*/init_thread(t,name,priority);tid=t->tid=allocate_tid();/*PreparethreadforfirstrunbyinitializingitsDothisatomicallysointermediatevaluesforthe'stack'membercannotbeobserved.*/old_level=intr_disable/*Stackframeforkernel_thread().*/kf=alloc_frame(t,sizeof*kf);kf->eip=kf->function=function;kf->aux=aux;/*Stackframeforswitch_entry().*/ef=alloc_frame(t,sizeof*ef);ef->eip=(void(*)(void))/*Stackframeforswitch_threads().*/sf=alloc_frame(t,sizeof*sf);sf->eip=switch_entry;sf->ebp=0;intr_set_level/*Addtorunqueue.*/thread_unblock(t);return}程已经被调度cpublocked_ticks值并不固定，因此可能会很大，也就会一直呆在阻塞我们之前有讲到thread_tick函数，这个函数在每个时钟周期都会被计时器中断调用一次。这个函数就是定义在time.c里面的timer_interrupt函数。“thread.c”函数里面定义的thread_tick函数。函idle_tickscpu多长的时间处于空闲状态，kernel_tickscpu多长的时间处于运行内核线程的状态，user_ticks统cpu多长的时间处于运行用户程序的状态，thread_ticks为了统计这个线程从上次被调度cpu了多长时间（也就是占用了多长时间的cpu）。因此我们可以很清楚地看到thread_tick函数主要是为统计处在运行状态的线程的信息。由于我们是需要将线程阻塞起来并函者在timer_interrupt函数调用一个能统计阻塞时间的函数。线程我们直接让我们之前定义的blocked_ticks减一就好了（也就是每个时钟周期检查一次，每次都将其数定义在用func数（这个函数必须以线程指t参数的指针（将参数所在空间的指针传递过去）作为参数）。因此我们可以将我们所写的那个计算阻塞时间的函数的指针作为参数传递给函数thread_foreach。一个处于阻塞状态的线程进行阻塞时间的计算；当然由于函数thread_foreach必须在中断的情况之0。小于0是不可能发生的，属于错误输入（如果我们不能将它处理掉可能会出现无穷休眠（因为我们是从ticks参数开始递减减到0以后说明休眠结束），出现线程被）；等于0说明不需要休眠，那就直接跳出函数就行了，不必要做这些无用功。由于阻塞函数thread_block是一个原子操作（因为我们不能中断把线程从cpu中调度出来进入阻塞状态的过程），因此我们需要先阻塞再进行阻塞操作。当然最进入就绪队列就可以了。而由于我们是在timer_interrupt函数中实现对所有阻塞的线程进行遍历，并对到0以后将阻塞状态变为非阻塞状态进入就绪队列就可以了。然后thread件夹下执行makecleanbuildmake文件夹下执行makecheck在pintos中实现优先级调度。当一个优先级高于正在cpu中运行线程的线程被创建出来，添加到就可能会导致当前运行的线程被抢占而不得不放弃cpu。pintos线程的优先级范围PRI_MIN0PRI_MAX63)。较低的优先级数对应较低的优先级，因此优0先级63最高优先级thread_create()函数进行新线程会默认为PRI_DEFAULT(31)。有关优先级的宏PRI_定义在threads/thread.h文件中,而我们不应该随函数只会被三个线程公有函数（即对每个线程都有效的函数）thread_block(),thread_exit(),和后再将一个新线程切换进cpu中运行。schedule()很短，但是要掌握却不那么先获取了当前处于运行状态的线程的指针，并将它放在局部变cur。并调next_thread_to_run()函数获取准备进cpu运行的新线程的指针存到局在所有线程中优先级最高的那个线程调度进cpu中。从这里我们可以很明显地看出，当就绪队列为空时，会返回空闲线程的指针（也就是告cpu有实际的线程要运行了）；当就绪队列不为空时，会返回就绪队列头部的线程的指针（也就是告诉cpu那然要选择所有线程中优先级最高的那个线程调度进cpu中，就存在两种办法。一种是利用因此我们只能另寻他法。既然next_thread_to_run()函数每次都是选取就绪队列队头的那个线程。那较为快速的排序（比如：归并排序）。但这个方法弊端比直接利用next_thread_to_run()函数每次选取那个最高优先级的线cpu还大，因此排序的时间复杂度总是大于选取最高优先级的线程的时间复杂能力，但也只能放弃cpu进入就绪队列的。现在我们需要对这三个情况进行逐条分析。可以很清楚地看到线程是通过thread_unblock()函数进入的就绪队列。绪状态的情况。也就是说阻塞线程也是通过thread_unblock()函数进入的就绪状态。最后是从运行状态回到就绪状态的情况。在之前的背景介绍中我们可thread_yield()函数在处理着从运行状态进入就绪状态的情况。也就是说正在运行的线程是通thread_yield()函数进入的就绪状re_ck()函数。并保存前的中断状态到局部变量old_level中（这里中断的原因在于将线程从阻塞状态进线程的指针通过list_push_back()函数直接放回到就绪队列的尾部，将线程的状态从原来的阻塞状态设为就绪状态。最后再从变量old_level恢复原来中断前的中断状态。蔽并保存前的中断状态到局部变量old_level中（这里中断的原因在于将线程从运行状态进入就绪状态是原子操作，中间是不能出现任何中断的，没有调度到一半停止的情况）。再检查当前处cpu通过list_push_back()函数直接放回到就绪队列的尾部，将线程的状态从原来的运行状态设为就绪状态。最后别忘了还要从变量old_level恢复原来中断前的中断状态。从对这两个函数的分析中我们可以看出将线程放回到就绪队列里面主要是通过list_push_back()函数在pintos里面就绪队列是通过双向链表实现的。近的元素为就绪队列尾的线程。“head”以外定义为NULL。同理，“tail”以外也定义为NULL。插入的用来指示插入的位置（这个函数会将新的元素插入到before数的前面）elem需要插入的新元是指structlist_elem类型之间的转换问题。structthread转换为structlist_elem的指针是不难的。别忘了在structthread定义时有一个参数elem。这个参数就是这个structthread类型的指针对应的structlist_elem类型的指针了。在thread_unblock()函数中我们就看到了类似的用法。然而从structlist_elem类型的指针转换为对应structthread类型的指针就没那么简单了。还好，在list.h文件中已经给我们实现了相关的宏定义。我们用这个宏定义就像用函数一样用就好了。比如说当前structlist_elem类型的指针为p，那么LIST_ELEM就是&p，STRUCT就是我们的目标类型structthread，MEMBER就是structthread中使用在注意thread_unblock()函数和thread_yield()函数都要进行修改）锁），而M线程又在就绪队列中的情况。这时候，H线程无法第一时间进入cpu中执行（因为它一直处于等待状态），而它所等待L程L程优先级低而无法运行（因为还M程存在）L线程将一直保有它的资源。一种合适的解决办法是在出现这种情况时，将HL。等到L线程将锁释放以后，优先级再恢复回来。在中函数voidthread_set_priority(intewpioity。函数intthread_get_priority之前有讲过，schedulethreads/thread.c和thread_yield()所调用。在这三个函数中的任意一个函数调用schedule()函数时,需要先中断或确然后再将一个新线程切换进cpu中运行。schedule()会首先获取了当前处于运行状态的线程的指针，并将它放在局部变量cur中。并调用next_thread_to_run()函数获取准备进入cpu中运行的新线程的指针存到局部变量next中。然后再调用作），切换进的新线程不会是当前运行的线程（因为一个线程不会既在cpu行又在就绪队列里面），最后还要确认一next_thread_to_run()函数获取到的确实是一个线程的指针，而不是别的什么）在switch_threads()函数结束调用返回之前，我们要切换的线程已经运行在cpu里面了。而这个函数也会返回我们需要通过switch_threads()函数调度出去的线程的指针。运行到的代码的指针（因为当前运行的线程可能还没有运行完））保存在这个线程对应的结构体structthread（这样的话下次运行时就知道上次运行到哪里了）structthread剩余的调度工作thread_schedule_tail()函数中进行。这个函数首先会将当前运行的线程（也就是cpu）的状态标识改为运行状态（cpu只是这个标识还没有改过来。由于schedule()函数是原子操作，因此我们不必担心在调用switch_threads()包structthread）。switch_threads()函数被调用之前做，因为switch_threads()函数还需要这个线程的相关信息。e（sewsee_（）（容遇很的但他大后没么了特是于是个线，在sw（）e：最顶上的虚拟栈帧是为switch_threads()函数准备的,标识为structswitch_threads_frame。在这样就可以通过这个函数指针调用到switch_entry()函数了。紧接着的虚拟栈帧是为switch_entry()函数准备的。switch_entry()函数是在threads/switch.S意，对于一个刚刚通过thread_create()函数创建的新线程来说，thread_schedule_tail()函数都由thread_create()函数所调用，而对于老线程来说都是先返回到schedule()函数再由schedule()函数所调用。正因如此，schedule()函数和thread_schedule_tail()函数分开在threads/thread.c文件中的一个函数。程中进行IO交互可能造成）。在某cpu运行的线程发生优先级变化时（因为我们不需要实现当前线程对其他线程的优先级作出修改而导致就绪队列或者处于阻塞状态的某个线程的优先级发生改变的情况），要判断cpu正在运行的线cpu运行。同时还要考虑刚刚创建的新线程的优先级情况（即在刚刚创建的新线程的优先级高过cpu中正在运行的线程时也要对它进行抢占）。我们从先前的背景分析中可以看到线程优先级的改变主要通过一个thread_set_priority()函数进行，从代码可以看出这个函数首先利thread_current()函数返回当前正cpu运行的线程的指针，然后将当前正在运行的线程的优先级改变为我们传入的参数new_priority。在使thread_set_priority()函数更改了当前运行的线程的优先级后，我们就需要判断cpu在先级的线程进入cpu中运行。这时候我们就需要处理以下几个问题在上一次的“优先级调度（一）”的任务中我们已经对thread_yield()函数做出了修改。我们通过thread_yield()函数就可以将刚刚在cpu中运行的线程调度出cpu，并按照优先级放到就绪队列中合适的位置中（使得就绪队列是优先级有序的）。因此我们可以直接通过thread_yield()函数把当前在cpu中运行的线程抢占出来，将就绪队列中的队头线程放到cpu里面，并把刚刚调度出来的线程在就绪队列中进行优先级插入。这种方法保证了从cpu中调度出来的线程总是能放到就绪队列中的合适位置（使得就绪队列是优先级有序的）。因此我们可以通过thread_yield()函数完成线程调度操作。然后我们再来看看第一次运行某thread_create()函数创建的新线程的情况。新创建的线程首先要为以后线程的正常运行做准备。所以会先通过创建虚拟栈帧的方法强制进到cpu里面抢占原有线程（此并执行switch_entry()函数和kernel_thread()函数）调整好一些相关参数（比如说调整栈的指针。在thread_set_priority()函数。最终返回，把新线程放到就绪队列中，原有在cpu正常运行的线程继续正常运行（因为没有通过schedule()函数和thread_yield()函数进行抢占，所以上述执行过程较一般情况下的cpu调度有很大不同。上述操作都是在中断被下的原子操作，而且有机制保证了这个过程中调用的thread_yield()函数等其他调度函数都没办法发挥作用。后造成的效果是一个新线程被加到了就绪队列中。这个线程有可能是比现在cpu运行的线程的优先级大的就行了。优先级大怎么办？很简单，把原来在cpu运行的线程抢占出来就行了。具体做法和先前的那cpu的线程的优先级必定大于除了这个新创建的线程之外的任何一个线程的优先级cpu运cpu运行的线程必定优先级最高。而如果这个新线程的优先级比cpu特别提醒，千万thread_unblock()函数中调thread_yield()函数，也thread_yield()放到就绪队列中。而且这两者都是原子操作，是不能被中断的。假如在thread_unblock()函数中调用了err（（（ee前运行的线程的更改后优先级与就绪队列中队头线程的优先级，并通过thread_yield()函数完成线程调度我们在上个任务中提到优先级反转”的问题。我们先来回顾一下。假设我们有三个线程H、M、L。H优先级大M，M优先级大L。如H程等L程的发生（比如说，H等待L有的锁），而M，H线程无法第一时间进入cpu中执行（因为它一在L线程L资源释放掉了以后才能运行（注意：不一定运行的处理被拖延（如果一直有较线程L的优先级线程被创建L无法运行，会出现H饿的现尽早释放资源给到线程L。没办法，又不能等到线程M运行完再运行L，马上运行L直到它把它占有的资源放出来（注意L在这时候可能还没运行完），这时候，线H到它想要的东西了，马上从非阻塞状态跑出来，把线L级的线程，让较低优先级线程先运行。假设就像原来那个只有H、M、L三个线程的情况。线程L的优先当期运行的线程H优先级给到线程L肯定比我们再取就绪队列队头线程（线程H）要简单）程中那个优先级最高的（对于这一点我们可以这样想。假设优30、20、10三个线程都需要优先级为5线程的资源，而就绪队列中又存在一个优先25的线程。如果我们就是把低优先级线程的优的为但优先级提高到25可以吗（也就是找就绪队列中的一个线程优先级来保证优先级为30的线程一种情况，当优先级30线程被占用的资源最先被低优先级线程释放时，优先级30线程就可以抢会继续抢占cpu。那我们又会想我们可以用其他相关方法保证它的正常功能啊，比如再加上一个比较，比出cpu。但此时又有问题了，调度出去以后那个低优先级线程的优先级应该设为多少。这又会对应出很多先cpu20线程一定会在优先20线程运行完了以后才cpu（当然，发生了优先实就算出现这种并不会造成影响。因为这时原来这个低优先级线程就只占有了优先级为20、30这两个线程的资源。因此这个低优先级线程优先级会被置为这两者的较大值30，那个优先级10程也就只能在就绪队列里面继续呆着了，而不会马上抢占cpu。现实生活中我们可能会遇到这样一种情况。还是原来优先级高到低的三个线程H、M、L。线H先级最高先进cpu。然后发现自己的资源被线M着，自己进入了阻塞态。没办法只好将线H优先级给到线M。结果没想到McpuL着，自己也进入了阻我们可以很容易想见这样一种解决办法：把现程M的优先级（此时线程M的优先级就是原来线源给到线H行就可以了。这样让渡看似非常简单，但有一个问题需要处理：线L运行到释放资源到了，使得这个线程不得cpu，调度一个新的进来。这个新线程也对临界区进行了操作。这出现了某A院办上厕所，这时院长来了也想上厕所。发现厕所门被锁上了。那院长也只能等你出来他才没有同步这个概念了（不管是不是临界区里面的代码都会非抢占地运行），也没有竞争这种情况（在中先级为30的线程不会和它竞争抢占cpu）。步问题不在了，但是却出其他的一些问题。因此不允许通过这种方法解决系统中出现的所有同步问题。我们应该采用信号量的方法来解决这个问题。我们需要通过信号量、锁和状态变量来解决大部分同步问题说在循环体内一直调用thread_yield()函数）。进行线程同步最原始的方法就是中断，也就是令cpu暂时不处理中断。如果中断被，由计时能，系统随时都可能抢占当前运行的线程（比如说来了一个高优先级线程），无论这个线程是在两C和使能中断的函数和数据类型在threads/interrupt.h文件中。类型:enumintr_level函数:enumintr_levelintr_get_level(void)函数enumintr_levelintr_set_level(enumintr_level根据level的值进行中断的 函数:enumintr_levelintr_enable(void)函数:enumintr_levelintr_disable(void)操作如果信号量被初始化0,则它可以用于同步，同步意味着一个执行单元的继续执行需等待另一个执行单元完成，保证执行的先后顺序。现有两个线程A、B。A是父线程，而B是子线程，A需要B运行完了才能运行。假设先执行了父线A（在父线程中没有定义V而只P作）。通过前边讲P作的特点可知，由于信号量值为0，该线程被阻塞，线程A不会继续运行。因此。直到子线B（在子线程中没有定P作，而只有V作）运行完了以后，进V作，由于信号量的等待队列中有线程（这里是父线A）在等待资源，则唤醒一个阻塞线程（这里是父线A），从而保证了父线A子线程B之后运行。到此这个信号量就地完成任务了。线程进入临界区时都会将信号量值递减。每当有线程V将信号量值递增并且唤体数，也就是表示了当前临界区还可以放多少进程）。一开始初始化为1，说明临界区在某一时刻只允许的pintos中与信号量有关的函数和数据类型在threads/synch.h文件中类型struct,函数:voidsema_down(structsemaphore*sema)函数boolsema_try_down(structsemaphore操作。如果这个信号量值不为正值则会让cpu处于忙等待状态，并返回false。若为正值，则允许该线程继续运行，并返true，将信号量0（直到运行完出了临界区，进V作，信号量说明已有线程处于临界区，1说明没有线程处于临界区。尤其注意不允许多次循环调用这个函函数voidsema_up(structsemaphore然而信号量也是通过中断和线程的唤醒与阻塞（通过thread_block()函数与thread_unblock()类型:structlock函数voidlock_init(structlock函数:voidlock_acquire(structlock*lock)函数:boollock_try_acquire(structlock*lock)功能与lock_acquire()函数类似。这个函数将通过无阻塞（忙等待）的方式请求锁。如果这个锁正在被其他线占有则会让cpu处于忙等待状态，并返回false。若没有，则将锁分配给那个线程，并返回true。注意不允许多次循环调用这个函数，否则将使系统处于严重的忙等待状态。如果真的要多次循环使用，请使用lock_acquire()函数。函数voidlock_release(structlock函数boollock_held_by_current_thread(conststructlockrraeerrerrme（和rreme（rr_s和rrae）Vrrem。P、V操作。我们之前提到过优先级反转都是与信号量有关的，或者更加准确一点点是与锁有关的。要去深入分析信号量的P、V作的具体过程。与此同时我们还不可避免的进行优先级的改变，因此上次任务中遇到的set_priority()函数自然也是绕不过去的。此我们就先从信号量开始看起。首先我们先来看一下关于信号量的定义和相关的操作（主要看P、V作定否存在。如果存在这样一个信号量，我们就初始化其对应的信号量值value，并初始化其对应的阻塞队sema_down()函数就是为实P作的。在sema_down()函数中需要传入信号量的指sema。这保留前的中断状态到参数old_level中。然后就会检查信号量值的大小。若信号量值为正，说明还存会被减一。最后别忘了从参数old_level恢复前的优先级状态（说明原子操作已经完成）。这时我们会产生一个疑问sema_up()函数是一个原子操作，怎么中间还会出thread_block()函数将当前运行的线程给阻塞掉，换出cpu呢？这个问题，写pintos的大牛们已经给出我们答案了。他们将答案写在了sema_up()函数上面的注释那里。不存在了。而当这个线程被唤醒了以后，又重新出现在了系统的眼前，等到一定时机进入cpu会继续操作。我们会这样想，既然当前线程thread_block()函数以后就被阻塞起来了，不再继续运行了。执行下面的信号量值才会被减一操作。那按照这个道理if句也while环呢？这里想卖个关子，先继续往下看V操作，我们就有答案了。sema_up()函数就是为实V作sema_up()函数中需要传入信号量sema。这个函数首先会检查传入的信号量的指针sema存在。若存在，就说明V作了。众所周知，信号量的P、V操作均为原子操作，所以我们需要将中断。所以调用intr_disable()函数中断，并保留前的中断状态到参数old_level中。然后就会检查这个信号量对应的阻塞队列是否为空，不为空则将最后也别忘了从参数old_level恢复前的优先级状态（说明原子操作已经完成）。现就答个了从)中可看唤的头程进就绪ef了（me），这显然是存在问是空闲没人占着吧；如果在某个工人手里，那我们就要知道到底在谁手里吧。因此我们需要一个struct这把的工人把仓库里的活干完以后，把让出来，才可以进去。因此我们还需要定义一个structlock_init()函数主要是用来初始化锁的。在lock_init()函数中需要传入锁的指针lock。这个函数首先开始锁是不被任何线占有的），对应的信号量值为1（因为在pintos中临界区只允许一个线程进入，lock_acquire()函数实现了锁的P。在lock_acquire()函数中需要传入锁的指针lock。这个函数它。如果没有，就说明可以开始做P下来的内容就顺理成章了。首先通过调用sema_down()那可以对这两个操作更换顺序吗？其实也是不能的。我们可以设想下面这种情况。假如线程A登记了信息（上面的信息说锁程A手里），然后被抢占，线程B又登记了信息（上面的信息更新为锁为这个锁已被占有，线程B就会被阻塞起来）。这时一件就发生了，明明锁放程A手里，登记的lock_release()函数实现了锁的V操作。在lock_release()函数中需要传入锁的指针lock。这个函数程持有的。如是，就可以开始做V操作了。首先先将锁的登记信息抹去，然后再通过真正收回锁。其次，可以对这两个操作更换顺序吗？其实也是不能的。我们可以设想下面这种情况。假如线A将锁释放，然后被抢占，线程B这个刚刚释放的锁（当然，线B如愿以偿地获得这把锁），并登记了信息（上面的信息更新为锁程B手里）。然后又被抢占，线程A将锁的登记信息抹去（上面的信息更新锁没有在任何一个线程手里）。这时一件无头案就发生了，明B走了锁，却踏雪无痕、逍list*结构体类型blocked用来说明当前线程正在被哪些线阻塞。这样便于判断线程在何时可以解除阻前线程的优先级大小。举个例子，当前线程优先级为10，拥有两个锁分别是A、B。假如锁A阻塞了10个线程，优2029B塞203059.当前线程优先级要改成什么？很们不可避免要做30次比较，这是效率很低的。因此锁所阻塞的最高优先级线程的优先级变成这个只用做次还有一个变量是structlist_elem构体类型holder_elem。这个变量没什么实际的作用，就是为了方便插入到structthread中structlist结构体类型变量locks准备的。按先进先出FIFO决定插入到阻塞队列中的位置。也就是先阻塞的线程放在队列靠前的位置，后阻塞的线可能在处理另外的锁的时候会得到别的线程让渡到的优先级，这时候sema->waiters里面的线程可能不是有序的了，而我们需要unblock优先级最高那个。因此我们需要先找到最高优先级的线程，然后唤醒那个thread.c里面的，因此我们需要在thread.c写一个函数进行修改，并在thread.h中这个函数，这样在synch.c就可以调用了。但我们不能直接粘贴项目二中的实现代码进入synch.c，否则会出现编译同时，这个低优先级线持有的锁的优先级就会发生改变。为了保证当前线程的成员structlist另外的线阻塞。而这一点我们通过当前线程的成员structlock*blocked就可以很容易判断。要是这需要在外面加入while循环。while循环的条件判断很简单。一是要判断传入的线程指针是否存在，二是而在当前线程已经拿到锁了以后。也就是做完P操作以后，我们也要更新当前线拥有锁的队列。由于多了一old_priority变量，所以thread_set_priority()函数也需要修改，具体有三种情况。第和的优先级比较小，人家本意应该是设置原来的优先级的，所以当前的变量priority不变，只改变变量变量priority。分析很，使用不当还可能导致进程死锁。针对信号量的问题，Dijkstra与1971年提出，为每个共享程）共享资源。这样既便于系统管理共享资源，又能保证互斥和进程间同步。1973年，Hansen和Hoare又把“”的概念发展成为管程（实际上管程也是一个信号量）。行。每个状态变量都是一种实际状态的反映，比如说“需要处理的数据已经送到”、“在过去10秒内用例子，如果是像表示“在过去10秒内用户未敲击过键盘”这种状态的状态变量就可以唤醒所有线程，如果是“需要某个线程处理的某个数据已经送到种状态的状态变量就可能只唤醒那一个线程），那个线多个线程。下图所示为一个带状态变量x，y的管程。类型:structcondition为 中断地）释放lock(管程锁)并被状态变量cond所阻塞直至被其它线程代码（把cond的改变和线程被唤醒并不是原子操作（就是状态变量cond的改变不一定就会唤醒上面的后cond可能会再次改变的情况，这时本来是要阻塞这个线程的，但由于非原子操作这个线程最终还是被唤醒了，这就会出现同步问题。于是在一般情况下，cond_wait()函数的调用者必须重condlock，因此不会马上进入临condlock，因此不会马上进入临醒通过cond_wait()函数所阻塞的最高优先级的线程，并通过测试priority_condvar。在cond_wait()函数中主要做由于某个状态变量的缘故而需要将线程阻塞的阻塞操作。一开始先通过semaphore_elem结构体了一个waiter变量。semaphore_elem结构体同样定义在了这个文件中。从这里可以看到一个semaphore_elem结构体其实就是一个信号量，但是为什么还要这样的一以通过P、V操作来实现。这样的话我们在阻塞时就不需要先拿到线程的指针添加进队列中，然后调用thread_unblock()函数唤醒它。只是需要P、V操作的函数调用就可以了，简洁明了，不易写错。与此同时我们还应该关注一点，那就是由于添加到structcondition构体中的所阻塞线程的链表实现在再来讲回cond_wait()函数，这个函数首先会判断传入参数的合理性，并且需要保证当前调用这个函数的线程（也就是当前cpu运行的线程）必须是当前持有这个管程的管程锁的线程。之前讲过这由于cond_wait()函数的主要任务是将线程阻塞。而我们现在又用信号量来代表线程，因此我们需要给每个线程先分配信号量。而在这里信号量值被初始化为0的就是保证线程执行的先后顺序。在之前的内容中我们举过这样一个例子。现有两个线程A、B。A是父线程B是子线程，A需要B运行完了才能运行。假设先执行了父线A（在父线程中没VP）。通过前边讲P作的特点可知，由于信号量值为0，该线程被阻塞，线程A会继续运行。因此。直到子线B（在子线程是父线程A）在等待资源，则唤醒一个阻塞线程（这里是父线程A），从而保证了父线程A能在子线程B唤醒时，再去获取管程锁（由于已经在lock_acquire()函数中实现了优先级调度，因此如果这个线程的优看到这个函数和cond_wait()函数一样一开始都是判断传入参数的合理性，并且保证当前调用这个函数的线程（也就是当前cpu行的线程）必须是当前持有这个管程的管程锁的线程。接下来的内容还是顺择一个信号量（对应着一个线程）进行V操作，同时删除阻塞队列中的对应项就可以了。的优先级就是线程的优先级。而这和我们之前定义锁的优先级的目的是一样的）。因此我们对structsemaphore这个结构体稍加修改，加上一个sema_priority变量来保存对应的线程的优先级。的初始化值相同，均为PRI_DEFAULT。（cu给s()函数，rry）r对于一个一般用途的调度器来说主要作用在于平衡线程间不同的调度需求。I/O相关的线程会有大量多短CPU期。另一方面，CPU关的线程需要CPU期来完成它们的工作，因此对响应速度不作太多要求。另有些线程介于二者之间，在CPU一会I/OCPU一会，再请求一下I/O。而不同线程间的转换是不同的。因此对于一个好的调度器来说应该可以适应所有情况，即使是所要在任意一个内核线程被CPU完成（也就是说，当我们准备将某个线程A调度进CPU前就要整型变nice。对于不同的线程来nice值可能各不相同，取值范围小至-2020niceCPU间。而与此同时，对于一个nice值为负的线程来说，它会使得自己的优先级升高从而抢夺别的线程的CPU间这两个函数来通过我们这次任务的所有测试。这两个函数定义在threads/thread.c文件中。函数intthread_get_nice返回当前（正在运行的）nice函数:voidthread_set_nice(intnew_nice)pintos程共64优先级（0（PRI_MIN）63（PRI_MAX）），由于每一个优先级都对应一条优先级队列，因此有64条队列。面我们讲过较小的优先级数对应较小的优先级，较大的优先级数对应较大的优先级。因此0最小的优先级63最大的优先级。在多级反馈队列调度中，当其中recent_cpu用的cpu（而且呈正相关关系，至于recent_cpu计算方法在下文中会有讲到），nice为这一线程的nice值。与此同时，由于priority的值必须是整数，因此我们需要将这个值取整（直接去掉小数部分）。而recent_cpu和nice的系 试用例统计出来的结果，并没有太多的数学含义。而且还要注意我们得出的结果必须要在0（PRI_MIN）priority值要降低到PRI_MAX）。进入过（或者相当长一段时间没有进入过）cpu的线程，recent_cpu的值就是0，再加之一个比较小的nice（nice在测试用例中已经规划好了，一般问题不大）可以使得这些没有进过cpu线程能够尽快地进入cpu中。时间做出考量。可以想见，由于我们衡量的是最近一段时间的，因此距现在较近的占用的cpu时间对recent_cpu这个变量造成的影响肯定要大于较长时间以前占用的cpu时间所造成的影响。法是用一个n个元素的数组来最近n秒的cpu时间。然而，由于线程众多，每个线程都需要O(n)空间用于 会随的值变化而变化）， 为当前时刻的值，为衰减 的系数为 的系数为 对应到的值上 的系数趋近于

近 增长 的系数从衰减为