Giới thiệu thuật toán semaphore trong Hệ điều hành

Để loại bỏ vấn đề lãng phí các wake-up signals, Dijkstra đã đề xuất một phương pháp liên quan đến việc lưu trữ tất cả các wake-up calls. Dijkstra nói rằng, thay vì đưa ra các wake-up calls trực tiếp cho consumer, producer  có thể lưu trữ các wake-up calls trong một biến. Bất kỳ consumer nào cũng có thể đọc nó bất cứ khi nào họ cần.

Semaphore là các biến lưu trữ toàn bộ các wake-up signals đang được chuyển từ producer sang consumer. Nó là một biến mà việc đọc, sửa đổi và cập nhật diễn ra tự động trong kernel mode.

Semaphore trong Hệ điều hành là gì ?

Semaphore trong hệ điều hành là một kiểu dữ liệu được sử dụng để đồng bộ hóa việc truy cập vào tài nguyên chung giữa nhiều tiến trình hoặc luồng. Nó giống như một từa đồng hồ, với mỗi từa đồng hồ là một tài nguyên đặc biệt. Khi một tiến trình hoặc luồng muốn truy cập vào một tài nguyên, nó sẽ yêu cầu từa đồng hồ tương ứng. Nếu từa đồng hồ có sẵn, nó sẽ được giữ bởi tiến trình hoặc luồng đó và không có tiến trình hoặc luồng nào khác có thể truy cập vào tài nguyên đó cho đến khi tiến trình hoặc luồng đó hoàn tất và giải phóng từa đồng hồ.

Semaphore là một phần quan trọng của hệ thống điều hành, vì nó cung cấp một cách để giữ cho việc truy cập vào tài nguyên chung an toàn và không xung đột. Nó cũng giúp tránh tình trạng của các tiến trình hoặc luồng chờ vô hạn cho tài nguyên mà họ cần, giúp cho hệ thống hoạt động mượt mà hơn.

Các bài viết liên quan:

• Cách tạo liên kết bằng lời chứng thực và bài đánh giá
• Hướng dẫn tạo đánh giá 5 sao trên Google
• Lập lịch FCFS trong Operating System
• Synchronization Mechanism mà không cần chờ đợi
• Tìm hiểu về Process trong hệ điều hành
• Quy trình Test case review trong kiểm thử phần mềm
• Dịch vụ viết bài Review sản phẩm
• Plugin Review cho wordpress
• Process Synchronization trong hệ điều hành 
• Cơ chế Interested Variable trong hệ điều hành
• Sử dụng process trong Node.js
• Deadlock trong hệ điều hành? kiến thức cơ bản

Semaphore không thể được thực hiện trong chế độ người dùng vì race condition có thể luôn phát sinh khi hai hoặc nhiều quy trình cố gắng truy cập biến đồng thời. Nó luôn cần sự hỗ trợ từ hệ điều hành để được thực hiện.

Ưu điểm và nhược điểm của semaphore trong Hệ điều hành

Semaphore trong hệ điều hành là một công cụ quản lý tài nguyên cho phép một hoặc nhiều tiến trình cùng sử dụng một tài nguyên cụ thể. Semaphore được sử dụng để giải quyết vấn đề về tài nguyên chia sẻ trong hệ điều hành để đảm bảo tính đồng bộ và an toàn.

Ưu điểm của semaphore:

• Giải quyết vấn đề tài nguyên chia sẻ: Semaphore cho phép nhiều tiến trình cùng sử dụng một tài nguyên cụ thể mà không gặp rủi ro xung đột hoặc gây hại.
• Tính đồng bộ: Semaphore đảm bảo tính đồng bộ giữa các tiến trình cùng sử dụng tài nguyên.
• Tăng hiệu suất: Semaphore có thể tăng hiệu suất hệ thống bằng cách cho phép nhiều tiến trình đồng thời sử dụng tài nguyên.

Nhược điểm của semaphore:

• Phức tạp: Semaphore có thể rất phức tạp để thiết kế và triển khai, đặc biệt với hệ thống phức tạp.
• Tốn thời gian: Semaphore có thể tốn thời gian trong việc quản lý tài nguyên và có thể giảm hiệu suất.

Các loại Semaphore

Theo nhu cầu của tình hình, Semaphore có thể được chia thành hai loại.

• Counting Semaphore
• Binary Semaphore hoặc Mutex

Chúng tôi sẽ thảo luận chi tiết từng cái một.

Counting Semaphore

Có những tình huống trong đó nhiều hơn một Process cần thực hiện đồng thời trong critical section. Tuy nhiên, counting semaphore có thể được sử dụng khi chúng ta cần có nhiều hơn một Process trong critical section cùng một lúc.

Mã lập trình của việc triển khai semaphore được hiển thị bên dưới, bao gồm cấu trúc của semaphore và logic sử dụng mục nhập và lối ra có thể được thực hiện trong critical section.

