Welcome to shouzo's blog!

• 20170324 [學習筆記] Linux 系統程式 (4)

  2017-03-24

  Linux  作業系統  程式設計

  Linux  作業系統  程式設計
  • 一、作業系統
    • Multithread Architecture
    • 一、Multicore Programming
    • 二、Concurrency vs Parallelism
      • 1. Concurrency
      • 2. Parallelism
      • 3. Concurrency vs Parallelism
      • 4. 相關整理
    • 三、Single and Multithreaded Processes
    • 四、User Threads and Kernel Threads
    • 五、Multithreading Models
    • 六、Pthreads
      • pthread.h
        • pthread_create()
        • pthread_exit()
        • pthread_join()
    • 課程作業

  一、作業系統

  • 課程簡報
    • Chapter 4: Mutithread Programming
    • Linux_programming_pthread
  • 參考資料
    • Toward Concurrency
    • Amdahl’s Law

  Multithread Architecture

  

  • Responsiveness – may allow continued execution if part of process is blocked, especially important for user interfaces.
  • Resource Sharing – threads share resources of process, easier than shared memory or message passing.
  • Economy – cheaper than process creation, thread switching lower overhead than context switching.
  • Scalability – process can take advantage of multiprocessor architectures.

  一、Multicore Programming

  • Multicore or multiprocessor systems putting pressure on programmers, challenges include:
    • Dividing activities
    • Balance
    • Data splitting
    • Data dependency
    • Testing and debugging
  • Parallelism implies a system can perform more than one task simultaneously.
  • Concurrency supports more than one task making progress.
    • Single processor / core, scheduler providing concurrency
  • Types of parallelism
    • Data parallelism – distributes subsets of the same data across multiple cores, same operation on each.
    • Task parallelism – distributing threads across cores, each thread performing unique operation.
  • As # of threads grows, so does architectural support for threading.
    • CPUs have cores as well as hardware threads.
    • Consider Oracle SPARC T4 with 8 cores, and 8 hardware threads per core.

  二、Concurrency vs Parallelism

  • 引用資料：Toward Concurrency
  • Concurrency is not Parallelism, by Rob Pike
    • 投影片
    • 錄影
    • 後續 stackoverflow 討論
  • Concurrency 對軟體設計的影響
    • 想要充分使用到 CPU 的資源
    • 程式越來越有機會造成 CPU-bound。雖然主要還是 IO-bound 等，但如果 CPU 時脈無法增加，而其他存取方式速度變快，最後會發生 CPU-bound
    • 軟體效能優化將會越來越重要
    • 程式語言必須好好處理 concurrency

  1. Concurrency

  • 是指程式架構，將程式拆開成多個可獨立運作的工作。eg：drivers，都可以獨立運作，但不需要平行化。
    • 拆開多個的工作不一定要同時運行
    • 多個工作在單核心 CPU 上運行

  2. Parallelism

  • 是指程式執行，同時執行多個程式。Concurrency 可能會用到 parallelism，但不一定要用 parallelism 才能實現 concurrency。eg：Vector dot product
    • 程式會同時執行 (例如：分支後，同時執行，再收集結果)
    • 一個工作在多核心 CPU 上運行

  3. Concurrency vs Parallelism

  • Rob Pike 用地鼠燒書做例子:

  • 如果今天增加多一只地鼠，一個推車或多一個焚燒盧，這樣有機會作到更好的資源使用率，但我們不能保證兩只或更多地鼠會同時進行 (可能只有有限的火爐)。在單核系統中只能允許一次進行一次的燒書工作，那樣就沒有效率了。 以 Concurrency 的方式去作業，能夠以不同的解構方式去進行，可以是三個地鼠分別負責一部分的工作 (decomposition) 其中也可以 Parallelism: 或

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

  • 拆開多個的工作不一定要同時運行
  • 多個工作在單核心 CPU 上運行

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

  • 程式會同時執行 (例如：fork 後，同時執行，再收集結果 [join])
  • 一個工作在多核心 CPU 上運行

  4. 相關整理

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

  (1) Concurrent (並行)

  • 工作可拆分成「獨立執行」的部份，這樣「可以」讓很多事情一起做，但是「不一定」要真的同時做。下方情境：
    • 展示具有並行性，但不去同時執行。
    • 並行性是種「架構程式」的概念。寫下一段程式之前，思考問題架構時就決定好的。

  (2) Parallel (平行)

  • 把規劃好、能夠並行的程式，分配給不同執行緒，並讓他們同時執行。
    • 「平行」是一種選擇。

  三、Single and Multithreaded Processes

  

  • Amdahl’s Law
    • 針對系統裡面某一個特定的元件予以最佳化，對於整體系統有多少的效能改變。
    • 分成兩部份
      • 有辦法改進的部份
      • 沒有辦法改進的部份
    • 因為有無法改進的部份，所以不可能無限提升系統的某一個特定部分的效率。

  四、User Threads and Kernel Threads

  • User threads
    • Management done by user-level threads library.
  • Kernel threads
    • Supported by the Kernel.

  五、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
     • Allows many user level threads to be mapped to many kernel threads.
     • Allows the operating system to create a sufficient number of kernel threads.
     • Solaris prior to version 9.
     • Example：Windows NT/2000 with the ThreadFiber package
  4. Two-level
     • Similar to M:M, except that it allows a user thread to be bound to kernel thread.
     • Examples：IRIX、HP-UX、Tru64 UNIX、Solaris 8 and earlier

  六、Pthreads

  • May be provided either as user-level or kernel-level.
  • A POSIX standard (IEEE 1003.1c) API for thread creation and synchronization.
  • Specification, not implementation.
  • API specifies behavior of the thread library, implementation is up to development of the library.
  • Common in UNIX operating systems (Solaris, Linux, Mac OS X).

  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_t *thread：thread 的識別字
  • pthread_attr_t *attr：thread 的屬性，設定為 NULL 表示使用預設值
  • void *(*start_routine)(void*)：thread 要執行的 function
  • void *arg：傳遞給 thread 的參數

  pthread_exit()

  void pthread_exit(void *retval);
  

  • void *retval：thread 結束時回傳的變數

  pthread_join()

  int pthread_join(pthread_t th, void **thread_return);
  

  • pthread_t th：thread 識別字
  • void **thread_return：接收 pthread_exit 傳回的變數

  課程作業

  • 從 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);
  }
  
  

  • 執行結果
  Read All

  ---

