軟體開發方法論(翻譯部分內容)

長篇大論

只求軟體開發的工程方法,最近上敏捷方法,教授開始講到了始祖 …

於是上演了輪番翻譯的戲碼,讓各種同學參與這份大型工程,關於翻譯的同時,深刻地理解到這也是為什麼無法接觸國外的最新資訊啊,曲解、誤解、亂解 …

我的語言記憶體如此小,卻搭載世界最複雜的語言。

In the past few years there’s been a blossoming of a new style of software methodology - referred to as agile methods. Alternatively characterized as an antidote to bureaucracy or a license to hack they’ve stirred up interest all over the software landscape. In this essay I explore the reasons for agile methods, focusing not so much on their weight but on their adaptive nature and their people-first orientation.

Probably the most noticeable change to software process thinking in the last few years has been the appearance of the word ‘agile’. We talk of agile software methods, of how to introduce agility into a development team, or of how to resist the impending storm of agilists determined to change well-established practices.

也許在這過去幾年最引人注目對軟件過程的思考的改變 - “敏捷 agile” 一詞的出現。我們將談論如何將敏捷軟體方法(agile software method)引入到開發團隊,或者如何抗拒即將到來的敏捷提倡者所帶來的風暴,這風暴將改變原先建立的好的業界實踐方法。

This new movement grew out of the efforts of various people who dealt with software process in the 1990s, found them wanting, and looked for a new approach to software process. Most of the ideas were not new, indeed many people believed that much successful software had been built that way for a long time. There was, however, a view that these ideas had been stifled and not been treated seriously enough, particularly by people interested in software process.

這新運動來自于 1990 年起不同人對於軟體程序的努力,他們發現和找到一個新的軟體程序。大多數敏捷方法的想法並不新,大多數人認為很多成功的軟件本來就有內置這種方式很久了,的確是有的,然而有一觀點指出,這些想法對於對軟體過程感興趣的人眼中並沒有受到重視,甚至被受到抑制。

This essay was originally part of this movement. I originally published it in July 2000. I wrote it, like most of my essays, as part of trying to understand the topic. At that time I’d used Extreme Programming for several years after I was lucky enough to work with Kent Beck, Ron Jeffries, Don Wells, and above all the rest of the Chrysler C3 team in 1996. I had since had conversations and read books from other people who had similar ideas about software process, but had not necessarily wanted to take the same path as Extreme Programming. So in the essay I wanted to explore what were the similarities and differences between these methodologies.

這篇文章也是新運動的起源一部份,最初發表于 2000 年 7 月。作為嘗試了解這文章一部份,您必須知曉這篇文章的風格如同其他大多數我寫的文章。在很幸運地與 Kent Beck, Ron Jeffries, Don Wells 共事後,我已經使用極限編程 (Extreme Programming) 好幾年。從 1996 年的 Chrysler C3 team 那時。我有機會與別人互相交流資訊和書籍來得到他們對於軟體過程中的類似想法,但即使是極限編程 (Extreme Programming) 也沒有一定要採用一樣的走法,所以在這篇文章中,我想要探索這些方法間的異同。

My conclusion then, which I still believe now, is that there were some fundamental principles that united these methodologies, and these principles were a notable contrast from the assumptions of the established methodologies.

以我的話來說,我至今仍相信那些方法一定有一些共同的基本原則,這些原則可能會從原本既有的(主流)方法假設中有明顯地對比。

This essay has continued to be one of the most popular essays on my website, which means I feel somewhat bidden to keep it up to date. In its original form the essay both explored these differences in principles and provided a survey of agile methods as I then understood them. Too much has happened with agile methods since for me to keep up with the survey part, although I do provide some links to continue your explorations. The differences in principles still remain, and this discussion I’ve kept.

這篇文章將會一直是一篇這個網站最熱門的文章,也意味者我會感到使命去保持這篇文章的更新。在文章原始架構中,會探討我所了解的這些原則的差異和提供敏捷方法的調查。當我在調查的同時,敏捷方法已經發生了變動,但仍我也提供一些鏈結供您探索,這些原則的差異和討論內容仍會保留在這篇文章中。

Most software development is a chaotic activity, often characterized by the phrase “code and fix”. The software is written without much of an underlying plan, and the design of the system is cobbled together from many short term decisions. This actually works pretty well as the system is small, but as the system grows it becomes increasingly difficult to add new features to the system. Furthermore bugs become increasingly prevalent and increasingly difficult to fix. A typical sign of such a system is a long test phase after the system is “feature complete”. Such a long test phase plays havoc with schedules as testing and debugging is impossible to schedule.

大多數軟體開發是一個混亂的開始,常常以一句話代以概括 ”撰寫!修復!“,這些軟體在撰寫時不用事先有基礎的計劃,也不用系統架構,將由短期項目討論就可以拼湊起來。這確切在系統很小時可以運作,但當系統越大時將會變得相當困難去增加新的功能。此外,BUG 也會越來越普遍見到,且越來越難除錯。這典型系統是在功能齊備後,才經由長時間的測試階段。這麼長時間的測試階段將嚴重破壞測試和除錯的行程,使得行程根本無法安排。試階段起著嚴重破壞的時間表為測試和調試是不可能的安排。

The original movement to try to change this introduced the notion of methodology. These methodologies impose a disciplined process upon software development with the aim of making software development more predictable and more efficient. They do this by developing a detailed process with a strong emphasis on planning inspired by other engineering disciplines - which is why I like to refer to them as engineering methodologies (another widely used term for them is plan-driven methodologies).

起源運動將要改變這種方法的概念,這些方法論所施加的紀律,將協助軟體開發變得更可預測和更有效率。他們將透過製定詳細的過程,這些過程特別強調設計,靈感來自于其他工程學門- 這就是為什麼我喜歡稱呼它們為 ”工程方法 enginerring methodologies“ (對於他們來說,另一個廣泛使用的術語為 “計劃驅動方法 plan-driven methodologies”)

Engineering methodologies have been around for a long time. They’ve not been noticeable for being terribly successful. They are even less noted for being popular. The most frequent criticism of these methodologies is that they are bureaucratic. There’s so much stuff to do to follow the methodology that the whole pace of development slows down.

工程方法已經存有一段歷史,它們都沒有被注目那背後可怕的成功,它們相當少被認為是受流行的,常見的批評為 ”它們是官僚政治的“ // 相當死板的 ? 。有相當多的項目都遵循這套方法論使用緩慢的發展步伐。

Agile methodologies developed as a reaction to these methodologies. For many people the appeal of these agile methodologies is their reaction to the bureaucracy of the engineering methodologies. These new methods attempt a useful compromise between no process and too much process, providing just enough process to gain a reasonable payoff.

敏捷方法的發展就是反映這些工程方法論,對于大多數的人而言,敏捷方法的吸引力是反映出工程方法的官僚主義,這些新方法是在沒有進展和太多進展中的折衷妥協方案,提供一種恰當的過程來獲得合理回饋。

