Linux0。11kernel目录llrwblk。c详解

　　该模块的作用是处理块设备的读写，其中最重要的函数就是电梯算法addrequest函数和llrwblock函数。addrequeststaticvoidaddrequest（structblkdevstructdev，structrequestreq）
　　该函数的作用是将块设备读写请求插入到电梯队列中。
　　首先将数据的脏数据标志置为0。if（reqbh）reqbhbdirt0；
　　如果当前设备的请求为空，就将入参中的请求作为设备电梯队列的头节点。并且立即调用requestfn。requestfn对于不同的设备对应不同的回调函数，对于硬盘设备而言，requestfn指的是dohdrequest，关于dohdrequest，将在hd。c中进行讲解。if（！（tmpdevcurrentrequest））｛devcurrentrequestreq；sti（）；（devrequestfn）（）；return；｝
　　上面的部分处理了请求队列只有一个请求的场景，接下来便是当请求队列有多个请求时，如何处理优先级顺序的逻辑，也就是电梯算法部分，其中最难理解的便是宏定义INORDER。INORDER的定义如下所示。defineINORDER（s1，s2）（（s1）cmd（s2）cmd（（s1）cmd（s2）cmd（（s1）dev（s2）dev（（s1）dev（s2）dev（s1）sector（s2）sector））））
　　上述代码是比较难懂的，可以使用ifelse来帮助理解boolinorder（requests1，requests2）｛if（s1。cmds2。cmd）｛returntrue；｝elseif（s1。cmds2。cmd）｛if（s1。devs2。dev）｛returntrue；｝elseif（s1。devs2。dev）｛if（s1。sectors2。sector）｛returntrue；｝returnfalse；s1。sectors2。sector｝returnfalse；s1。devs2。dev｝returnfalse；s1。cmds2。cmd｝
　　展开上面的ifelse结构逻辑就清晰了很多，INORDER实际上就是依次对操作类型，设备号，扇区号作比较，并且操作类型优先级大于设备号，设备号优先级大于扇区号。
　　对于操作类型而言，读操作优先级大于写操作。对于设备号而言，设备号小的设备优先级大于设备号大的设备的优先级。对于扇区而言，扇区序号小的扇区优先级高于扇区序号大的扇区。
　　有了这个认识之后，再看下面的语句，就会简单很多，实际上就是根据优先级找到合适的位置插入数据。for（；tmpnext；tmptmpnext）if（（INORDER（tmp，req）！INORDER（tmp，tmpnext））INORDER（req，tmpnext））break；reqnexttmpnext；tmpnextreq；
　　下面的这一段代码可以用两个if语句进行替代，即定向扫描和折返扫描两个场景。if（（INORDER（tmp，req）！INORDER（tmp，tmpnext））INORDER（req，tmpnext））
　　条件1：定向扫描，req在当前扫描的方向上if（tmpreqreqtmpnext）｛reqnexttmpnext；tmpnextreq；｝
　　条件2：折返扫描，req在下一轮扫描的方向上if（tmptmpnextreqtmpnext）｛reqnexttmpnext；tmpnextreq；｝
　　这里需要阐明的是，Linux0。11实际使用的磁盘扫描算法是CSCAN算法，也是电梯算法（可戏称为跳楼机）。
　　其思路就是只单向寻道，到头后直接复位再次沿同方向寻道，这样对于所有磁盘位置的请求都是公平的。
　　我们通过下面的代码实际感受一下这个过程，我们固定cmd和dev，只让sector号有区别，依次插入50，80，60，30，20，看看最后的结果如何。includestdio。hincludestdlib。hdefineREAD0defineWRITE1structrequest｛intdev；1ifnorequestintcmd；READorWRITEinterrors；unsignedlongsector；unsignedlongnrsectors；charbuffer；structtaskstructwaiting；structbufferheadbh；structrequestnext；｝；defineINORDER（s1，s2）（（s1）cmd（s2）cmd（s1）cmd（s2）cmd（（s1）dev（s2）dev（（s1）dev（s2）dev（s1）sector（s2）sector）））作为解析，以明白的分支结构重写一个内容一样的inorder函数boolinorder（structrequests1，structrequests2）｛if（s1cmds2cmd）｛returntrue；onlywhens1cmdREAD；s2cmdWRITE；｝elseif（s1cmds2cmd）｛if（s1devs2dev）｛returntrue；when（s1cmds2cmd）（s1devs2dev）｝elseif（s1devs2dev）｛if（s1sectors2sector）｛returntrue；whenwhen（s1cmds2cmd）（s1sectors2sector）｝returnfalse；whenwhen（s1cmds2cmd）（s1sectors1sector）｝returnfalse；when（s1cmds2cmd）（s1devs2dev）｝returnfalse；whens1cmds2cmd｝voidAddRequest（structrequesthead，structrequestreq）｛if（！head）｛headreq；headnext0；return；｝structrequesttmphead；for（；tmpnext；tmptmpnext）｛if（（INORDER（tmp，req）！INORDER（tmp，tmpnext））INORDER（req，tmpnext））｛break；｝｝reqnexttmpnext；tmpnextreq；return；｝voidPrintQueen（structrequestn）｛while（n）｛printf（（d，d，d），，ncmd，ndev，nsector）；nnnext；｝printf（）；｝intmain（intargc，charargv）｛structrequests1；structrequestpHead0；structrequestreqnewstructrequest；reqcmd0；reqdev0；reqsector50；AddRequest（pHead，req）；PrintQueen（pHead）；structrequestreq3newstructrequest；req3cmd0；req3dev0；req3sector80；AddRequest（pHead，req3）；PrintQueen（pHead）；structrequestreq2newstructrequest；req2cmd0；req2dev0；req2sector60；AddRequest（pHead，req2）；PrintQueen（pHead）；structrequestreq5newstructrequest；req5cmd0；req5dev0；req5sector30；AddRequest（pHead，req5）；PrintQueen（pHead）；structrequestreq4newstructrequest；req4cmd0；req4dev0；req4sector20；AddRequest（pHead，req4）；PrintQueen（pHead）；return0；｝
　　上述代码的执行结果如下所示：（0，0，50），（0，0，50），（0，0，80），（0，0，50），（0，0，60），（0，0，80），（0，0，50），（0，0，60），（0，0，80），（0，0，30），（0，0，50），（0，0，60），（0，0，80），（0，0，20），（0，0，30），
　　可以看出最后的顺序是5060802030，实际上效果就是单方向移动到最后一个位置，再复位进行扫描，再次沿同方向扫描。
　　csan算法示意图
　　makerequeststaticvoidmakerequest（intmajor，intrw，structbufferheadbh）
　　该函数的作用是创建请求项并插入请求队列中。
　　首先判断命令是否READA或者是WRITEA。READA代表预读取，WRITEA代表预写入。所以当命令是预读取或者是预写入，如果bh块被锁，那么就放弃，直接返回。如果bh块没有被锁，那么就当作普通的READ和WRITE。structrequestreq；intrwahead；WRITEAREADAisspecialcaseitisnotreallyneeded，soifthebufferislocked，wejustforgetaboutit，elseitsanormalreadif（（rwahead（rwREADArwWRITEA）））｛if（bhblock）return；if（rwREADA）rwREAD；elserwWRITE；｝
　　如果命令不是读或者写，那么就是一个致命错误，直接通过panic抛出错误。对命令校验之后，就去锁定该数据块。如果命令是写操作，但是该数据块并没有脏数据，则没有必要去写块设备，就可以对bh块进行解锁。除此以外，如果命令是读操作，但是该bh块中的内容已经是最新的，也没有必要去读块设备，就可以对bh块进行解锁。if（rw！READrw！WRITE）panic（Badblockdevcommand，mustbeRWRAWA）；lockbuffer（bh）；if（（rwWRITE！bhbdirt）（rwREADbhbuptodate））｛unlockbuffer（bh）；return；｝
　　下面需要从request数组中寻找一个位置来创建该请求。对于读请求而言，将会从数组的尾部开始搜索。对于写请求而言，将会从数组的23处开始搜索。如果找到了位置，那么就开始进行创建，如果没有找到位置，就sleepon进行等待。if（rwREAD）reqrequestNRREQUEST；elsereqrequest（（NRREQUEST2）3）；findanemptyrequestwhile（reqrequest）if（reqdev0）break；ifnonefound，sleeponnewrequests：checkforrwaheadif（reqrequest）｛if（rwahead）｛unlockbuffer（bh）；return；｝sleepon（waitforrequest）；gotorepeat；｝
　　当找到该位置时，就在该位置上进行构建请求。构建完之后，调用addrequest插入到电梯队列中。filluptherequestinfo，andaddittothequeuereqdevbhbdev；reqcmdrw；reqerrors0；reqsectorbhbblocknr1；reqnrsectors2；reqbufferbhbdata；reqwaitingNULL；reqbhbh；reqnextNULL；addrequest（majorblkdev，req）；llrwblockvoidllrwblock（intrw，structbufferheadbh）
　　该函数的作用就是读写数据块。
　　下面一段代码用于对bh块对应的设备做相应的校验。如果主设备号不存在，或者该设备对应的请求操作函数不存在，就显示出错信息。if（（majorMAJOR（bhbdev））NRBLKDEV！（blkdev〔major〕。requestfn））｛printk（Tryingtoreadnonexistentblockdevicer）；return；｝
　　如果校验没有问题就调用makerequest建立块设备读写请求。makerequest（major，rw，bh）；blkdevinitvoidblkdevinit（void）
　　该函数的作用是初始化块设备。
　　遍历request数组，对request数组中每一项的dev设置为1，对next指针设置为NULL。for（i0；iNRREQUEST；i）｛request〔i〕。dev1；request〔i〕。nextNULL；｝lockbufferstaticinlinevoidlockbuffer（structbufferheadbh）
　　该函数的作用是锁定指定的缓冲块。cli（）；关中断while（bhblock）如果缓冲区已被锁定就睡眠，一直到缓冲区解锁sleepon（bhbwait）；bhblock1；立即锁定缓冲区sti（）；开中断unlockbufferstaticinlinevoidunlockbuffer（structbufferheadbh）
　　该函数的作用是解锁指定的缓冲块。if（！bhblock）如果该缓冲区没有加锁，则打印出错信息printk（llrwblock。c：buffernotlockedr）；bhblock0；对缓冲区解锁wakeup（bhbwait）；唤醒等待该缓冲区的任务。