Wiley.Symbian.OS.Internals.Real.time.Kernel.Programming.Dec.2005.eBook-DDU (779891), страница 24
Текст из файла (страница 24)
We set the ‘‘DLL’’ type bit and clear the Win32 entry point3. We load the copy as a DLL4. We find the Symbian OS entry point by looking for the _E32Startupexport.As a result, if you set the target type to EXE, then the tool chain createsa file that can bootstrap the emulator and that can also be loaded as aprocess within the emulator multiple times.3.5.1.2 Entry pointsThe DLL and EXE entry point scheme used in the emulator has beenchanged, allowing the emulator to fully control how and when thesefunctions are called. It also enables the Symbian OS ‘‘EXE’’ scheme I havejust described.The entry point in a Win32 DLL is not used at all, and the entry pointfor a Win32 EXE merely bootstraps the emulator by calling BootEpoc().The Symbian OS entry points are implemented by exporting a namedsymbol from the DLL or EXE. The DLL entry point is ‘‘_E32Dll ’’ andthe EXE entry point is ‘‘_E32Startup ’’.
The export management toolsrecognize these symbols and ensure that they are not included in frozenexports files and are always exported by name as the last symbol fromthe file.98THREADS, PROCESSES AND LIBRARIES3.6 SchedulingEKA2 implements a priority-driven, preemptive scheduling scheme. Thehighest-priority ready thread, or one of several ready threads of equalhighest priority, will usually run. (The exception, which I discussed earlier,is when a high-priority thread is waiting on a nanokernel fast mutex heldby a lower-priority thread – in this case, the lower-priority thread runs.)Within Symbian OS, scheduling is the responsibility of the nanokernel.Threads that are eligible for execution (that is, threads that are not waitingfor an event) are called ‘‘ready’’ and are kept on a priority-ordered list,the ready list.Each nanothread has an integer priority between 0 and 63 inclusive.As we have said, the highest-priority thread that is ready to run will run.
Ifthere are several threads at the same priority, then one of two things mayhappen. Firstly, the threads may be executed in a round-robin fashion,with the timeslice selectable on a thread-by-thread basis. Secondly, theymay be executed in FIFO order – that is the first thread to become ready atthat priority will run until it blocks and other threads at the same prioritywill not run until the first thread blocks. Which of these two methods ischosen is a property of the thread itself, not the scheduler.Each thread has its own timeslice (iTimeslice) and time count(iTime). Whenever the thread blocks or the kernel rotates the threadto the end of the queue of threads at the same priority, the kernel setsthe iTime field equal to iTimeslice.
The low-level tick interruptthen decrements the current thread’s iTime if it is positive and triggersa reschedule if it becomes zero. So you can see that if iTimesliceis positive, the thread will run for iTimeslice low level timer ticksbefore yielding to the next thread at the same priority. If iTimeslice isnegative, the thread will only yield to other threads at the same priority ifit blocks.The ready list, shown graphically in Figure 3.2, holds all the threadsthat are currently eligible for execution. It is always accessed with thekernel locked so, to maintain low thread latency, operations on theready list need to be bounded and as fast as possible.
We achieve thisby using 64 separate queues, one for each possible thread priority – thekernel places each ready thread in the queue corresponding to its priority.The kernel also maintains a 64-bit mask to indicate which queues haveentries; bit n in the mask is set if and only if the queue for priority n hasentries.So, to insert an entry, the kernel simply adds it to the tail of thequeue corresponding to its priority (no searching is required) and sets thecorresponding bit in the bit mask. To remove an entry, the kernel firstunlinks it from its queue, then, if that queue is now empty, resets the bit inSCHEDULING9964-bit mask001...111...Ready list forhighestpriority = 63Ready list forpriority = nReady list forlowestpriority = 00Thread AiQueue [63]iQueue [n]iQueue [0]nth bit setimplies ready listfor priority n hasentriesFigure 3.2 The ready listthe bit mask.
To find the highest-priority entry, the kernel finds the mostsignificant 1 in the bit mask (which can be done with a binary search orwith a single instruction on some CPUs), and then finds the first entry onthe corresponding queue. You can see that this implementation gives usbounded (and small) execution times for insertion and removal of entriesand for finding the highest-priority entry.To save on memory, we use a single pointer for each queue.
This isNULL if the queue is empty, otherwise it points to the first entry on thequeue. We arrange the entries in the queue in a doubly linked ring. Weuse the same priority ordered list implementation for DFC queues, andsemaphore and mutex wait queues.The kernel also maintains a flag (TheScheduler.iRescheduleNeededFlag) that indicates whether a thread switch may be required. Itsets this flag whenever it adds a thread to the ready list, and that thread’spriority is greater than the highest priority of any other thread already onthe list. The nanokernel timer tick interrupt also sets this flag when thecurrent thread’s timeslice has expired.When the kernel subsequently becomes unlocked, it checks this flagto determine whether a reschedule is needed, and clears the flag when itperforms the reschedule.The scheduler is responsible both for running IDFCs (immediatedeferred function calls) and for selecting the next thread to run andswitching to it.
It does not do any page table manipulations to switch processes – instead it provides a hook that the Symbian OS memory modeluses to arrange for such code to be called.100THREADS, PROCESSES AND LIBRARIESHere is a summary of the scheduler control block:FieldDescriptioniPresent[2]64-bit mask with a 1 in bit position n if and only ifiQueue[n] is non-empty, that is, if and only if there is athread of priority n on the ready list.iQueue[64]64 pointers, one for each possible thread priority. If there isno ready thread at priority n, iQueue[n]=NULL, elseiQueue[n] points to the first ready thread at priority n.iRescheduleNeededFlagBoolean flag that is set if a reschedule is needed when thekernel is locked, and cleared by the scheduler when it runs.iDfcPendingFlagBoolean flag, set when an IDFC is queued and clearedwhen all pending IDFCs have been processed.iKernCSLockedThe kernel lock (otherwise known as the preemption lock).iDfcsDoubly linked list of pending IDFCs.iMonitorExceptionHandler Pointer to exception handler installed by the crashdebugger.iProcessHandlerPointer to the process address space switch handler in theSymbian OS memory model.iLockThe system lock fast mutex.iCurrentThreadPointer to the currently executing NThread.iAddressSpaceThe identifier of the currently active process address space.iExtras[16]Space reserved for extra data used by the Symbian OSprocess switch handler.Now let’s look at the full scheduler algorithm.
Before we start, we’lldefine some terms.Non-volatile registers: those CPU registers that are preserved across afunction call (r4–r11 and r13 on ARM).CPU-specific registers: those registers, outside the normal supervisormode register set, that are required to exist on a per-thread basis. Exampleson ARM include the DACR (domain access control register, CP15 CR3)and user mode R13 and R14.System lock: a fast mutex, iLock, which the kernel uses to protectaddress space changes, among other things.SCHEDULING101Kernel lock: a counter, iKernCSLocked, which is always ≥ 0.
Zerois the normal state and indicates that IDFCs and a reschedule may runimmediately following an interrupt. Non-zero values indicate that IDFCsand reschedules must be deferred until the count is decremented to zero.Also known as the preemption lock.The kernel calls the scheduler in two different situations. The first is at theend of an interrupt service routine, if the following conditions are met:1. IDFCs are pending or a reschedule is pending2. The kernel is not locked (iKernCSLocked==0)3.
On ARM the interrupted mode must be usr or svc. (Other modes arenon-preemptible since they don’t have per-thread stacks.)The kernel also calls the scheduler when it becomes unlocked (iKernCSLocked decrements to zero), if the following condition is met:4. Either IDFCs are pending or a reschedule is pending. (This will be thecase if the current thread has just completed a nanokernel functionthat has blocked it or made a higher-priority thread ready.)Here is the full scheduler algorithm for the moving memory model:// Enter with kernel locked// Active stack is supervisor stack of current thread12345678910111213141516171819202122232425Disable interruptsstart_resched:IF IDFCs pending (iDfcPendingFlag TRUE)Run IDFCs (with interrupts enabled but kernel locked)iDfcPendingFlag = FALSEENDIFIF reschedule not needed (iRescheduleNeededFlag FALSE)iKernCSLocked=0 (unlock the kernel)ReturnENDIFReenable interruptsSave nonvolatile registers and CPU specific registers on stackiCurrentThread->iSavedSP = current stack pointeriRescheduleNeededFlag = FALSEnext_thread = first thread in highest priority non-empty ready queueIF next_thread->iTime==0 (ie timeslice expired)IF another thread is ready at same priority as next_threadIF next_thread holds a fast mutexnext_thread->iHeldFastMutex->iWaiting=TRUEgoto resched_endENDIFnext_thread->iTime=next_thread->iTimeslice (new timeslice)next_thread=thread after next_thread in round-robin orderENDIFENDIF102262728293031THREADS, PROCESSES AND LIBRARIES394041424344454647484950515253545556575859606162636465666768697071IF next_thread holds a fast mutexIF next_thread holds system lockgoto resched_endENDIFIF next_thread requires implicit system lockIF system lock is held OR next_thread requires address spaceswitchnext_thread->iHeldFastMutex->iWaiting=TRUEENDIFENDIFgoto resched_endENDIFIF next_thread is blocked on a fast mutexIF next_thread->iWaitFastMutex->iHoldingThread (mutex is stilllocked)next_thread=next_thread->iWaitFastMutex->iHoldingThreadgoto resched_endENDIFENDIFIF next_thread does not require implicit system lockgoto resched_endENDIFIF system lock held by another threadnext_thread=system lock holding threadsystem lock iWaiting = TRUEgoto resched_endENDIFIF thread does not require address space switchgoto resched_endENDIFiCurrentThread=next_threadcurrent stack pointer = next_thread->iSavedSPRestore CPU specific registers from stacksystem lock iHoldingThread = next_threadnext_thread->iHeldFastMutex = system lockUnlock kernel (scheduler may go recursive here, but only once)Invoke address space switch handlerLock the kernelsystem lock iHoldingThread = NULLnext_thread->iHeldFastMutex = NULLIF system lock iWaiting (there was contention for the system lock)system lock iWaiting = FALSEiRescheduleNeededFlag = TRUE (so we reschedule again)IF next_thread has critical section operation pendingDo pending operationENDIFENDIFgoto switch_threads72737475resched_end:// switch threads without doing process switchiCurrentThread=next_threadcurrent stack pointer = next_thread->iSavedSPRestore CPU specific registers from stack76777879switch_threads:Restore nonvolatile registers from stackDisable interruptsIF IDFCs pending or another reschedule needed32333435363738SCHEDULING80818283103goto start_reschedENDIFiKernCSLocked=0 (unlock the kernel)Return with interrupts disabledLines 1–10 are concerned with running IDFCs.
We check for the presenceof IDFCs with interrupts disabled, since an interrupt could add an IDFC.If IDFCs are present, we call them at this point; we do this with interruptsenabled and with the kernel locked. IDFCs run in the order in whichthey were added to the queue. An IDFC could add a thread to theready list; if that thread has a sufficiently high priority, the kernel setsiRescheduleNeededFlag. We remove each IDFC from the pendingqueue just before we execute it. We then disable interrupts again andmake another check to see if more IDFCs are pending.
If there are nomore IDFCs, the kernel clears the iDfcPendingFlag. Interrupts are stilldisabled here. Next we check iRescheduleNeededFlag. This couldhave been set in several different ways:1. By the current thread just before calling the scheduler (for example ifthat thread needs to block waiting for an event)2.