week 10b
CS6640
03/13 2026
https://naizhengtan.github.io/26spring/

□ 1. egos rwfs design
□ 2. intro to concurrency
---

1. egos rwfs (Lab7)

   - a Unix-like fs
    -- with many simplifications
    -- for example, dirs are no deeper than 10

   A) underlying HW

    - logical view of the disk
      -- a block is 512B
      -- total size = 2MB

                        |<-inode arr->|<-data blocks->|
       +-------+--------+-------------+---------------+
       | super | block  |  |  | ...   |  |  | ...     |
       | block | bitmap |  |  |       |  |  |         |
       +-------+--------+-------------+---------------+
    block  0       1     2  3    ...11 12...

    - backed by SD card
      -- qemu simulated SD Card
      -- mkfs.c

    - talk to the disk?
      void block_read(int block_no, void* dst);
      void block_write(int block_no, void* src);

  B) rwfs design

    -- superblock
      [see handout]

    -- block bitmap
      -- tells fs which blocks are free
      -- one bit represents one block

      --QUESTION: what's the maximum size of rwfs?
      [answer: 2MB = 512B * 8 * 512]

    -- inode array
      -- locating files and dirs
      -- 10 blocks: [block#2, block#11]
      -- (local) inode number == index of inode array
      -- the tricky problem: global vs. local inode numbers
         * why Linux doesn't have this problem?
         * no global inode number

      --QUESTION: given sizeof(inode)=64B, 
        how many files (including dirs) do rwfs support?
      [answer: 80 = 10 * (512 / sizeof(inode)) ]

  C) data structures

    -- file and inode

      [see handout]

      -- metadata
        -- mode (see below)
        -- size: file size in bytes

        [see full file metadata: https://pubs.opengroup.org/onlinepubs/7908799/xsh/sysstat.h.html]
        -- uid, gid: user and group of this file
        -- ctime: changed time, time of last status (metadata) change
        -- mtime: modified time, time of last data modification

      -- ptrs
        [draw on board]

      --Question: what's the maximum size of a file?
      [answer:
        number of ptrs = (4KB - 20B) / 4B = 1019
        file size = 1019 * 512B = 509.5KB ~= 0.5MB
      ]

    -- mode
     [see handout]

    file or dir
    |<-   ->|                   |<- S-app ->|<- U-app ->|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+
    | F | D |   |   |   |   |   | R | W | X | R | W | X |
    +---+---+---+---+---+---+---+---+---+---+---+---+---+

      -- R: read
      -- W: write
      -- X: execute

      -- F bit: 0100000 (the 16th bit from right)
      -- D bit: 0040000 (the 15th bit from right)

   -- directory
     -- recall that directory is used to map name to #inode
     -- a pair: <inode, name>

     [see handout]
     [draw on board as well]

   -- page cache

    typedef struct fs_struct {
        ...

        // page caches
        uint buffer_blk_id;
        block_t buffer_cache;
    } fs_t;

    -- inode_t *__load_inode(int ino)
    -- void flush_inode(int ino)


  D) interfaces

    -- void fs_init(inode_intf disk, uint offset_ino);
    -- int  fs_dir_lookup(int dir_ino, const char *path);
    -- int  fs_read(int ino, int offset, int len, char *buf);
    -- int  fs_write(int ino, int offset, int len, const char *buf);
    -- int  fs_getsize(uint ino);

    ** fs_read - read data from a file

      --how? for example, "read(file, buf, len, offset)" (pseudocode)
      [answer:
        1. path walk to find the file's inode
        2. find offset's block
           (all data blocks compose a linear space)
        3. read len bytes
      ]


2. Intro to concurrency

    There are many sources of concurrency.

    --what is concurrency?

        --stuff happening at the same time

    --sources of concurrency

        --on a single CPU, processes/threads can have their instructions
        interleaved (helpful to regard the instructions in multiple
        threads as "happening at the same time")

        --computers have multiple CPUs and common memory, so
        instructions in multiple threads can happen at the same time!

        --interrupts (CPU was doing one thing; now it's doing another)

    --why is concurrency hard?

        *** Hard to reason about all possible interleavings
        *** Source of non-determinism
        *** (deeper reason: human brain is "single-threaded")

   [will continue from here next time]