ECE391- Computer
System Engineering
Lecture 17
Copyright By PowCoder代写 加微信 powcoder
University of Illinois at Urbana-
Announcements
• Checkpoint 1: 5:59PM on Tuesday 10/19
• 10/28/2021, 7-9 PM, ECEB 1002
• Conflicts by 10/22/2021
• No Class 10/28/2021
Virtualization
• Virtualization is the process of creating a software-
based, or virtual, representation of something, such
as virtual applications, servers, [memory, cpu, ]
storage and networks.
• How do we virtualize?
https://www.vmware.com/solutions/virtualization.html
• What did we just share last lecture? How? What
else might we virtualize?
• Gain familiarity with the concept of Multitasking,
Context switching
• Understand the User/Application view of processes
using LINUX as an example
• Application functions (e.g., fork, exit, wait, execve)
• Familiarize yourself with shells
• Understand the System Software view of processes
using LINUX as an example
• Basic data structures (e.g., task struct)
• Organization (e.g., double-linked lists, hashes)
• Function calls
• Appreciate the x86 hardware view of tasks and their
use in LINUX
User/Application View
• Definition: A process is an instance of a running
• One of the most profound ideas in computer science
• Not the same as “program” or “processor”
• Process provides each program with two key
abstractions:
• Logical control flow
• Each program seems to have exclusive use of the CPU
• Private virtual address space
• Each program seems to have exclusive use of main memory
• How are these Illusions maintained?
• Process executions interleaved (multitasking) or run on
separate cores
• Address spaces managed by virtual memory system
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
The World of Multitasking
• System runs many processes concurrently
• Process: executing program
• State includes memory image + register values + program counter
• Regularly switches from one process to another
• Suspend process when it needs I/O resource or timer event occurs
• Resume process when I/O available or given scheduling priority
• Appears to user(s) as if all processes executing
simultaneously
• Even though most systems can only execute one process at a time
• Except possibly with lower performance than if running alone
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
Concurrent Processes
• Two processes run concurrently (are concurrent) if
their flows overlap in time
• Otherwise, they are sequential
• Examples (running on single core):
• Concurrent: A & B, A & C
• Sequential: B & C
Process A Process B Process C
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
User View of Concurrent Processes
• Control flows for concurrent processes are physically
disjoint in time
• However, we can think of concurrent processes as
running in parallel with each other
Process A Process B Process C
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
Context Switching
• Processes are managed by a shared chunk of OS code
called the kernel
• Important: the kernel is not a separate process, but rather
runs as part of some user process
• Control flow passes from one process to another via a
context switch
Process A Process B
kernel code
kernel code
context switch
context switch
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
fork: Creating New Processes
• int fork(void)
• creates a new process (child process) that is identical to
the calling process (parent process)
• returns 0 to the child process
• returns child’s pid (process id) to the parent process
• Fork is interesting (and often confusing) because
it is called once but returns twice
pid_t pid = fork();
if (pid == 0) {
printf(“hello from child\n”);
printf(“hello from parent\n”);
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
Understanding fork
pid_t pid = fork();
if (pid == 0) {
printf(“hello from child\n”);
printf(“hello from parent\n”);
pid_t pid = fork();
if (pid == 0) {
printf(“hello from child\n”);
printf(“hello from parent\n”);
Child Process m
pid_t pid = fork();
if (pid == 0) {
printf(“hello from child\n”);
printf(“hello from parent\n”);
pid_t pid = fork();
if (pid == 0) {
printf(“hello from child\n”);
printf(“hello from parent\n”);
pid_t pid = fork();
if (pid == 0) {
printf(“hello from child\n”);
printf(“hello from parent\n”);
pid_t pid = fork();
if (pid == 0) {
printf(“hello from child\n”);
printf(“hello from parent\n”);
hello from parent hello from childWhich one is first?
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
Fork Example #1
void fork1()
int x = 1;
pid_t pid = fork();
if (pid == 0) {
printf(“Child has x = %d\n”, ++x);
printf(“Parent has x = %d\n”, –x);
printf(“Bye from process %d with x = %d\n”, getpid(), x);
• Parent and child both run same code
• Distinguish parent from child by return value from fork
• Start with same state, but each has private copy
• Including shared output file descriptor
• Relative ordering of their print statements undefined
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
Fork Example #2
void fork2()
printf(“L0\n”);
printf(“L1\n”);
printf(“Bye\n”);
• Two consecutive forks
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
Fork Example #3
• Three consecutive forks
void fork3()
printf(“L0\n”);
printf(“L1\n”);
printf(“L2\n”);
printf(“Bye\n”);
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
Fork Example #4
• Nested forks in parent
void fork4()
printf(“L0\n”);
if (fork() != 0) {
printf(“L1\n”);
if (fork() != 0) {
printf(“L2\n”);
printf(“Bye\n”);
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
Fork Example #5
• Nested forks in children
void fork5()
printf(“L0\n”);
if (fork() == 0) {
printf(“L1\n”);
if (fork() == 0) {
printf(“L2\n”);
printf(“Bye\n”);
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
exit: Ending a process
• void exit(int status)
• exits a process
• Normally return with status 0
• atexit() registers functions to be executed upon exit
void cleanup(void) {
printf(“cleaning up\n”);
void fork6() {
atexit(cleanup);
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
• When process terminates, still consumes system resources
• Various tables maintained by OS
• Called a “zombie”
• Living corpse, half alive and half dead
• Performed by parent on terminated child (using wait or
• Parent is given exit status information
• Kernel discards process
• What if parent doesn’t reap?
• If any parent terminates without reaping a child, then child
will be reaped by init process (pid == 1)
• So, only need explicit reaping in long-running processes
• e.g., shells and servers
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
linux> ./forks 7 &
Running Parent, PID = 6639
Terminating Child, PID = 6640
PID TTY TIME CMD
6585 ttyp9 00:00:00 tcsh
6639 ttyp9 00:00:03 forks
6640 ttyp9 00:00:00 forks
6641 ttyp9 00:00:00 ps
linux> kill 6639
[1] Terminated
PID TTY TIME CMD
6585 ttyp9 00:00:00 tcsh
6642 ttyp9 00:00:00 ps
• ps shows child process as
• Killing parent allows child to be
reaped by init
void fork7()
if (fork() == 0) {
/* Child */
printf(“Terminating Child, PID = %d\n”,
getpid());
printf(“Running Parent, PID = %d\n”,
getpid());
; /* Infinite loop */
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
wait: Synchronizing with Children
• Parent reaps child by calling the wait function
• int wait(int *child_status)
• suspends current process until one of its children terminates
• return value is the pid of the child process that terminated
• if child_status != NULL, then the object it points to will
be set to a status indicating why the child process terminated
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
wait: Synchronizing with
void fork9() {
int child_status;
if (fork() == 0) {
printf(“HC: hello from child\n”);
printf(“HP: hello from parent\n”);
wait(&child_status);
printf(“CT: child has terminated\n”);
printf(“Bye\n”);
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
execve: Loading and Running Programs
• int execve(
char *filename,
char *argv[],
char *envp[]
• Loads and runs in current process:
• Executable filename
• With argument list argv
• And environment variable list envp
• Does not return (unless error)
• Overwrites code, data, and stack
• keeps pid, open files and signal context
• Environment variables:
• “name=value” strings
• getenv and putenv
Null-terminated
env var strings
Null-terminated
cmd line arg strings
envp[n] == NULL
Linker vars
argv[argc] == NULL
argv[argc-1]
Stack bottom
Stack frame for
main Stack top
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
execve Example
if ((pid = Fork()) == 0) { /* Child runs user job */
if (execve(argv[0], argv, environ) < 0) {
printf("%s: Command not found.\n", argv[0]);
envp[n] = NULL
argv[argc] = NULL
argv[argc-1]
“/usr/include”
“USER=droh”
“PRINTER=iron”
“PWD=/usr/droh”
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
Unix Process Hierarchy
Login shell
ChildChildChild
GrandchildGrandchild
e.g. httpd
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
Shell Programs
• A shell is an application program that runs programs
on behalf of the user.
• sh Original Unix shell ( , AT&T Bell Labs, 1977)
• csh BSD Unix C shell (tcsh: enhanced csh at CMU and elsewhere)
• bash “Bourne-Again” Shell
int main() {
char cmdline[MAXLINE];
while (1) {
/* read */
printf("> “);
Fgets(cmdline, MAXLINE, stdin);
if (feof(stdin))
/* evaluate */
eval(cmdline);
Execution is a sequence of
read/evaluate steps
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
Simple Shell eval Function
void eval(char *cmdline) {
char *argv[MAXARGS]; /* argv for execve() */
int bg; /* should the job run in bg or fg? */
pid_t pid; /* process id */
bg = parseline(cmdline, argv);
if (!builtin_command(argv)) {
if ((pid = Fork()) == 0) { /* child runs user job */
if (execve(argv[0], argv, environ) < 0) { printf("%s: Command not found.\n", argv[0]); if (!bg) { /* parent waits for fg job to terminate */ int status; if (waitpid(pid, &status, 0) < 0) unix_error("waitfg: waitpid error"); else /* otherwise, don’t wait for bg job */ printf("%d %s", pid, cmdline); https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/ What Is a “Background Job”? • Users generally run one command at a time • Type command, read output, type another command • Some programs run “for a long time” • Example: “delete this file in two hours” • A “background” job is a process we don't want to wait unix> sleep 7200; rm /tmp/junk # shell stuck for 2 hours
unix> (sleep 7200 ; rm /tmp/junk) &
unix> # ready for next command
https://www.cs.cmu.edu/afs/cs/academic/class/15213-f12/www/lectures/
OS/System Software View
• Reality: each CPU can only run one program at a
• Fiction to user: many people getting short (~10-100
ms) time slices
• pseudo-parallelism à multiprogramming
• modeled as sequential processes
• context switch
https://www.cs.columbia.edu/~hgs/teaching/ap/slides/process_threads.ppt
What’s a process?
• timesharing system: alternate between processes,
interrupted by OS:
• run on CPU
• clock interrupt happens
• save process state (context switch)
• registers (PC, SP, numeric)
• memory map
• continue some other process
https://www.cs.columbia.edu/~hgs/teaching/ap/slides/process_threads.ppt
Process creation
• Processes are created:
• system initialization
• by another process
• Foreground processes interact with user
• Background processes (daemons)
https://www.cs.columbia.edu/~hgs/teaching/ap/slides/process_threads.ppt
Linux: Processes or Threads?
• Linux uses a neutral term: tasks
• Tasks represent both processes and threads
• Linux view
• Threads: processes that share address space
• Linux “threads” (tasks) are really “kernel threads“
• Lighter-weight than traditional processes
• File descriptors, VM mappings need not be copied
• Implication: file table and VM table not part of process
descriptor
http://www.cs.columbia.edu/~nahum/w4118/lectures/Processes.ppt
Stacks and task-descriptors
• To manage multitasking, the OS needs to use a data-structure which
can keep track of every task’s progress and usage of the computer’s
available resources (physical memory, open files, pending signals,
• Such a data-structure is called a ‘process descriptor’ – every active
task needs one
• Every task needs its own ‘private’ stack
• So every task, in addition to having its own code and data, will also
have a stack-area that is located in user-space, plus another stack-
area that is located in kernel-space
• Each task also has a process-descriptor which is accessible only in
kernel-space
http://www.cs.columbia.edu/~nahum/w4118/lectures/Processes.ppt
Process Descriptor
• Process – dynamic, program in motion
• Kernel data structures to maintain “state”
• Descriptor, PCB (control block), task_struct
• Larger than you think! (about 1K)
• Complex struct with pointers to others
• Type of info in task_struct
• state, id, priorities, locks, files, signals, memory maps, locks,
queues, list pointers, …
• Some details
• Address of first few fields hardcoded in asm
• Careful attention to cache line layout
http://www.cs.columbia.edu/~nahum/w4118/lectures/Processes.ppt
The Linux process descriptor
task_struct
user_struct
signal_struct
files_struct
Each process
descriptor
contains many
and some are
pointers to
other kernel
structures
themselves
include fields
that point to
structures
http://www.cs.columbia.edu/~nahum/w4118/lectures/Processes.ppt
What is a process/task in Linux?
• unit of scheduling in Linux
• also name of data structure (struct task_struct) (see
linux/sched.h)
User-level view
• each execution context that can be independently
scheduled must have its own process descriptor
• traditional process id (pid, a field in task
structure/process descriptor)
• from 1 to 32,767 in Linux, used as task-unique identifier
• tgid (thread group id) plays process id role for
multithreaded applications (common id for all threads
in process)
• most processes belong to a thread group consisting of a
single member
Kernel view
• keeps two data structures in a single per-process
area (8kB)
• thread_info structure (keeps pointer
to task structure or process descriptor)
• kernel stack
• both dynamically allocated
• architecture-dependent thread
info shares space with kernel stack
• Remember: DO NOT USE RECURSION IN THE
thread info
Task structures
• placed in a cyclic, doubly-linked list
• list starts with sentinel: init_task
• first task created by kernel at boot time
• persists until machine shut down/rebooted
• used for lazy page table updates (discussed later)
tasks.next
tasks.prev
For system calls
• must translate pid to struct pid* (small structure referencing task)
• find_pid (kernel/pid.c) uses a hash table
• map large, sparse space into small, dense space
• O(1) access time if # buckets similar to # of elements (really O(n))
• NOT dynamically grown
• doubly-linked list per bin, but back links only for deletion
• hash function = ((pid * big prime #) >> shift)
struct pid*)
. pidchain.next (*)pidchain.pprev (**)bound as small
as 15 on machines
with less memory
parent/child relationships
• a process that creates a second process
• is said to be the latter’s parent
• shell from which you run program
• is the parent for those programs
• a tree relationship with unbounded degree
• root of the tree is the init_task
how can such a structure be contained in
constant space per node?
Sibling List
• include list of children as part of each childʼs structure…
parent parent pointer
children.next oldest child pointer
children.prev youngest child pointer
sibling.prev older sibling pointer
sibling.next younger sibling pointer
real_parent original parent (for debugging)
ild parent
younger sibling
older sibling
(sibling list
is cyclic)
Creating Processes/Tasks
• User-level:
• fork, vfork, and clone system calls
Creating Processes/Tasks
• In kernel: all map into do_fork
• prototype in linux/sched.h; implementation in kernel/fork.c
int do_fork (unsigned long clone_flags,
unsigned long stack_start,
struct pt_regs* regs,
unsigned long stack_size,
int __user* parent_tidptr,
int __user* child_tidptr);
• __user means not to be dereferenced
• returns new pid or negative value on error
Parameters
• clone_flags – control flags, to be discussed later; for
now, just CLONE_PARENT, which creates a sibling
task (like a thread) instead of a child task
• stack_start – the new task’s ESP (in user space; 0
for kernel threads)
• regs – register values for the new task
• stack_size – ignored on x86, but needed on some
• parent/child_tidptr – filled in as part of system call
(sys_clone only)
Creating Processes/Tasks (cont.)
• do_fork calls copy_process (same file) to set up the
process descriptor and any other kernel data
structures necessary for child execution
• mostly relies on an architecture-dependent version,
copy_thread (see arch/i386/kernel/process.c)
• only stack_start and regs are used by x86 version
Creating Kernel Threads
• What is a kernel thread?
• a task without an associated address space
• inherits address space from last user task to execute
• (all address spaces map the kernel pages and data
structures)
Creating Kernel Threads (cont.)
• The interface
• prototype in asm/processor.h; implementation in
arch/i386/kernel/process.c
int kernel_thread (int (*fn)(void*), void* arg,
unsigned long flags);
• returns new pid or negative value on error
Creating Kernel Threads (cont.)
• to identify a kernel thread, check the memory map
fields of task
• mm = memory map owned by the task
• active_mm = memory map in use by task
• these are identical for user tasks; for kernel threads, mm
Creating Kernel Threads (cont.)
• init_task is a kernel thread
• created during boot (in start_kernel); persists until
• Other kernel threads
• ksoftirqd – the soft interrupt daemon (periodically try to
execute tasklets)
init_files
init_signals/init_sighand
ISA/Hardware View
IA-32 architecture’s task
management facilities
• A task is a unit of work that a processor can dispatch, execute, and suspend.
• It can be used to execute a program, a task or process, an operating-system service
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com