作業系統

• 英文課名：Operating System
• 永久課號：CSIC30015
• 教師：吳俊峯

課程內容

因為沒上過交大這邊教的大學部 OS，所以不知道跟大學的差別有多少。但是體感上跟清大差不少。清大周志遠教授的 OS 感覺比較想是每個 component 都碰一下，但是這堂比較偏向每個都會教到比較深層的。但可能時間的關係，所以也沒有辦法教很多很深。老師好像是作記憶體的（他下學期還有開一門〈記憶體與儲存系統〉），所以那段講的特別細節和清楚。

TL;DR

從郵局匯款到 Fristrade，綁定約定到入帳最快可能可以四天完成。兩天是綁定的時間，兩天是匯款的時間。郵局這邊的手續費因為活動期間，用行動郵局 App 轉帳只要 168。之後最便宜應該也要 300 + 100。中轉行收 15 USD。

Disk Structure

由磁盤組成，最小儲存單位是 sector，買來就切死的，所以用軟體的 block （多個 sector）來控制。Sector 會有 number，所以可以對特定資料作讀取。

Sectors per Track

• Constant linear velocity ****(CLV)

  • Density of bits per track 是固定的

  • 這樣內圈的資料量就會小於外圈的

  • 但是這樣讀取資料的速度會不固定

    → 讀內圈要轉比較快

  • applications: CD-ROM and DVD-ROM

• Constant angular velocity ****(CAV)
  • keep same rotation speed
  • 內圈 density 比較高
  • 這樣轉速就不用改
  • applications: hard disks

Disk IO

• EIDE, ATA, SATA (Serial ATA), USB, SCSI, etc
• 效能會有差
• I/O bus is controlled by controller

Overview

• 電腦不是在做 I/O 就是在做計算

• I/O devices: tape, HD, mouse, joystick, network card, screen, flash disks, etc

• I/O subsystem: the methods to control all I/O devices

• Two conflicting trends

  • 我們希望他是 interface，這樣才可以 standardization 的控制
  • 但是他又很多樣性

• Device drivers: a uniform device-access interface to the I/O subsystem

  ⇒ Similar to system calls between apps and OS

• Device categories

  • Storage devices: disks, tapes
  • Transmission devices: network cards, modems
  • Human-interface devices: keyboard, screen, mouse
  • Specialized devices: joystick, touchpad

I/O Hardware

• Port: A connection point between I/O devices and the host. 每個 port 都有自己的 ID，那就是 device 對於電腦的 identifier。

  → E.g.: USB ports

• Controller: A collection of electronics that can operate a port, a bus, or a device

  ⇒ A controller could have its own processor, memory, etc. (E.g.: SCSI controller)

• Bus: A set of wires and a well-defined protocol that specifies messages sent over the wires（連接的方式，除了物理相接，還有 protocol 的部分）

  → E.g.: PCI bus

File-System Structure

• 一個 disk 提供的最小單位是 sectors（usually 512 bytes）
• 但是 mapping 的時候不喜歡用 sector，太小了
• 所以都用 Blocks，通常是四到十幾個 sectors
• 一個 OS 可以 support > 1 個 FS type
• 需要兩個 interface
  • 對上：user programs
  • 對下：physical storage (disk)

Layered File System

• 最上層是 API
• 最下層（最終要寫到 disk 上面去的）要透過 driver 寫過去，那 driver 要的是單位是 sector
• Logical file system — 根據 file path 找到 file ID，也要去判斷權限（i.e. 判斷 API 是不是合法可執行的東西）
• File-organization module — 每一個 FS 最不一樣的地方。要找到在 logical 中的位址對應到的 physical 的地方。（甚至需要 map 到不同的電腦）
• Basic File system — 最基本的 I/O 的動作（跟檔案管理無關啦）

• 之所以一個 fread 可以對不同的 file system 作操作就是中間有 FS manager (VFS — Virtual File System)

  

File Concept

File 也是抽像的概念。

• Physical storage unit in disk

  

• File attributes (Metadata)

  • Identifier: non-human-readable name
  • Name
  • Type
  • Location
  • Size
  • Protection
  • Last-access time, Last-updated time

• File operations

  • Create
  • Write
  • Read
  • Repositioning within a file (i.e. file seek)
  • Delete
  • Truncating → 切掉尾巴
  • Appending → 貼在尾巴
    Read more »

Deadlock Characterization

• Example
  • 2 processes and 2 tape drivers
    • 一人各拿一個，然後等對方手上那個
  • 2 processes, and semaphores A & B
    • P1 (hold B, wait A): wait(A), signal(B)
    • P2 (hold A, wait B): wait(B) , signal(A)

Necessary Condition → 一定要全部的條件同時發生

• Mutual exclusion — 資源是沒有共享性的（暫時）

• Hold and Wait — 會 hold resource 然後 wait 別人

• No preemptive — 不能強制別人放開 resource

• Circular wait — 一定會有一個 circular 的 wait。

  \(P_0 \rightarrow P_1 \rightarrow P_1 \rightarrow \dots\rightarrow P_n \rightarrow P_0\)

Background

• 因為有 share 的 data，會被多個 content 去用他，所以需要
• 就算只有一個 core，也會有 Concurrent 的問題（因為會有 content switch）
• 重點就是他們 execute 的 order
• Consumer & Producer Problem

  • 用 counter 去記還有幾個空位

  • Producer

    1 2 3 4 5 6 7

    while (1) { nextItem = getItem( ); while (counter == BUFFER_SIZE); buffer[in] = nextItem; in = (in + 1) % BUFFER_SIZE; counter++; }

  • Consumer

    1 2 3 4 5 6

    while (1) { while (counter == 0) ; item = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; }

  • 但是 counter 會是這兩隻 thread 共用的東東，所以會出現不一致的問題：

    • counter++

      1 2 3

      move ax, counter add ax, 1 move counter, ax

    • counter--

      1 2 3

      move bx, counter sub bx, 1 move counter, bx

    • 但是…如果是這樣呢？（counter initially is 5）

      1 2 3 4 5 6 7 8 9

      producer: move ax, counter // ax = 5 producer: add ax, 1 // ax = 6 context switch consumer: move bx, counter // bx = 5 consumer: sub bx, 1 // bx = 4 context switch producer: move counter, ax // counter = 6 context switch consumer: move counter, bx // counter = 4

      不過如果不是 preemptive 就不會有這個問題了。

Race Condition

• Single processor 的可以用 disable interrupt 或 non-preemptive CPU 來解決。

Basic Concepts

因為 multiprogramming 所以才要 scheduling。

CPU-I/O burst cycle

→ 東西要嘛在 CPU 要嘛在 I/O

• 所以每一個 process 就切成在 CPU burst 和在 I/O burst

• I/O-bound program → 大部分在做 I/O

  ⇒ 不等於 I/O burst 的 cycle 數比 CPU 多（數量應該要是一樣的，因為一個做完接另一個），應該要是一個 burst 要很久。

• CPU-bound program → 大部分在做 CPU

• CPU 大多是短的 burst 很多

  

CPU Scheduler

Ready state → Running state

下面都假設是 single core，只有單一隻程式

網路溝通可以分成兩種主要的 API

• Web Service APIs (e.g. SOAP, JSON-RPC, XML-RPC, REST)
• Web Socket APIs

HTTP

HTTP/2: the difference between HTTP/1.1, benefits and how to use it

REST (REpresentational State Transfer)

→ 幫 HTTP 套規則

• GET → 取得資料
• PUT → 修改資料
• POST → 新增資料
• DELETE → 刪除資料