Welcome to shouzo's blog!

移動的覺察 / 詮釋者，致力於用技術重現所有天賦

20170407 [學習筆記] Linux 系統程式 (6)

2017-04-07

Linux 作業系統程式設計

Linux 作業系統程式設計
- 一、作業系統
一、作業系統
- 課程簡報
- 參考資料
  - 簡易的程式平行化方法－OpenMP（一）簡介
  - Toward Concurrency
(一) Thread Pools
- Create a number of threads in a pool where they await work.
- Advantages:
  - Usually slightly faster to service a request with an existing thread than create a new thread.
  - Allows the number of threads in the application(s) to be bound to the size of the pool.
  - Separating task to be performed from mechanics of creating task allows different strategies for running task.
    - Tasks could be scheduled to run periodically.
(二) OpenMP
- Set of compiler directives and an API for C, C++, FORTRAN.
- Provides support for parallel programming in shared-memory environments.
- Identifies parallel regions – blocks of code that can run in parallel.
#pragma omp parallel
- Create as many threads as there are cores.
```
#pragma omp parallel for
for(i = 0; i < N; i++) {
    c[i] = a[i] + b[i];
}
// Run for loop in parallel
```
Example
```
#include <omp.h>
#include <stdio.h>

int main(int argc, char *argv[]) {
    /* sequential code */
    
    #pragma omp parallel
    {
        printf("I am a parallel region.");
    }

    /* sequential code */
    
    return 0;
}
```
(三) Threading Issues

1. Semantics of fork() and exec()
- Does fork() duplicate only the calling thread or all threads?
  - Some UNIXes have two versions of fork
- Exec() usually works as normal – replace the running process including all threads.
2. Signal Handling
- Signals are used in UNIX systems to notify a process that a particular event has occurred.
- A signal handler is used to process signals.
  1. Signal is generated by particular event
  2. Signal is delivered to a process
  3. Signal is handled by one of two signal handlers:
    1. default
    2. user-defined
- Every signal has default handler that kernel runs when handling signal.
  - User-defined signal handler can override default.
  - For single-threaded, signal delivered to process.
- Where should a signal be delivered for multi-threaded?
  - Deliver the signal to the thread to which the signal applies.
  - Deliver the signal to every thread in the process.
  - Deliver the signal to certain threads in the process.
  - Assign a specific thread to receive all signals for the process.
3. Thread Cancellation
- Terminating a thread before it has finished.
- Thread to be canceled is target thread.
- Two general approaches:
  - Asynchronous cancellation terminates the target thread immediately.
  - Deferred cancellation allows the target thread to periodically check if it should be cancelled.
- Pthread code to create and cancel a thread:
```
pthread_t tid;

/* Create the thread */
pthread_create(&tid, 0, worker, NULL);

...

/* Cancel the thread */
pthread_cancel(tid);
```
4. Thread-Local Storage
- Thread-local storage (TLS) allows each thread to have its own copy of data.
- Useful when you do not have control over the thread creation process (i.e., when using a thread).
- Different from local variables
  - Local variables visible only during single function invocation.
  - TLS visible across function invocations
- Similar to static data
  - TLS is unique to each thread.
5. Scheduler Activations
- Both M:M and Two-level models require communication to maintain the appropriate number of kernel threads allocated to the application.
- Typically use an intermediate data structure between user and kernel threads – lightweight process (LWP)
  - Appears to be a virtual processor on which process can schedule user thread to run
  - Each LWP attached to kernel thread.
  - How many LWPs to create?
- Scheduler activations provide upcalls - a communication mechanism from the kernel to the upcall handler in the thread library.
- This communication allows an application to maintain the correct number kernel threads.
(四) Thread Scheduling
- Distinction between user-level and kernel-level threads.
- When threads supported, threads scheduled, not processes.
- Many-to-one and many-to-many models, thread library schedules user-level threads to run on LWP.
  - Known as process-contention scope (PCS) since scheduling competition is within the process.
  - Typically done via priority set by programmer.
