BYR Achieve · 镜像论坛

Hi There, I’m Stanley Sun from incubation team in ATC. I’m glad to receive your resume. Before going forward to next step. I want to confirm that you can commit a full-time internship in ATC for at least half year. Note, we need your tutor’s permission. Meanwhile, I have a little quiz here I fist want you to understand how CriticalSection works on a Windows system. And then implement your own CriticalSection APIs other user mode APIs such as “event”, InterlockedExchange: The CriticalSection APIs include: InitializeCriticalSection DeleteCriticalSection EnterCriticalSection LeaveCriticalSection Before you start working I would also like to share you some of my experience. A common mistake people made is that they start design the solution without fully understanding the critical section. For example, how does it works if there are multi-thread wait on that critical section, and what will happen if the programmer calling LeaveCriticalSection before they call EnterCriticalSection. There are many situation such as those. So, please dig them out and make your solution as good as possible Best Regards Stanley Sun 答案： //////////////////////////////////////////////////////// //FileName: CriticalSection.h //Version 1.0 //Describe: Defines the struct for CriticalSection.cpp //Author: Nie Bingwen //Date: 2007-11-27 /////////////////////////////////////////////////////// #pragma once #if defined(__cplusplus) extern "C" { #endif // for some basic type definitions #include <windows.h> // traditional thread priority levels #define THREAD_PRIOR_LEVELS 7 // max threads number in a process #define MAX_THREADS_IN_PROCESS 65535 // I guess that Max threads number in a process under Windows System /************************************************************************ to track threads blocked in cretical section, we need certain method to record threads that are waiting for the critical section available, here we exploit list based queue to accomodate this feature ************************************************************************/ // thread handle, in or out queue as a node struct WAIT_THREAD_QUEUE_NODE { HANDLE hWaitingThread; WAIT_THREAD_QUEUE_NODE * next; }; // queue head structure, holding head and tail of the queue. // nPriority is the priority of all threads in the queue. // Note: for different priority threads, there're different queue. struct WAIT_THREAD_QUEUE_HEAD { int nPriority; WAIT_THREAD_QUEUE_NODE * head; WAIT_THREAD_QUEUE_NODE * tail; }; // two queue manipulating function // Param: // QueueArray, the array of queue // nPriority, the priority of thread // hThread, the handle of thread, if needed // Return: // InWaitThreadQueue() return True on success, else False // OutWaitThreadQueue() return a handle to thread, if failed just return NULL static BOOL InWaitThreadQueue( WAIT_THREAD_QUEUE_HEAD * QueueArray, int nPriority, HANDLE hThread ); static HANDLE OutWaitThreadQueue(WAIT_THREAD_QUEUE_HEAD * QueueArray); /******************************************************************* <windows.h> has typedefed CRITICAL_SECTION structure, but it's too bloat for our purpose, to work around this problem, I defined _CRITICAL_SECTION to substitute the old one. some definitions and declarations here are borrowed from winbase.h (which from winnt.h) *******************************************************************/ typedef struct _CRITICAL_SECTION { // control enter and leave the critical section for the resource. // lock counter, do not include recursion lock LONG LockCount; // recursly enter needs recursly leave LONG RecurionCount; // handle for current thread which is in critical section HANDLE OwningThread; // semaphore to sync between group of threads in a process HANDLE LockSemaphore; // queue array for waiting thread group, each group have a queue. // the queue ranks from high priority to low one, i.e., // WaitThreadQueueHead[0] - THREAD_PRIORITY_TIME_CRITICAL // WaitThreadQueueHead[1] - THREAD_PRIORITY_HIGHEST // ... // WaitThreadQueueHead[6] - THREAD_PRIORITY_IDLE WAIT_THREAD_QUEUE_HEAD WaitThreadQueueHead[THREAD_PRIOR_LEVELS]; } * LP_CRITICAL_SECTION; // APIs for maniplating critical section objects VOID WINAPI EnterCriticalSection(LP_CRITICAL_SECTION pcsCriticalSection); VOID WINAPI LeaveCriticalSection(LP_CRITICAL_SECTION pcsCriticalSection); VOID WINAPI InitializeCriticalSection(LP_CRITICAL_SECTION pcsCriticalSection); VOID WINAPI DeleteCriticalSection(LP_CRITICAL_SECTION pcsCriticalSection); BOOL WINAPI TryEnterCriticalSection(IN OUT LP_CRITICAL_SECTION lpcsCriticalSection); #if defined(__cplusplus) }; #endif //////////////////////////////////////////////////////// //FileName: CriticalSection.cpp //Version 1.0 //Describe: Defines the functions of CriticalSection //Author: Nie Bingwen //Date: 2007-11-27 //Modified in 2007-11-29 /////////////////////////////////////////////////////// #include <stdafx.h> #include <stdlib.h> #include "CriticalSection.h" // thread priority map table static const int ThreadPriorityMap[THREAD_PRIOR_LEVELS] = { THREAD_PRIORITY_TIME_CRITICAL, THREAD_PRIORITY_HIGHEST, THREAD_PRIORITY_ABOVE_NORMAL, THREAD_PRIORITY_NORMAL, THREAD_PRIORITY_BELOW_NORMAL, THREAD_PRIORITY_LOWEST, THREAD_PRIORITY_IDLE }; /********************************************************************* implementation of manipulating functions of CriticalSection object *********************************************************************/ VOID WINAPI EnterCriticalSection(LP_CRITICAL_SECTION pcsCriticalSection) { DWORD dwState; HANDLE hCurrentThread; hCurrentThread = (HANDLE)GetCurrentThreadId(); // if current thread recurse call EnterCriticalSection(), // then just return, this action avoid deadlock if(hCurrentThread == pcsCriticalSection->OwningThread && pcsCriticalSection->LockCount >= 0) { pcsCriticalSection->RecurionCount++; return; } // test semaphore to see if critical section is available dwState = WaitForSingleObject(pcsCriticalSection->LockSemaphore, 0); switch(dwState) { // can enter into critical section case WAIT_OBJECT_0: pcsCriticalSection->LockCount++; pcsCriticalSection->RecurionCount++; pcsCriticalSection->OwningThread = hCurrentThread; return; // cannot enter into critical section, waiting until critical section // is available and the thread to run is current thread. case WAIT_TIMEOUT: while(1) { dwState = WaitForSingleObject(pcsCriticalSection->LockSemaphore, INFINITE); // if current thread is the one to be resumed, then return; // otherwise, release control first, and then keep waiting. if(WAIT_OBJECT_0 == dwState && pcsLBCriticalSection->OwningThread == hCurrentThread) { pcsCriticalSection->LockCount++; pcsCriticalSection->RecurionCount++; return; } else if(WAIT_OBJECT_0 == dwState && pcsLBCriticalSection->OwningThread != hCurrentThread) { // give up gained control, because current thread is not the one to run. ReleaseSemaphore(pcsCriticalSection->LockSemaphore, 1, NULL); } else { // other occasions are error. // error handling } } break; // error case WAIT_FAILED: default: // error handling break; } } VOID WINAPI LeaveCriticalSection(LP_CRITICAL_SECTION pcsCriticalSection) { HANDLE hCurrentThread; HANDLE hNextThread; hCurrentThread = (HANDLE)GetCurrentThreadId(); // validating, this condition should always be true, // that only the thread in critical section can call Leave function, // otherwise there must be an error occured if(hCurrentThread == pcsCriticalSection->OwningThread) { // deal with recursion if(pcsCriticalSection->RecurionCount > 0) { pcsCriticalSection->RecurionCount--; return; } else { // select a thread to run, according thread priority rank hNextThread = OutWaitThreadQueue(pcsCriticalSection->WaitThreadQueueHead); // if need to hand over the ownership of critical section // to another thread, then set OwningThread to the target // thread, else do nothing. if(hNextThread) { pcsCriticalSection->OwningThread = hNextThread; } // it's time to release ownership pcsCriticalSection->LockCount--; ReleaseSemaphore(pcsCriticalSection->LockSemaphore, 1, NULL); } } else { // other thread cannot leave before enter the critical section // error handling } } VOID WINAPI InitializeCriticalSection(LP_CRITICAL_SECTION pcsCriticalSection) { int index; pcsCriticalSection->LockCount = -1; pcsCriticalSection->RecurionCount = 0; pcsCriticalSection->OwningThread = 0; for(index = 0; index < THREAD_PRIOR_LEVELS; index++) { pcsCriticalSection->WaitThreadQueueHead[index].nPriority = ThreadPriorityMap[index]; pcsCriticalSection->WaitThreadQueueHead[index].head = NULL; pcsCriticalSection->WaitThreadQueueHead[index].tail = NULL; } pcsCriticalSection->LockSemaphore = CreateSemaphore(NULL, 1, MAX_THREADS_IN_PROCESS, NULL); if(!pcsCriticalSection->LockSemaphore) { // error handling } } BOOL WINAPI TryEnterCriticalSection(IN OUT LP_CRITICAL_SECTION lpcsCriticalSection) { DWORD dwState = WaitForSingleObject(lpcsCriticalSection->LockSemaphore, 0); if(WAIT_OBJECT_0 == dwState) { return (TRUE); } return (FALSE); } VOID WINAPI DeleteCriticalSection(LP_CRITICAL_SECTION pcsCriticalSection) { int index; HANDLE hThread; CloseHandle(pcsCriticalSection->LockSemaphore); //pcsCriticalSection->LockCount = -1; //pcsCriticalSection->RecurionCount = 0; for(index = 0; index < THREAD_PRIOR_LEVELS; index++) { // terminate all other threads, except current thread itself. hThread = OutWaitThreadQueue(pcsCriticalSection->WaitThreadQueueHead); while(hThread && hThread != pcsCriticalSection->OwningThread) { TerminateThread(hThread, 0); hThread = OutWaitThreadQueue(pcsCriticalSection->WaitThreadQueueHead); } } delete pcsCriticalSection; } /************************************************************************* implement assistant queue manipulating functions *************************************************************************/ static BOOL InWaitThreadQueue( WAIT_THREAD_QUEUE_HEAD * QueueArray, int nPriority, HANDLE hThread ) { WAIT_THREAD_QUEUE_NODE * node; WAIT_THREAD_QUEUE_HEAD * queue; // map into proper queue switch(nPriority) { case THREAD_PRIORITY_TIME_CRITICAL: queue = QueueArray; break; case THREAD_PRIORITY_HIGHEST: queue = QueueArray + 1; break; case THREAD_PRIORITY_ABOVE_NORMAL: queue = QueueArray + 2; break; case THREAD_PRIORITY_NORMAL: queue = QueueArray + 3; break; case THREAD_PRIORITY_BELOW_NORMAL: queue = QueueArray + 4; break; case THREAD_PRIORITY_LOWEST: queue = QueueArray + 5; break; case THREAD_PRIORITY_IDLE: queue = QueueArray + 6; break; default: return (FALSE); } // alloc new queue node and setting node = (WAIT_THREAD_QUEUE_NODE *)malloc(sizeof(WAIT_THREAD_QUEUE_NODE)); if(!node) { return (FALSE); } node->hWaitingThread = hThread; node->next = NULL; // append to queue tail if(!queue->head && !queue->tail) { queue->tail = queue->head = node; return (TRUE); } else { queue->tail = queue->tail->next = node; return (TRUE); } return (FALSE); } static HANDLE OutWaitThreadQueue(WAIT_THREAD_QUEUE_HEAD * QueueArray) { int index; HANDLE hThread; WAIT_THREAD_QUEUE_NODE * node; WAIT_THREAD_QUEUE_HEAD * queue; for(index = 0; index < THREAD_PRIOR_LEVELS; index++) { queue = QueueArray + index; if(queue->head) { // get and check the queue's head node node = queue->head; if(!node) { return (NULL); } // adapting the queue, return needed value queue->head = queue->head->next; hThread = node->hWaitingThread; free(node); return (hThread); } } return (NULL); } 其实这个算法也是在网上找的，感觉这个题目巨难，一开始就要人写API函数啊!

贴个我去年面Microsoft ATC实习生的笔试题