Wednesday, October 2, 2013

Linux Scheduler

See link:

3 Linux Scheduling Policies:
  •  SCHED_OTHER/SCHED_NORMAL Time-based policy with time slices
  • SCHED_FIFO Priority-based policy
  • SCHED_RR Priority-based policy with time slices

Linux scheduler queues:
  •      runqueue
  •      wait_queue or
  •      red-black tree
Linux task states :
  • TASK_RUNNING(runqueue)
  • TASK_INTERRUPTIBLE(wait_queue)
Linux Scheduling Algorithm Evolution :
  • O(N)
  • O(1)
  • Completely Fair Scheduler (CFS)

Threads vs Process on Linux

See the following links:

Thread has its own stack, its own register set/context. User space threads or kernel space threads?
The context of a thread is the register set, including the stack pointer.
Context switch between threads includes saving registers, restore registers only, while MMU context(Page table) & TLB stays.

Process has its own virtual address space, and has at least one thread; all threads within it share the parent process's virtual address space.
The context of a process includes state, priority, signal info, process id, and a pointer to thread.
Context switch between processes needs a switch of virtual address space, including cache and TLB flushing, MMU context switching, and thread switching.

Both thread and process 's creation in user space went to the same system call(clone) in the kernel.
Linux implements 1:1 model.
Keep in mind, TLB and MMU context is per-CPU on Linux.

Tuesday, October 1, 2013

vmlinux vs vmlinuz vs (b)zImage vs uImage

See the wiki link
  • vmlinux -- compiled from source 
  • vmlinuz -- compressed from vmlinux
  • (b)zImage -- final binary image includes: bootloader, uncompress vmlinuz, load vmlinux, ramdisk
  • uImage -- final image for U-boot
  • # readelf -h /boot/vmlinuz-2.6.18-238.el5
    ELF Header:
      Magic:   7f 45 4c 46 02 01 01 ff eb 3d 00 00 00 00 00 00
      Class:                             ELF64
      Data:                              2's complement, little endian
      Version:                           1 (current)
      OS/ABI:                            Standalone App
      ABI Version:                       235
      Type:                              DYN (Shared object file)
      Machine:                           Advanced Micro Devices X86-64
      Version:                           0x1
      Entry point address:               0x100
      Start of program headers:          80 (bytes into file)
      Start of section headers:          0 (bytes into file)
      Flags:                             0x0
      Size of this header:               64 (bytes)
      Size of program headers:           56 (bytes)
      Number of program headers:         2
      Size of section headers:           64 (bytes)
      Number of section headers:         0
      Section header string table index: 0
  • # dd if=uImage of=zImage bs=64 skip=1
    42667+1 records in
    42667+1 records out
  • # hexdump -v uImage.header
    0000000 0527 5619 4713 7f79 2f4d e379 2900 ceaa
    0000010 0000 0000 0000 0000 b9d8 534e 6ab9 e05b
    0000020 a06b ec5b 1885 0898 80f2 6f74 0705 0102
    0000030 694c 756e 2d78 2e32 2e36 3031 6d5f 6c76