- Kernel thread scheduled onto available CPU is system-contention scope (SCS) – competition among all threads in system.
(五) Pthread Scheduling
- API allows specifying either PCS or SCS during thread creation.
  - PTHREAD_SCOPE_PROCESS schedules threads using PCS scheduling.
  - PTHREAD_SCOPE_SYSTEM schedules threads using SCS scheduling.
- Can be limited by OS – Linux and Mac OS X only allow PTHREAD_SCOPE_SYSTEM.
(六) Multiple-Processor Scheduling
- CPU scheduling more complex when multiple CPUs are available.
- Homogeneous processors within a multiprocessor.
- Asymmetric multiprocessing – only one processor accesses the system data structures, alleviating the need for data sharing.
- Symmetric multiprocessing (SMP) – each processor is self-scheduling, all processes in common ready queue, or each has its own private queue of ready processes.
  - Currently, most common
- Processor affinity – process has affinity for processor on which it is currently running.
  - soft affinity
  - hard affinity
  - Variations including processor sets
- Load Balancing - attempts to keep workload evenly distributed.
  - Push migration – periodic task checks load on each processor, and if found pushes task from overloaded CPU to other CPUs.
  - Pull migration – idle processors pulls waiting task from busy processor.
(七) Socket - Message Passing

1. What is a socket？
- An interface between application and network.
  - The application creates a socket.
  - The socket type dictates the style of communication.
    - reliable vs. best effort
    - connection-oriented vs. connectionless
- Once configured the application can
  - pass data to the socket for network transmission
  - receive data from the socket (transmitted through the network by some other host)
2. Two essential types of sockets

(1) SOCK_STREAM
- a.k.a. TCP
- reliable delivery
- in-order guaranteed
- connection-oriented
- bidirectional
(2) SOCK_DGRAM
- a.k.a. UDP
- unreliable delivery
- no order guarantees
- no notion of “connection” – app indicates dest. for each packet
- can send or receive
3. Connection setup

課程作業
- 自 Client 端輸入一整數，將數字傳至 Server 端判斷是否為質數，再將結果回傳自 Client。
- client 部份
```
/*  Make the necessary includes and set up the variables.  */

#include <sys/types.h>
#include <sys/socket.h>
#include <stdio.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <stdlib.h>

int main()
{
    int sockfd;
    int len;
    struct sockaddr_in address;
    int in;     // integer
    int result;
    // char ch = 'A';
  

/*  Create a socket for the client.  */

    sockfd = socket(AF_INET, SOCK_STREAM, 0);

/*  Name the socket, as agreed with the server.  */

    address.sin_family = AF_INET;
    address.sin_addr.s_addr = inet_addr("127.0.0.1");
    address.sin_port = 9453;
    len = sizeof(address);

/*  Now connect our socket to the server's socket.  */

    result = connect(sockfd, (struct sockaddr *)&address, len);

    if(result == -1) {
        perror("oops: Client");
        exit(1);
    }

/*  We can now read/write via sockfd.  */

    printf("Please key in an integer：");
    scanf("%d", &in);

    write(sockfd, &in, sizeof(int));
    read(sockfd, &in, sizeof(int));

    if (in == 1)
        printf("Result from Server：數字'是質數'\n");
    else
        printf("result from server：數字'不是質數'\n");

    close(sockfd);
    exit(0);
}
```
- server 部份
```
/*  Make the necessary includes and set up the variables.  */

#include <sys/types.h>
#include <sys/socket.h>
#include <stdio.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <stdlib.h>

int main()
{
    int server_sockfd, client_sockfd;
    int server_len, client_len;
    struct sockaddr_in server_address;
    struct sockaddr_in client_address;

/*  Create an unnamed socket for the server.  */

    server_sockfd = socket(AF_INET, SOCK_STREAM, 0);

/*  Name the socket.  */

    server_address.sin_family = AF_INET;
    server_address.sin_addr.s_addr = inet_addr("127.0.0.1");
    server_address.sin_port = 9453;
    server_len = sizeof(server_address);
    bind(server_sockfd, (struct sockaddr *)&server_address, server_len);

/*  Create a connection queue and wait for clients.  */

    listen(server_sockfd, 5);
    while(1) {
        int i = 0, count = 0;   // Set loop
        char in;

        printf("Server waiting...\n");

/*  Accept a connection.  */

        client_len = sizeof(client_address);
        client_sockfd = accept(server_sockfd, 
            (struct sockaddr *)&client_address, &client_len);

/*  We can now read/write to client on client_sockfd.  */

        read(client_sockfd, &in, sizeof(int));
        printf("Input from Client = %d\n",in);

        for (i = in; i > 0; i--)
            if (in % i == 0)
                count++;
        
        if (count > 2)
            in = 0;
        else if (count <= 2)
            in = 1;
     
        write(client_sockfd, &in, sizeof(int));
        close(client_sockfd);
    }
}
```
- 執行結果
Read All
20170406 [學習筆記] 人工智慧 (6)

