[ Windows DDP ] 驅動程式的同步處理 : 核心模式下的同步物件 - 信號燈

前言 : 
在內核中還有另一種同步物件, 這就是信號燈. 和事件對向一樣, 信號燈在使用者模式下和核心模式下是完全統一的, 只不過操作方式不太一樣. 在使用者模式下, 信號燈物件用控制碼代表, 而在核心模式下, 信號燈物件用 KSEMAPHORE 資料結構表示. 

核心模式下的信號燈 : 
在使用信號燈物件前, 需要對信號燈物件進行初始化. 使用內核函式 KeInitializeSemaphore 對信號燈初始化, 其函式宣告如下 : 

- Syntax :

view plaincopy to clipboardprint?

1. VOID KeInitializeSemaphore(  
2.   __out  PRKSEMAPHORE Semaphore,  
3.   __in   LONG Count,  
4.   __in   LONG Limit  
5. );  

參數說明 : 

* 參數 Semaphore : 這個參數獲得內核信號燈物件指標
* 參數 Count : 這個參數式初始化時的信號燈計數.
* 參數 Limit : 這個參數指名信號燈計數的上限.

KeReadStateSemaphore 函式可以讀取信號燈當前的計數. 釋放信號燈會增加信號燈計數, 它對應的內核函式是 KeReleaseSemaphore. 程式設計師可以用這個函式指定增量值. 獲得信號燈可以使用 KeWaitXXX 系列函式. 如果能獲得, 就將計數減一, 否則陷入等待, 下面程式碼展示了如何在驅動程式中使用信號燈物件 : 

- Driver.cpp : 示範如何在核心模式下使用 信號燈

view plaincopy to clipboardprint?

1. VOID SemaphoreFun(IN PVOID pContext)  
2. {  
3.     // 得到信號燈  
4.     PKSEMAPHORE pkSemaphore = (PKSEMAPHORE) pContext;  
5.     KdPrint(("Enter SemaphoreFun\n"));  
6.     KeReleaseSemaphore(pkSemaphore, IO_NO_INCREMENT, 1, FALSE);  
7.     LONG count = KeReadStateSemaphore(pkSemaphore);  
8.     //KdPrint(("\tThe Semaphore count is %d\n", count));  
9.     KdPrint(("Leave SemaphoreFun\n"));  
10.     // 結束執行緒  
11.     PsTerminateSystemThread(STATUS_SUCCESS);  
12. }  
13.   
14. #pragma PAGEDCODE  
15. VOID TestSemaphore()   
16. {  
17.     HANDLE hMyThread;  
18.     KSEMAPHORE kSemaphore;  
19.     // 初始化內核信號燈  
20.     KeInitializeSemaphore(&kSemaphore, 2, 2);  
21.     // 讀取信號燈狀態  
22.     LONG count = KeReadStateSemaphore(&kSemaphore);  
23.     KdPrint(("The Semaphore count is %d\n", count));  
24.     // 等待信號燈  
25.     KeWaitForSingleObject(&kSemaphore, Executive, KernelMode, FALSE, NULL);  
26.     // 讀取信號燈狀態  
27.     count = KeReadStateSemaphore(&kSemaphore);  
28.     KdPrint(("The Semaphore count is %d\n", count));  
29.     NTSTATUS status = PsCreateSystemThread(&hMyThread, 0, NULL, NtCurrentProcess(), NULL, SemaphoreFun, &kSemaphore);  
30. }  

底下是執行結果 : 

[ Data Structures with Java ] Section 9.3 : ArrayList Applications

Preface : 
This section includes two applications that demonstrate use of the ArrayList class. The method join() concatenates one ArrayList onto the end of another. We will develop join() and use it in a simple program. An ArrayList is useful when the amount of storage required is not know in advance. A particularly interesting example of this is the closet-pair program. Input any number of points in the plane and determine a pair of points that are closest together. We will conclude this section by developing an algorithm that solves the closest-pair problem and using it in an application. 

Joining ArrayLists : 
The concatenation of one string onto the end of another is the model for joining two ArrayList objects. The method join() takes two lists listA and listB as arguments. A loop scans the elements of listB and copies them onto the end of listA by using the add() method. 
The algorithm begins by identifying the size of each ArrayList. A call to the method ensureCapacity() uses the sum of the two sizes as an argument. If ArrayList listA doesn't not have sufficient space to hold the incoming elements from listB, the operation makes a single allocation of new memory that contains the current elements in listA and space for the elements in listB. A simple loop scans the elements in listB and appends them to listA. 

- 函式 join() 代碼 :

view plaincopy to clipboardprint?

1. public static  void join(ArrayList listA, ArrayList listB) {  
2.     int sizeA = listA.size(), sizeB = listB.size();  
3.     listA.ensureCapacity(sizeA+sizeB);  
4.     for(T t:listB)  
5.         listA.add(t);  
6. }  

