Thảo luận Bài 7

Dữ liệu chia sẻ:
semaphore chopstick[5];
Khởi đầu các biến đều là:
1
.
while (1){wait(chopstick[i])wait(chopstick[(i+1) % 5 ] )…
eat
…signal(chopstick[i]);signal(chopstick[(i+1) % 5] );…
think
…}
Giải pháp trên có thể gây ra deadlock Khi tất cả triết gia đói bụng cùng lúc và đồng thời cầm một chiếc đũa bên tay trái
⇒
deadlock Có thể xảy ra trường hợp ách vô hạn định (starvation)

HANDLE s;s = CreateSemaphore(0, n, max, t); //t là tên đèn hiệu hoặc để giá trị 0.WaitForSingleObject(s, timeout); //timeout = INFINITE hoặc số mili giây chờ.RealeaseSemaphore(s, 1, NULL);

Xét hai process: P1 và P2Yêu cầu: lệnh S1 trong P1 cần được thực thi trước lệnh S2 trong P2Định nghĩa semaphore “synch” dùng đồng bộKhởi động semaphore:synch.value= 0Để đồng bộ hoạt động theo yêu cầu, P1 phải định nghĩa như sau:S1;signal(synch);Và P2 định nghĩa như sau:wait(synch);S2;

- Với tác nguyên Wait có vòng lặp vô tận kiểm tra biến đếm S có nhỏ hơn 0 hay không, điều đó làm chocác tiến trình có thể tự khóa mình (Block Itseft) và chuyển sang trạng thái waiting, sau đó xếp vào hàngchờ của đèn hiệu. Trình điếu phối CPU có thể chọn tiến trình khác trong hàng chờ Ready để thực hiện.- Khi một tiến trình nào đó thực hiện lệnh Signal(S), một tiến trình P nào đó đang chờ tại S được lựachọn và đánh thức bằng lệnh WakeUp(P) để chuyển P từ trạng thái Waiting sang trạng thái Ready. Lúcnày trình điều phối có thể cho P thực thi ngay hay không còn tuỳ thuộc vào thuật giải cụ thể.

NguyenBaoLoc70(I22A) đã viết:HANDLE semEmpty, semFull; //hai đèn hiệu
CRITICAL_SECTION critSec;//Biến kiểu Mutex
void Producer(void * p)
{
while (1)
{
// ... Sản xuất (nextProduced)
// Chờ đến khi có chỗ trống
WaitForSingleObject(semEmpty, INFINITE);
EnterCriticalSection(&critSec);
//…Sắp sản phẩm vào Buffer
// Tăng (semFull) lên 1
ReleaseSemaphore(semFull, 1, NULL);
LeaveCriticalSection(&critSec);
SuspendThread(GetCurrentThread());
}
}
void Consumer()
{
int nextConsumed;
while (1)
{
// Chờ đến khi có sản phẩm
WaitForSingleObject(semFull, INFINITE);
EnterCriticalSection(&critSec);
nextConsumed=buffer[out];
out=(out+1)%BUFFER_SIZE;
// Tăng (semEmpty) lên 1
ReleaseSemaphore (semEmpty, 1, NULL);
LeaveCriticalSection(&critSec);
// ... Tiêu thụ (nextConsumed)
SuspendThread(GetCurrentThread());
}
}
- Biến semEmpty dùng để chứa mục quản của đèn hiệu quản lý số vùng trống trong bộ đệm.
- Biến semFull dùng để chứa mục quản của đèn hiệu quản lý số sản phẩm trong bộ đệm.
- CritSec là đối tượng đèn hiệu kiểu mutex dùng để bảo vệ đoạn tương tranh để đảm bảo tính loại trừ lẫn nhau trong công việc của các tiến trình với tài nguyên dùng chung.

Bạn cho mình xin đoạn code của hàm ShowBuffer() nhé? Tks bạn

Có 5 triết gia ngồi ăn trên một bàn tròn và suy nghĩ Mỗi người cần 2 chiếc đũa để ănTrên bàn chỉ có 5 chiếc đũa xếp xoay vòng và xen kẽ mỗi người. Người nào cầm đủ hai chiếc đũa sẽ được ăn.Bài toán này minh hoạ sự khó khăn trong việc phân phối tài nguyên giữa các process sao cho không xảyra deadlock và starvation

