[ home ] [ math / cs / ai / phy / as / chem / bio / geo ] [ civ / aero / mech / ee / hdl / os / dev / web / app / sys / net / sec ] [ med / fin / psy / soc / his / lit / lin / phi / arch ] [ off / vg / jp / 2hu / tc / ts / adv / hr / meta / tex ] [ chat ] [ wiki ]

/os/ - Operating Systems

Name
Email
Subject
Comment
Verification
Instructions:
  • Press the Get Captcha button to get a new captcha
  • Find the correct answer and type the key in TYPE CAPTCHA HERE
  • Press the Publish button to make a post
  • Incorrect answer to the captcha will result in an immediate ban.
File
Password (For file deletion.)
25 Dec 2021Mathchan is launched into public
Catalog Archive

File: os_sticky_2.png ( 54.55 KB , 669x648 , 1709217350028.png )

Image
  No. 12
Reply
This board is for the discussion of operating systems.


File: Semaphore.png ( 16.56 KB , 368x207 , 1655551926593.png )

Image
  No. 1
Reply
What is threading?
Consider a function that contains an infinite loop: 
void* a(void* data)
{
    for ( ; ; ) {
        printf("a");
    }
    return NULL;
}

Calling the function 
a();
would cause the program to print "a" forever.

Now consider another function with an infinite loop: 
void* b(void* data) 
{
    for ( ; ; ) {
        printf("b");
    }
    return NULL;
}

Calling the function 
b();
, it would cause the program to print "b" forever.

What if we were to consecutively call 
a(); b();
? Well, since 
a()
contains an infinite loop, the call to 
b()
is never going to happen, so all we're going to get is "aaaaaaaaaaaaaaaa". Similarly, if we were to call 
b(); a();
all we're going to get is "bbbbbbbbbbbbbbbbb". Is there a way to make the program print a little bit of "a" and a little bit of "b" (i.e. "aaaabbbbbbbaaabbbb") without changing the code (i.e. with infinite loops)? This is what threads are about. By creating threads, we make it possible for multiple infinite loops to execute concurrently. Note that there is a slight difference between concurrency and parallelism. Parallel execution means two tasks are running completely simultaneously. Concurrent execution means two tasks are switching turns: task 1 is executing, then task 2, then task 1 again... If context switching is happening fast enough (the OS scheduler is the one deciding this), it would appear as if though they were running in parallel. Most synchronization techniques work the same for both so we'll make no distinction.


By default, every program is single-threaded and the only thread running is the one executing the 
main()
function. We can create more threads by calling 
pthread_create()
and passing the pointer to a callback function (
void* (*cb)(void*);
). If we create two threads - one for function 
a()
and one for function 
b()
- we will end upPost too long. Click here to view the full text.
3 posts and 3 image replies omitted. Click here to view.
>>
  No. 5

File: rounded-buffer.png ( 39.18 KB , 767x513 , 1655574754738.png )

Image
Producers and Consumers
Assume there are
NN
producer threads,
MM
consumer threads, and a shared rounded buffer of size
SS
(pic related). Producers always put data in the shared buffer, while consumers always take data from the shared buffer.

If producers are generate data too quickly, it could cause a buffer overflow. Similarly, if consumers fetch data too quickly, the buffer will empty out and they would start fetching invalid or obsolete data. In addition, the buffer has to be protected with a mutex lock, otherwise producers would be competing for the same slot, and consumers could fetch the same data.

The latter problem is solved by surrounding buffer operations with a mutex lock/unlock. This makes the buffer MT-Safe. The former problem is be solved in similar way A-B synchronization was solved >>3 ("abababababababab..."). Producers and consumers will block themselves if the buffer is full or empty respectively, but they will also signal each other each time they put in or take out data from the buffer

Implementation

POSIX Semaphores used: 
sem_t mutex, full, empty;
int main() {
    sem_init(&mutex, 0, 1);
    sem_init(&full,  0, BUFFER_SIZE);
    sem_init(&empty, 0, 0);
    ...
    sem_destroy(&mutex);
    sem_destroy(&full);
    sem_destroy(&empty);
}


Producer threads: 
void* producer(void* data)
{
    for ( ; ; ) {
        auto data = PRODUCE_DATA();
        sem_wait(&full);
        sem_wait(&mutex);
        BUFFER_PUT(buffer, data);
        assert(sem_post(&mutex) == 0);
        assert(sem_post(&empty) == 0);
    }
    return NULL;
}


Consumer threads: 
void* consumer(void* data)
{
    for ( ; ; ) {
        sem_wait(&full);
        sem_wait(&mutex);
        auto data = BUFFER_GET(buffer);
        assert(sem_post(&mutex) == 0);
        assert(sem_post(&empty) == 0);
        CONSUME_DATA(data);
    }
    return NULL;
}


Full code: 
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>

#define RED(s) ("\e[7m
Post too long. Click here to view the full text.
>>
  No. 6

File: rwlock.png ( 32.35 KB , 525x338 , 1655656617191.png )

