存档:2009年一月

2009没有标题的标题

一月 31, 2009 | 心情杂记 | RSS 2.0

年终于过完了,总的来说还是挺高兴的,主要是能和亲人聚聚,和老同学说说话,共同回忆一点往事,也算是幸福吧,回忆过去的懵懂,过去的无知,也许是真的随着年龄的增大人会越来越会回忆往事,事物矛盾的,得到的同时总让你失去点什么,再过一年弟弟,妹妹都要结婚了,留下我孤苦伶仃的,呵呵,祝贺他们,特别是我妹妹为了我上大学高中,付出了不少,初中未毕业都出去打拼。吃了好多苦头。有时候静静的想想,总觉得欠她好多,可是有时候到了面前,又说不出口,希望她能一直 走好。不说这些了,说说我的2009吧。
希望我的爱情磨合的更加稳定
希望我的知识更加宽广扎实
希望我的做人更加成功
希望我的专业学的更加牛逼
希望我的事业在进步
为此我会付出努力,我知道凡事预则立,不预则废,所以一定要拿出点计划。不然又会被荒废。
2009这个一年跟有意义,不论对我的人生还是家人。这个几年一定要好好学,好好干,肯吃苦。

大致想到的学习 的好习惯
把学习当成自己的嗜好,兴趣
1 坚持看google reader
2 写doc文档
3 天天登陆chinaunix
4 坚持linux下的c语言
5基础知识有时候的学习
6专业外知识的学习
7 php的追求跟高
6 架构方面
7 嵌入式的

没有评论 »

intro to Caching,Caching algorithms and caching frameworks

一月 22, 2009 | c/c++, 数据结构算法 | RSS 2.0

intro to Caching,Caching algorithms and caching frameworks part 1

parti

Introduction:

Alot of us heard the word cache and when you ask them about caching theygive you a perfect answer but they don’t know how it is built, or onwhich criteria I should favor this caching framework over that one andso on, in this article we are going to talk about Caching, CachingAlgorithms and caching frameworks and which is better than the other.

The Interview:

“Cachingis a temp location where I store data in (data that I need itfrequently) as the original data is expensive to be fetched, so I canretrieve it faster. “

That what programmer 1 answered in theinterview (one month ago he submitted his resume to a company whowanted a java programmer with a strong experience in caching andcaching frameworks and extensive data manipulation)

Programmer 1did make his own cache implementation using hashtable and that what heonly knows about caching and his hashtable contains about 150 entrywhich he consider an extensive data(caching = hashtable, load thelookups in hashtable and everything will be fine nothing else) so letssee how will the interview goes.

Interviewer: Nice and based on what criteria do you choose your caching solution?

Programmer 1 :huh, (thinking for 5 minutes) , mmm based on, on , on the data (coughing…)

Interviewer: excuse me! Could you repeat what you just said again?

Programmer 1: data?!

Interviewer: oh I see, ok list some caching algorithms and tell me which is used for what

Programmer 1 :( staring at the interviewer and making strange expressions with hisface, expressions that no one knew that a human face can do :D )

Interviewer: ok, let me ask it in another way, how will a caching behave if it reached its capacity?

Programmer 1:capacity? Mmm (thinking… hashtable is not limited to capacity I can addwhat I want and it will extend its capacity) (that was in programmer 1mind he didn’t say it)

The Interviewer thanked programmer 1 (theinterview only lasted for 10minutes) after that a woman came and said:oh thanks for you time we will call you back have a nice day
Thiswas the worst interview programmer 1 had (he didn’t read that there wasa part in the job description which stated that the candidate shouldhave strong caching background ,in fact he only saw the line talkingabout excellent package ;) )

Talk the talk and then walk the walk

Afterprogrammer 1 left he wanted to know what were the interviewer talkingabout and what are the answers to his questions so he started to surfthe net, Programmer 1 didn’t know anything else about caching except:when I need cache I will use hashtable
After using his favorite search engine he was able to find a nice caching article and started to read.

Why do we need cache?

Longtime ago before caching age user used to request an object and thisobject was fetched from a storage place and as the object grow biggerand bigger, the user had spend more time to fulfill his request, itreally made the storage place suffer a lot coz it had to be working forthe whole time this caused both the user and the db to be angry andthere were one of 2 possibilities

1- The user will get upset and complain and even wont use this application again(that was the case always)

2-The storage place will pack up its bags and leave your application ,and that made a big problems(no place to store data) (happened in raresituations )

Caching is a god sent:

After few years researchers at IBM (in 60s) introduced a new concept and named it “Cache”

What is Cache?

Cachingis a temp location where I store data in (data that I need itfrequently) as the original data is expensive to be fetched, so I canretrieve it faster.

Caching is made of pool of entries and theseentries are a copy of real data which are in storage (database forexample) and it is tagged with a tag (key identifier) value for retrieval.
Great so programmer 1 already knows this but what he doesn’t know is caching terminologies which are as follow:

Cache Hit:

Whenthe client invokes a request (let’s say he want to view productinformation) and our application gets the request it will need toaccess the product data in our storage (database), it first checks thecache.

If an entry can be found with a tag matching that of the desired data (say product Id), the entry is used instead. This is known as a cache hit (cache hit is the primary measurement for the caching effectiveness we will discuss that later on).
And the percentage of accesses that result in cache hits is known as the hit rate or hit ratio of the cache.

Cache Miss:

On the contrary when the tag isn’t found in the cache (no match were found) this is known as cache miss, a hit to the back storage is made and the data is fetched back and itis placed in the cache so in future hits it will be found and will makea cache hit.

If we encountered a cache miss there can be either a scenarios from two scenarios:

First scenario:there is free space in the cache (the cache didn’t reach its limit andthere is free space) so in this case the object that cause the cache miss will be retrieved from our storage and get inserted in to the cache.

Second Scenario: there is no free space in the cache (cache reached its capacity) so the object that cause cache misswill be fetched from the storage and then we will have to decide whichobject in the cache we need to move in order to place our newly createdobject (the one we just retrieved) this is done by replacement policy (caching algorithms) that decide which entry will be remove to make more room which will be discussed below.