sem_t s;
sem_init(&s, 0, n);
sem_wait(&s);
sem_post(&s);

LeThiKimNgan67(I11C) đã viết:Có 5 triết gia ngồi ăn trên một bàn tròn và suy nghĩ Mỗi người cần 2 chiếc đũa để ănTrên bàn chỉ có 5 chiếc đũa xếp xoay vòng và xen kẽ mỗi người. Người nào cầm đủ hai chiếc đũa sẽ được ăn.Bài toán này minh hoạ sự khó khăn trong việc phân phối tài nguyên giữa các process sao cho không xảyra deadlock và starvation

Hay nhỉ. ^^

HANDLE semEmpty, semFull; //hai đèn hiệu
CRITICAL_SECTION critSec;//Biến kiểu Mutex
void Producer(void * p)
{
while (1)
{
// ... Sản xuất (nextProduced)
// Chờ đến khi có chỗ trống
WaitForSingleObject(semEmpty, INFINITE);
EnterCriticalSection(&critSec);
//…Sắp sản phẩm vào Buffer
// Tăng (semFull) lên 1
ReleaseSemaphore(semFull, 1, NULL);
LeaveCriticalSection(&critSec);
SuspendThread(GetCurrentThread());
}
}
void Consumer()
{
int nextConsumed;
while (1)
{
// Chờ đến khi có sản phẩm
WaitForSingleObject(semFull, INFINITE);
EnterCriticalSection(&critSec);
nextConsumed=buffer[out];
out=(out+1)%BUFFER_SIZE; // Tăng (semEmpty) lên 1
ReleaseSemaphore (semEmpty, 1, NULL);
LeaveCriticalSection(&critSec); // ... Tiêu thụ (nextConsumed)
SuspendThread(GetCurrentThread());
}
}
- Biến semEmpty dùng để chứa mục quản của đèn hiệu quản lý số vùng trống trong bộ đệm.
- Biến semFull dùng để chứa mục quản của đèn hiệu quản lý số sản phẩm trong bộ đệm.
- CritSec là đối tượng đèn hiệu kiểu mutex dùng để bảo vệ đoạn tương tranh để đảm bảo tính loại trừ lẫn nhau trong công việc của các tiến trình với tài nguyên dùng chung.

- Đoạn tương tranh :Xét một hệ có n tiến trình P0,P1, ...,Pn, mỗi tiến trình có một đoạn mã lệnh, nếu như trong đoạn mã này các tiến trình thao tác trên các biến chung,đọc ghi file... (tổng quát: thao tác trên dữ liệu chung) thì đoạn mã lệnh đó là đoạn tương tranh.
- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.
- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).
Ví dụ:
ĐƠN XIN VIỆC
Kính gửi: Giám đốc công ty x
Tôi tên là: Nguyễn Thi Lan
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 20 tháng 10năm 2011
Người làm đơn
....(chữ ký)....
Nguyễn Thi Lan


. Nội dung đơn này phải được đảm bảo tính toàn vẹn (Integrity), ví dụ: Phía trên là Lê Văn Ba thì phía dưới cũng phải là Lê Văn Ba.
. Nếu vài tiến trình (hơn 1) cùng sửa đơn trên một lúc (không đảm bảo được tính Loại trừ lẫn nhau) thì nội dung của nó có thể không đúng. Ví dụ, giả sử tiến trình P1 (nhà sản xuất) sửa Nguyễn Thị Lan phía trên thành Nguyễn thị Hương, trong khi P2 (nhà sản xuất khác) sửa Nguyễn Thị Lan phía dưới thành Nguyễn Thị Đào, mà có tiến trình P3 (nhà tiêu thụ) nào đó "lấy" đơn về dùng (để in ra) thì kết quả sẽ không nhất quán như sau:

ĐƠN XIN VIỆC
Kính gửi: Giám đốc công ty x
Tôi tên là: Nguyễn Thi Hương
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 5 tháng 5 năm 2011
Người làm đơn
....(chữ ký)....
Nguyễn Thị Đào

