Priority scheduling

每一個process都有一個priority，system會從priority的開始優先處理。若一直有高priority的process要執行的話，則可能會造成low priority的process永遠不會被執行到，造成indefinite blocking or starvation。

Priority Scheduling可以是preemptive or non-preemptive。若是preemptive，則新到process若其priority比正在跑之process高則取代它執行；若是後者則放在ready queue中等待執行

indefinite blocking也可能發生在用LIFO(Last In First Out)的scheduling中

Solution:這可以用aging或者Dynamic Priority, Floating Priority來解決
/* aging: 系統每隔一段時間，將待在系統內時間很長，卻又未能完成工作的process，逐漸調高其priority，因此，在有限的時間內，其優先權可以升到最高，進而可取得資源完成工作 */


Reference:
[1]http://www.csie.ntnu.edu.tw/~swanky/os/chap4.htm

Race condition

在shared memory[1]溝通方式下，若未對共享變數提供任何互斥存取控制(or同步)機制，則執行的結果(共享變數之值)會依process執行次序不同而有所不同


解決Race condition有幾種方法，1)Disable Interrupt，2)Critical Section Design


1)Disable Interrupt：
Process在對共享變數進行存取之前，先Disable Interrupt(i.e. 發出system call請求OS執行)，如此可以確保Process在對其共享變數存取期間不受任何其他processes干擾(or preemption)。直到完成此敘述後才Enable Interrupt

優點：簡單
缺點：僅適用於uni-processor環境，但不適用於multi-processors下
/* 因為要disable all cpu的 interrupt非常耗費時間及資源，system performance很差 */

2)Critical Section Design：
對共享變數進行Lock control，process一旦取得對此共享變數之存取權，在其尚未完成工作時，Lock決不會打開直到完成，才會打開Lock讓其他process存取。

/* 點我延伸討論Critical Section Design */

Reference:
[1] shared memory：
一組process透過對share variables之存取，達到彼此溝通之目的。OS沒有提供額外支援(Global)，僅提供memory space而已，此種方式Programmer負擔重，必須確保共享變數之互斥存取機制(or同步)，以確保正確性。Race condition為shared memory下可能產生的問題之一，另外一個可能問題是Data Inconsistency，執行的結果不如預期。

[2] OS課本/教材

C語言 - 簡單小考題(1)

void main(void)
{

  int a=5, b=0, c=6;

  a=(a=b)&&(c=b);

  printf("a=%d, b=%d, c=%d \n",a,b,c);

}


最後答案是a=0,b=0,c=6



Ｑ：為什麼最後答案c不是＝0？？？

答案是因為＆＆在做怪。
&&前面如果是0的話就不會做後面的了，ex. A&&B, if A==0, B就會skip掉判斷

Note: OR (A||B) 也是一樣

Critical Section/Mutex/Semaphore

Critical section(臨界區間)指的是一個存取共用資源（例如：共用裝置或是共用記憶體）的程式片段，而這些共用資源又無法同時被多個執行緒存取的特性[1]

Critical section design必須要滿足三個特性：
1)Mutual exclusion
2)Progress
3)Bounded waiting


1)Mutual exclusion
同一時間點，絕不允許有多個(大於兩個)processes在各自的C.S.內活動，亦即當有一process在自己的C.S.內活動，其他想進入各別C.S.內的processes必須等待，直到該process離開C.S.

2)Progress
I：不想進入C.S.的process絕不能阻礙其他processes進入C.S. (i.e.絕不參與進入C.S.的決策過程)
II：決定哪個processes可以進入C.S.的決策時間是有限的(i.e. No Deadlock)

3)Bounded waiting
自process提出申請進入C.S.到其獲准進入C.S.的這段等待時間是有限的。/* 即n個process欲進入C.S.，則任何一process至多等待(n-1)次後，即可進入C.S */



multi-tasking system中要解決Critical section問題就有Mutex以及Semaphore兩種方法
1)Mutex
Mutex基本就像是把key，當有process想要access一個共用的resource時會先去取得進入這個resource的"Key"，當這個key被前一個process給hold住的時候就只能wait

2)Semaphore
雷同Mutex，但是把它擴大為可以同時有N個人擁有key並能access共用的resource

Reference:

[1]http://zh.wikipedia.org/wiki/%E8%87%A8%E7%95%8C%E5%8D%80%E6%AE%B5

Interrupt and Exception

