PHÁT BIỂU BÀI TOÁN SẢN XUẤT - TIÊU THỤ VỚI THUẬT GIẢI ĐỒNG BỘ HÓA BẰNG 3 ĐÈN HIỆU semFull, semEmpty và Mutex

PHÁT BIỂU BÀI TOÁN SẢN XUẤT - TIÊU THỤ VỚI THUẬT GIẢI ĐỒNG BỘ HÓA BẰNG 3 ĐÈN HIỆU semFull, semEmpty và Mutex

Tiến trình sản xuất( Producer) tạo ra dòng thông tin để tiến trình tiêu thụ(Consumer) sử dụng.
Ví dụ: Compiler và Assembler vừa là nhà sản xuất vừa là nhà tiêu thụ.Compiler tạo ra mã dùng cho Assembler, tiếp theo Assembler sản sinh mã máy làm đầu vào cho Loader hoặc Linkage Editor.
Phát biểu bài toán
- Giả sử có Bộ nhớ đệm(Buffer) bao gồm 1 số hữu hạn các khoang chứa(Items) được tiến trình Producer lần lượt đưa vào các sản phẩm S1, S2, ...vào.
- Tiến trình Consumer lấy sản phẩm ra theo đúng thứ tự.
- Công việc của Producer phải đồng bộ với Consumer.Không đưa ra sản phẩm khi hết chỗ trống, không lấy được sản phẩm khi chưa có.

Thuật giải đồng bộ hóa bằng 3 đèn hiệu: Bài toán sản xuất - tiêu thụ(Producer - Consumer)thường được dùng để hiển thị sức mạnh của các hàm cơ sở đồng bộ hóa.Hai quá trình cùng chia sẻ một vùng đệm có kích thước giới hạn n. Biến mutex đảm bảo sự loại trừ hỗ tương để truy xuất vùng đệm (nghĩa là mỗi thời điểm chỉ có 1 tiến trình sản xuất hay tiêu thụ được truy cập/ cập nhật tài nguyên dùng chung) và được khởi tạo với giá trị 1. Các biến semEmpty và semFull đếm số khe trống và đầy tương ứng. Biến semEmpty được khởi tạo tới giá trị n; biến semFull được khỏi tạo tới giá trị 0.

Thuật giải cho Producer:

Code:

// Tạo ra sản phẩm mới
wait(semEmpty);
wait(mutex);
//Đưa sản phẩm vào bộ đệm Buffer
Buffer[in]=sp mới;//Xếp sản phẩm vào bộ đệm.
in=(in+1)%BUFFER_SIZE;
signal(semFull);
signal(mutex);


Thuật giải cho Consumer:

Code:

wait(semFull);
wait(mutex);
// Lấy sản phẩm từ bộ đệm Buffer
p=Buffer[out];
out=(out+1)%BUFFER_SIZE;
// Tiêu thụ sản phẩm vừa lấy được
signal(semEmpty);
signal(mutex);

Các bạn cho ý kiến đóng góp bài tập này cho hoàn thiện nhé. Bài tập này của Thày cho làm ở lớp đó!

Admin
Hai hàm trên được trình bày tốt.

Những đoạn code của thầy có bạn nào có không, post lên cho mọi người tham khảo với. Mình vừa nghe thầy giãng, vừa ghi mà ghi không kịp. Thanks mọi người nhiều...

KimThao_I83C_08H1012087 đã viết:Những đoạn code của thầy có bạn nào có không, post lên cho mọi người tham khảo với. Mình vừa nghe thầy giãng, vừa ghi mà ghi không kịp. Thanks mọi người nhiều...

Đây nè bạn


#include <stdio.h>
#include <conio.h>
#include <windows.h>

#define BUFFER_SIZE 10

int buffer[BUFFER_SIZE];
char s[BUFFER_SIZE]; // chứa kí hiệu của nhà sx sản xuất ra chứa trong buffer

int in=0;
int out=0;

int nextProduced=1;

HANDLE semEmpty, semFull; // hai biến chứa mục khoản Hai đèn hiệu, semEmpty quản lý số vùng trống trong bộ đệm
// semFull dùng chứa mục quản đèn hiệu qlý số sản phẩm trong bộ đệm
//semFull tăng 1 thì semEmpty giảm 1 và ngược lại

