飞

The  Symposium on Operating Systems Principles  ( SOSP ) Operating Systems Design and Implementation  (OSDI)

Monitor 相当于一个封闭的盒子，Monitor对里面的东西进行监控。 Java的Monitor，类似于Mesa。以前只知道Java里面同不用synchronized，但是其实每一个Object可以被当作Monitor，控制里面所有synchronized 方法，variable。 当有一个process 进入synchronized 函数后，其它的process，都会被block在外。直到，这个process运行完，或者wait，主动退出。buffer 是解释Monitor最好的例子，当一个process，get或者put时，条件不符合，然后主动wait （process 进入一个monitor waiting queue），直到有一个process调用了notify，这时有一个在 waiting queue 里面的waiting process，会醒来。进入while loop再检查一遍条件是否符合，如果符合就继续。 之所以要进入while loop再检查一遍是因为有可能调用的是notifyAll，许多process一起醒来，最先醒来的已经改变了Condition Variable（条件），当另一个process 检查的时候条件已经不符合了。 Mesa Monitor，一个process notify 以后继续执行，其它所有的waiting process都醒来，检查条件，但是只有一个会真正的执行。为了避免starvation（有的waiting process）永远抢不到，时间等的最久的可能会最先执行（增加了scheduling的概念）。Mesa Monitor 优点是，反应速度快，notifying process 不用等，继续执行 Hoare Monitor，的特点是一个process notify以后，条件肯定满足，所以不需要while loop，醒来的process直接执行下一步。 另外Mesa Monitor 有一个invariant，当有process 在monitor里面是为false，其他时候都是true。在wait前和wait return 以后invariant can be assumed，必须是hold，其它时候不能确定。也就是说当要 修改monitor状态的时候invariant 必须hold ，比如修改waiting...

MicroKernel  可以叫做微内核，有人认为传统的monolithic kernel 提供的东西太多，我们可以给内核减负。 最典型的例子就是L4 micro kernel (图中的kernel)只提供最简单的服务，比如IPC (inter process communication), scheduling, address space  剩下的都交给Server 去处理，Server 类似于传统的monolithic kernel 比如Linux, 但是需要改动,L4 把它改为L4Linux. 源代码修改，此外他们还修改了Windows XP (windows 并非完全的不开源，在授权的情况下可以看到源代码). 修改的目的，很简单：以前Server talks to hardware directly, 现在多加了一层 Kernel (L4),它处理所有的hardware interrupt, 然后作为message 传递给server, server 再传递给software. 比如浏览器process 需要一个network packet。 收到packet 以后,L4 作出interrupt,传给Server(比如L4Linux),Server 再与L4,通过IPC 请求packet内容，L4会map到L4Linux的address space，Server 再传给Software(e.g. Firefox).  再比如page fault（由于内存容量有限，有些内容被暂时swap 到硬盘，application 想用的时候发现不在了，就产生page fault） 产生,首先处理interrupt的是Kernel, Kernel sends IPC to L4Linux, L4Linux从自己manage的physical memory 里面分一个page出来，给application,并更新自己的shadow page table(不是真正的page table) .L4Linux 产生一个返回值告诉L4, 已经完成。L4 updates its true hardware page table. Micro Kernel 从设计之初的想法应该是高效的，反映速度快，因为很多东西都由u...

这些系统最初都源于 Bell Lab 的Unix 在"The UNIX Time Sharing System" 有详细描述 Unix 的优势: -从1969年第一个Unix到1974年改进后的 UNIX, 到现在Linux, MacOS, 它最大的优势就是能 在很便宜的机器上运行 ("UNIX can run on hardware costing as little as $40,000",在当时对于计算机应该非常小的数目) -第二重要的特点就是它的易使用性，shell command 简单，易学 特点: 文件系统(File System): -inode (inode 指定文件的block 在硬盘上的具体位置,每个文件夹可以包含每个子文件的初始inode,注意 inode 不是文件名, inode 的数量是有限的，虽然很大，但是还是会用完的. 当寻找一个文件时"/a/b/c.txt"，首先在"/"根目录寻找a，找到后，在"/a/"寻找b，最后寻找c, 这个过程中都是先看文件名，再看inode） -Access control List (Unix 主要使用ACL, 原因是，每个文件都有一个ACL, 当一个用户想要访问这个文件的ACL,如果检查后允许，这个用户就可以做指定的动作。当删除或者添加一个文件的时候，只需要添加，和删除这个文件的ACL，不需要其它操作) -Capabilities （UNIX也有Capabilities, 这个东西好比一个钥匙，可以被传递，通常情况下系统保留一张大的“表”，上面规定哪个用户可以对哪个文件干什么，但是当频繁的添加删除文件时，这个表需要频繁的更新，效率非常低。所以 UNIX不用它。只有一种情况例外，当调用system call open() 的时候 e.g (fd = open(path),'r')），系统会产生一个capability 他就是file discriptor, 这样当每次读写文件的时候就不用check ACL. 

THE, Layers Pro: -easy to debug -easy to verify -modularity abstraction Cons: -may nto be efficient (database may not use filesystem (FS cache),it talks to disk directly),you go the kernel,you introduce overhead -require careful design -ned to avoid circular dependencies The first time to design system, it's easy to use layer design, may be the second time you don't need them. -Synchronization Shared Memory Nucleus -small nucleus for supporting multiple simultaneous OS(user level process) implementation -central abstraction is the concurrent process -synchronization via message passing how is is different from Virtual Machine? -VM wants to virtual hardware, different purpose. Build different flavor of OS (batch, multi-media, real-time). Cons and Pros of message passing -clear, hard to mess up -less efficient Hydra: -Capability(reference to an object, attached to a write, e.x: file discriptor has capability with itself, from the user-point) b...

Goal: Design a system in which mode of operatin could be changed.(This means it will make a general system to support anything) Process: The system only has two layers: Process & Nucleus ( software extension of hardware structure ) -Internal process: Execution of programs in a given storage area -external process: input/output of a given document -process communication (information transfer): message buffering  Each  process has message buffers and message queue.  We know receiver process, but semaphore doen't know who will use that. The disadvantage is also obvious, additional buffers will be used and managed -Scheduling: round-robin -Initially all resources are owned by the basic operating System S Message Passing & Semaphore are two major approaches for IPC. In Semaphore System ，all the resources are EXPOSED , processes have the knowledge of existing resource, but when they try to access them, they may be blocked. In Message Passing Syste...

Definition: Bigtable is a distributed storage system for managing structured data that is designed to scale to a very large size Tablet: Large table broken into tablet at boundary Background: Many Google applications such as web indexing, google earth use BigTable to store data. 这些服务无论从数据大小，or latency requirement 都有很大不同 characteristics: -Simple data model: dynamic control over data layout and format -Data is indexed using row and column names - Bigtable schema parameters let clients dynamically control whether to serve data out of memory or from disk . -Based on GFS to store data and log files Components: -One master server  -library linked into every client  (client communicate directly with tablet for read&write, 和GFS 原理一样) - Dynamically  added tablet server (Used to store table,each tablet server store ten to a thousand tables)