JJ/Homework1(面試題目)
===
# 1.

公司名稱：模擬面試
職務說明：NA
面試題目：

Semaphore 和 Mutex 的差異

解答：

counter vs. owner
priority inversion
Semaphore與mutex都是在處理同步問題的機制，最主要的差別是:
semaphore是一個counter的概念，可以設定有多少個process存取資源，如果存取的process數量到達上限，其他要求存取資源的process會被送到wait queue中，等待有process釋放資源，再繼續執行。
Mutex就像是一把鑰匙，會記錄擁有這把鑰匙的owner是哪個process，process需要取得鑰匙後才能進到critical section存取資源，等到存取完成後才釋放出這把鑰匙的擁有權，達到mutual exclusion。
mutex還需要注意另一個priority inversion問題，假設A,B,C 三個process 優先權 A>B>C
C握有lock，A在等lock造成優先權高的A等待C的情況，若此時B變為可執行的，則B會preempt process C，造成process A需要等待更久的時間，這種情況稱為unbounded priority inversion。
發生這種情況是用priority inheritance protocol來解決，即暫時提高C的priority繼承A的priority，這樣就能阻止process B preempt，等C執行完時再放棄繼承priority，回復原本的priority。

流程：NA
出處：[資訊科技產業面試模擬和工作咨詢 (2014/10/5)](https://hackpad.com/-2014105-5TOjUJI2rKu)

---
# 2.

公司名稱：模擬面試
職務說明：NA
面試題目：

Process 和 Thread 的差異

解答：

address space
process:將程式(program)載入記憶體中，變成可執行的process。
thread:一個process可以產生多個thread。

process 之間的address space並不相同，thread則共用相同的address space。
linux threading model

(3) Red-black tree 在 Linux 核心的應用

流程：NA
出處：[資訊科技產業面試模擬和工作咨詢 (2014/10/5)](https://hackpad.com/-2014105-5TOjUJI2rKu)

---
# 3.

公司名稱：模擬面試
職務說明：NA
面試題目：

用 C 語言實做 big-endian 和 little-endian 互轉的程式

解答：以 uint32_t 為例

unsigned uint32_t swap_uint32( uint32_t val )
{
    val = ((val << 8) & 0xFF00FF00 ) | ((val >> 8) & 0xFF00FF ); 
    return (val << 16) | (val >> 16);
}
int32_t swap_int32( int32_t val )
{
    val = ((val << 8) & 0xFF00FF00) | ((val >> 8) & 0xFF00FF ); 
    return (val << 16) | ((val >> 16) & 0xFFFF);
}

[參考]( http://www.prudentman.idv.tw/2007/11/big-enttradianlittle-endian.html)
流程：NA
出處：[資訊科技產業面試模擬和工作咨詢 (2014/10/5)](https://hackpad.com/-2014105-5TOjUJI2rKu)

---
# 4.

公司名稱：模擬面試
職務說明：NA
面試題目：

C++ function overriding vs. overloading

解答
- Overloading:是一個簡化函式命名的技巧，有多個相同名稱的函式，依據傳入的parameter list數量或是型別的不同，決定該呼叫哪一個函式。如:

void print(int i) {...}
void print(double d) {...}
void print (char c) {...}

- Overriding:子類別將父類別函式重新定義成符合自身所需，使得相同的函式在不同的類別，會有不同的行為反應。如:

class person {
    public void iam() {
        cout<<"i am person";
    }
}

class superman extends person {
    public void iam() {
        cout<< "i am superman";
    }
}

[參考網站](http://antrash.pixnet.net/blog/post/79139547-%E8%AB%96%E7%89%A9%E4%BB%B6%E5%B0%8E%E5%90%91part-8%EF%BC%9Awhy-overloading%E3%80%81overriding)
流程：NA
出處：[資訊科技產業面試模擬和工作咨詢 (2014/10/5)](https://hackpad.com/-2014105-5TOjUJI2rKu)

---
# 5.

公司名稱：模擬面試
職務說明：NA
面試題目：

 C++的copy constructor, deep copy

解答：
**constructor的功用是讓我們在建立物件的同時，就初始化資料成員的內容，constructor必須與類別同名，並且不能有回傳值，若無定義constructor，編譯器會替類別定義一個default constructor**
<br>
- copy constructor：當程式定義新物件，並且以同類別其他物件來做初始值時會呼叫copy constructor，來進行物件複製

class time{
public:
time(int);
private:
int hour;
};
time::time(int h){   //constructor
hour = h;
}
time::time(const time &t){      //copy constructor
hour = t.hour;
}
int main(){
time t1(9);
time t2 = t1; //t2,t3,t4都會呼叫copy constructor
time t3(t2);
time t4 = time(t3);
}

- deep copy：會再開闢一個記憶體區塊複製一份指標所指向的變數內容給指定的物件，因此被複製的物件及指定的物件所存取的變數就不會互相影響

class MyString
{
private:
    char *m_pchString;
    int m_nLength;
 
public:
    MyString(char *pchString="")
    {
        // Find the length of the string
        // Plus one character for a terminator
        m_nLength = strlen(pchString) + 1;
 
        // Allocate a buffer equal to this length
        m_pchString= new char[m_nLength];
 
        // Copy the parameter into our internal buffer
        strncpy(m_pchString, pchString, m_nLength);
 
        // Make sure the string is terminated
        m_pchString[m_nLength-1] = '\0';
    }
       
    
    MyString::MyString(const MyString& cSource)
    {
        // because m_nLength is not a pointer, we can shallow copy it
        m_nLength = cSource.m_nLength;
 
        // m_pchString is a pointer, so we need to deep copy it if it is non-null
        if (cSource.m_pchString)
        {
            // allocate memory for our copy
            m_pchString = new char[m_nLength];
 
            // Copy the string into our newly allocated memory
            strncpy(m_pchString, cSource.m_pchString, m_nLength);
        }
        else
            m_pchString = 0;
    }
 
    ~MyString() // destructor
    {
        // We need to deallocate our buffer
        delete[] m_pchString;
 
        // Set m_pchString to null just in case
        m_pchString = 0;
    }
 
    char* GetString() { return m_pchString; }
    int GetLength() { return m_nLength; }
};

[參考網站](http://www.learncpp.com/cpp-tutorial/915-shallow-vs-deep-copying/)
流程：NA
出處：[資訊科技產業面試模擬和工作咨詢 (2014/10/5)](https://hackpad.com/-2014105-5TOjUJI2rKu)

---
# 6.

公司名稱：模擬面試
職務說明：NA
面試題目：

簡述 TLB(translation look-aside buffer,TLB)

解答：

到main memory中查詢page table是很耗時的工作，
因此將最近常用到的分頁目錄及entry存到TLB cache中，用來加速對physical memory的存取。
若要找的頁數不在TLB中，則發生TLB miss，必須到main memory找分頁項目，
再對physical memory進行存取，並且將頁數和欄號加到TLB中，若TLB已經滿了，
則移除最近最少使用的項目(LRU)

流程：NA
出處：[資訊科技產業面試模擬和工作咨詢 (2014/10/5)](https://hackpad.com/-2014105-5TOjUJI2rKu)

---
# 7.

公司名稱：模擬面試
職務說明：NA
面試題目：

page fault 與 OS kernel 對應的行為

解答：

page fault: main memory中找不到資料而需要到second memory中找，稱作page fault

步驟：
流程：NA
出處：[資訊科技產業面試模擬和工作咨詢 (2014/10/5)](https://hackpad.com/-2014105-5TOjUJI2rKu)

---
# 8.

公司名稱：模擬面試
職務說明：NA
面試題目：

cache invalidate, cache flush 發生的時機

解答：
[reference link](https://hackpad.com/2014914-M4UmNprwldI#:h=(5)-DMA-和-cache-的關聯)

流程：NA
出處：[資訊科技產業面試模擬和工作咨詢 (2014/10/5)](https://hackpad.com/-2014105-5TOjUJI2rKu)

---
# 9.

公司名稱：模擬面試
職務說明：NA
面試題目：

給定 opendir() 與 readdir() 函式，用遞迴寫出類似 find 的程式page fault 與 OS kernel 對應的行為

解答：
***find 的功能：列出包含目前目錄和其所有子目錄之下的檔案名稱***

void list_dir (const char *dir_name)
{
    DIR * d = opendir (dir_name);
    if (! d) {
        fprintf (stderr, "Cannot open directory '%s\n", dir_name);
        return;         
    }
    while (1) {
        const char * d_name;
        struct dirent * entry = readdir (d);
        if (! entry) break;

d_name = entry->d_name;
        printf ("%s/%s\n", dir_name, d_name);

        if (entry->d_type & DT_DIR) {
            if (strcmp (d_name, "..") != 0 && strcmp (d_name, ".") != 0) {
                int path_length;
                char path[PATH_MAX];
                path_length = snprintf (path, PATH_MAX, "%s/%s", dir_name, d_name);
                printf ("%s\n", path);
                if (path_length >= PATH_MAX) {
                    fprintf (stderr, "Path length has got too long.\n");
                    return;
                }
                /* Recursively call "list_dir" with the new path. */
                list_dir (path);
            }
        }
    }
    if (closedir (d)) {
        fprintf (stderr, "Could not close '%s'\n", dir_name);
        return;
    }
}

流程：NA
出處：[資訊科技產業面試模擬和工作咨詢 (2014/10/5)](https://hackpad.com/-2014105-5TOjUJI2rKu)

---
[資訊科技產業面試模擬和工作咨詢](http://wiki.csie.ncku.edu.tw/embedded/rehearsal)