The result of all of this is that agile methods have some significant changes in emphasis from engineering methods. The most immediate difference is that they are less document-oriented, usually emphasizing a smaller amount of documentation for a given task. In many ways they are rather code-oriented: following a route that says that the key part of documentation is source code.

這一切的結過是,敏捷方法從工程方法中有顯的改變。最明顯的差異是少寫文件(文件導向),通常強調少量文件的工作,在許多說法上,它們更偏向代碼導向(code-oriented: 文件的關鍵部分是源代碼 source code)

糟透的軟體開發

在土木工程中,建造一個橋來說,通常在設計草圖完成後,即使換了別的公司繼續接按下去做,一樣能按照這個設計草圖完成。如果在施工過程中遇到問題,通常問題也不會太難,而且非常容易被解決。

在了解這些設計草圖後,可以發現勞心者和勞力者的工作是分開的,設計由專家耗費心力完成,而實作能由工人來按照草圖,因此這些設計草圖是確保工人們能看得懂,但是在軟體工程中,大部分都是勞心者和勞力者集一人之中。

施工是一個相當耗費成本的工作,在早期的軟體工程開發專家,希望能將土木工程的方法轉移到軟體工程上。讓專家進行設計,再讓低成本的工作人員來完成實作,設計費用通常比實作費用來的低,工程師仍有高低薪之分,新一代的低薪工程師呢!

專家寫出來的設計草圖,要讓 programmer 看得懂,通常是非常困難的。即使是 UML 圖,雖然在紙(草圖)上看起來相當不錯,但是實作上的問題卻相當多,土木工程的設計圖可以經過數學模型去測試,但是軟體工程的設計圖只能由人腦去找到邏輯BUG,即使是設計熟練的專家,要設計出不會有實作問題的草圖也是常發生的。

接續著剛剛討論的造橋問題,設計費用只占了全部花費的十分之一,按照草圖寫 code 是相當簡單的,根據 McConnell 調查大型專案,只有 15% 的成本進行程式撰寫和測試(這裡我們需要勞力成本比例越高越好)。即使把其他成本混在一起,設計仍占了 50% 的成本比例。軟體工程只是工程分枝中之一,這其中一定有蹊蹺。

結論

  • 軟體的建造相當便宜,甚至於免費(只淤需要電腦和編譯器,沒有實體。)
  • 軟體受設計影響,因此需要有創造力和有天賦的人。
  • 俱有創新的程序不容易去規劃,可預測的性質甚至變成不可能。
  • 我們需要不同於傳統工程的方法,來解決這詭異的軟體工程的開發程序。

常常有開發者收到客戶不斷地改變需求,但是改變需求是常態,但是對於開發者而言卻是想不透的謎。這表示當初需求並沒有弄完整,但是也不能說像客戶簽訂契約——表示在軟體完成前,需求都不會改變。需求改變是很正常的,這客戶來說這個契約反而不合理。

按需求收費,加什麼功能要多少錢?估算收費也是不好量化,也會根據產品使用的方式和使用者有關,因此品質的水準與費用是不好預估。客戶以為“軟”體容易修改,但並不是每個需求都容易修改,通常會耗費大量的時間去滿足客戶的需求。

如果需求不穩定,就得不到可預測的計劃去完成軟體。

真的不可預測?

在 NASA 太空軟體開發中,他們的計劃是可以預測的,但這也只是一個特別的例子,主要原因是長期時間,龐大的團隊,穩定的需求。

更可怕的是,如果客戶需求不穩定,卻告知有可預測的計劃,這樣自欺欺人的行為相當令人詬病。

”可預測“是令人相當渴望的,這導致一開始擬定的計劃越飄越遠,最後計劃將會分崩離析。

按照方法論運行總是美好的,但是在軟體開發上必須要捨棄掉,但這樣的舉動相當困難,要捨棄一直以來處理事情的方式,但也並不是讓事情處理變得無法控制的混沌,捨棄“預測”吧!

控制 “不可預測”程序

使用迭代方式,並且將計劃越短越好,看起來就是多方面失敗的開始,但卻有機會看來進步的地方,當計劃越短,就能越早知道反饋(feedback)。

文件可以隱藏缺失,沒有經過測試將會有更多的缺失。

XP 一周或兩周,SCRUM 一個月之類的,越熟練則會越短時間。

=====

並不是每個工程師都像零件,換個人就可以繼續運行。

不可更換的人零件都跑了,也就是最有創意的人力都走了,可更換的人卻留下了。

Programmer 是有責任的專業人員?

早期是工廠的運行模式,希望能讓工人多做一點事情,來讓成本降低。

每個 programmer 是獨特的,產出的代碼也都不同,每一個人的創意不同,把人當資源就錯了。

施工和設計能不能分開?施工只是由編譯器來,因此軟體全是文創業,算是設計類型的職業。

Read More +

《刺激消費,我是主角》心得

當代消費文化與社會 期中報告

閱讀書名:《刺激消費,我是主角》
書目作者:日野佳惠子

對於當今社會物質富裕已經為大多數人的基礎,因此消費行為也越來越特異化,從注重環保以及各種責任意義,消費的著重點也有所不同。

如何聰明消費?或者說消費出聰明的價值?的確有一股取向,有錢人的消費模式在於大批購買,而我們這種一般人對於聰明的消費是相當自豪的,聰明消費能夠展現自己能在低價購入高品質的產品,這裡的低價就不單單只是低消費額,是一個相對於產品應有的價值之下。在這股潮流之下,依賴情報消費真的很重要,因此也易受於口碑品牌的影響。就如比特幣剛出時,大批人覺得是一個未來重要的貨幣商品而大量購買 … 等。

如果徵才也是互動型的消費,文中說明消費者若有貢獻出一己之力的機會,將會更容易讓其主動消費,例如廣告為『我們想像身為家庭主婦的您,購買做家事的能力與烹飪能力』比起『時薪 OO 徵才』好太多了,文中所提的例子相當有感,能對別人有所助益,即使中間的過程是消費的一環,也是相當具有自願性的行為。不單單只是為了個人去購買商品,同時也是為了其他外界因素而進行消費。如同當初 Firefox 打擊微軟的 IE 手法,提供開源代碼的方式,希望其他人參與這場攻防戰,願意幫助這個軟體更完善,在不花一毛錢的情況下,這個組織靠著消費者活到了至今。

模仿身邊的人進行消費,如果這個商品是對於土豪們為取向,那麼消費族群也總是那一群,需要靠身邊親朋好友的消費習慣來渲染自己,如果身邊沒有人這麼消費,那要成為第一個購買者的機會是相當低的,因此企業常會用親民的代表人物來推銷自己的商品。我相信在相同處境下,需求是彼此靠攏的。這有點粒子群聚算法的感覺。

『對於不懂得使用方法的人,不了解真正含義的人,無法因商品獲得快樂的人而言,即使技術再進步,一切都是毫無意義。』看到這一句話,越來越明白消費的同時也是在教導,如果單純只是想要擴張客源,沒有好好教導消費者如何使用也是不行的。