Image
Readers and Writers
Assume there
NN
reader threads and
MM
writer threads and a shared file. Reader threads should be able to concurrently read the file, but only one writer should be able to modify the file. Readers' lock is often called a "shared lock" while writers' lock is often called "exclusive lock".

In Unix, this type of lock is already provided by the OS through 
flock()
: 
void MT_safe_read(int fd) 
{   
    flock(fd, LOCK_SH);

    /* Read */

    flock(fd, LOCK_UN);
}

void MT_safe_write(int fd) 
{
    flock(fd, LOCK_EX);
    
    /* Write */
    
    flock(fd, LOCK_UN);
}


In addition, POSIX threads (pthreads) also have an implementation of a read/write lock: 
void MT_safe_read(pthread_rwlock_t *rw) 
{   
    pthread_rwlock_rdlock(rw);

    /* Read */

    pthread_rwlock_unlock(rw);
}

void MT_safe_write(pthread_rwlock_t *rw) 
{
    pthread_rwlock_wrlock(rw);

    /* Read */

    pthread_rwlock_unlock(rw);
}


Using POSIX semaphores, RW-lock logic will have to implemented manually. The basic idea is: A reader (or writer) will check if they can read (or write) before locking the file with a shared (or exclusive) lock. If they find themselves unable to lock the file, they will put themselves in the "want-to-read" waiting queue (or "want-to-write" waiting queue) . Once any process finishes reading (or writing) they will check if there is anybody in the "want-to-write" waiting queue & writing is allowed, or if there is anybody in the "want-to-read" waiting queue & reading is allowed. If yes, they will be let through. If not, the mutex will be released (checking process needs to be atomic thus a mutex is necessary).

A pseudo-code of this logic would look like: 

void rw_lock(...) {
    /* Acquire lock */
    wait(MUTEX)
    
    /* Check condition */
    if (lock) {
        if (isReader) {
            if (! can_read) {
                signal(MUTEX)
                wait(R_QUEUE)
            }
        } else if (isWriter) {
            if (! can_write) {
                signal(MUTEX)
                wait(W_QUEUE)
            }
        }
    }
    
    /* Allow next */
    if (writers_waiting > 0 && can_w
Post too long. Click here to view the full text.
>>
  No. 7

File: barrier.jpeg ( 97.42 KB , 1200x725 , 1655995461457.jpeg )

Image
Barrier synchronization
Barriers are used accumulate a certain number of threads on the barrier letting them continue.

Assume there are 5 threads downloading video clips from the internet for the purpose of splicing them together. Some threads will finish quicker than others depending on download speed and the size of the clip. In any case, every downloader thread has to wait for other four to finish downloading before splicing can happen.

Barriers are natively implemented by pthreads 
static int count = 5;
pthread_barrier_t bar;

void *thread(void *data) {
    for ( ; ; ) {
        ...
        pthread_barrier_wait(&bar);
        ...
    }
}

int main() {
    ...
    pthread_barrier_init(&bar, NULL, count);
    ...
    pthread_barrier_destroy(&bar);
}


Implementation using POSIX semaphores involves simply counting the number of threads blocked on the barrier and flushing all of them after a certain number is reached. The counter variable has to be protected with a mutex of course.

Implementation
bar.h 
#ifndef __BARRIER_H__
#define __BARRIER_H__
#include <semaphore.h>
#include <stdlib.h>
struct barrier_t {
    sem_t b_mutex;
    sem_t b_barrier;
    int b_required;
    int b_count;
    void* b_retval;
};

void bar_init(struct barrier_t *bar, int required);
void bar_wait(struct barrier_t *bar);
void bar_destroy(struct barrier_t *bar);

#endif


bar.c 
#include "bar.h"

void bar_init(struct barrier_t *bar, int required)
{
    sem_init(&bar->b_mutex, 0, 1);
    sem_init(&bar->b_barrier, 0, 0);
    bar->b_required = required;
    bar->b_count = 0;
    bar->b_retval = NULL;
}

void bar_wait(struct barrier_t *bar)
{
    sem_wait(&bar->b_mutex);
    bar->b_count += 1;
    if (bar->b_count == bar->b_required) {
        bar->b_count = 0;
        int i;
        for (i = 0; i < bar->b_required; i++)
            sem_post(&bar->b_barrier);
    }
    sem_post(&bar->b_mutex);
    sem_wait(&bar->b_barrier);
}

void bar_destroy(struct barrier_t *bar)
{
    sem_destroy(&bar->b_mutex);
    sem_destroy(&bar->b_barrier);
}


main.c 
#include <pthread.h>
#include
Post too long. Click here to view the full text.
>>
  No. 9
Thank you anonerd.
>>
  No. 11
Wow. Did you write this or is this copied from somewhere?

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] | Catalog | Archive
[ home ] [ math / cs / ai / phy / as / chem / bio / geo ] [ civ / aero / mech / ee / hdl / os / dev / web / app / sys / net / sec ] [ med / fin / psy / soc / his / lit / lin / phi / arch ] [ off / vg / jp / 2hu / tc / ts / adv / hr / meta / tex ] [ chat ] [ wiki ]