Advance I/O#

Blocking / Non-blocking I/O#

根據上一章提到的 I/O model 中，當我們在做操作的時候，有可能會遇到

1. Data not ready，可能還在 disk 上
2. Buffer full，沒地方寫了

Blocking 與 Non-blocking mode 是 I/O 一個處理這種問題的 property

• Blocking: 一個 I/O system call 必須要執行完畢所有的操作才能 return（e.g., write() 必須把所有 data 都寫入才 return），在這期間不保證一直在 CPU 上，有可能會被 context switch 出去
• Non-blocking: 不論做了多少事情，遇到 data not ready 或 buffer full 也不會等，會立即 return -1，並且把 errno 設為 EAGAIN 或 EWOULDBLOCK

如果我們開 non-blocking mode 一次要 100 個 bytes（read(fd, buf, 100)），假設 buffer cache 裡面有 30 個 bytes，第一次 OS 會先把在 buffer cache 裡面的給你，然後 read() 會立即 return，但 OS 還是會默默搜集剩下的 bytes 到 buffer cache 裡面，你再次 call read() 就會有資料了

一個普通的 process system call by default 是 Blocking mode，System 比較喜歡 blocking mode，因為可以被踢出 CPU 讓 OS 做 performance optimization，Non-blocking mode 的最大目的則是為了避免被踢出 CPU

Non-blocking#

Slow System call#

在 System call 裡面有一些可能會導致 forever block，我們就會稱他為 Slow system calls

• read() operation 在一些 data 還沒準備好的 file 上（如 pipe, terminal, network socket）會導致 forever block
• write() operation 在一些 buffer 已經滿了的 file 上（如 pipe, network flow control）會導致 forever block
• 對一個沒有 readers 的 FIFO 做 O_WRONLY 的 open()
• 對一個正在等 user input 的 terminal 做 read()
• ioctl()
• 一些 IPC system call

面對這些 system call 我們不可能使用 blocking mode，因為他會 forever block，所以我們通常會用 non-blocking mode 來對這些 device 做 I/O，我們可以在 open() 的時候直接指定 O_NONBLOCK flag，或是之後用 fcntl() 把它改成 non-blocking mode

non-blocking mode for a file

雖然 Disk I/O 是很慢，但我們並不會把它歸類為 slow system call，因為它不會 forever block

通常我們會用以下方法來改變 file status flags

• val | flags: turn on flags
• val &= ~flags: clear the flag

#include "apue.h"
#include <fcntl.h>

void set_fl(int fd, int flags) 
/* flags are file status flags to turn on */
{
    int val;

    if ((val = fcntl(fd, F_GETFL, 0)) < 0)
        。err_sys("fcntl F_GETFL error");

    val |= flags;       /* turn on flags */

    if (fcntl(fd, F_SETFL, val) < 0) 
        err_sys("fcntl F_SETFL error");
}

以下是一個 non-blocking 的範例程式，不斷不斷讀取直到全部讀完

#include "apue.h"
#include <errno.h>
#include <fcntl.h>

char buf[500000];

int main(void) {
  int   ntowrite, nwrite;
  char  *ptr;

  ntowrite = read(STDIN_FILENO, buf, sizeof(buf));
  fprintf(stderr, "read %d bytes\n", ntowrite);
  
  set_fl(STDOUT_FILENO, O_NONBLOCK); /* set nonblocking */
  
  ptr = buf;
  while (ntowrite > 0) {
    errno = 0;
    nwrite = write(STDOUT_FILENO, ptr, ntowrite);
    fprintf(stderr, "nwrite = %d, errno = %d\n", nwrite, errno);

    if (nwrite > 0) {
      ptr += nwrite;
      ntowrite -= nwrite;
    }
  }

  clr_fl(STDOUT_FILENO, O_NONBLOCK); /* clear nonblocking */
  
  exit(0);
}

Terminal Device#

Terminal Device 的 buffer 會是 circular buffer，意思是我們只會使用一段固定長度的 buffer，在 blocking mode 下，當 buffer 滿了以後就要先 block 住，等待 read() 把 buffer 裡面的資料讀走，才會有空間可以寫入新的資料

• 當 Process 發現 readptr == writeptr 就代表 buffer 滿了

要有 Buffer 的原因是因為，Input, Output 的速度差太多了

• input 是 memory to memory 快
• output 是 memory to I/O 慢

看看以下這張圖，當我們在 terminal 上打字的時候，OS 會先把我們打的字放在 buffer 裡面，等到我們按下 Enter 的時候才會把 buffer 裡面的資料送到 process 裡面去，這樣就不會因為我們打字太快而來不及處理了

Terminal Circular Buffer

Terminal 有一個特別的機制是我們打字可以非常快速的顯示在螢幕上，這是因為我們可以開啟 echo，在我們用鍵盤（Device）輸入的時候，OS 會把這份資料複製，同時放到 input queue 跟 output queue，termial 的 process 就可以從 input queue 讀取資料，Terminal 的 I/O process 則會從 output queue 讀取資料

