Windows , (, , ).
| User | Graphics Device Interface | Kernel |
| , | , | , , |
.
Win32API
, . Windows ( HANDLE). , , .
(, CreateThread)
, . ( )
, .
:
1) Create, .
2) , Win32API
3) CloseHandle.
!! !!
, , :
.
| Create |
| Unblock |
| Block |
| Exit |
| Run |
| Interrupt |
, , . .
,
Create , . .
Exit . .
,
Run , . . , .
Interrupt . , , .
|
|
|
Block , . , , , - .
Unblock , .. .
, .
, , .
:
,
, .
.
. , - , , .
, , . , .
, .
2.4 Windows
Windows , .
Windows
Windows :
(HANDLE);
.
, .
Windows
Windows :
,
Windows.
Windows
Windows :
.
.
:
(working threads)
(user interface threads)
.
, .
, , , (primary) (main) .
, main.
, WinMain.
Windows
ü CreateThread ;
|
|
|
ü ExitThread ;
ü TerminateThread ;
ü ResumeThread ;
ü Sleep .
Windows
Windows
Windows , , . , Windows .
Windows
Windows :
(HANDLE);
.
.
, .
Windows
Windows :
,
, .
Windows
.
.
.
Windows
ü CreateProcess ;
ü ExitProcess ;
ü TerminateProcess .
, CreateProcess, , .
, CreateProcess, , .
2.6 Windows
, , .
, , .
, .
Windows :
Create ;
SetHandleInformation.
, ,
GetHandleInformation.
: .
.
3.1
, .
-.
, .. , .
, .
, .
|
|
|
. .. , .
, .
.
, .
1. (), .
2. .
, .
, . :
;
;
.
, .
, .
. :
;
.
3.2
.
, () . .
, , , .
, .
.
.
.
.
.
() , .
:
, ;
.
3.3
, .
|
|
|
:
1. FCFS
:
, , ;
, ( );
, .
FCFS (first come first served)
2. SPN
, SPN (shortest process next): .
.
: 
, S1 , ; Tn n- ; Sn+1 (n+1)- .
3.4
, , ( )
, , .
.
1. RR
Windows :
SetPriorityBoost ;
GetProcessPriorityBoost , ;
SetThreadPriorityBoost ;
GetThreadPriorityBoost , .
3.8
1.
FCFS (First Come First Served).
, :
;
: ; .
47/5 = 9,4.
28/5 = 5,6.
2.
SPN (Shortest Process Next)
, 1.
39/5 = 7,8.
|
|
|
20/5 = 4.
3.9
3.
RR (Round-robin)
, 1.
,
;
;
.
50/5 = 10.
31/5 = 6,2.
4.1 ()
.
, .
, , :
;
.
:
, .
;
.
, :
, ;
;
.
.. , :
disable_interrupt();
;
enable_interrupt();
, .. , , , .
4.2
, , (private) .
, (, ) , , (shared) .
, ( ) .
shared x, y;
private a, b;
a = x; //
y = b; //
x = x+1; //
++a; //
x =a; //
x = y; //
4.3
, .
, .
, .
.
, , () .
1 (Non-interference postulate) , , () .
2 (Atomicity postulate) .
3 (Interleaving postulate ) () .
, , , (race condition).
, .
.
4.4
, , .
, () , .
, .
, , , .
, .
.
, .
:
<await() >
() , .
:
await , ;
, .
.
.
:
, <await(true) >:= <>
.
.
, , .
:
, <await()>
await , .. .
.
4.5
.
: , .
, , , .
1. (safety requirement) .
2. (progress requirement) ( ).
3. (fairness requirement) ( ).
, 3 2.
3 .
, 2.
4.6
(Peterson G.L. 1981)
bool x1, x2;
int q //
x1 = false;
x2 = false;
void thread1 () {
while (true)
{
noncriticalSection1();
x1 = true; // 1
q = 2; // 2
while (x2 &&q == 2); //
criticalSection1();
x1 = false;
} }
void thread2 () {
while (true)
{
nonCriticalSection2();
x2 = true;
q = 1;
while(x1 && q == 1);
criticalSection2();
x2 = false;
} }
1. .
thread1 1 , : ((x2 & q == 2) ≡ 0) => (not(x2 & q==2) ≡ 1) => (not(x2) | not(q==2) ≡ 1) => (not(x2) | q==1 ≡ 1). , thread1 1, (x1 == true) ≡ 1 : Q1 = x1 & (notx2 | q == 1) 1, .. thread1 1, Q1 = 1. , 2: Q2 = x2& (notx1 | q == 2). :
Q1&Q2 ≡ (x1 & (notx2 | q == 1)) & (x2& (notx1 | q == 2)) ≡ (x1 &x2) & (notx1 | q == 2) & (notx2 | q == 1) ≡ (x1 & x2) & ((notx1 & notx2) | (notx1 & q == 1) | (notx2 & q==2) | (q == 1 & q == 2)) ≡ (x1 & x2 & notx1 & notx2) | (x1 & x2 & notx1 & q == 1) | (x1 & x2 & notx2 & q==2) ≡ 0.
, Q1&Q2 ≡0. , thread1 thread2 .
2. .
thread1 , (x2&q==1) ≡ 1. , thread2 (x1&q==2) ≡ 1.
(x2&q==2)&(x1&q==1) ≡ x1&x2&q==1&q==2 ≡ 0
, thread1 thread2 .
3.
, .., thread1 .
(x2&q==2) ≡1. , x2 ≡1 & (q==2) ≡1.
2 , thread2 thread1.
, (x1 & q==1) not≡ 1.
, thread2 while x2 = false q=1 .
. .
4.7
bool event;
event = false;
void thread1()
{
beforeEvent1();
while(!event);
afterEvent1();
}
void thread2()
{
beforeEvent2();
event = true; //
afterEvent2();
}
, thread1 afterEvent1 , thread2 event.
4.8 ()
, , .. .
( ) .
, .
xchg
Intel x86 xchg ( ), :
void xchg(register int r, int* x)
{
register int temp;
temp = r;
r = *x;
*x = temp;
}
N-
xchg N- , .
int lock = 0;
void thread()
{
while(true)
{
int key=1; //
while(key==1) //
xchg(key, &lock);
criticalSection();
lock =0;
nonCriticalSection();
} }
1. . . , keyi = 0 keyj = 0 i<>j. , xchg . , . , , .
2. . . , while(key==1) xchg(key, &lock); , ∑keyi + lock = n+1. , ∑keyi + lock = n xchg. , .
3. . , .
: while .
(busy waiting).
-
, , .
while -, -, (spin lock, live lock).
5.1
(, ) .
.
.
, .
.
, , .
, .
class ThreadQueue
{
Thread* tp;
public:
ThreadQueue():tp(NULL){}
~ThreadQueue(){}
void enqueueThread(Thread& t);
bool dequeueThread();
};
void ThreadQueue::enqueueThread(Thread& t)
{
includeThreadToList(t);
t.suspendThread();//
}
bool ThreadQueue::dequeueThread()
{
Thread t;
if (!tp)
return false;
else
{
t = excludeThreadFromQueue();
t.resumeThread();//
return true;
}
}
5.2 Lock()
Lock
class Lock
{
bool free;
ThreadQueue tq;
public:
Lock(): free(true){}
~Lock(){}
void acquire();//
void release();//
};
void Lock::acquire()
{
disableInterrupt();
if(!free)
tq.enqueueThread(currentThread());
else
free = false;
enableInterrupt();
}
void Lock::release()
{
disableInterrupt();
if(!tq.dequeueThread())
free = true;
enableInterrupt();
}
Lock
| Lock lock; void thread1() { beforeCS1(); lock.acquire(); cS1(); lock.release(); afterCS1(); } | Lock lock; void thread2() { beforeCS2(); lock.acquire(); cS2(); lock.release(); afterCS2(); } |
Lock Windows
Windows Lock CRITICAL_SECTION, Mutex.
5.3 Condition
Condition
class Condition
{
bool event;
ThreadQueue tq;
public:
Condition():event(false){}
~Condition(){}
void wait();//
void signal(); //
};
void Condition::wait()
{
disableInterrupt();
if(event)
event = false;
else
tq.enqueueThread(currentThread());
enableInterrupt();
}
void Condition::signal()
{
disableInterrupt();
if(!tq.dequeueThread())
event = true;
enableInterrupt(); }
Condition
Condition c;
void thread1)
{
beforeCS1();
c.wait();
afterCS1();
}
void thread2()
{
beforeCS2();
c.signal();
afterCS2();
}
Condition
Condition c;
c.signal();//
void thread1()
{
beforeCS1();
c.wait();
cS1();
c.signal();
afterCS1();
}
void thread2()
{
beforeCS2();
c.wait();
cS2();
c.signal(;
afterCS2();
}
Condition Windows
Windows Condition Event
5.4
, .
, , .
s , : p(s) ; v(s) .
p(s) { if s > 0 then s = s 1; else wait;} v(s) { if somebody is waiting release one; else s = s -1; }
, 0, 1, ; .
, , , v .
, p v , , .
, , . . FIFO, , .
FIFO, , .
, 0 1, .
, 1, .
Semaphor s = 1; //
| void thread1() { beforeCS1(); P(s); // CriticalSection1(); V(s); // afterCS1(); } | void thread2() { beforeCS2(); P(s); // CriticalSection2(); V(s); // afterCS2(); } |
Semaphor s = 0; //
| void thread1() { beforeEvent1(); P(s); // afterEvent1(); } | void thread2() { beforeEvent2(); V(s); // afterEvent2(); } |
5.5
class Semaphore
{
int count; //
ThreadQueue tq; //
public:
Semaphore(int& n): count(n){}
~Semaphore() {...}
void wait(); //
void signal(); //
};
void Semaphore::wait()
{
disableInterrupt();
if (count > 0)
--count;
else
tq.enqueueThread(currentThread());
enableInterrupt();
}
void Semaphore::signal()
{
disableInterrupt();
if (!tq.dequeueThread())
++count;
enableInterrupt();
}
5.6 Windows
Windows , : .
:
, . Windows (Mutex), (Event), (Semaphore).
(waitable timer).
, , . , . , .
Windows , , .
:
, , , ;
, , , , , , .
Windows
WaitForSingleObject .
WaitForMultipleObjects .
5. 7 Windows
, , Windows CRITICAL_SECTION.
CRITICAL_SECTION , .. . , .. .
CRITICAL_SECTION
InitializeCriticalSection ;
EnterCriticalSection ;
TryEnterCriticalSection ;
LeaveCriticalSection ;
DeleteCriticalSection .
5.8 Windows
, , Windows (mutex).
, . .
.
CreateMutex ;
OpenMutex ;
ReleaseMutex ( );
WaitForSingleObject WaitForMultipleObjects ( )
5.9 Windows
Windows Event.
Event .
Windows : .
ResetEvent;
ResetEvent, WaitForSingleObject WaitForMultipleObjects.
WaitForSingleObject WaitForMultipleObjects, .
CreateEvent ;
OpenEvent ;
SetEvent ;
ResetEvent ;
PulseEvent , ;
WaitForSingleObject, WaitForMultiplyObject ;
5.10 Windows
Windows Semaphore.
,
.
0
=0
CreateSemaphore ;
OpenSemaphore ;
ReleaseSemaphore +1;
WaitForSingleObject, WaitForMultiplyObject , -1;
