解題區/解題區 - UVa

UVa 675 - Convex Hull of the Polygon

Problem

Suppose that a polygon is represented by a set of integer coordinates, {(x0, y0), (x1, y1), (x2, y2), …, (xn, yn), (x0, y0)}. Please find the convex hull of the polygon, where a convex hull is the minimum bounding convex polygon and “convex” means the angle between two consecutive edges is less than 180o.

Input file

Input consists of several datasets separated by a blank line. Each dataset contains a sequence of integer coordinates xi, yi, one in each line. All input sequence will contain at least 3 different points.

Output

The output for each dataset should contain a sequence of integer coordinates xi, yi specifying the convex hull, each in a line. The first coordinate of the output sequence must be the first coordinate in the input sequence that belongs to the convex hull. The output sequence must be in counter-cockwise order. Print a blank line between datasets.

Sample Input

1
2
3
4
5
6
0, 0
2, 0
1, 1
2, 2
0, 2
0, 0

Sample Output

1
2
3
4
5
0, 0
2, 0
2, 2
0, 2
0, 0

Solution

題目相當單純要輸出凸包的結果，但是最痛恨的是輸出格式，要求從輸入順序中最小的開始打印。

莫名其妙地弄了很多 WA 出來，也許輸入有重複點的關係，所以把點附加輸入編號可能會有所錯誤，總是暴力查找一個哪個點是要開始打印的即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Pt {
    int x, y;
    Pt(int a = 0, int b = 0):
        x(a), y(b) {}
    bool operator <(const Pt &a) const {
        if(x != a.x)       
            return x < a.x;
        return y < a.y;
    }   
    bool operator ==(const Pt &a) const {
        return x == a.x && y == a.y;
    }
};
int cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m - 1;
}
Pt D[100005], C[100005<<1], p;
Pt I[100005];
int main() {
    int cases = 0;
    char s[1024];
    while(gets(s)) {
        if(cases++ > 0)
            puts("");
        int n = 0, m, x, y;
        sscanf(s, "%d, %d", &x, &y);
        I[n] = D[n] = Pt(x, y);
        n++;
        while(gets(s) && s[0] != '\0') {
            sscanf(s, "%d, %d", &x, &y);
            I[n] = D[n] = Pt(x, y);
            n++;
        }
        m = monotone(n, D, C);
        int mark = -1;
        for(int i = 0; i < n && mark == -1; i++) {
            for(int j = 0; j < m; j++)
                if(C[j] == I[i]) {
                    mark = j;
                    break;
                }
        }
        for(int i = mark; i < m; i++)
            printf("%d, %d\n", C[i].x, C[i].y);	
        for(int i = 0; i <= mark; i++)
            printf("%d, %d\n", C[i].x, C[i].y);	
    }
    
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11260 - Odd Root Sum

Problem

Given the value of an n you will have to find the modulo 100000000 value of the following expression:

floor(sqrt(1)) + floor(sqrt(3)) + floor(sqrt(5)) + ... + floor(sqrt(m)) , where m is the largest odd number not greater than n. Or in other words you will have to find the value of S where,

S = floor(sqrt(1)) + floor(sqrt(3)) + floor(sqrt(5)) + ... + floor(sqrt(m)) MOD 100000000

Input

The input file contains at most 30000 lines of inputs. Each line contains a single 64-nit signed integer which denotes the value of n. Input is terminated by a line containing a single zero which should not b processed.

Output

For each line of input produce one line of output. This line contains the value of S.

Sample Input

1
2
3
4
5
9
19
29
10000000
0

Output for Sample Input

1
2
3
4
9
26
49
38426378

Solution

先把前幾項列出來，會發現一個規律

1
2
3
4
5
6
7
8
11
22
3333
4444
555555
666666
77777777
...

每一次會增加兩個。

假設第 1 組為 11 22，第 2 組為 3333 4444 …
需要使用二分搜尋找到我們總共要幾組，然後直接利用公式算出來 sigma(2i * (2i - 1 + 2i))。

但是公式算出來後，會有一個 /3 需要出處理，這邊使用乘法反元素，幸好 3 和 100000000 有互質，不然還真是沒有辦法避免大數運算，計算的時候請各種小心 overflow 的問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
#define MOD 100000000 
long long inv(long long n, long long m) { // get n*? = 1 (mod m)
    long long la = 1, lb = 0, ra = 0, rb = 1;
    long long i = 0, t, mod = m;
    while(n%m) {
        if(!i) {
            la -= n/m*ra;
            lb -= n/m*rb;
        } else {
            ra -= n/m*la;
            rb -= n/m*lb;
        }
        i = !i;
        t = n, n = m, m = t%m;
    }
    if(i)
        return (la%mod+mod)%mod;
    return (ra%mod+mod)%mod;
}
long long getM(long long n) {
    long long l = 0, r = 3037000499LL/2, m, ret;
    long long tmp;
    while(l <= r) {
        m = (l + r) / 2;
        tmp = 4 * (m) * (m + 1);
        if(tmp <= n)
            l = m + 1, ret = m;
        else
            r = m - 1;
    }
    return ret;
}
int main() {
    unsigned long long n;
    long long inv3 = inv(3, MOD);
    while(scanf("%llu", &n) == 1 && n) {
        long long ret = 0;/*
		for(long long i = 1; i <= n; i += 2) {
			// printf("%d\n", (int)sqrt(i));
			ret += (long long) sqrt(i);
			ret %= MOD;
		}
		printf("%lld\n", ret);*/
        unsigned long long m = getM(n);
        long long prev = 4*(m)*(m + 1)%MOD*(2*m + 1)%MOD*inv3%MOD - m * (m + 1)%MOD;
        unsigned long long pn = 4 * (m) * (m + 1) - 1;
        prev = (prev%MOD + MOD)%MOD;
        //printf("%lld %lld %lld\n", m, prev, pn);
        m++;
        if(pn + m * 4 < n) {
            prev += (2 * m - 1) * 2 * m%MOD;
            pn += m * 4;
            //printf("CROSS1 %llu %llu\n", pn, prev);
            prev += (n - pn)/2 * 2 * m%MOD;
            //printf("CROSS2 %llu %llu\n", m * 2, (n - pn) /2);
        } else {
            prev += (n - pn)/2 * (2 * m - 1)%MOD;
            //puts("CROSS3");
        }
        printf("%llu\n", (prev%MOD + MOD)%MOD);
    }
    return 0;
}
/*
11
22
3333
4444
555555
666666
77777777
...
*/
/*
10000000001
*/
Read More +
學校課程/作業系統

向 NachOS 4.0 作業進發 (2)

接續

接續上一篇的 向 NachOS 4.0 作業進發 (1)，我們繼續完成排程處理，在原始的 NachOS 4.0 中，基礎排程是 Round-robin，它的運作方式藉由定時呼叫 threads/alarm.h 中的 Alarm::CallBack()，而呼叫的時脈來源設定為 machine/stats.h 中的 const int TimerTicks = 100; 決定，數值越小表示呼叫頻率越高，置換的次數就會上升。

目標 Scheduler

  • FIFO (FCFS) 先來先服務
  • SJF 最短工作優先
  • Priority 最小優先權優先
  • RR (Round-robin)
  • multi-level queue 最後的大魔王

開始

第一步 - 測試

先來說說怎麼測試自己的寫的代碼正確性，不然怎麼寫都只是理論腦補，雖然會動，但是不知道是否寫對。

  • 第一種方式為下達 

    $ ./nachos -e ../test/test1 -e ../test/test2 ... 多個

    這樣必須自己設置優先權、Burst Time，這方面撰寫方式有兩種，其一是來亂，其二是較為正式，而在 Burst Time 的計算又分成兩種，一是執行前已知、二是執行時猜測。

    • 其一來亂寫法，

      $ ./nachos -e ../test/test1 -e ../test/test2 ... 多個

      不改變原本的的執行方式，直接在代碼中決策 thread fork 出來時所擁有的優先權和 Burst Time。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      static int testPriority = 0;
      void 
      Thread::Fork(VoidFunctionPtr func, void *arg)
      {
      // morris add
          testPriority++;
          if(testPriority == 1)
              setPriority(64);
          else if(testPriority == 2)
              setPriority(128);
          else
              setPriority(64);
      // end morris add

      因此，您可能會寫出以上的代碼，當然我不建議這麼寫，雖然是一種測試方式，但這並不好，一開始就這麼錯得相當離譜。

    • 其二寫法，增加下達參數，不過這些參數格式要去查閱一下他們的參數傳遞建造，我想會寫成大概的樣子為

      $ ./nachos -e ../test/test1 -pw 64 -e ../test/test2  -pw 128 ...

      多個為了不增加工作量，這裡就沒有親自去實作。某方面來說，可能要寫很多 small program 進行測試，並且撰寫時還要預測會跑多久，這難度會稍微提高。

  • 第二種方式按照軟工的寫法
    來寫 test code 吧！如果細心一點，就會看到相關的 Class::SelfTest() 在很多 class 都有的，因此我們需要把 test code 寫到 SelfTest 中被呼叫。因此，不需要有實體的 process 運行，只是單純地測試我們寫的 scheduler 的排程順序是否正確。

    threads/thread.cc
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    void
    threadBody() {
        Thread *thread = kernel->currentThread;
        while (thread->getBurstTime() > 0) {
            thread->setBurstTime(thread->getBurstTime() - 1);
            kernel->interrupt->OneTick();
            printf("%s: remaining %d\n", kernel->currentThread->getName(), kernel->currentThread->getBurstTime());
        }
    }
    void
    Thread::SchedulingTest()
    {
        const int thread_num = 4;
        char *name[thread_num] = {"A", "B", "C", "D"};
        int thread_priority[thread_num] = {5, 1, 3, 2};
        int thread_burst[thread_num] = {3, 9, 7, 3};
        
        Thread *t;
        for (int i = 0; i < thread_num; i ++) {
            t = new Thread(name[i]);
            t->setPriority(thread_priority[i]);
            t->setBurstTime(thread_burst[i]);
            t->Fork((VoidFunctionPtr) threadBody, (void *)NULL);
        }
        kernel->currentThread->Yield();
    }

    請自行在 class Thread 增加 setPriority(), setBurstTime(), SchedulingTest() … 等 method header and body。
    threads/thread.h
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Thread {
      private:
       ...
      public:
       ...
        // morris add
        void setBurstTime(int t)	{burstTime = t;}
        int getBurstTime()		{return burstTime;}
        void setStartTime(int t)	{startTime = t;}
        int getStartTime()		{return startTime;}
        void setPriority(int t)	{execPriority = t;}
        int getPriority()		{return execPriority;}
        static void SchedulingTest();
      private:
        // some of the private data for this class is listed above
        // morris add
        int burstTime;	// predicted burst time
        int startTime;	// the start time of the thread
        int execPriority;	// the execute priority of the thread
        ...
    };

    接著是需要 call testcode 加入到 ThreadedKernel 中。
    threads/kernel.cc
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void
    ThreadedKernel::SelfTest() {
       Semaphore *semaphore;
       SynchList<int> *synchList;
       
       LibSelfTest();		// test library routines
       
       currentThread->SelfTest();	// test thread switching
       Thread::SchedulingTest();   
       				// test semaphore operation
       semaphore = new Semaphore("test", 0);
        ...
    }

    因此我們可以利用單一 module 就能進行檢查。

    $ cd code/threads
$ ./nachos

    但是這種方式，並沒有決定我們要測試哪一種類型的 scheduler，額外需要設定參數，讓其選擇建造哪一種的 readyList(Thread*)

    $ cd code/threads
$ ./nachos FCFS
$ ./nachos SJF
$ ./nachos Priority
$ ./nachos RR

    預計要修成如上述的測試方式。

    threads/main.cc
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    int
    main(int argc, char **argv)
    {
        ...
        debug = new Debug(debugArg);
        
        DEBUG(dbgThread, "Entering main");
    //
        SchedulerType type = RR;
        if(strcmp(argv[1], "FCFS") == 0) {
        type = FIFO;
        } else if (strcmp(argv[1], "SJF") == 0) {
        type = SJF;
        } else if (strcmp(argv[1], "PRIORITY") == 0) {
        type = Priority;
        } else if (strcmp(argv[1], "RR") == 0) {
        type = RR;
        }
    //
        kernel = new KernelType(argc, argv);
        kernel->Initialize(type);
        
        CallOnUserAbort(Cleanup);		// if user hits ctl-C
        kernel->SelfTest();
        kernel->Run();
        
        return 0;
    }

第一步測試撰寫就這麼結束，比起撰寫新的 code，不會進行測試也是徒勞。

雖然這麼說，實際運作也是先寫 code 再寫 test code，因為當時還不太懂這些，所以如果已經先寫了一些也不用難過，大家都是這麼走過來的。

如果不知道怎麼執行，哪還有什麼撰寫的欲望，如果不知道怎麼測試，那就是在黑暗中漫步。

第二步 - 撰寫

在撰寫開始前，如果使用走第一種測試方式的人，需要將實體記憶體用大一點，否則需要實作虛擬記憶體的 context-swith。

machine/machine.h
1
2
3
const unsigned int NumPhysPages = 64;  // morris modify, old value=32
const int MemorySize = (NumPhysPages * PageSize);
const int TLBSize = 4;			// if there is a TLB, make it small

若完成以上的修改，在 /userprog 下，執行

1
$ ./nachos -e ../test/test1 -e ../test/test2 -e ../test/test1

就不會跑出 segment fault 。

threads/scheduler.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
enum SchedulerType {
        RR,     // Round Robin
        SJF,
        Priority,
        FIFO
};
...
class Scheduler {
  public:
    Scheduler();
    Scheduler(SchedulerType type);		// Initialize list of ready threads 
    ...
    	// morris add
    SchedulerType getSchedulerType() {return schedulerType;}
    void setSchedulerType(SchedulerType t) {schedulerType = t;}
  private:
    ...
};

如果有機會查閱其他代碼，很常見會把 List<Thread *> *readyList; 改成 SortedList<Thread *> *readyList; 但是其實不用的，可以利用多形來完成，畢竟 SortedList 繼承 List。因此是不需要更動的。

接著，我們使用多形，在建構子中決定要用哪一種類型的排程，並且宣告相對應的 compare function，參照如下。

threads/scheduler.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int SJFCompare(Thread *a, Thread *b) {
    if(a->getBurstTime() == b->getBurstTime())
        return 0;
    return a->getBurstTime() > b->getBurstTime() ? 1 : -1;
}
int PriorityCompare(Thread *a, Thread *b) {
    if(a->getPriority() == b->getPriority())
        return 0;
    return a->getPriority() > b->getPriority() ? 1 : -1;
}
int FIFOCompare(Thread *a, Thread *b) {
    return 1;
}
//----------------------------------------------------------------------
// Scheduler::Scheduler
// 	Initialize the list of ready but not running threads.
//	Initially, no ready threads.
//----------------------------------------------------------------------
Scheduler::Scheduler() {
    Scheduler(RR);
}
Scheduler::Scheduler(SchedulerType type)
{
    schedulerType = type;
    switch(schedulerType) {
    case RR:
        readyList = new List<Thread *>;
        break;
    case SJF:
        readyList = new SortedList<Thread *>(SJFCompare);
        break;
    case Priority:
        readyList = new SortedList<Thread *>(PriorityCompare);
        break;
    case FIFO:
        readyList = new SortedList<Thread *>(FIFOCompare);
    }
    toBeDestroyed = NULL;
}

上述的寫法是因為沒有辦法宣告 default argument value for class。

如果需要搶先 (Preemptive) 設計，則在 Alarm::CallBack() 決定是否要呼叫 interrupt->YieldOnReturn() 查看是否有更需要優先的 process 要執行。

threads/alarm.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void 
Alarm::CallBack() 
{
    Interrupt *interrupt = kernel->interrupt;
    MachineStatus status = interrupt->getStatus();
    bool woken = _bedroom.MorningCall();
    kernel->currentThread->setPriority(kernel->currentThread->getPriority() - 1);
    if (status == IdleMode && !woken && _bedroom.IsEmpty()) {// is it time to quit?
        if (!interrupt->AnyFutureInterrupts()) {
        timer->Disable();	// turn off the timer
    }
    } else {			// there's someone to preempt
    if(kernel->scheduler->getSchedulerType() == RR ||
        kernel->scheduler->getSchedulerType() == Priority ) {
//		interrupt->YieldOnReturn();
        cout << "=== interrupt->YieldOnReturn ===" << endl;
        interrupt->YieldOnReturn();
        }
    }
}

在 Burst Time 計算上，如果採用運行時估計，可以在以下代碼中進行計算。kernel->stats->userTicks 是執行 user program 的時間累加器 (也存有一個 system program 的時間累加器，運行 thread context-free, thread scheduling … 等時間用途。)

threads/alarm.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
void 
Alarm::WaitUntil(int x) {
    IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);
    Thread* t = kernel->currentThread;
    // burst time
    int worktime = kernel->stats->userTicks - t->getStartTime();
    t->setBurstTime(t->getBurstTime() + worktime);
    t->setStartTime(kernel->stats->userTicks);
    cout << "Alarm::WaitUntil go sleep" << endl;
    _bedroom.PutToBed(t, x);
    kernel->interrupt->SetLevel(oldLevel);
}

其實到這裡已經完成，接下來就放幾張測試結果。

multi-programming

FCFS(1)
FCFS(2)

RR(1)
RR(2)

SJF(1)
SJF(2)

Priority(1)
Priority(1)

最後

如果在

1
2
$ cd code
$ make

編譯時發生錯誤，想必是兩個地方的 Initialize() 發生錯誤，所以請參照以下代碼進行修改。這問題是發生於我們在 /threads 下修改 main.cc 的關係，所以必須在每一個 kernel 宣告地方都給一個決定 scheduler 類型的參數。

其一,

userprog/userkernel.h
1
2
3
4
5
6
7
8
9
#include "../threads/scheduler.h"
class SynchDisk;
class UserProgKernel : public ThreadedKernel {
  public:
  	...
    void Initialize();		// initialize the kernel 
    void Initialize(SchedulerType type);
    ...

其二,
userprog/userkernel.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void
UserProgKernel::Initialize()
{
    Initialize(RR);
}
void
UserProgKernel::Initialize(SchedulerType type)
{
    ThreadedKernel::Initialize(type);	// init multithreading
    machine = new Machine(debugUserProg);
    fileSystem = new FileSystem();
#ifdef FILESYS
    synchDisk = new SynchDisk("New SynchDisk");
#endif // FILESYS
}

其三,
network/netkernel.h
1
2
3
4
5
6
7
8
9
10
11
#include "../threads/scheduler.h"
class PostOfficeInput;
class PostOfficeOutput;
class NetKernel : public UserProgKernel {
  public:
    ...
    void Initialize();		// initialize the kernel 
    void Initialize(SchedulerType);
    ...

其四,
network/netkernel.cc
1
2
3
4
5
6
7
8
9
10
11
12
void 
NetKernel::Initialize() {
    Initialize(RR);
}
void
NetKernel::Initialize(SchedulerType type)
{
    UserProgKernel::Initialize(type);	// init other kernel data structs
    postOfficeIn = new PostOfficeInput(10);
    postOfficeOut = new PostOfficeOutput(reliability, 10);
}

致網路資源

感謝網路上前人們所遺留的遺產。雖然在看不懂的文字中摸索，但仍抓到了一點線索。

我一無所有，直到見到了你們。

Read More +
解題區/解題區 - UVa

UVa 157 - Route Finding

Problem

Many cities provide a comprehensive public transport system, often integrating bus routes, suburban commuter train services and underground railways. Routes on such systems can be categorised according to the stations or stops along them. We conventionally think of them as forming lines (where the vehicle shuttles from one end of the route to the other and returns), loops (where the two ends of the branch are the same and vehicles circle the system in both directions) and connections, where each end of the route connects with another route. Obviously all of these can be thought of as very similar, and can connect with each other at various points along their routes. Note that vehicles can travel in both directions along all routes, and that it is only possible to change between routes at connecting stations.

To simplify matters, each route is given a designation letter from the set A to Z, and each station along a route will be designated by another letter from the set a to z. Connecting stations will have more than one designation. Thus an example could be:

A common problem in such systems is finding a route between two stations. Once this has been done we wish to find the best route, where best means shortest time.

Write a program that will read in details of such a system and then will find the fastest routes between given pairs of stations. You can assume that the trip between stations always takes 1 unit of time and that changing between routes at a connecting station takes 3 units of time.

Input

Input will consist of two parts. The first will consist of a description of a system, the second will consist of pairs of stations. The description will start with a number between 1 and 26 indicating how many routes there are in the system. This will be followed by that many lines, each describing a single route. Each line will start with the route identifier followed by a : followed by the stations along that route, in order. Connections will be indicated by an = sign followed by the complete alternative designation. All connections will be identified at least once, and if there are more than two lines meeting at a connection, some or of all the alternative designations may be identified together. That is, there may be sequences such as ...hc=Bg=Cc=Abd.... If the route forms a loop then the last station will be the same as the first. This is the only situation in which station letters will be repeated. The next portion of the input file will consist of a sequence of lines each containing two stations written contiguously. The file will be terminated by a line consisting of a single #.

Output

Output will consist of a series of lines, one for each pair of stations in the input. Each line will consist of the time for the fastest route joining the two stations, right justified in a field of width 3, followed by a colon and a space and the sequence of stations representing the shortest journey. Follow the example shown below. Note that there will always be only one fastest route for any given pair of stations and that the route must start and finish at the named stations (not at any synonyms thereof), hence the time for the route must include the time for any inter-station transfers.

The example input below refers to the diagram given above.

Sample input

1
2
3
4
5
6
7
8
9
4
A:fgmpnxzabjd=Dbf
D:b=Adac=Ccf
B:acd=Azefg=Cbh
C:bac
AgAa
AbBh
BhDf
#

Sample output

1
2
3
 5: Agfdjba
 9: Abaz=Bdefgh
10: Bhg=Cbac=Dcf

Solution

題目描述：

這一個交通運輸工具，配置如上圖所述，以大寫字母 (A - Z) 表示哪一種線路，每一條線路上有一些站牌 (a - z)。求某線某站到某線某站的最少花費時間。

然而在同一個線路上，轉換一個站的成本為 1，如果在線路交集站換一條線路走成本為 3。

輸入上比較特別，會用 = 表示交集的站編號，當然有可能會遇到多個線路的站交集在一起。

Dhc=Bg=Cc=Abd 則表示 D 線路上的 Dh-Dc-Dd，其中 Dc, Bg, Cc, Ab 共站。

可以當作雙向連通，如果有環，則會頭尾相同，例如 Dhch。

題目解法：

題目最令人討厭的是，交集站沒有說清楚，也就是說單一線路上的轉運站沒有說清楚，但事實上會被表示在其他線路上，這裡要自己取聯集。

但是做聯集是件挺麻煩的事，因此在求最短路上做點手腳，把狀態表示成 (某線某站, 前一次是否轉運)，這麼做就方便多了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
int trans_node(int r, int a) {
    r -= 'A', a -= 'a';
    return r * 26 + a;
}
void reverse_node(int n, int &r, int &a) {
    r = n /26 + 'A', a = n %26 + 'a';
}
vector<int> g[1024], g2[1024];
void spfa(int st, int ed) {
    int used[1024][2] = {}, dist[1024][2] = {}, prex[1024][2][2];
    for(int i = 0; i < 1024; i++)
        dist[i][0] = dist[i][1] = 0x3f3f3f3f;
    queue<int> Q, S;
    Q.push(st), S.push(0);
    dist[st][0] = 0, prex[st][0][0] = -1;
    while(!Q.empty()) {
        int u = Q.front(), s = S.front();
        Q.pop(), S.pop();
        used[u][s] = 0;
        for(int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if(dist[v][0] > dist[u][s] + 1) {
                dist[v][0] = dist[u][s] + 1;
                prex[v][0][0] = u, prex[v][0][1] = s;
                if(!used[v][0]) {
                    used[v][0] = 1, Q.push(v), S.push(0);
                }
            }
        }
        int cost = (s == 1) ? 0 : 3;
        for(int i = 0; i < g2[u].size(); i++) {
            int v = g2[u][i];
            if(dist[v][1] > dist[u][s] + cost) {
                dist[v][1] = dist[u][s] + cost;
                
                if(cost == 0)
                    prex[v][1][0] = prex[u][s][0], prex[v][1][1] = prex[u][s][1];
                else
                    prex[v][1][0] = u, prex[v][1][1] = s;
                if(!used[v][1]) {
                    used[v][1] = 1, Q.push(v), S.push(1);
                }
            }
        }
    }
    printf("%3d: ", min(dist[ed][0], dist[ed][1]));
    
    int r = -1, a = -1, s, mm = ed;
    if(dist[ed][0] <= dist[ed][1])
        s = 0;
    else
        s = 1;
    do {
        int nr, na;
        reverse_node(mm, nr, na);
        if(nr != r) {
            if(mm != ed)	printf("=");
            printf("%c%c", nr, na);
        } else {
            printf("%c", na);
        }
        int om = mm;
        mm = prex[om][s][0], s = prex[om][s][1];
        r = nr, a = na;
    } while(mm != -1);
    puts("");
}
int main() {
    char line[1024];
    for(int n; scanf("%d", &n) == 1;) {
        for(int i = 0; i < 1024; i++)
            g[i].clear(), g2[i].clear();
        while(n--) {
            scanf("%s", &line);
            int r = line[0], preX;
            preX = trans_node(r, line[2]);
            for(int i = 3; line[i]; i++) {
                if(line[i] != '=') {
                    int x = trans_node(r, line[i]);
                    int y = preX;
                    g[x].push_back(y);
                    g[y].push_back(x);
                    preX = x;
                } else {
                    int x = trans_node(line[i+1], line[i+2]);
                    int y = preX;
                    g2[x].push_back(y);
                    g2[y].push_back(x);
                    i += 2;
                }
            }
        }
        while(scanf("%s", line) == 1 && line[0] != '#') {
            int x = trans_node(line[0], line[1]);
            int y = trans_node(line[2], line[3]);
            spfa(y, x);
        }
    }
    return 0;
}
/*
4
A:fgmpnxzabjd=Dbf
D:b=Adac=Ccf
B:acd=Azefg=Cbh
C:bac
AgAa
AbBh
BhDf
#
5 
A:ab=Bbcdefghijk 
B:abc=Ajdef=Cb 
C:ab 
D:cd=Eg 
E:fg=Bf 
AaAk 
AcAk 
AbBb 
BaDd 
# 
*/
Read More +
解題區/解題區 - UVa

UVa 172 - Calculator Language

Problem

Calculator Language (CL) supports assignment, positive and negative integers and simple arithmetic. The allowable characters in a CL statement are thus:

All operators have the same precedence and are right associative, thus 15 - 8 - 3 = 15 - (8 - 3) = 10. As one would expect, brackets will force the expression within them to be evaluated first. Brackets may be nested arbitrarily deeply. An expression never has two operators next to each other (even if separated by a bracket), an assignment operator is always immediately preceded by a variable and the leftmost operator on a line is always an assignment. For readability, spaces may be freely inserted into an expression, except between a negative sign and a number. A negative sign will not appear before a variable. All variables are initialised to zero (0) and retain their values until changed explicitly.

Write a program that will accept and evaluate expressions written in this language. Each expression occupies one line and contains at least one assignment operator, and maybe more.

Input

Input will consist of a series of lines, each line containing a correct CL expression. No line will be longer than 100 characters. The file will be terminated by a line consisting of a single #.

Output

Output will consist of a series of lines, one for each line of the input. Each line will consist of a list of the final values of all variables whose value changes as a result of the evaluation of that expression. If more than one variable changes value, they should be listed in alphabetical order, separated by commas. If a variable changes value more than once in an expression, only the final value is output. A variable is said to change value if its value after the expression has been evaluated is different from its value before the expression was evaluated. If no variables change value, then print the message `No Change’. Follow the format shown below exactly.

Sample input

1
2
3
4
5
6
7
A = B = 4
C = (D = 2)*_2
C = D = 2 * _2
F = C - D
E = D * _10
Z = 10 / 3
#

Sample output

1
2
3
4
5
6
A = 4, B = 4
C = -4, D = 2
D = -4
No Change
E = 40
Z = 3

Solution

題目描述：

給一個六則運算，並且所有運算由右往左，也就是題目提及的 right associative，並且在每一個運算式之後輸出有改變值的變數結果。

題目解法：

要處理的問題相當多，按照一般的思路要做出 right associative 還不打緊，就像冪次的定義一樣，也就是把 stack 的嚴格遞增改成非嚴格遞增。

但是查閱討論區給定的數據後，如下所示

範例輸入

1
2
B=(A=1)+(A=2)
#

範例輸出

1
A = 1, B = 3

這表示著連括弧運算順序都是 right associative，這一點相當苦惱，於是最後建造 tree，然後先拜訪右子樹、再拜訪左子樹來解決這些問題。

中間誤把 No Change 寫成 No change，因此卡了不少 Wrong Answer。

Sample Input:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A = B = 4
B=B-6+B=100
C = (D = 2) * _2
C = D = 2 * _2
E = D * _10
F = 15 - 8 - 3
F = 15 - 8 + _3
F=1+F=F-1
A=((3))
Z=Y=X=A=B=C=1+D=E=F=G=2-H=K=J=I=L=M=O=N=P=Q=R=S=T=V=U=W=3
A=100/2
A=100/_2
B=(_1+A*2)/2
B=(1+A*_2)/2
A=(((1-2)*3)+4)
A=((1-(2*3))+4)
A=((1-2)*(3+4))
A=(1-(2*(3+4)))
A=1+2+1+1+1+1+1+1+1+1+1+1+1+1+1+11+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+3
#

AC Sample Output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
A = 4, B = 4
B = -6
C = -4, D = 2
D = -4
E = 40
F = 10
No Change
No Change
A = 3
A = 0, B = 0, C = 0, D = -1, E = -1, F = -1, G = -1, H = 3, I = 3, J = 3, K = 3, L = 3, M = 3, N = 3, O = 3, P = 3, Q = 3, R = 3, S = 3, T = 3, U = 3, V = 3, W = 3
A = 50
A = -50
B = -50
B = 50
A = 1
A = -1
A = -7
A = -13
A = 62

一開始還在想為什麼當 B = 4 時，B=B-6+B=100 會產出 B = -6，由右往左運算。

  • B = 100
  • 6 + B = 106
  • B - (6 + B) = 100 - 106 = -6
  • B assign(=) -6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
// Accepted
#include <stdio.h>
#include <stack>
#include <string.h>
#include <algorithm>
#include <ctype.h>
#include <iostream>
#include <sstream>
using namespace std;
int priority_op(char c) {
    switch(c) {
        case '(':return -1;
        case '=':return 3;
        case '+': case '-':return 1;
        case '*': case '/':return 2;
    }
    puts("ERROR");
    return -1;
}
void trans(char infix[], char buffer[]) {
    int len = strlen(infix);
    char *ptr = buffer;
    stack<char> op;
    *ptr = '\0';
    for(int i = 0; i < len; i++) {
        if(infix[i] == '_' || isdigit(infix[i]) || isalpha(infix[i])) {
        	while(infix[i] == '_' || isdigit(infix[i]) || isalpha(infix[i])) {
        		if(infix[i] == '_')
        			sprintf(ptr, "-");
        		else
            		sprintf(ptr, "%c", infix[i]);	
            	while(*ptr)    ptr++;
            	i++;
        	}
            sprintf(ptr, " ");	
            while(*ptr)    ptr++;
        	i--;
        }else {
        	if(infix[i] == ' ')	continue;
            if(infix[i] == ')') {
                while(!op.empty() && op.top() != '(') {
                    sprintf(ptr, "%c ", op.top()), op.pop();
                    while(*ptr) ptr++;
                }
                op.pop();
            } else {
                if(infix[i] != '(') {
                	if(infix[i] == '=') {
                		while(!op.empty() && priority_op(op.top()) > priority_op(infix[i])) {
                    		sprintf(ptr, "%c ", op.top()), op.pop();
                    		while(*ptr) ptr++;
                		}
                	} else {
                		while(!op.empty() && priority_op(op.top()) > priority_op(infix[i]) && op.top() != '=') {
                    		sprintf(ptr, "%c ", op.top()), op.pop();
                    		while(*ptr) ptr++;
                		}
                	}
                }
                op.push(infix[i]);
            }
        }
    }
    while(!op.empty()) {
        sprintf(ptr, "%c ", op.top()), op.pop();
        while(*ptr) ptr++;
    }
}
int Variable[26] = {}, oldVal[26] = {};
string to_string(int number) {
   stringstream ss;//create a stringstream
   ss << number;//add number to the stream
   return ss.str();//return a string with the contents of the stream
}
struct TreeNode {
    string 	A, B, OP;
    int 	l, r;
    TreeNode(string a="", string b="", string op=""):
        A(a), B(b), OP(op) {}
};
TreeNode node[1024];
int runTree(int label) {
    string 	A = node[label].A;
    string	B = node[label].B;
    int 	a, b;
    if(node[label].OP == "LEAF") {
        if(isalpha(A[0]))
           	a = Variable[A[0] - 'A'];
        else
           	a = atoi(A.c_str());
        return a;	
    }
    b = runTree(node[label].r);
    a = runTree(node[label].l);
//	printf("%d %d\n", a, b);
    //cout << A << ", " << B << ", " << node[label].OP << endl;
    switch(node[label].OP[0]) {
    	case '+': a = a + b; break;
        case '-': a = a - b; break;
        case '*': a = a * b; break;
        case '/': a = a / b; break;
        case '=': 
        	a = b;
        	if(isalpha(A[0])) {
        		Variable[A[0] - 'A'] = a;
        		//cout << A << " -- " << a << endl;
        	}
        	break;
    }
    return a;
}
void buildTree(char postfix[]) {
    
    stringstream	sin(postfix);
    string 			token, A, B;
    stack<string>	stk;
    stack<int>		nodeLabel;
    int 			treeSize = 0;
    
    while(sin >> token) {
    	if(isalpha(token[0])) {
    		stk.push(token);
    		nodeLabel.push(treeSize);
    		node[treeSize++] = TreeNode(token, "", "LEAF");
    		
    	} else if(isdigit(token[token.length() - 1])) {
    		stk.push(token);
    		nodeLabel.push(treeSize);
    		node[treeSize++] = TreeNode(token, "", "LEAF");
    	} else {
            B = stk.top(), stk.pop();
            A = stk.top(), stk.pop();
            int a, b;
            b = nodeLabel.top(), nodeLabel.pop();
            a = nodeLabel.top(), nodeLabel.pop();
            nodeLabel.push(treeSize);
            node[treeSize] = TreeNode(A, B, token);
            node[treeSize].l = a, node[treeSize].r = b;
            treeSize++;
            stk.push("INNER");
    	}
    }
    runTree(nodeLabel.top());
}
char infix[262144], postfix[262144];
int main() {
    while(gets(infix) && infix[0] != '#') {
        trans(infix, postfix);
        
        for(int i = 0; i < 26; i++)
        	oldVal[i] = Variable[i];
        	
        buildTree(postfix);
        
        int f = 0;
        for(int i = 0; i < 26; i++) {
        	if(oldVal[i] != Variable[i]) {
        		if(f)	printf(", ");
        		f = 1;
        		printf("%c = %d", i + 'A', Variable[i]);
        	}
        }
        if(f == 0)
        	puts("No Change");
        else
        	puts("");
        //printf("%s\n", postfix);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 177 - Paper Folding

Problem

If a large sheet of paper is folded in half, then in half again, etc, with all the folds parallel, then opened up flat, there are a series of parallel creases, some pointing up and some down, dividing the paper into fractions of the original length. If the paper is only opened half-way'' up, so every crease forms a 90 degree angle, then (viewed end-on) it forms adragon curve’’. For example, if four successive folds are made, then the following curve is seen (note that it does not cross itself, but two corners touch):

UVa 177

Write a program to draw the curve which appears after N folds. The exact specification of the curve is as follows:

  • The paper starts flat, with the ``start edge’’ on the left, looking at it from above.
  • The right half is folded over so it lies on top of the left half, then the right half of the new double sheet is folded on top of the left, to form a 4-thick sheet, and so on, for N folds.
  • Then every fold is opened from a 180 degree bend to a 90 degree bend.
  • Finally the bottom edge of the paper is viewed end-on to see the dragon curve.

From this view, the only unchanged part of the original paper is the piece containing the start edge, and this piece will be horizontal, with the start edge on the left. This uniquely defines the curve. In the above picture, the start edge is the left end of the rightmost bottom horizontal piece (marked s). Horizontal pieces are to be displayed with the underscore character _, and vertical pieces with the | character.

Input

Input will consist of a series of lines, each with a single number N (1 <= N <= 13). The end of the input will be marked by a line containing a zero.

Output

Output will consist of a series of dragon curves, one for each value of N in the input. Your picture must be shifted as far left, and as high as possible. Note that for large N, the picture will be greater than 80 characters wide, so it will look messy on the screen. The pattern for each different number of folds is terminated by a line containing a single `^’.

Sample input

1
2
3
4
2
4
1
0

Sample output

1
2
3
4
5
6
7
8
9
10
|_
 _|
^
   _   _
  |_|_| |_
   _|    _|
|_|
^
_|
^

Solution

題目描述：

將一個長條紙水平擺放，接著將右手邊的紙摺疊到左上邊的紙上面，接著又再重複做幾次，直到 N 次 ( 若將其攤平則會有 2N 個折疊區塊 )。摺疊完後，依序將其攤開，攤開的方式為：將前一次摺疊的 (想像與 s 重疊的那一片) 從 180 度旋轉到 90 度位置，依序攤開 N 次。

題目解法：

這一題就是題目理解麻煩點，但是不難發現肯定是有遞迴需要處理的。

假設我們定義展開的每一根，分別為往上下左右的射線，會發現其對應關係，新的尾會跟舊的頭對照，依序對照到中間部分。

最後得到關係

  • 上 變成 左
  • 下 變成 右
  • 左 變成 下
  • 右 變成 上

輸出處理方面，利用一個 map 結構去完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h> 
#include <map>
#include <set>
#include <algorithm>
using namespace std;
map<int, set< pair<int, int> > > P;
void build(int n) {
    int A[1<<15];
    // 0 up, 1 down, 2 left, 3 right
    int trans[] = {2, 3, 1, 0};
    int m = 1;
    A[0] = 3;
    for(int i = 1; i <= n; i++) {
        for(int j = m - 1, k = m; j >= 0; j--, k++)
            A[k] = trans[A[j]];
        m = m << 1;
    }
    int x = -1, y = 0, px = 0, py = 0;
    P.clear();
    for(int i = 0; i < m; i++) {
        if(A[i] == 0)		x = px<<1, y = py;
        else if(A[i] == 1)	x = px<<1, y = py - 1;
        else if(A[i] == 2)	x = (px<<1)-1, y = py;
        else				x = (px<<1)+1, y = py;
        //printf("%d %d %d - %d %d\n", px, py, A[i], x, y);
        if(A[i] == 0) {
            P[y].insert(make_pair(x, 0));
        } else if(A[i] == 1) {
            P[y].insert(make_pair(x, 1));
        } else if(A[i] == 2) {
            P[y].insert(make_pair(x, 2));
        } else {
            P[y].insert(make_pair(x, 3));
        }
        if(A[i] == 0)		py++;
        else if(A[i] == 1)	py--;
        else if(A[i] == 2)	px--;
        else				px++;
    }
}
int main() {
    for(int n; scanf("%d", &n) == 1 && n; ) {
        build(n);
        int mxy = -0x3f3f3f3f, mnx = 0x3f3f3f3f;
        for(map<int, set< pair<int, int> > >::iterator it = P.begin();
        it != P.end(); it++) {
            mxy = max(mxy, it->first);
            for(set< pair<int, int> >::iterator jt = it->second.begin();
                jt != it->second.end(); jt++) {
                mnx = min(mnx, jt->first);
            }
        }
        for(map<int, set< pair<int, int> > >::reverse_iterator it = P.rbegin();
        it != P.rend(); it++) {
            int i = mnx;
            for(set< pair<int, int> >::iterator jt = it->second.begin();
                jt != it->second.end(); jt++) {
                while(i < jt->first)	putchar(' '), i++;
                i++;
                if(jt->second == 0 || jt->second == 1)
                    putchar('|');
                else
                    putchar('_');
            }
            puts("");
        }
        //printf("%d %d\n", mxy, mnx);
        puts("^");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 132 - Bumpy Objects

Problem

132img1

Consider objects such as these. They are polygons, specified by the coordinates of a centre of mass and their vertices. In the figure, centres of mass are shown as black squares. The vertices will be numbered consecutively anti-clockwise as shown.

An object can be rotated to stand stably if two vertices can be found that can be joined by a straight line that does not intersect the object, and, when this line is horizontal, the centre of mass lies above the line and strictly between its endpoints. There are typically many stable positions and each is defined by one of these lines known as its base line. A base line, and its associated stable position, is identified by the highest numbered vertex touched by that line.

Write a program that will determine the stable position that has the lowest numbered base line. Thus for the above objects, the desired base lines would be 6 for object 1, 6 for object 2 and 2 for the square. You may assume that the objects are possible, that is they will be represented as non self-intersecting polygons, although they may well be concave.

Input and Output

Successive lines of a data set will contain: a string of less than 20 characters identifying the object; the coordinates of the centre of mass; and the coordinates of successive points terminated by two zeroes (0 0), on one or more lines as necessary. There may be successive data sets (objects). The end of data will be defined by the string ‘#’.

Output will consist of the identification string followed by the number of the relevant base line.

Sample input

1
2
3
4
5
6
7
Object2
4 3
3 2  5 2  6 1  7 1  6 3  4 7  1 1  2 1  0 0
Square 
2 2
1 1  3 1  3 3  1 3  0 0
#

Sample output

1
2
Object2             6
Square              2

Solution

題目描述：

給定一個多邊形，將會給予這個多邊形的質心和頂點。在圖中，質心表示成黑色正方形的小點，而頂點將會使用連續編號逆時針給點。

多邊形可以藉由旋轉放置於水平，並且穩定立起。這時可以發現，會有兩個頂點拉起的水平線，並且質心會位於水平線上的兩個端點之間。

通常一個多邊形具有多個這種水平放置方法，對於一個水平放置方式，可以用在水平線上最大編號的頂點描述。

請輸出最小水平放置的編號。

題目解法：

對多邊形著手凸包計算，這裡使用單調鍊去完成凸包。接著利用內積找到質心是否在兩個水平線端點 (segment 的上方) 之間。

可以利用外積判斷是否在線 (line) 上。

好好利用數學運算，將可以在簡短的代碼完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator-(const Pt &a) const {
        Pt ret;
        ret.x = x - a.x;
        ret.y = y - a.y;
        return ret;
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m - 1;
}
int main() {
    char testcase[105];
    Pt P[1024], CH[1024], IN[1024];
    while(scanf("%s", testcase) == 1) {
        if(!strcmp(testcase, "#"))
            break;
        double 	x, y;
        int 	n = 0, m;
        Pt mc;
        scanf("%lf %lf", &mc.x, &mc.y);
        while(scanf("%lf %lf", &x, &y) == 2) {
            if(x == 0 && y == 0)
                break;
            IN[n] = P[n] = Pt(x, y);
            n++;
        }
        m = monotone(n, P, CH);
        int ret = 0x3f3f3f3f;
        for(int i = 0, j = m - 1; i < m; j = i++) {
            if(between(CH[i], CH[j], mc)) {
                int mn = 0;
                for(int k = 0; k < n; k++)
                    if(onSeg(CH[i], CH[j], IN[k]))
                        mn = max(mn, k);
                ret = min(ret, mn);
            }
        }
        printf("%-20s%d\n", testcase, ret + 1);
    }
    return 0;
}
Read More +
學校課程/作業系統

作業系統 multiprocess & multithread 作業

A 班程式要求

請使用所熟悉的程式開發環境設計單一行程產生子行程 ( Child Process ) 與 多執行緒 ( Multi-Thread) 的程式，意即完成下列傳統 for loop 之列印工作，將其改寫成多行程與多執行緒，由不同的行程與執行緒列印不同 i 值。

1
2
for (int i = 0; i < 10; i++)
    printf("output i = %d\n", i);

注意事項

  • 嚴禁從網路抄襲作業 。每份程式作業將被程式比對軟體檢查，一旦發現抄襲，該份作業以零分計，並且這學期作業系統作業成績以零分計。
  • 後略

這種作業不抄來抄去也難。但是作業格式不清楚，所以也有不同理解方式就是了。

開始動手

對於將 for 迴圈改寫，我們必須認知到幾項

  • 是否要按照順序輸出？
  • 平台 M$, Linux, or Max OS？

此篇假設目標是一模一樣的輸出

multiprocess

child process 屬於 multiprocess 中的一種方式。為什麼這麼說呢？multiprocess 只是要求一個 CPU 中有多個工作同時在進行，藉由排程器去進行工作分配。

先不管這些，要實作 child process 看起來只有走向 fork() 一途。而之前 inker 大神則是走非 child process 使用類似 ./nachos -e ../test/test1 -e ../test/test1 的方式去運行。

為了實作按照順序輸出，我們需要 process 共同擁有的 shared memory，這個 shared memory 將要紀錄原本 for 裡面的 i 值和一個 sem_t，來保證 process 和 process 之間不會同時搶先動作，sem_t 也許是不需要的，這裡留給實驗者去測試。

為了使輸出一致，在 fork() 完之後，使用 wait() 來等待所有子程序結束。這樣會造成當 for loop 需要跑 n 次，就會總共 n 個 process，也就是一整條鏈下去。

  • 思考 wait() 和 sem_t 都不是這麼必要？// 這個要看寫法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include <semaphore.h>
#ifndef  MAP_ANONYMOUS
#ifdef  MAP_ANON
#define MAP_ANONYMOUS MAP_ANON
#endif
#endif
static int *glob_var;
static int n = 32;
int main(void)
{
    glob_var = (int *)mmap(NULL, sizeof *glob_var, PROT_READ | PROT_WRITE,
                    MAP_SHARED | MAP_ANONYMOUS, -1, 0);
    
    sem_t *sema = (sem_t *)mmap(NULL, sizeof(sema),
                       PROT_READ |PROT_WRITE,MAP_SHARED|MAP_ANONYMOUS,
                       -1, 0);
    sem_init(sema, 1, 0);
    *glob_var = 0;
    while (*glob_var < n) {
        sem_wait(sema);
        int pid = fork();
        int output = (*glob_var)++;
        if (output < n)
            printf("%d, pid = %d\n", output, pid);
        sem_post(sema);
        int wpid, status = 0;
        while ((wpid = wait(&status)) > 0)
        {
            //printf("Exit status of %d was %d (%s)\n", (int)wpid, status, (status > 0) ? "accept" : "reject");
        }
    }
    munmap(glob_var, sizeof *glob_var);
    return 0;
}

multithread

Thread 就相當簡單，因為它們是共用同一個記憶體區段，因此沒有 share memory 的問題。
雖然使用 sem_wait(&sem) 和 sem_post(&sem) 來保證區域內的代碼不會同時有多個 thread 在運行，但仍遇到 i = 0 同時在多個 Thread 噴出的情況，這一點百思不得其解，為了解決這一切問題，使用課本提到的 Producer–consumer problem 寫法。

希望能從代碼中看懂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <semaphore.h>
#include <pthread.h>
int i = 0, n = 16;
int count = 0;
sem_t sem;
const int MAX_THREAD = 4;
void *Producer(void *arg) {
    for(int i = 0; i < n;) {
        sem_wait(&sem);
        if(count == 1) {
            sem_post(&sem);
            continue;
        }
        count++;
        // printf("\nProducer is :%d\n", count);
        sem_post(&sem);
        i++;
    }
    pthread_exit(NULL);
}
void *runPrint(void *arg) {
    int id = *((int *) arg);
    for (; i < n ;) {
        sem_wait(&sem);
        if (count == 0) {
            sem_post(&sem);
            continue;
        }
        count--;
        i++;
        printf("loop i = %d, thread id %d\n", i, id);
        sem_post(&sem);
    }
    pthread_exit(NULL);
}
int main() {
    pthread_t *threads;
    sem_init(&sem, 0, 0);
    threads = (pthread_t *) malloc(MAX_THREAD * sizeof(pthread_t));
    for (int i = 0; i < MAX_THREAD; i++) {
        int *p = (int *) malloc(sizeof(int));
        *p = i;
        pthread_create(&threads[i], NULL, runPrint, (void *)(p));
    }
    pthread_t producer;
    int *p = (int *) malloc(sizeof(int));
    *p = -1;
    pthread_create(&producer, NULL, Producer, (void *)(p));
    for (i = 0; i < MAX_THREAD; i++) {
        pthread_join(threads[i], NULL);
    }
    sem_destroy(&sem);
    return 0;
}

後記

代碼沒有寫得很完整，也就是能達到輸出相同且用符合需求，這一點是有很多漏洞的，前人也是鑽漏洞交作業的。相較之下，我們 B 班的作業略顯兇殘，但是網路上資料還真是少呢，雖然還是找地方抄和理解。

測試的時候，為了保證輸出是穩定的，記得得多測試幾次，並且把數字範圍作變調，當然能不能讓一個 create thread 跑完整個迴圈呢？畢竟加上 main thread 就算是 multithread？haha

執行

編譯

  • Mac OSX

    $ clang -pthread x.cpp -o x

  • Linux

    $ gcc -lpthread x.cpp -o x

    運行

  • Linux & Max OSX

    $ ./x

Mac 運行問題

1
2
3
4
5
#ifndef  MAP_ANONYMOUS
#ifdef  MAP_ANON
#define MAP_ANONYMOUS MAP_ANON
#endif
#endif

不知道為什麼 clang 中沒有定義 MAP_ANONYMOUS，增加上述代碼後正確運行。

其他作業

B 班程式作業 1
B 班程式作業 2

Read More +
學校課程/通識課程

當代消費文化與社會 (2)

母親節篇

  1. 請簡述母親節與消費文化的關聯性 ?
    母親節與消費文化原本是扯不上邊的，後來商人們藉由這些推銷的活動，給予不知道母親節要怎麼犒勞養育辛勞的兒女們一項消費選擇，因此提供了相關的優惠活動方便消費者，母親節就逐漸跟情人節送禮一樣的氣氛。
  2. 舉例說明母親節有哪些消費現象 ?
    相關女性用品優惠，對於餐飲業而言就是雙人、多人套餐，而觀光景點就是帶著母親出遊享優惠 … 等等。
  3. 您決定購買什麼禮物送媽媽及其理由 ?
    身為一個程序猿，買禮物卻沒有思路，寫卡片卻沒有語言，在這樣的情況下，按照自己最常做的事情下手設計，但最近還有其他程序要趕，大概是趕不上這個母親節專案了。

血色月灣

Youtube

在這場被隱藏的殺戮中，繼上次壽司造成的魚類問題，沒想到日本又在海洋造成了更大的傷害，不管是不是海豚，也許有人會因為海豚可愛而在這一次的血色海灣而保護它，在我們不喜歡的動物上，說不定也有類似的問題。

最令人訝異的是，即使在國際會議中，也有隱瞞事實的大人物在，果然要執行某些事情，不是會議或者是組織所為，而是來自個人的發起。這句話有額外的啟發，為了背後國民的飯碗或支持，這些代表人物不得不說謊的情境，假使一開始錯了，他們便會一直錯下去，這樣的情況令人相當惋惜。

海豚的確很有靈性，在他們受到如此的遭遇，難免會感受到如新世界中，那些因為外表被看成不同種的情況，而受到摧殘的可能，對於靈性的動物，在受到傷害，我們給予同情，在其他情況下則沒有這麼強烈的反應。

消費型科技商品

現在出門一定有 GPS 衛星導航的裝置，才能穿梭於大街小巷，這些裝置給我們相當大的便利，不用攜帶大量的地圖資訊出門，不會迷路、不用煩惱就可以輕鬆出門。

科技所帶來的便利，使得停下來思考的機會少了，也不會看看四周的景色，追求更快速地抵達目的地，目的地以外的機緣就越來越少了。比起問人，問機器更來得有信任感，這也表示著相信別人給的知識也不是那麼重要。根據新聞的研究報導，也許我們正在改變記憶方式，開始不擅長記繁瑣的事物，而開始擅長去哪裡找資料、如何使用資料。

因此，也常發生因衛星導航所造成的交通事故，被引導到錯誤地方或者是進入不合適的地點。這也反應使用者即使發現了不合理之處，最後仍相信訊息給的答案。假使衛星給了錯誤訊息，或者被惡意修改成錯誤訊息，很容易造就嚴重事故，我們已經被訓練得無法自己處理這些資訊。

也許老師會問我「那你認為到底要不要買衛星導航？」這一點還真的是要看需求，身為宅的人們不喜歡出門呢。

Read More +
學校課程/作業系統

向 NachOS 4.0 作業進發 (1)

關於 NachOS 4.0

作為教學用作業系統，需要實現簡單並且儘量縮小與實際作業系統之間的差距，所以我們採用 Nachos 作為作業系統課程的教學實踐平臺。Nachos 是美國加州大學伯克萊分校在作業系統課程中已多次使用的作業系統課程設計平臺，在美國很多大學中得到了應用，它在作業系統教學方面具有一下幾個突出的優點：

  • 採用通用虛擬機器
  • 簡單而易於擴展
  • 物件導向性
  • … 略

簡單地來說，就是一個模擬作業系統的軟體

安裝

課程頁面：http://networklab.csie.ncu.edu.tw/2014_os/osweb.html#download

  • Platform: Linux or Linux over VMware 
    RedHat Linux 9.0
    在 Ubuntu 上面運行無法
  • Install steps
    • Get NachOS-4.0
      wget ../nachos-4.0.tar.gz
    • Get Cross Compiler
      wget ../mips-decstation.linux-xgcc.tgz
    • Move Cross Compiler to /
      mv ./mips-decstation.linux-xgcc.tgz /
    • Untar Cross Compiler
      tar zxvf ./mips-decstation.linux-xgcc.tgz
    • Untar NachOS-4.0
      tar zxvf ./nachos-4.0.tar.gz
    • Make NachOS-4.0
      cd ./nachos-4.0/code
make
    • Test if installation is succeeded
      cd ./userprog
./nachos -e ../test/test1
./nachos -e ../test/test2

預期運行結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Total threads number is 1
Thread ../test/test1 is executing.
Print integer:9
Print integer:8
Print integer:7
Print integer:6
return value:0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
                                                                                
Ticks: total 200, idle 66, system 40, user 94
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0
Total threads number is 1
Thread ../test/test2 is executing.
Print integer:20
Print integer:21
Print integer:22
Print integer:23
Print integer:24
Print integer:25
return value:0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
Ticks: total 200, idle 32, system 40, user 128
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0

作業階段

Multiprogramming

執行下述指令

1
./nachos –e ../test/test1 –e ../test/test2

test1.c
1
2
3
4
5
6
#include "syscall.h"
main() {
    int n;
    for (n=9;n>5;n--)
        PrintInt(n);
}
test2.c
1
2
3
4
5
6
7
#include "syscall.h"
main() {
    int n;
    for (n=20;n<=25;n++)
        PrintInt(n);
}

在開始動工前，發現在 Multithread 操作會有錯誤，test1 程序會遞減輸出，而 test2 程序會遞增輸出，但是根據運行結果，兩個程式都會遞增輸出。

目標運行結果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Total threads number is 2
Thread ../test/test1 is executing.
Thread ../test/test2 is executing.
Print integer:9
Print integer:8
Print integer:7
Print integer:20
Print integer:21
Print integer:22
Print integer:23
Print integer:24
Print integer:6
return value:0
Print integer:25
return value:0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
 
Ticks: total 300, idle 8, system 70, user 222
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0

  • 為什麼兩個程式都會遞增輸出？
    明顯地是兩個程式匯入時，操作到相同區域的 code segment。如果發現各別遞增和遞減，但是輸出 n 的結果錯誤，則可以想到是 context-switch 上發生問題。

解決

需要為 physical address 做標記，這個 physical address 就是在 main memory 裡面的位置。而每一個 process 都會有一個 AddrSpace，然後紀錄 logical address 所對應在 physical address，也就是 pageTable 對應到 pageTable[i].physicalPage。

也就是說，當要執行 process 某一頁的程序，則將會去找 pageTable 所對應的 physicalPage，然後去運行。在作業一開始給的代碼中，會發現所有程序的 physicalPage 都共用，如此一來當然會執行到同一份 code。

首先，我們需要一個全局的標記，來記錄 main memory page 的情況。

usrprog/addrspace.h
1
2
3
4
5
6
7
class AddrSpace {
  public:
    ...
    static bool usedPhyPage[NumPhysPages];
  private:
    ...
};

接著，在 addrspace.cc 宣告實體，並且初始化是 0，表示全部都還沒有用過。

usrprog/addrspace.cc
1
2
3
4
5
6
7
8
#include "copyright.h"
#include "main.h"
#include "addrspace.h"
#include "machine.h"
#include "noff.h"
    ...
bool AddrSpace::usedPhyPage[NumPhysPages] = {0};
    ...

當 process 執行成功後，將會釋放資源。此時將要把標記使用的 page 設回未使用。

usrprog/addrspace.cc
1
2
3
4
5
6
AddrSpace::~AddrSpace()
{
    for(int i = 0; i < numPages; i++)
        AddrSpace::usedPhyPage[pageTable[i].physicalPage] = false;
   delete pageTable;
}

最後，就是稍微麻煩的地方，當將程序載入記憶體時，要去填入 pageTable[] 對應的 physicalPage，這裡使用線性時間去搜索第一個未使用的 page 進行填入。

載入確定後，便要開始執行，執行的時候要去算程序進入點，進入點的位置即是 main memory address。

mainMemory[pageTable[noffH.code.virtualAddr/PageSize].physicalPage * PageSize + (noffH.code.virtualAddr%PageSize)]

首先算出第幾頁，然後乘上 PageSize 就是 page base，而 page offset 則是 code.address mod PageSize。

最後，page base + page offset 就是我們所需要的程序進入點。

usrprog/addrspace.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
bool AddrSpace::Load(char *fileName) {
    OpenFile *executable = kernel->fileSystem->Open(fileName);
    NoffHeader noffH;
    unsigned int size;
    if (executable == NULL) {
    cerr << "Unable to open file " << fileName << "\n";
    return FALSE;
    }
    executable->ReadAt((char *)&noffH, sizeof(noffH), 0);
    if ((noffH.noffMagic != NOFFMAGIC) && 
        (WordToHost(noffH.noffMagic) == NOFFMAGIC))
    	SwapHeader(&noffH);
    ASSERT(noffH.noffMagic == NOFFMAGIC);
// how big is address space?
    size = noffH.code.size + noffH.initData.size + noffH.uninitData.size 
            + UserStackSize;	// we need to increase the size
                        // to leave room for the stack
    numPages = divRoundUp(size, PageSize);
//	cout << "number of pages of " << fileName<< " is "<< numPages << endl;
// morris add
    pageTable = new TranslationEntry[numPages];
    for(unsigned int i = 0, j = 0; i < numPages; i++) {
        pageTable[i].virtualPage = i;
        while(j < NumPhysPages && AddrSpace::usedPhyPage[j] == true)
            j++;
        AddrSpace::usedPhyPage[j] = true;
        pageTable[i].physicalPage = j;
        pageTable[i].valid = true;
        pageTable[i].use = false;
        pageTable[i].dirty = false;
        pageTable[i].readOnly = false;
    }
// end morris add
    size = numPages * PageSize;
    ASSERT(numPages <= NumPhysPages);		// check we're not trying
                        // to run anything too big --
                        // at least until we have
                        // virtual memory
    DEBUG(dbgAddr, "Initializing address space: " << numPages << ", " << size);
// then, copy in the code and data segments into memory
    if (noffH.code.size > 0) {
        DEBUG(dbgAddr, "Initializing code segment.");
    DEBUG(dbgAddr, noffH.code.virtualAddr << ", " << noffH.code.size);
// morris add
        	executable->ReadAt(
        &(kernel->machine->mainMemory[pageTable[noffH.code.virtualAddr/PageSize].physicalPage * PageSize + (noffH.code.virtualAddr%PageSize)]), 
            noffH.code.size, noffH.code.inFileAddr);
// end morris add
    }
    if (noffH.initData.size > 0) {
        DEBUG(dbgAddr, "Initializing data segment.");
    DEBUG(dbgAddr, noffH.initData.virtualAddr << ", " << noffH.initData.size);
// morris add
        executable->ReadAt(
        &(kernel->machine->mainMemory[pageTable[noffH.initData.virtualAddr/PageSize].physicalPage * PageSize + (noffH.code.virtualAddr%PageSize)]),
            noffH.initData.size, noffH.initData.inFileAddr);
// end morris add
    }
    delete executable;			// close file
    return TRUE;			// success
}

Sleep() System call

撰寫自己的 Sleep function，將該 Thread 進入休眠。

測試檔案

與一開始的 test1.c 很像，這裡先做個簡單測試。

/code/test/sleep.c
1
2
3
4
5
6
7
8
9
#include "syscall.h"
main() {
    int i;
    for(i = 0; i < 5; i++) {
        Sleep(10000000);
        PrintInt(50);
    }
    return 0;
}

因為整個測試檔案是要能在 nachOS 上面跑，所以不能使用一般的編譯方式？所以把這些訊息寫入 Makefile 中，之後下 $ make 產出 sleep 即可。
/code/test/Makefile
1
2
3
4
5
6
7
...
all: halt shell matmult sort test1 test2 sleep
...
sleep: sleep.o start.o
    <span>$(LD)$</span><!-- Has MathJax -->(LDFLAGS) start.o sleep.o -o sleep.coff
    ../bin/coff2noff sleep.coff sleep
...

如果無法在 /code/test 下 $ make 順利產出，則請參照 其他指令 ，將原本下載的 mips-decstation.linux-xgcc.gz 解壓縮產生的 /usr 移動到正確位置。

解決

首先，要模仿 PrintInt()，找到切入的宣告位置。努力地尾隨前人。

/code/userprog/syscall.h
1
2
3
4
5
6
7
...
#define SC_PrintInt	11
#define SC_Sleep	12
...
void PrintInt(int number);	//my System Call
void Sleep(int number);         // morris add
...

接著，找一下 ASM。
以下部分就不得而知了，為什麼會出現在 /code/test 目錄下。

/code/test/start.s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    ...
PrintInt:
    addiu   <span>$2,$</span><!-- Has MathJax -->0,SC_PrintInt
    syscall
    j       $31
    .end    PrintInt
    .globl  Sleep
    .ent	Sleep
Sleep:
    addiu   <span>$2,$</span><!-- Has MathJax -->0,SC_Sleep
    syscall
    j	$31
    .end	Sleep
    ...

最後，確定 nachOS 會處理我們的例外操作。

/code/userprog/exception.cc
1
2
3
4
5
6
7
8
9
10
11
    ...
case SC_PrintInt:
    val=kernel->machine->ReadRegister(4);
    cout << "Print integer:" << val << endl;
    return;
case SC_Sleep:
    val=kernel->machine->ReadRegister(4);
    cout << "Sleep Time " << val << "(ms) " << endl;
    kernel->alarm->WaitUntil(val);
    return;
    ...

到這裡需要喘口氣，剛找了一陣子的代碼。接著才是重頭戲，因為你看到了 kernel->alarm->WaitUntil(val); 出現了。沒錯！我們需要撰寫那邊的代碼。

既然 kernel 存有 alarm，也就是說每隔固定一段間，就會呼叫 Alarm::CallBack()，因此，對於這個鬧鐘來個累加器 Bedroom::_current_interrupt，全局去記數，當作毫秒 (ms) 看待就可以，每加一次就相當於過了 1 毫秒 (ms)。

假設現在某一個 time = _current_interrupt 呼叫 Sleep(x) 後，將 (Thread address, _current_interrupt + x) 丟入 List，則期望在 _current_interrupt + x 的時候甦醒。因此，每當 _current_interrupt++ 就去檢查 List 中，誰的預期時間小於 _current_interrupt，就將其從 List 中清除。

這裡先不考慮 _current_interrupt Overflow 的問題，根據電腦效率，可能在 5 ~ 10 秒內就發生一次，此時會造成所有 Thread 沉眠很久。若察覺 Sleep 太久，則是發生 Overflow。

  • 當有程序呼叫 Sleep() 時，會呼叫 WaitUntil()，然後將其丟入 Bedroom 安眠。
  • 然後在 CallBlack() 被呼叫時，來去 Bedroom 檢查誰該醒來了。
/code/threads/alarm.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include "copyright.h"
#include "utility.h"
#include "callback.h"
#include "timer.h"
#include <list>
#include "thread.h"
class Bedroom {
    public:
        Bedroom():_current_interrupt(0) {};
        void PutToBed(Thread *t, int x);
    bool MorningCall();
    bool IsEmpty();
    private:
        class Bed {
            public:
                Bed(Thread* t, int x):
                    sleeper(t), when(x) {};
                Thread* sleeper;
                int when;
        };
    
    int _current_interrupt;
    std::list<Bed> _beds;
};
// The following class defines a software alarm clock. 
class Alarm : public CallBackObj {
  public:
    Alarm(bool doRandomYield);	// Initialize the timer, and callback 
                // to "toCall" every time slice.
    ~Alarm() { delete timer; }
    
    void WaitUntil(int x);	// suspend execution until time > now + x
  private:
    Timer *timer;		// the hardware timer device
    Bedroom _bedroom;
    void CallBack();		// called when the hardware
                // timer generates an interrupt
};

確定有哪些 method 就可以開始實作了。

/code/threads/alarm.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void Alarm::CallBack() {
    Interrupt *interrupt = kernel->interrupt;
    MachineStatus status = interrupt->getStatus();
    bool woken = _bedroom.MorningCall();
    
    if (status == IdleMode && !woken && _bedroom.IsEmpty()) {// is it time to quit?
        if (!interrupt->AnyFutureInterrupts()) {
        timer->Disable();	// turn off the timer
    }
    } else {			// there's someone to preempt
    interrupt->YieldOnReturn();
    }
}
void Alarm::WaitUntil(int x) {
    IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);
    Thread* t = kernel->currentThread;
    cout << "Alarm::WaitUntil go sleep" << endl;
    _bedroom.PutToBed(t, x);
    kernel->interrupt->SetLevel(oldLevel);
}
bool Bedroom::IsEmpty() {
    return _beds.size() == 0;
}
void Bedroom::PutToBed(Thread*t, int x) {
    ASSERT(kernel->interrupt->getLevel() == IntOff);
    _beds.push_back(Bed(t, _current_interrupt + x));
    t->Sleep(false);
}
bool Bedroom::MorningCall() {
    bool woken = false;
    _current_interrupt ++;
    for(std::list<Bed>::iterator it = _beds.begin(); 
        it != _beds.end(); ) {
        if(_current_interrupt >= it->when) {
            woken = true;
            cout << "Bedroom::MorningCall Thread woken" << endl;
            kernel->scheduler->ReadyToRun(it->sleeper);
            it = _beds.erase(it);
        } else {
            it++;
        }
    }
    return woken;
}

到這裡我們就完成 Sleep() 製作。

在下一階段，將要加入排程的製作。

Scheduling

目標完成 SJF, RR, FIFO。
請參閱 “向 NachOS 4.0 作業進發 (2)”

其他指令

  • 打包轉移 // 交作業前，將檔案包出傳送，此指令不是壓縮用途

    1
    $ tar cvf FileName.tar DirName

  • 複製資料夾 // 將 nachos gcc library 搬移至 /usr/local/nachos ...

    1
    $ cp -a DirName TARGET_PATH

  • 轉移至 root 權限 // 如果指令權限不夠，需要下達此指令。

    1
    $ su

備忘

  • 網路上有幾個 Java 版本的 NachOS，架構稍微不同，如果發現文章說明有點怪怪的，請看一下他是用 JAVA 版本還是 C++ 版本。
  • 至於怎麼將檔案從 Red Hat，這有點惱人，可以想辦法安裝其他瀏覽器，然後開 e-mail 送出，或者使用 terminal 上的 wget 安裝 … 一堆辦法。最後我自己用 nodejs 寫一個簡單的 upload server 傳出來。

代碼下載

Github

Read More +