作業系統

tags: 作業系統

20170302

20170309

(一) Process in Memory

(二) Process State


* new: The process is being created
* running: Instructions are being executed.
* waiting: The process is waiting for some event to occur.
* ready: The process is waiting to be assigned to a processor.
* terminated: The process has finished execution.

(三) Process Control Block (PCB)

(四) Process Switch

(五) Process、Thread

(六) Process Scheduling

Schedulers

Degree of multiprogramming：多工程度、記憶體中行程的總數量

Processes

(七) Process Creation

#include <sys/types.h>
#include <stdio.h>
#include <unistd.h>

int main(void) {
	pid_t pid;
	
/* fork a child process */
	pid = fork();

	
	if (pid < 0) {		// erro occurred
		fprintf(stderr, "Fork Failed");
		return 1;
	}
	else if (pid == 0) {	// child process
		execlp("/bin/ls", "ls", NULL);
	}
	else {			// parent process
		// parent will wait for the child to complete
		wait(NULL);
		printf("Child Complete\n");
	}
	
	return 0;
}

20170316

一、Basic Concepts

二、CPU Scheduler

三、Dispatcher

四、Scheduling Algorithm Optimization Criteria

  1. CPU utilization – keep the CPU as busy as possible.
  2. Throughput – # of processes that complete their execution per time unit.
  3. Turnaround time – amount of time to execute a particular process.
  4. Waiting time – amount of time a process has been waiting in the ready queue.
  5. Response time – amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment).

五、Scheduling Algorithm

(一) First-Come, First-Served (FCFS)：先到先服務法

(二) Shortest-Job-First (SJF)：最短優先法

(三) Priority Scheduling (PS)：優先權排班法

(四) Round Robin (RR)：輪流法

1. Time Quantum and Context Switch Time

2. Turnaround Time Varies With The Time Quantum

(五) Multilevel

1. Queue

2. Feedback Queue

課程作業

scheduler()

main()

  1. call scheduler() to get the pid of a process,
  2. if the pid obtained by step 1 is -1, go to step 7.
  3. if the remaining time of the selected process is smaller than a time slice add clock by the remaining time of the process store the value of clock as the turnaround time of the process；set the remaining time of the process as zero, endif.
  4. if the remaining time of the selected process is equal to a time slice add clock by a time slice store the value of clock as the turnaround time of the process.set the remaining time of the process as zero, endif.
  5. if the remaining time of the selected process is larger than a time slice add clock by a time slice subtract the remaining time of the process by a time slice, endif.
  6. go to step 1.
  7. summate the turnaround time of all the processes.
  8. calculate the average turnaround time of the processes.







































#define TIMESLICE	1
#define PROCESS_NO	4
int remaintime[PROCESS_NO] = {6, 3, 1, 7};
int turnaroundtime[PROCESS_NO];
int clock = 0; // global time clock

int scheduler(void)
{
    // select one from the read processes by the round robin algorithm, 
    // and then return the pid of the selected process;
    // if no ready process (i.e., all the processes are finished), then return -1;
}

int main(void)
{

    //1. call scheduler() to get the pid of a process,
    //2. if the pid obtained by step 1 is -1, go to step 7
    //3. if the remaining time of the selected process is smaller than a time slice
    //         add clock by the remaining time of the process
    //         store the value of clock as the turnaround time of the process.
    //         set the remaining time of the process as zero.
    //  endif
    //4. if the remaining time of the selected process is equal to a time slice
    //         add clock by a time slice 
    //         store the value of clock as the turnaround time of the process.
    //         set the remaining time of the process as zero.
    //  endif
    //5. if the remaining time of the selected process is larger than a time slice
    //         add clock by a time slice
    //         subtract the remaining time of the process by a time slice
    //  endif
    //6. go to step 1.
    //7. summate the turnaround time of all the processes
    //8. calculate the average turnaround time of the processes
           
}

20170323

Multithread Architecture

一、Multicore Programming

二、Concurrency vs Parallelism

1. Concurrency

2. Parallelism

3. Concurrency vs Parallelism

Rob Pike 用地鼠燒書做例子:

Concurrency: 是指程式架構，將程式拆開成多個可獨立運作的工作，像是驅動程式都可獨立運作，但不需要平行化