struct Semaphore  
{  
    int value; // processes that can enter in the critical section simultaneously.   
    queue type L; // L contains set of processes which get blocked   
}  
Down (Semaphore S)  
{  
    SS.value = S.value - 1; //semaphore's value will get decreased when a new   
    //process enter in the critical section   
    if (S.value< 0)  
    {  
        put_process(PCB) in L; //if the value is negative then   
        //the process will get into the blocked state.  
        Sleep();   
    }  
    else  
        return;  
}  
up (Semaphore s)  
{  
    SS.value = S.value+1; //semaphore value will get increased when   
    //it makes an exit from the critical section.   
    if(S.value<=0)  
    {  
        select a process from L; //if the value of semaphore is positive   
        //then wake one of the processes in the blocked queue.   
        wake-up();  
    }  
    }  
}  

Trong cơ chế này, việc nhập và xuất trong phần tới hạn được thực hiện trên cơ sở giá trị couting semaphore. Giá trị couting semaphore tại bất kỳ thời điểm nào cho biết số lượng process tối đa có thể nhập vào critical section cùng một lúc.

Một process muốn nhập vào critical section trước tiên hãy giảm giá trị semaphore đi 1 và sau đó kiểm tra xem nó có bị âm hay không. Nếu nó bị âm thì process sẽ bị đẩy vào danh sách các blocked processes, nếu không thì nó sẽ được nhập vào critical section.

Khi một Process thoát khỏi critical section, nó sẽ tăng couting semaphore đang lên 1 và sau đó kiểm tra xem nó là số âm hay số không. Nếu nó là âm thì điều đó có nghĩa là ít nhất một process đang đợi ở blocked state, do đó, để đảm bảo việc chờ có giới hạn, process đầu tiên trong danh sách các blocked processes sẽ wake up và được nhập vào critical section.

Các Process trong blocked processes sẽ được wake up theo thứ tự mà chúng đã ngủ. Nếu giá trị đếm semaphore là số âm thì nó cho biết số lượng Process ở blocked processes trong khi nếu nó là dương thì nó cho biết số lượng process có sẵn trong critical section.

Vấn đề về Couting Semaphore

Các câu hỏi đang được hỏi về couting semaphore trong GATE. Nói chung các câu hỏi rất đơn giản chỉ bao gồm phép trừ và phép cộng.

1. Wait → Decre → Down → P   
2. Signal → Inc → Up → V  

Các câu hỏi loại sau có thể được hỏi trong GATE.

Một Semaphore đếm được khởi tạo thành 12. sau đó các hoạt động 10P (chờ) và 4V (Tín hiệu) được tính trên semaphore này. Kết quả là gì?

S = 12 (initial)   
10 p (wait) :  
SS = S -10 = 12 - 10 = 2   
then 4 V :   
SS = S + 4 =2 + 4 = 6  

Do đó, giá trị cuối cùng của đếm semaphore là 6.

Binary Semaphore

Binary Semaphore hoặc Mutex là hai loại Semaphore sử dụng trong hệ điều hành. Chúng ta sử dụng Binary Semaphore hoặc Mutex để giải quyết vấn đề tài nguyên của việc chia sẻ dữ liệu.

Binary Semaphore: Là một loại Semaphore đơn giản, chỉ có hai trạng thái là 1 hoặc 0. Binary Semaphore được sử dụng để đảm bảo rằng một tài nguyên chỉ được sử dụng bởi một tiến trình duy nhất tại một thời điểm.

Mutex: Là viết tắt của từ “Mutual Exclusion”, nó cũng là một loại Binary Semaphore. Mutex được sử dụng để đảm bảo rằng chỉ có một tiến trình được truy cập vào một tài nguyên cụ thể tại một thời điểm.

Ví dụ code Binary Semaphore

Dưới đây là một ví dụ code cho Binary Semaphore trong lập trình C:

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
 
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
 
void *thread1_func(void *arg)
{
    pthread_mutex_lock(&mutex);
    printf("Thread 1 đang sử dụng tài nguyên.\n");
    sleep(3);
    pthread_mutex_unlock(&mutex);
 
    return NULL;
}
 
void *thread2_func(void *arg)
{
    pthread_mutex_lock(&mutex);
    printf("Thread 2 đang sử dụng tài nguyên.\n");
    sleep(3);
    pthread_mutex_unlock(&mutex);
 
    return NULL;
}
 
int main()
{
    pthread_t thread1, thread2;
 
    pthread_create(&thread1, NULL, thread1_func, NULL);
    pthread_create(&thread2, NULL, thread2_func, NULL);
 
    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);
 
    return 0;
}

Trong ví dụ trên, chúng ta sử dụng Binary Semaphore (sử dụng pthread_mutex_t) để đảm bảo rằng tài nguyên chỉ được sử dụng bởi một thread trong một thời điểm duy nhất. Khi một thread đang sử dụng tài nguyên, các thread khác sẽ phải chờ cho đến khi tài nguyên được giải phóng.