2017-04-06

人工智慧

人工智慧
- (一) Fuzzy 建模 (建立模型)
- 參考資源
  - http://fuzzy.cs.ovgu.de/ci/fs/
(一) Fuzzy 建模 (建立模型)
- 利用現有的輸入、輸出資料建立模型：y = f(x1, x2)。
- 規則表
Read All
20170403 [有感而發] 求學就像是吃餅，怎麼可能一口氣吃得完？當然是要從最有興趣的地方開始慢慢吃啊！

2017-04-03

未分類

心情記事
- 求學，就像是吃一塊漫無邊際的大餅
- 怎麼可能無所不知？不懂就只能坦白承認啦！
今天不談社團，來聊聊其他的。剛剛在看到 Jserv 在網路上發的一篇文：https://www.facebook.com/microjserv/posts/10155154029752389

讓我聯想到之前國、高中上課發問時的情景 (通常得到的答覆和上文差不多)。但是直到現在大四下學期，我發現自己在大學系上課程中得知的東西仍然有限。我可不希望以後詞窮被問了類似的問題 (以下對話參考自上方連結之原文)：

兒子好奇：「爸，什麼是電腦？為什麼電腦可以運作？」

我卻只能回答：「因為爸爸認真工作，乖乖繳交電費，讓你可以使用電腦。」

兒子不爽：「 … 原來你大學讀電機資訊系就學這些啊，讀了書卻無法正面回答我的問題，這樣讀書有什麼意思呢？你自己讀書沒用，又何必要求我讀書呢？」

上述情境當然有很多地方值得探討，但是以 「在體制教育內的求學期間不知道學了些什麼」 這個面向來看卻格外諷刺…

而我後來在進行一些更深入的實作和研究時，漸漸發現某些科目學問存在的重要性 (各個領域之間其實彼此都相互連結)。但是那些科目當初在授課時 「根本沒有學過」， 或者教授說 「那些東西在研究所時才會教」 …。

這時候又會想到那一句老話：「師父領進門，修行在個人。」我個人認為這句話不完全正確，要是遇到那種 「師父不引你進門，卻帶你用頭去撞門。」 的情況該怎麼辦呢？(還真的得算自己倒霉，認賠殺出？)

(… 唉，又講到傷心事了，回歸正題。)

求學，就像是吃一塊漫無邊際的大餅

我以目前自己所在的電資領域為出發點，先摒除掉「因為分數剛好，所以就到這裡」、「學非所願」、「唸到一半才發現這不是我想讀的科系」…等等原因。

求學就像是吃一塊大得漫無邊際的餅，有無限種吃法，就看你自己想要怎麼吃。試著想像一下：「這裡有一塊餅，你沒辦法一口氣吃完，該怎麼辦？」

廢話！這麼大塊的餅乾，怎麼可能一口氣吃得完？當然是要從你自己最有興趣的地方開始慢慢吃啊！

一門領域要學的東西有多少，才短短幾年怎麼可能全部都會？至少得從喜歡或者是一個不排斥的東西開始吧？

怎麼可能無所不知？不懂就只能坦白承認啦！

…回到最一開始的那一段對話，假設我真的不知道背後的原理，被這樣酸了：

兒子不爽：「 … 原來你大學讀電機資訊系就學這些啊，讀了書卻無法正面回答我的問題，這樣讀書有什麼意思呢？你自己讀書沒用，又何必要求我讀書呢？」