Storage Cost:

Whena cache miss occurs, data will be fetch it from the back storage, loadit and place it in the cache but how much space the data we justfetched takes in the cache memory? This is known as Storage cost

Retrieval Cost:

And when we need to load the data we need to know how much does it take to load the data. This is known as Retrieval cost

Invalidation:

Whenthe object that resides in the cache need is updated in the backstorage for example it needs to be updated, so keeping the cache up todate is known as Invalidation.
Entry will be invalidate from cache and fetched again from the back storage to get an updated version.

Replacement Policy:

Whencache miss happens, the cache ejects some other entry in order to makeroom for the previously uncached data (in case we don’t have enoughroom). The heuristic used to select the entry to eject is known as the replacement policy.

Optimal Replacement Policy:

The theoretically optimal page replacement algorithm (also known as OPT or Belady’s optimal page replacement policy)is an algorithm that tries to achieve the following: when a cachedobject need to be placed in the cache, the cache algorithm shouldreplace the entry which will not be used for the longest period of time.

Forexample, a cache entry that is not going to be used for the next 10seconds will be replaced by an entry that is going to be used withinthe next 2 seconds.

Thinking of the optimal replacement policy wecan say it is impossible to achieve but some algorithms do near optimalreplacement policy based on heuristics.
So everything is based on heuristics so what makes algorithm better than another one? And what do they use for their heuristics?

Nightmare at Java Street:

While reading the article programmer 1 fall a sleep and had nightmare (the scariest nightmare one can ever have)

Programmer 1: nihahha I will invalidate you. (Talking in a mad way)

Cached Object: no no please let me live, they still need me, I have children.

Programmer 1: all cached entries say that before they are invalidated and since when do you have children? Never mind now vanish for ever.

Buhaaahaha, laughed programmer 1 in a scary way, ,silence took over the place forfew minutes and then a police serine broke this silence, police caughtprogrammer 1 and he was accused of invalidating an entry that was stillneeded by a cache client, and he was sent to jail.

Programmer 1work up and he was really scared, he started to look around andrealized that it was just a dream then he continued reading aboutcaching and tried to get rid of his fears.

Caching Algorithms:

No one can talk about caching algorithms better than the caching algorithms themselves

Least Frequently Used (LFU):

I am Least Frequently used; I count how often an entry is needed by incrementing a counter associated with each entry.

Iremove the entry with least frequently used counter first am not thatfast and I am not that good in adaptive actions (which means that itkeeps the entries which is really needed and discard the ones thataren’t needed for the longest period based on the access pattern or inother words the request pattern)

Least Recently Used (LRU):

Iam Least Recently Used cache algorithm; I remove the least recentlyused items first. The one that wasn’t used for a longest time.

Irequire keeping track of what was used when, which is expensive if onewants to make sure that I always discards the least recently used item.
Webbrowsers use me for caching. New items are placed into the top of thecache. When the cache exceeds its size limit, I will discard items fromthe bottom. The trick is that whenever an item is accessed, I place atthe top.

So items which are frequently accessed tend to stay inthe cache. There are two ways to implement me either an array or alinked list (which will have the least recently used entry at the backand the recently used at the front).

