以 Linux 為分析對象

實驗和統計的重要

• [ source ]

• [ source ]

「Process 和 Thread 有什麼差異？」

大部份的學生很快就可以「背誦」作業系統課程給予的「心法」，回答一長串，可是，其中多少人「看過」Process 和 Thread 呢？多少人知道這兩者怎麼實做出來？又，為何當初電腦科學家和工程師會提出這兩個概念呢？

書本說 thread 建立比 process 快，但你知道快多少？是不是每次都會快？然後這兩者的 context switch 成本為何？又，在 SMP 中，是否會得到一致的行為呢？

之前選修課程的學生透過一系列的實驗，藉由統計來「看到」process 與 thread。物理學家如何「看到」微觀的世界呢？當然不是透過顯微鏡，因為整個尺度已經太小了。統計物理學 (statistical physics) 指的是根據物質微觀夠以及微觀粒子相互作用的認知，藉由統計的方法，對大量粒子組成的物理特性和巨觀規律，做出微觀解釋的理論物理分支。今天我們要「看到」context switch, interrupt latency, jitter, … 無一不透過統計學！

• Solving Problems at Google Using Computational Thinking (video)

以 Linux 為分析對象

[ Thread & Synchronization ]

• Shared Code and Reentrancy
  • reentrancy 會造成問題的案例: strtok()
  • 解決辦法: strtok_r()
  • newlib 實做:
    • strtok
    • strtok_r
      • 沒有全域變數
      • 有個工作區，去保存變數

char *
_DEFUN (strtok_r, (s, delim, lasts),
register char *s _AND
register const char *delim _AND
char **lasts)
{
    return __strtok_r (s, delim, lasts, 1);
}

• Use condition variables to atomically block threads until a particular condition is true.

• Always use condition variables together with a mutex lock

• Mutex in Linux: Various implementations for performance/function tradeoffs

• Speed or correctness (deadlock detection)

• lock the same mutex multiple times

• priority-based and priority inversion

• forget to unlock or terminate unexpectedly

• Priority Inversion on Mars

• FUTEX (fast mutex)

• Lightweight and scalable

• In the noncontended case can be acquired/released from userspace without having to enter the kernel.

• invoke sys_futex only when there is a need to use futex queue
• need atomic operations in user space
• race condition: atomic update of unlock and system call are not atomic
• Kernel preemption

• a process running in kernel mode can be replaced by another process while in the middle of a kernel function
• process B may be waked up by a timer and with higher priority
• 考量點: 降低 dispatch latency
• Linux kernel thread

static struct task_struct *tsk;
static int thread_function(void *data)
{
    int time_count = 0;
    do {
        printk(KERN_INFO "thread_function: %d times", ++time_count);
        msleep(1000);
    } while(!kthread_should_stop() && time_count<=30);
    return time_count;
}

static int hello_init(void)
{&nbsp;&nbsp;
    tsk = kthread_run(thread_function, NULL, "mythread%d", 1);&nbsp;&nbsp;
    if (IS_ERR(tsk)) {&nbsp; …. }
}

• Work Queue

• tasklets execute quickly, for a short period of time, and in atomic mode
• workqueue functions may have higher latency but need not be atomic
• Run in the context of a special kernel process (worker thread)
  • more flexibility and workqueue functions can sleep.
  • they are allowed to block (unlike deferred routines)
  • No access to user space
• Atomic Operations
• provide instructions that are:
• executable atomically;
• without interruption
• Not possible for two atomic operations by a single CPU to occur concurrently
• ARM: SWP (早期); LDREX/STREX (ARMv6+) [ source ]
  • support multi-master systems, for example, systems with multiple cores or systems with other bus masters such as a DMA controller.
  • Their primary purpose is to maintain the integrity of shared data structures during inter-master communication by preventing two masters making conflicting accesses at the same time, i.e., synchronization of shared memory.
• Spinlock
• 作用: Ensuring mutual exclusion using a busy-wait lock
  • really only useful in SMP systems
• Spinlock with local CPU interrupt disable

spin_lock_irqsave(&my_spinlock, flags);
/* critical section */
spin_unlock_irqrestore(&my_spinlock, flags);

• Reader/writer spinlock (存在效能議題，近年許多替代方案被提出)

• Semaphore

• blocked thread can be in TASK_UNINTERRUPTIBLE or TASK_INTERRUPTIBLE (by timer or signal)

• 之後探討 real-time Linux 時，這部份會重新分析

• Blocking Mechanism

• ISR can wake up a block kernel thread which is waiting for the arrival of an event

• Wait queue

• wait_for_completion_timeout

  • specify "completion" condition, timeout period, and action at timeout
  • "complete" to wake up thread in wait queue
  • wake-one or wake-many

• Reader/Writer

• 這部份很重要，下個月繼續探討

[ Process Management ]

• Scheduling
  • Find the next suitable process/task to run
• Context switch
  • Store the context of the current process, restore  the context of the next process
• Process context + interrupt context

• Linux kernel is possible to preempt a task at  any point, so long as the kernel does not hold  a lock
• Kernel can be interrupted ≠ kernel is preemptive
  • Non‐preemptive  kernel, interrupt returns to interrupted  process
  • Preemptive kernel, interrupt returns to any schedulable  process
• [ Page 48 - 51 ] Process vs. Thread

• (和作業系統和計算機組織結構的設計有極大的落差)

• Scheduling simulation
  • LinSched: Simulating the Linux Scheduler in user space

• Cheddar project : real-time scheduling analyzer

對照 2015 年選修課程學生的 ARM-Linux 技術報告

• Concurrency in The Linux Kernel

ARM + Multitasking

[ Build A Minimal OS Kernel fork ARM ]

[ STM32 程式開發：以 GNU Toolchain 為例 ]

[ Build minimal ARM Kernel from Scratch ]

• UART 概念
• USART (最詳盡的中文資訊)
  • mini-arm-os 裡面 USART 驅動說明
  • USART interrupt 的行為
  • mini-arm-os 中，改用 PLL 作為 SYSCLK source