我希望這時候的我可以這樣回答：

我：「這個東西爸爸不懂，但是你不覺得這個問題很有趣嗎？我們一起來研究為什麼吧！」

求學讀書不應該是為了考試，而是為了要更加瞭解這個世界，同時也應該是一件發自內心想要去完成的事情。
Read All

20170331 [學習筆記] Linux 系統程式 (5)

2017-03-31

Linux 作業系統程式設計

一、作業系統

一、作業系統

課程簡報
參考資料
- Toward Concurrency
- Using condition variables in pthreads

(一) Thread Synchronization

1. Semaphore

semaphore.h

#include <semaphore.h>

int sem_init(sem_t *sem, int pshared, unsigned int value);
//create a semaphore

int sem_wait(sem_t *sem);
//lock a semaphore

int sem_post(sem_t *sem);
//unlock a semaphore

int sem_destroy(sem_t *sem);
//delete a semaphore

sem_init()

int sem_init(sem_t *sem, int pshared, unsigned
int value);

sem_t *sem：semaphore 識別字
int pshared：設定為 0 表示僅供目前的 process 及其 thread 使用。非 0 表示此 semaphore 與其他 process 共用
unsigned int value：semaphore 的初始值

sem_wait()

int sem_wait(sem_t *sem);

若 semaphore 為非 0，則 semaphore 值減 1；若 semaphore 為 0，則呼叫此 function 的 thread 會被 block ，直到 semaphore 值不為 0。

sem_post()

int sem_post(sem_t *sem);

對 semaphore 值加 1 。

sem_destroy()

int sem_destroy(sem_t *sem);
//delete a semaphore

2. Mutex

pthread.h

#include <pthread.h>

int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *mutexattr);
//create a mutex

int pthread_mutex_lock(pthread_mutex_t *mutex);
//lock a mutex

int pthread_mutex_unlock(pthread_mutex_t *mutex);
//unlock a mutex

int pthread_mutex_destroy(pthread_mutex_t *mutex);
//delete a mutex

pthread_mutex_init()

int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *mutexattr);

pthread_mutex_t *mutex：mutex 識別字
const pthread_mutexattr_t *mutexattr：mutex 的屬性。設定為 NULL 表示使用預設。

pthread_mutex_lock()

int pthread_mutex_lock(pthread_mutex_t *mutex);
//lock a mutex

pthread_mutex_unlock()

int pthread_mutex_unlock(pthread_mutex_t *mutex);
//unlock a mutex

pthread_mutex_destroy()

int pthread_mutex_destroy(pthread_mutex_t *mutex);
//delete a mutex

3. Condition Variables

4. Barrier

(二) Producer-Consumer Problem

1. Producer

item next produced;
while (true) {
    /* produce an item in next produced */
    
    while (((in + 1) % BUFFER SIZE) == out)
    ; /* do nothing */
        
    buffer[in] = next produced;
    in = (in + 1) % BUFFER SIZE;
}

2. Consumer

item next consumed;
while (true) {
    while (in == out)
    ; /* do nothing */
    
    next consumed = buffer[out];
    out = (out + 1) % BUFFER SIZE;
    
    /* consume the item in next consumed */
}

課程作業

/*
 *  Solution to Producer Consumer Problem
 *  Using Ptheads, a mutex and condition variables
 *  From Tanenbaum, Modern Operating Systems, 3rd Ed.
 */

/*
    In this version the buffer is a single number.
    The producer is putting numbers into the shared buffer
    (in this case sequentially)
    And the consumer is taking them out.
    If the buffer contains zero, that indicates that the buffer is empty.
    Any other value is valid.
*/

#include <stdio.h>
#include <pthread.h>

#define MAX 10//000000			/* Numbers to produce */
#define BUFFER_SIZE 5

pthread_mutex_t the_mutex;
pthread_cond_t condc, condp;
int buffer[BUFFER_SIZE];
int in = 0, out = 0;