Terminal 有時候會關掉 Echo，像是我們打 sudo 的時候，OS 就會關掉 Echo，這樣我們打的密碼就不會顯示在螢幕上了

I/O Multiplexing#

有兩個理由讓我們使用 I/O Multiplexing

1. 當我們想讓 terminal I/O 這種 slow system call 變成 non-blocking 的時候，我們會需要不停的去 query，看看 data 是不是 ready 了，這樣就會浪費很多 CPU cycles
2. 當我們有多個 thread 或 process 都需要用到 I/O，如果我們一直 query 就會造成 IPC 的 overhead，會有 performance 問題

I/O Multiplexing 的 idea 就是說，我們可以一次性地告訴 OS 我們對哪些 fd 需要做管理，當這些 fd 裡面有任何一個變成 ready 的時候，OS 就會通知我們，這樣我們就不需要一直 query 了，Unix 提供了兩個 system call 來做 I/O Multiplexing，分別是 select() 跟 poll()

I/O Multiplexing system call#

select()#

int select(int maxfdp1, fd_set *restrict readfds,
           fd_set *restrict writefds, fd_set *restrict exceptfds,
           struct timeval *restrict tvptr);

使用方法通常是

totalFds = select(nfds, readfds, writefds, errorfds, timeout)

• nfds 代表有多少 fd
• readfds 有興趣要 read 的 fd，用 bits string 代表，有興設定為 1
• writefds 有興趣要 write 的 fd，，用 bits string 代表，有興設定為 1

為了 Portability，readfds, writefds 的 type 是 fd_set，這樣就不用管 System 的實作細節了，Unix 會幫我們把它轉成 bits string

Illustration of select()

呼叫 select() 後，system 就會去看前面 4 個 fd，後面的就不用幫忙看，當有 partial ready 後，就會 return 一個 totalFds（幾個 ready 了），所以 readfds, writefds 同時會被當作輸入也會被當作輸出

poll()#

int poll(struct pollfd *fdarray, nfds_t nfds, int timeout);

• nfds: the number of items in the fds array
• timeout: how long to wait before un-suspending the process
  • -1: wait forever, 0: don’t wait: >0: wait (milliseconds)

slect() 太複雜了，而且只能用 bits string 來代表 fd，這樣就會有 fd 數量的限制（通常是 1024），所以 poll() 就被提出來了，poll() 用陣列的方式來代表 fd，並且如果要設定一個很大的 fd，用 select() 非常不直觀，而且 select() 沒辦法得知你原始設定的 bitmask，因為輸入輸出是同一個

totalFds = poll(fdarray[], nfds, timeout)

以下是 pollfd 的 struct 定義：

struct pollfd {
    int   fd;       /* file descriptor to check, or <0 to ignore */
    short events;   /* bit mask: each bit indicates an event of interest on fd */
    short revents;  /* bit mask: each bit indicates an event that occurred on fd */
}

這裡的 events，不只 select() 的三種

• POLLIN 代表 data ready to read
• POLLOUT 代表 data ready to write
• POLLERR 代表 error occurred
• POLLHUP 代表 hang up occurred
• POLLPRI 代表 priority data ready to read

select(), poll() 呼叫後會等待直到 return ，期間會 context switch 去其他地方，select(), poll() 實務上，我們會把它做成 atomic 的 pselect(), ppoll()，防止 signal 來打斷它，因為 signal 可能會導致 select(), poll() return，依然是 TOCTTOU 問題

select() return 跟 read() 中間會有一個 gap，我們會把它的 fd 改成 non-blocking mode，不然資料可能被別的 blocking I/O 讀走

File Lock#

當有兩個 process 想要同時 write() 一個 file 的時候，一會出問題，以下是個例子

• 從 fd 讀出存款到 int_var 裡面，假設本來有 1000，藍色 program 先讀到 1000，然後被 context switch 出去，紅色 program 讀到 1000，然後做 int_var -= 200，然後寫回 fd，這時候藍色 program 又被 context switch 回來，做 int_var -= 200，照理來說兩次提領應該要剩 600，但因為藍色 program 讀到的 int_var 是 1000，所以最後寫回去的還是 800，這樣就會有 race condition 問題了

Race condition on two processes writing a file

因此我們就會需要 file lock 來解決這個問題，File lock 的概念就是說，當一個 process 在 write() 一個 file 的時候，OS 會幫他把這個 file lock 住，其他 process 就不能對這個 file 做任何操作了，直到這個 process 把 lock 解掉了以後，其他 process 才能對這個 file 做操作

