trinkle

算法一词在古籍中最早见于周髀算经，对应的algorithm一词来自于波斯数学家al-Khwarizmi ，均以数学语言描述。最早的算法在线性方程组中用到，其中的欧几里得算法为史上第一个算法。算法一词在日常生活中也越来越普遍，究竟什么才可以称为算法呢？我们又可以怎样衡量算法效率呢？

为了满足各种要求，计算机的输入/输出设备种类繁多，功能繁杂，速度不一。操作系统通过I/O子系统对I/O设备进行有效的管理。

计算机的输入设备为信息进入计算机的设备，如键盘，鼠标等，输出设备将计算结果展示给用户，如显示器、打印机、喇叭等。输入/输出设备为计算机与外部交换信息的通道。I/O设备种类繁多，其中各设备速度差距悬殊。操作系统通过I/O子系统来管理I/O设备。

文件系统是操作系统中管理持久性数据的子系统，提供数据存储和访问功能，可以提供组织、检索、读写访问数据功能。在没有文件系统时，我们在计算机上操作的数据无法有效保存，在计算机关机再重启时数据就丢失了。大多数计算机系统都有文件系统，我们常用的谷歌也是一个文件系统，支持分布式应用的数据管理，可以支持系统监控、故障检测、故障容忍和自动恢复，提供很高的可靠性。

由于竞争资源或者通信关系，两个或更多的并发进程各自占有某种资源而又都等待别的进程释放它们所占有的资源的现象称为死锁。这些并发进程循环等待，互不相让，所以形成了死锁的僵持局面，无法向前推进。通信则可以让多个进程进行同步和共享资源。

在之前的lab5中，进程通过读ELF定义全局变量来标识程序的起始位置和信息，从而将程序加载到内存中，从而执行存储在磁盘上的文件读写功能。每次读入数据均从ELF文件中读入显然不现实，所以由操作系统中的文件系统来负责管理和存储可长期保存数据。alb8主要侧重于文件系统的实现，从而实现对文件和目录的一系列操作。

文件系统涉及到的内容比较多，这也是我们称之为文件系统而不是文件子系统的原因吧。

lab6完成了用户进程的调度框架和具体的调度算法，可调度运行多个进程。进程间需要协同操作或访问共享资源，这时候引入了同步互斥问题。本次实验主要是熟悉进程同步机制中的信号量机制，基于信号量机制解决哲学家就餐问题。然后参考信号量机制，实现基于管程的条件变量机制，并给出基于条件变量机制的哲学家就餐问题的解决方案。

在之前我们讨论了并发问题，多线程并发导致资源竞争，可能会引发意想不到的错误所以引入同步来协调多线程对共享数据的访问，任何时刻只能由一个线程执行临界区代码。确保同步正确可以通过底层硬件支持，也可以通过高层次抽象。高层次抽象中比较典型的两种则为信号量和管程。

进程并发执行可提高程序效率，但是并发执行过程是不确定性和不可重现的。在进程间有共享资源，而处理过程并不是整体执行，所以会存在和预期不一致的问题。借助生活中同步问题例子，我们设计了一系列方案并进行改进。

lab5完成了用户进程的管理，可在用户态运行多个进程。但是lab5所采用的调度策略为简单的FIFO策略，未考虑到进程的特征，性能比较差。lab 6对ucore的调度部分进行了修改，设计了系统调度器框架，不涉及具体的调度算法。之后，ucore基于此框架实现了RR调度算法。另外，考虑到进程优先级的问题，又引入了stride调度算法。

执行多任务的计算机必然会涉及到进程切换的问题，进程切换也是CPU当前使用者的切换，下一个使用CPU运行的进程或线程则由处理及调度来完成。与页面置换算法不同，调度策略有不一致的目标比如响应时间、吞吐量、公平性。针对不同目标，设计了不同的调度算法，各有优劣之处，无法兼顾各个指标。