Processes and Threads What are processes? How does the operating system manage them? Nick Urbanik nicku@vtc.edu.hk Department of Information and Communications Technology Copyright Conditions: Open Publication License (see http://www.opencontent.org/openpub/) Introduction What is a process?. . . . . . . . . . . . . . . What is a process? — 2 . . . . . . . . . . . What is a thread? . . . . . . . . . . . . . . . Program counter . . . . . . . . . . . . . . . . Environment of a process . . . . . . . . . . Permissions of a Process. . . . . . . . . . . Multitasking Multitasking . . . . . . . . . . . . . . . . . . . Multitasking — 2 . . . . . . . . . . . . . . . Multitasking — 3 . . . . . . . . . . . . . . . Start of Process Birth of a Process . . . . . . . . . . . . . . . Process tree . . . . . . . . . . . . . . . . . . . Scheduler Scheduler . . . . . . . . . . . . . . . . . . . . . When to Switch Processes?. . . . . . . . . Scheduling statistics: vmstat . . . . . . . Interrupts . . . . . . . . . . . . . . . . . . . . . Process States Process States . . . . . . . . . . . . . . . . . . What is Most Common State? . . . . . . Most Processes are Blocked . . . . . . . . Linux Process States . . . . . . . . . . . . . Linux Process States — 2. . . . . . . . . . Linux Process States — 3. . . . . . . . . . Process States: vmstat . . . . . . . . . . . Tools for monitoring processes . . . . . . Monitoring processes in Win 2000 . . . . top Process Monitoring — top . . . . . . . . . load average . . . . . . . . . . . . . . . . . . . top: process states. . . . . . . . . . . . . . . top and memory . . . . . . . . . . . . . . . . Virtual Memory: suspended processes . Suspended Processes . . . . . . . . . . . . . Process Control Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide slide slide slide slide slide 2 3 4 5 6 7 . . . . . . . . . . . . . . . . slide 8 . . . . . . . . . . . . . . . . slide 9 . . . . . . . . . . . . . . . slide 10 . . . . . . . . . . . . . . . slide 11 . . . . . . . . . . . . . . . slide 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide 13 14 15 16 17 18 19 20 21 22 23 24 25 27 28 29 30 31 32 OS Process Control Structures . . . . . . . What is in a PCB . . . . . . . . . . . . . . . . Context Switch . . . . . . . . . . . . . . . . . . Execution Context . . . . . . . . . . . . . . . . Program Counter in PCB . . . . . . . . . . . PCB Example . . . . . . . . . . . . . . . . . . . PCB Example Diagram . . . . . . . . . . . . PCB Example — Continued . . . . . . . . . Address of I/O instructions . . . . . . . . . System Calls System Calls . . . . . . . . . . . . . . . . . . . . File I/O system calls: a sidetrack . . . . . init. . . . . . . . . . . . . . . . . . . . . . . . . . . SUID, SGID and IDs . . . . . . . . . . . . . . Other system calls: getting process info . fork(): what it does . . . . . . . . . . . . . . Using fork(): pseudocode . . . . . . . . . . Simple fork() Example (no Checking) . An example using fork(). . . . . . . . . . . Example using fork()—(contd.). . . . . . Output of fork-example.c: . . . . . . . . . Running fork-example again . . . . . . . . Why two “before fork” messages? . . . So what does this show?. . . . . . . . . . . . Running another program — exec(). . . execve() system call . . . . . . . . . . . . . . fork() — exec() Example . . . . . . . . . Using execl() . . . . . . . . . . . . . . . . . . print.c: a program we call . . . . . . . . . Calling ./print using execl(). . . . . . . vfork() sytem call . . . . . . . . . . . . . . . wait(), waitpid() system calls . . . . . . wait(), waitpid() system calls . . . . . . A shell program Part of Simple Shell Program . . . . . . . . Windows and Processes . . . . . . . . . . . . Windows and Processes — 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide 34 35 36 37 38 39 40 41 42 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 . . . . . . . . . . . . . . slide 67 . . . . . . . . . . . . . . slide 68 . . . . . . . . . . . . . . slide 69 CreateProcess() prototype . . . . . . . CreateProcess() . . . . . . . . . . . . . . Example: CreateProcess() . . . . . . . Processes in Linux, Unix, Windows . . IPC Problem with Processes . . . . . . . . . . Interprocess Communication (IPC) . . IPC — Shared Memory . . . . . . . . . . IPC — Signals . . . . . . . . . . . . . . . . Signals and the Shell . . . . . . . . . . . . Threads Threads and Processes . . . . . . . . . . . Threads have own. . . . . . . . . . . . . . . Threads share a lot . . . . . . . . . . . . . Threads in Linux, Unix . . . . . . . . . . hello.c: a simple threaded program. Compile POSIX Threads . . . . . . . . . pthread create(). . . . . . . . . . . . . . pthread create(). . . . . . . . . . . . . . Problem with threads: . . . . . . . . . . . Race Condition Race Conditions . . . . . . . . . . . . . . . Critical Sections . . . . . . . . . . . . . . . Race Condition — one possibility . . . Example — another possibility . . . . . Solution: Synchronisation. . . . . . . . . File Locking . . . . . . . . . . . . . . . . . . Synchronisation Synchronisation . . . . . . . . . . . . . . . . Semaphores. . . . . . . . . . . . . . . . . . . Semaphores — 2 . . . . . . . . . . . . . . . POSIX and Win32. . . . . . . . . . . . . . Threads Example 1 . . . . . . . . . . . . . Threads Example 2 . . . . . . . . . . . . . Threads Example 3 . . . . . . . . . . . . . Condition Variables . . . . . . . . . . . . . Monitors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide slide 70 71 72 73 75 76 77 78 79 81 82 83 84 85 86 87 88 89 91 92 93 94 95 96 . slide 98 . slide 99 slide 100 slide 101 slide 102 slide 103 slide 104 slide 105 slide 106 Spinlocks . . . . . . . . . . . . . . . . . . . . . . Summary and References Summary — Process States, Scheduling. Summary — Processes and Threads . . . Summary — Synchronisation . . . . . . . . References. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide 107 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . slide slide slide slide 109 110 111 112 What is a process?    OSSI — ver. 1.5 ¡¢ prints one line for each process. A program can be executed a number of times simultaneously. ◦ Each is a separate process. Processes — slide 2           A process is a program in execution Each process has a process ID In Linux, $ What is a process? — 2 A process includes current values of: ◦ Program counter ◦ Registers ◦ Variables A process also has: ◦ The program code ◦ It’s own address space, independent of other processes ◦ A user that owns it ◦ A group owner ◦ An environment and a command line This information is stored in a process control block, or task descriptor or process descriptor ◦ a data structure in the os, in the process table ◦ See slides starting at 34. OSSI — ver. 1.5 £¤ ¥ Processes — slide 3 What is a thread? A thread is a lightweight process ◦ Takes less cpu power to start, stop Environment of a process       Part of a single process Shares address space with other threads in the same process Threads can share data more easily than processes Sharing data requires synchronisation, i.e., locking — see slide 95. This shared memory space can lead to complications in programming: “Threads often prevent abstraction. In order to prevent deadlock. you often need to know how and if the library you are using uses threads in order to avoid deadlock problems. Similarly, the use of threads in a library could be affected by the use of threads at the application layer.” – David Korn See page 180, ESR in references, 112. OSSI — ver. 1.5 ¢§ ¨      The environment is a set of names and values Examples: PATH=/usr/bin:/bin:/usr/X11R6/bin HOME=/home/nicku SHELL=/bin/bash In Linux shell, can see environment by typing: $   Processes — slide 6 Permissions of a Process A process executes with the permissions of its owner ◦ The owner is the user that starts the process A Linux process can execute with permissions of another user or group If it executes as the owner of the program instead of the owner of the process, it is called set user id Similarly for set group id programs Processes — slide 7 OSSI — ver. 1.5 Processes — slide 4 ¦ Program counter      The code of a process occupies memory The Program counter (PC) is a cpu register PC holds a memory address. . . . . . of the next instruction to be fetched and executed Processes — slide 5   OSSI — ver. 1.5           OSSI — ver. 1.5 Multitasking Our lab PCs have one main cpu ◦ But multiprocessor machines are becoming increasingly common ◦ Linux 2.6.x kernel scales to 16 cpus How execute many processes “at the same time”? Processes — slide 8 OSSI — ver. 1.5 Multitasking — 2 Birth of a Process In Linux, a process is born from a fork() system call ◦ A system call is a function call to an operating system service provided by the kernel     CPU rapidly switches between processes that are “ready to run” Really: only one process runs at a time Change of process called a context switch ◦ See slide 36 With Linux: see how many context switches/second using vmstat under “system” in column “cs” Processes — slide 9 OSSI — ver. 1.5       ¥     Each process has a parent The parent process calls fork() The child inherits (but cannot change) the parent environment, open files Child is identical to parent, except for return value of fork(). ◦ Parent gets child’s process ID (pid) ◦ Child gets 0 OSSI — ver. 1.5 Processes — slide 11 Multitasking — 3 This diagram shows how the scheduler gives a “turn” on the cpu to each of four processes that are ready to run process D C B A time context switches OSSI — ver. 1.5 Processes — slide 10   OSSI — ver. 1.5 £¤  ¡¢ ¡¢© ¨ or $     CPU executes process Process tree Processes may have parents and children Gives a family tree In Linux, see this with commands: $ §§ Processes — slide 12 Scheduler OS decides when to run each process that is ready to run (“runable”) The part of OS that decides this is the scheduler Scheduler aims to: ◦ Maximise CPU usage ◦ Maximise process completion ◦ Minimise process execution time ◦ Minimise waiting time for ready processes ◦ Minimise response time OSSI — ver. 1.5 Processes — slide 13 Interrupts         Will discuss interrupts in more detail when we cover I/O An interrupt is an event (usually) caused by hardware that causes: ◦ Saving some CPU registers ◦ Execution of interrupt handler ◦ Restoration of CPU registers An opportunity for scheduling Processes — slide 16   OSSI — ver. 1.5 Process States waiting for input Running scheduler chooses this process Blocked input available OSSI — ver. 1.5 Processes — slide 17 When to Switch Processes? The scheduler may change a process between executing (or running) and ready to run when any of these events happen: ◦ clock interrupt ◦ I/O interrupt ◦ Memory fault ◦ trap caused by error or exception ◦ system call See slide 17 showing the running and ready to run process states. scheduler chooses another process Ready     OSSI — ver. 1.5 ¥ Processes — slide 14 Scheduling statistics:     What is Most Common State? ◦ “cs” — number of context switches per second ◦ “in” — number of interrupts per second See slide 36, man vmstat   ¥ OSSI — ver. 1.5 Processes — slide 15      The “system” columns give statistics about scheduling:   Now, my computer has 160 processes. How many are running, how many are ready to run, how many are blocked? What do you expect is most common state? Processes — slide 18 OSSI — ver. 1.5 Most Processes are Blocked 9:41am up 44 days, 20:12, 1 user, load average: 2.02, 2.06, 2.13 160 processes: 145 sleeping, 2 running, 13 zombie, 0 stopped Linux Process States — 2 Running — actually contains two states: ◦ executing, or ◦ ready to execute Interruptable — a blocked state ◦ waiting for event, such as: – end of an I/O operation, – availability of a resource, or – a signal from another process Uninterruptable — another blocked state ◦ waiting directly on hardware conditions ◦ will not accept any signals (even SIGKILL) OSSI — ver. 1.5 Processes — slide 21    Here you see that most are sleeping, waiting for input! Most processes are “I/O bound”; they spend most time waiting for input or waiting for output to complete With one cpu, only one process can actually be running at one time However, surprisingly few processes are ready to run The load average is the average number of processes that are in the ready to run state.      In output from the top program above, see over last 60 seconds, there are 2.02 processes on average in rtr state Processes — slide 19   OSSI — ver. 1.5 Linux Process States stopped   zombie         Linux Process States — 3 Stopped — process is halted ◦ can be restarted by another process running state ◦ e.g., a debugger can put a process into stopped state executing creation Zombie — a process has terminated ◦ but parent did not wait() for it (see slide 33) Processes — slide 22 ready to run scheduling wait for event event OSSI — ver. 1.5 Process States: interruptible OSSI — ver. 1.5 Processes — slide 20     signal or event uninterruptible The “procs” columns give info about process states: “r” — number of processes that are in the ready to run state “b” — number of processes that are in the uninterruptable blocked state Processes — slide 23 OSSI — ver. 1.5     Tools for monitoring processes Process Monitoring with     ¢¨ £¨ Linux provides: ◦ Good to monitor over time: Process Monitoring —  ¡© " !   ¢ ¨ £¨  $ ◦ Easier to understand than vmstat ◦ Monitor over time with 08:12:13 up 1 day, 13:34, 8 users, load average: 0.16, 0.24, 0.49 111 processes: 109 sleeping, 1 running, 1 zombie, 0 stopped CPU states: cpu user nice system irq softirq iowait idle total 0.0% 0.0% 3.8% 0.0% 0.0% 0.0% 96.1% Mem: 255608k av, 245064k used, 10544k free, 0k shrd, 17044k buff 152460k active, 63236k inactive Swap: 1024120k av, 144800k used, 879320k free 122560k cached R9BQ 9@A BCDE 9E@ F@C @GD ECCH IDECP PI 1253 1769 23548 1 2 3 4 6 5 root nicku nicku root root root root root root 15 16 16 16 15 15 34 15 15 0 73996 13M 11108 S 0 2352 1588 1488 S 0 1256 1256 916 R 0 496 468 440 S 0 0 0 0 SW 0 0 0 0 SW 19 0 0 0 SWN 0 0 0 0 SW 0 0 0 0 SW 2.9 1.9 1.9 0.0 0.0 0.0 0.0 0.0 0.0 7 SDSQ P@SD 5.5 0.6 0.4 0.1 0.0 0.0 0.0 0.0 0.0 19:09 2:10 0:00 0:05 0:00 0:00 0:00 0:00 0:11 0 0 0 0 0 0 0 0 0 X magicdev top init keventd kapmd ksoftirqd/0 bdflush kswapd 8 R9B RTS 54 6 Processes — slide 27 Processes — slide 28    View processes with " ! #  ¢©£ ¡ ¨ $ ¡© — see slides 27 to 30 The system monitor shows data collected over time: See man sar; investigate sar -c and sar -q See the utilities in the procps software package. You can list them with $ ¥ OSSI — ver. 1.5   OSSI — ver. 1.5 ¢ ' ¡ ¡ ' %%! £¡ %%! ¨ % ¢" ! ¢£ % £ ) §  ¨( ¡ ¢ 0¡ ¨ ¡ ¨ £ ¨¨ § ! 1£ ¨ 21 3 ¡&© ©§  ¡¢ §¡ § #$ % ¡© ¡¢ ©¡ Processes — slide 24 : load average up 1 day, 13:34, 8 users, 7 8 Monitoring processes in Win 2000 08:12:13     Windows 2000 provides a tool: Start → Administrative Tools → Performance. Can use this to monitor various statistics Processes — slide 25 load average is measured over the last minute, five minutes, fifteen minutes Over that time is the average number of processes that are ready to run, but which are not executing A measure of how “busy” a computer is. OSSI — ver. 1.5       OSSI — ver. 1.5 Y`aW b`c efifdgh efi dpq efdqr VWW UX IAF 111 processes: 109 sleeping, 1 running, 1 zombie, 0 stopped 9@A 78  BCDE : process states i /o : Processes and Memory 7 8 R9BQ F@C @GD ECCH IDECP PI 15 0 73996 13M 11108 S 2.9 SDSQ P@SD 5.5 9@E 1253 root sleeping Most processes (109/111) are sleeping, waiting for running This is the number of processes that are both ready to run and are executing zombie There is one process here that has terminated, but its parent did not wait() for it. The wait() system calls are made by a parent process, to get the exit() status of its child(ren). This call removes the process control block from the process table, and the child process does not exist any more. ( 34)  ¨ SIZE This column is the total size of the process, including the part which is swapped (paged out) out to the swap partition or swap file Here we see that the process X uses a total of 73,996 Kb, i.e., 73,996 × 1024 bytes ≈ 72MB, where here 1MB = 220 bytes. RSS The resident set size is the total amount of ram that a process uses, including memory shared with other processes. Here X uses a total of 13MB ram, including ram shared with other processes. SHARE The amount of shared memory is the amount of ram that this process shares with other processes. Here X shares 11,108 KB with other processes. We can see that the total amount of ram used exclusively by one process is rss−share. Here we see that X uses about 13×220 −11,108×210 ≈ 2 MB OSSI — ver. 1.5 Processes — slide 30     stopped When you press  Control-z © a shell, you will increase this in number by 1 OSSI — ver. 1.5 Processes — slide 29 ¥ Virtual Memory: suspended processes With memory fully occupied by processes, could have all in blocked state! cpu could be completely idle, but other processes waiting for ram Solution: virtual memory ◦ will discuss details of vm in memory management lecture Part or all of process may be saved to swap partition or swap file Processes — slide 31        OSSI — ver. 1.5 R9B 19:09 0X RTS IAF Suspended Processes Could add more states to process state table: ◦ ready and suspended ◦ blocked and suspended OSSI — ver. 1.5 Processes — slide 32 What is in a PCB In slide 3, we saw that a pcb contains: ◦ a process id (pid) ◦ process state (i.e., executing, ready to run, sleeping waiting for input, stopped, zombie) ◦ program counter, the cpu register that holds the address of the next instruction to be fetched and executed ◦ The value of other CPU registers the last time the program was switched out of executing by a context switch — see slide 36 ◦ scheduling priority ◦ the user that owns the process ◦ the group that owns the process ◦ pointers to the parent process, and child processes ◦ Location of process’s data and program code in memory ◦ List of allocated resources (including open files) pcb holds the values as they were when process was last switched out of executing by a context switch — see slide 36       Process Control Blocks The Process Table Data structure in OS to hold information about a process OS Process Control Structures ¥ ¥ OSSI — ver. 1.5       Every os provides process tables to manage processes In this table, the entries are called process control blocks (pcbs), process descriptors or task descriptors. We will use the abbreviation pcb. There is one pcb for each process in Linux, pcb is called include/linux/sched.h task struct, defined in ◦ In a Fedora Core or Red Hat system, you will find it in the file /usr/src/linux-2.*/include/linux/sched.h if you have installed the kernel-source software package OSSI — ver. 1.5 Processes — slide 34 ¥ Processes — slide 35 Context Switch os does a context switch when: ◦ stop current process from executing, and ◦ start the next ready to run process executing on cpu Program Counter in PCB      What value is in the program counter in the pcb? If it is not executing on the cpu, ◦ The address of the next cpu instruction that will be fetched and executed the next time the program starts executing If it is executing on the cpu, ◦ The address of the first cpu instruction that was fetched and executed when the process began executing at the last context switch ( 36)       os saves the execution context (see 37) to its pcb os loads the ready process’s execution context from its pcb When does a context switch occur? ◦ When a process blocks, i.e., goes to sleep, waiting for input or output (i/o), or ◦ When the scheduler decides the process has had its turn of the cpu, and it’s time to schedule another ready-to-run process A context switch must be as fast as possible, or multitasking will be too slow ◦ Very fast in Linux os Processes — slide 36 ¥ OSSI — ver. 1.5 ¥ Processes — slide 38   OSSI — ver. 1.5 Process Control Blocks—Example The diagram in slide 40 shows three processes and their process control blocks. There are seven snapshots t0 , t1 , t2 , t3 , t4 , t5 and t6 at which the scheduler has changed process (there has been a context switch— 36) On this particular example cpu, all i/o instructions are 2 bytes long The diagram also shows the queue of processes in the: ◦ Ready queue (processes that are ready to run, but do not have a cpu to execute on yet) ◦ Blocked, or Wait queue, where the processes have been blocked because they are waiting for i/o to finish. OSSI — ver. 1.5 Processes — slide 39 Execution Context Also called state of the process (but since this term has two meanings, we avoid that term here), process context or just context The execution context is all the data that the os must save to stop one process from executing on a cpu, and load to start the next process running on a cpu This includes the content of all the cpu registers, the location of the code, . . . ◦ Includes most of the contents of the process’s pcb. OSSI — ver. 1.5 Processes — slide 37        ¥      ¥ PCB Example: Diagram t0 t1 t2 t3 t4 t5 t6 CPU idle time What is the address of I/O instructions? We are given that all i/o instructions in this particular example are two bytes long (slide 39) ◦ We can see that when the process is sleeping (i.e., blocked), then the program counter points to the instruction after the i/o instruction ◦ So for process P1, which blocks with program counter pc = C0DE16 , the i/o instruction is at address C0DE16 − 2 = C0DC16 ◦ for process P2, which blocks with program counter pc = FEED16 , the i/o instruction is at address FEED16 − 2 = FEEB16 ◦ for process P3, which blocks with program counter pc = D1CE16 , the i/o instruction is at address D1CE16 − 2 = D1CC16 OSSI — ver. 1.5 Processes — slide 42   Ready Queue: Blocked Queue: P3 P2 P3 P1 P1 P2 P2 P3 P3 PCB for P1 0xCAFE Running 0xC0DE Blocked 0xC0DE Ready 0xC0DE Running Process 1 has terminated; It’s PCB has been freed Sfrag replacements PCB for P2 0xFACE Ready 0xFACE Running 0xFEED Blocked 0xFEED Ready 0xFEED Running Process 2 has terminated PCB is freed PCB for P3 0xDEAF Ready 0xDEAF Ready 0xDEAF Running 0xD1CE Blocked 0xD1CE Ready 0xD1CE Running P3 has exited; PCB freed OSSI — ver. 1.5 Processes — slide 40 PCB Example — Continued In slide 40, ◦ The times t0 , t1 , t2 , t3 , t4 , t5 and t6 are when the scheduler has selected another process to run. ◦ Note that these time intervals are not equal, they are just the points at which a scheduling change has occurred. Each process has stopped at one stage to perform i/o ◦ That is why each one is put on the wait queue once during its execution. Each process has performed i/o once Processes — slide 41 s s t Process System Calls How the OS controls processes s OSSI — ver. 1.5 ¥ How you use the OS to control processe Major process Control System Calls Process IDs and     Every process has a process id (pid) process 0 is the scheduler, part of kernel process 1 is , the parent of all other processes  §¤    § © ' uv § uv — start a new process — replace calling process with machine code from another program file ◦ a normal user process, not part of kernel ◦ program file is /sbin/init , — parent process gets status of its’ child after the child has terminated, and cleans up the process table entry for the child (stops it being a zombie)    All other processes result from init calling the " !! ¨ yxw w system call  1 1£ ! ¡ ¨ )! uv £ ¨! This is the only way a new process is created by the kernel Processes — slide 46 OSSI — ver. 1.5 — terminate the current process Processes — slide 44  §¤ OSSI — ver. 1.5 File I/O system calls: a sidetrack #include ssize_t read( int filedes, void *buf, size_t nbytes ); returns number of bytes read, 0 at end of file, −1 on error ssize_t write( int filedes, void *buf, size_t nbytes ); ¨! uv SUID, SGID and IDs      Every process has six or more ids associated with it uid and gid of person who executes program file: ◦ real user id, real group id ids used to calculate permissions: ◦ Effective uid, Effective gid ids saved when use exec() system call: ◦ Saved set-user-ID, saved set-group-ID ◦ idea is can drop special privileges and return to executing with real uid and real gid when privilege is no longer required     returns number of bytes written, else −1 on error Note: these are unbuffered, that is, they have effect “immediately”. This is different from stdio.h functions, which are buffered for efficiency. Processes — slide 45 OSSI — ver. 1.5     OSSI — ver. 1.5 © ' uv Processes — slide 47 uv Other system calls: getting process info #include #include Using : pseudocode        pid t getpid(void); returns PID of calling process pid t getppid(void); returns PID of parent uid t getuid(void); returns real user ID of process if ( ( pid = fork() ) < 0 ) fork error has happened else if ( pid == 0 ) /∗ I am the child ∗/ do things the child process should do else /∗ I am the parent ∗/ do things the parent should do OSSI — ver. 1.5 Processes — slide 50 uid t geteuid(void); returns effective user ID of process gid t getgid(void); returns real group ID of process Processes — slide 48 gid t getegid(void); returns effective group ID of process OSSI — ver. 1.5 Simple  ‚ ƒ„ 7€ Example (no Checking) #include #include int main() { int pid = fork(); printf( "PID is %d\n", pid ); if ( pid == 0 ) printf( "I’m the child\n" ); else printf( "I’m the parent\n" ); } Processes — slide 49 OSSI — ver. 1.5 Processes — slide 51 : what it does      ‚ ƒ„ 7€ #include #include pid_t fork(void); returns 0 in child returns pid of child in parent returns −1 if error OSSI — ver. 1.5  ‚ ƒ„ 7€ An example using Output of :  ‚ ƒ„ 7€ #include #include #include int glob = 6; char buf[] = "a write to standard output\n"; int main( void ) { int var = 88; /∗ local variable on the stack ∗/ pid t pid; if ( write( STDOUT FILENO, buf, sizeof (buf) − 1 ) = sizeof( buf ) − 1 ) { fprintf( stderr, "write error" ); exit( 1 ); } $ gcc -o fork-example fork-example.c $ ./fork-example a write to standard output before fork pid = 7118, global = 7, var = 89 child’s vars changed pid = 7117, global = 6, var = 88 parent’s copy not changed OSSI — ver. 1.5 Processes — slide 54 Running 7€ OSSI — ver. 1.5 Processes — slide 52 $ ./fork-example > tmp.out $ cat tmp.out a write to standard output before fork pid = 7156, global = 7, var = 89 before fork pid = 7155, global = 6, var = 88 OSSI — ver. 1.5 Processes — slide 55 Example using —(contd.) printf( "before fork\n" ); if ( ( pid = fork() ) < 0 ) { fprintf( stderr, "fork error\n" ); exit( 1 ); } else if ( pid == 0 ) { ++glob; ++var; } else sleep( 2 ); /∗ parent ∗/ printf( "pid = %d, glob = %d, var = %d\n", getpid(), glob, var ); exit( 0 ); }  ‚ ƒ„ 7€ Why two “ /∗ child ∗/ 8‰ ‡ˆ 7€  ‡  ‚… 7 ‡ “€     write() system call not buffered write() called before fork(), so one output printf() is buffered ◦ line buffered if connected to terminal ◦ fully buffered otherwise; parent and child both have a copy of the unwritten buffer when redirected exit() causes both parent and child buffers to flush Processes — slide 56 OSSI — ver. 1.5 Processes — slide 53   OSSI — ver. 1.5 ‚ ‡ 7€ …† ‚ ‡ˆ  8 ‘‡ ‰ ’ again ” messages? So what does this show? — Example  ‚ ƒ„ 7€ Processes — slide 57       It shows that the child is an exact copy of the parent, with all variable values, buffers, open files,. . . All are inherited by the child #include #include int main() { int pid = fork(); printf( "PID is %d\n", pid ); if ( pid == 0 ) printf( "I’m the child\n" ); else printf( "I’m the parent\n" ); } OSSI — ver. 1.5 Running another program —     To run another program file first call fork() to create a child process child calls exec() to replace current copy of parent with a totally new program in execution Processes — slide 58 ‡’ ƒ„ ‡ˆ OSSI — ver. 1.5 ‡ˆ ‡’ ƒ„ Processes — slide 60 OSSI — ver. 1.5 system call ‡ ƒ„ ‡ˆ ‡’ Using #include int execve( const char ∗filename, char ∗const argv[], char ∗const envp[] );       executes the program filename, replaces current process Passes the command line in argv[] passes the environment variables in envp[] Does not return, unless error, when returns with −1 Usually called through library exec*() calls — see man 3 exec Processes — slide 59     OSSI — ver. 1.5 OSSI — ver. 1.5 ‡ˆ int execl( const char *path, const char *arg, ... ); Parameter number: 1. gives full path of the program file you want to execute 2. gives name of the new process 3. specifies the command line arguments you pass to the program 4. last is a NULL pointer to end the parameter list. We must always put a NULL pointer at the end of this list. Processes — slide 61 ‡’ ‰ ƒ„ #include #include int main( int argc, char ∗argv[] ) { // argv[0] is the program name int num = atoi( argv[1] ); int loops = atoi( argv[2] ); int i; for ( i = 0; i < loops; ++i ) printf( "%d ", num ); } OSSI — ver. 1.5 Processes — slide 62        ‚ ƒ„ : a program we call sytem call yxw 7 € 8  ’ A lightweight fork() Designed for running execvp() straight after ◦ modern Linux fork() is very efficient when call exec*() Child does not contain an exact copy of parent address space; child calls exec() or exit() after fork() parent is suspended till child calls fork() or exit() Processes — slide 64 OSSI — ver. 1.5 , system calls w ƒ„ •   #include #include pid_t wait( int *status ); pid_t waitpid( pid_t pid, int *status, int options ); return process id if ok, 0, or −1 on error Processes — slide 65 OSSI — ver. 1.5 Calling using 8 ” xw  #include #include int main() { printf( "hello world\n" ); int pid = fork(); printf( "fork returned %d\n", pid ); if ( pid == 0 ) execl( "./print", "print", "1", "100", NULL ); else execl( "./print", "print", "2", "100", NULL ); }  ‡ˆ ‡’ ‰ ƒ„ OSSI — ver. 1.5 Processes — slide 63         w ƒ„ • 8w –w ƒ„ OSSI — ver. 1.5 , 8w –w ƒ„ • • system calls wait() can block caller until child process terminates waitpid() has option to prevent blocking waitpid() can wait for a specific child instead of the first child if child has terminated already (it’s a zombie), wait returns immediately, cleaning up the process table data structures for the child Processes — slide 66 Part of Simple Shell Program Windows and Processes — 2 Win32 uses handles for almost all objects such as files, pipes, sockets, processes and events handles can be inherited from parent No proper parent-child relationship ◦ caller of CreateProcess() could be considered as parent ◦ but child cannot determine it’s parent OSSI — ver. 1.5 Processes — slide 69 int main( int argc, char ∗∗argv ) { char ∗prog name = basename( ∗argv ); print prompt( prog name ); read command(); for ( ;; ) { int pid = fork(); if ( pid == 0 ) { execvp( args[ 0 ], args ); } wait( NULL ); print prompt( prog name ); read command(); } } OSSI — ver. 1.5 Processes — slide 67 Windows and Processes Windows provides a Win32 API call to create a process: CreateProcess() Creates a new process, loads program into that process CreateProcess() takes ten parameters Processes — slide 68      OSSI — ver. 1.5      ‡ —   ‡˜ 7 ’‡  ƒ„ CreateProcess() is much more complicated than pid_t fork( void ); Four of the parameters point to structs, e.g., ◦ LPSTARTUPINFO points to a struct with 4 members ◦ LPPROCESS INFORMATION points to a struct with 18 members!     ‡ —   ‡˜ 7 ’‡  ƒ„ Creation flags: OSSI — ver. 1.5 prototype Can Specify Program in either 1st or 2nd parameter: ◦ first: location of program to execute ◦ second: command line to execute ◦ if 0, runs in existing window Processes — slide 71 BOOL CreateProcess ( LPCTSTR lpApplicationName, // pointer to executable module LPTSTR lpCommandLine, // pointer to command line string LPSECURITY ATTRIBUTES lpProcessAttrib, // process security LPSECURITY ATTRIBUTES lpThreadAttrib, // thread security BOOL bInheritHandles, // handle inheritance flag DWORD dwCreationFlags, // creation flags LPVOID lpEnvironment, // pointer to new environment block LPCTSTR lpCurrentDirectory, // pointer to current dir name LPSTARTUPINFO lpStartupInfo, // pointer to STARTUPINFO LPPROCESS INFORMATION lpProcessInformation // pointer to // PROCESS INFORMATION ); OSSI — ver. 1.5 Processes — slide 70 Example: ‡ — ‡ #include #include void main() { STARTUPINFO si; PROCESS INFORMATION pi; memset( &si, 0, sizeof( si ) ); si.cb = sizeof(si); if ( ! CreateProcess( NULL, "..\\..\\print\\Debug\\print.exe 5 100", NULL, NULL, TRUE, 0, NULL, NULL, &si, &pi) ) fprintf( stderr, "CreateProcess failed with %d\n", GetLastError() ); WaitForSingleObject( pi.hProcess, INFINITE ); CloseHandle( pi.hProcess ); CloseHandle( pi.hThread ); } OSSI — ver. 1.5 7 ˜ ’‡  ƒ„ Processes — slide 72 Processes in Linux, Unix, Windows Linux often provides 2 or more processes per application Windows have one process per application, but often 2 or more threads Windows CreateProcess() more takes time than fork() — exec() CreateThread() takes very much less time than CreateProcess() Processes — slide 73 How Processes can Talk to Each Other Problem with Processes Communication! Processes cannot see the same variables Must use Inter Process Communication (IPC) IPC Techniques include: ◦ pipes, and named pipes (FIFOs) ◦ sockets ◦ messages and message queues ◦ shared memory regions All have some overhead Processes — slide 75     Example: apache web server parent process watches for connections, one child process per client Linux processes have much less overhead than in Windows     fork() — exec() very efficient posix threads are very efficient, and faster than fork() — exec()     OSSI — ver. 1.5              OSSI — ver. 1.5 Interprocess Communication (IPC) Pipe — circular buffer, can be written by one process, read by another ◦ related processes can use unnamed pipes – used in shell programming, e.g., the vertical bar ‘|’ in $ " )! §¨™ ◦ unrelated processes can use named pipes — sometimes called fifos Messages — posix provides system calls msgsnd() and msgrcv() ◦ message is block of text with a type IPC Inter Process Communication   ◦ each process has a message queue, like a mailbox ◦ processes are suspended when attempt to read from empty queue, or write to full queue. OSSI — ver. 1.5 Processes — slide 76 ¤£© d &¢ %! § IPC — Shared Memory Shared Memory — a Common block of memory shared by many processes Fastest way of communicating Requires synchronisation (See slide 48) Processes — slide 77 Signals and the Shell We can use the built in command to make the call to send a signal system        OSSI — ver. 1.5 IPC — Signals Some signals can be generated from the keyboard, i.e.,  Control-C © ¨ ¨   — interrupt (SIGINT);  Control-\ © quit (SIGQUIT),  — Control-Z © — stop (SIGSTOP) A process sends a signal to another process using the tem call sys ¨       signals are implemented as single bits in a field in the pcb, so cannot be queued A process may respond to a signal with: ◦ a default action (usually process terminates) ◦ a signal handler function (see notes), or in shell programming % uv '%!   # %ef '%!          A shell script uses the built in command to handle a signal Ignoring the signals SIGINT, SIGQUIT and SIGTERM: trap "" INT QUIT TERM Handling the same signals by printing a message then exiting: trap "echo ’Got a signal; exiting.’;exit 1" INT QUIT TERM Handling the same signals with a function call: signal_handler() { echo "Received a signal; terminating." rm -f $temp_file exit 1 } trap signal_handler INT QUIT TERM Sending a SIGKILL signal to process with pid 3233: $ OSSI — ver. 1.5 gg hih h ©£ ¨ ¡ Processes — slide 79 ◦ ignore the signal (unless it is SIGKILL or SIGSTOP) A process cannot ignore, or handle a SIGSTOP or a SIGKILL signal. ◦ A KILL signal will always terminate a process (unless it is in interruptible sleep) ◦ A SIGSTOP signal will always send a process into the stopped state. OSSI — ver. 1.5 Processes — slide 78   ©£ ¨ ¡ Threads % uv '%! '%! % Lightweight processes that can talk to each other easily Threads share a lot Changes made by one thread to shared system resources (such as closing a file) will be seen by all other threads. Two pointers having the same value point to the same data. Threads and Processes Threads in a process all share the same address space Communication easier Overhead less Problems of locking and deadlock a major issue Processes have separate address spaces Communication more indirect: ipc (Inter Process Communication) Overhead higher Less problem with shared resources (since fewer resources to share!) Processes — slide 81          A number of threads can read and write to the same memory locations, and so you need to explicitly synchronise access Processes — slide 83 OSSI — ver. 1.5           Threads in Linux, Unix OSSI — ver. 1.5 Threads have own. . .       stack pointer register values scheduling properties, such as policy or priority set of signals they can each block or receive own stack data (local variables are local to thread) Processes — slide 82   OSSI — ver. 1.5 OSSI — ver. 1.5 " ! j %(! u v klmf no ©§ 3 £¢ ) j $ ◦ or in Emacs, C-H m libc then middle-click on POSIX threads Provides: ◦ semaphores, ◦ mutexes and ◦ condition variables for locking (synchronisation) Processes — slide 84     posix is a standard for Unix Linux implements posix threads On Red Hat 8.x, documentation is at : a simple threaded program  7‰ ’ #include #include #define NUM THREADS 5 void ∗ print hello( void ∗threadid ) { printf( "\n%d: Hello World!\n", threadid ); pthread exit( NULL ); } int main() { pthread t threads[ NUM THREADS ]; int rc, t; for ( t = 0; t < NUM THREADS; t++ ) { printf( "Creating thread %d\n", t ); rc = pthread create( &threads[ t ], NULL, print hello, ( void ∗ ) t ); if ( rc ) { printf( "ERROR; pthread create() returned %d\n", rc ); exit( −1 ); } } pthread exit( NULL ); } #include void * pthread_create( pthread_t *thread, pthread_attr_t *attr, void *(*start_routine)(void *), void *arg );    returns: 0 if successfully creates thread returns error code otherwise Processes — slide 87 OSSI — ver. 1.5 OSSI — ver. 1.5 Processes — slide 85 How to Compile a POSIX Threads Program Need to use the libpthread library ◦ Specify this with the option -lpthread Need to tell the other libraries that they should be reentrant (or “thread safe”) ◦ This means that the library uses no static variables that may be overwritten by another thread ◦ Specify this with the option -D REENTRANT So, to compile the program program .c, do: $ program program     qr uvs twx xyz s} | €‚ ~ s„ ƒ w{yz OSSI — ver. 1.5 Processes — slide 86 …r       ‡ p – ’ ‡ ‡  ƒ„ parameters: OSSI — ver. 1.5 8   Quite different from fork() Thread must always execute a user-defined function 1. pointer to thread identifier 2. attributes for thread, including stack size 3. user function to execute 4. parameter passed to the user function Processes — slide 88 ‡  ƒ„ ‡ p‰ ‡ p 8 ’ ‡ – Problem with threads: Avoid 2 or more threads writing or reading and writing same data at the same time Avoid data corruption Need to control access to data, devices, files Need locking Provide three methods of locking: ◦ mutex (mutual exclusion) ◦ semaphores ◦ condition variables OSSI — ver. 1.5 Processes — slide 89 Critical Sections critical resource — a device, file or piece of data that cannot be shared                 critical section — part of program only one thread or process should access contains a critical resource ◦ i.e., you lock data, not code All the code in the previous slide is a critical section Consider the code: very_important_count++; executed by two threads on a multiprocessor machine (smp = symmetric multiprocessor) Processes — slide 92 OSSI — ver. 1.5 Race Condition Race Conditions race condition — where outcome of computation depends on sheduling an error in coding Example: two threads both access same list with code like this:      Race Condition — one possibility thread 1 read very important count (5) add 1 (6) write very important count (6) read very important count (6) add 1 (7) Processes — slide 91 OSSI — ver. 1.5 write very important count (7) Processes — slide 93 thread 2 if ( list.numitems > 0 ) { // Oh, dear, better not change to // other thread here! remove_item( list ); // not here! // ...and not here either: --list.numitems; } OSSI — ver. 1.5 Example — another possibility thread 1 read very important count (5) read very important count (5) add 1 (6) add 1 (6) write very important count (6) OSSI — ver. 1.5 write very important count (6) Processes — slide 94 thread 2 File Locking For example, an system call can be used to provide exclusive access to an open file The call is atomic ◦ It either: – completely succeeds in locking access to the file, or – it fails to lock access to the file, because another thread or process holds the lock – No “half-locked” state ◦ No race condition Alternatives can result in race conditions; for example: ◦ thread/process 1 checks lockfile ◦ thread/process 2 checks lockfile a very short time later ◦ both processes think they have exclusive write access to the file ◦ file is corrupted by two threads/processes writing to it at the same time       Solution: Synchronisation OSSI — ver. 1.5  % ' uv Processes — slide 96      Solution is to recognise critical sections use synchronisation, i.e., locking, to make sure only one thread or process can enter critical region at one time. Methods of synchronisation include: ◦ file locking ◦ semaphores ◦ monitors ◦ spinlocks ◦ mutexes Methods of Synchronisation Processes — slide 95 OSSI — ver. 1.5 What is it? mutex, semaphore, condition variables, monitor, spinlock Semaphores A variable with three opererations: ◦ initialise to non-negative value ◦ down (or wait) operation: – decrement variable – if variable becomes negative, then process or thread executing the down operation is blocked – has nothing to do with the wait system call for a parent process to get status of its child ◦ up (or signal ) operation: – increment the semaphore variable; – if value is not positive, then a process or thread blocked by a down operation is unblocked. A semaphore also has a queue to hold processes or threads waiting on the semaphore. Processes — slide 99 Synchronisation Synchronisation is a facility that enforces ◦ mutual exclusion and ◦ event ordering Required when multiple active processes or threads can access shared address spaces or shared i/o resources even more critical for smp (Symmetric Multiprocessor) systems ◦ kernel can run on any processor ◦ all processors are of equal importance (there is no one cpu that is the “boss”) ◦ smp systems include pcs with more than one cpu, as you might find in the Golden Shopping Centre OSSI — ver. 1.5 Processes — slide 98           OSSI — ver. 1.5 Semaphores — 2 The up and down semaphore operations are atomic ◦ the up and down operations cannot be interrupted ◦ each routine is a single, indivisible step Using semaphores—pseudocode mutex — posix Threads Example (1) It is good practice to put the mutex together with the data it proects I have removed the error checking from this example to save space—in real code, always check library calls for error conditions     /∗ only one process can enter critical section at one time: ∗/ semaphore s = 1; down( s ); /∗ critical section ∗/ up( s );     #include #include struct { pthread mutex t mutex; /∗ protects access to value ∗/ int value; /∗ Access protected by mutex ∗/ } data = { PTHREAD MUTEX INITIALIZER, 0 }; OSSI — ver. 1.5 Processes — slide 102 Initialise semaphore to number of processes allowed into critical section at one time Processes — slide 100   OSSI — ver. 1.5 mutex — posix Threads Example (2) #define NUM THREADS 5 Mutex—posix and Win32 Threads     mutual ex clusion Easier to use than semaphores (see slide 50) When only one thread or process needs to write to a resource ◦ all other writers refused access A special form of the more general semaphore ◦ Can have only two values; ◦ sometimes called binary semaphores. void ∗thread( void ∗t id ) { int i; for ( i = 0; i < 200; ++i ) { pthread mutex lock( &data.mutex ); ++data.value; printf( "thread %d: data value = %d\n", t id, data.value ); pthread mutex unlock( &data.mutex ); } pthread exit( NULL ); }   OSSI — ver. 1.5 Processes — slide 101 OSSI — ver. 1.5 Processes — slide 103 mutex — posix Threads Example (3) Monitors int main() { pthread t threads[ NUM THREADS ]; int rc, t; for ( t = 0; t < NUM THREADS; t++ ) { printf( "Creating thread %d\n", t ); pthread create( &threads[ t ], NULL, thread, ( void ∗ ) t ); } pthread exit( NULL ); }       A higher level structure for synchronisation Implemented in Java, and some libraries main characteristics: ◦ data in monitor is accessible only to procedures in monitor ◦ a process or thread enters monitor by executing one of its procedures ◦ Only one process or thread may be executing in the monitor at one time. Can implement with mutexes and condition variables. Processes — slide 106 OSSI — ver. 1.5 Processes — slide 104 OSSI — ver. 1.5 Spinlocks    Lets threads sleep till a condition about shared data is true Basic operations: ◦ signal the condition (when condition is true) ◦ wait for the condition – suspend the thread till another thread signals the condition       posix Condition Variables Used in operating system kernels in smp systems Linux uses kernel spinlocks only for smp systems a very simple single-holder lock if can’t get the spinlock, you keep trying (spinning) until you can. Spinlocks are: ◦ very small and fast, and ◦ can be used anywhere     Always associated with a mutex Very useful Missing from Windows: See ∼schmidt/win32-cv-1.html http://www.cs.wustl.edu/ Processes — slide 105 OSSI — ver. 1.5 Processes — slide 107 OSSI — ver. 1.5 Summary and References Summary — Processes and Threads   §¤   § uv 1£ ! ¨ uv ©§ † £§ ¨ © k §¢¢ uv With Linux and Unix, main process system calls are , and — understand the function of each of these Windows provides Win32 api calls ◦ The and various calls have a purpose similar to that of the system call in Linux and Unix Threads are lightweight processes ◦ part of one process ◦ share address space ◦ can share data easily ◦ sharing data requires synchronisation, i.e., locking   OSSI — ver. 1.5 1£ ! ¨ uv £ ‡ ¨© ˆ! ‰‰‰ uv Processes — slide 110 Summary — Process States, Scheduling Scheduler changes processes between ready to run and running states ◦ context switch: when scheduler changes process or thread Most processes are blocked, i.e., sleeping: waiting for i/o ◦ understand the process states ◦ why a process moves from one state to another Communication between processes is not trivial; ipc methods include ◦ pipes ◦ messages ◦ shared memory ◦ signals ◦ semaphores OSSI — ver. 1.5 Processes — slide 109 Summary — Synchronisation When two threads of execution can both write to same data or i/o, ◦ Need enforce discipline ◦ Use synchronisation We looked at the following methods of synchronisation: ◦ semaphore ◦ mutex ◦ condition variable ◦ monitor ◦ spinlock There are other methods we have not examined here. Processes — slide 111             OSSI — ver. 1.5 ‰‰‰ £ ¨ ‡! © ˆ uv © ' uv References There are many good sources of information in the library and on the Web about processes and threads. Here are some I recommend: Š Š Š Š ŠŠ Š ŠŠŠ A good online tutorial about posix threads: http://www.llnl.gov/computing/tutorials/ workshops/workshop/pthreads/MAIN.html http://www.humanfactor.com/pthreads/ provides links to a lot of information about posix threads The best book about posix threads is Programming with POSIX Threads, David Butenhof, Addison-Wesley, May 1997. Even though it was written so long ago, David wrote much of the posix threads standard, so it really is the definitive work. It made me laugh, too! Operating Systems: A Modern Perspective: Lab Update, 2nd Edition, Gary Nutt, AddisonWesley, 2002. A nice text book that emphasises the practical (like I do!) Microsoft msdn provides details of Win32 api calls and provides examples of code. William Stallings, Operating Systems, Fourth Edition, Prentice Hall, 2001, chapters 3, 4 and 5 Deitel, Deitel and Choffnes, Operating Systems, Third Edition, Prentice Hall, 2004, ISBN 0-13-1182827-4, chapters 3, 4 and 5 Paul Rusty Russell, Unreliable Guide To Locking http://kernelnewbies.org/documents/ kdoc/kernel-locking/lklockingguide.html W. Richard Stevens, Advanced Progamming in the UNIX Environment, Addison-Wesley, 1992 Eric S. Raymond, The Art of UNIX Programming, Addison-Wesley, 2004, ISBN 0-13142901-9. OSSI — ver. 1.5 Processes — slide 112