『消費者也是加工者,開創低價商品交給消費者加工,並且銷售宣傳』由於消費者不喜歡與別人相同,又想要做出自己的風格,低價商品的拓展性就變得相當高了,低價商品通常有著量多便宜的特性,譬喻成大自然的元素也不為過。想到這一點,有人開發出有前景的軟硬體,通常會湧出一批人去購買,並且修正或運用然後進行傳播,這影響力堪稱指數擴張。這也應對消費者也是企業的助手,一群消費者就是一大群的應援團,將與企業或產品一同發展。

『不消費的智慧』雖然使得商品沒有利益,但是這也表示新的消費可能再也不是利益,而是商品後頭的智慧,看著越來越多的消費手法,沒有智慧學習的商品,除了一般生活所需外,在未來可能很難遍及市場,娛樂市場又是另外一回事。

『把整個環境一同賣給你』即使商品單獨具有高性能,沒有環境展現其性能事件很糟糕的事情,就如蘋果電腦和軟體總是整包出售,兩項缺一不可。而最近微軟最近正有著附上環境出售的趨勢,不過搭配性不強,跟裸機差不多。

Read More +

a576. No Cheating

題目

內容:

有個學校想辦一場考試,提供了 T 間教室。每間教室的座位都是 M×N 的矩陣(不同教室的 M, N 可以不一樣),而有的座位壞掉了不能坐。此外,為了避免學生作弊,如下圖,對任何一個學生而言,他的左方、左前方、右方、右前方都不可以有人坐。請問每間教室所能容納的學生數最多為何?

輸入說明:

第一行有一個數字 T,代表學校有 T 間教室。接下來會有每個教室的資料,每筆資料會有在同一行兩個正整數 M, N,代表座位的配置是 M×N。接下來的 M 行,每行有 N 個字元,’.’代表那個座位是好的,而’x’則代表那個座位壞了。

輸出說明:

對於每間教室,輸出”Case #X: Y”, 其中 X 代表這是第幾間教室,而 Y 則代表這間教室能容納的學生數最大值。

範例輸入:

4
2 3
...
...
2 3
x.x
xxx
2 3
x.x
x.x
10 10
....x.....
..........
..........
..x.......
..........
x...x.x...
.........x
...x......
........x.
.x...x....

範例輸出:

Case #1: 4
Case #2: 1
Case #3: 2
Case #4: 46

解法

  • 作法:
    按列黑白染色,會發現不能連的位置恰好可以化成二分圖,求最大獨立集即可。
    最大獨立集 = 點個數 - 最大匹配數
a576.cpp
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
/**********************************************************************************/
/* Problem: a576 "No Cheating" from GCJ 2008 Round 3 C */
/* Language: CPP (3826 Bytes) */
/* Result: AC(0.1s, 1.2MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2014-04-18 18:09:46 */
/**********************************************************************************/
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
using namespace std;
struct Node {
int x, y, v;// x->y, v
int next;
} edge[65536];
int e, head[6500], prev[6500], record[6500];
int level[6500], visited[6500];
void addEdge(int x, int y, int v) {
edge[e].x = x, edge[e].y = y, edge[e].v = v;
edge[e].next = head[x], head[x] = e++;
edge[e].x = y, edge[e].y = x, edge[e].v = 0;
edge[e].next = head[y], head[y] = e++;
}
bool buildLevelGraph(int s, int t) {
memset(level, 0, sizeof(level));
queue<int> Q;
Q.push(s), level[s] = 1;
while(!Q.empty()) {
int tn = Q.front();
Q.pop();
for(int i = head[tn]; i != -1; i = edge[i].next) {
int y = edge[i].y;
if(edge[i].v > 0 && level[y] == 0) {
level[y] = level[tn] + 1;
Q.push(y);
}
}
}
return level[t] > 0;
}
int constructBlockingFlow(int s, int t) {
int ret = 0;
stack<int> stk;
memset(visited, 0, sizeof(visited));
stk.push(s);
while(!stk.empty()) {
int now = stk.top();
if(now != t) {
for(int i = head[now]; i != -1; i = edge[i].next) {
int y = edge[i].y;
if(visited[y] || level[y] != level[now] + 1)
continue;
if(edge[i].v > 0) {
stk.push(y), prev[y] = now, record[y] = i;
break;
}
}
if(stk.top() == now)
stk.pop(), visited[now] = 1;
} else {
int flow = 1e+9, bottleneck;
for(int i = t; i != s; i = prev[i]) {
int ri = record[i];
flow = min(flow, edge[ri].v);
}
for(int i = t; i != s; i = prev[i]) {
int ri = record[i];
edge[ri].v -= flow;
edge[ri^1].v += flow;
if(edge[ri].v == 0)
bottleneck = prev[i];
}
while(!stk.empty() && stk.top() != bottleneck)
stk.pop();
ret += flow;
}
}
return ret;
}
int maxflowDinic(int s, int t) {
int flow = 0;
while(buildLevelGraph(s, t))
flow += constructBlockingFlow(s, t);
return flow;
}
int main() {
int n, m;
int testcase, cases = 0;
int i, j, k, x, y;
char g[128][128];
int id[128][128];
scanf("%d", &testcase);
while(testcase--) {
e = 0;
memset(head, -1, sizeof(head));
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
scanf("%s", g[i]);
int ST[2] = {0, 0};
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(g[i][j] == '.') {
id[i][j] = ST[j&1]++;
} else {
id[i][j] = -1;
}
}
}
int source = ST[0] + ST[1];
int sink = source + 1;
for(int i = 0; i < ST[0]; i++)
addEdge(source, i, 1);
for(int i = 0; i < ST[1]; i++)
addEdge(i + ST[0], sink, 1);
int dx[] = {-1, -1, 0, 0, 1, 1};
int dy[] = {-1, 1, -1, 1, 1, -1};
int tx, ty, u, v;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j += 2) {
if(id[i][j] == -1)
continue;
v = id[i][j];
for(int k = 0; k < 6; k++) {
tx = i + dx[k];
ty = j + dy[k];
if(tx < 0 || ty < 0 || tx >= n || ty >= m)
continue;
u = id[tx][ty];
if(u == -1)
continue;
addEdge(v, u + ST[0], 1);
}
}
}
int ret = maxflowDinic(source, sink);
printf("Case #%d: %d\n", ++cases, ST[0] + ST[1] - ret);
}
return 0;
}
Read More +

a858. 數三角形

題目

內容:

你有一個大小為N的完全圖,這N(N-1)/2條邊可能是紅色或黑色。任三個不同的點都形成一個三角形,請問三邊同色的三角形有幾個?

輸入說明:

第一行輸入一個正整數N,其中N<=1,000。接下來的N行,每行有N個數字,其中第i行的第j個數字代表邊(i,j)的顏色,紅色用1表示,黑色用2表示,i=j時則用0表示。

輸出說明:

請輸出同色三角形的數目。