• 20170323 [學習筆記] 人工智慧 (4)

  2017-03-23

  人工智慧

  人工智慧
  • 用程式實現歸屬函數的判定

  用程式實現歸屬函數的判定

  • 請分別輸入 NB、NM、NS、PS、PM、PB 的數值，再輸入欲判定的值，輸出其 歸屬函數(membership function, mf) 的值。
    1. 直線 mf
    2. S函數 mf

  #include <stdlib.h>
  #include <stdio.h>
  
  int main(void) {
      int i = 0, j = 0;  // Set loop
      float mf[7], tmp = .0, input = .0, sa = .0, ua = .0, ub = .0;
      char name[7][3] = {"NB", "NM", "NS", "ZR", "PS", "PM", "PB"};
  
      /* Key the value of name */
      printf("Please define NS、NM、NB value (smaller than 0)\n");
      for (i = 0; i < 3; i++) {
          scanf("%f", &mf[i]);
      }
        
      printf("Please define PS、PM、PB value (bigger than 0)\n");
      for (i = 3; i < 6; i++) {
          scanf("%f", &mf[i]);
      }
  
      mf[6] = 0;  // Set the ZR value
  
  
      /* Sort the numbers */
      for (i = 0; i < 7; i++) {
          for (j = 0; j < 7; j++) {
              if ((mf[j] > mf[i])) {
                  tmp = mf[i];
                  mf[i] = mf[j];
                  mf[j] = tmp;
              }
         }
      }
  
  
      /* The entry */
      while(1) {
          /* Key the value of x */
          printf("\n\nPlease key in the value of 'Input'\n");
          printf("Input = ");
          scanf("%f", &input);
  
  
          /* Calculate the linear μ */
          printf("\n\n****The membership function****\n");
          for (i = 0; i < 7; i++) {
              // input = mf
              if (((input == mf[i]))) { 
                  printf("μ[%s] = %.f\n", name[i], (mf[i] / mf[i]));
                  break;
              }
  
              // input bigger than the max's mf
              else if ((input > mf[6])) { 
                  printf("μ[%s] = %.f\n", name[6], (mf[6] / mf[6]));
                  break;
              }
  
              // input smaller than the min's mf
              else if ((input < mf[0])) { 
                  printf("μ[%s] = %.f\n", name[0], (mf[0] / mf[0]));
                  break;
              }
  
              // Calculate...
              else if ((input > mf[i]) && (input < mf[i+1])) {
                  /* linear area */
                  printf("\n****The linear****\n");
                  ua = (1 - (mf[i] - input) / (mf[i] - mf[i+1]));
                  ub = (1 - (input - mf[i+1]) / (mf[i] - mf[i+1])); 
                  printf("μ[%s] = %.3f\n", name[i], ua);
                  printf("μ[%s] = %.3f\n", name[i+1], ub);
                  
                  /* non-linear area */
                  printf("\n****The non-linear (S-function)****\n");
                  if (input < ((mf[i] + mf[i+1]) / 2)) {
                      sa = (((input - mf[i]) / (mf[i+1] - mf[i])));
                      ua = 1 - (2 * sa * sa);
                      ub = 1 - ua;
                      printf("μ[%s] = %.3f\n", name[i], ua);
                      printf("μ[%s] = %.3f\n", name[i+1], ub);
                  }
  
                  else if ((input >= ((mf[i] + mf[i+1]) / 2)) && (input < mf[i+1])) {
                      sa = (((input - mf[i+1]) / (mf[i+1] - mf[i])));
                      ua = (2 * sa * sa);
                      ub = 1 - ua;
                      printf("μ[%s] = %.3f\n", name[i], ua);
                      printf("μ[%s] = %.3f\n", name[i+1], ub);
                  }
                  break;
              }
          }
      }
      return 0;
  }
  

  • 執行結果
  Read All

  ---