Interrupt 和 exception 是兩種改變系統執行程式順序的方式，分別透過不同的元件觸發。當 interrupt 或 exception 被觸發時，系統會經由查表找到相對應的處理程式（ ISR: Interrupt Service Routine，或稱 interrupt handler ），並中斷原本在執行的程式，讓 CPU 執行 ISR 的內容，之後才再轉回原來的程式中。這是多工（ multi-tasking ）環境中常常用到的技術。

在此， interrupt 指的是由硬體發出的中斷訊號，而 exception 指的是由軟體或系統所產生的中斷訊號。


Exception 則依照發生的場合可以分為兩種類型： 程式執行錯誤或例外事件，前者是發生在程式執行錯誤時，如被除數為零、 overflow 等；後者則像是 system call 等作業系統所提供的服務。
 
 
Reference:
[1] http://opencsl.openfoundry.org/Lab06_interrupt_exception.rst.html
 
--
/* Note: 去面試考到這個，但太久沒看OS全部都忘光，好慘 - -*/

DHCP Snooping

DHCP
DHCP (Dynamic Host Configuration Protocol)
是用來自動取得IP的一種通訊協定，定義在RFC2131 & RFC2132
最主要有兩個角色：Clinet以及Server。
Clinet就是要需要取得IP的裝置，Server則是配有很多IP Pool可以assign
Switch上則多「Relay」的角色(意即對接host端Switch扮演著類似server；對server則扮演host)

常見跟DHCP有關的功能
DHCP Snooping
switch在經過它的DHCP packet中偷偷去紀錄一些資訊，主要是為了security issue.
主要設定會有設定所謂的Trust port，這通常是接到DHCP server
透過Snooping可以建立binding table，也可以說是白名單，這原本是用於IP Source Guard，當有packet進來的時候會去check packet的一些欄位資訊看是不是合法的；如果不是合法的就會被drop掉。這可以配合ARP INSPECTION來使用，當DHCP完成 host要發出arp時也會確認binding table來確認是不是合法的user

/* 註記 */
binding table除了自己learn到外也可以用自己設定的，所謂的static binding，自己建立白名單
所以當default的config，只開arp inspection的話，當有arp packet進來，查白名單裡面是空白的，那就全部進去filter名單，全部被drop，那網路就不通了


DHCP Relay
剛提到的DHCP Snooping只做到偷看，不影響原本的行為；但今天如果DHCP Server剛好不在同一個domain/vlan的話該怎麼辦?
switch上有這個relay的功能，可以代替
OPTION 82

DHCP Relay可以分成Global Relay(Smart-Relay)以及VLAN Relay

DHCP Relay

Global Relay透過config設定可以把不同vlan的dhcp packet都forward相同的vlan上的「同一台」dhcp server；
VLAN Relay則是透過設定，可以把不同vlan的dhcp packet forward「相同」vlan上的「不同」dhcp server去

Global and VLAN Relay

DHCP Relay-Broadcast:
這不是standard有的行為。是個功能的開關。通常會有DHCP Relay都是access switch(Layer 2)為主，那Relay就是switch幫忙把原本client的DHCP broadcast給包成unicast往已知的server丟。那原本DHCP Broadcast的packet呢? 要繼續做broadcast嘛? 所以才會有這個小功能。但這樣也會有缺點就是說當原本 broadcast VLAN上有多個DHCP server的時候，client就會收到多台server給他的DHCP offer，至於client挑選哪台DHCP server回的packet就是網卡來決定。與switch就無關


DHCP Database
DHCP snooping主要是為了建立binding table，建立binding table有手動(static binding)以及dynamic learn(開DHCP Snooping，等DHCP完成後自動建立)，如果今天是因為自動建立的話如果重開機的話是不是就要重新DHCP一次create binding table很麻煩?  dynamic的binding table有沒有辦法做備份!?   DHCP Database就是為了解決這個問題而產生。使用TFTP的方式將binding table做備份在外部的TFTP server上以及support restore的功能，在下次重開機的時候可以快速把binding table給restore回去


DHCP-VLAN
DHCP VLAN OVERWRITE

字串處理

被這個卡了半天，實在是太可恥了。趕快來寫下心得筆記

字串處理有幾個主要的方式。分別討論如下：

1)字串長度
2)字串複製
3)字串串連

1)字串長度
size_t strlen(const char*); /* size_t 為unsigned integer. but will be unsigned long in 64bit system */

/* sample code */

void main(void)
{
size_t string_len = 0;
char *string = "AlubaGood";

string_len = strlen(string);
printf("Lengtg of input string = %u \n\r",string_len);
}