Parallelism: 是指程式執行，同時執行多個程式。Concurrency 可能會用到 parallelism，但不一定要用 parallelism 才能實現 concurrency。eg：Vector dot product

4. 相關整理

線上教材 Introduction to OpenMP 做了以下整理:

(1) Concurrent (並行)

三、Single and Multithreaded Processes

四、User Threads and Kernel Threads

五、Multithreading Models

  1. Many-to-One

    • Many user-level threads mapped to single kernel thread.
    • One thread blocking causes all to block.
    • Multiple threads may not run in parallel on muticore system because only one may be in kernel at a time.
    • Examples：Solaris Green Threads、GNU Portable Threads

  2. One-to-One

    • Each user-level thread maps to kernel thread.
    • Creating a user-level thread creates a kernel thread.
    • More concurrency than many-to-one.
    • Number of threads per process sometimes restricted due to overhead.
    • Examples：Windows NT/XP/2000、Linux、Solaris 9 and later

  3. Many-to-Many

  1. Two-level

六、Pthreads

pthread.h

#include <pthread.h>

int pthread_create(pthread_t *thread, pthread_attr_t
*attr, void *(*start_routine)(void *), void *arg);
//create a thread


void pthread_exit(void *retval);
//terminate a thread


int pthread_join(pthread_t th, void **thread_return);
//wait for thread termination
pthread_create()
int pthread_create(pthread_t *thread,
pthread_attr_t *attr, void *(*start_routine)(void
*), void *arg);
pthread_exit()
void pthread_exit(void *retval);
pthread_join()
int pthread_join(pthread_t th, void **thread_return);

課程作業

從 1 - 10000 之間取出所有的質數，利用 threads 來分配計算質數的範圍。























































































































#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h> 
#include <time.h>

#define NUM_THREADS 10
#define MSIZE 10000

// 找出 1 - 10000 的所有質數

static double getDoubleTime();
void *thread_function(void *arg);
pthread_mutex_t work_mutex;

// 宣告 prime_array 陣列
int prime_array[NUM_THREADS][(MSIZE / NUM_THREADS)];


int main(void) {
	int res;
	pthread_t a_thread[NUM_THREADS];
	void *thread_result;
	int lots_of_threads;
    int print_prime = 0;


	// start to measure time...
	double start_time = getDoubleTime();
	
	// initialize mutex...
	res = pthread_mutex_init(&work_mutex, NULL);
	if (res != 0) {
       	perror("Mutex initialization failed");
	    exit(EXIT_FAILURE);
    }

	// pthread_create...
	for (lots_of_threads = 0; lots_of_threads < NUM_THREADS; lots_of_threads ++) {
		res = pthread_create(&(a_thread[lots_of_threads]), NULL, thread_function, (void*)(long)lots_of_threads);

        if (res != 0) {
			perror("Thread creation failed");
        		exit(EXIT_FAILURE);
		}
	}

	// pthread_join...
	for (lots_of_threads = NUM_THREADS - 1; lots_of_threads >= 0; lots_of_threads--) {
        	res = pthread_join(a_thread[lots_of_threads], &thread_result); 

            if (res != 0) {
	            perror("pthread_join failed");
        	}
    }	
    
    int i = 0;  // 設定計數器
    for (lots_of_threads = 0; lots_of_threads < NUM_THREADS; lots_of_threads ++) { 
        printf("\n\nThe thread[%d]'s numbers：\n", lots_of_threads);

        for (i = 0; i < (MSIZE / NUM_THREADS); i++) {
            if (prime_array[lots_of_threads][i] != 0)
                printf("%d\t", prime_array[lots_of_threads][i]);                        }
    }


	printf("\nThread joined\n");

	// stop measuring time...
	double finish_time = getDoubleTime();
	printf("Execute Time:  %.3lf ms\n", (finish_time - start_time));
    exit(EXIT_SUCCESS);
}


