chapter4操作系统.ppt

1、The OS kernel: Implementing processes and Threads,Kernel Definitions and Objects Queue Structures Threads Implementing Processes and Threads Implementing Synchronization and Communication Mechanisms Interrupt Handling,Kernel Definitions and Objects,Process and thread management Interrupt and trap ha

2、ndling Resource management Input and output,OS kernel: a basic set of objects, primitive operations, data structures, and processes from which the remainder of the system may be constructed,Kernel,Interactions with kernel objects,A Process Creation Hierarchy,Queue structures,Queues in OSs -queue for

3、 PCB -queues for hardware managers -queues for synchronization -queues for shared software components Implementations of Queues -single-level queues -priority queues,Implementations of queues,Types of queues: -FIFO -priority based,Elements of queues,Operations related to queues -insert( queue Q, ele

4、ment x) -remove( queue Q, element x) -empty( queue Q),Header or descriptor of queues,Single-Level Queues,Circular array Linked list,Priority queues,Fixed-number priorities,Queue pointer,front,rear,0,1,. . .,i,. . .,N-1,. . .,. . .,. . .,Binary heap,1125,Threads,The normal implementation of processes

5、 results in much runtime overhead. To alleviate this problem, multiple “lightweight” scheduling units is implemented within a process. These units share the same resources as there host process,Create a new thread; Initiate or make a thread ready; Destroy or terminate a thread; Delay or terminate a

6、thread Delay or put a thread to sleep for a given amount of time; Synchronize threads through semaphores, events or condition variables; Perform lower-level operations, such as blocking, suspending, or scheduling a thread,Operations on threads:,Implementing processes and threads,Process and thread d

7、escriptors Implementing operations on processes Operations on threads,PCB,Identification State vector Processors Status information Creation tree other information,Structure of process descriptor,PCB,ID,Cpu_state,Processor_ID,memory,Open_files,Other_resources,list,type,priority,parent,child,. . .,pr

8、ocessors,resources,State vector,status,Creation_tree,Other information,State vector,Status information,Implementing operations on processes,Create Create(so,mo,pi,pid) p=Get_New_PCB(); pid=Get_New_PID(); p-ID=pid; p-CPU_State=s0; p-Memory=m0; p-Priority=pi; p-State.Type=“ready_s”; p-Creation_tree.Pa

9、rent=self; p-Creation_Tree.child=NULL; insert(self-Creation_tree.child,p); insert(RL,p); Scheduler(); ,Suspend suspend(pid) p=Get_PCB(pid); s=p-Status.Type; if(s=“blocked_a”)|(s=“blocked_s”) p-status.Type=“block_s”; else p-status.Type=“ready_s”; if(s=“running”) cpu=p-Processor_ID; p-CPU_State=Interr

10、upt(cpu); Scheduler(); ,Activate Activate(pid) p=Get_PCB(pid) if(p-Status.Type=“ready_s”) p-Status.Type=“ready_a”; Scheduler(); else p-status.Type=“blocked_a”; ,Destroy Destroy(pid) p=Get_PCB(pid); Kill_Tree(p); Scheduler(); Kill_Tree(p) for(each q in p-Creation_Tree.Child) Kill_Tree(q); if(p-Status

11、.Type=“running”) cpu=p-Processor_ID Interrupt(cpu); Remove(p-Status.List,p); Release_all(p-Memory); Release_all(p-Other_Resources); Close_all(p-Open_Files); Delete_PCB(p); ,Implementing synchronization and communication mechanisms,Semaphores and locks Monitor primitives Clock and time management Com