如上sample code, 我們會得到string_len = 9


2)字串複製
如果要進行字串複製，可以使用strcpy()函式，若要複製字串中若干字元內容，則可以使用strncpy()：
char* strcpy(char*, const char*);
char* strncpy(char*, const char*, size_t);

/* sample code */
void main(void)
{
char *string_1="abcdefg";
char *string_2="hijklmn";

strcpy(string_1,string_2);
printf("After copy, string_1=%s, string_2=%s \n\r",string_1,string_2);
}

上面的結果會show出 After copy , string_1=hijklmn, string_2=hijklmn
strcpy()是會把source string整個「蓋掉」destinaion string. 如果只是想要copy「某些長度」的string的話則要用strncpy()

上面的code如果把strcpy()換成strncpy(string_1,string_2,3); 則會show出 After copy, string_1=hij, string_2=hijklmn


3)字串串連
如果今天要做的是把兩個字串「相連/相加」在一起的話則是要用strcat(), 相連特定長度的話用strncat()

/* sample code */
void main(void)
{
char *string_1="abcdefg";
char *string_2="hijklmn";

strcat(string_1,string_2);
printf("After connect, string_1=%s, string_2=%s \n\r",string_1,string_2);
}
上面的結果會show出 After copy , string_1=abcdefghijklmn, string_2=hijklmn

如果把strcat()換成strncat(string_1,string_2,3); 則上面結果會變成 After copy , string_1=abcdefghij, string_2=hijklmn


Reference:
http://caterpillar.onlyfun.net/Gossip/CGossip/StringLengthCopyCat.html
http://www.cplusplus.com/reference/clibrary/cstring/strncat/

Multicast (IGMP Snooping)

Multicast, 有別於broadcast(一送全部收)及unicast(一送一個人收).只讓特定的user可以接收到packet，好比一送多個人收。其中主要的protocol為IGMP

IGMP
IGMP, Internet Group Management Protocol. based on network layer的feature。是用來支援主機和路由器之間的Multicast封包的管理協定


IGMP是指router在layer3進行Multicast。但是實際上在layer2時是進行Broadcast。如果switch有支援
IGMP Snooping的話，就會在layer2建立和維護MAC 的Multicast地址表，以達到在layer2也進行Mutlicast，這樣最主要就是為了節省封包流量。


也因為是network layer的feature，所以他的multicast address會帶有特定IP的information. 其中class D(224.0.0.0~239.255.255.255)是用來做multicast group的multicast address

而IGMP目前有三種版本 v1,v2,v3 其中有些許的差別，分別define於RFC 1112, RFC 2236 and RFC 3376.
IGMP-v1:只有query和report的封包,要等到timeout才會leave
IGMP-v2:加入了leave的packet
IGMP-v3:加入了source filter的功能，host端可以決定要收到來自哪些source來的IGMP packet


在Layer 2 switch上跟IGMP有關的功能主要是IGMP Snooping. snooping可以當作是偷看偷學的意思。這feature最主要的用意就是要減少packet的流量。
比方說port 3送了一個Join multicast 224.0.0.1的封包到switch，這時候switch就偷偷地學起來，等到從port 5收到multicast 224.0.0.1的封包時，就知道只要傳給port 3就好了，不用傳給別的port，達到減少流量的優點。

此外，每個VLAN都可以有自己的multicast group，IGMP snooping最多可以support到16個VLAN
所以VLAN 100有multicast group 224.0.0.100
VLAN 200也可以有multicast group 224.0.0.100


在L2 switch上除了減少流量外還可以做到其他setting來做控管。可分成per system及per port的設定，包含了
1)group limit以及max group number /* per port */
2)igmp snooping filtering /* per port */
3)Host Timeout /* per system */
4)replace 802.1p Priority tag /* per system */
5)Unknown Multicast Frame drop or flooding /* per system */
6)reserved multicast group drop of flooding /* per system */
7)report-proxy /* per system */
分簡述如下：

1)group limit abd max group number:
限制per port可以加入幾個multicast group. if 超過設定的group number，則用throttling來設定，可以設定當超過的時候是要把新的group給drop掉還是replace原本最舊的group

2)IGMP Snooping Filtering:
我們可以設定per port可以允許加入的multicast group，如果multicast group不屬於IGMP Filtering Profile，就不會進到此port

3)Host timeout
當開snooping時候可以決定per system多久沒收到report packet的時候就把這個port從那個multicast group給remove. default是260 second