void *thread_function(void *arg) {
    // pthread_mutex_lock(&work_mutex);
	
    int my_num = (long)arg;
	// if (MSIZE % NUM_THREADS != 0){    printf("error");   pthread_exit(-1);    }

    int start_num = (MSIZE / NUM_THREADS) * my_num + 1;
	int end_num = (MSIZE / NUM_THREADS) * (my_num + 1);

    int i = 0, j = 0, k = 0;   // Set the loop
    int count = 0;      // Set the counter
    int result = 0;     // result

    printf("I'm thread[%d], start_num:%d, end_num:%d\n", my_num, start_num, end_num);

    /* find the prime number */
    for (i = start_num; i <= end_num; i++) {
        count = 0;      // Reset counter

        for (j = 1; j <= i; j++) {
            if (i % j == 0)
                count += 1;
        }
        
        if (count == 2) { 
            prime_array[my_num][k] = i;
            k++;
        }
    }


    // pthread_mutex_unlock(&work_mutex);
	pthread_exit(0);
}


static double getDoubleTime() {
        struct timeval tm_tv;
        gettimeofday(&tm_tv,0);
        return (double)(((double)tm_tv.tv_sec * (double)1000. + (double)(tm_tv.tv_usec)) * (double)0.001);
}

20170330

(一) 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_wait()
int sem_wait(sem_t *sem);
sem_post()
int sem_post(sem_t *sem);
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_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

pthread_cond_init (condition, attr)

pthread_cond_destroy (condition)

pthread_condattr_init (attr)

pthread_condattr_destroy (attr)

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 */
}

20170406

(一) Thread Pools

(二) OpenMP

#pragma omp parallel

#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()

2. Signal Handling

3. Thread Cancellation

pthread_t tid;

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

...

/* Cancel the thread */
pthread_cancel(tid);

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

課程作業

























































/*  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);
}































































/*  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);
    }
}

20170413

(一) Direct Communication

(二) Indirect Communication

(三) Synchronization

(四) Buffering

Examples of IPC Systems

1. POSIX

2. Mach

3. Windows

(五) Communications in Client-Server Systems

1. Sockets

2. Remote Procedure Calls

3. Pipes


課堂作業








































































/* 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);
}
















































































/* 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);
}

20170424

Race Condition

(一) Critical-Section Problem

(二) 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

(四) Synchronization Hardware

1. test_and_set Instruction

2. compare_and_swap Instruction

(五) Mutex Locks

acquire() and release()

20170504

(一) Semaphore

wait(S)
    while (S <= 0)
        ; //busy wait
    S--;
}
signal(S) {
    S++;
}

1. Usage

P1:
    S1;
    signal(synch);
P2:
    wait(synch);
    S2;

2. Implementation

(1) Busy waiting
(2) with no Busy waiting
typedef struct{
    int value;
    struct process *list;
} semaphore;

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // add this process to S->list;
        block();
    }
}

signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // remove a process P from S->list;
        wakeup(P);
    }
}

(二) Deadlock and Starvation

(三) Classical Problems of Synchronization

1. Bounded-Buffer Problem

(1) The structure of the producer process
do {
    ...
    /* produce an item in next_produced */
    ...
    
    wait(empty);
    wait(mutex);
    
    ...
    /* add next produced to the buffer */
    ...

    signal(mutex);
    signal(full);
} while (true);
(2) The structure of the consumer process
do {
    wait(full);
    wait(mutex);

    ...
    /* remove an item from buffer to next_consumed */
    ...

    signal(mutex);
    signal(empty);

    ...
    /* consume the item in next consumed */
    ...
} while (true);

2. Readers-Writers Problem

(1) The structure of a writer process
do {
    wait(rw_mutex);
    
    ...
    /* writing is performed */
    ...
    
    signal(rw_mutex);
} while (true);
(2) The structure of a reader process
do {
    wait(mutex);
    read_count++;
    
    
    if (read_count == 1)    // only for the first reader entering
        wait(rw_mutex);
        
    signal(mutex);    // if the first reader wait for rw_mutex, other readers will be blocked on wait(mutex)
        
    ...
    /* reading is performed */
    ...
        
    wait(mutex);
    read_count--;
        
    if (read_count == 0)    // only for the last reader leaving
        signal(rw_mutex);
    
    signal(mutex);
} while (true)
(3) Problem

3. Dining-Philosophers Problem

(1) In the case of 5 philosophers
do {
    wait ( chopstick[i] );
    wait ( chopStick[ (i+1) % 5] );
    
    // eat

    signal ( chopstick[i] );
    signal (chopstick[ (i+1) % 5] );
    
    // think
    
} while (TRUE);
(2) Monitors

Monitors Implementation
1. Using Semaphores
semaphore mutex; // (initially = 1)
semaphore next; // (initially = 0)
int next_count = 0;

