某储备粮的“学习笔记” - 2011年10月

OS161 System Calls Implementation Notes

2011-10-31T12:38:37+08:00

这篇文章的目的是记录CS350 Assignment2中, 我编写各种System Calls时所采用的思路. 实际coding的时候, 同一种System Call的实现方式很可能不止一种, 但殊途同归.注1: 文章顺序和实际coding顺序并不一定一致, 请参考Assignment中的Strategy部分.注2: 如果没有仔细读过code和Assignment...这里很有些东西你可能读的似懂非懂.欢迎在评论中提问...General Tips 别管写什么function, 第一步永远是检查parameter是否有效!!!(比如, pointer是不是NULL, string是不是空, etc) 不要放过任何一个warning...需要explicit cast的时候, 千万不要偷懒. function一般使用parameter中的pointer进行value return, 正常的return用来return errno. 开始coding之前, 除了读Assignment, 读code, 还要好好读Assignment Hint! 解答了很多FAQ 注意在header file里用#ifndef, 保证header不会出现重复include kmalloc了的东西...在destroy的时候一定要kfree. 不然A3里, 你会发现各种memory leak(Create某些data structure的中间, 如果出现error, 则需要首先free已经allocated的内存, 然后返回error) 善用spl解决mutex问题. 当然, 首先你要明白什么样的操作需要mutex! 我会边写这个Note边添加Tips...Part 1, Play with the files and console在OS161中, 所有应用程序在打开, 关闭, 读取, 写入一个文件的时候, 都是通过一个file descriptor [ID]来标识某一个文件的. 需要注意的是, file descriptor [ID]和vnode是完全两个东西.每个thread都有单独一套file descriptors [ID], 但两个thread的两个不同的file descriptor [ID]如果标识的是同一个文件, 则共用一个vnode.(这里所说的file descriptors实际上只是一个int, 是代表一个file descriptor的ID, 而实际上file descriptor要保存很多内容. 后边继续)简单来说, 我们需要给每一个thread都增加一个, 记录所有opened file的机制. 我们暂称之为file table.file table可以就是个简单的array, 但为了让file table的operation和thread以及syscall相互独立, 减少重复code并减少bug机会, 我强烈建议大家把file table相关的所有operations都写成独立的functions, 放在单独的文件里.file table & file descriptorfile table其实很简单, 一个array外加一个size_t记录array的长度, 就ok了. (这里说的所有array都是struct array, OS161中自带的kernel array lib)file descriptor中需要记录以下几个东西, vnode pointer permission flags the current offset in file probably need something else, depends on your implementation. (like a reference counter, etc.) 然后就是操作file table的各种function, 比如 create file table destroy file table duplicate file table (is one of the most important part of execv fork, but not nessesary for now) add/get/delete a file descriptor may need extra functions or helpers for convenience 至此基本没有难点 (就类似写个小"class").之后要把file table添加到thread里, 并且在thread_fork中进行initialization.Stdin & Stdout 也是FILE!!!这是Assignment在"Implementing file system calls"中特别提到的一点.在建立一个新的process时候, 不止要initialization一个file table, 而且还要把table的0, 1, 2分别设置成standard input, standard output和standard error, 不然printf就不work哦, 哈哈哈.注: OS161中stdout和stderr是一样的.知道了怎么Open, Close就简单了open步骤 1. 创建file descriptor 2. vfs_open打开文件 (获取vnode) 3. 往file descriptor中存需要的数据 4. 把file descriptor加到file table中, 并取得ID 5. return ID给user program如何用vfs_open打开文件, 请参考runprogram.cRead和Write差在细节有file descriptor就有vnode...如何用VOP_READ配合vnode和uio读文件, 请参看loadelf.c注意offset怎么算!!!!!考验你读code读够不够细致的时候到了...好好读vnode.h(的comment)吧.Write和Read差在uio的配置, 和用VOP_WRITE.请细读uio.h(的comment)= =...都是comment有用, code看不懂影响不是很大.Part 2, Get the process organizedfork, getpid, waitpid, _exit...注: 按我的理解, OS161所有的thread都是process, 只不过有parent和child之分.这部分中, PID的管理逻辑是关键, 主要解决几个问题. 如何让一个process wait在一个PID上, 并在exit的时候wake up所有在当前PID waiting的process 如何防止deadlock (P1 wait on P2, and P2 wait on P1) 如何保存exitcode. 并明确, 何时可以安全的删除这个exitcode的记录如何重复使用已经空闲的PID 除此之外, fork还要考虑其他问题, 后边再说. Table解决一切问题...和file descriptor类似, PID也需要构建一个table. 区别在于, process table必须是global的! 也就是说, 整个系统只有一个process table.然后考虑, 我们需要为每个PID/process保存哪些信息, 才能解决上边列举的几个问题.process table相关的function (仅供参考), create process table (use in thread_bootstrap) destroy process table (use in thread_shutdown) assign and save a PID for new process (use in thread_fork) mark a PID as inactive and save the exitcode (use when _exit is called) you may also want to add other things here. Like the actual implementation of waitpid, wakeup waitings, release a exited PID or any other PID related functions. But its all depends on your implementation decision. Wait&Wakeup的钥匙 - A magical memory address第一个Assignment写完, 对于thread_sleep和thread_wakeup应该都很熟悉了.两个function都consume一个pointer作为钥匙. 只要sleep的thread和wakeup的thread用的是同一个钥匙, 睡着的所有thread就能被唤醒.这在implement waitpid和_exit的时候是很实用的.fork意味着, 一模一样这估计是这次Assignment中最难的部分.fork的作用是生成一个和当前thread完全一样的thread. 说具体点就是, CPU的每个register值一模一样 address space中的memory一模一样打开的file一模一样 (duplicate a file table) 其他一个thread中可能包含的部分只有PID不一样!!! fork system call要点: consume一个东西, trapframe. 这里保存着user program进入privilege mode之前, 所有register的数据. 用memcpy把trapframe复制一份给新thread用调用thread_fork的时候, 用复制的trapframe和md_forkentry作为parameter. thread_fork要点: thread_fork要想办法知道, 是不是被fork system call调用的如果是, 需要复制address space 如果是, 需要duplicate file table. 否则, 创建新的 md_forkentry要点: trapframe要复制到kernel stack上 (太简单了以至于有时候想不到用) fork里复制的trapframe要free掉在trapframe里设置return value, (pc貌似也要increment...回忆不起来当时increment的原因了) address space需要activate Follow这些要点, 应该可以比较顺利的搞定fork. 但我仍推荐先把fork和md_forkentry的工作原理搞明白, 再开始.(如果写完了还没明白, 为什么要把md_forkentry pass给thread_fork, 那你绝对是奇葩)到这里, A2中最难的部分过去了...runprogram和execv, 我不确定有没有时间在下周一之前总结出来.这两个大同小异, runprogram写好, execv只是稍微多点东西.exception handling是打酱油...大家加油

