滴水穿石 - OSDI

2 minute read

以前球隊在回防時, 教練總會說”快跑! 別回頭, 到定點再休息”.
關於人生, 喘息點在哪兒? 我想就在滴水穿石之間!

Week22 (06/02)

讀書心得

OSDI: Memory Management
Kernel space的memory management, 要考慮到的問題, Internal/External fregmentation, physical/logical contiguous, buddy system, slab allocator.
User space的memory管理, page fault handler, Red-Black Tree / AVL Tree.

論文學習

FarmBeats: An IoT Platform for Data-Driven Agriculture PDF ,Slides
FarmBeats這套系統提出了几個解決方法:

  • 遠距傳輸, 以往的解法是用satellite或是手機訊號, 這裡是使用TVWS(TV White Space)以減少硬體成本, TVWS是利用數位電視未使用的頻寬做傳輸, 屬於低頻有傳輸距離長, 穿透力強的優點.
  • 天氣感知系統, 透過OpenWeather API的資料來規劃電量的使用及電池的充電與否.
  • 風力輔助系統, 收集農地的風向及風力數據, 透過飛行演算法(Flight Planning Algorithm)規劃出適當的路線, 減少逆風造成的額外耗電量.
  • 本地影像及資料壓縮, 一般Drone的航空影像(Aerial Imagery)或sensors資料都是直接傳到雲端, 透過Farmbeats的gateway做中繼站並壓縮影像及sensors資料, 可支援1星期的在網路無法使用情況.

Week23 (06/09)

網路文章

When should we use mutex and when should we use semaphore

讀書心得

OSDI: Kernel Synchronization
Race condition and synchronization issues.
Seamphores/mutexes 是用spink locks現實, spink locks是由Atomic oprations來的.
Spin lock速度: spin_lock < spin_lock_irq < spin_lock_iqrsave
Semaphores: 是sleeping locks, 沒有disable kernel preemption, 把自己設為idle讓的task先做, 用在需要等比較久的時間, 在acquire spin lock後不能再acquire semaphore,但hold a semaphore可以再acquire a spin lock.
Mutex: 跟semaphore類似但只count one, semaphore會等所有的locks都release時才會離開sleep, Mutex是較簡單且效能較好的lock機制, 只想知道有沒有人acquire.

論文學習

An Evolutionary Study of Linux Memory Management for Fun and Profit
這份研究分析2009~2015年之間4587筆有關memory management(mm)的patches, Linux版本由v2.6.32.1 ~ v4.0-rc4.
主要的bug fix在: Memory Allocation, Garbage Collection (GC), Virtual Memory Management.
大部份memory leak並不是因為忘了free, 而是錯誤的page fault handling和 free page的計算.
MM較大的問題是很難去track正確的狀態.
常用的data structures: Radix tree, Red-black tree, bitmap, list.
Optimization patches主要有3種: data structure, memory policy, fast path.
Virtual Memory Management是MM裡最大的component, 因為新的硬體及較大的容量, 而存在許多問題.
Memory Resource Controller最大的問題是concurrency的處理.
Memory Allocation主要問題在於checking/lock.
Garbage Collection 透過policy design決定performance的trade-off, 需要一個scalable and coordinated的GC.

Week24 (06/16)

網路文章

Power Causes Brain Damage

Intel Issues End-of-Life Notices for Galileo / Galileo 2, Edison and Joule Boards & Modules
Intel的IoT開發平台負評不少丫.

網路資源

A Candy Dispenser
使用Android Things + Cloud Vision API. Demo

讀書心得

OSDI: Interrupt and Interrupt Handling
Linux 驅動的實現分為3個部份: 註冊(init_module), file operations(API), interrupt handler.
Linux驅動分為3種類型: block device, character device, network device.
以及2種裝置類別: vritual device driver, physical device driver.

Interrupt handling會拆分為2個部份(top/bottom)處理, 減少interrupt disable時間, 讓系統反應更即時. Top Half: 執行時間要短, 中斷是disable的狀態
Bottom Half: 真正在處理中斷資料的地方, 這時可以允許被中斷
Top and Bottom Halves

Linux kernel設計了3種不同的bottom halves: softirq, tasklet, workqueue

  • Softirq用在硬碟, 網路卡, Timer
  • 同個softirq在多核的CPU上是可以同時進行的, 所以concurrency要做好.
  • tasklet是建在softirq之上, 但同一個tasklet無法在多核CPU同時進行.
  • ksoftirqd是softirq daemon.
  • top half把softirq(bottom half)叫起來的, 但有些softirq是自己把自己叫起來(ex:網路卡).
  • Work queues是標準的thread, 可以sleep

Week25 (06/23)

網路文章

Linux Performance
介紹了一些分析工具, 也包括了
BCC - Tools for BPF-based Linux IO analysis, networking, monitoring, and more
perf-tools - Performance analysis tools

網路資源

Stressful Application Test - userspace memory and IO test
壓力測試工具

catapult
Catapult是集合了Trace-viewer, Telemetry, Performance Dashboard, and Systrace的一個專案, 原本是用在Chromium performance analysis, 但也可使用在Android/Linux.

讀書心得

OSDI: Filesystem and Block I/O
從硬碟讀取資料會有2次的memroy copy: HDD DMA -> kernel space buffer -> user space buffer.

File I/O大略可分為2層

  • file system driver: ext4, fat32, NTFS…
  • device driver: Hard Disk, eMMC, USB storage…

Virtual file system 用來做為不同的file system drivers的介面, 管理inode (file)以及inode/dentry cache.
主要的data structure

  • superblock object: 用來表達一個file system
  • inode object: 用來表達一個file及屬性
  • dentry object: 用來表達一個目錄
  • file object: 說明file被誰open及路徑

Week26 (06/30)

網路文章

5 tips for maximizing your lat exercises
Muscle contraction matters.
The longer path of movement means more muscles are conducted. This article points out some mistakes I had done when I was a beginner years ago, and sometimes insufficient movement is because of muscle fatigue. Pilates is a good way for resilience.

讀書心得

OSDI: Network Protocol and NIC Driver
由網路架構可回顧之前所講的整個系統架構

  • Process management: fork, exec, kill, sheduler, spin lock, thread
  • Memory management: free, malloc, GC, Allocator, Virtual Memory
  • Device driver
    • Block devices: File system
    • Character devices: Keyboard, Mouse, Graphic card
    • Network devices: net devices

Socket操作行為很像file的操作.
網路通訊協定7層在實作時並沒有上下關係, 只是表達每一層該做的事, ARP可能在user space, HTTP可能在kernel.

kernel統一透過socketcall來處理socket連線, 第一個參數為要執行的動作(action)

SDU vs PDU
SDU(service data unit): OSI model中要傳送給下一層的資料.
PDU(protocol data unit): OSI model中要由上層傳送過來的資料.

Socket Buffer: 網路封包在傳送過程中, 在不同的層級會被加入不同的header或checksum(padding), 這個過程會造成多次的memory copy, socket buffer是為了加速及減少memory copy的overhead.
Socket buffer是用來描述封包的meta data(data structure).

NAPI(New API): 隨著網路的發展, network device(網卡)要處理的資料量越來越大(100Mbps/1Gbps/10Gbps), 這代表CPU要處理的interrupt變多並造成livelock.
NAPI需要硬體支援, 是為了降低CPU處理interrupt的量, 結合interrupt及polling的設計, 當interrupt超過一定的量會disable interrupt改為polling處理網路封包.
缺點: 某些case會有額外的IRQ latency. 有些硬體設計IRQ masking是較慢的, 頻繁的操作會影響系統.

New API

Leave a Comment