# 資訊創意研究社-中等程度的 C
共六題，加油喔>_<
測驗期間可以上網
不得使用編譯器查看輸出
本次考試主要範圍為 程式設計和**少量的**作業系統和計算機組織
C99 規格書關鍵字為 C99 spec
完整好讀版請見Hackmd
https://hackmd.io/s/ByBMNrT0G
google表單填寫網址
https://goo.gl/forms/xYXQFiVqZfwSLPCq2
---
# 題目 1
C 語言規格中，明確聲明 char 預設是 signed (有號) 抑或 unsigned (無號)。
**是編譯器實作相依**，請補完以下程式碼，在執行時期判斷 char 在這個編譯器中是否為有號。
:::info
注意:作答區不得出現 ? , ; 等字元
:::
```clike=
#include <stdbool.h>
#include <stdio.h>
int main() {
bool is_char_signed = (char) ________;
if (is_char_signed)
puts("char is signed.");
else
puts("char is unsigned.");
return 0;
}
```
## 底線部份應填入什麼？
Ans：___________________________
---
# 題目 2
以下程式碼可將第n個bit清除(unset,也就是設定為0)，請補完底線部份的程式碼。
:::info
注意:作答區不得出現 ? , ; 等字元
:::
```clike=
#include <stdint.h>
uint32_t unset(uint32_t in, int n) {
return ________;
}
```
## 底線部份應填入什麼？
Ans：___________________________
---
# 題目 3
Cache 是為了加快電腦整體執行速度而發展出來的配備，存取速度遠大於 memory 接近 CPU (但還是慢一些)，所有 CPU 要讀取資料時都會先去 Cache 找，找不到的話再去 memory 找，如果在 memory 找到後則會先更新 Cache 的資料再讓 CPU 從 Cache 讀取。而 Cache 在從 memory 讀取資料時因為 hardware prefetch 中 STR 的機制一次讀取時都會從讀取的記憶體位置開始讀取一整個 cache line size 的資料。
接下來這題測驗你分析 C 程式中 Cache 行為的能力，假設以下硬體條件
* sizeof(int) == 4
* 機器有 4KB 的 Cache，每個 cache line size 為 16 byte
(放置時會依序置在 cache 中，放滿時就從第一筆開始重新擺放)
* 在迴圈中程式 cache 只對 Main memory 中的 data 存取， loop counter 和 sum 都放在 register 中
* array_t 陣列起始於 memory 地址 0x0800 0000
* cache 初始為空
對於 N = 64 和 N = 60 的情況如下表，填入他們的 cache miss rate
| function | N = 64 | N = 60 |
| -------- | -------- | -------- |
| sumA | **P1** | **P2** |
| sumB | **P3** | **P4** |
| sumC | **P5** | **P6** |
```clike=
typedef int array_t[N][N];
int sumA(array_t a) {
int i, j;
int sum = 0;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
sum += a[i][j];
return sum;
}
int sumB(array_t a) {
int i, j;
int sum = 0;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
sum += a[j][i];
return sum;
}
int sumC(array_t a) {
int i, j;
int sum = 0;
for (i = 0; i < N; i+=2)
for (j = 0; j < N; j+=2)
sum += (a[j][i] + a[j][i+1] + a[j+1][i] + a[j+1][i+1])
}
```
下圖為CPU 到 Cache 的路線圖
## P1 = ?
* `(A)` 0%
* `(B)` 25%
* `(C)` 50%
* `(D)` 75%
* `(E)` 100%
## P2 = ?
* `(A)` 0%
* `(B)` 25%
* `(C)` 50%
* `(D)` 75%
* `(E)` 100%
## P3 = ?
* `(A)` 0%
* `(B)` 25%
* `(C)` 50%
* `(D)` 75%
* `(E)` 100%
*
## P4 = ?
* `(A)` 0%
* `(B)` 25%
* `(C)` 50%
* `(D)` 75%
* `(E)` 100%
## P5 = ?
* `(A)` 0%
* `(B)` 25%
* `(C)` 50%
* `(D)` 75%
* `(E)` 100%
## P6 = ?
* `(A)` 0%
* `(B)` 25%
* `(C)` 50%
* `(D)` 75%
* `(E)` 100%
---
# 題目 4
在多執行序的程式中，常常會見到需要同時對同一個檔案做操作的情形，檔案可以同時讀取，但是檔案沒有辦法同時寫入，這個時候通常這個檔案會被放到被特別劃分出來的區域中，這就是臨界區間(critical section)，而當你要對這個檔案做寫入的話，就必須進入這個 critical section 之中才行。
critical section 必須滿足三個要求：
* **互斥**：若有 Process 在臨界區間中，則其他的 Process 不行在臨界區間中執行。
* **進行**：如果沒有 Process 在 critical section 之中，同時有其他的 Process 想要進入 critical section ，只有那些不在 remainder section 之中的 Process 才行決定下一個能進入 critical section 的 ｐrocess 是誰。
* **限制性等待**：在一個 Process 已經要求進入 critical section 之中，而此要求尚未被答應之前，允許其他的 Process 進入的 critical section 次數有限制。
而用軟體實作 critical section 的方法比較常見的有兩種，分別是 semaphore 和 mutex ，semaphore 是比較早期的作法，所以有許多問題，現今多改用 mutex ，而 mutex 簡單來說就像是一把鑰匙，一個人拿了才可進入對應房間，出來的時候把鑰匙交給其他人。
{%youtube 9lAuS6jsDgE%}
考慮以下 C 程式:
```clike=
#include <pthread.h>
typedef struct node {
int val;
struct node *link;
pthread_mutex_t lock;
} node_t;
node_t ListHead = { .val = 0 };
node_t *node_delete(int val) {
node_t *prev, *current;
prev = &ListHead;
pthread_mutex_lock(&prev->lock);
while ((current = prev->link)) {
pthread_mutex_lock(¤t->lock);
if (current->val == val) {
prev->link = current->link;
current->link = NULL;
return current;
}
pthread_mutex_unlock(&prev->lock);
prev = current;
}
pthread_mutex_unlock(&prev->lock);
return NULL;
}
```
這是個 mutex lock 實作目標在多執行緒環境運作的 singly-linked list ,我們忽略新增節點的函式,並且聚焦在 delete 函式,後者的作用是從 linked list 中移除某個數值,演算法如下:
:::success
1. first search the list starting at ListHead (which itself is never removed) until the desired node is found.
2. To protect this search from the effects of concurrent deletions, lock each node before any of its contents are accessed.
3. Because all searches start at ListHead, there is never a deadlock because the locks are always taken in list order.
4. When the desired node is found, lock both the node and its predecessor since the change involves both nodes.
5. Because the predecessor’s lock is always taken first, you are again protected from deadlock.
:::
指出這個函式是否能符合演算法一般的運作,在下方挑出最接近的描述選項。
## Ans = ?
* `(a)` 可以運作,一看就知道是「慣 C」上乘之作;
* `(b)` 無法運作,應該在第 25 行後補上 pthread_mutex_unlock(¤t->lock);
* `(c)` 無法運作,應該將第 23 行換成 pthread_mutex_unlock(¤t->lock);
* `(d)` 無法運作,應該在第 19 行後補上 pthread_mutex_unlock(¤t->lock);
pthread_mutex_unlock(&prev->lock);
* `(e)` 無法運作,應該在第 19 行後補上 pthread_mutex_unlock(¤t->lock);
:::danger
Reference
* Why does POSIX have recursive mutexes? [Because of a dare.](https://www.reddit.com/r/programming/comments/qrju5/why_does_posix_have_recursive_mutexes_because_of/)
* [ Linus Torvalds 談論 recursive mutex ](http://yarchive.net/comp/linux/recursive_locks.html)
:::
---
# 題目 5
考慮以下程式碼:
```clike=
#include <stdlib.h>
#include <stdio.h>
int isMultN(unsigned int n)
{
if ( (n == 0) )
return 1;
if ( (n >> 2) < (n & 3) )
return 0;
n = (n >> 2) - (n & 3);
return(isMultN(n));
}
```
其作用為檢查輸入整數是否為 N 的倍數，那麼 N 為多少？
* `(A)` 2
* `(B)` 3
* `(C)` 5
* `(D)` 7
* `(E)` 11
* `(F)` 13
---
# 題目 6
FuncX 的功能等價於 FuncY
參考以下兩個函式
```clike=
void FuncX(List *list, Node *node) {
Node **ptop = &list->head;
while (*ptop != node)
ptop = &(*ptop)->next;
*ptop = node->next;
}
void FuncY(List *list, Node *node) {
Node *prev = NULL;
Node *temp = list->head;
while (temp != node) {
@@@X1@@@
temp = temp->next;
}
if (!prev)
@@@X2@@@
else
prev->next = node->next;
}
```
## FuncX 是取自 linux kernel 的程式碼，請選以下敘述中最接近 FuncX 功能的敘述
* `(A)` 搜尋 node 然後在找到後將 node 後方的 Node 資料整串移動 head
* `(B)` 搜尋 node 然後在找到後將 node 刪除
* `(C)` 搜尋 node 然後在找到後將 node -> next 連接回 node 變成環狀結構
* `(D)` 搜尋 node 然後在找到後將 head 後方的 Node 資料整串移動到 node 後方
* `(E)` 搜尋 node 然後在找到 node 之後將 node 改為 head
## @@@X1@@@部份應填入下列何者？
* `(A)` temp = prev;
* `(B)` prev = temp->next;
* `(C)` prev = temp;
* `(D)` temp = list->head;
## @@@X2@@@部份應填入下列何者？
* `(A)` node = list->head;
* `(B)` node->next = list->head;
* `(C)` list->head = node;
* `(D)` list->head = node->next;
###### tags: `社團` `題目`
---
Sign in with Wallet
Connect another wallet