Các câu hỏi phổ biến về thuật toán semaphore

1. Semaphore là gì?

• Semaphore là một cấu trúc dữ liệu được sử dụng để đồng bộ hóa truy cập vào tài nguyên chia sẻ giữa các tiến trình hoặc luồng trong hệ thống.

2. Semaphore có bao nhiêu loại?

• Semaphore có hai loại chính là binary semaphore và counting semaphore. Binary semaphore chỉ có thể giữ giá trị 0 hoặc 1, trong khi counting semaphore có thể giữ bất kỳ giá trị nguyên dương nào.

3. Semaphore được sử dụng để làm gì?

• Semaphore được sử dụng để đảm bảo tính đúng đắn và hiệu quả của các thuật toán đồng bộ hóa truy cập vào tài nguyên chia sẻ giữa các tiến trình hoặc luồng trong hệ thống.

4. Semaphore làm việc như thế nào?

• Semaphore được khởi tạo với một giá trị ban đầu và có thể được tăng hoặc giảm bởi các tiến trình hoặc luồng. Khi một tiến trình muốn truy cập vào tài nguyên chia sẻ, nó phải yêu cầu giảm giá trị của semaphore. Nếu giá trị semaphore là 0, tiến trình sẽ bị chặn và phải chờ đợi cho đến khi semaphore có giá trị khác 0. Khi tiến trình hoàn tất công việc của mình, nó sẽ tăng giá trị của semaphore để cho phép các tiến trình khác tiếp cận tài nguyên chia sẻ.

5. Semaphore có ưu điểm gì?

• Semaphore có thể giúp đảm bảo tính đúng đắn và hiệu quả của các thuật toán đồng bộ hóa truy cập vào tài nguyên chia sẻ giữa các tiến trình hoặc luồng trong hệ thống. Semaphore cũng giúp tránh tình trạng deadlock trong quá trình sử dụng tài nguyên chia sẻ.

6. Semaphore có nhược điểm gì?

• Semaphore có thể dẫn đến tình trạng gián đoạn (starvation) nếu một tiến trình hoặc luồng luôn được ưu tiên truy cập vào tài nguyên chia sẻ.

7. Semaphore và mutex khác nhau như thế nào?

• Semaphore và mutex đều được sử dụng để đồng bộ hóa truy cập vào tài nguyên chia sẻ giữa các tiến trình hoặc luồng trong hệ thống. Tuy nhiên, semaphore là một cấu trúc dữ liệu bao gồm một giá trị và một hàng đợi, trong khi mutex chỉ là một cấu trúc dữ liệu đơn giản chỉ gồm một bit hoặc một flag. Semaphore cho phép nhiều tiến trình hoặc luồng truy cập vào tài nguyên chia sẻ cùng lúc, trong khi mutex chỉ cho phép một tiến trình hoặc luồng truy cập vào tài nguyên chia sẻ tại một thời điểm. Semaphore cũng được sử dụng để giải quyết các bài toán đồng bộ hóa phức tạp hơn mutex.

8. Khi nào thì cần sử dụng semaphore?

• Semaphore được sử dụng khi có nhiều tiến trình hoặc luồng cần truy cập vào tài nguyên chia sẻ, ví dụ như các bài toán về đồng bộ hóa truy cập vào file, database, hoặc các tài nguyên khác trong hệ thống. Semaphore cũng được sử dụng để giải quyết các bài toán về điều khiển luồng (flow control) trong các ứng dụng đa luồng.

9. Semaphore có được hỗ trợ trong các ngôn ngữ lập trình khác nhau không?

• Semaphore là một cấu trúc dữ liệu rất phổ biến trong lập trình đa tiến trình hoặc đa luồng, và được hỗ trợ trong hầu hết các ngôn ngữ lập trình như C, C++, Java, Python, Ruby, JavaScript, và nhiều ngôn ngữ khác.

10. Semaphore và deadlock có liên quan gì đến nhau?

• Semaphore được sử dụng để tránh tình trạng deadlock trong quá trình sử dụng tài nguyên chia sẻ giữa các tiến trình hoặc luồng trong hệ thống. Tình trạng deadlock xảy ra khi một tài nguyên chia sẻ bị nhiều tiến trình hoặc luồng cùng yêu cầu truy cập, và các tiến trình hoặc luồng này lại chặn lẫn nhau, dẫn đến việc tất cả các tiến trình hoặc luồng đều bị treo và không thể tiếp tục thực hiện công việc của mình. Semaphore được sử dụng để giải quyết vấn đề này bằng cách đồng bộ hóa truy cập vào tài nguyên chia sẻ giữa các tiến trình hoặc luồng, giúp tránh tình trạng deadlock.