- Mục đích của đồng bộ hóa công việc các tiến trình là đảm bảo Tính nhất quán của tài nguyên chung và Tránh được hiện tượng Deadloack( Hiện tượng kẹt tiến trình )
+ Đảm bảo tính nhất quán của tài nguyên dùng chung.
+ Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình) .
VD1: một trường học chỉ có 1 phòng lab (tài nguyên dùng chung) , lớp có giờ học trước thì được vào phòng lab học, các lớp còn lại phải chờ đến khi lớp học trước đó hết giờ mới được vào phòng lab.

- Đoạn tương tranh là một đoạn mã lệnh trong chương trình, mỗi tiến trình có một đoạn mã lệnh dùng để điều khiển công việc các tiến trình, khi mà các đoạn mã này được thực hiện sẽ tác động đến các tài nguyên hay dữ liệu chung.

- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang vận hành ở trong đoạn tương tranh, thì không có tiến trình nào khác trong nhóm cùng tồn tại chung đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung, nếu như có một tiến trình khác cũng muốn thực hiện cùng đoạn tương tranh đó thì phải đợi cho đến khi tiến trình đó kết thúc và ra khỏi đoạn tương tranh, lúc đó tiến trình khác mới có thể tiếp tục thực hiện công việc trên đoạn tương tranh đó.

- Các tiến trình tương tranh có cấu trúc mã bao gồm:

while(1) {
remainder section //Đoạn còn lại
entry section //Đoạn đăng nhập
critical section //Đoạn tương tranh
exit section //Đoạn đăng xuất
remainder section //Đoạn còn lại
}

Chú thích:
- Đoạn còn lại: (nằm ngoài đoạn tương tranh) không gây ảnh hưởng gì đến tài nguyên dùng chung.
- Đoạn đăng nhập: báo cho các tiến trình khác biết rằng đang có 1 tiến trình đang vận hành đoạn mã tương tranh.
- Đoạn tương tranh: đoạn mã khi thực thi sẽ gây ảnh hưởng đến tài nguyên dùng chung.
- Đoạn đăng xuất: báo cho các tiến trình khác biết rằng hiện chưa có tiến trình vận hành đoạn mã tương tranh.

4 điều kiện dẫn đến Deadlock và giải pháp ngăn chặn Deadlock
- Loại trừ lẫn nhau (Multual Exclusion): Ít nhất có 1 tài nguyên có tính không chia sẻ (non-shareable), nghĩa là mỗi thời điểm chỉ có một tiến trình được sử dụng nó.
- Giữ và chờ (Hold and Wait): Có 1 tiến trình đang giữ tài nguyên và xin thêm tài nguyên đang bị độc chiếm bởi tiến trình khác.
- Không có tiếm quyền (No Preemption): Tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền mà phải được tiến trình này tự nguyện trả lại hệ thống sau khi dùng xong.
- Chờ xoay vòng (Circular Wait): Giả sử có n tiến trình đang chờ tài nguyên là {P1,P2…Pn}, khi đó P1 chờ TN giữ bởi P2, tiến trình P2 chờ TN giữ bởi P3, …, Pn chờ P1.
* Giải pháp ngăn chặn Deadlock
Để ngăn chặn Deadlock ta phải làm sao cho ít nhất 1 trong 4 điều kiện dẫn đến Deadlock không xảy ra. Cụ thể:
- Với Mutual Exclusion: Đảm bảo TN nào cũng dùng chung được cùng một lúc bởi nhiều tiến trình.
- Với Hold and Wait:
1- Khi TT yêu cầu TN, nó không được giữ 1 TN nào khác.
2- TT phải yêu cầu và được cấp tất cả các TN mà nó cần ngay đầu công việc.
- Với No Preemption:
1- Khi TT giữ TN mà xin thêm nhưng không được, các TN mà nó giữ phải bị tiếm quyền sử dụng và trả lại HĐH.
2- Khi TT xin thêm TN, nếu TN này đang được giữ bởi TT khác đang ở trạng thái chờ, TN của TT khác này bị tiếm quyền sử dụng để cấp cho TT đang xin.
- Với Circular Wait: Cấp TN theo một thứ tự nào đấy
Ví dụ : kẹt xe giữa đường hay cầu , chỉ cần 1 cái j đó để nhấc các thành phần gây ra kẹt xe ở chỗ bị kẹt 1 thời gian để xe lưu thông là sẽ có thể giải quyết tình trạng này.
* Ngăn chặn deadlock (bằng cách phủ định 1 trong 4 điều kiện):
Loại bỏ các điều kiện dẫn đến deadlock.
Các điều kiện xem như không thể loại bỏ:
Loại trừ tương hỗ.
Không lấy lại tài nguyên từ process.
Loại bỏ điều kiện loại trừ tương hỗ (loại trừ lẫn nhau):
Giảm số tài nguyên tranh chấp.
Tăng số lượng tài nguyên.
Cấp phát tài nguyên dạng spool.
Vd: chỉ 1 printer daemon dùng máy in.
+ Các process gởi yêu cầu cho printer daemo

