Welcome to shouzo's blog!

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

20170428 [學習筆記] Linux 系統程式 (8)

2017-04-28

Linux 作業系統程式設計

Linux 作業系統程式設計
- 一、作業系統
一、作業系統
- 課程簡報
  - Chapter 6: Process Scheduling
Race Condition
- Consumer
- Producer
- Race Condition
(一) Critical-Section Problem
- General Structure：
(二) Solution to Critical-Section Problem
1. Mutual Exclusion - If process Pi is executing in its critical section, then no other processes can be executing in their critical sections.
2. Progress - If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely.
3. Bounded Waiting - A bound must exist on the number of times that other processes are allowed to enter their critical sections.
  - Assume that each process executes at a nonzero speed.
  - No assumption concerning relative speed of the n processes.
4. Two approaches depending on if kernel is preemptive or non-preemptive.
  - Preemptive – allows preemption of process when running in kernel mode.
  - Non-preemptive – runs until exits kernel mode, blocks, or voluntarily yields CPU.
    - Essentially free of race conditions in kernel mode.
(三) Peterson’s Solution
- Good algorithmic description of solving the problem.
- Two process solution
- Assume that the load and store instructions are atomic; that is, cannot be interrupted
- The two processes share two variables：
  - int turn;
  - Boolean flag[2]
- The variable turn indicates whose turn it is to enter the critical section
- The flag array is used to indicate if a process is ready to enter the critical section.
- flag[i] = true implies that process Pi is ready!
- Provable that
  1. Mutual exclusion is preserved.
  2. Progress requirement is satisfied.
  3. Bounded-waiting requirement is met.
(四) Synchronization Hardware
- Many systems provide hardware support for critical section code.
- All solutions below based on idea of locking.
  - Protecting critical regions via locks.
- Uniprocessors – could disable interrupts
  - Currently running code would execute without preemption.
  - Generally too inefficient on multiprocessor systems.
    - Operating systems using this not broadly scalable.
- Modern machines provide special atomic hardware instructions.
  - Atomic = non-interruptible
    - Either test memory word and set value.
    - Or swap contents of two memory words.
1. test_and_set Instruction
- Solution using test_and_set()
- Bounded-waiting Mutual Exclusion with test_and_set
2. compare_and_swap Instruction
- Solution using compare_and_swap
(五) Mutex Locks
- Previous solutions are complicated and generally inaccessible to application programmers.
- OS designers build software tools to solve critical section problem.
- Simplest is mutex lock
- Product critical regions with it by first acquire() a lock then release() it.
  - Boolean variable indicating if lock is available or not
- Calls to acquire() and release() must be atomic.
  - Usually implemented via hardware atomic instructions
- But this solution requires busy waiting.
  - This lock therefore called a spinlock
acquire() and release()
Read All
20170427 [社團相關] 關於社團傳承，你必須要知道的事情...

2017-04-27

社團

社團
- (一) 關於社團傳承，你必須要知道的事情…
(一) 關於社團傳承，你必須要知道的事情…
- 簡報網址：https://shouzo.github.io/collections/clubs/20170427-club-inheritance.pdf
- SlideShare：https://www.slideshare.net/danny200026/20170427-75453393
[畫面預覽]
Read All
20170422 [社團相關] 原始點醫學分享

2017-04-22

社團

社團
- (一) 原始點醫學分享
(一) 原始點醫學分享
- 簡報網址：https://shouzo.github.io/collections/clubs/20170422-Original_Point.pdf
- SlideShare：https://www.slideshare.net/danny200026/20170422
[畫面預覽]
Read All
20170414 [學習筆記] Linux 系統程式 (7)

2017-04-14

Linux 作業系統程式設計

Linux 作業系統程式設計
- 一、作業系統
一、作業系統
- 課程簡報
  - Chapter 3: Process Concept
(一) Direct Communication
- Processes must name each other explicitly：
  - send(P, message) – send a message to process P
  - receive(Q, message) – receive a message from process Q
- Properties of communication link
  - Links are established automatically
  - A link is associated with exactly one pair of communicating processes
  - Between each pair there exists exactly one link
  - The link may be unidirectional, but is usually bi-directional
(二) Indirect Communication
- Messages are directed and received from mailboxes (also referred to as ports)
  - Each mailbox has a unique id
  - Processes can communicate only if they share a mailbox