範例輸入:

4
0 1 2 1
1 0 1 1
2 1 0 2
1 1 2 0

範例輸出:

1

解法

  • 作法:
    分治,將輸入 n 個劃分成兩堆,分別窮舉所有可能,採用合併的方式去運算。
a858.cpp
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
/**********************************************************************************/
/* Problem: a858 "數三角形" from */
/* Language: CPP (462 Bytes) */
/* Result: AC(0.1s, 264KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2014-04-17 11:06:20 */
/**********************************************************************************/
#include <stdio.h>
int main() {
int n, x;
while (scanf("%d", &n) == 1) {
int p = (n) * (n-1) * (n-2) / 6;
int s = 0;
for (int i = 0; i < n; i++) {
int b = 0, r = 0;
for(int j = 0; j < n; j++) {
scanf("%d", &x);
r += x == 1;
b += x == 2;
}
s += r * b;
}
printf("%d\n", p - s/2);
}
return 0;
}
Read More +

a007. 判斷質數

題目

內容:

請判斷某數是否為質數

輸入說明:

輸入有多組測試資料(以EOF結尾),每組測試資料占一行,只包含一個整數x, 2 ≦ x ≦ 2147483647。

輸出說明:

對於每組測試資料,如果輸入的x為質數,則輸出一行「質數」(不含引號);否則輸出一行「非質數」(不含引號)。詳見範例測試資料。

範例輸入:

13
14

範例輸出:

質數
非質數

解法

  • 作法:
    Miller-Rabin Algorithm
a007.cpp
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
/**********************************************************************************/
/* Problem: a007 "判斷質數" */
/* Language: CPP (715 Bytes) */
/* Result: AC(0.2s, 224KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2014-04-18 20:25:42 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int Pow(long long x, int n, long long mod) {
long long Ans = 1, t = x;
while(n) {
if(n&1)
Ans *= t, Ans %= mod;
t *= t, t %= mod, n >>= 1;
}
return (int)Ans;
}
int JudgePrime(int n) {
if(n == 2 || n == 3) return 1;
if(n == 1) return 0;
if(!(n&1)) return 0;
int a, x, flag = 1, t;
for(a = 0; a < 2; a++) {
x = rand()%(n-4)+2;
t = Pow(x, n-1, n);
if(t != 1) return 0;
}
return 1;
}
int main() {
int n;
while(scanf("%d", &n) == 1) {
if(JudgePrime(n)) puts("質數");
else puts("非質數");
}
return 0;
}
Read More +

a962. 新專輯

題目

內容:

給定正整數N,請求出(N除以1的餘數)+(N除以2的餘數)+(N除以3的餘數)+…+(N除以N的餘數)。

輸入說明:

輸入只有一個正整數N,其中1<=N<=1014。

輸出說明:

為了避免要寫大數,你只要輸出這個奇怪的和除以1000000009的餘數就好了。

範例輸入:

10

範例輸出:

13

解法

  • 作法:
    各種方式要避免 mod 運算。
a962.cpp
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
/**********************************************************************************/
/* Problem: a962 "新專輯" from TIOJ 1674 */
/* Language: CPP (1612 Bytes) */
/* Result: AC(0.8s, 272KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2014-04-18 20:11:19 */
/**********************************************************************************/
#include <stdio.h>
#include <math.h>
#define MOD 1000000009LL
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;
}
int main() {
long long inv2 = inv(2, MOD);
long long n;
while(scanf("%lld", &n) == 1) {
long long ret = 0, hret = 0;
long long half = (long long)sqrt(n)/5;
long long u = -1, v = 0;
for(half = 1; u != v; half++, u = v, v = n/half) {
hret += n%half;
}
hret -= n%(half - 1);
hret %= MOD;
long long l = half - 1, r, div;
long long a0, d, tn, buff;
while(l <= n) {
div = n / l;
r = n / div;
a0 = n % l, d = -div, tn = r - l + 1;
if(tn >= MOD) tn %= MOD;
if(d >= MOD) d %= MOD;
if(a0 >= MOD) a0 %= MOD;
buff = (a0 * 2 + (tn - 1)*d);
if(buff < 0 || buff >= MOD) buff %= MOD;
buff *= tn;
if(buff < 0 || buff >= MOD) buff %= MOD;
ret += buff;
l = r + 1;
}
ret %= MOD;
ret = (ret * inv2)%MOD;
ret = (ret + hret + MOD)%MOD;
printf("%lld\n", ret);
}
return 0;
}
/*
100000000000000
*/
Read More +

a981. 求和問題

題目

內容:

給你N個正整數, 試求哪幾個之和剛好為M, 印出所有合條件的解, 如有多組解, 請按由小到大的順序印出(格式可參考樣例輸出)

輸入說明:

n m (1<=n<=30, 1<=m<=100000000) n個正整數, 全部以空格分開

輸出說明:

  • 其和剛好等於m的數, 如果有多組解則按由小到大全部印出, 如果無解則印出 -1

範例輸入:

10 100
10 20 40 30 50 80 60 70 5 15

範例輸出:

5 10 15 20 50
5 10 15 30 40
5 10 15 70
5 15 20 60
5 15 30 50
5 15 80
10 20 30 40
10 20 70
10 30 60
10 40 50
20 30 50
20 80
30 70
40 60

解法

  • 作法:
    分治,將輸入 n 個劃分成兩堆,分別窮舉所有可能,採用合併的方式去運算。
a981.cpp
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
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
int main() {
int n, m;
int A[35];
while(scanf("%d %d", &n, &m) == 2) {
for(int i = 0; i < n; i++)
scanf("%d", &A[i]);
sort(A, A + n, greater<int>());
int h1Cnt = n / 2, h2Cnt = n - h1Cnt;
map<long long, vector<int> > h1, h2;
for(int i = (1<<h1Cnt)-1; i >= 0; i--) {
long long sum = 0;
for(int j = 0; j < h1Cnt; j++) {
if((i>>j)&1) sum += A[j];
}
h1[sum].push_back(i);
}
for(int i = (1<<h2Cnt)-1; i >= 0; i--) {
long long sum = 0;
for(int j = 0; j < h2Cnt; j++) {
if((i>>j)&1) sum += A[j + h1Cnt];
}
h2[sum].push_back(i<<h1Cnt);
}
set<int> ret;
for(map<long long, vector<int> >::iterator it = h1.begin();
it != h1.end(); it++) {
long long f = (long long)m - it->first;
map<long long, vector<int> >::iterator jt = h2.find(f);
if(jt != h2.end()) {
for(vector<int>::iterator iv = it->second.begin();
iv != it->second.end(); iv++) {
for(vector<int>::iterator jv = jt->second.begin();
jv != jt->second.end(); jv++) {
ret.insert(*iv| *jv);
}
}
}
}
if(ret.size() == 0)
puts("-1");
for(set<int>::reverse_iterator it = ret.rbegin();
it != ret.rend(); it++) {
for(int i = n-1; i >= 0; i--) {
if(((*it)>>i)&1) {
printf("%d ", A[i]);
}
}
puts("");
}
}
return 0;
}
Read More +