• Loại bỏ điều kiện giữ và chờ tài nguyên:

• Nguyên tắc: process không được giữ tài nguyên khi yêu cầu tài nguyên mới. Process khai báo tài nguyên và được cấp phát 1 lần. Nếu process yêu cầu tài nguyên và không được cấp phát thì phải trả các tài nguyên đang giữ.

• Loại bỏ điều kiện không lấy lại tài nguyên (không có tiếm quyền)

• Lấy lại tài nguyên từ proces

Thực thi bài toán sản xuất,tiêu thụ được đồng bộ bằng 3 đèn hiệu
HANDLE semEmpty, semFull; //hai đèn hiệu
CRITICAL_SECTION critSec;//Biến kiểu Mutex
void Producer(void * p)
{
while (1)
{
// ... Sản xuất (nextProduced)
// Chờ đến khi có chỗ trống
WaitForSingleObject(semEmpty, INFINITE);
EnterCriticalSection(&critSec);
//…Sắp sản phẩm vào Buffer
// Tăng (semFull) lên 1
ReleaseSemaphore(semFull, 1, NULL);
LeaveCriticalSection(&critSec);
SuspendThread(GetCurrentThread());
}
}
void Consumer()
{
int nextConsumed;
while (1)
{
// Chờ đến khi có sản phẩm
WaitForSingleObject(semFull, INFINITE);
EnterCriticalSection(&critSec);
nextConsumed=buffer[out];
out=(out+1)%BUFFER_SIZE;
// Tăng (semEmpty) lên 1
ReleaseSemaphore (semEmpty, 1, NULL);
LeaveCriticalSection(&critSec);
// ... Tiêu thụ (nextConsumed)
SuspendThread(GetCurrentThread());
}
}
- Biến semEmpty dùng để chứa mục quản của đèn hiệu quản lý số vùng trống trong bộ đệm.
- Biến semFull dùng để chứa mục quản của đèn hiệu quản lý số sản phẩm trong bộ đệm.
- CritSec là đối tượng đèn hiệu kiểu mutex dùng để bảo vệ đoạn tương tranh để đảm bảo tính loại trừ lẫn nhau trong công việc của các tiến trình với tài nguyên dùng chung.

Thực thi đèn hiệu có hàng chờ
- Với tác nguyên Wait có vòng lặp vô tận kiểm tra biến đếm S có nhỏ hơn 0 hay không, điều đó làm cho các tiến trình có thể tự khóa mình (Block Itseft) và chuyển sang trạng thái waiting, sau đó xếp vào hàng chờ của đèn hiệu. Trình điếu phối CPU có thể chọn tiến trình khác trong hàng chờ Ready để thực hiện.
- Khi một tiến trình nào đó thực hiện lệnh Signal(S), một tiến trình P nào đó đang chờ tại S được lựa chọn và đánh thức bằng lệnh WakeUp(P) để chuyển P từ trạng thái Waiting sang trạng thái Ready. Lúc này trình điều phối có thể cho P thực thi ngay hay không còn tuỳ thuộc vào thuật giải cụ thể.

