Post

Giải bài tập chương 5–Hệ điều hành

Posted
By Scott Le
10 min read

Đây là phần giải bài tập chương 5 môn hệ điều hành do mình tự làm (thầy Khánh không giải. Mình sẽ chỉ viết bài giải từ bài 5 trở đi thôi. Từ bài 1 đến bài 4 không có gì để nói hết. Các bạn nào biết đáp án rồi mà phát hiện mình sai chỗ nào comment dùm nghen. Thanks các bạn nhiều.

Bài 5: bài giải tổng quát như sau (đề bài phải sửa lại thành nb<=na<=nb+10 mới có thể thực hiện được):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

<span style="color:#666666;">// Share data</span>
Semaphore b, max<span style="color:#008080;">;</span>
b.<span style="color:#007788;">value</span> <span style="color:#000080;">=</span> <span style="color:#0000dd;">0</span><span style="color:#008080;">;</span>
max.<span style="color:#007788;">value</span> <span style="color:#000080;">=</span> <span style="color:#0000dd;">9</span><span style="color:#008080;">;</span>  <span style="color:#666666;">// if we set max = 10, then</span>
                        <span style="color:#666666;">// at some point, a will be greater than b+10</span>
<span style="color:#666666;">// Process A</span>
<span style="color:#0000ff;">while</span> <span style="color:#008000;">(</span><span style="color:#0000ff;">true</span><span style="color:#008000;">)</span>
<span style="color:#008000;">{</span>
    wait<span style="color:#008000;">(</span>max<span style="color:#008000;">)</span><span style="color:#008080;">;</span>  <span style="color:#666666;">// Check whether it has reached the max value or not </span>
                 <span style="color:#666666;">// (na<=nb+10)</span>
        na<span style="color:#000040;">++</span><span style="color:#008080;">;</span>  <span style="color:#666666;">// do work</span>
    <span style="color:#0000ff;">signal</span><span style="color:#008000;">(</span>b<span style="color:#008000;">)</span><span style="color:#008080;">;</span>  <span style="color:#666666;">// increase b.value one unit. This makes process A </span>
                 <span style="color:#666666;">// always execute before process B, </span>
                 <span style="color:#666666;">//  so nb <= na every time</span>
<span style="color:#008000;">}</span>   <span style="color:#666666;">// Process B</span>
<span style="color:#0000ff;">while</span> <span style="color:#008000;">(</span><span style="color:#0000ff;">true</span><span style="color:#008000;">)</span>
<span style="color:#008000;">{</span>
    wait<span style="color:#008000;">(</span>b<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
        nb<span style="color:#000040;">++</span><span style="color:#008080;">;</span>  <span style="color:#666666;">// do work </span>
    <span style="color:#0000ff;">signal</span><span style="color:#008000;">(</span>max<span style="color:#008000;">)</span><span style="color:#008080;">;</span> <span style="color:#666666;">// release one value of max's value, so that it make A </span>
                   <span style="color:#666666;">//be able to increase its </span>
                  <span style="color:#666666;">// value, and also ensure na<=nb+10</span>
<span style="color:#008000;">}</span>

Còn dưới đây là code demo sử dụng C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

<span style="color:#0000dd;">1</span><span style="color:#008080;">:</span>  <span style="color:#339900;">#include "stdio.h"</span>
<span style="color:#0000dd;">2</span><span style="color:#008080;">:</span>  <span style="color:#339900;">#include "windows.h"</span>
<span style="color:#0000dd;">3</span><span style="color:#008080;">:</span>  <span style="color:#339900;">#include "conio.h"</span>
<span style="color:#0000dd;">4</span><span style="color:#008080;">:</span>  <span style="color:#339900;">#include "tchar.h"</span>
<span style="color:#0000dd;">5</span><span style="color:#008080;">:</span>  HANDLE maxSemaphore, mutex<span style="color:#008080;">;</span>
<span style="color:#0000dd;">6</span><span style="color:#008080;">:</span>
<span style="color:#0000dd;">7</span><span style="color:#008080;">:</span>  DWORD WINAPI ProcessA <span style="color:#008000;">(</span>LPVOID num<span style="color:#008000;">)</span>
<span style="color:#0000dd;">8</span><span style="color:#008080;">:</span>  <span style="color:#008000;">{</span>
<span style="color:#0000dd;">9</span><span style="color:#008080;">:</span>      <span style="color:#0000ff;">int</span> na<span style="color:#000080;">=</span><span style="color:#0000dd;">0</span>, i<span style="color:#000080;">=</span><span style="color:#0000dd;">0</span><span style="color:#008080;">;</span>  <span style="color:#0000dd;">10</span><span style="color:#008080;">:</span>      <span style="color:#0000ff;">while</span> <span style="color:#008000;">(</span>i<span style="color:#000080;"><</span><span style="color:#0000dd;">100</span><span style="color:#008000;">)</span>
<span style="color:#0000dd;">11</span><span style="color:#008080;">:</span>      <span style="color:#008000;">{</span>
<span style="color:#0000dd;">12</span><span style="color:#008080;">:</span>          <span style="color:#0000ff;">if</span> <span style="color:#008000;">(</span>WaitForSingleObject<span style="color:#008000;">(</span>maxSemaphore, INFINITE<span style="color:#008000;">)</span><span style="color:#000080;">==</span><span style="color:#0000dd;">0</span><span style="color:#008000;">)</span>
<span style="color:#0000dd;">13</span><span style="color:#008080;">:</span>          <span style="color:#008000;">{</span>
<span style="color:#0000dd;">14</span><span style="color:#008080;">:</span>              na<span style="color:#000040;">++</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">15</span><span style="color:#008080;">:</span>              ReleaseSemaphore<span style="color:#008000;">(</span>mutex, <span style="color:#0000dd;">1</span>, <span style="color:#0000ff;">NULL</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">16</span><span style="color:#008080;">:</span>                  <span style="color:#666666;">//printf ("Release mutex error!n");                  </span>
<span style="color:#0000dd;">17</span><span style="color:#008080;">:</span>              <span style="color:#0000dd;">printf</span> <span style="color:#008000;">(</span><span style="color:#ff0000;">"na= %dn"</span>, na<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">18</span><span style="color:#008080;">:</span>              i<span style="color:#000040;">++</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">19</span><span style="color:#008080;">:</span>          <span style="color:#008000;">}</span>
<span style="color:#0000dd;">20</span><span style="color:#008080;">:</span>          <span style="color:#0000ff;">else</span>
<span style="color:#0000dd;">21</span><span style="color:#008080;">:</span>              <span style="color:#0000dd;">printf</span> <span style="color:#008000;">(</span><span style="color:#ff0000;">"Wait for maxSemaphoren"</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">22</span><span style="color:#008080;">:</span>
<span style="color:#0000dd;">23</span><span style="color:#008080;">:</span>      <span style="color:#008000;">}</span>
<span style="color:#0000dd;">24</span><span style="color:#008080;">:</span>      <span style="color:#0000ff;">return</span> <span style="color:#0000dd;">0</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">25</span><span style="color:#008080;">:</span>  <span style="color:#008000;">}</span>
<span style="color:#0000dd;">26</span><span style="color:#008080;">:</span>  DWORD WINAPI ProcessB <span style="color:#008000;">(</span>LPVOID num<span style="color:#008000;">)</span>
<span style="color:#0000dd;">27</span><span style="color:#008080;">:</span>  <span style="color:#008000;">{</span>
<span style="color:#0000dd;">28</span><span style="color:#008080;">:</span>      <span style="color:#0000ff;">int</span> nb<span style="color:#000080;">=</span><span style="color:#0000dd;">0</span>, i<span style="color:#000080;">=</span><span style="color:#0000dd;">0</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">29</span><span style="color:#008080;">:</span>      <span style="color:#0000ff;">while</span> <span style="color:#008000;">(</span>i<span style="color:#000080;"><</span><span style="color:#0000dd;">100</span><span style="color:#008000;">)</span>
<span style="color:#0000dd;">30</span><span style="color:#008080;">:</span>      <span style="color:#008000;">{</span>
<span style="color:#0000dd;">31</span><span style="color:#008080;">:</span>          <span style="color:#0000ff;">if</span> <span style="color:#008000;">(</span>WaitForSingleObject<span style="color:#008000;">(</span>mutex, INFINITE<span style="color:#008000;">)</span><span style="color:#000080;">==</span><span style="color:#0000dd;">0</span><span style="color:#008000;">)</span>
<span style="color:#0000dd;">32</span><span style="color:#008080;">:</span>          <span style="color:#008000;">{</span>
<span style="color:#0000dd;">33</span><span style="color:#008080;">:</span>              ReleaseSemaphore<span style="color:#008000;">(</span>maxSemaphore, <span style="color:#0000dd;">1</span>, <span style="color:#0000ff;">NULL</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">34</span><span style="color:#008080;">:</span>              nb<span style="color:#000040;">++</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">35</span><span style="color:#008080;">:</span>              <span style="color:#0000dd;">printf</span> <span style="color:#008000;">(</span><span style="color:#ff0000;">"nb= %dn"</span>, nb<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">36</span><span style="color:#008080;">:</span>              i<span style="color:#000040;">++</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">37</span><span style="color:#008080;">:</span>          <span style="color:#008000;">}</span>
<span style="color:#0000dd;">38</span><span style="color:#008080;">:</span>          <span style="color:#0000ff;">else</span>
<span style="color:#0000dd;">39</span><span style="color:#008080;">:</span>              <span style="color:#0000dd;">printf</span> <span style="color:#008000;">(</span><span style="color:#ff0000;">"Wait for mutexn"</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">40</span><span style="color:#008080;">:</span>      <span style="color:#008000;">}</span>
<span style="color:#0000dd;">41</span><span style="color:#008080;">:</span>      <span style="color:#0000ff;">return</span> <span style="color:#0000dd;">0</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">42</span><span style="color:#008080;">:</span>  <span style="color:#008000;">}</span>
<span style="color:#0000dd;">43</span><span style="color:#008080;">:</span>
<span style="color:#0000dd;">44</span><span style="color:#008080;">:</span>
<span style="color:#0000dd;">45</span><span style="color:#008080;">:</span>  <span style="color:#0000ff;">int</span> main<span style="color:#008000;">(</span><span style="color:#008000;">)</span>
<span style="color:#0000dd;">46</span><span style="color:#008080;">:</span>  <span style="color:#008000;">{</span>
<span style="color:#0000dd;">47</span><span style="color:#008080;">:</span>      HANDLE hThread<span style="color:#008000;">[</span><span style="color:#0000dd;">2</span><span style="color:#008000;">]</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">48</span><span style="color:#008080;">:</span>      DWORD threadID<span style="color:#008000;">[</span><span style="color:#0000dd;">2</span><span style="color:#008000;">]</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">49</span><span style="color:#008080;">:</span>      mutex <span style="color:#000080;">=</span> CreateSemaphore <span style="color:#008000;">(</span><span style="color:#0000ff;">NULL</span>, <span style="color:#0000dd;">0</span>, <span style="color:#0000dd;">1</span>, <span style="color:#0000ff;">NULL</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">50</span><span style="color:#008080;">:</span>      <span style="color:#0000ff;">if</span> <span style="color:#008000;">(</span>mutex<span style="color:#000080;">==</span><span style="color:#0000ff;">NULL</span><span style="color:#008000;">)</span>
<span style="color:#0000dd;">51</span><span style="color:#008080;">:</span>      <span style="color:#008000;">{</span>
<span style="color:#0000dd;">52</span><span style="color:#008080;">:</span>          <span style="color:#0000dd;">printf</span> <span style="color:#008000;">(</span><span style="color:#ff0000;">"Create mutex error!n"</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">53</span><span style="color:#008080;">:</span>          <span style="color:#0000ff;">return</span> <span style="color:#000040;">-</span><span style="color:#0000dd;">1</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">54</span><span style="color:#008080;">:</span>      <span style="color:#008000;">}</span>
<span style="color:#0000dd;">55</span><span style="color:#008080;">:</span>      maxSemaphore <span style="color:#000080;">=</span> CreateSemaphore<span style="color:#008000;">(</span><span style="color:#0000ff;">NULL</span>, <span style="color:#0000dd;">9</span>, <span style="color:#0000dd;">9</span>, <span style="color:#0000ff;">NULL</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">56</span><span style="color:#008080;">:</span>      <span style="color:#0000ff;">if</span> <span style="color:#008000;">(</span>maxSemaphore<span style="color:#000080;">==</span><span style="color:#0000ff;">NULL</span><span style="color:#008000;">)</span>
<span style="color:#0000dd;">57</span><span style="color:#008080;">:</span>      <span style="color:#008000;">{</span>
<span style="color:#0000dd;">58</span><span style="color:#008080;">:</span>          <span style="color:#0000dd;">printf</span> <span style="color:#008000;">(</span><span style="color:#ff0000;">"Create maxSemaphore error!n"</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">59</span><span style="color:#008080;">:</span>          <span style="color:#0000ff;">return</span> <span style="color:#000040;">-</span><span style="color:#0000dd;">1</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">60</span><span style="color:#008080;">:</span>      <span style="color:#008000;">}</span>
<span style="color:#0000dd;">61</span><span style="color:#008080;">:</span>      hThread<span style="color:#008000;">[</span><span style="color:#0000dd;">0</span><span style="color:#008000;">]</span> <span style="color:#000080;">=</span> CreateThread<span style="color:#008000;">(</span><span style="color:#0000ff;">NULL</span>,  <span style="color:#666666;">// default security attributes  </span>
<span style="color:#0000dd;">62</span><span style="color:#008080;">:</span>          <span style="color:#0000dd;">0</span>, <span style="color:#666666;">// default stack size  </span>
<span style="color:#0000dd;">63</span><span style="color:#008080;">:</span>          <span style="color:#008000;">(</span>LPTHREAD_START_ROUTINE<span style="color:#008000;">)</span>ProcessA, <span style="color:#666666;">// procedure to execute  </span>
<span style="color:#0000dd;">64</span><span style="color:#008080;">:</span>          <span style="color:#0000ff;">NULL</span>, <span style="color:#666666;">// no argument  </span>
<span style="color:#0000dd;">65</span><span style="color:#008080;">:</span>          <span style="color:#0000dd;">0</span>, <span style="color:#666666;">// default creation flags  </span>
<span style="color:#0000dd;">66</span><span style="color:#008080;">:</span>          <span style="color:#000040;">&</span>threadID<span style="color:#008000;">[</span><span style="color:#0000dd;">0</span><span style="color:#008000;">]</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span> <span style="color:#666666;">// thread identifier  </span>
<span style="color:#0000dd;">67</span><span style="color:#008080;">:</span>      <span style="color:#0000ff;">if</span> <span style="color:#008000;">(</span>hThread<span style="color:#008000;">[</span><span style="color:#0000dd;">0</span><span style="color:#008000;">]</span><span style="color:#000080;">==</span><span style="color:#0000ff;">NULL</span><span style="color:#008000;">)</span>
<span style="color:#0000dd;">68</span><span style="color:#008080;">:</span>      <span style="color:#008000;">{</span>
<span style="color:#0000dd;">69</span><span style="color:#008080;">:</span>          <span style="color:#0000dd;">printf</span> <span style="color:#008000;">(</span><span style="color:#ff0000;">"Create thread A error: %dn"</span>, GetLastError<span style="color:#008000;">(</span><span style="color:#008000;">)</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">70</span><span style="color:#008080;">:</span>          <span style="color:#0000ff;">return</span> <span style="color:#000040;">-</span><span style="color:#0000dd;">2</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">71</span><span style="color:#008080;">:</span>      <span style="color:#008000;">}</span>
<span style="color:#0000dd;">72</span><span style="color:#008080;">:</span>
<span style="color:#0000dd;">73</span><span style="color:#008080;">:</span>      hThread<span style="color:#008000;">[</span><span style="color:#0000dd;">1</span><span style="color:#008000;">]</span> <span style="color:#000080;">=</span> CreateThread<span style="color:#008000;">(</span><span style="color:#0000ff;">NULL</span>,  <span style="color:#666666;">// default security attributes  </span>
<span style="color:#0000dd;">74</span><span style="color:#008080;">:</span>          <span style="color:#0000dd;">0</span>, <span style="color:#666666;">// default stack size  </span>
<span style="color:#0000dd;">75</span><span style="color:#008080;">:</span>          <span style="color:#008000;">(</span>LPTHREAD_START_ROUTINE<span style="color:#008000;">)</span>ProcessB, <span style="color:#666666;">// procedure to execute  </span>
<span style="color:#0000dd;">76</span><span style="color:#008080;">:</span>          <span style="color:#0000ff;">NULL</span>, <span style="color:#666666;">// no argument  </span>
<span style="color:#0000dd;">77</span><span style="color:#008080;">:</span>          <span style="color:#0000dd;">0</span>, <span style="color:#666666;">// default creation flags  </span>
<span style="color:#0000dd;">78</span><span style="color:#008080;">:</span>          <span style="color:#000040;">&</span>threadID<span style="color:#008000;">[</span><span style="color:#0000dd;">1</span><span style="color:#008000;">]</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span> <span style="color:#666666;">// thread identifier  </span>
<span style="color:#0000dd;">79</span><span style="color:#008080;">:</span>      <span style="color:#0000ff;">if</span> <span style="color:#008000;">(</span>hThread<span style="color:#008000;">[</span><span style="color:#0000dd;">1</span><span style="color:#008000;">]</span><span style="color:#000080;">==</span><span style="color:#0000ff;">NULL</span><span style="color:#008000;">)</span>
<span style="color:#0000dd;">80</span><span style="color:#008080;">:</span>      <span style="color:#008000;">{</span>
<span style="color:#0000dd;">81</span><span style="color:#008080;">:</span>          <span style="color:#0000dd;">printf</span> <span style="color:#008000;">(</span><span style="color:#ff0000;">"Create thread B error: %dn"</span>, GetLastError<span style="color:#008000;">(</span><span style="color:#008000;">)</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">82</span><span style="color:#008080;">:</span>          <span style="color:#0000ff;">return</span> <span style="color:#000040;">-</span><span style="color:#0000dd;">2</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">83</span><span style="color:#008080;">:</span>      <span style="color:#008000;">}</span>
<span style="color:#0000dd;">84</span><span style="color:#008080;">:</span>      WaitForMultipleObjects<span style="color:#008000;">(</span><span style="color:#0000dd;">2</span>,hThread,FALSE,INFINITE<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">85</span><span style="color:#008080;">:</span>      <span style="color:#0000ff;">for</span> <span style="color:#008000;">(</span><span style="color:#0000ff;">int</span> i<span style="color:#000080;">=</span><span style="color:#0000dd;">0</span><span style="color:#008080;">;</span> i<span style="color:#000080;"><</span><span style="color:#0000dd;">2</span><span style="color:#008080;">;</span> i<span style="color:#000040;">++</span><span style="color:#008000;">)</span>
<span style="color:#0000dd;">86</span><span style="color:#008080;">:</span>      <span style="color:#008000;">{</span>
<span style="color:#0000dd;">87</span><span style="color:#008080;">:</span>          CloseHandle<span style="color:#008000;">(</span>hThread<span style="color:#008000;">[</span>i<span style="color:#008000;">]</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">88</span><span style="color:#008080;">:</span>      <span style="color:#008000;">}</span>
<span style="color:#0000dd;">89</span><span style="color:#008080;">:</span>      CloseHandle<span style="color:#008000;">(</span>maxSemaphore<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">90</span><span style="color:#008080;">:</span>      CloseHandle<span style="color:#008000;">(</span>mutex<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">91</span><span style="color:#008080;">:</span>      <span style="color:#0000ff;">return</span> <span style="color:#0000dd;">0</span><span style="color:#008080;">;</span>
<span style="color:#0000dd;">92</span><span style="color:#008080;">:</span>  <span style="color:#008000;">}</span>

Bài 6: Dễ dàng chứng minh với đoạn code đó thì X có thể vượt quá 20. Để đảm bảo X không vượt quá 20, ta chỉ cần sử dụng một trong các giải thuật định thời đã học.

Bài 7:

1
2
3
4
5
6
7
8
9
10
11
12

<span style="color:#666666;">// share data</span>
Semaphore s1, s2<span style="color:#008080;">;</span>
s1<span style="color:#000080;">=</span><span style="color:#0000dd;">0</span><span style="color:#008080;">;</span> s2<span style="color:#000080;">=</span><span style="color:#0000dd;">0</span><span style="color:#008080;">;</span>
<span style="color:#666666;">// do work</span>
A1<span style="color:#008000;">(</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000ff;">signal</span><span style="color:#008000;">(</span>s1<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
B1<span style="color:#008000;">(</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000ff;">signal</span><span style="color:#008000;">(</span>s2<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
wait<span style="color:#008000;">(</span>s2<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
A2<span style="color:#008000;">(</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
wait<span style="color:#008000;">(</span>s1<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
B2<span style="color:#008000;">(</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>

Bài 8: With every k (k>=1), Ak just starts if only Bk-1 has finished and Bk just starts if only Ak-1 has finished.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

<span style="color:#666666;">// Share data</span>
Semaphore S<span style="color:#008000;">[</span><span style="color:#0000dd;">100</span><span style="color:#008000;">]</span><span style="color:#008080;">;</span>
<span style="color:#0000ff;">for</span> <span style="color:#008000;">(</span><span style="color:#0000ff;">int</span> i<span style="color:#000080;">=</span><span style="color:#0000dd;">0</span><span style="color:#008080;">;</span> i<span style="color:#000080;"><</span><span style="color:#0000dd;">100</span><span style="color:#008080;">;</span> i<span style="color:#000040;">++</span><span style="color:#008000;">)</span>
    S<span style="color:#008000;">[</span>i<span style="color:#008000;">]</span>.<span style="color:#007788;">value</span> <span style="color:#000080;">=</span> <span style="color:#0000dd;">0</span><span style="color:#008080;">;</span>
<span style="color:#666666;">// Process A</span>
<span style="color:#0000ff;">for</span> <span style="color:#008000;">(</span><span style="color:#0000ff;">int</span> i<span style="color:#000080;">=</span><span style="color:#0000dd;">0</span><span style="color:#008080;">;</span> i<span style="color:#000080;"><</span><span style="color:#0000dd;">100</span><span style="color:#008080;">;</span> i<span style="color:#000040;">+</span><span style="color:#000080;">=</span><span style="color:#0000dd;">2</span><span style="color:#008000;">)</span>
<span style="color:#008000;">{</span>
    execute Ai
    <span style="color:#0000ff;">signal</span><span style="color:#008000;">(</span>S<span style="color:#008000;">[</span>i<span style="color:#008000;">]</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
    wait<span style="color:#008000;">(</span>S<span style="color:#008000;">[</span>i<span style="color:#008000;">]</span><span style="color:#000040;">+</span><span style="color:#0000dd;">1</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
    execute Ai<span style="color:#000040;">+</span><span style="color:#0000dd;">1</span>
<span style="color:#008000;">}</span>
<span style="color:#666666;">// Process B</span>
<span style="color:#0000ff;">for</span> <span style="color:#008000;">(</span><span style="color:#0000ff;">int</span> j<span style="color:#000080;">=</span><span style="color:#0000dd;">0</span><span style="color:#008080;">;</span> j<span style="color:#000080;"><</span><span style="color:#0000dd;">100</span><span style="color:#008080;">;</span> j<span style="color:#000040;">+</span><span style="color:#000080;">=</span><span style="color:#0000dd;">2</span><span style="color:#008000;">)</span>
<span style="color:#008000;">{</span>
    execute Bj
    <span style="color:#0000ff;">signal</span><span style="color:#008000;">(</span>S<span style="color:#008000;">[</span>j<span style="color:#008000;">]</span><span style="color:#000040;">+</span><span style="color:#0000dd;">1</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
    wait<span style="color:#008000;">(</span>S<span style="color:#008000;">[</span>j<span style="color:#008000;">]</span><span style="color:#008000;">)</span><span style="color:#008080;">;</span>
    execute B<span style="color:#008000;">[</span>j<span style="color:#008000;">]</span><span style="color:#000040;">+</span><span style="color:#0000dd;">1</span><span style="color:#008080;">;</span>
<span style="color:#008000;">}</span>

Bài 9: Sử dụng Semaphore để viết lại chương trình theo mô hình xử lí đồng hành.

Giải quyết đề bài như sau: (ứng với mỗi số được xem như một process hoặc thread).

1
2
3
4
5
6
7

w <span style="color:#008080;">:</span><span style="color:#000080;">=</span> x1 <span style="color:#000040;">*</span> x2 <span style="color:#008000;">(</span><span style="color:#0000dd;">1</span><span style="color:#008000;">)</span><span style="color:#666666;">// 1 starts before 5 and 6</span>
v <span style="color:#008080;">:</span><span style="color:#000080;">=</span> x3 <span style="color:#000040;">*</span> x4 <span style="color:#008000;">(</span><span style="color:#0000dd;">2</span><span style="color:#008000;">)</span><span style="color:#666666;">// 2 starts before 3 and 4</span>
y <span style="color:#008080;">:</span><span style="color:#000080;">=</span> v <span style="color:#000040;">*</span> x5 <span style="color:#008000;">(</span><span style="color:#0000dd;">3</span><span style="color:#008000;">)</span><span style="color:#666666;">// 3 starts after 2 and before 5</span>
z <span style="color:#008080;">:</span><span style="color:#000080;">=</span> v <span style="color:#000040;">*</span> x6 <span style="color:#008000;">(</span><span style="color:#0000dd;">4</span><span style="color:#008000;">)</span><span style="color:#666666;">// 4 starts after 2 and before 6</span>
y <span style="color:#008080;">:</span><span style="color:#000080;">=</span> w <span style="color:#000040;">*</span> y <span style="color:#008000;">(</span><span style="color:#0000dd;">5</span><span style="color:#008000;">)</span><span style="color:#666666;">// 5 starts after 1, 3 and before 7</span>
z <span style="color:#008080;">:</span><span style="color:#000080;">=</span> w <span style="color:#000040;">*</span> z <span style="color:#008000;">(</span><span style="color:#0000dd;">6</span><span style="color:#008000;">)</span> <span style="color:#666666;">// 6 starts after 1, 4 and before 7</span>
ans <span style="color:#008080;">:</span><span style="color:#000080;">=</span> y <span style="color:#000040;">+</span> z <span style="color:#008000;">(</span><span style="color:#0000dd;">7</span><span style="color:#008000;">)</span><span style="color:#666666;">// 7 starts after 5 and 6</span>

Ta sẽ tạo ra các semaphore gồm: s15, s16, s23, s24, s35, s46, s57, s67. Initial value của tất cả các semaphore đều là 0. Giải thích việc đặt tên như sau: process nào thực thi trước sẽ có số đại diện đứng trước, process thực thi sau sẽ có số đại diện đứng sau, ví dụ process 1 thực thi trước process 5 và process 6 nên sẽ có s15, s16.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

<span style="color:#666666;">// Process 1</span>
w <span style="color:#000080;">=</span> x1 <span style="color:#000040;">*</span> x2<span style="color:#008080;">;</span>
<span style="color:#0000ff;">signal</span> <span style="color:#008000;">(</span>s15<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000ff;">signal</span> <span style="color:#008000;">(</span>s16<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#666666;">// Process 2</span>
v <span style="color:#000080;">=</span> x3 <span style="color:#000040;">*</span> x4<span style="color:#008080;">;</span>
<span style="color:#0000ff;">signal</span><span style="color:#008000;">(</span>s23<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#0000ff;">signal</span><span style="color:#008000;">(</span>s24<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#666666;">// Process 3</span>
wait<span style="color:#008000;">(</span>s23<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
y <span style="color:#000080;">=</span> v <span style="color:#000040;">*</span> x5<span style="color:#008080;">;</span>
<span style="color:#0000ff;">signal</span><span style="color:#008000;">(</span>s35<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#666666;">// Process 4</span>
wait<span style="color:#008000;">(</span>s24<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
z <span style="color:#000080;">=</span> v <span style="color:#000040;">*</span> x6<span style="color:#008080;">;</span>
<span style="color:#0000ff;">signal</span><span style="color:#008000;">(</span>s46<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#666666;">// Process 5</span>
wait<span style="color:#008000;">(</span>s15<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
wait<span style="color:#008000;">(</span>s35<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
y <span style="color:#000080;">=</span> w <span style="color:#000040;">*</span> y<span style="color:#008080;">;</span>
<span style="color:#0000ff;">signal</span><span style="color:#008000;">(</span>s57<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#666666;">// Process 6</span>
wait<span style="color:#008000;">(</span>s16<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
wait<span style="color:#008000;">(</span>s46<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
z <span style="color:#000080;">=</span> w <span style="color:#000040;">*</span> z<span style="color:#008080;">;</span>
<span style="color:#0000ff;">signal</span><span style="color:#008000;">(</span>s67<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
<span style="color:#666666;">// Process 7</span>
wait<span style="color:#008000;">(</span>s57<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
wait<span style="color:#008000;">(</span>s67<span style="color:#008000;">)</span><span style="color:#008080;">;</span>
ans <span style="color:#000080;">=</span> y <span style="color:#000040;">+</span> z<span style="color:#008080;">;</span>

Ok, bài giải của mình. Các bạn xem cho ý kiến đúng sai thế nào nha. Thanks a lot .

Learning, Operating System
Bài tập hệ điều hành
This post is licensed under CC BY 4.0 by the author.

Comments powered by Disqus.