wait(mutex);

...
body of F;
...

if (next_count > 0)
    signal(next)
else
    signal(mutex);
2. Condition Variables
semaphore x_sem; // (initially = 0)
int x_count = 0;

x-count++;
if (next_count > 0)
    signal(next);
else
    signal(mutex);
wait(x_sem);
x-count--;
Resuming Processes
Allocate Single Resource
monitor ResourceAllocator
{
    boolean busy;
    condition x;
    
    void acquire(int time) {
        if (busy)
            x.wait(time);
        busy = TRUE;
    }
    
    void release() {
        busy = FALSE;
        x.signal();
    }
    
    initialization code() {
        busy = FALSE;
    }
}
(3) Solution
DiningPhilosophers.pickup(i);
    EAT
DiningPhilosophers.putdown(i);

monitor DiningPhilosophers
{
    enum { THINKING; HUNGRY, EATING) state [5] ;
    condition self [5];

    void pickup (int i) {
        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING) self [i].wait;
    }
    
    void putdown (int i) {
        state[i] = THINKING;
    
        /* test left and right neighbors */
        test((i + 4) % 5);
        test((i + 1) % 5);
    }

    void test (int i) {
        if ((state[(i + 4) % 5] != EATING) &&
(state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING)) {
            state[i] = EATING;
            self[i].signal();
    }
}

    initialization_code() {
        for (int i = 0; i < 5; i++)
            state[i] = THINKING;
    }
}

20170511

(一) Deadlock Characterization

(二) Resource-Allocation Graph


1. Example

2. Basic Facts

3. Methods for Handling Deadlocks

(三) Deadlock Prevention

1. Example

/* thread one runs in this function */
void *do work one(void *param)
{
    pthread mutex lock(&first mutex);
    pthread mutex lock(&second mutex);
    /** * Do some work */
    pthread mutex unlock(&second mutex);
    pthread mutex unlock(&first mutex);
    pthread exit(0);
}

/* thread two runs in this function */
void *do work two(void *param)
{
    pthread mutex lock(&second mutex);
    pthread mutex lock(&first mutex);
    /** * Do some work */
    pthread mutex unlock(&first mutex);
    pthread mutex unlock(&second mutex);
    pthread exit(0);
}

void transaction(Account from, Account to, double amount)
{
    mutex lock1, lock2;
    lock1 = get lock(from);
    lock2 = get lock(to);
    acquire(lock1);
    acquire(lock2);
    withdraw(from, amount);
    deposit(to, amount);
    release(lock2);
    release(lock1);
}

2. Deadlock Avoidance

3. Safe State

4. Basic Facts

5. Safe, Unsafe, Deadlock State

6. Avoidance algorithms

7. Resource-Allocation Graph


8. Algorithm

(1) Data Structures for the Banker’s Algorithm

(2) Safety Algorithm

20170518

(一) Deadlock Detection

(二) Detection Algorithm



(三) Recovery from Deadlock

1. Process Termination

2. Resource Preemption