• 20170322 [學習筆記] 關於用 Pthread 取質數的問題

  2017-03-22

  Linux  作業系統  程式設計

  Linux  作業系統  程式設計
  • 前言
  • 一、輸出有問題
    • (一) 原本的程式
    • (二) 做個測試，來看看是怎麼一回事

  前言

  從 1 - 100 之間取出所有的質數，利用 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 100
  
  // 找出 1 - 100 的所有質數
  
  static double getDoubleTime();
  void *thread_function(void *arg);
  pthread_mutex_t work_mutex;
  
  
  int main(void) {
  	int res;
  	pthread_t a_thread[NUM_THREADS];
  	void *thread_result;
  	int lots_of_threads;
  	
  	// 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");
          	}
      }	
  
  	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;   // Set the loop
      int count = 0;      // Set the counter
      int result = 0;     // result
  
  	printf("\n\nI'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) { 
              result = i;
              printf("%d\t", result);
          }
      }
  
      // 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);
  }
  
  

  • [執行結果]

  (二) 做個測試，來看看是怎麼一回事

  • 目前的假設

    當ㄧ個 thread 還沒 printf 完它所負責範圍的質數時，就被切換到另一個 thread 裡面執行。

  • 參考資料
    • Using mutex for pthread results in random answer

  

  • 驗證假設
    • 為了驗證假設的正確性，我在 printf 質數時後面再補上該質數所對應的 thread number，作法如下：

     /* 前面省略 */
     
     /* 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) { 
              result = i;
              printf("%d-[%d]\t", result, my_num);
          }
      }
      
      /* 後面省略 */
  

  • [執行結果]

    看來前面的假設是正確的，但是我們該如何避免這種情形？

  Read All

  ---

• 20170317 [學習筆記] Vim 常用技巧

  2017-03-17

  程式設計

  Vim  程式設計
  • 前言
  • 一、常用功能

  前言

  這一陣子開始使用 Vim 作為主要的文字編輯器，但是在使用上遇到了一些問題 (主要原因是還不習慣 Vim 的操作方式)，因此整理了一些常用的技巧。

  一、常用功能

  • 引用資料
    • Vim小技巧

  1. 刪除一行 - dd

  2. 進入編輯模式 - i

  3. 進入VISUAL模式 - v

  4. 進入VISUAL BLOCK模式 - ctrl(按鍵) + v

  5. 寫入(儲存) - :w

  6. 離開 - :q

  7. 不儲存強制離開 - :q!

  8. paste模式，直接貼上文字時格式不會跑掉 - :set paste

  9. 顯示行數 - :set nu

  10. 設定一個tab等於四個空白長度 - :set tabstop=4

  11. 設定以後，使用tab鍵時會用空白取代(由tabstop決定) - :set expandtab

  12. 消除Highlight - :noh

  13. 範圍縮排(3到5行向右縮排，向左縮排用<) - :3,5>

  14. 將tab轉換成space - :retab

  15. 將檔案編碼轉成utf8 - :set fileencoding=utf8

  16. 另存新檔 - :w myfilename

  17. 開啟檔案 - :e filename

  18. 自動對齊 - ==

  19. 移動到該行最前端 - ^

  20. 移動到該行最末端 - $

  21. 移動到下一個單字的第一個字元 - w

  22. 移動到前一個單字的第一個字元 - b

  23. 移動到下一個單字的最後一個字元 - e

  24. 移動到下一個單字的最後一個字元(無視符號) - E

  25. 全選(gg為游標移動到最上方，v為切換成選擇模式，G是游標移動到最下方) - ggvG

  26. 游標移動到特定行數(移動到第三行) - 3G

  27. 複製反白的區塊(需要在VISUAL模式) - y

  28. 剪下反白的區塊(需要在VISUAL模式) - d

  29. 複製游標所在的那行(需要在VISUAL模式) - shift(按鍵) + y

  30. 貼上 - p

  31. 回復 - u

  32. 自動完成 (需要在編輯模式) - ctrl(按鍵) + p

  33. 搜尋字串 - /<字串>：向下找、?<字串>：向上找

  Read All

  ---