- Properties of communication link
  - Link established only if processes share a common mailbox
  - A link may be associated with many processes
  - Each pair of processes may share several communication links
  - Link may be unidirectional or bi-directional
- Operations
  - create a new mailbox
  - send and receive messages through mailbox
  - destroy a mailbox
- Primitives are defined as：
  - send(A, message) – send a message to mailbox A
  - receive(A, message) – receive a message from mailbox A
- Mailbox sharing
  - Who gets the message？
    - P 1 , P 2 , and P 3 share mailbox A
    - P 1 , sends; P 2 and P 3 receive
- Solutions
  - Allow a link to be associated with at most two processes.
  - Allow only one process at a time to execute a receive operation.
  - Allow the system to select arbitrarily the receiver. Sender is notified who the receiver was.
(三) Synchronization
- Message passing may be either blocking or non-blocking
- Blocking is considered synchronous
  - Blocking send has the sender block until the message is received
  - Blocking receive has the receiver block until a message is available
- Non-blocking is considered asynchronous
  - Non-blocking send has the sender send the message and continue
  - Non-blocking receive has the receiver receive a valid message or null
- Different combinations possible
  - If both send and receive are blocking, we have a rendezvous
- Producer-consumer becomes trivial
(四) Buffering
- Queue of messages attached to the link; implemented in one of three ways
  1. Zero capacity – 0 messages Sender must wait for receiver (rendezvous)
  2. Bounded capacity – finite length of n messages Sender must wait if link full
  3. Unbounded capacity – infinite length Sender never waits
Examples of IPC Systems

1. POSIX
- POSIX Shared Memory
  - Process first creates shared memory segment：shm_fd = shm_open(name, O CREAT | O RDRW, 0666);
  - Also used to open an existing segment to share it
  - Set the size of the object：ftruncate(shm fd, 4096);
  - Now the process could write to the shared memory：sprintf(shared memory, "Writing to shared memory");
2. Mach
- Mach communication is message based
  - Even system calls are messages
  - Each task gets two mailboxes at creation- Kernel and Notify
  - Only three system calls needed for message transfer：msg_send(), msg_receive(), msg_rpc()
  - Mailboxes needed for commuication, created via：port_allocate()
  - Send and receive are flexible, for example four options if mailbox full：
    - Wait indefinitely
    - Wait at most n milliseconds
    - Return immediately
    - Temporarily cache a message
3. Windows
- Message-passing centric via advanced local procedure call (LPC) facility
  - Only works between processes on the same system
  - Uses ports (like mailboxes) to establish and maintain communication channels
  - Communication works as follows：
    - The client opens a handle to the subsystem’s connection port object.
    - The client sends a connection request.
    - The server creates two private communication ports and returns the handle to one of them to the client.
    - The client and server use the corresponding port handle to send messages or callbacks and to listen for replies.
(五) Communications in Client-Server Systems

1. Sockets
- A socket is defined as an endpoint for communication
- Concatenation of IP address and port – a number included at start of message packet to differentiate network services on a host
  - The socket 161.25.19.8:1625 refers to port 1625 on host 161.25.19.8
- Communication consists between a pair of sockets
- All ports below 1024 are well known, used for standard services
- Special IP address 127.0.0.1 (loopback) to refer to system on which process is running
2. Remote Procedure Calls
- Remote procedure call (RPC) abstracts procedure calls between processes on networked systems
  - Again uses ports for service differentiation
- Stubs – client-side proxy for the actual procedure on the server
- The client-side stub locates the server and marshalls the parameters
- The server-side stub receives this message, unpacks the marshalled parameters, and performs the procedure on the server
- On Windows, stub code compile from specification written in Microsoft Interface Definition Language (MIDL)
- Data representation handled via External Data Representation (XDL) format to account for different architectures
  - Big-endian and little-endian
- Remote communication has more failure scenarios than local
  - Messages can be delivered exactly once rather than at most once
- OS typically provides a rendezvous (or matchmaker) service to connect client and server
3. Pipes
- Acts as a conduit allowing two processes to communicate
- Issues
  - Is communication unidirectional or bidirectional?
  - In the case of two-way communication, is it half or full-duplex?
  - Must there exist a relationship (i.e. parent-child) between the communicating processes?
  - Can the pipes be used over a network?