(四) Memory-Management

  1. Base and Limit Registers

    • A pair of base and limit registers define the logical address space

    • CPU must check every memory access generated in user mode to be sure it is between base and limit for that user

    • Hardware Address Protection with Base and Limit Registers

  2. Address Binding

    • Programs on disk, ready to be brought into memory to execute form an input queue
      • Without support, must be loaded into address 0000
    • Inconvenient to have first user process physical address always at 0000
      • How can it not be?
    • Further, addresses represented in different ways at different stages of a program’s life
      • Source code addresses usually symbolic
      • Compiled code addresses bind to relocatable addresses
        • i.e. “14 bytes from beginning of this module”
      • Linker or loader will bind relocatable addresses to absolute addresses
        • i.e. 74014
      • Each binding maps one address space to another

  1. Logical vs. Physical Address Space

  2. Memory-Management Unit (MMU)

    • Hardware device that at run time maps virtual to physical address
    • Many methods possible, covered in the rest of this chapter
    • To start, consider simple scheme where the value in the relocation register is added to every address generated by a user process at the time it is sent to memory
      • Base register now called relocation register
      • MS-DOS on Intel 80x86 used 4 relocation registers
    • The user program deals with logical addresses; it never sees the real physical addresses
      • Execution-time binding occurs when reference is made to location in memory
      • Logical address bound to physical addresses

  3. Dynamic relocation

    • Using a relocation register

  4. Dynamic Linking

    • Static linking - system libraries and program code combined by the loader into the binary program image
    • Dynamic linking – linking postponed until execution time
    • Small piece of code, stub, used to locate the appropriate memory-resident library routine
    • Stub replaces itself with the address of the routine, and executes the routine
    • Operating system checks if routine is in processes’ memory address
      • If not in address space, add to address space
    • Dynamic linking is particularly useful for libraries
    • System also known as shared libraries
    • Consider applicability to patching system libraries
      • Versioning may be needed

  5. Swapping

    • A process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued execution
      • Total physical memory space of processes can exceed physical memory
    • Backing store – fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images
    • Roll out, roll in – swapping variant used for priority-based scheduling algorithms; lower-priority process is swapped out so higher-priority process can be loaded and executed
    • Major part of swap time is transfer time; total transfer time is directly proportional to the amount of memory swapped
    • System maintains a ready queue of ready-to-run processes which have memory images on disk
    • Does the swapped out process need to swap back in to same physical addresses?
      • Depends on address binding method
        • Plus consider pending I/O to / from process memory space
    • Modified versions of swapping are found on many systems (i.e., UNIX, Linux, and Windows)
      • Swapping normally disabled
      • Started if more than threshold amount of memory allocated
      • Disabled again once memory demand reduced below threshold

20170525

(一) Contiguous Allocation

(二) Dynamic Storage-Allocation Problem

(三) Fragmentation

(四) Segmentation

Segmentation Architecture

20170601

(一) Paging

(二) Address Translation Scheme



(三) Implementation of Page Table


(四) Effective Access Time

(五) Memory Protection

(六) Shared Pages

(七) Structure of the Page Table

Hierarchical Page Tables

Two-Level Page-Table Scheme

Three-level Paging Scheme

Hashed Page Tables

Inverted Page Table

20170608

(一) Background

(二) Virtual Address Space

(三) Demand Paging

1. Valid-Invalid Bit

2. Example

EAT = (1 – p) x 200 + p (8 milliseconds)
= (1 – p) x 200 + p x 8,000,000
= 200 + p x 7,999,800

3. Optimizations

(四) Page Fault

1. Aspects of Demand Paging

2. Instruction Restart

Performance of Demand Paging
  1. Trap to the operating system
  2. Save the user registers and process state
  3. Determine that the interrupt was a page fault
  4. Check that the page reference was legal and determine the location of the page on the disk
  5. Issue a read from the disk to a free frame:
    (1) Wait in a queue for this device until the read request is serviced
    (2) Wait for the device seek and/or latency time
    (3) Begin the transfer of the page to a free frame
  6. While waiting, allocate the CPU to some other user
  7. Receive an interrupt from the disk I/O subsystem (I/O completed)
  8. Save the registers and process state for the other user
  9. Determine that the interrupt was from the disk
  10. Correct the page table and other tables to show page is now in memory
  11. Wait for the CPU to be allocated to this process again
  12. Restore the user registers, process state, and new page table, and then resume the interrupted instruction

(五) Copy-on-Write

(六) Page Replacement

1. What Happens if There is no Free Frame?

2. Basic Page Replacement

  1. Find the location of the desired page on disk
  2. Find a free frame:
    a. If there is a free frame, use it
    b. If there is no free frame, use a page replacement algorithm to select a victim frame
    c. Write victim frame to disk if dirty
  3. Bring the desired page into the (newly) free frame; update the page and frame tables
  4. Continue the process by restarting the instruction that caused the trap

3. Page and Frame Replacement Algorithms

(1) First-In-First-Out (FIFO) Algorithm



(2) Optimal Algorithm

(3) Least Recently Used (LRU) Algorithm

(4) LRU Approximation Algorithms

(5) Counting Algorithms
(6) Page-Buffering Algorithms

20170615

(一) Allocation of Frames

1. Fixed Allocation

2. Priority Allocation

3. Global vs. Local Allocation

4. Non-Uniform Memory Access

5. Thrashing

6. Demand Paging and Thrashing

7. Working-Set Model


8. Page-Fault Frequency


(二) Memory-Mapped Files

(三) Other Considerations – Prepaging

(四) Other Issues