12、munication,General version of the Request/Release,Request(res) if(Free(res) Allocate(res,self); else Block(self,res); Scheduler(); Release(res) Deallocate(res,self); if(Process_Blocked_on(res,pr) Allocate(res,pr); Unblock(pr,res); Scheduler(); ,Semaphores and locks,BT：carry appointed bit to CF; BTC：

13、 carry appointed bit to CF, and reverse it; BTR： carry appointed bit to CF, and change it to 0; BTS： carry appointed bit to CF, and change it to 1;,Bit Test Instruction :,Spin Locks on Binary Semaphores,Pb(sb): do TS(R,sb); while(!R);/*wait loop*/ Vb(sb): sb=1;,General Semaphores with spin locks,P p

14、(s) s=s-1; if(s0) Pb(delay_s; V v(s) s=s+1; if(s=0) Vb(delay_s); else ,Pb(mutex_s);,Vb(mutex_s);,Vb(mutex_s);,Pb(mutex_s);,Vb(mutex_s);,Avoiding the Busy-Wait,P(s) Inhibit_Interrupts; Pb(mutex_s); s=s-1; if(s0) Block(self, Ls); Vb(mutex_s); Enable_Interrupts; Scheduler(); else Vb(mutex_s); Enable_In

15、terrupts; ,V(s) Inhibit_Interrupts; Pb(mutex_s); s=s+1; if(s=0) Unblock(q, Ls); Vb(mutex_s); Enable_Interrupts; Scheduler(); else Vb(mutex_s); Enable_Interrupts; ,Primitive and atomic operation,Priority Interrupt request Switching tasks on single CPU Switching tasks on multiple CPU,struct semaphore

16、atomic_t count; int sleepers; wait_queue_head_t wait; #if WAITQUEUE_DEBUG long _magic; #endif ;,static inline void down(struct semaphore * sem) #if WAITQUEUE_DEBUG CHECK_MAGIC(sem-_magic); #endif _asm_ _volatile_( # atomic down operationnt LOCK decl %0nt /* -sem-count */ js 2fn 1:n LOCK_SECTION_STAR

17、T() 2:tcall _down_failednt jmp 1bn LOCK_SECTION_END :=m (sem-count) :c (sem) :memory); ,asm( .textn .align 4n .globl _down_failedn _down_failed:nt #if defined(CONFIG_FRAME_POINTER) pushl %ebpnt movl %esp,%ebpnt #endif pushl %eaxnt pushl %edxnt pushl %ecxnt call _downnt popl %ecxnt popl %edxnt popl %

18、eaxnt #if defined(CONFIG_FRAME_POINTER) movl %ebp,%espnt popl %ebpnt #endif ret );,void _down(struct semaphore * sem) struct task_struct *tsk = current; DECLARE_WAITQUEUE(wait, tsk); tsk-state = TASK_UNINTERRUPTIBLE; add_wait_queue_exclusive( ,static inline void spin_lock(spinlock_t *lock) #if SPINL

19、OCK_DEBUG _label_ here; here: if (lock-magic != SPINLOCK_MAGIC) printk(eip: %pn, nopnt jle 2bnt jmp 1bn LOCK_SECTION_END,#define spin_lock_irq(lock)do local_irq_disable(); spin_lock(lock); while (0),Monitor primitives,Body of each procedure: p(mutex); procedure_body; if(urgentcnt) V(urgent); else V(

20、mutex); C.wait: condcnt_c=condcnt_c+1; if(urgentcnt) V(urgent); else V(mutex); P(condsem_c) condcnt_c=condcnt-1; C.signal: if(condcnt_c) urgentcnt=urgentcnt+1; V(condsem_c); P(urgent); urgentcnt=urgentcnt-1; ,Clock and Time Management,Wall clock timer - Update_clock - Get_Time - SetClock(tnew),Count

21、down Timers - Set_Timer(tdel) - Delay(tdel) Delay(tdel) Set_timer(tdel); P(delsem); - TimeOut() TimeOut( ) V(delsem): ,Implementing logical timers,Logical timer - tn=Create_LTimer(); - Destroy_LTimer(tn); - SetLTimer(tn,tdel);,Using a Priority Queue with Absolute Wakeup Times,Hardware timers,Wall-clock,countdown,103,12,Timer queue,TQ,a,b,TQ,Using a Priority Queue with Time Differences,Hardware timers,countdown,12,Timer queue,TQ,a,b,TQ,Communication primitives,Generic form of message-passing primitives - send(p,m) - receive(q, m) Two issues must be resolved - how does the sender know that s