《考川大,操作系统重点打印版(一卷再手,os不愁)》由会员分享，可在线阅读，更多相关《考川大,操作系统重点打印版(一卷再手,os不愁)（6页珍藏版）》请在金锄头文库上搜索。
1、进程：线程：调度队列的种类：1.job queue set of all processes in the system2.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 creat
2、ed2.running: instructions are being executed3.waiting: waiting for some event to occur4.ready: waiting to be assigned to a processor5.terminated: has finished executionFCB 的内容：1.Process state2.Program counter3.CPU registers4.CPU scheduling information5.Memory-management information6.Accounting infor
3、mation7.I/O status information8.page table or relocation register and limit register9.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 a
4、nd allocates CPU生产者-消费者问题（指利用了 n-1 个单元）shared data#define BUFFER_SIZE 10typedef struct . . . item;item bufferBUFFER_SIZE;int in = 0;int out = 0;item nextProduced; / local variablewhile (1) /* produce an item in nextProduced */while (in + 1) % BUFFER_SIZE) = out);bufferin = nextProduced;in = (in + 1)
5、 % BUFFER_SIZE;item nextConsumed; / local variablewhile (1) while (in = out); / buffer is emptynextConsumed = bufferout;out = (out + 1) % BUFFER_SIZE;/* consume the item in nextConsumed */用户线程和内核线程User threads：supported above the kernelimplemented by a thread library at the user levelthe library sup
6、port 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 processKernel threads：supported directly by the operating system: the kernel performs thread creation, scheduling, and manage
7、ment in kernel spaceslower to create and manage than user threadsindependent block among threadsgood support for multiprocessorsMany to one：many user-level threads mapped to single kernel threadthread management is done in user space，used on systems that do not support kernel threadsdrawbacks：bad bl
8、ockingbad ，utilization of multiprocessorsone to one：each user-level thread maps to a kernel thread：more concurrency than many-to-one，support multiprocessorsdrawback：overhead of creating kernel threadsexamples：Windows 95/98/NT/2000，OS/2many to many：multiplexes many user level threads to a smaller or
9、equal number of kernel threadsallows the programmer to create a sufficient number of user threadsavoid bad blocking, support multiprocessorsExamples：Solaris 2，Windows NT/2000 with the ThreadFiber package 线程的终止：thread cancellationtarget thread: the thread to be cancelledasynchronous cancellation: one
10、 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 resourcedeferred cancellation: the target thread can periodically check if it should terminate (at so called cancellation points in Pthread)同步信号和异步信号：
11、synchronous signalsan illegal memory access, a division by zerodelivered to the same process that cause the signalasynchronous signalsa user keystroke (Ctrl-C), a timer expirationtypically sent to another process线程池：Why the thread pools?1.avoid creation and termination overhead, so that it is faster
12、 to service a request2.put bound on number of threads, thus limit CPU and memory usageconsiderationsnumber of CPUsamount of physical memoryexpected number of concurrent requests进程同步种类： 1.blocking(synchronous) versus nonblocking (asynchronous) 2.blocking send: the sending process is blocked until the
13、 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 re
14、sumes operationCPU 调度算法 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 Critical Section turn = 1- i; Reminder Section while (1); 分析：满足了互斥，但不满足有空让进
15、条件。做为反 例，假设 P0 由于某些原因，还没有运行到与临界区 相关的处理语句就停下来了。这个时候，turn 初始地 为零。那么就算 P1 已经准备好进入自己的临界区， 它也无法进入。算法 2：进程共享变量 boolean flag2和 initially flag 0 = flag 1 = false，这 里，flag i = true 意味着 Pi 已经准备好进入它的临界区了。对于第 i 个进程（i = 0 或 1）： do flagi := true; while (flag1-i); critical section flag i = false; Remainder Section
16、 while (1); 分析：满足了互斥，但不满足有空让进条件。做为反例，假设一次调度使得 P0 刚好执行完了 flagi = true，这个时候 P1 开始执行，当 P1 执行倒同样一 句话后，可以看到，flag0和 flag1都等于 true 这样，两个进程会一直相互等 下去。共享变量 mutex = 1 do wait(mutex); Rritical Section signal(mutex) Remainder Section; while (1); P(S)操作和 V(S)操作： wait (S) while(S 0); S-; signal (S) S+; 信号量的结构： typedef struct int value;struct process *L; semaphore;读者写者问题：进程共享一个读 写空间。采用信号量 mutex，wrt， 共享数据 int readcount，初始值 mutex