CRITICAL_SECTION critSec; // Biến kiểu Mutex cũng là một đèn hiệu nhị phân biểu diễn đoạn tương tranh

void Producer(void * p – biến con trỏ chứa địa chỉ 32bit){
while (1){ - vòng lặp bất tận
// ... Sản xuất (nextProduced)
// Chờ đến khi có chỗ trống

WaitForSingleObject(semEmpty, INFINITE); //ngủ thay cho một vòng busy-wiating, chờ bất tận cho đến khi giá trị đèn hiệu lớn hơn 1(xanh), buffer có chỗ trống

EnterCriticalSection(&critSec); // xin phép vào đoạn tương tranh

buffer[in]=nextProduced++; // đưa thêm 1 sp vào buffer, đèn hiệu chuyển màu đỏ

switch ((int)p){
case 1:
s[in]=’P’; // kí hiệu nhà sx thứ 1
break;
case 2:
s[in]=’p’;// kí hiệu nhà sx thứ 2
break;
default:
s[in]=’S’;
};
in=(in+1)%BUFFER_SIZE;
// Tăng (semFull) lên 1
ReleaseSemaphore(semFull, 1, NULL);

LeaveCriticalSection(&critSec); // ra khỏi đoạn tương tranh

SuspendThread(GetCurrentThread()); // ngủ cho đến khi được đánh thức
}
}

void Consumer(){
int nextConsumed;
while (1){
// Chờ đến khi có sản phẩm
WaitForSingleObject(semFull, INFINITE); // chờ đến khi giá trị semFull >= 1
// tiêu thục chờ semFull, sx chờ semEmp
EnterCriticalSection(&critSec); // đoạn đăng nhập

nextConsumed=buffer[out]; // tiêu thụ vị trí out
out=(out+1)%BUFFER_SIZE; // tăng out

// Tăng (semEmpty) lên 1
ReleaseSemaphore (semEmpty, 1, NULL);

LeaveCriticalSection(&critSec); // đoạn đăng xuất

// ... Tiêu thụ (nextConsumed)

SuspendThread(GetCurrentThread()); // ngủ bất tận cho đến khi đc đánh thức
}
}

void ShowBuffer(){ // In nội dung bộ đệm
const char * LeftMargin="\n ";
int i;

printf(LeftMargin);

for(i=0; i<(in*5); i++) putchar(' '); printf("!in");
printf(LeftMargin);

for (i=0; i<BUFFER_SIZE-1; i++)
printf("%c%2d, ", s[i], buffer[i]);
printf("%c%2d", s[BUFFER_SIZE-1], buffer[BUFFER_SIZE-1]);

printf(LeftMargin);

for(i=0; i<(out*5); i++) putchar(' ');
printf("^out");

printf("\n");
}