void *producer(void *ptr) {
    int i;

    for (i = 0; i < MAX; i++) {
        pthread_mutex_lock(&the_mutex);	/* protect buffer */
        
        while (((in + 1) % BUFFER_SIZE) == out)		       /* If there is something in the buffer then wait */
            pthread_cond_wait(&condp, &the_mutex);

        buffer[in] = i;
        printf("ProBuffer[%d]：%2d\n", in, buffer[in]);
        in = (in + 1) % BUFFER_SIZE;
   
        pthread_cond_signal(&condc);	/* wake up consumer */
        pthread_mutex_unlock(&the_mutex);	/* release the buffer */
    }

    pthread_exit(0);
}


void *consumer(void *ptr) {
    int i;

    for (i = 0; i < MAX; i++) {
        pthread_mutex_lock(&the_mutex);	/* protect buffer */
    
        while (in == out)			/* If there is nothing in the buffer then wait */
            pthread_cond_wait(&condc, &the_mutex);
    
        printf("ConBuffer[%d]：%2d\n", out, buffer[out]);
        out = (out + 1) % BUFFER_SIZE;
        buffer[out] = 0;
    
        pthread_cond_signal(&condp);	/* wake up consumer */
        pthread_mutex_unlock(&the_mutex);	/* release the buffer */
    }
    pthread_exit(0);
}

int main(int argc, char **argv) {
    pthread_t pro, con;

    // Initialize the mutex and condition variables
    /* What's the NULL for ??? */
    pthread_mutex_init(&the_mutex, NULL);	
    pthread_cond_init(&condc, NULL);		/* Initialize consumer condition variable */
    pthread_cond_init(&condp, NULL);		/* Initialize producer condition variable */

    // Create the threads
    pthread_create(&con, NULL, consumer, NULL);
    pthread_create(&pro, NULL, producer, NULL);

    // Wait for the threads to finish
    // Otherwise main might run to the end
    // and kill the entire process when it exits.
    pthread_join(con, NULL);
    pthread_join(pro, NULL);

    // Cleanup -- would happen automatically at end of program
    pthread_mutex_destroy(&the_mutex);	/* Free up the_mutex */
    pthread_cond_destroy(&condc);		/* Free up consumer condition variable */
    pthread_cond_destroy(&condp);		/* Free up producer condition variable */
}

執行結果

Read All

20170330 [學習筆記] 人工智慧 (5)

2017-03-30

人工智慧

人工智慧

Read All

18/26

Welcome to shouzo's blog!

20170407 [學習筆記] Linux 系統程式 (6)

一、作業系統

(一) Thread Pools

(二) OpenMP

#pragma omp parallel

Example

(三) Threading Issues

1. Semantics of fork() and exec()

2. Signal Handling

3. Thread Cancellation

4. Thread-Local Storage

5. Scheduler Activations

(四) Thread Scheduling

(五) Pthread Scheduling

(六) Multiple-Processor Scheduling

(七) Socket - Message Passing

1. What is a socket？

2. Two essential types of sockets

(1) SOCK_STREAM

(2) SOCK_DGRAM

3. Connection setup

課程作業

20170406 [學習筆記] 人工智慧 (6)

(一) Fuzzy 建模 (建立模型)

20170403 [有感而發] 求學就像是吃餅，怎麼可能一口氣吃得完？當然是要從最有興趣的地方開始慢慢吃啊！

求學，就像是吃一塊漫無邊際的大餅

怎麼可能無所不知？不懂就只能坦白承認啦！

20170331 [學習筆記] Linux 系統程式 (5)

一、作業系統

(一) Thread Synchronization

1. Semaphore

semaphore.h

sem_init()

sem_wait()

sem_post()

sem_destroy()

2. Mutex

pthread.h

pthread_mutex_init()

pthread_mutex_lock()

pthread_mutex_unlock()

pthread_mutex_destroy()

3. Condition Variables

pthread_cond_init (condition, attr)

pthread_cond_destroy (condition)

pthread_condattr_init (attr)

pthread_condattr_destroy (attr)

4. Barrier

(二) Producer-Consumer Problem

1. Producer

2. Consumer

課程作業

20170330 [學習筆記] 人工智慧 (5)

`#pragma omp parallel`