Process

process

• fork
• exec

process/task state

• process/task state
  • able to run
    • TASK_RUNNING
  • asleep
    • TASK_INTERRUPTIBLE
    • TASK_UNINTERRUPTIBLE
      • ignore signals

• __set_current_state
  • Changes the process state
  • do { current->state = (state_value); } while (0)

scheduler/process switch

• The Linux Process Scheduler
  • Linux Process Scheduler Improvements in Version 2.6.0
  • O(1) scheduler
    • A closer look at the Linux O(1) scheduler
    • Inside the Linux scheduler
    • Ingo Molnár's scheduler used in versions of the Linux kernel 2.6 prior to 2.6.23 is an O(1) scheduler.
  • Completely Fair Scheduler
    • The scheduler used thereafter 2.6.23 runs in O(log N) time.

• schedule
  • The act of picking the next task to run and switching to it is implemented via the schedule() function.
  • if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) Re: use of PREEMPT_ACTIVE ?
    1. set state to NOT TASK_RUNNING
    2. Preempty happens(maybe interrupt happen and preempt_schedule_irq() is called after interrupt handler terminated) (state != TASK_RUNNING && preempt_count == PREEMPTY_ACTIVE)
    3. put task into wait queue by calling schedule()(state != TASK_RUNNING && preempt_count !=PREEMPTY_ACTIVE)

• switch_to

delay

• ndelay
• udelay
• mdelay

• schedule_timeout
• schedule_timeout_uninterruptible
• schedule_timeout_interruptible
• msleep
• msleep_interruptible
• ssleep

thread

• Linux threading models compared: LinuxThreads and NPTL

• LinuxThreads
  • LinuxThreads Frequently Asked Questions
    • H. Compiling multithreaded code; errno madness
  • _REENTRANT
• NPTL
  • Native POSIX Threads Library (NPTL) Support for uClibc

• POSIX Threads(Pthreads)
  • ANSI/IEEE POSIX 1003.1 - 1995 standard
  • Programming with POSIX(R) Threads
  • Programming POSIX Threads
  • POSIX Threads Programming
  • YoLinux.com Tutorial - POSIX thread (pthread) libraries
  • pthread_sigmask
    • POSIX 线程 – pthread_sigmask

• Multithreaded Programming Guide
  • Chapter 6 Safe and Unsafe Interfaces

concurrency

• Concurrency, Performance, and Architectures in Software Systems

SMP

• Linux SMP HOWTO
• Introduction to Multithreading and Multiprocessing in the FreeBSD SMPng Network Stack
• Locking in OS Kernels for SMP Systems

wait queue head

• typedef struct __wait_queue_head wait_queue_head_t(each wait queue has a head)
  • spinlock_t lock
    • Because wait queues can also be modified in interrupts, a spinlock named lock must be acquired before the queue is manipulated.
  • struct list_head task_list
    • a doubly linked list used to implement what it’s best at queues
  • Declaring Wait Queue Head
    • DECLARE_WAIT_QUEUE_HEAD
    • init_waitqueue_head

wait queue entry

• typedef struct __wait_queue wait_queue_t(elements in the queue)
  • wait_queue_func_t func
    • is invoked to wake the element
  • struct list_head task_list
    • a list element to position wait_queue_t instances in a wait queue
  • initialize
    1. init_waitqueue_entry
  • create
    • DECLARE_WAITQUEUE(name, tsk)
      • wait_queue_t name = __WAITQUEUE_INITIALIZER(name, tsk)
  • create and initialize
    1. DEFINE_WAIT

• flags
  • WQ_FLAG_EXCLUSIVE
    • it is added to the end of the wait queue. Entries without that flag are, instead, added to the beginning.
    • When wake_up is called on a wait queue, it stops after waking the first process that has the WQ_FLAG_EXCLUSIVE flag set.

• add_wait_queue, __add_wait_queue
• remove_wait_queue, __remove_wait_queue

wait/sleep

• prepare_to_wait
  • add your wait queue entry to the queue, and set the process state.
• prepare_to_wait_exclusive
  • sets the "exclusive" flag in the wait queue entry and adds the process to the end of the wait queue.
• finish_wait

• wait_event families
  • wait_event
    • ignores signals
  • wait_event_interruptible
  • wait_event_timeout
  • wait_event_interruptible_timeout
• sleep_on families(it is very easy to accidentally introduce races)
  • sleep_on
  • interruptable_sleep_on
  • sleep_on_timeout

wake up

• remove_wait_queue

• wake_up
  • wake up every process in the queue. The exception is if one has TASK_EXCLUSIVE set, in which case the remainder of the queue will not be woken.
• wake_up_nr
  • awaken up to nr exclusive waiters
• wake_up_all
• wake_up_interruptible
  • restricts itself to processes performing an interruptible sleep
• wake_up_interruptible_nr
• wake_up_interruptible_all
• wake_up_sync
  • What is the purpose of wake_up_sync? Avoid the reschedule_idle() call
  • Why would you want to prevent reschedule_idle()? If one process runs, wakes up another process and knows that it's going to sleep immediately after the wake_up it doesn't need the reschedule_idle: the current cpu will be idle soon, the scheduler doesn't need to find another cpu for the woken up thread.
  • ask to not be scheduled out of the processor at this time
• wake_up_interruptible_sync