• 20170317 [學習筆記] Linux 系統程式 (3)

  2017-03-17

  Linux  作業系統  程式設計

  Linux  作業系統  程式設計
  • 一、作業系統
    • Basic Concepts
    • CPU Scheduler
    • Dispatcher
    • Scheduling Algorithm Optimization Criteria
    • 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

  一、作業系統

  • 課程簡報
    • Chapter 5: Process Scheduling
  • 參考資料
    • Preemptive Process Scheduling 的觀念
    • 各種 CPU 排程演算法之探討
    • 行程排程演算法
    • Operating System Scheduling algorithms

  Basic Concepts

  • Maximum CPU utilization obtained with multiprogramming.
  • CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait.
  • CPU burst followed by I/O burst.
  • CPU burst distribution is of main concern.

  CPU Scheduler

  • Short-term scheduler selects from among the processes in ready queue, and allocates the CPU to one of them.
    • Queue may be ordered in various ways.
  • CPU scheduling decisions may take place when a process:
    1. Switches from running to waiting state
    2. Switches from running to ready state
    3. Switches from waiting to ready
    4. Terminates
  • Scheduling under 1 and 4 is nonpreemptive.
  • All other scheduling is preemptive.
    • Consider access to shared data.
    • Consider preemption while in kernel mode.
    • Consider interrupts occurring during crucial OS activities.

  Dispatcher

  • Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves：
    1. switching context
    2. switching to user mode
    3. jumping to the proper location in the user program to restart that program
  • Dispatch latency：time it takes for the dispatcher to stop one process and start another running.

  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).

  • Length of Next CPU Burst
    • Determining
    • Prediction

  Scheduling Algorithm

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

  

  ---

  

  • Convoy effect：很多短時間的 process，都在等一個 長時間的 process 時，所產生的效應 (因為等待時間很長)。

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

  • Associate with each process the length of its next CPU burst.
    • Use these lengths to schedule the process with the shortest time.
  • SJF is optimal – gives minimum average waiting time for a given set of processes.
    • The difficulty is knowing the length of the next CPU request.
    • Could ask the user.

  

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

  • A priority number (integer) is associated with each process.
  • The CPU is allocated to the process with the highest priority (smallest integer » highest priority).
    • Preemptive
    • Nonpreemptive
  • SJF is priority scheduling where priority is the inverse of predicted next CPU burst time.
  • Problem：Starvation – low priority processes may never execute.
  • Solution：Aging – as time progresses increase the priority of the process.

  

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

  • Each process gets a small unit of CPU time (time quantum q), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.
  • If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units.
  • Timer interrupts every quantum to schedule next process.
  • Performance.
    • q large » FIFO.
    • q small » q must be large with respect to context switch, otherwise overhead is too high.

  

  1. Time Quantum and Context Switch Time

  

  2. Turnaround Time Varies With The Time Quantum

  

  (五) Multilevel

  1. Queue

  • Ready queue is partitioned into separate queues, eg:
    • foreground (interactive)
    • background (batch)
  • Process permanently in a given queue. Each queue has its own scheduling algorithm:
    • foreground – RR
    • background – FCFS
  • Scheduling must be done between the queues:
    • Fixed priority scheduling; (i.e., serve all from foreground then from background). Possibility of starvation.
    • Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes; i.e., 80% to foreground in RR.
    • 20% to background in FCFS.

  

  2. Feedback Queue

  • A process can move between the various queues; aging can be implemented this way.
  • Multilevel-feedback-queue scheduler. defined by the following parameters:
    • number of queues.
    • scheduling algorithms for each queue.
    • method used to determine when to upgrade a process.
    • method used to determine when to demote a process.
    • method used to determine which queue a process will enter when that process needs service.

  

  • 課程作業
  Read All

  ---