I am fast and I amadaptive in other words I can adopt to data access pattern, I have alarge family which completes me and they are even better than me (I dofeel jealous some times but it is ok) some of my family member are(LRU2 and 2Q) (they were implemented in order to improve LRU caching

Least Recently Used 2(LRU2):

Iam Least recently used 2, some people calls me least recently usedtwice which I like it more, I add entries to the cache the second timethey are accessed (it requires two times in order to place an entry inthe cache); when the cache is full, I remove the entry that has asecond most recent access. Because of the need to track the two mostrecent accesses, access overhead increases with cache size, If I amapplied to a big cache size, that would be a problem, which can be adisadvantage. In addition, I have to keep track of some items not yetin the cache (they aren’t requested two times yet).I am better that LRUand I am also adoptive to access patterns.

-Two Queues:

Iam Two Queues; I add entries to an LRU cache as they are accessed. Ifan entry is accessed again, I move them to second, larger, LRU cache.

Iremove entries a so as to keep the first cache at about 1/3 the size ofthe second. I provide the advantages of LRU2 while keeping cache accessoverhead constant, rather than having it increase with cache size.Which makes me better than LRU2 and I am also like my family, amadaptive to access patterns.

Adaptive Replacement Cache (ACR):

Iam Adaptive Replacement Cache; some people say that I balance betweenLRU and LFU, to improve combined result, well that’s not 100% trueactually I am made from 2 LRU lists, One list, say L1, contains entriesthat have been seen only once “recently”, while the other list, say L2,contains entries that have been seen at least twice “recently”.

Theitems that have been seen twice within a short time have a lowinter-arrival rate, and, hence, are thought of as “high-frequency”.Hence, we think of L1as capturing “recency” while L2 as capturing“frequency” so most of people think I am a balance between LRU and LFUbut that is ok I am not angry form that.

I am considered one ofthe best performance replacement algorithms, Self tuning algorithm andlow overhead replacement cache I also keep history of entries equal tothe size of the cache location; this is to remember the entries thatwere removed and it allows me to see if a removed entry should havestayed and we should have chosen another one to remove.(I really havebad memory)And yes I am fast and adaptive.

Most Recently Used (MRU):

Iam most recently used, in contrast to LRU; I remove the most recentlyused items first. You will ask me why for sure, well let me tell yousomething when access is unpredictable, and determining the least mostrecently used entry in the cache system is a high time complexityoperation, I am the best choice that’s why.

I am so common inthe database memory caches, whenever a cached record is used; I replaceit to the top of stack. And when there is no room the entry on the topof the stack, guess what? I will replace the top most entry with thenew entry.

First in First out (FIFO):

Iam first in first out; I am a low-overhead algorithm I require littleeffort for managing the cache entries. The idea is that I keep track ofall the cache entries in a queue, with the most recent entry at theback, and the earliest entry in the front. When there e is no place andan entry needs to be replaced, I will remove the entry at the front ofthe queue (the oldest entry) and replaced with the current fetchedentry. I am fast but I am not adaptive

-Second Chance:

HelloI am second change I am a modified form of the FIFO replacementalgorithm, known as the Second chance replacement algorithm, I ambetter than FIFO at little cost for the improvement. I work by lookingat the front of the queue as FIFO does, but instead of immediatelyreplacing the cache entry (the oldest one), i check to see if itsreferenced bit is set(I use a bit that is used to tell me if this entryis being used or requested before or no). If it is not set, I willreplace this entry. Otherwise, I will clear the referenced bit, andthen insert this entry at the back of the queue (as if it were a newentry) I keep repeating this process. You can think of this as acircular queue. Second time I encounter the same entry I cleared itsbit before, I will replace it as it now has its referenced bit cleared.am better than FIFO in speed

-Clock:

I amClock and I am a more efficient version of FIFO than Second chancebecause I don’t push the cached entries to the back of the list likeSecond change do, but I perform the same general function asSecond-Chance.

I keep a circular list of the cached entries inmemory, with the “hand” (something like iterator) pointing to theoldest entry in the list. When cache miss occurs and no empty placeexists, then I consult the R (referenced) bit at the hand’s location toknow what I should do. If R is 0, then I will place the new entry atthe “hand” position, otherwise I will clear the R bit. Then, I willincrement the hand (iterator) and repeat the process until an entry isreplaced.I am faster even than second chance.

Simple time-based:

Iam simple time-based caching; I invalidate entries in the cache basedon absolute time periods. I add Items to the cache, and they remain inthe cache for a specific amount of time. I am fast but not adaptive foraccess patterns

Extended time-based expiration:

Iam extended time based expiration cache, I invalidate the items in thecache is based on relative tim …

没有评论 »

Linux下的管道编程技术 dup dup2 popen(转)

一月 20, 2009 | c/c++, linux | RSS 2.0

管道技术是Linux的一种基本的进程间通信技术。在本文中,我们将为读者介绍管道技术的模型,匿名管道和命名管道技术的定义和区别,以及这两种管道的创建方法。同时,阐述如何在应用程序和命令行中通过管道进行通信的详细方法。 

    一、管道技术模型 

    管道技术是Linux操作系统中历来已久的一种进程间通信机制。所有的管道技术,无论是半双工的匿名管道,还是命名管道,它们都是利用FIFO排队模型来指挥进程间的通信。对于管道,我们可以形象地把它们当作是连接两个实体的一个单向连接器。例如,请看下面的命令:
  

ls -1 | wc -l

    该命令首先创建两个进程,一个对应于ls –1,另一个对应于wc –l。然后,把第一个进程的标准输出设为第二个进程的标准输入(如图1所示)。它的作用是计算当前目录下的文件数量。

图1:管道示意图 

    如上图所示,前面的例子实际上就是在两个命令之间建立了一根管道(有时我们也将之称为命令的流水线操作)。第一个命令ls执行后产生的输出作为了第二个命令wc的输入。这是一个半双工通信,因为通信是单向的。两个命令之间的连接的具体工作,是由内核来完成的。下面我们将会看到,除了命令之外,应用程序也可以使用管道进行连接.

二.信号和消息的区别 我们知道,进程间的信号通信机制在传递信息时是以信号为载体的,但管道通信机制的信息载体是消息。那么信号和消息之间的区别在哪里呢? 

    首先,在数据内容方面,信号只是一些预定义的代码,用于表示系统发生的某一状况;消息则为一组连续语句或符号,不过量也不会太大。在作用方面,信号担任进程间少量信息的传送,一般为内核程序用来通知用户进程一些异常情况的发生;消息则用于进程间交换彼此的数据。 

    在发送时机方面,信号可以在任何时候发送;信息则不可以在任何时刻发送。在发送者方面,信号不能确定发送者是谁;信息则知道发送者是谁。在发送对象方面,信号是发给某个进程;消息则是发给消息队列。在处理方式上,信号可以不予理会;消息则是必须处理的。在数据传输效率方面,信号不适合进大量的信息传输,因为它的效率不高;消息虽然不适合大量的数据传送,但它的效率比信号强,因此适于中等数量的数据传送.三.管道和命名管道的区别
    我们知道,命名管道和管道都可以在进程间传送消息,但它们也是有区别的。 

    管道技术只能用于连接具有共同祖先的进程,例如父子进程间的通信,它无法实现不同用户的进程间的信息共享。再者,管道不能常设,当访问管道的进程终止时,管道也就撤销。这些限制给它的使用带来不少限制,但是命名管道却克服了这些限制。 

    命名管道也称为FIFO,是一种永久性的机构。FIFO文件也具有文件名、文件长度、访问许可权等属性,它也能像其它Linux文件那样被打开、关闭和删除,所以任何进程都能找到它。换句话说,即使是不同祖先的进程,也可以利用命名管道进行通信。 

    如果想要全双工通信,那最好使用Sockets API。下面我们分别介绍这两种管道,然后详细说明用来进行管道编程的编程接口和系统级命令.四.管道编程技术   在程序中利用管道进行通信时,根据通信主体大体可以分为两种情况:一种是具有共同祖先的进程间的通信,比较简单;另一种是任意进程间通信,相对较为复杂。下面我们先从较为简单的进程内通信开始介绍。 

    1. 具有共同祖先的进程间通信管道编程 

    为了了解管道编程技术,我们先举一个例子。在这个例中,我们将在进程中新建一个管道,然后向它写入一个消息,管道读取消息后将其发出。代码如下所示: 

    示例代码1:管道程序示例 

1: #include <unistd.h>
2: #include <stdio.h>
3: #include <string.h>
4:
5: #define MAX_LINE 80

6: #define PIPE_STDIN 0
7: #define PIPE_STDOUT 1
8:
9: int
main()
10: ...
{
11: const char *string=...{"A sample message."}
;
12: int ret, myPipe[2
];
13: char buffer[MAX_LINE+1
];
14
:
15: /**//* 建立管道 */

16: ret = pipe( myPipe );
17
:
18: if (ret == 0) ...
{
19
:
20: /**//* 将消息写入管道 */

21: write( myPipe[PIPE_STDOUT], string, strlen(string) );
22
:
23: /**//* 从管道读取消息 */

24: ret = read( myPipe[PIPE_STDIN], buffer, MAX_LINE );
25
:

没有评论 »

线程

一月 20, 2009 | c/c++, linux | RSS 2.0

线程库

下面简要论述了特定任务及其相关手册页。


创建缺省线程

如果未指定属性对象,则该对象为 NULL,系统会创建具有以下属性的缺省线程:

  • 进程范围

  • 非分离

  • 缺省栈和缺省栈大小

  • 零优先级

还可以用 pthread_attr_init() 创建缺省属性对象,然后使用该属性对象来创建缺省线程。有关详细信息,请参见初始化属性一节。


pthread_create 语法

使用 pthread_create(3C) 可以向当前进程中添加新的受控线程。

int pthread_create(pthread_t *tid, const pthread_attr_t *tattr,

    void*(*start_routine)(void *), void *arg);
#include <pthread.h>

pthread_attr_t() tattr;

pthread_t tid;

extern void *start_routine(void *arg);

void *arg;

int ret; 

/* default behavior*/

ret = pthread_create(&tid, NULL, start_routine, arg);

/* initialized with default attributes */

ret = pthread_attr_init(&tattr);

/* default behavior specified*/

ret = pthread_create(&tid, &tattr, start_routine, arg);

使用具有必要状态行为的 attr 调用 pthread_create() 函数。 start_routine 是新线程最先执行的函数。当 start_routine 返回时,该线程将退出,其退出状态设置为由 start_routine 返回的值。请参见pthread_create 语法

pthread_create() 成功时,所创建线程的 ID 被存储在由 tid 指向的位置中。

使用 NULL 属性参数或缺省属性调用 pthread_create() 时,pthread_create() 会创建一个缺省线程。在对 tattr 进行初始化之后,该线程将获得缺省行为。


pthread_create 返回值

pthread_create() 在调用成功完成之后返回零。其他任何返回值都表示出现了错误。如果检测到以下任一情况,pthread_create() 将失败并返回相应的值。

EAGAIN

描述:

超出了系统限制,如创建的线程太多。

EINVAL

描述:

tattr 的值无效。


等待线程终止

pthread_join() 函数会一直阻塞调用线程,直到指定的线程终止。


pthread_join 语法

使用 pthread_join(3C) 等待线程终止。

int pthread_join(thread_t tid, void **status);
#include <pthread.h>

pthread_t tid;

int ret;

void *status;

/* waiting to join thread "tid" with status */

ret = pthread_join(tid, &status);

/* waiting to join thread "tid" without status */

ret = pthread_join(tid, NULL); 

指定的线程必须位于当前的进程中,而且不得是分离线程。有关线程分离的信息,请参见设置分离状态

status 不是 NULL 时,status 指向某个位置,在 pthread_join() 成功返回时,将该位置设置为已终止线程的退出状态。

如果多个线程等待同一个线程终止,则所有等待线程将一直等到目标线程终止。然后,一个等待线程成功返回。其余的等待线程将失败并返回 ESRCH 错误。

pthread_join() 返回之后,应用程序可回收与已终止线程关联的任何数据存储空间。


pthread_join 返回值

调用成功完成后,pthread_join() 将返回零。其他任何返回值都表示出现了错误。如果检测到以下任一情况,pthread_join() 将失败并返回相应的值。

ESRCH

描述:

没有找到与给定的线程 ID 相对应的线程。

EDEADLK

描述:

将出现死锁,如一个线程等待其本身,或者线程 A 和线程 B 互相等待。

EINVAL

描述:

与给定的线程 ID 相对应的线程是分离线程。

pthread_join() 仅适用于非分离的目标线程。如果没有必要等待特定线程终止之后才进行其他处理,则应当将该线程分离。


简单线程的示例

示例 2–1 中,一个线程执行位于顶部的过程,该过程首先创建一个辅助线程来执行 fetch() 过程。fetch() 执行复杂的数据库查找操作,查找过程需要花费一些时间。

主线程将等待查找结果,但同时还执行其他操作。因此,主线程将执行其他活动,然后通过执行 pthread_join() 等待辅助线程。

将新线程的 pbe 参数作为栈参数进行传递。这个线程参数之所以能够作为栈参数传递,是因为主线程会等待辅助线程终止。不过,首选方法是使用 malloc 从堆分配存储,而不是传递指向线程栈存储的地址。如果将该参数作为地址传递到线程栈存储,则该地址可能无效或者在线程终止时会被重新分配。



示例 2–1 简单线程程序

void mainline (...)

{

        struct phonebookentry *pbe;

        pthread_attr_t tattr;

        pthread_t helper;

        void *status;

        pthread_create(&helper, NULL, fetch, &pbe);

            /* do something else for a while */

        pthread_join(helper, &status);

        /* it's now safe to use result */

}

void *fetch(struct phonebookentry *arg)

{

        struct phonebookentry *npbe;

        /* fetch value from a database */

        npbe = search (prog_name)

            if (npbe != NULL)

                *arg = *npbe;

        pthread_exit(0);

}   

struct phonebookentry {

        char name[64];

        char phonenumber[32];

        char flags[16];

}


分离线程

pthread_detach(3C)pthread_join(3C) 的替代函数,可回收创建时 detachstate 属性设置为 PTHREAD_CREATE_JOINABLE 的线程的存储空间。


pthread_detach 语法

int pthread_detach(thread_t tid);
#include <pthread.h>

pthread_t tid;

int ret;

/* detach thread tid */

ret = pthread_detach(tid); 

pthread_detach() 函数用于指示应用程序在线程 tid 终止时回收其存储空间。如果 tid 尚未终止,pthread_detach() 不会终止该线程。


pthread_detach 返回值

pthread_detach() 在调用成功完成之后返回零。其他任何返回值都表示出现了错误。如果检测到以下任一情况,pthread_detach() 将失败并返回相应的值。

EINVAL

描述:

tid 是分离线程。

ESRCH

描述:

tid 不是当前进程中有效的未分离的线程。


为线程特定数据创建键

单线程 C 程序有两类基本数据:局部数据和全局数据。对于多线程 C 程序,添加了第三类数据:线程特定数据。线程特定数据与全局数据非常相似,区别在于前者为线程专有。

线程特定数据基于每线程进行维护。TSD(特定于线程的数据)是定义和引用线程专用数据的唯一方法。每个线程特定数据项都与一个作用于进程内所有线程的键关联。通过使用 key,线程可以访问基于每线程进行维护的指针 (void *)。


pthread_key_create 语法

int pthread_key_create(pthread_key_t *key,

    void (*destructor) (void *));
#include <pthread.h>

pthread_key_t key;

int ret;

/* key create without destructor */

ret = pthread_key_create(&key, NULL);

/* key create with destructor */

ret = pthread_key_create(&key, destructor); 

可以使用 pthread_key_create(3C) 分配用于标识进程中线程特定数据的。键对进程中的所有线程来说是全局的。创建线程特定数据时,所有线程最初都具有与该键关联的 NULL 值。

使用各个键之前,会针对其调用一次 pthread_key_create()。不存在对键(为进程中所有的线程所共享)的隐含同步。

创建键之后,每个线程都会将一个值绑定到该键。这些值特定于线程并且针对每个线程单独维护。如果创建该键时指定了 destructor 函数,则该线程终止时,系统会解除针对每线程的绑定。

pthread_key_create() 成功返回时,会将已分配的键存储在 key 指向的位置中。调用方必须确保对该键的存储和访问进行正确的同步。

使用可选的析构函数 destructor 可以释放过时的存储。如果某个键具有非 NULL destructor 函数,而线程具有一个与该键关联的非 NULL 值,则该线程退出时,系统将使用当前的相关值调用 destructor 函数。destructor 函数的调用顺序不确定。


pthread_key_create 返回值

pthread_key_create() 在成功完成之后返回零。其他任何返回值都表示出现了错误。如果出现以下任一情况,pthread_key_create() 将失败并返回相应的值。

EAGAIN

描述:

key 名称空间已经用完。

ENOMEM

描述:

此进程中虚拟内存不足,无法创建新键。


删除线程特定数据键

使用 pthread_key_delete(3C) 可以销毁现有线程特定数据键。由于键已经无效,因此将释放与该键关联的所有内存。引用无效键将返回错误。Solaris 线程中没有类似的函数。


pthread_key_delete 语法

int pthread_key_delete(pthread_key_t key);
#include <pthread.h>

pthread_key_t key;

int ret;

/* key previously created */

ret = pthread_key_delete(key); 

如果已删除,则使用调用 pthread_setspecific()pthread_getspecific() 引用该键时,生成的结果将是不确定的。

程序员在调用删除函数之前必须释放所有线程特定资源。删除函数不会调用任何析构函数。反复调用 pthread_key_create()pthread_key_delete() 可能会产生问题。如果 pthread_key_delete() 将键标记为无效,而之后 key 的值不再被重用,那么反复调用它们就会出现问题。对于每个所需的键,应当只调用 pthread_key_create() 一次。


pthread_key_delete 返回值

pthread_key_delete() 在成功完成之后返回零。其他任何返回值都表示出现了错误。如果出现以下情况,pthread_key_delete() 将失败并返回相应的值。

EINVAL

描述:

key 的值无效。


设置线程特定数据

使用 pthread_setspecific(3C) 可以为指定线程特定数据键设置线程特定绑定。


pthread_setspecific 语法

int pthread_setspecific(pthread_key_t key, const void *value);
#include <pthread.h>

pthread_key_t key;

void *value;

int ret;

/* key previously created */

ret = pthread_setspecific(key, value); 


pthread_setspecific 返回值

pthread_setspecific() 在成功完成之后返回零。其他任何返回值都表示出现了错误。如果出现以下任一情况,pthread_setspecific() 将失败并返回相应的值。

ENOMEM

描述:

虚拟内存不足。

EINVAL

描述:

key 无效。


注 –

设置新绑定时,pthread_setspecific() 不会释放其存储空间。必须释放现有绑定,否则会出现内存泄漏。



获取线程特定数据

请使用 pthread_getspecific(3C) 获取调用线程的绑定,并将该绑定存储在 value 指向的位置中。


pthread_getspecific 语法

void *pthread_getspecific(pthread_key_t key);
#include <pthread.h>

pthread_key_t key;

void *value;

/* key previously created */

value = pthread_getspecific(key); 


pthread_getspecific 返回值

pthread_getspecific 不返回任何错误。


全局和专用线程特定数据的示例

示例 2–2 显示的代码是从多线程程序中摘录出来的。这段代码可以由任意数量的线程执行,但该代码引用了两个全局变量:errnomywindow。这些全局值实际上应当是对每个线程专用项的引用。



示例 2–2 线程特定数据-全局但专用

body() {

    ...

    while (write(fd, buffer, size) == -1) {

        if (errno != EINTR) {

            fprintf(mywindow, "%s", strerror(errno));

            exit(1);

        }

    }

    ...

}

errno 引用应该从线程所调用的例程获取系统错误,而从其他线程所调用的例程获取系统错误。因此,线程不同,引用 errno 所指向的存储位置也不同。

mywindow 变量指向一个 stdio (标准 IO)流,作为线程专属的流窗口。因此,与 errno 一样,线程不同,引用 mywindow 所指向的存储位置也不同。最终,这个引用指向不同的流窗口。唯一的区别在于系统负责处理 errno,而程序员必须处理对 mywindow 的引用。

下一个示例说明对 mywindow 的引用如何工作。预处理程序会将对 mywindow 的引用转换为对 _mywindow() 过程的调用。

此例程随后调用 pthread_getspecific()pthread_getspecific() 接收 mywindow_key 全局变量作为输入参数,以输出参数 win 返回该线程的窗口。



示例 2–3 将全局引用转化为专用引用

thread_key_t mywin_key;

FILE *_mywindow(void) {

    FILE *win;

    win = pthread_getspecific(mywin_key);

    return(win);

}

#define mywindow _mywindow()

void routine_uses_win( FILE *win) {

    ...

}

void thread_start(...) {

    ...

    make_mywin();

    ...

    routine_uses_win( mywindow )

    ...

}

mywin_key 变量标识一类变量,对于该类变量,每个线程都有其各自的专用副本。这些变量是线程特定数据。每个线程都调用 make_mywin() 以初始化其时限并安排其 mywindow 实例以引用线程特定数据。

调用此例程之后,此线程可以安全地引用 mywindow,调用 _mywindow() 之后,此线程将获得对其专用时限的引用。引用 mywindow 类似于直接引用线程专用数据。

示例 2–4 说明如何设置引用。



示例 2–4 初始化线程特定数据

void make_mywindow(void) {

    FILE **win;

    static pthread_once_t mykeycreated = PTHREAD_ONCE_INIT;

    pthread_once(&mykeycreated, mykeycreate);

    win = malloc(sizeof(*win));

    create_window(win, ...);

    pthread_setspecific(mywindow_key, win);

}

void mykeycreate(void) {

    pthread_key_create(&mywindow_key, free_key);

}

void free_key(void *win) {

    free(win);

}

首先,得到一个唯一的键值,mywin_key。此键用于标识线程特定数据类。第一个调用 make_mywin() 的线程最终会调用 pthread_key_create(),该函数将唯一的 key 赋给其第一个参数。第二个参数是 destructor 函数,用于在线程终止后将该线程的特定于该线程的数据项实例解除分配。

接下来为调用方的线程特定数据项的实例分配存储空间。获取已分配的存储空间,调用 create_window(),以便为该线程设置时限。win 指向为该时限分配的存储空间。最后,调用 pthread_setspecific(),将 win 与该键关联。

以后,每当线程调用 pthread_getspecific() 以传递全局 key,线程都会获得它在前一次调用 pthread_setspecific() 时设置的与该键关联的值)。

线程终止时,会调用在 pthread_key_create() 中设置的 destructor 函数。每个 destructor 函数仅在终止线程通过调用 pthread_setspecific()key 赋值之后才会被调用。


获取线程标识符

请使用 pthread_self(3C) 获取调用线程的 thread identifier


pthread_self 语法

pthread_t  pthread_self(void);
#include <pthread.h>

pthread_t tid;

tid = pthread_self();


pthread_self 返回值

pthread_self() 返回 …

没有评论 »

read proc cpuinfo

一月 9, 2009 | linux | RSS 2.0

学习过了devic一章,基本上都是常见的设备的概念介绍 ,开始proc,

#include <stdio.h>
#include <string.h>
float get_cpu_clock_speed ()
{
  FILE* fp;
  char buffer[1024];
  size_t bytes_read;
  char* match;
  float clock_speed;

  fp =fopen(”/proc/cpuinfo”,”r”);
  bytes_read = fread(buffer,1,sizeof(buffer),fp);
  fclose(fp);
  printf(”2xxxxxxxx%s”,buffer);
    if(0 == bytes_read || sizeof(buffer) == bytes_read)
    return 0;
  buffer[bytes_read]=’0′;
  printf(”hello word”);p
  match = strstr(buffer,”cpu MHz”);
  if(match == NULL)
    return 0;
  sscanf(match,”cpu MHz:%s”,&clock_speed);
  return clock_speed;

}
int main()  {

    printf(”cpu clock speed :%4.0f MHz”,get_cpu_clock_speed());
    return 0;
}

没有评论 »

奎伯的杯子问题 对自己思维模式的思考

一月 8, 2009 | 数学, 数据结构算法, 读书 | RSS 2.0

 a.巴尼在饮店工作,他给他的两位顾客表演10个杯子游戏。  
 b.巴尼:这有一排10个杯子,前5个杯子装着可乐,后5个杯子空着,你能挪4个杯子,使满杯和空杯间隔排列吗?   
 c.巴尼:好,只需第2个杯子和第7个杯子交换位置,第4个杯子和第9个杯子交换位置。  
 d.奎伯教授总想一些奇特的方法,碰巧听到了这个问题。
奎伯教授:为什么要挪4个杯子,我们能否只动2个杯子?
 e.奎伯教授:很简单,把第2个杯中的可乐倒进第7个杯中,把第4个杯中的可乐倒进第9个杯中。           
不寻常的奎伯
尽管奎伯教授通过巧辩解决了这个问题,但普遍问题并不像这个问题这么平常。例如,同样的问题,如果是100个满杯和100个空杯需要对调多少次才能使满杯和空杯间隔排列? 
用200个杯子做实验不很实际,我们首先分析较小的n值的解决方法,这里n是满杯或空杯数。你可以用两种颜色的记号来解题(或者牌的正反面、硬币的正反面、不同面值的硬币等等)当n=1时无解。n=2时显然只对调一次。n=3时也对调一次。进一步努力,你可以发现简单的公式,n是偶数时,对调数为n/2。n是奇数时,为(n—1)/2。所以,如果是100个满杯和100个空杯,需要对调50次。 
这需要移动100个杯子,奎伯的幽默作法把移动杯数减少了一半。
又有一个类似的分隔同题,但比较难解。在同一排中有n个一类物体,相邻的是n个另一类物体(如上面用玻璃杯、记号、牌等来表示)你还是要把这一排列变为互相间隔状态,但我们移动原则不同了。我们必须移动一对记号放到队列中任何空白处,移动中不能改变这两个记号的顺序。例如,这是n=3时的做法:

XXXOOO
  XOOOXX
  X00  XOX
    OXOXOX 
一般的解法是什么呢?n=1时无解。你很快也发现,n=2时也无解。对所有大于2的n,最小的移动次数是n。 
当n=4时,解决这个同题就很不易,或许你已经解决了,或许当n大于等于3时你能用公式来表示这个问题的解。
这些问题变化一下,可以产生一些其它的难题:
(1)规则同前,只是当你移动一对记号时,如果是不同颜色的,在移动前交换它们的位置。也就是黑红对在移动前变为红黑对,8个记号移动5次可以完成,10个记号移动5次也可以完成。我们还不知道一般的解决方法,或许你能找到。
(2)规则和原题一样,只是一种颜色的记号有n个,另一种颜色的记号有n+1个,并且只有颜色不同的一对才能移动。可以证明:无论n为何值,都需移动n2次,且这是最小的移动次数。 
(3)三种不同颜色的记号,移动每对相邻的记号使三种颜色相互间隔,如果n=3(即总共9个记号)需移5次。在以上的变化中,我们都设变化为最后排列时排列中没有空隙,如果允许空隙存住,移动4次就能得到结果

一些变化的假设迄今还没有提出来,更不必说解决了。比如,在以上的变化中,一次移动3个或更多相邻记号。
还有,如果先移动1个记号,再移动2个相邻的记号,接下来是3个以至4个等等。已知各有n个两种颜色的记号,移动n次能解决问题吗?
第二个问题。

a.奎伯教授又给你出了一个难题。
奎伯教授:拿3个空塑料杯,放进11便士的硬币,使得每个杯中的数是奇数。
b.奎伯教授:这并不难,可以有许多办法。你可以一个杯里放3个,一个杯里放7个,第3个杯里放1个。
c.奎伯教授:但是,你能在3个杯中放10个便士使每个杯中仍是奇数吗?这是可能的,但需要你想一个巧妙的办法。
d.奎伯教授:我希望你锲而不舍,你所要做的就是把一个杯子放进另一个杯子中去,这不是很容易吗?每个杯子中就都是奇数了。

通过把一个杯子放进另一个杯子的灵感解决了奎伯的智力难题。同一组硬币可以属于不止一个杯子。用集合理论用语,我们的答案是一个7元素的集合加上一个3元素的集合,这个3元素的集合包括一个单元素子集。这个答案也可以用如下的圆表示:

 

你可能找到了其它的答案。很容易找到10个答案,但总共能找到15个答案。

 

找到这15个答案以后,你就可以通过硬币数的变化,杯子数的变化以及每个杯子中硬币数的变化对这个问题归纳总结。

没有评论 »

啊哈,灵机一动乒乓问题

一月 8, 2009 | 数学, 数据结构算法, 读书 | RSS 2.0

这个是在书上看到的,乒乓问题,
 a.米拉德·费尔默中学乒乓球俱乐部的5名成员决定举办一次淘汰赛。  
 b.教练解释他的比赛安排。
教练:5是一个奇数,所以第一轮比赛一名队员轮空。第二轮比赛仍有一个轮空,需比赛4场。  
 c.第二年乒乓球运动非常流行,俱乐部已拥有37名成员。教练还是按使轮空次数最少来安排比赛,你能算出要比多少场吗?
 d.你还没算出来吗?你还在画表吗?你失去了好机会!每场比赛淘汰一名队员,有36名队员要被淘汰,要比36场,对吗?

有多少人轮空

 

如果你用直观的方法解决这个问题,你可以实际画一下37个人实际的比赛表。你可以看到无论怎样画,总有4个轮空。轮空数是比赛者人数n的函数,怎样来计算这个数呢?

 

n已知,可按如下方祛确定轮空数。用2的最小指数幂,要求它大于等于n,减去n,差额用二进制来表示。二进制表达式中1的个数就是转空数。在我们的例子中,我们用64(26)减去37得到27,用二进制表示27=11011,有4个1,所以比赛中共有4个轮空,这是满足这种奇妙算法的有趣验证。

 

这种问题所描述的比赛被称为是淘汰赛。计算机专家们总结这种算法是通过成对比较,确定一组几个元素中最大元素。我们看到要确定最大值,实际需要n-1次比较,计算机处理器可以比较3组,4组,5组等等这样的集合。

 

数据处理这个问题在计算机理论和应用上非常重要,所有的书都阐述这个问题。你可以很容易想到许多实际问题在数据处理方面的重要性。据估计,在科技、商业和工业方面花费在数据处理问题上的计算时间要占计算机运行时间的1/4

我的思考是37对2移位,移动以为如果是对2取摸等于0则轮空的人数加1。

没有评论 »

Design pattern (computer science) and linux study site

一月 7, 2009 | 软件工程/编程技巧/设计模式 | RSS 2.0

发现wikipedia的设计模式讲的还不错,而且还带各种代码,学习学习
http://en.wikipedia.org/wiki/Design_pattern_(computer_science)
20  http://ubuntu:ubuntuftp@ftp.ubuntu.org.cn/   
21.         http://mirrors.huihoo.org/       
23.         http://bingle.pku.edu.cn          、
24.         http://so.hustonline.net/
25.         ftp://ftp:ftp@www.chinalinux.org.cn/
26     http://www.fdigg.net/
 

没有评论 »

socket ipc

一月 6, 2009 | c/c++, linux | RSS 2.0

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/socket.h>
#include <sys/un.h>
#include <unistd.h>

/* Read text from the socket and print it out.  Continue until the
   socket closes.  Return non-zero if the client sent a “quit”
   message, zero otherwise.  */

int server (int client_socket)
{
  while (1) {
    int length;
    char* text;

    /* First, read the length of the text message from the socket.  If
       read returns zero, the client closed the connection.  */
    if (read (client_socket, &length, sizeof (length)) == 0)
      return 0;
    /* Allocate a buffer to hold the text.  */
    text = (char*) malloc (length);
    /* Read the text itself, and print it.  */
    read (client_socket, text, length);
    printf (”%s”, text);
    /* Free the buffer.  */
    free (text);
    /* If the client sent the message “quit”, we’re all done.  */
    if (!strcmp (text, “quit”))
      return 1;
  }
}

int main (int argc, char* const argv[])
{
  const char* const socket_name = argv[1];
  int socket_fd;
  struct sockaddr_un name;
  int client_sent_quit_message;

  /* Create the socket.  */
  socket_fd = socket (PF_LOCAL, SOCK_STREAM, 0);
  /* Indicate this is a server.  */
  name.sun_family = AF_LOCAL;
  strcpy (name.sun_path, socket_name);
  bind (socket_fd, &name, SUN_LEN (&name));
  /* Listen for connections.  */
  listen (socket_fd, 5);

  /* Repeatedly accept connections, spinning off one server() to deal
     with each client.  Continue until a client sends a “quit” message.  */
  do {
    struct sockaddr_un client_name;
    socklen_t client_name_len;
    int client_socket_fd;

    /* Accept a connection.  */
    client_socket_fd = accept (socket_fd, &client_name, &client_name_len);
    /* Handle the connection.  */
    client_sent_quit_message = server (client_socket_fd);
    /* Close our end of the connection.  */
    close (client_socket_fd);
  }
  while (!client_sent_quit_message);

  /* Remove the socket file.  */
  close (socket_fd);
  unlink (socket_name);

  return 0;
}

#include <stdio.h>
#include <string.h>
#include <sys/socket.h>
#include <sys/un.h>
#include <unistd.h>

/* Write TEXT to the socket given by file descriptor SOCKET_FD.  */

void write_text (int socket_fd, const char* text)
{
  /* Write the number of bytes in the string, including
     NUL-termination.  */
  int length = strlen (text) + 1;
  write (socket_fd, &length, sizeof (length));
  /* Write the string.  */
  write (socket_fd, text, length);
}

int main (int argc, char* const argv[])
{
  const char* const socket_name = argv[1];
  const char* const message = argv[2];
  int socket_fd;
  struct sockaddr_un name;

  /* Create the socket.  */
  socket_fd = socket (PF_LOCAL, SOCK_STREAM, 0);
  /* Store the server’s name in the socket address.  */
  name.sun_family = AF_LOCAL;
  strcpy (name.sun_path, socket_name);
  /* Connect the socket.  */
  connect (socket_fd, &name, SUN_LEN (&name));
  /* Write the text on the command line to the socket.  */
  write_text (socket_fd, message);
  close (socket_fd);
  return 0;
}

没有评论 »

lighttpd源代码一窥

一月 6, 2009 | linux | RSS 2.0

无意间lighttpd的源代码,发现一处跟平常实现不同的函数,就是字母转换大小写。验证。

int light_isdigit(int c) {        return (c >= '0' && c <= '9');}这个很好理解。不说了int light_isxdigit(int c) {        if (light_isdigit(c)) return 1;        c |= 32;        return (c >= 'a' && c <= 'f');}这个主要是c |=32用的好,查看asii码表可以知道,a-z的-范围在97到127之间int light_isalpha(int c)        c |= 32;        return (c >= 'a' && c <= 'z');}int light_isalnum(int c) {        return light_isdigit(c) || light_isalpha(c);}int buffer_to_lower(buffer *b) {        char *c;        if (b->used == 0) return 0;        for (c = b->ptr; *c; c++) {                if (*c >= 'A' && *c <= 'Z') {                        *c |= 32;                }        }        return 0;}int buffer_to_upper(buffer *b) {        char *c;        if (b->used == 0) return 0;        for (c = b->ptr; *c; c++) {                if (*c >= 'a' && *c <= 'z') {                        *c &= ~32;                }        }        return 0;}t light_isdigit(int c) {        return (c >= '0' && c <= '9');}int light_isxdigit(int c) {        if (light_isdigit(c)) return 1;        c |= 32;        return (c >= 'a' && c <= 'f');}int light_isalpha(int c) {        c |= 32;        return (c >= 'a' && c <= 'z');}int light_isalnum(int c) {        return light_isdigit(c) || light_isalpha(c);}int buffer_to_lower(buffer *b) {        char *c;        if (b->used == 0) return 0;        for (c = b->ptr; *c; c++) {                if (*c >= 'A' && *c <= 'Z') {                        *c |= 32;                }        }        return 0;}int buffer_to_upper(buffer *b) {        char *c;        if (b->used == 0) return 0;        for (c = b->ptr; *c; c++) {                if (*c >= 'a' && *c <= 'z') {                        *c &= ~32;                }        }        return 0;}

另外附近两种
char *toLowercase(char *src)
{
    char *p;
   
    p = src;
    while (*p != ‘0′)
    {
        *p = tolower(*p);
        p++;
    }
   
    return src;
}

char *toUppercase(char *src)
{
    char *p;
   
    p = src;
    while (*p != ‘0′)
    {
        *p = toupper(*p);
        p++;
    }
   
    return src;   
}

/**
 * strtolower – string to lowner
 *
 */
static char *strtolower( char *s ){
    int i, len = sizeof(s);
    for( i = 0; i < len; i++ ){
        s[i] = ( s[i] >= ‘A’ && s[i] <= ‘Z’ ? s[i] + ‘a’ – ‘A’ : s[i] );
    }
    return(s);
}
 
/**
 * strtoupper – string to upper
 *
 */
static char *strtoupper( char *s ){
    int i, len = sizeof(s);
    for( i = 0; i < len; i++ ){
        s[i] = ( s[i] >= ‘a’ && s[i] <= ‘z’ ? s[i] + ‘A’ – ‘a’ : s[i] );
    }
    return(s);
}
 
/**
 * strpos – find char at string position
 *
 */
static int strpos (const char *s, char c){
    int i, len;
    if (!s || !c) return -1;
    len = strlen(s);
    for (i=0; i<len; i++){
        if (s[i] == c) return i;
    }
    return -1;     
}

没有评论 »