Skip to content

Process

Process Concept

Process：a unit of resource allocation and protection

  • program - 静态的，存在 disk 里的 byte
  • 一个程序运行一次（loaded in memory）产生一个进程

  • Process = code + data section +（静态）

    pc + stack + heap（动态）

  • stack 高地址，heap 低地址

一个简单的 C 程序的 memory layout

alt text

stack frame 中有什么

  • 调用函数传递的参数
  • 函数的局部变量
  • 返回地址
  • 返回值

call sequence 越长，stack 越大 -> runtime stack overflow（尤其是递归调用时

由同一程序产生的两个进程：

alt text

以前 OS 只能一次运行一个进程，现在可以运行多个

Process Control Block

PCB, also called task control block

  • PCB 与 Process 是一对一的关系
  • PCB 在 Process 创建时被分配，在终止时被销毁
  • 一般有下面这些内容：
    • Process state – running, waiting, etc
    • Program counter – location of instruction to next execute
    • CPU registers – contents of all process-centric registers
    • CPU scheduling information- priorities, scheduling queue pointers
    • Memory-management information – memory allocated to the process
    • Accounting information – CPU used, clock time elapsed since start, time limits
    • I/O status information – I/O devices allocated to process, list of open files

task_struct - linux 的 PCB

Process State

  • new - The process is being created
  • ready - The process is waiting to be assigned to a processor
  • running - Instructions are being executed
  • waiting - The process is waiting for some events to occur
  • terminated - The process has finished execution

alt text

Process Creation

alt text

  • 父亲可以继续执行，也可以等待孩子执行完毕
  • 孩子可以是父亲的克隆，也可以完全是新的程序

fork

  • fork() - create a new process
  • 产生一个子程序
  • 子程序从 fork() 后开始执行（return from fork）
  • return new_pid to parent, return 0 to children
  • 子程序现有的资源为 0

为什么 fork 能返回两个值 - 有两个 user space 的 context

Process Termination

  • A process terminates itself with the exit() system call
  • All resources of a process are deallocated by the OS
  • A process can cause the termination of another process - use signal 和 kill()

execve() system call used after a fork() to replace the process’ memory space with a new program

example
if (fork() == 0) { // run ls
    char *const argv[] = {"ls", "-l", "/tmp/", NULL};
    execv("/bin/ls", argv);
}// 把后续程序替换成 ls

wait()

  • blocks until any child completes
  • returns the pid of the completed child and the child’s exit code

waitpid()

  • blocks until a specific child completes
  • can be made non-blocking with WNOHANG options

alt text

Process and Signal

  • A process can receive signals, i.e., software interrupts（异步
  • signal 的作用 - 程序同步
  • os 定义 signal 的名字和对应的数字
  • signal 的例子
    • 键盘 ^C on the command-line sends a SIGINT signal to the running
    • A segmentation violation sends a SIGBUS signal to the running process
    • A process sends a SIGKILL signal to another

Manipulating Signals

  • Each signal causes a default behavior in the process
    • 比如 SIGINT signal causes the process to terminate
  • 为安全考虑，一些 signal 不能由用户写 handler
    • SIGKILL and SIGSTOP 
signal(SIGINT, SIG_IGN); // ignore signal
signal(SIGINT, SIG_DFL); // set behavior to default
signal(SIGINT, my_handler); // customize behavior

//handler is as:  
void my_handler(int sig) { ... }

zombie - 自己死了父母没死

  • terminate
  • 因为父母可能需要子进程的 exit code，所以 os 还没 collect garbage（会占用 memory
  • PCB 不能被回收
  • 在下面两种情况下被回收
    • parents called wait()
    • parents died
  • When a child exits, a SIGCHLD signal is sent to the parent
  • 避免 zombie：
    • The parent associates a handler to SIGCHLD
    • The handler calls wait()
    • This way all children deaths are “acknowledged”

orphans - 父母死了自己没死，

  • 会被 pid=1 的父进程领养
    • init on a Linux system
    • launchd on a Mac OS X system
  • The process with pid 1 does handle child termination with a handler for SIGCHLD that calls wait
  • 因此，orphan 不会变成 zombie
  • “Trick” to fork a process that’s completely separate from the parent (with no future responsibilities): create a grandchild and “kill” its parent

Child becomes zombie, parent needs to handle child exit properly

Process Scheduling

  • Process scheduler selects among ready processes for next execution on CPU core
  • ready queue - set of all processes residing in main memory, ready and waiting to execute
  • wait queue - set of processes waiting for an event (i.e. I/O)
  • 链表数据结构 alt text

Context Switch

alt text

  • Context - 寄存器的内容
  • 发生在特权模式
  • 起作用的位置 - context_switch, more specifically, in cpu_switch_to
  • 存到哪 - PCB, more specifically, in cpu_context

alt text

arm 架构的代码

PC、stack 都改变，因此进程改变

  • cpu_switch_to() Return to the caller of cpu_switch_to -> eventually to schedule()

程序栈的两个 PC

  • low address - kernel space 的 pc
  • high address - user space 的 pc