課堂作業
- client 部份
```
/* vim: ts=4 sw=4 et
*/
/* The second program is the producer and allows us to enter data for consumers.
 It's very similar to shm1.c and looks like this. */

#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include <sys/shm.h>

#include "shm_com.h"

int main()
{
    int running = 1;
    void *shared_memory = (void *)0;
    struct shared_use_st *shared_stuff;
    char buffer[BUFSIZ];
    int shmid;
    int rand_arr[10];

    shmid = shmget((key_t)1234, sizeof(struct shared_use_st), 0666 | IPC_CREAT);
	
    if (shmid == -1) {
        fprintf(stderr, "shmget failed\n");
        exit(EXIT_FAILURE);
    }

    shared_memory = shmat(shmid, (void *)0, 0);
    if (shared_memory == (void *)-1) {
        fprintf(stderr, "shmat failed\n");
        exit(EXIT_FAILURE);
    }

    printf("Memory attached at %X\n", (unsigned int)(long)shared_memory);

    shared_stuff = (struct shared_use_st *)shared_memory;

    while (1) {
        while (shared_stuff->written_by_you == 1) {
            sleep(1);            
            printf("waiting for client...\n");
        }
        
        /*
        printf("\nPress Enter to continue...");
        while (getchar() != '\n');
        // fgets(buffer, BUFSIZ, stdin);
        */

        srand((unsigned)time(NULL));
        for (int i = 0; i < 10; i++) {
            rand_arr[i] = rand() % 100 + 1;
            shared_stuff->some_text[i] = rand_arr[i];
            printf("[%d]%d \t", i, rand_arr[i]);
        }
        printf("\n");

        //  strncpy(shared_stuff->some_text, &rand_arr, TEXT_SZ);
        shared_stuff->written_by_you = 1;
        break;
    }

    if (shmdt(shared_memory) == -1) {
        fprintf(stderr, "shmdt failed\n");
        exit(EXIT_FAILURE);
    }
    exit(EXIT_SUCCESS);
}
```
- server 部份
```
/* vim: ts=4 sw=4 et
*/
/* Our first program is a consumer. After the headers the shared memory segment
 (the size of our shared memory structure) is created with a call to shmget,
 with the IPC_CREAT bit specified. */

#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include <sys/shm.h>

#include "shm_com.h"

int main()
{
    int running = 1;
    void *shared_memory = (void *)0;
    struct shared_use_st *shared_stuff;
    int shmid;

    srand((unsigned int)getpid());    

    shmid = shmget((key_t)1234, sizeof(struct shared_use_st), 0666 | IPC_CREAT);
    
    if (shmid == -1) {
        fprintf(stderr, "shmget failed\n");
        exit(EXIT_FAILURE);
    }

/* We now make the shared memory accessible to the program. */

    shared_memory = shmat(shmid, (void *)0, 0);
    if (shared_memory == (void *)-1) {
        fprintf(stderr, "shmat failed\n");
        exit(EXIT_FAILURE);
    }

    printf("Memory attached at %X\n", (unsigned int)(long)shared_memory);

/* The next portion of the program assigns the shared_memory segment to shared_stuff,
 which then prints out any text in written_by_you. The loop continues until end is found
 in written_by_you. The call to sleep forces the consumer to sit in its critical section,
 which makes the producer wait. */

    shared_stuff = (struct shared_use_st *)shared_memory;
    shared_stuff->written_by_you = 0;
    
    while (1) {
        if (shared_stuff->written_by_you) {
            printf("\nYou wrote:\n");
            
            for (int i = 0; i < 10; i++) {
                printf("[%d]%d \t", i, shared_stuff->some_text[i]);
            }
            printf("\n");

            sleep(rand() % 4); /* make the other process wait for us ! */
            // shared_stuff->written_by_you = 0;
            
        shared_stuff->written_by_you = 0;
        }
    }
/* Lastly, the shared memory is detached and then deleted. */


    if (shmdt(shared_memory) == -1) {
        fprintf(stderr, "shmdt failed\n");
        exit(EXIT_FAILURE);
    }

    if (shmctl(shmid, IPC_RMID, 0) == -1) {
        fprintf(stderr, "shmctl(IPC_RMID) failed\n");
        exit(EXIT_FAILURE);
    }

    exit(EXIT_SUCCESS);
}
```
- 執行結果
Read All
20170413 [學習筆記] 人工智慧 (7)

2017-04-13

人工智慧

人工智慧

Read All