Scarky 您的博客線上檢測系統

Scarky 提供線上出程式題目的平台

出了一道好题目却不知道该怎样投递到各大OJ上?现在不用担心这个问题了,因为你可以直接把自己的Blog变成一个OJ。Scarky是一个建立在SPOJ系统上的OJ平台。所不同的是,任何人无需注册便可以编写自己的题目并发在自己的网站上与网友分享,并且网友们提交答案时也不需要进行注册。这个网站的功能还在不断扩充中,但目前就Programming Challenge模块看来,这个网站已经很强大了。以后我有了好题目就用这种方式和大家分享了,这里先试用一下,题目来源好像是某次USACO月赛。

matrix67 的說明
Scarky 網址點我

創建題目

  • 點進網站,點選創建自己的題目,您將會看到下圖的訊息,記得要求它寄封題目鏈結到你的信箱。這些題目內容稍後還能修改。
    scarky5.png
  • 在信封中,將會收到編輯頁面鏈結。
    scarky3.png
  • 回到編輯頁面,將可以把輸入輸出測資放上去,最後按儲存訊息即可。
    基本上這裡都採用嚴格比對,也就是多空白多換行字符都是不行的。
    scarky2.png
  • 編輯者還能看到目前的統計資料。為什麼身為管理者看不到別人上傳的代碼,這不科學。
    scarky4.png
  • 放上博客有三種方式。
    scarky1.png

使用心得

  • 正如上方的題目,編輯頁面要打 HTML,這點不科學也不方便。
  • 頁面顯示上就是固定,大小無法更動。
  • 題目生存期限有多久?曾經放著一年前的題目還在。
  • HTML 打好放上去,編輯時從曾經打過的 <br/> 會消失。
  • 最後附上簡單的測試。
      <strong>題目描述</strong><br/><br/>
          <p>
              請將 NFA 轉換成 DFA,不用進行最佳化。
          </p><br/>
      <strong>輸入描述</strong><br/><br/>
          <p>
              輸入只會有一筆 NFA 描述,輸入以 EOF(end-of-file) 為結尾。
              <br/><br/>
              略 ...
          </p><br/>
      <strong>輸出格式</strong><br/><br/>
          <p>
          輸出對於每一組 DFA,格式如下。<br/>
          輸出第一行為字母集 CDFA (按照字典順序輸出)。<br/>
          <br/>
          略 ...
          </p><br/>
      <strong>Example Input :</strong><br/>
          <pre>
          (l,a,b,2)
          (2,0)(3,0)(0,0)
          (0,0)(4,5)(0,0)
          (0,0)(0,0)(4,0)
          (0,0)(5,0)(5,0)
          (*,*)(*,*)(*,*)
          略 ...
          </pre>
      <strong>Example Output:</strong><br/>
          <pre>
          (a,b)
          (1,2)(*3,4,5)(0)
          (*3,4,5)(*5)(*4,5)
          (*5)(0)(0)
          (*4,5)(*5)(*5)
          略 ...
          </pre>
    

Hexo

  • 文章格式
      title: Scarky 您的博客線上檢測系統
      date: 2014-04-17 19:35:27
      tags: [Scarky, ACM, Judge]
      categories: 出題解題
      scarky: PNFCQOY5
    
  • 文章顯示
    theme/layout/_partial/post/article.ejs
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    <div id="main" class="<%= item.layout %>" itemscope itemprop="blogPost">
    <article itemprop="articleBody">
    <%- partial('header') %>
    <div class="article-content">
    <%- partial('gallery') %>
    <% if( table&&(item.toc !== false) && theme.toc.article){ %>
    <div id="toc" class="toc-article">
    <strong class="toc-title"><%= __('contents') %></strong>
    <%- toc(item.content) %>
    </div>
    <% } %>
    <% if(item.scarky) { %>
    <!-- scarky widget http://scarky.com/ -->
    <script type="text/javascript" src="http://scarky.com/widget/get/<%= item.scarky %>/"></script>
    <!-- end scarky widget -->
    <% } %>
    <%- item.content %>
    </div>
    <%- partial('footer') %>
    </article>
    <%- partial('pagination') %>
    <%- partial('comment') %>
    </div>
Read More +

作業系統 筆記 (1)

讀物

現在恐龍書不知道第幾版了,而且中文翻譯有點慘。看英文原文又太慢的情況,剛好查到聯合大學陳士杰教授寫的 ppt。繁體中文的說明,採用恐龍書第七版的內容。

下附章節簡報和課後習題解答。

稍微看過每一章的內容後,就可以著手看習題解答。

CH 1
CH 2
CH 3
CH 4
CH 5
CH 6
CH 7
CH 8
CH 9
CH 10

恐龍書課後習題解答 感謝大大的提供

之前也有好幾次參照教授寫的中文簡報,相當有助益。

可能遭遇的問題

個人拙見,請自行過濾

Round-Robin Scheduling

  • 這個問題在寫考題的時候,略顯著的疑惑。
  • 對於 Round-Robin Scheduling 的部分
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    queue Q
    while(true) {
    w = Q.front()
    w = work(w)
    if(hasProcess())
    Q.push(nextPorcess())
    if(w != null)
    Q.push(w)
    time++
    }

    詳見代碼後,由於超過時限後,還要將變數存起來,所以丟入 queue 的時間會晚一點,也就是說在同一時刻會慢於新抵達的 process。之後的程序就按照 queue 的順序去運行。

考古題(課本後習題)

(=゚ω゚)= 下附解答僅個人拙見,請勿隨意採信,請發揮您的善心,救救笨蛋