关系模型概念整理 (Relational Model)

2011-10-19T08:49:01+08:00

Definition实在不知道怎么概括= =... Intention of a relation: relation definition and constrains Extention of a relation: the actual data, tuples Relation properties Set Theory Attributes has order (not necessary) Value are used to identify tuples Tuples dont have order Tuples cant have duplication Attribute value are atomic Degree: How many attributes in the schema Cardinality: How many tuples in an instance Constraints Let the DBMS to ensure the entry or modification on data are legal Give applications' bug no chance to ruin the data Three Constraint Level Tuple-level Domain restrictions (datatype) Attribute comparisons (好像是指check) Relation-level Special type of keys Superkey: 能uniquely identifies a tuple的一个or一组attribute Candidate key: Superkey的最小集, (最简单的一个or一组attribute) Primary key: 被选中, 用来identity tuples的Candidate key Database-level Referential integrity Foreign key: 其他relation中的primary key Referential integrity: 不允许出现和对应relation中的记录不符的情况 Inclusion dependencies: = =`不懂

数据库基础概念整理

2011-10-19T04:55:14+08:00

Definitions Database: is a large and persistent collection of pieces of information organized in a way that facilitate efficient retrieval and modification. DBMS: is a program that manages details related to storage and access for a database. Schema: is a description of the data interface to the database. Instance: is a database that conforms to a given schema. Transaction: is an application-specified atomic and durable unit of work. View: is a relation in the external schema whose instance is determined by the instances of the relations in the conceptual schema. Trigger: is a procedure executed by the database in response to a change to the database instance Three Level Schema Architecture External schema (view): visualized data Conceptual schema: logical structure Physical schema: file/storage devices Data Independence Application access the data through an abstract data model provided by the DBMS, rather than direct access Physical: applications cant touch the storage stucture Logical: applications cant change the data organization Four Transaction PropertiesNoSQL据说就是要break these properties= =`IDK why... Atomic: once the transaction happens, it happened. No intermediate stage! Consistency: transaction follows the database consitences Isolated: concurrent transactions wont effect each other Durable: transaction results permanently What DBMS do Remoce common code from applications Provide uniform access to data Guarantee data integrity manage concurrent access Protect against system failure Set access policies for data

SQL语法整理

2011-10-17T06:00:15+08:00

SELECTSELECT attribute-expression-list FROM relation-list [ WHERE condition ]; attribute-expression-list: [relation-name.]attribute [relation-name.]attribute [arithmatic computation] AS another name i.e., E.Salary - 40000 AS SalaryDiff CASE WHEN ... THEN ...ELSE ... END i.e., CASE WHEN E.Salary < 40000 THEN 0ELSE E.Salary - 40000 END relation-list: list of table names seperate by comma condition: arithmetic operation +, -, *, / comparisions =, <>, <, <=, >. >= logical connectives AND, OR, NOT attribute IN (Q) attribute NOT IN (Q) attribute op SOME (Q) attribute op ALL (Q) EXISTS (Q) NOT EXISTS (Q) IS [NOT] NULL NULLAND Table AND TRUE FALSE NULL TRUE TRUE FALSE NULL FALSE FALSE FALSE FALSE NULL NULL FALSE NULL OR Table OR TRUE FALSE NULL TRUE TRUE TRUE TRUE FALSE TRUE FALSE NULL NULL TRUE NULL NULL NOT Table NOT TRUE FALSE NULL FALSE TRUE NULL UNION INTERSECT EXCEPT(Q1 and Q2 must have same attribute-list)Q1 UNION Q2 => Together all the tuples in Q1 and Q2Q1 INTERSECT Q2 => Only tuples in both Q1 and Q2Q1 EXCEPT Q2 => Tuples only in Q1 but not in Q2ALL关键字: 允许重复UNION ALL will include twice of duplicate tuplesINTERSECT ALL will include all possible pairs of match tuples, duplication possibleEXCEPT ALL will include all "not in Q2" tuples, duplication possible[INNER]/OUTER JOIN Inner join把两个表连接在一起, 返回两个表中相匹配的记录, 是2和3的交集 Left outer join, 左侧表所有的记录都返回, 右侧匹配的记录返回, 没有匹配的返回Null Right outer join, 与Left outer join相反, 右侧的记录返回, 左侧返回匹配的记录, 没有匹配返回Null Full outer join, 2和3的并集 Cross join, 两个表的笛卡儿积, 返回所有可能的值, 不允许有连接条件 ORDER BYSELECT ... ... ORDER BY attribute [DESC/ASC], attribute [DESC/ASC], ...... Note: 如果没有指定Order, return的数据可能是任意顺序GROUP BY, HAVING, Aggregate expressions{count, sum, avg, min, max} => Aggregate expressionsOrder: Group => Having => Aggregate count(*): number of tuples count(E): number of tupple for which E is non-NULL count(distinct E): number of distinct non-NULL E values sum(E) sum(distinct E) avg(E) avg(distinct E) min(E) max(E) Note: 没有被group by指定的attribute不能出现在SELECT的attr-list中, 除非是aggregateINSERT INTOINSERT INTO relation-name [( attribute-list )] VALUE ( value-list ); DELETEDELETE FROM relation-name [ WHERE condition ]; UPDATEUPDATE relation-name SET attribute-assignment-list [ WHERE condition ]; attribute-assignment-list: pairs of assignment seperate by comma i.e., WorkDept = 'E01', Address = 'Waterloo' CREATE TABLECREATE TABLE relation-name ( attribute-name attribute-type [constraints-list], ... ) attribute-type: http://www.w3school.com.cn/sql/sql_datatypes.aspconstraints-list: (Constraints的格式在各种数据库中都不太一样, 就不列举了) NOT NULL PRIMARY KEY UNIQUE FOREIGN KEY Column or Tuple CHECK CREATE VIEWCREATE VIEW view-name AS ( SELECT ... ) 从View SELECT的方法和table一样CREATE TRIGGERCREATE TRIGGER trigger-name AFTER UPDATE OF attribute-list ON relation-name REFERENCING OLD as instance-name(o) NEW as instance-name(n) FOR EACH ROW ... 不同database语法不一