Thuật giải cho Xe qua cầu:
While(1)
{
Đi đến cầu;
Wait (mutex);
lên cầu;
qua cầu;
Signal(mutex);
đi tiếp;
quay về theo cầu khác;
}
Giải thích:
Đầu tiên xe đi đến cầu. nếu đèn mutex màu xanh tức là chưa có xe nào trên cầu ( chưa có tiến trình nào bước vào đoạn tương tranh ) thì xe được phép lên cầu và bước vào đoạn tương tranh, lúc này đèn mutex chuyễn sang đỏ. Trong lúc xe A đang qua cầu nếu có xe khác tới cầu gặp đèn đỏ thì nó phải ngủ chờ trước đèn tín hiệu. khi xe A qua cầu và rời khỏi cầu thì đèn mutex chuyển sang xanh báo hiệu xe kế tiếp có thể qua cầu. Lúc này HDH sẽ đánh thức một xe đang ngủ dậy để qua cầu. Cứ như thế các xe khác tiếp tục lên cầu và qua cầu.

ví dụ:
- Bài toán sản xuất tiêu thụ.
Thầy viết lên bảng (tài nguyên dùng chung của lớp) thông tin cá nhân nhưng chưa ghi xong thì bạn khác dưới lớp chụp lại thông tin trên sẽ không đúng. Muốn lấy thông tin chính xác thì các bạn dưới lớp cần lấy thông tin của thầy trên bảng ghi phải chờ thầy ghi hết thông tin rồi mới chụp ảnh.
- Tránh Deadlock ( hiện tượng kẹt tiến trình).
ví dụ: một trường học chỉ có 1 phòng máy (tài nguyên dùng chung) ,lớp có giờ học trước thì được vào phòng máy học, các lớp còn lại phải chờ đến khi lớp học trước đó hết giờ mới được vào học.

Định nghĩa Semaphore
Định nghĩa: Semaphore là một cờ hiệu trong thực thi đa tuyến, nếu một tuyến cần sử dụng tài nguyên nó sẽ thông báo với semaphore.
-Khởi đầu Semaphore mang giá trị dương. Tuyến yêu cầu sử dụng tài nguyên bằng cách gọi hàm sem_wait(), semaphore sẽ kiểm tra giá trị của mình xem có >0 hay không.
-Nếu Semaphore vẫn còn >0, nó sẽ tự động làm giảm giá trị đi 1 và cho phép tuyến sử dụng tài nguyên.
-Nếu giá trị Semaphore <=0 hệ thống sẽ tạm thời dừng tuyến.
-Khi một tuyến sử dụng xong tài nguyên nó gọi hàm sem_post() để trả quyền sử dụng tài nguyên lại cho Semaphore cấp phát cho lần sử dụng khác.
Ứng dụng Semaphore:
-Bài toán nổi tiếng về tranh chấp tài nguyên dễ hiểu nhất là bài toán “sản xuất – tiêu thụ”.
-Hai tuyến chạy song song nhau. Một tuyến chịu trách nhiệm sản xuất ra sản phẩm. Một tuyến lấy sản phẩm ra để tiêu thụ.

Ví dụ đoạn tương tranh và vùng tương tranh
Ví dụ : hai đoạn mã là đoạn tương tranh trong việc sử dụng đèn hiệu
1.wait (semaphore S) {
while ( S <= 0 ); // chờ bận nếu S<=0
S --; // Giảm S đi 1
}

2.signal (semaphore S) {
S ++; //Tăng S lên 1
}

Vùng tranh chấp: là vùng chứa các biến dùng chung mà các đoạn mã tương tranh tác động.
Ví dụ :
Trong ví dụ các chuyến xe qua chung 1 cây cầu có đèn hiệu thì cây cầu chính là "vùng tranh chấp". Chiếc xe thứ nhất đang qua cầu thì đèn đang đỏ, các xe tiếp theo đứng chờ cho đến khi xe thứ nhất qua bên kia cầu, đèn xanh bật lên thì xe thứ hai tiếp tục qua cầu.

Admin
Trong Ví dụ trên, chưa thấy nêu Đoạn tương tranh ở đâu cả !