95 期中考

  • What is multiprogramming ? what is time-sharing ?(10%)

    • Multiprogramming(多重程式):

      • 定義:
        內存有多個 processs 同時執行,一般電腦的運行方式。透過 CPU scheduling 將發生中斷 (eg. wait for I/O complete, resource not available, etc.) 的行程切換給可執行的運作。
      • 特色:
        可以避免 CPU idle,提高 CPU utilization(使用率)
      • 其他:
        1. Multiprogramming Degree:系統內存在執行的 process 數目
        2. 通常 Multiprogramming Degree 越高,則 CPU utilization 越高(p.s. ch7 Thrashing 除外)
        3. 多個 process 同時執行,mode 有兩種 Concurrent(並行)、Parallel(平行)
    • Time-sharing:

      • 定義:
        Multiprogramming 的一種,在 CPU 排班法則方面,其使用 RR(Round-Robin) 法則。
        // RR 法則-CPU time quantum,若 process 在取得 CPU 後,未能於 quantum
        // 內完成工作,則必須被迫放棄 CPU,等待下一次輪迴。
      • 特色:
        對每個 user 皆是公平的,適用在 user interactive 且 response time (反應時間)要求較短的系統環境,透過 resource sharing 技術(eg. CPU scheduling, memory sharing, spooling 達到 I/O Device 共享),使得每個user皆認為有專屬的系統存在。
  • Describe the differences between symmetric and asymmetric multiprocessing. What are three advantages and one disadvantage of multiprocessor systems ?
    In Distributed System - Multiprocessor - Tightly-Coupled System(different from Loosely-Coupled Distributed System)

    • Symmetric Multiprocessors (SMP) 對稱式多處理器
      • 定義:
        每個 processor 的能力皆相同,即可負責的功能完全一樣。萬一某個 processor 壞了,其上工作可由其他processor 接手,系統不會整個 crash,只是整體效能下降而已。
      • 特色:
        Reliability (可靠性)大幅提升,強調 load balancing (負載平衡)(每個CPU的工作負擔相同)
    • Asymmetric Multiprocessors (ASMP) 非對稱式多處理器
      • 定義:
        不同(群)顆的 processor,其負擔的功能不盡相同,在此架構下,通常含有一個Master CPU,負責工作的分派與協調,其他 CPUs 稱為 Slave CPU (稱為 Master-Slave Architecture)
      • 特色:
        效能通常較SMP高,但可靠度較差
  • What are the differences between a trap and an interrupt? What is the use of each function ?
    • Trap:
      軟體產生 system call
      an exception in a user process.
      ex. system call (software divide-by-zero)
    • Interrupt:
      硬體產生 signal
      something generated by the hardware.
      ex. IO-complete interrupt (hardware generated)
    • 兩者相同之處
      從 User Mode 切換到 Kernel Mode。
      兩者都算是 interrupt 中斷指令。
  • What is the purpose of system calls?
    System calls allow user-level processes to request services of the operating system.
    System calls 提供 使用者級別 的程序來請求作業系統給的服務。
    // process control, file Management, device management, information maintenance, communication
  • Describe the differences among short-term, medium-term, and long-term scheduling.
    • short-term (CPU scheduler) —
      CPU 工作排程
      selects from jobs in memory those jobs that are ready to execute and allocates the CPU to them.
    • medium-term —
      常用於分時系統的排程器。當記憶體不夠的時候,需要暫時將部分的執行程序搬出,將新來的程序載入,置換機制被建置用來移除部份在記憶體執行中及恢復那些被暫時移除的程式。
      used especially with time-sharing systems as an intermediate scheduling level. A swapping scheme is implemented to remove partially run programs from memory and reinstate them later to continue where they left off.
    • long-term (job scheduler) —
      將 job 變成 process 的工作排程,將工作從硬碟載入到主記憶體中。
      determines which jobs are brought into memory for processing.
  • Can a multithreaded solution using multiple user-level threads achieve better performance on a multiprocessor system than on a single-processor system? Why?
    • A multithreaded system comprising of multiple user-level threads cannot make use of the different processors in a multiprocessor system simultaneously. The operating system sees only a single process and will not schedule the different threads of the process on separate processors. Consequently, there is no performance benefit associated with executing multiple user-level threads on a multiprocessor system.
    • 以 user-level hreads 實現 multithread 的程式,在多處理器系統中不能比在單處理機系統中有更好的效率, 因在多處理機系統中之作業系統不會將多個 CPU 同時分配給該 user-level multithread 程式。
  • Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:

         Process           Burst Time         Priority
           P1                 10                  3
           P2                  1                  1
           P3                  2                  3
           P4                  1                  4
           P5                  5                  2
    

    The processes are assumed to have arrived in the order P1,P2,P3,P4,P5, all at time 0.

    • (a) Draw four Gantt charts illustrating the execution of these processes using FCFS, SJF, a nonpreempitive priority(a small priority number implies a higher priority), and RR(quantum = 1) scheduling.(5%)
    • (b) What is the turnaround time of each process for each of the scheduling algorithms in part(a).(5%)
    • (c) What is the waiting time of each process for each of the scheduling algorithms in part(a).(5%)
    • (d) Which of the schedules in part (a) results in the minimal average waiting time(over all processes)? (5%)

        請參照上附的習題解法。
      

      5.12 solution