The Closest-Pair Problem : 
The closest-pair problem requires finding the two closest points in a set of n points in the plane. Assume we specify each point using the standard Cartesian coordinate notation (x, y) and that the distance between two points Pi = (xi, yi) and Pj=(xj, yj) is : 
 
A simple approach to the problem is to evaluate the distance between every pair of distinct points and determine the pair with the smallest distance. We do not want to determine the distance between the same pair of points twice. For instance d(P1, P8) = d(P8, P2). We avoid doing this by only considering pairs(Pi, Pj) where i 
Our algorithm is similar to the selection sort algorithm that we discussed in Chapter 4. In a nested loop structure, we find the distance between P0 and the set of points {P1, P2, ... Pn-1}, keeping track of the minimum distance. We continue by computing the distance between P1 and the set of points {P2, P3, ... Pn-1}. In general, pass i of the algorithm computes the distances between Pi and the set of points {Pi+1, ... , Pn-1}. To optimize our algorithm's performance, we do not compute d(Pi, Pj) but compute d(Pi, Pj)^2. The square root takes additional time to compute and general cannot be computed exactly. 
The method closestPair() implements the algorithm. Its arguments are ArrayList variables x and y containing the x-coordinate and the y-coordinate of the points. The method returns an array of two integers that contains the indices of the two closet points : 

- 函式 closestPair() 代碼 :

view plaincopy to clipboardprint?

1. protected static double sqr(double x) {  
2.     return x*x;  
3. }  
4.   
5. public static int[] closestPair(ArrayList x, ArrayList y) {  
6.     int n = x.size(), p1=-1, p2=-1;  
7.     int[] closest = new int[2];  
8.     double minumDist = java.lang.Double.MAX_VALUE,tempDist=0;  
9.     double x1,x2,y1,y2;  
10.     for(int i=0; i<(n-1); i++) {  
11.         x1 = x.get(i);  
12.         y1 = y.get(i);  
13.         for(int j=(i+1); j
14.             x2 = x.get(j);  
15.             y2 = y.get(j);  
16.             //System.out.print("x1="+x1+",y1="+y1+"; x2="+x2+",y2="+y2);  
17.             tempDist = sqr((x1-x2))+sqr((y1-y2));  
18.             //System.out.println(" >> Check "+tempDist+"...(MinNow="+minumDist+")");                
19.             if(tempDist
20.                 //System.out.println("\tGot P"+i+" and P"+j);  
21.                 p1=i; p2=j;  
22.                 minumDist = tempDist;  
23.             }  
24.         }  
25.     }  
26.     closest[0] = p1;  
27.     closest[1] = p2;  
28.     return closest;  
29. }  
30.   
31. public static void main(String args[]) {  
32.     ArrayList x = new ArrayList(), y = new ArrayList();  
33.     double[] xPt = {-1, -1.45, -1, -1, 0.75, 1, 0.8, 1.65, -1.2, 3, 2, 2.7, 1.35, 0.5};  
34.     double[] yPt = {1, 1.3, 0, 3, -1.75, -1, 0.7, 1, -1.3, 0, 2, 1.3, 1.1, 2.45};  
35.     for(int i=0; i
36.         x.add(xPt[i]);  
37.         y.add(yPt[i]);  
38.     }  
39.     int[] closestPoints = closestPair(x,y);  
40.     System.out.printf("The closest points are (%.2f, %.2f) and (%.2f, %.2f)\n",   
41.             xPt[closestPoints[0]], yPt[closestPoints[0]],  
42.             xPt[closestPoints[1]], yPt[closestPoints[1]]);  
43.     System.out.println("Distance="+  
44.             Math.sqrt(sqr(  
45.                     xPt[closestPoints[0]]-xPt[closestPoints[1]])+sqr(yPt[closestPoints[0]]-yPt[closestPoints[1]])));  
46. }  

Analysis of the Closest-Pair Algorithm : 
Pass 0 of the algorithm compares n-1 points, and pass 1 compares n-2 points. The total number of comparisons is : 
(n-1) + (n-2) + ... + 1 = n(n-1)/2 

The algorithm has running time O(n^2) ; in other words, it is quadratic. The technique we used is an example of a brute force algorithm. Brute force is a straightforward approach to solving a problem when we have something to search for or when we wish to optimize some property. It is usually based directly on the problem's statement. Normally, the technique enumerates all possible configurations of the input and picks the best of these enumerated configurations. There are important applications of the closest-pair problem. For instance, the algorithm will tell an air traffic controller which pair of n planes is closest during approach to the airport. For this reason, our brute algorithm is too slow. Actually there is a divide-and-conquer O(nlog2(n)) algorithm for the problem but it is too involved to discuss here.