进程：
线程：
调度队列的种类
：
1. job queue – set of all processes in the system
2. ready queue – set of all processes residing in main memory, ready and
waiting to executegenerally stored as a linked list
3. device queues – set of processes waiting for a particular I/O device, eg.
a tape driver, a disk
进程状态
：
1. new: being created
2. running: instructions are being executed
3. waiting: waiting for some event to occur
4. ready: waiting to be assigned to a processor
5.
terminated
: has finished execution
FCB
的内容
：
1. Process state
2. Program counter
3. CPU registers
4. CPU scheduling information
5. Memory-management
information
6. Accounting information
7. I/O status information
8. page table or relocation register
and limit register
9. file open table
调度器
scheduler
分类：
long-term scheduler (or job scheduler) – selects which processes should
be loaded for execution
short-term scheduler (or CPU scheduler) – selects which process should
be executed next and allocates CPU
生产者
-
消费者问题
（
指利用了
n
-
1
个单元
）
shared data
#define BUFFER_SIZE 10
typedef struct {
. . .
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
item nextProduced; // local variable
while (1) {
/* produce an item in nextProduced */
while (((in + 1) % BUFFER_SIZE) == out);
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
}
item nextConsumed; // local variable
while (1) {
while (in == out); // buffer is empty
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
/* consume the item in nextConsumed */
}
用户线程和内核线程
User threads：
supported above the kernel
implemented by a thread library at the user
level
the library support thread creation, scheduling,
management with no support from the kernel
(on a single thread kernel) any user-level
thread performs a blocking system call blocks the
whole process
Kernel threads：
supported directly by the operating system: the
kernel performs thread creation, scheduling, and
management in kernel space
slower to create and manage than user threads
independent block among threads
good support for multiprocessors
M
any to one
：
many user-level threads mapped to single kernel thread
thread management is done in user space，used on systems that do not
support kernel threads
drawbacks：bad blockingbad ，utilization of multiprocessors
one to one：
each user-level thread maps to a kernel thread：more concurrency than
many-to-one，support multiprocessors
drawback：overhead of creating kernel threads
examples：Windows 95/98/NT/2000，OS/2
many to many：
multiplexes many user level threads to a smaller or equal number of
kernel threads
allows the programmer to create a sufficient number of user threads
avoid bad blocking, support multiprocessors
Examples：Solaris 2，Windows NT/2000 with the ThreadFiber package
线程的终止
：
thread cancellation
ü target thread: the thread to be cancelled
ü asynchronous cancellation: one thread immediately terminates the target thread，may be cancelled in the middle of updating
data shared with other threads，may not free a system-wide resource
ü deferred cancellation: the target thread can periodically check if it should terminate (at so called cancellation points in Pthread)
同步信号和异步信号
：
synchronous signals
an illegal memory access, a division by zero
delivered to the same process that cause the
signal
asynchronous signals
a user keystroke (Ctrl-C), a timer expiration
typi
cally sent to another process
线程池
：
Why the thread pools?
1. avoid creation and termination overhead, so that it is faster to
service a request
2. put bound on number of threads, thus limit CPU and memory usage
considerations
number of CPUs
amount of physical memory
expected number of concurrent requests
进程同步种类：
1. blocking(synchronous) versus nonblocking (asynchronous)
2. blocking send: the sending process is blocked until the message is
received by the receiving process or by the mailbox
3. nonblocking send: the sending process sends the message, and
resumes operation
4. blocking receive: the receiver blocks until a message is available
5. nonblocking receive: the receiver retrieves either a valid message
or a null, and resumes operation
CPU
调度算法
1. FCFS：等待时间不稳定，响应时间不稳定。
特点：easy to understand, easy to implement (an FIFO queue), large variance of waiting/response time. convoy effect.
nonpreemptive, bad for time-sharing system
2. SJF：分为 preemptive & nonpreemptive.平均等待时间最短。最优但不实际的调度，是其他算法的判定标准。
3. Priority scheduling：分为 preemptive & nonpreemptive. 存在饥饿的问题，可以通过 aging 的方法来弥补。
4. Round Robin： q large ⇒ FIFO；q small ⇒ q 相对于切换上下文的时间而言不许足够长，否则将导致系统开销过大。time
quantum/slice 用完后，被抢占并插入就绪队列末尾，如果这个进程结束的时候有新进程产生，则挂在该进程的前面。假定
就绪队列中有 n 个进程、时间量为 q, 则每个进程每次得到 1/n 的、不超过 q 单位的成块 CPU 时间，没有任何一个进程的等
待时间会超过(n-1)*q 单位。RR 的平均周转时间比 SJF 长，但响应时间要短一些。
PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