96 期中考

  • FCFS, SJF, Priority, Round-Robin and Multilevel Queue
    Which can be preemptive ? (5%)

    • preemptive 可搶先
      SRTF (剩餘最短優先)、Priority (優先權優先)、Multilevel Queue (多層佇列)、RR
    • non-preemptive 不可搶先
      FCFS (先到先服務)、SJF (最短工作優先)、Priority (優先權優先)
    • Priority (優先權優先) 屬於可搶先跟不可搶先。
    • 可搶先的定義為非自願性被踢出 CPU。
  • What are the four main purposes of an operating system ? (10%)

    • Managing programs
    • Managing Memory
    • Handling input and output
    • User Interface
  • Please give a detail description on the differences among the terms multiprocessing, multitasking and multithreading. (15%)

    • multiprocessing
      具有多個處理器,在同一時間可以在各自處理器上運行程序。
    • multitasking
      執行單一使用者的多個行程,利用排程器讓每一個行程都在平均時間內解決。
    • multithreading
      可以將程序切成好幾個執行緒,若硬體可以同時執行多個執行緒,效率將會上升,如果不能,由於速度夠快看起來也很像多個執行緒同時運行。
  • What are the differences between a trap and an interrupt ? What is the use if each function ? (20%)

    • Trap:
      軟體產生 system call
      an exception in a user process.
      ex. system call (software divide-by-zero)
    • Interrupt:
      硬體產生 signal
      something generated by the hardware.
      ex. IO-complete interrupt (hardware generated)
    • 兩者相同之處
      從 User Mode 切換到 Kernel Mode。
      兩者都算是 interrupt 中斷指令。
  • What is the purpose of system calls, Please describe three general methods that be used to pass parameters to the operating system. (10%).

    • System call 由作業系統提供 API interface 給 user program,可以藉由 system call 向作業系統請求服務,作業系統接收到請求後,執行完報告結果給 user program。
    • [方法1] Registers
      利用Registers ( 暫存器 )儲存這些參數
      優:速度快
      (∵不用作記憶體的存取 )
      缺:不適用於參數個數多的情況
    • [方法2] Memory
      將參數利用 Table 或 Block 的方式儲存在 Memory 中,同時利用一個 Register 記錄此 Table 或 Block 的起始位址,並傳給O.S.
      優:適用於參數個數較多的情況
      缺:速度慢
    • [方法3] Stack
      利用System Stack (堆疊 )。要存放參數時,將之Push 到Stack Stack, 再由O.S.從Stack中Pop 取出參數 。
      Stack在系統中比Register多一些(可用Mem. 或其它硬體(如:Register)來實作此Stack)
  • What is a process ? Draw the diagram of Process State. And describe every state. (15%)
    process state

  • What are the differences between thread and process ? Why do threads have much shorter context switching times ? (10%)

        |        Thread                   |      Process              |
        |---------------------------------|---------------------------|
        | Light Weight Process            | Heavy Weight Process      |
        |                                 |                           |
        | 同一個Task (或 Process ) 內的   |  不同的Process之間無共享的| 
        | Threads可以共享 Code Section,   |  Address Space,互為獨立。|
        | Data Section, 及O.S. Resources  |                           |
        |                                 |
        | Context Switching 負擔輕        |  負擔重
        |                                 |
        | Thread的管理(Management)成本低  |  成本高
        | (管理項目: Creation,           |
        | Scheduling, Context, Switching  |
        | Switching…etc.)                 |
        |                                 |
        | 一個Task內有多條Threads存在     |  一個Task內只有一條Thread
        |  Process (Task) 內的某 Thread   |
        | 被 Block,則可切到其它Thread    |
        | 執行。此時,若 Process 內只要還有
        | Thread 在執行,則 Process 不會被 Block
    
  • What is Multilevel Feedback-Queue scheduling ? (5%)

      定義:
      與Multilevel Queue的定義相似,差別在於允許 Process 在各佇列之間移動 ,以避免Starvation 的情況。
      * 採取類似 “Aging” 技術,毎隔一段時間就將 Process 往上提升到上一層 Queue 中。∴在經過有限時間後,在 Lower Priority Queue 中的 Process 會被置於 Highest Priority Queue 中。故無 Starvation。
      * 亦可配合降級之動作。當上層 Queue 中的 Process 取得 CPU 後,若未能在 Quantum 內完成工作,則此 Process 在放棄 CPU 後,會被置於較下層的 Queue 中。
    
  • Please draw the Gantt charts for the following processes for the problems shown below.
    (a) Round-Robinm time quantum = 1 (5%)
    (b) Shortest-remaining-time-first (Preemptive SJF) (5%)

                  Arrival Time    Brust Time
    
          P1      0               4
          P2      1               2
          P3      2               3
          P4      5               4
          P5      6               3
    
      (a) Time : 0
          Queue: P1
    
          0   1
          +---+
            P1
    
          先丟入 P2, P1 因為超時丟入,此時執行 P2
          Time : 1
          Queue: P2, P1
    
          0   1   2
          +---+---+
           P1  P2
    
          丟入 P3, P2 因為超時丟入,此時執行 P1
          Time : 2
          Queue: P1, P3, P2
    
          0   1   2   3
          +---+---+---+
           P1  P2  P1
    
          P1 因為超時丟入,此時執行 P3
          Time : 3
          Queue: P3, P2, P1
    
          0   1   2   3   4
          +---+---+---+---+
           P1  P2  P1  P3
    
          P3 因為超時丟入,此時執行 P2
          Time : 4
          Queue: P2, P1, P3
    
          0   1   2   3   4   5
          +---+---+---+---+---+
           P1  P2  P1  P3  P2
    
          P2 完成,P4 抵達丟入,此時執行 P1
          Time : 5
          Queue: P1, P3, P4
    
          0   1   2   3   4   5   6
          +---+---+---+---+---+---+
           P1  P2  P1  P3  P2  P1
    
          P5 抵達丟入,P1 超時丟入,此時執行 P3
          Time : 6
          Queue: P3, P4, P5, P1
    
          0   1   2   3   4   5   6   7
          +---+---+---+---+---+---+---+
           P1  P2  P1  P3  P2  P1  P3
    
          P3 超時丟入,此時執行 P4
          Time : 7
          Queue: P4, P5, P1, P3
    
          0   1   2   3   4   5   6   7   8
          +---+---+---+---+---+---+---+---+
           P1  P2  P1  P3  P2  P1  P3  P4
    
          P4 超時丟入,此時執行 P5
          Time : 8
          Queue: P5, P1, P3, P4
    
          0   1   2   3   4   5   6   7   8   9
          +---+---+---+---+---+---+---+---+---+
           P1  P2  P1  P3  P2  P1  P3  P4  P5
    
          P5 超時丟入,此時執行 P1
          Time : 6
          Queue: P1, P3, P4, P5
    
          0   1   2   3   4   5   6   7   8   9  10
          +---+---+---+---+---+---+---+---+---+---+
           P1  P2  P1  P3  P2  P1  P3  P4  P5  P1
    
          P1 完成,此時執行 P3
          Time : 10
          Queue: P3, P4, P5
    
          0   1   2   3   4   5   6   7   8   9  10  11
          +---+---+---+---+---+---+---+---+---+---+---+
           P1  P2  P1  P3  P2  P1  P3  P4  P5  P1  P3
    
          P3 完成,此時執行 P4
          Time : 11
          Queue: P4, P5
    
          0   1   2   3   4   5   6   7   8   9  10  11  12
          +---+---+---+---+---+---+---+---+---+---+---+---+
           P1  P2  P1  P3  P2  P1  P3  P4  P5  P1  P3  P4
    
          ...
    
          0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
          +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
           P1  P2  P1  P3  P2  P1  P3  P4  P5  P1  P3  P4  P5  P4  P5  P4
    

課本習題快取區

ch 5

  • 5.9 Why is it important for the scheduler to distinguish I/O-bound programs
    from CPU-bound programs?
    為什麼排程器需要需分 IO 密集程式 CPU 綁定程式 ?

Answer: I/O-bound programs have the property of performing only a small amount of computation before performing I/O. Such programs typically do not use up their entire CPU quantum. CPU-bound programs, on the other hand, use their entire quantum without performing any blocking I/O operations. Consequently, one could make better use of the computer’s resouces by giving higher priority to I/O-bound programs and allow them to execute ahead of the CPU-bound programs.
IO 密集程式占用 CPU 的時間比較少,大部分時間等在等待 IO。相反地 CPU 綁定程式則會大幅度占用 CPU 的時候,因為沒有 IO 操作的堵塞。

而 CPU bound 的程序因此而得到了很多調度機會並且每次都能把CPU run完。故在這樣的系統裡要給 I/O bound 的程序更高的優先級使其能被調度得更多些。

  • 5.10 Discuss how the following pairs of scheduling criteria conflict in certain
    settings.
    a. CPU utilization and response time // CPU 使用率 和 回應時間 的比較
    b. Average turnaround time and maximum waiting time // 平均運轉時間 和 最大等待時間 的比較
    c. I/O device utilization and CPU utilization // IO 裝置使用率 和 CPU 使用率 的比較

Answer:
a. CPU utilization and response time: CPU utilization is increased if the overheads associatedwith context switching isminimized. The context switching overheads could be lowered by performing context switches infrequently. This could, however, result in increasing
the response time for processes.
CPU 的使用率(utilization)上升時,切換工作的次數(context-switches)就會少,由於切換次數少,則回應時間(response time)就會上升。

b. Average turnaround time and maximum waiting time: Average turnaround time is minimized by executing the shortest tasks first. Such a scheduling policy could, however, starve long-running tasks and thereby increase their waiting time.
平均運作時間(average turnaround time) 的最小化可以藉由最短工作優先的方式,但是這將會使得長工作飢餓,如此會增加最大等待時間。