• 只要有 process 在 write() File 就會被 lock 住，多個 process 會搶一個 file
• 是否上鎖是 Unix 決定的，因為只有 System 知道其他人有沒有在讀寫，如果不行鎖，就等到可以鎖（blocking）或 context switch 走（nonblocking）

Type of Lock#

Lock 除了 write() 以外，還有 read() 也可以上 lock，我們可以根據 lock 的性質用以下的表格來分類

The type of lock

• Shared read lock
  • 可以多 process 共享
  • 但上了 read lock 就不能上 write lock
• Exclusive write lock
  • 只有一個 process 可以 lock
  • 上了 write lock 就不能上 read lock

實務上我們要 read() 即使可以上 read lock 也不一定會上，因為 lock 之間有 exclusive 的性質，如果有 process 需要 write() 那他必須得上 write lock，但上 write lock 的前置條件是，而 read lock unlock 要等所有人 unlock 有公平性問題

System Call of File Lock#

以下幾個 System call 都可以用來做 file lock

• flock(): 鎖住整個 file，不推
• fcntl()
• lockf(): 也是 fcntl() 的 implementation 不推

Record Locking fcntl()#

int fcntl(int fd, int cmd, ... /* struct flock *flockptr */);

• 用 F_GETLK: query, F_SETLK: lock 兩個 flag 控制 lock 的行為

lock 的時候不必先做 F_GETLK，直接 lock，因為 context switch 出去會出現狀態改變，反而會出現 TOCTTOU 問題，Unix 採用 Advisory Lock (後續會提到)

struct flock {
  short l_type;   /* F_RDLCK, F_WRLCK, or F_UNLCK */
  off_t l_start;  /* offset in bytes, relative to l_whence */
  short l_whence; /* SEEK_SET, SEEK_CUR, or SEEK_END */
  off_t l_len;    /* length, in bytes; 0 means lock to EOF */
  pid_t l_pid;    /* returned with F_GETLK */
}

• l_type 代表 lock 的類型，F_RDLCK (a shared read lock), F_WRLCK (an exclusive write lock), or F_UNLCK (unlocking a region)

同一隻 file 被 read lock 又想上 write lock，OS 是不會擋住的，OS 認為是 programmer 的責任

看下下面的圖片（FreeBSD System），我們可以知道，lock 與 fd 無關，而是跟 process, file 有關

• 所有共享 file 的 fd 都可以去關掉他，file close, process terminated lock 都會被 release
• lock 無法繼承，舉個例子 write lock 是 exclusive 的，不可能被繼承

Process Structure and Lock in FreeBSD

因為 lock structure 記錄的是 process，他只認 process 所以只要是從正確的 process 來的 release request 就可以把 lock release 掉，下面兩個 code 為例

fd1 = open(pathname, ...);
read_lock(fd1, ...);
fd2 = dup(fd1);
close(fd2);

• 根據圖片，他會被關掉

fd1 = open(pathname, ...);
read_lock(fd1, ...);
fd2 = open(pathname, ...);
close(fd2);

• 根據圖片，即便它有重新開了一個 open file table，但 lock 是紀錄 process id，並且 i-node 是同一個，所以 lock 也會被 release 掉

Advisory vs. Mandatory lock#

Advisory lock#

有些 process 可能會不去 F_GETLK, F_SETLK，直接 call write()，意思是這個 lock 只是一個建議性的 lock，不一定要 call fcntl() 像是左下角的 process，就可以 access file，但因為 Unix 本身就有 account 和 permission 的機制，其他人根本對 file 並沒有 permission，只有自己動得了自己的檔案

Advisory lock

Mandatory lock#

所有 system call 都要先透過 kernel 去檢查 lock 的狀態，才可以 access file，也只有 kernel 才有權限碰到 lock，所有 process 都只能提出 request

Mandatory lock

在現代的系統裡，Mandatory lock 很少被使用，因為它會造成很多 overhead，而且也不容易 debug，Advisory lock 只要大家都遵守規則就可以了

Networking Device#

也是一種 slow system call，因為網路的速度比 memory 還慢很多，通常我們會用 non-blocking mode 來做 I/O，並且使用 I/O Multiplexing 來避免一直 query，詳見 NTU-CN 計算機網路筆記 ↗

Client Server model#

• Client: 提出 request
• Server: 處理 request

是在網路的一種處理資料的 model，通常會有一個 server 在等待 client 的 request，當 client 提出 request 後，server 會處理 request 並且回傳 response 給 client

Client Server model

Socket#

Socket 是一個抽象的概念，代表一個 endpoint，可以用來做網路的 I/O，通常會有兩個 socket，一個在 client 端，一個在 server 端，兩個 socket 之間可以透過網路傳輸資料，就好像是一個 pipe 一樣，client 端的 socket 可以用來 send request，server 端的 socket 可以用來 receive request，我們也可以把它比作一種 IPC 只不過是跨 device 的 IPC，因為它是透過網路來傳輸資料的

Networking Stack