# :writing_hand: ==LECTURE OPERATING SYSTEM (CONT.)== ## :pushpin: Chapter :five: : Thread (PART A) :::info :question: Chúng ta cần tìm hiểu **Thread là gì** và các **cấu trúc thực thi** của nó trong hệ điều hành của máy tính ra sao ? ::: ### I. Thread Concepts #### 1. What is a Thread (tiểu trình / luồng) ? :::success * **Một tiến trình** có thể tạo **nhiều tiểu trình**, mỗi tiểu trình thực hiện **một chức năng** nào đó và **thực thi đồng thời** cũng bằng cách **chia sẻ CPU**. * Các **tiểu trình** trong **cùng một tiến trình** dùng **chung không gian địa chỉ** tiến trình nhưng có **con trỏ lệnh**, **tập các thanh ghi** và **stack riêng**. * Một **tiểu trình** cũng có thể **tạo lập các tiến trình con**, và **nhận các trạng thái khác nhau** như một tiến trình. ::: * **++Thread:++** an execution line (luồng thực thi) within a process (i.e, a lightweight process: khi chúng ta có nhu cầu thực thi các phần khác nhau của tiến trình một cách song song độc lập $\to$ tăng khả năng tính toán và giảm thời gian thực thi) * A process is divided into different parts (threads) (một tiến trình lớn chia thành nhiều luồng tiểu trình nhỏ, mỗi luồng nhỏ thực thi một đoạn code riêng của tiểu trình đó nhằm đảm nhận một công việc tính toán nào đó cho tiến trình, chạy độc lập và có thể chạy song song với các luồng tiểu trình khác nếu trên một hệ thống multiprocessors / multicores). * Threads belonging to a process can execute concurrently (độc lập hay song song đồng thời). * **++Liên lạc giữa các tiểu trình++** * Các tiến trình chỉ có thể liên lạc với nhau thông qua các cơ chế (IPC: shared memory, socket, ...) do hệ điều hành cung cấp $\to$ nặng hơn tiểu trình. * Các tiểu trình liên lạc với nhau dễ dàng thông qua các biến toàn cục của tiến trình. Các tiểu trình có thể do hệ điều hành quản lý hoặc hệ điều hành và tiến trình cùng phối hợp quản lý. * Có hai mô hình chính: * ==Single - threaded process== * Một tiến trình chỉ có một tiểu trình thực thi và cần nạp vào tiến trình đó các thông tin sau: * code : execuable code (đoạn mã thực thi nhị phân) * static & global data: dữ liệu tĩnh và động * files: resources files * stack: lưu các lời gọi hàm hay các tham số trong lời gọi hàm * local data: biến cục bộ * register: các tập thanh ghi (giúp cho quá trình tính toán trong CPU nhanh hơn) <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434319734_328950613095225_8612736238157899091_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=tGP0UX2s7OQAX-dIv1N&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdSzIr3_MarTKCl1FBfVIEBcI_ErYGwQrtpNvDNb7Tf9gQ&oe=662B1A49><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434336539_3633215346896081_166604247637105455_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=aVk-KmCAvaIAX_XG8j0&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdSZzeaXhCpcS9tYebXAlyhevSqxeJ3cEbwvBmiu3HrBMA&oe=662CE0BE></center> * ++Ví dụ:++ Ba tiến trình thực thi đồng thời, mỗi tiến chình chỉ có một tiểu trình. * ==Multi - threaded process== * Một process được chia thành nhiều thread thực thi khác nhau mà mỗi thread sẽ đảm nhận một công việc riêng biệt cho process đó nhằm tăng khả năng chia sẻ tài nguyên (biến dùng chung), gia tăng tốc độ tính toán, tốc độ phối hợp xử lý tác vụ và giảm đi thời gian xử lý vấn đề. <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/431531204_407076965268854_4001756230671015624_n.png?_nc_cat=102&ccb=1-7&_nc_sid=5f2048&_nc_ohc=HU7KeaBobZkAX_41vzA&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdRz5S_7Tft67k38mMtHoPR2ibUXFHwE2YoU4naVqwIo6w&oe=662B1448></center> * ++Ví dụ:++ Process chia thành 3 threads sỡ hữu chung những tài nguyên của process cha (code, data files) nhưng do mỗi thread có một đoạn thực thi độc lập với các đoạn khác trong một tiến trình nên những vùng gắn liền với việc thực thi cục bộ $\to$ mỗi thread sở hữu riêng stack, register, program counter, pointer, ... Việc hoạt động đồng thời của các tiểu trình là do tiến trình quản lý. | Trong cùng một tiến trình | Trong mỗi tiểu trình | |:-------------------------------------:|:--------------------:| | Không gian địa chỉ | Bộ đếm chương trình | | Các biến toàn cục | Các thanh ghi | | Các tập tin mở | Ngăn xếp | | Các tiến trình con | Trạng thái | | Các cảnh báo | | | Các tín hiệu và các bộ xử lý tín hiệu | | | Thông tin tài khoản | | #### 2. Purpose * Process perform various tasks *(threads of execution)* simultaneously $\to$ simplify tasks. * Especially efficient on multiprocessor (nhiều CPUs) or multicore (1 CPU nhiều cores) systems. <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434351007_388063064147200_937549212372552914_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=AQwW3rqDoaMAX8iSG8u&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdQOPahMGojrK_a4dX9X5bl1Jj5iegALP7TPt7tjQDF6CA&oe=662B4F8B></center> #### 3. Benefits * Responsiveness - `Tính phản hồi nhanh` * If a thread of a process is blocked or time-consuming, other parts of the process still can continue their jobs (các tiểu trình khác không bị ảnh hưởng khi các tiểu trình bị blocked hay time-consuming còn tiến trình thì bị ảnh hưởng nếu một tiến trình khác bị blocked). * Resources sharing - `Chia sẻ tài nguyên` * Threads belonging to the same process share the same address space * Economy - `Giảm chi phí` * Less cost of thread creation and management (khi tạo một thread không cần phải tạo lại tài nguyên dùng chung có sẵn trong một tiến trình). * Scalability - `Khả năng mở rộng` * Threads can be executed on different cores/processors (có thể thực thi song song trên nhiều processors) ### II. Thread Models #### 1. Thread - level Implementation <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432420013_961175015637546_5292423822225837005_n.png?_nc_cat=101&ccb=1-7&_nc_sid=5f2048&_nc_ohc=UKD2khH8fuMAX-kZYI8&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdSeszu8RPwOcOQqb9wd65R9IwgPXVER8Ln2BgWeliqJBg&oe=662B3A1D></center> #### 2. User - level Threads * Implemented by user thread libraries (i.e., APIs supported by programming languages) in user space with no kernel support. * Advantages: * Be efficient * Thread management, context switching, and synchronization done without any OS intervention * Do not need system support * Disadvantages: * The kernel knows nothing about user threads * Entire process will be blocked if one of its threads is blocked (có sự cố xảy ra thì kernel không biết) * Timesharing system: giving the same amount of time to each process for execution $\implies$ Fairness when P1 having $10$ threads and P2 having $1000$ threads? (nếu của hai tiến trình có cùng một quantum time để thực thi mà số lượng threads của mỗi tiến trình khác nhau thì sẽ gây ra sự không công bằng.) #### 3. Kernel - level Threads * Supported directly by OS and implemented in kernel space. * Advantages: * OS manages thread * When a thread of a process is blocked, other parts of the process can continue to execute independently. * Disadvantages: * Slower and less efficient (vì mỗi hành động của tiểu trình đểu có sự can thiệp hoạt động của hệ điều hành $\to$ tốc độ thực thi nhiều hơn và thao tác nặng hơn vì không được đơn giản hóa) * Thread management, context switching, and synchronization require OS intervention. #### 4. Kernel - level and User - level Thread Mapping * Many - to - one model: mô hình ở Kernel - Space chỉ có một kernel thread, còn ở User - Space các lập trình viên sẽ dùng các thư việc Thread libraries để chia nhỏ tiến trình thành nhiều tiểu trình con. * Disadvantage: Nếu kernel thread bị block thì tất cả user thread không được xử lý bởi kernel. * Many - to - many model: mô hình có $n > 0$ user thread ở user - space được mapping với $1 < m < n$ kernel thread ở kernel space. * Disadvantage: Nếu một user thread trong user space bị block thì ảnh hưởng đến $m$ kernel thread còn lại. * One - to - one model: mỗi một user thread sẽ tương ứng với một kernel thread. * Disadvantage: Nếu user thread quá nhiều dẫn tới kernel thread cũng quá nhiều thì kernel space sẽ bị quá tải. * Two - level model: cấu trúc hybrid giữa one - to - one và many - to - many model. <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432341953_2420917218104508_7489933110682497910_n.png?_nc_cat=105&ccb=1-7&_nc_sid=5f2048&_nc_ohc=5nPtYwlAMIkAX-pAOc6&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdTethL85W2xZaxD1On9OG-BZ7kxEgj3qRDwwOkctbH2tA&oe=662B6096></center> ### III. Thread Management #### 1. User - level vs. Kernel - level Management * **Cài đặt trong Kernel - Space:** bảng quản lý Thread lưu trữ ở phần Kernel và việc điều phối các thread là do hệ điều hành chịu trách nhiệm. * **Cài đặt trong User - Space:** bảng quản lý Thread lưu trữ ở phần User - Space và việc điều phối các thread là do tiến trình chịu trách nhiệm. * **Cài đặt trong Kernel - Space và User - Space:** Một số Thread mức User được cài đặt bằng một Thread mức Kernel. <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432465771_430862756149103_5906233925320350561_n.png?_nc_cat=105&ccb=1-7&_nc_sid=5f2048&_nc_ohc=lKDf4uMImPUAX8fVxqg&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdSA4-utajpziRTDsobOamQK8U4_XCOfAV1PachLDgxOSA&oe=662B65F4><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434394239_954753959582824_7137173604496815328_n.png?_nc_cat=105&ccb=1-7&_nc_sid=5f2048&_nc_ohc=PIw2LXSQG-cAX8YIwpV&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdTjx8NdEekR0AkVA4t4PBvcP_To-sinVTxB4xY1f0UUlw&oe=662D679A><p> <b>Kernel - User - level Thread Management</b> </p></center> #### 2. Thread Scheduling * Ví dụ: giả sử quantum của process = $50$ ms, quantum của thread = $5$ ms và giả sử tiến trình $A$ có $3$ thread, tiến trình $B$ có $4$ thread. * Nếu việc điều phối thread được thực hiện mức user - space thì thứ tự điều phối có thể là $A_1, A_2, A_3, A_1, A_2, A_3$ nhưng không thể là $A_1, B_1, A_2, B_2, A_3, B_3$, vì khi tiến trình $A$ được cho thực thi với quantum = $50$ ms và mỗi thread được thực thi với quantum = $5$ ms thì không thể $A_1$ đến $B_1$ được do thread của tiến trình nào tiến trình đó quản lý và tiến trình $A$ chưa hết quantum nên thread của tiến trình $B$ không thể thực hiện. * Nếu điều phối thread được thực hiện ở mức kernel - space thì thứ tự điều phối $A_1$ đến $B_1$ là có thể vì các thread do hệ điều hành quản lý. <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432791434_2147907005589065_9222941476469278299_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=ryQAGw8y8UYAX-Tqv9w&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdRym7y-2hwJrdvAcoXxnvoPE-IfsfPIUVvS2wwSnuFZsA&oe=662B699C></center> #### 3. Thread Libraries * Provide **APIs** for thread creation and management * ++POSIX thread (Pthread):++ support both user and kernel thread libraries * ++Windows thread:++ support kernel threads managed directly by Windows * ++Java thread:++ support Java thread programming <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434315421_1959898294425003_7549975856881983915_n.png?_nc_cat=108&ccb=1-7&_nc_sid=5f2048&_nc_ohc=HiFvuHhLks0AX8eIg4l&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdTZXlr5CCmuxvJGAmioaSiJ3iW2aOGZs4uL50xMe10SOw&oe=662B42BD></center> --- ## :pushpin: Chapter :five: : Synchronization (PART B) ### I. Critical Section Problem #### 1. Race conditions - `Tình huống tương tranh` :::info **What if several processes/threads access a shared variable concurrently?** ::: * Disadvantages: Data inconsistencies and errors <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434257485_384362714399815_1732226002123735533_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=X4JX06uHQSAAX-lWMnX&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdS2NqYNVmjdoax1WQQJjDWWQgKfQfHT64fVPx6IEsV-uQ&oe=662B5ED2></center> :::success **Race condition** là một tình huống xảy ra khi nhiều threads cùng truy cập và cùng lúc muốn thay đổi dữ liệu (có thể là một biến, một row trong database, một vùng shared data, memory , etc...). Vì thuật toán chuyển đổi việc thực thi giữa các threads có thể xảy ra bất cứ lúc nào, nên không thể biết được thứ tự của các threads truy cập và thay đổi dữ liệu đó sẽ dẫn đến giá trị của data sẽ không như mong muốn. Kết quả sẽ phụ thuộc vào thuật toán thread scheduling của hệ điều hành ::: #### 2. Critical Section Problem - `Vấn đề tương tranh / tranh chấp` :::success Miền găng (critical section): đoạn mã của một tiến trình có khả năng xảy ra lỗi khi truy xuất tài nguyên dùng chung (biến, tập tin, ...) ::: <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434316468_1670699933748744_5976949349084036009_n.png?_nc_cat=108&ccb=1-7&_nc_sid=5f2048&_nc_ohc=yKgENkgyKQ8AX-CVCrQ&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdQ9JwN_VYCo9FuateLiaVBtlNT6m8MHCZjI9dpLWxibvg&oe=662B73B4></center> * Examples: availTicket $\implies$ Solution: synchronization (đồng bộ hóa) ### II. Synchronization #### 1. Synchronization Requirements :::success **Đồng bộ (Synchronization)** là các tiến trình là bảo đảm các tiến trình xử lý song song không tác động sai lệch đến nhau. Việc đồng bộ hóa là do các yêu cầu sau: ::: * Mutual Exclusion - `Yêu cầu độc quyền truy xuất` * Only one process/thread can be executing inside a critical section at a time :::spoiler **Giải thích** * Tại một thời điểm, chỉ có một tiến trình được quyền truy xuất một tài nguyên không thể chia sẻ. ::: * Synchronization - `Yêu cầu phối hợp` * Các tiến trình cần hợp tác với nhau để hoàn thành công việc. * ++Ví dụ:++ chương trình in xuất ký tự vào buffer, ký tự được lấy và in bởi chương trình điều khiển máy in (printer driver). Hai tiến trình này phải phối hợp với nhau như là chương trình in không được xuất ký tự vào buffer khi buffer đầy mà phải chờ printer driver lây bớt dữ liệu. Từ hai yêu cầu trên, ta có hai "bài toán đồng bộ" cần giải quyết đó là bài toán "độc quyền truy xuất" (hay còn gọi là "bài toán miền găng") và bài toán "phối hợp thực hiện". Khi giải quyết bài toán miền găng cần chú ý 4 điều kiện sau: * Không có hai tiến trình cùng ở trong miền găng cùng lúc. * Không có giả thiết về tốc độ của các tiến trình, cũng như số lượng bộ xử lý. * Progress - `tiến trình ngoài miền găng không được khóa tiến trình muốn vào miền găng` * A process/thread outside a critical section cannot block others to enter this critical section * Bounded Waiting - `không có tiến trình nào phải đợi vô hạn` * Processes/Threads should not wait indefinitely for entering a critical section #### 2. Synchronization Solutions <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434266212_1476538829906186_9031209582727443150_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=yFBxhz_0XqQAX-PF66N&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdSBYJNsbb1bHIHz93Ya60bA2A_xUiUkGgP6UjvjqAeVYA&oe=662B9214></center> ##### 2.1. Busy Waiting Solutions ###### a. Lock variable <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432450663_757281346137435_1019289515648428456_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=d_PA_GrQGmUAX_PijfT&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdRL9OId_zl2dW7Yp3h2cKZiF79QqW_A-kja-A0tmRcmYQ&oe=662B7F51></center> * Disadvantage: Two processes / threads may be inside CS (Critical Section) at a time. ###### b. Strict Alternation <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432460201_222955710905633_7960850911658030849_n.png?_nc_cat=104&ccb=1-7&_nc_sid=5f2048&_nc_ohc=SHAFLILoS-cAX9dH1Ga&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdTlmNARLtjZn60Pi3kNomNBFrFOW0-6pXzvMolPp4Oi0g&oe=662BA996></center> * Disadvantage: A process/thread outside CS (Critical Section) may prevent another thread from entering CS (Critical Section) ###### c. Peterson's Solution ```cpp= Process_A() { while(1){ enterCS(0); critical_section; leaveCS(0); } } Process_B() { while(1){ enterCS(1); critical_section; leaveCS(1); } } ``` * Disadvantage: * CPU wasting * Priority Inversion <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432777878_1737596907053256_7562634751888289645_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=cZzihT7hAVQAX8p3qy7&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdQvP2AmnZtzxNkm1rxUjN7GOG8x-xwlbsPAFmibpvTMWw&oe=662BA082><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432791584_914785420141141_2959158197570816485_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=13Soflwsjl0AX9Pg5mV&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdR2WT4bUThdwWNScWvAviW1MQzpEuQB8FenmhYOK9NM4A&oe=662B83A7></center> ###### d. Interrupt Disabling - `Hardware support` * Interrupts: signals emitted by a hardware or a software * Timer Interrupts: handle CPU Scheduling * I/O device Interrupts: inform I/O completion * $\dots$ $\implies$ Perform a context switch. * Interrupt-based solution for critical section problem <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434285098_1322782248417472_7634024584999429686_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=u8N-0A8uco8AX92ENiV&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdTlU0isQcI9YRKXXg9E1DUQz60fkAcmdt1k_VronK75rw&oe=662B9779></center> * Disadvantage: * What if a process/thread is blocked inside CS or time-consuming? * What if systems have multiple processors? ###### e. TSL (Test - And - Set) - `Hardware support` <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432465159_947926673169443_5421344369522819550_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=h2pYk6LYjL4AX92T6G4&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdQAT-G-xCnE6C0soIEwdWQmRONzJF4q-cLKbB8HWzC7-w&oe=662B94E0></center> ##### 2.2. Sleep and Wakeup Solutions ###### a. Semaphore * **Integer variable** used to restrict access to a CS via two atomic operations: **down** and **up** * **Down** (also termed **P** or **wait**) called before entering a CS to verify if the calling thread has permission to enter the CS * Up (also termed **V** or **signal**) called when exiting CS to release this CS and wake up another sleeping thread (if there is any) * Two types of semaphores * Binary semaphore * Alike to lock solution (also termed mutex lock). * Value ranging from 0 to 1 * Counting semaphore * Used to control access to a resource having a finite number of instances * Initialized to the number of resources available <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434512401_405512075420827_4846364486364364315_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=Rwe_n3I5TnsAX9FEuxx&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdSY5o2IhYiI7XbzeJy8-2_C2d6BIhFrPNcbQAO0qWIbLg&oe=662BA7C9><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432820221_292204787106846_4496863728418519507_n.png?_nc_cat=109&ccb=1-7&_nc_sid=5f2048&_nc_ohc=5uGDg5H7330AX-JhdzP&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdRVBqB1ocGNObFvtkrN3LcJJpKIHYd5pHVe1MqSL44etQ&oe=662BC795></center> ###### b. Monitor * A programming construct for controlling access to shared data, which encapsulates: * **Shared variables** * **Condition variables**, along with 2 operations (**wait** and **signal**) for synchronization. * **Procedures** operating on shared variables * Also termed “thread-safe” class * Only procedures *(operations)* inside a monitor can access its variables * Processes/Threads access shared variables by invoking procedures * Only one process/thread may be executing in the monitor at a time <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434294829_881721603715872_3749150135678131194_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=pPY_QHOlCG4AX9t5uKT&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdSSqdJaSuP4x2dOqB-JVf1szgyzeCKm_TC0q3_VDgRVPw&oe=662B946D></center> ##### 2.3. And other ... ###### a. Message - based solution ###### b. Barrier ### III. Classic synchronization problems #### 1. Producer - Consumer Problem * Also known as bounded-buffer problem * Producer and consumer share a fixed size buffer * Producer produces an item and places it in the shared buffer * Consumer picks an item from the shared buffer and consume it * Regulations * Buffer is FULL $\to$ producer will be blocked * Buffer is EMPTY $\to$ consumer will be blocked * Only one producer or consumer may access the shared buffer at a time <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434306842_958636735989842_6041803621605100297_n.png?_nc_cat=104&ccb=1-7&_nc_sid=5f2048&_nc_ohc=0TGowRo5nvUAX9sXZyH&_nc_oc=AdgNc5OGslRCvBzl9Z859YN19Rh9vaV_3IapaxRAhUrA_xEoWlFi8HKktik6YGpxPIpS7e8SoMLrx0rqyOEo72To&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdQmuLx3BKRQiNqvC0_ev6zArHVNETfrEXp7pWlDeAZhNg&oe=662BB5DB><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434307968_1510501509512679_4112384766687862663_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=zebQxVrRDKAAX9de2qd&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdSLX17cPQmHblftLc8rODKpJb-QcQVxXFbyiQTr8uXDZw&oe=662B951E></center> #### 2. Readers - Writers Issues ##### a. Problems * Classic database problem: readers and writers share a database * Regulations * Several readers can read from database at the same time * If a writer is writing to database, other threads cannot access database * If there are any readers in database, a writer cannot access database <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432469153_1135864807590908_2129553105480153718_n.png?_nc_cat=100&ccb=1-7&_nc_sid=5f2048&_nc_ohc=gqRyXDTzYXMAX80IKAr&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdT3Q1j2Xykwm3_RMMO680akAKb9OCEohAbBfWK3X_I9sg&oe=662B9BF6></center> ##### b. Solutions <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432896053_6822405324530643_7262170548834866566_n.png?_nc_cat=108&ccb=1-7&_nc_sid=5f2048&_nc_ohc=2ad08Fsh3x0AX9Tdjgc&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdTcsz6Muyqp_NnX5dlkvYGUCWvSkBM4FpD_JwO7sBGOUw&oe=662BC243><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432476495_893683762496415_7691840218027336634_n.png?_nc_cat=100&ccb=1-7&_nc_sid=5f2048&_nc_ohc=mlDGza-PEeYAX8W264_&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdRxnG2On357nrS1jKrwnSoGrZ7nFr5OR5bCdgaBAs4j_Q&oe=662B99EF></center> #### 3. Dining Philosophers Issues ##### a. Problems * Five philosophers are seated around a circular table, which is laid with five forks * Each philosopher must take two nearest forks for eating, but: * He can only pick up one fork at a time * He cannot pick up the fork which has been taken by his neighbors <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432484015_1896391837430601_3037473001243710519_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=bagsERQqPdsAX-L8olN&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdR3ZdTxcKC845XD30AoMoC43Mlx4WbHVtUK6DdVgh6ldA&oe=662B939C></center> ##### b. Solutions :::info **What if all five philosophers take left fork at once?** ::: <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434315426_1440040806897960_4330182420831032803_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=K-aB2h3J_6sAX84hQza&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdTx_VmJjlKWMHuO8YWTxn3kjEa1bqPAIQwKHdYv5fTaFA&oe=662BA4E5></center> * Disadvantage: Deadlock <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432342055_3812807145621460_1691672940940134574_n.png?_nc_cat=101&ccb=1-7&_nc_sid=5f2048&_nc_ohc=qrNp6BG7uU8AX_D5dzc&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdSzRzvWEAudweexj4ruVJawWUJiPj3Fl0J7a_yyNnf-uQ&oe=662BB92D></center> --- ## :pushpin: Chapter :six: : Deadlock ### I. Introduction to Deadlock #### 1. Recall: Dining-Philosophers Problem * Vấn đề đặt ra: Bữa ăn tối của các triết gia. Có 5 nhà triết gia cùng ngồi ăn tối. Mỗi nhà triết gia cần dùng 2 cái nĩa để có thể ăn. Nhưng trên bàn chỉ có tổng cộng 5 cái nĩa, nếu cả 5 người đều cầm cái nĩa bên trái cùng lúc, thì sẽ không có ai có được cái nĩa bên phải để có thể bắt đầu ăn. Tình trạng này gọi là tình trạng tắc nghẽn. <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434478465_1790081211511447_7808332554794663310_n.png?_nc_cat=102&ccb=1-7&_nc_sid=5f2048&_nc_ohc=Ymh8aGkl8sUAb6wUbih&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEYVniVLkaplA0icGzU9Z5pkinx07ybjrakMGfEHUD87w&oe=66490FB3><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434850319_783946963689586_8747864367616912353_n.png?_nc_cat=105&ccb=1-7&_nc_sid=5f2048&_nc_ohc=vQK4WnsAsQIAb6SVxrx&_nc_oc=AdjTh67RkkGRS_4MTnHr4Q4HQmj5bLom_lB4K8v8UR_Ci7UXlH59Xk9tmKm_MYfI-x5DnOqJ0y30pgX4cAvu98vL&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGnVEWCpHQnGVr17zWGOiR8T0aSFcDG7AWZAYXq474CRA&oe=664AE29D></center> #### 2. Resource-Allocation Graph (RAG) * RAG: là đồ thị cấp phát tài nguyên, cho biết tình trạng của các tiến trình đang sở hữu những tài nguyên gì, đang đòi hỏi những tài nguyên gì $\to$ cho thấy được mô hình về kịch bản cấp phát tài nguyên cho các tiến trình dưới dạng đồ thị để nhìn rõ hơn tình huống đang xảy ra trong hệ thống. Trong một vài trường hợp thì đồ thị này có thể được sử dụng để phát hiện ra deadlock. * Hình tròn là tiến trình, hình vuông là tài nguyên. Đối với tiến trình, mũi tên đi ra là chiếm giữ tài nguyên, mũi tên vào là yêu cầu tài nguyên. * Ví dụ tiến trình A đang giữ tài nguyên R, tiến trình B yêu cầu tài nguyên S. Tiến trình C giữ U, yêu cầu T, tiến trình D giữ T, yêu cầu U. Tập hợp tiến trình {C,D} gọi là ở tình trạng tắc nghẽn <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434850313_2538383223011354_1522064911896838610_n.png?_nc_cat=108&ccb=1-7&_nc_sid=5f2048&_nc_ohc=l1aaZ1HNcbAAb77__pL&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHqCtCJ01bPQ8fzLBiiS84aADbMRdTPTULXHo7fCS3R-w&oe=664ADA7D></center> * Tài nguyên có thể là tài nguyên vật lý (máy in, bộ nhớ, cpu, đĩa, ...) hoặc tài nguyên logic (file, semaphore, monitor,...). Tài nguyên lại phân thành hai loại: loại tài nguyên có thể lấy lại từ một tiến trình đang chiếm giữ mà không ảnh hưởng đến tiến trình đang chiếm giữ và loại tài nguyên không thể thu hồi lại từ tiến trình đang chiếm giữ. * Deadlock <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434905993_777104151063249_7451246260248319032_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=b-ddhzuEcwkAb5tzCqz&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QF-xX25V8qGUZwkkfsecorcFoWyUzGAzCwYFEQbhcgtMg&oe=664ABC69></center> * No deadlock <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434785516_981795526670806_5283254841420513470_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=-5_qlzkRiH8Ab5IR73Z&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFR4T2_OPWY8EDG9G5kMx6mNMo-s7HsTgkdKdIUzpVOfQ&oe=664AC255></center> * Graph with no cycle $\to$ no deadlock * Graph with a cycle and resources having only one instance $\to$ deadlock * Graph with a cycle and resources having various instances $\to$ deadlock possibility <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434848401_983803550061431_7865186650867566230_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=S8HfQ3KgSgsAb4MDOXJ&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFWWX50LQLQVNwMB7y4f19ffzR4O-QXdb1210iUHXtk4A&oe=664AB4FA><p> <b>No Deadlock</b> </p></center> #### 3. Deadlock Definition * A set of processes is in a **deadlock** situation when each of them is waiting for resources allocated to other waiting processes in the set, therefore none of them can get all necessary resources to continue executing. :::spoiler **Giải thích** * Một tập hợp các tiên trình gọi là ở tình trạng tắc nghẽn nêu môi tiên trình trong tập hợp đêu chờ đợi tài nguyên mà tiến trình khác trong tập hợp đang chiếm giữ. * Ví dụ tại một thời diểm, tiến trình 1 đang giữ tài nguyên R1, yêu cầu R2 và tiến trình 2 đang giữ tài nguyên R2, yêu cầu R1, như vây yêu cầu về tài nguyên không thể đáp ứng cho cả hai tiến trình. Khi đó không có tiến trình nào có thể tiếp tục xử lý, cũng như giải phóng tài nguyên cho tiến trình khác sử dụng, tất cả các tiến trình trong tập hợp đều bị khóa vĩnh viễn! ::: #### 4. Conditions for Deadlock * **All four following conditions must ++take place++ to cause deadlock** * **Mutual Exclusion - `độc quyền truy xuất`**: có sử dụng tài nguyên không thể chia sẻ * Only one process can hold the resource at a time (Mỗi thời điểm, một tài nguyên không thể chia sẻ được hệ thống cấp phát chỉ cho một tiến trình, khi tiến trình sử dụng xong tài nguyên này, hệ thống mới thu hồi và cấp phát tài nguyên cho tiến trình khác.) * Ví dụ: máy in không thể cùng thực thi 2 tiến trình in cùng lúc hay luân phiên lẫn nhau. * **Hold and Wait - `chiếm giữ và chờ đợi`**: sự chiếm giữ và yêu cầu thêm tài nguyên không thể chia sẻ * Process holds some resources while waiting for others, which are held by other waiting processes (Có tiến trình chiếm giữ các tài nguyên trong khi lại chờ đợi được cấp phát thêm tài nguyên bị chiếm giữ bởi tiến trình khác). * **No preemption - `không chiếm đoạt xảy ra (độc quyền)`**: không thu hồi tài nguyên từ tiến trình đang giữ chúng * A resource can be released only by the process holding it (Tài nguyên không thể được thu hồi từ tiến trình đang chiếm giữ chúng trước khi tiến trình này sử dụng chúng xong.) * **Circular Wait - `vòng đợi`**: tồn tại một chu trình trong đồ thị cấp phát tài nguyên. * There is a wait-cycle between at least two processes (Có ít nhất hai tiến trình chờ đợi lẫn nhau: tiến trình này chờ được cấp phát đang bị chiếm giữ và ngược lại) ### II. Deadlock Handling #### 1. Deadlock Ignorance - `bỏ qua tắc nghẽn` * **Ostrich Algorithm: pretend that deadlocks do not cause any problem** * Deadlocks occur rarely * Deadlock handling is much more costly * Bỏ qua việc xử lý tắc nghẽn, xem như hệ thống không bao giờ xảy ra tắc nghẽn. Thường được áp dụng phương pháp này khi hệ thống rất ít khi bị tắc nghẽn và chi phí kiểm tra tắc nghẽn cao (UNIX và WINDOWS sử dụng phương pháp này). #### 2. Deadlock Prevention - `đề phòng tắc nghẽn` * **Eliminate the occurrence of one of the four conditions causing deadlocks** (để không xảy ra tắc nghẽn, cần bảo đảm tối thiểu một trong 4 điều kiện không xảy ra) * Mutual Exclusion * Cons :disappointed: : Not practical $\to$ điều kiện này gần như không thể tránh được vì bản chất tài nguyên gần như cố định. * Hold and Wait * Process must require all necessary resources when starting executing (Tiến trình phải yêu cầu tất cả các tài nguyên cần thiết trước khi cho bắt đầu xử lý.) * Phương pháp này gặp khó khăn là hệ điều hành ==khó có thể biết trước được các tài nguyên tiến trình cần phải sử dụng== vì nhu cầu tài nguyên còn phụ thuộc vào quá trình tiến trình thực hiện. * Ngoài ra nếu cho tiến trình ==chiếm giữ sẵn tài nguyên chưa cần sử dụng== ngay $\to$ việc sử dụng tài nguyên kém hiệu quả $\to$ low resource utilization $\to$ nếu tiến trình đó ==chiếm dụng hết tất cả tài nguyên== thì các tiến trình còn lại không được sử dụng $\to$ starvation possibility * Or release currently holding resources before requesting others (khi tiến trình yêu cầu một tài nguyên mới và bị từ chối, nó phải giải phóng các tài nguyên đang chiếm giữ, sau đó được cấp phát trở lại cùng lần với tài nguyên mới) * Phương pháp này sẽ gặp ==khó khăn trong việc bảo vệ tính toàn vẹn dữ liệu== của hệ thống. * Nếu tiến trình cứ giải phóng liên tục tài nguyên cũ để nạp tài nguyên mới vào $\to$ tăng số lần chuyển đổi ngữ cảnh giữa các tài nguyên $\to$ tiêu tốn thời gian thực thi việc chuyển đổi ngữ cảnh $\to$ giảm hiệu suất xử lý tài nguyên. * Cons :disappointed: * Difficult to know all necessary resources at the beginning * Low resource utilization * Starvation possibility * No preemption * OS may preempt resources from a process in some circumstance (thường sử dụng hệ thống theo lô): để điều kiện này không xảy ra, hệ điều hành cần cho phép hệ thống được thu hồi tài nguyên từ các tiến trình bị khóa và cấp phát trở lại cho tiến trình khi nó thoát khỏi tình trạng bị khóa. * Tuy nhiên, với một số loại tài nguyên, việc thu hồi sẽ rất khó khăn vì vi phạm sự toàn vẹn dữ liệu. * Cons :disappointed: : May cause errors for some resources (e.g., printer, files) * Circular Wait * Allocate different resource types according to a priority order * Gọi R = {R1, R2, ..., Rm} là tập các loại tài nguyên. Các loại tài nguyên được đánh số thứ tự. Ví dụ: F(đĩa) = 2, F(máy in) = 12. Khi tiến trình đang chiếm giữ tài nguyên Ri thì chỉ có thể yêu cầu các tài nguyên Rj nếu F(Rj) > F(Ri). #### 3. Deadlock Avoidance - `ngăn chặn, tránh né tắc nghẽn` **Test deadlock possibility before granting resources to avoid a future deadlock** * OS requires processes to provide additional information (e.g., maximum requirement) to decide on resource allocation * Whenever a process requests a resource, OS tests deadlock possibility by using deadlock avoidance algorithms * If a resource request may lead to a future deadlock, the resource can **NOT BE GRANTED**. * One instance of resource type: RAG * Multiple instances of resource type: Banker’s algorithm * Safe state: no deadlock (nếu hệ thống có thể thỏa mãn các nhu cầu tài nguyên tối đa của mỗi tiến trình theo một thứ tự cấp phát nào đó mà không bị tắc nghẽn thì gọi là hệ thống ở trạng thái an toàn) * System is safe if there exists a safe sequence for resource allocation * All resource requests will be granted without entering a deadlock situation * Unsafe state: may lead to deadlock (hệ thống ở trạng thái không an toàn có thể dẫn đến tắc nghẽn) * Deadlock avoidance: ensure that the system will be in a safe state after resource allocation <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434702986_919790729840385_3357160302217080833_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=PZTouZuP8vMAb64PfPG&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEny1sbqsxhzgSZSTixi7E8-Y6vR0crzzPDyG5Kvlph_A&oe=664AF391></center> * Banker’s algorithm * Also referred to as safety algorithm, developed by Edsger Dijkstra * Notions used in Banker’s algorithm * Available: available resources * Max: maximum resource requirements of each process * Allocation: resources allocated to each process * Need: remaining resources needed for each process * Need = Max – Allocation * Request: resource request chain of a process * For a request, test if the system will be in a safe state * Example of Banker's Algorithm <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434797160_194794310394710_3978454029078502676_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=vPneOzsX3toAb7up-3x&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEBtU7i6fJYQ5ZWGG5NsbjK93Xn6k5IpylraY4eR3h6ww&oe=664ACB20><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/437851701_1804765930017798_5663297156069338189_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=u3cGqMA8V5oAb7WhFAV&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QE8uQyNOaJHTz1OudWjJ3vZpED6E73GEf5_QwoGOPX5Ig&oe=664ACF8D></center> Request~P1~ = (1, 0, 2) will be granted safely? Request~P1~ < Need~P1~ < Available $\to$ Request~P1~ granted $\to$ Update Allocation~P1~, Need~P1~, Available <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434746569_384021134612051_7773939942489138133_n.png?_nc_cat=100&ccb=1-7&_nc_sid=5f2048&_nc_ohc=ft8pOnoMIRgAb4dyYYV&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGtabUybYBh2UAuJxZf8L5nFID2Zm_S6kzDbRVRhKUAkA&oe=664AD3F8></center> #### 4. Deadlock Detection and Recovery - `phát hiện và khôi phục tắc nghẽn` **Allow deadlock occurrence and then recover the system** * Deadlock Detection * One instance of resource type: *wait-for graph* (i.e., a variation of RAG) <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434434762_752796543653826_6273673830873616782_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=iAiNBIzy4bgAb6gJsaL&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QE5tpJhB3iUzSIw9i0WpWOpU1Z9itm8utrAQVnbhR83Gw&oe=664AE293><p> <b>Example of using a wait-for graph to detect deadlocks </b> </p></center> * Multiple instances of resource type: *matrix-based detection algorithm* (also referred to as a variation of Banker’s algorithm) * P1, P3 and P4 can finish and release holding resources * Cons :disappointed_relieved:: P0 and P2 could not finish $\to$ Deadlock detected <center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434852238_1063019718129666_8735833588681426457_n.png?_nc_cat=108&ccb=1-7&_nc_sid=5f2048&_nc_ohc=Y77UAPDBwaIAb6P_Xl2&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QG4taTSVYrUr132p9SBkiLDDTkTYE4B76X2UXmxNkUqnA&oe=664AE853><p> <b>Example of using matrix-based detection algorithm </b> </p></center> * Recovery * Terminate deadlocked processes * Rollback system to the previous safe checkpoint * Preempt resources