Code through

  • 每个 Task 需要 Task struct（3KB）
  • 之前有规定 NR_Tasks - Task 的最大数量
    • 这样需要用的时候遍历一遍表即可
  • 后来变为动态（仍受内存限制）

CPU Scheduling

Definition - 决定下一个运行哪个进程，运行多久

  • 对 CPU 的利用很重要
  • The mechanism is the dispatcher

CPU-I/O Burst Cycle

  • I/O bound - 总是在等 I/O
  • CPU bound - 总是在用 CPU，很少 I/O

Non-preemtive scheduling - 非抢占式，跑到不想跑（Running to Ready 不会发生）

  • Also called “cooperative” scheduling

Preemtive scheduling - 抢占式

  • 不需要进程自愿放弃
  • 操作系统操控
  • 复杂，需要考虑很多 process synchronization 的问题
    • 访问共享数据
    • kernel mode 抢占
    • 操作系统在执行重要操作时发生抢占

可能发生的 Scheduling Decision：

alt text

Scheduling 的目标

  • Maximize CPU Utilization - CPU 不处在空闲状态的比例
  • Maximize Throughput - “useful work” done per time unit
  • Minimize Turnaround Time - Time from process creation to process completion
  • Minimize Waiting Time - time a process spends in the READY state
  • Minimize Response Time - Time from process creation until the “first response” is received

Scheduling queues

  • 链表实现
  • Ready Queue contains processes that are in the READY state
  • Device Queues contain processes waiting for particular devicesalt text

Dispatcher latency

  • Dispatcher module
    • switching to kernel mode
    • switching context
    • switching to user mode
    • jumping to the proper location in the user program to restart that program
  • Dispatch latency – time it takes for the dispatcher to stop one process and start another to runalt text

Scheduling Algorithms

一共六种

必考一道大题

First-Come, First-Served Scheduling

  • 先来的先执行
  • Gantt chart alt text
  • waiting time = start time - Arrivel time
    • 上图的例子：Average waiting time: (6 + 0 + 3)/3 = 3
  • Turnaround time = finish time – arrival time
    • Average turnaround time: (30 + 3 + 6)/3 = 13
  • 如果 P1 先来，上面两个时间都会大幅度提高 - Convoy effect

Shortest-Job-First Scheduling

  • SJF - 最优 for average wait time
  • 抢占式比非抢占式优
  • Preemptive - shortest-remaining-time-first (SRPT)
    • 此时 waiting time = finish time – arrival time - burst time = alt text
  • 实际情况下，我们并不能准确知道 burst durations
    • Predicting - Exponential averaging \(T_{n+1} = \alpha t_n + (1-\alpha) T_n\)
    • 其中 T 是预测，t 是实际观测
    • 可以扩展

Round-Robin Scheduling

  • 抢占式
  • 定义 time Quantum（A fixed interval of time (10-100ms)）
  • 每个进程最多只能执行一个 Quantum（更短时间执行完也行）
  • Ready Queue is a FIFO（被换下来的放在 end）
  • 好处 - 平均等待时间不如 SJF，但 better response time
    • 没有 starvation
    • waiting time 有上界
  • 坏处：Quantum
    • 太长了 - low overhead
    • 太短了 - context switch

Priority Scheduling

  • 选取优先级最高的程序执行
    • priority 可以是对时间的预测（SJF）- internal
    • 也可以 set by users to specify relative importance of job - externel
    • 一般来说，数字越小，优先级越高
  • Simply implement the Ready Queue as a Priority Queue
  • problem - 优先级低的程序执行不了（starvation）
  • aging - 增长年龄，也是优先级的一部分

Multilevel Queue Scheduling

  • The RR Scheduling scheme treats all processes equally
  • 为一个类的进程创建一个 ready queue（例如不同优先级的程序放在不同类里
  • Scheduling within queues
    • 每个队列有不同的方式（比如可以 High-priority could be RR, Low-priority could be FCFS
  • Scheduling between the queues
    • Typically preemptive priority scheduling, Or time-slicing among queues (为高优先级的队列分配更多时间)

Multilevel Feedback Queue Scheduling

  • Processes can move among the queues
  • 如果 process's characteristics have changed，例如预测 burst time 变少，可以从低优先级队列放到高优先级队列中（可以实现 priority aging

What’s a Good Scheduling Algorithm?

  • Few analytical/theoretical results are available
  • Another option: Simulation
  • Finally: Implementation

Thread Scheduling

感觉不重要

  • 进程内部 process-contention scope (PCS)
  • 所有进程之间 system-contention scope (SCS)
  • Multicore Processors

Operating System Examples

windows - 数越大优先级越高

  • XP - Priority-based, time quantum-based, multi-queue, preemptive scheduling

idle thread

Linux - 数越小优先级越高（NICE）

  • Round-robin + priority scheduling
  • Array
  • TASK-RUNNING means ready
  • O(N)
  • 后续优化：bitmap - O(1)
  • CFS 算法

alt text

会画甘特图

会算 average waiting time