c. I/O device utilization and CPU utilization: CPU utilization is maximized by running long-running CPU-bound tasks without performing context switches. I/O device utilization is maximized by scheduling I/O-bound jobs as soon as they become ready to run, thereby incurring the overheads of context switches.
CPU 使用率的上升盡可能讓 CPU 密集工作長時間運行 (減少 IO 或者其他的中斷所引發的上下文切換),IO 裝置使用率的上升靠的是讓排入的 IO 密集工作立即地運行,但這會增加上下文切換的開銷。

  • 5.11 Consider the exponential average formula used to predict the length of the next CPU burst.What are the implications of assigning the following values to the parameters used by the algorithm?
    使用指數平均公式去預測下一次的 CPU burst。 t0 預估時間。
    a. a = 0 and t0 = 100 milliseconds
    b. a = 0.99 and t0 = 10 milliseconds

Answer: When a = 0 and t0 = 100 milliseconds, the formula always makes a prediction of 100 milliseconds for the next CPU burst. When a = 0.99 and t0 = 10 milliseconds, themost recent behavior of the process is given much higher weight than the past history associated with the process. Consequently, the scheduling algorithm is almost memoryless, and simply predicts the length of the previous burst for the next quantum of CPU execution.
當 a = 0 時,預測的時間總會是 100 milliseconds,而當 a = 0.99 時,將會高度依賴近期幾次的結果,而對於歷史關聯只有較輕的權重。
// t(n+1) = a * 上一次實際時間 + (1 - a) * t(n)

Reference

Kernel Mode 與 User Mode 的概念
恐龍書中文 ppt 介紹 聯合大學 陳士杰

Read More +

Nodejs 初學上手

網站利器

簡介

寫網站對筆者來說是第一次,只有看過別人用 PHP framework 架站,會用到 SQL 語法,還要搭配前端的 CSS、javascript,到現在 javascript 和 CSS 都仍不熟,那這麼還寫一篇文章出來害人呢。

Nodejs 出來後,一個完全 javascript 的環境,撇開了 Apache,只剩下 Javascript 和前端頁面!

前置作業

您需要會點,倒不如說吾就這點程度。

  • HTML 基礎文本語法,能夠造出靜態網頁。
  • Javascript

環境安裝

  • 安裝 NodeJs
  • 安裝 MongoDB
  • 安裝 WebMatrix
    非必要,但是開專案後大體上就會棄,用 Sublime 編輯。其實是因為到了 express 網站,也看不懂要去哪裡下什麼指令指令去安裝架設。

目標

知道 Nodejs 在做什麼,並且用它來寫網站。

歷程

一開始被丟了相當大的問題,原因是當下根本不清楚 Nodejs 是什麼,於是小夥伴們先丟了一個 七天學會 Nodejs 的鏈結給我。

就一股腦地走馬看花,同時也看了很多篇相關於 Nodejs 的文章,但仍壓根不知其何物,只有見識到相當多的指令說明,果然還真必須實作一番才能理解。

    慧根嚴重不足,請多多見諒

以前可能用過 Apache,但也不知道其功能,只知道可以幫助將資料藉由 port 80 傳出去,而且還因為某個軟件自帶的安裝 Apache ,其中漏洞導致成為殭屍網路的一群發動攻擊。那件往事還真是難忘,在宿舍還被鎖網。

Nodejs 相當強,全部基於 javascript 可以運行讀檔寫檔還有架站,php 的功能全都包了,但是對於 SQL 資料庫的部分,由於 Nodejs 的操作插件都是在 NPM 平台上,有什麼需求都必須去那邊下載使用。大多數使用 Nodejs 搭配 mongoDB,就相當於 php 搭配 MySQL。

因此藉由上述內容,請明白 Nodejs 和 NPM 是同時灌的,就像 java application 必須有 import library 使用。

換了語言換了腦袋,真的只認為是換語言如此單純的事情嗎?

對於架站 framework 來說,應該不少有人用過 php framework,如果不明白 framework 也沒關係,現在動手去查。看完之後再去查查 MVC MVP MVVM。總之,如果在大學寫過一點程式,多少都會明白自幹框架是多麻煩的事情,但也是好修好改的開始。這裡不談 php framework,nodejs 有一個 express 的 framework,基於我的無知,看不懂官方網站如何指導安裝,那使用邪惡 Windows WebMatrix 提供的網頁開發方式,先快速開啟專案。

後來是明白 express 的安裝方式,express github 上的 README.md 說得相當清楚,這時也要培養看完 README.md 再行動的習慣。

打開 express 專案,一定會發現有數個未知附檔名的出現,大多是 .jade,不要太擔心, jade 檔案就是 html 基於縮排而成的語言,相當精簡且可以根據 express 架構導入變數值。

如果要為這個專案下的 server.js (舊版命名為 app.js) 增加新的模組套用怎麼做?

yourProject/folder/
1
$ npm link modulesName

如果原本使用下述安裝至作業系統,則在 server.js 則不會發生找不到模組的問題。

anywhere
1
$ npm install -g modulesName

接著你會發現專案下 node_modules 會有無數你在 server.js 中 require 的模組內容,同時也會發現模組下又有相依模組,可以層層查閱,這是一個很有趣的現象,不知道模組與模組下會不會有相同相依模組存在。看起來可以猜測為-有。

專案都開啟了,最關注於 CSS 和 JQuery 怎麼灌輸進去。

project/views/layout.jade
1
2
3
4
5
6
7
8
9
10
11
12
doctype 5
html
head
title= title
link(rel='stylesheet', href='/stylesheets/style.css')
link(rel='stylesheet', href='/stylesheets/ui-darkness/jquery-ui-1.10.4.custom.css')
link(rel='stylesheet', href='/stylesheets/webstyle.css')
script(src='/javascripts/jquery-1.10.2.js')
script(src='/javascripts/jquery-ui-1.10.4.custom.js')
body
block content
<script src='/javascripts/global.js'></script>

而你的 javascript file 就在 project/public/javascript 下,而 CSS 則在 project*public/stylesheets 下,頓時心中一塊大石頭放下了,在還沒調用資料庫前,至少靜態網頁能在 express 運行中出現。

先談到這裡了,要用 express 架出完整的網站,還要走段 mongoDB 的運用,還要學會 jade 的撰寫方式。

其實學到 nodejs express 後,第一個挖到的是 Hexo blog 的製作,也就是你眼前所見的網站。這是一個基於 nodejs 下的套件,使用 markdown 編撰文章,雖然沒有文章線上編輯,幾乎靠者純文字檔的方式運行,為了架設這個頁面,費盡了一番苦心想要進行搬家工程。

如何進行搬家工程? 爬蟲 對吧?那要用什麼語言進行爬蟲,沒錯!就是剛學到的 Nodejs,可是要轉換成 markdown file 耶,之後是失敗了,因為有很多 CSS 上的問題,轉換一直不理想。

如何架出第一個有 ajax 和 database 的 express 網站,可以查閱下方鏈結。

Resource & Reference

Read More +