文件系统的存储视图：SuperBlock, inode, dir_entry, data block。
文件数据块的分配方式：① 连续分配（高效的顺序和随机读访问；频繁分配会带来碎片；增加文件内容开销大） ② 链式分配（创建、增大、缩小很容易；几乎没有碎片；随机访问效率低，可靠性差；分为显式链接和隐式链接，前者显式建立常驻内存的文件分配表 FAT 记录盘块的先后关系，隐式则是盘块中记录下一个盘块的指针） ③ 索引分配（创建、增大、缩小很容易；几乎没有碎片；支持直接访问；当文件很小时，存储索引的开销相对大）
为了处理大文件，引入链式索引 / 多级索引的索引分配方式。
每次读数据需要 Read Inode, Read Data, Write Inode
如果需要创建一个新的 Inode / Data block，则需要对对应的 bitmap 先 R 后 W，创建新文件需要 write 新文件的 inode，父目录的 inode 和父目录的 data block。对文件写入则需要 R Inode，W 数据块，W Inode。
/* resource.P() is equivalent to wait(resource) resource.V() is equivalent to signal(resource) rmutex.P() is equivalent to wait(rmutex) rmutex.V() is equivalent to signal(rmutex) */
writer() { resource.P(); //Lock the shared file for a writer
<CRITICAL Section> // Writing is done
<EXIT Section> resource.V(); //Release the shared file for use by other readers. Writers are allowed if there are no readers requesting it. }
reader() { rmutex.P(); //Ensure that no other reader can execute the <Entry> section while you are in it <CRITICAL Section> readcount++; //Indicate that you are a reader trying to enter the Critical Section if (readcount == 1) //Checks if you are the first reader trying to enter CS resource.P(); //If you are the first reader, lock the resource from writers. Resource stays reserved for subsequent readers <EXIT CRITICAL Section> rmutex.V(); //Release
// Do the Reading
rmutex.P(); //Ensure that no other reader can execute the <Exit> section while you are in it <CRITICAL Section> readcount--; //Indicate that you no longer need the shared resource. One fewer reader if (readcount == 0) //Checks if you are the last (only) reader who is reading the shared file resource.V(); //If you are last reader, then you can unlock the resource. This makes it available to writers. <EXIT CRITICAL Section> rmutex.V(); //Release }
int readcount, writecount; //(initial value = 0) semaphore rmutex, wmutex, readTry, resource; //(initial value = 1)
//READER reader() { <ENTRY Section> readTry.P(); //Indicate a reader is trying to enter rmutex.P(); //lock entry section to avoid race condition with other readers readcount++; //report yourself as a reader if (readcount == 1) //checks if you are first reader resource.P(); //if you are first reader, lock the resource rmutex.V(); //release entry section for other readers readTry.V(); //indicate you are done trying to access the resource
<CRITICAL Section> //reading is performed
<EXIT Section> rmutex.P(); //reserve exit section - avoids race condition with readers readcount--; //indicate you're leaving if (readcount == 0) //checks if you are last reader leaving resource.V(); //if last, you must release the locked resource rmutex.V(); //release exit section for other readers }
//WRITER writer() { <ENTRY Section> wmutex.P(); //reserve entry section for writers - avoids race conditions writecount++; //report yourself as a writer entering if (writecount == 1) //checks if you're first writer readTry.P(); //if you're first, then you must lock the readers out. Prevent them from trying to enter CS wmutex.V(); //release entry section resource.P(); //reserve the resource for yourself - prevents other writers from simultaneously editing the shared resource <CRITICAL Section> //writing is performed resource.V(); //release file
<EXIT Section> wmutex.P(); //reserve exit section writecount--; //indicate you're leaving if (writecount == 0) //checks if you're the last writer readTry.V(); //if you're last writer, you must unlock the readers. Allows them to try enter CS for reading wmutex.V(); //release exit section }
int readcount; // init to 0; number of readers currently accessing resource
// all semaphores initialised to 1 semaphore resource; // controls access (read/write) to the resource. Binary semaphore. semaphore rmutex; // for syncing changes to shared variable readcount semaphore serviceQueue; // FAIRNESS: preserves ordering of requests (signaling must be FIFO)
//READER reader() { <ENTRY Section> serviceQueue.P(); // wait in line to be serviced rmutex.P(); // request exclusive access to readcount readcount++; // update count of active readers if (readcount == 1) // if I am the first reader resource.P(); // request resource access for readers (writers blocked) serviceQueue.V(); // let next in line be serviced rmutex.V(); // release access to readcount <CRITICAL Section> //reading is performed <EXIT Section> rmutex.P(); // request exclusive access to readcount readcount--; // update count of active readers if (readcount == 0) // if there are no readers left resource.V(); // release resource access for all rmutex.V(); // release access to readcount }
//WRITER writer() { <ENTRY Section> serviceQueue.P(); // wait in line to be serviced resource.P(); // request exclusive access to resource serviceQueue.V(); // let next in line be serviced <CRITICAL Section> // writing is performed <EXIT Section> resource.V(); // release resource access for next reader/writer }