Khái niệm đèn hiệu
- Đèn hiệu là phương tiện đồng bộ hoá được E.W. Dijkstra đề xuất năm 1965.
- Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu):

typedef int semaphore; // Định nghĩa kiểu Đèn hiệu
wait (semaphore S)
{
while ( S <= 0 ); // Chờ bận nếu S<=0
S --; // Giảm S đi 1
}

signal (semaphore S)
{
S ++; // Tăng S lên 1
}

-Việc kiểm tra S <= 0 và giảm S (trong Wait) hoặc tăng S (trong Signal) phải được thực hiện trọn vẹn (không xảy ra ngắt trong thời gian thi hành), do đó Wait và Signal được gọi là các tác nguyên (Atomic Operations)

Giả sử có n tiến trình . Mỗi tiến trình có đoạn mã gọi là Đoạn tương tranh trong đó tiến trình có thể truy cập và thay đổi vùng nhớ ,tập tin hay tài nguyên chung.
- Tính loại trừ lẫn nhau hay loại trừ tương hỗ về phương diện thời gian : khi có 1 tiến trình đang ở trong đoạn tương tranh của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy , nghĩa là : Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và thay đổi tài nguyên chung.
- Các tiến trình có cấu trúc mã bao gồm :

Đoạn đăng nhập
Đoạn tương tranh
Đoạn đăng xuất
Đoạn còn lại

Vậy để giải quyết vấn đề này thì phải thỏa các ĐK sau :

Loại trừ lẫn nhau : Mỗi thời điểm chỉ có 1 tiến trình vận hành trong đoạn tương tranh
Tiến triển : Không có tiến trình nào phải chờ vô hạn tại Đoạn đăng nhập

 Xét trường hợp 2 process (P0 và P1) và một tài nguyên
 Hai process dùng chung:
- Biến turn: xác định đến phiên process nào vào vùng tranh chấp.
- Mảng boolean interested[2]: thể hiện process sẵn sàng vào vùng tranh chấp.
- Interested[0] : P0 sẵn sàng vào vùng tranh chấp.
- Khởi động interested[0] = interested[1]=FALSE

Trong mô hình truy cập cơ sở dữ liệu trên môi trường nhiều người dùng, bài toán đồng bộ liên quan đến việc nhiều người cùng đọc, ghi trên một số bảng cơ sở dữ liệu. Một quá trình đọc cơ sở dữ liệu gọi là bộ đọc (reader). Quá trình cập nhật dữ liệu gọi là bộ ghi (writter).Ví dụ, một hệ thống bán vé máy bay có nhiều quá trình cùng thực hiện thao tác đọc, ghi trên cơ sở dữ liệu khách hàng. Có hai ràng buộc cần tuân thủ để đạt đồng bộ đọc, ghi. Thứ nhất, tại một thời điểm, hệ thống cho phép chỉ một quá trình cập nhật dữ liệu và nhiều quá trình đọc. Tương tự, ràng buộc thứ hai là: khi một số quá trình đang đọc, không có quá trình nào được phép cập nhật dữ liệu. Phần này, ta xét đến cách thức áp dụng các giải pháp trên với bài toán reader - writter.

Giải pháp thông dụng là sử dụng một semaphore db để cài đặt cơ chế độc quyền truy cập trên cơ sở dữ liệu. Số lượng các reader muốn truy cập dữ liệu được biểu thị bởi biến rc. Cuối cùng semaphore mutex kiếm soát việc truy cập đến rc.

 Một cửa hiệu cắt tóc có một thợ, một ghế cắt tóc và N ghế cho khách đợi.
 Nếu không có khách hàng, anh thợ cắt tóc sẽ ngồi vào ghế cắt tóc và ngủ thiếp đi.
 Khi một khách hàng vào tiệm, anh ta phải đánh thức người thợ.
 Nếu một khách hàng vào tiệm khi người thợ đang bận cắt tóc cho khách hàng khác, người mới vào sẽ phải ngồi chờ nếu có ghế đợi trống, hoặc rời khỏi tiệm nếu đã có N người đợi.