int main(){
HANDLE ProducerHandle1, ProducerHandle2;
HANDLE ConsumerHandle1, ConsumerHandle2;

DWORD ProducerID1, ProducerID2;
DWORD ConsumerID1, ConsumerID2;

semEmpty=CreateSemaphore(0, BUFFER_SIZE, BUFFER_SIZE, 0); // buffer_size = 10 --> có 11 màu, giá trị ban đầu = 10, gtrị tối đa = 10, ko tên
semFull=CreateSemaphore(0, 0, BUFFER_SIZE, 0);// màu ban đầu = 0, gtrị tối đa là 10

InitializeCriticalSection(&critSec); // khởi lập gtrị ban đầu cho critSec, hai trạng thái, ban đầu =1 – xanh

// Tạo các luồng nhưng ở trạng thái ngủ (Suspend)
ProducerHandle1=CreateThread(0,0,
(LPTHREAD_START_ROUTINE)Producer, (void *) 1 // truyền gtrị 1 cho luồng, ép sang kiểu void *, 4, &ProducerID1);
ProducerHandle2=CreateThread(0,0,
(LPTHREAD_START_ROUTINE)Producer, (void *) 2, 4, &ProducerID2);

ConsumerHandle1=CreateThread(0,0,
(LPTHREAD_START_ROUTINE)Consumer, 0, 4, &ConsumerID1); // ngủ
ConsumerHandle2=CreateThread(0,0,
(LPTHREAD_START_ROUTINE)Consumer, 0, 4, &ConsumerID2); // ngủ

while(1)
{
printf("\n- Nhấn P/p để sản xuất, C/c để tiêu thụ:");
switch (getch()){
case 'P': // Đánh thức luồng SX 1
ResumeThread(ProducerHandle1);
break;
case 'p': // Đánh thức luồng SX 2
ResumeThread(ProducerHandle2);
break;
case 'C': // Đánh thức luồng TT 1
ResumeThread(ConsumerHandle1);
break;
case 'c': // Đánh thức luồng TT 2
ResumeThread(ConsumerHandle2);
break;
case '0': // Kết thúc ứng dụng
printf("\n");
CloseHandle(semEmpty);
CloseHandle(semFull);
DeleteCriticalSection(&critSec);
return 0;
}
EnterCriticalSection(&critSec);
ShowBuffer(); // nằm trong đoạn tương tranh vì có truy xuất BUFFER là tài nguyên dùng chung, khi đang show thì không sx, không tiêu thụ.
LeaveCriticalSection(&critSec);
}
}

Mình post luôn code C# 2005 của thầy
- Form BufferState :(frmBufferState.cs)

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;

using System.Threading;


namespace SanXuatTieuThu2005
{
public partial class frmBufferState : Form
{
public frmBufferState()
{
InitializeComponent();
}

int topLblIn, topLblOut;

private void frmBufferState_Load(object sender, EventArgs e)
{
topLblIn = this.lblIn.Top;
topLblOut = this.lblOut.Top;
}

private void timer1_Tick(object sender, EventArgs e)
{
Program.mutex.WaitOne();

for (int i = 0; i < Program.BUFFER_SIZE; i++)
{
this.Controls["txtItem"+i.ToString()].Text = "S"+Program.buffer[i].ToString();
this.Controls["txtProducer" + i.ToString()].Text = "P" + Program.s[i].ToString();
}

lblIn.Top = this.Controls["txtItem" + Program.ptrIn.ToString()].Top;
lblOut.Top = this.Controls["txtItem" + Program.ptrOut.ToString()].Top;

Program.mutex.ReleaseMutex();
}

}
}

- Form Panel (frmPanel.cs)
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;

using System.Threading;// dùng cho Semaphore

namespace SanXuatTieuThu2005
{
public partial class frmPanel : Form
{
public frmPanel()
{
InitializeComponent();
}
// hai mảng luồng
Thread[] thrConsumers = new Thread[Program.numConsumers];
Thread[] thrProducers = new Thread[Program.numProducers];
// ko cần HANDLE
Semaphore semEmpty, semFull;// chứa đối tượng thuộc lớp Semaphore (đèn hiệu), không dùng HANDLE
// C# ko dùng biến con trỏ
int NextProduced;
int NextConsumed;


private void btnStart_Click(object sender, EventArgs e)
{
(new frmBufferState()).Show();

NextProduced = 1;

semEmpty = new Semaphore(Program.BUFFER_SIZE, Program.BUFFER_SIZE, "E");// đèn hiệu có tên E
semFull = new Semaphore(0, Program.BUFFER_SIZE, "F");// đèn hiệu có tên F

Program.mutex = new Mutex();

for (int i = 0; i < Program.numProducers; i++)
{
thrProducers[i] = new Thread(new ParameterizedThreadStart(Producer));
thrProducers[i].Priority = ThreadPriority.Normal;
thrProducers[i].Start(i);
}
for (int i = 0; i < Program.numConsumers; i++)
{
thrConsumers[i] = new Thread(new ParameterizedThreadStart(Consumer));
thrConsumers[i].Priority = ThreadPriority.Normal;
thrConsumers[i].Start(i);
}
}

public void Producer(object id)
{
while(true)
{
Thread.Sleep((int)(DateTime.Now.Ticks % 2000));
semEmpty.WaitOne();// chờ tại đèn hiệu semEmpty
//WaitOne - chờ một lát
Program.mutex.WaitOne();// xin phép vào đoạn tương tranh
Program.buffer[Program.ptrIn] = NextProduced++;
Program.s[Program.ptrIn] = ((int)id) + 1;
Program.ptrIn = (Program.ptrIn + 1) % Program.BUFFER_SIZE;
semFull.Release();
Program.mutex.ReleaseMutex();
}
}

public void Consumer(object id)
{
while (true)
{
Thread.Sleep((int)(DateTime.Now.Ticks % 1500));
semFull.WaitOne();
Program.mutex.WaitOne();
NextConsumed = Program.buffer[Program.ptrOut];
Program.ptrOut = (Program.ptrOut + 1) % Program.BUFFER_SIZE;
semEmpty.Release();
Program.mutex.ReleaseMutex();
}
}

private void btnSuspend_Click(object sender, EventArgs e)
{
for (int i = 0; i < Program.numProducers; i++)
{
thrProducers[i].Suspend();
}
for (int i = 0; i < Program.numConsumers; i++)
{
thrConsumers[i].Suspend();
}
btnProducer1.ForeColor = Color.Gray;
}

private void btnResume_Click(object sender, EventArgs e)
{
for (int i = 0; i < Program.numProducers; i++)
{
if (thrProducers[i].ThreadState == ThreadState.Suspended)
thrProducers[i].Resume();
}
for (int i = 0; i < Program.numConsumers; i++)
{
if (thrConsumers[i].ThreadState == ThreadState.Suspended)
thrConsumers[i].Resume();
}
btnProducer1.ForeColor = Color.Black;
}


private void frmPanel_FormClosing(object sender, FormClosingEventArgs e)
{
try
{
for (int i = 0; i < Program.numProducers; i++)
{
if (thrProducers[i].ThreadState == ThreadState.Suspended)
thrProducers[i].Resume();
thrProducers[i].Abort();
}
for (int i = 0; i < Program.numConsumers; i++)
{
if (thrConsumers[i].ThreadState == ThreadState.Suspended)
thrConsumers[i].Resume();
thrConsumers[i].Abort();
}
}
catch (Exception e1) { }
}

private void btnProducer1_Click(object sender, EventArgs e)
{
if (thrProducers[0].ThreadState == ThreadState.Suspended)
{
thrProducers[0].Resume();
btnProducer1.ForeColor = Color.Black;
}
else
{
thrProducers[0].Suspend();
btnProducer1.ForeColor = Color.Gray;
}
btnProducer1.Refresh();
}

private void frmPanel_Load(object sender, EventArgs e)
{

}

}
}

- Program.cs
using System;
using System.Collections.Generic;
using System.Windows.Forms;

using System.Threading;

namespace SanXuatTieuThu2005
{
static class Program
{
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main()
{
Application.EnableVisualStyles();
Application.SetCompatibleTextRenderingDefault(false);
Application.Run(new frmPanel());
}
// toàn bộ là tài nguyên dùng chung
public const int BUFFER_SIZE = 10;

public const int numProducers = 6;
public const int numConsumers = 4;

public static int[] buffer = new int[BUFFER_SIZE];
public static int[] s = new int[BUFFER_SIZE];

public static int ptrIn = 0, ptrOut = 0; // hai con trỏ In và Out

public static Mutex mutex; // đèn hiệu mutex


}
}

Tất cả các code thầy giảng đều có trong các file đi kèm slides của thầy rùi mà, bạn down file zip bài giảng của thầy về là có hết

nếu bạn để ý thì sẽ thấy là phần mình post lên có cả lời giải thích của thầy trên lớp

ngocdangI83C đã viết:nếu bạn để ý thì sẽ thấy là phần mình post lên có cả lời giải thích của thầy trên lớp

Cảm ơn bạn ngocdang nhiều.

VuThanhLongI92 đã viết:Tất cả các code thầy giảng đều có trong các file đi kèm slides của thầy rùi mà, bạn down file zip bài giảng của thầy về là có hết

Vậy bạn Long gửi lại giúp mình fil zip này nha. Mình sử dụng tài liệu cũ nên không có code. Cám ơn bạn trước nha.