4)replace 802.1p Priority tag
可以決定 pass through switch的IGMP的control packet其中的priority tag被換成多少(0~7 可自行設定)

5)Unknown Multicast Frame drop or flooding
對於這台switch沒有learning到的multicast group pakcet是會被drop還是flooding

6)Reserved Mulitcast Group是指224.0.0.0 ~ 224.0.0.255這段multicast address，這是local network所使用的multicast group
可以設定這個multicast group的packet是會被drop還是flooding

ex. 224.0.0.251, MAC address of 01:00:5E:00:00:FB for IPv4; FF02::FB for IPv6. multicast DNS
224.0.0.252, MAC address of 01-00-5E-00-00-FC for IPv4; FF02::1:3 for IPv6, Link Local Multicast Name Resolution (LLMNR), Windows vista, windows server 2008, windows 7才有

7)report-proxy
用於簡化packet的流量。當有多條IGMP join/report的packet時可以把它整合成一個packet送給multicast router

multicast另外個重要應用為跨VLAN的功能，這主要是用在MoD(Media-on-Demand)之類的應用上。可稱為Multicast VLAN or Multicast VLAN Registration(MVR)

MVR主要會針對IGMP join與leave封包進行處理, IGMP report的封包則是交給IGMP snooping. 這部分可以再另外開個topic來討論...

Reference:
[1] http://guiderworld.blogspot.com/2009/03/multicastigmp.html
[2] http://tw.myblog.yahoo.com/hughes-blog/article?mid=64&prev=66&next=61

C語言- 一行搞定判斷是不是2的n次方

if_power_of_2(n) (n != 0 && ((n & (n -1)) == 0))

Reference: http://nano-chicken.blogspot.com/2011/03/in-c.html

C語言- 三行搞定swap

剛看到的一段code，真的很神!! 快來筆記一下
用XOR作swap;

void swap(int *x, int *y) {
    if (x != y) {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}

Reference:
[1] http://nano-chicken.blogspot.com/2011/03/in-c.html
[2] http://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B

C語言- structure pointer

struct Data
{
int a;
int b;
char* name;
}Mydata;

struct Data *ptr = NULL;

/* assign pointer to structure parameter Mydata */
ptr = &Mydata;


如果要存取structure parameter a;b;*name, 可以用 ptr->a; ptr->b;ptr->name

C語言- dynamic memory allocation

void *malloc(size_t size);
http://www.cplusplus.com/reference/clibrary/cstdlib/malloc/

void free(void *ptr);
http://www.cplusplus.com/reference/clibrary/cstdlib/free/

透過malloc()所分配出來的空間必須由使用者呼叫free()才能歸還給系統。初學者常犯的錯誤之一,就是忘了用free()歸還空間,這會造成程式佔用太多記憶體,此現象稱為memory leakage。相反的,如果空間已用free()歸還了,卻還試著去使用那塊記憶體,則會發生Segmentation Fault (core dumped)的錯誤。


Reference:
http://programming.im.ncnu.edu.tw/Chapter13.htm

C語言- const 用法

const為constant的縮寫，用來宣告變數並設定初值後「不能」再被修改。
ex. const double = 3.14;

const在指標(pointer)使用中可以表明指標指到data是const or 指標本身是const or 兩者都是

[1] char *p = "Qoo";  /* non-const pointer, non-const data */
[2] const char *p = "Qoo"; /* non-const pointer, const data */
[3] char* const p = "Qoo"; /* const pointer, non-const data */
[4] const char* const p = "Qoo" /* const pointer, const data */

關鍵在於：*與const的前後關係！當const出現在*的左邊(const *)，則表示pointer指到的data為常數;反之如果const出現在*的右邊(* const)，則表示指標本身是常數

所以在[2]
*p = 10;       /*錯誤*/
*(p + 2) = 1;  /*錯誤*/

在[3]
*p = 2;          /*可以*/
*(p+1) = 10;     /*可以*/
p++;             /*不可以*/

事實上，在The C++ Programming Language中有提到一個簡單的要訣：由右向左讀!!

所以
[2] p is a pointer that point to char, which is const
[3] p is a constant pointer point to char
[4] p is a constant pointer point to char which is const

用const是其中一種固定變數值的方法，但更常用的是用#define。一來可以讓程式碼簡潔，二來可以配合macro，用一個簡單的指令替代多個步驟

References:
[1] Effective C++ clause 21.
[2] http://www.wretch.cc/blog/cwz0205/15360838