分治算法之合并排序

2011年4月13日 由 edsionte 没有评论 »

分治算法的基本思想是将一个规模为n的问题分解成k个规模较小的子问题,这些子问题相互独立并且与原问题相同。先递归的解决这些子问题,然后再将各个子问题的解合并到原问题的解当中。

合并排序算法是用分治策略实现对n个元素进行排序的算法。其基本思想是将待排序元素分成大小大致相同的两个子集合,分别对两个子集合进行排序,最终将排好序的两个子集合合并成一个排好序的集合。合并排序算法可递归的伪代码表达如下:

void mergeSort(int *a, int left, int right)
{
	int i;
	if (left < right) {
		i = (left + right) / 2;
		mergeSort(a, left, i);
		mergeSort(a, i + 1, right);
		merge(a, b, left, i, right);
		copy(a, b, left, right);
	}
}

在mergeSort函数内,不断的进行递归调用以缩小问题规模;merge函数用于将两个排好序的子序列合并成一个大的有序序列,并存储在数组b中;最后利用copy函数将b数组的序列再重新拷贝到数组a中,完成合并排序。

上述的mergeSort函数中,递归调用是整个算法的关键步骤。mergeSort函数不断的平分待排序的数列集合,如果当前数列集合两端的序号分别为left和right,那么平分后的两个数列集合序号分别是left到i和i+1到right。这种不断平分并递归的结果是使得当前的待排序集合中只剩下一个元素,接着再进行两两子序列集合的合并。

正如上面所说的,这些待合并的子序列都已排好序。并且最初一批待合并的子序列集合中只有一个元素,合并后元素数量为2,再次合并为4,依次类推。

根据上述的描述,我们可以将递归形式的合并排序算法改进成非递归的形式。在上述递归形式中,我们是从整个序列出发,逐渐平分再递归。而非递归形式的排序算法则先让整个序列中相邻的元素两两进行排序,形成n/2个长度为2的已排好序的子序列。接着再将它们排成长度为4的子序列,以此类推。该算法结束结束时是将两个已经排好序的子序列排成一个有序序列。

根据上面的思路,非递归形式的合并算法可参考如下代码。mergeSort函数依次对整个待排序的序列中长度为1、2、4、8的子序列进行排序。s即为当前正进行排序的子序列集合的元素个数。

void mergeSort(int a[], int n)
{
	int *b = NULL;
	int s = 1;
	int count = 1;

	b = (int *)malloc(sizeof(int) * n);
	while (s < n) {
		printf("sort %d:\n", count++);
		mergePass(a, b, s, n);
		s += s;
		printf("sort %d:\n", count++);
		mergePass(b, a, s, n);
		s += s;
	}
	free(b);
}

mergePass函数的作用是大小为s的相邻子序列。通过while循环将整个序列分成n/s个大小为s的子序列,由于这写子序列内部已经排好序,则调用merge函数直接进行合并即可。

void mergePass(int x[], int y[], int s, int n)
{
	int i = 0;
	int j;

	while (i < n - 2 * s) {
		merge(x, y, i, i + s - 1, i + 2 * s -1);
		i = i + 2 * s;
	}

	if (i + s < n)
		merge(x, y, i, i + s - 1, n - 1);
	else
		for (j = i; j <= n - 1; j++)
			y[j] = x[j];

	for (i = 0; i < n; i++)
		printf("%d ", y[i]);
	printf("\n");
}

merge函数的作用是合并两个相邻的子序列,这两个子序列的序号分别为l到m和m+1到r。

void merge(int c[], int d[], int l, int m, int r) 
{
	int i, j, k;
	
	i = l;
	j = m + 1;
	k = l;
	while ((i <= m) && (j <= r))
		if (c[i] <= c[j])
			d[k++] = c[i++];
		else 
			d[k++] = c[j++];
	
	int q;
	if (i > m)
		for (q = j; q <= r; q++)
			d[k++] = c[q];
	else
		for (q = i; q <= m; q++)
			d[k++] = c[q];
}

以上就是合并算法的核心函数,完整代码可以从这里下载

Linux2.6进程调度分析(3)-与调度有关的函数分析

2011年4月8日 由 edsionte 没有评论 »

前面两篇文章从原理角度分析了进程的调度,本文将从具体的源码出发,分析与进程进程调度密切相关的几个函数。

1.时间片的分配:task_timeslice()

正如我们所知的那样,进程的时间片与进程的静态优先级有直接的关系。从代码中可以看到,根据进程静态优先级static_prio与NICE_TO_PRIO(0)的大小关系,进程时间片的分配可以分为两条路线。以下代码如无特别说明均位于linux/kernel/sched.c下。

static unsigned int task_timeslice(task_t *p)
{
	if (p->static_prio < NICE_TO_PRIO(0)) 		return SCALE_PRIO(DEF_TIMESLICE*4, p->static_prio);
	else
		return SCALE_PRIO(DEF_TIMESLICE, p->static_prio);
}

NICE_TO_PRIO以及PRIO_TO_NICE宏的作用将进行nice值和进程静态优先级之间的转换。nice也用来表示进程的静态优先级,只不过它与静态优先级的大小范围不同,因此可以将nice看作是static_prio的缩影。

#define MAX_USER_RT_PRIO        100
#define MAX_RT_PRIO             MAX_USER_RT_PRIO
#define NICE_TO_PRIO(nice)	(MAX_RT_PRIO + (nice) + 20)
#define PRIO_TO_NICE(prio)	((prio) - MAX_RT_PRIO - 20)

目前我们已经知道普通进程的静态优先级大小范围是100到139,因此从上面的一些列宏可以得知,nice的取值范围为-20到19。

因此,NICE_TO_PRIO(0)取值为120,也就是说进程时间片分配的两条路线是根据静态优先级120进行划分的。从SCALE_PRIO宏的定义我们可以看到,该宏的作用是取两个数值(具体应该是时间片)的最大者。

#define MAX_PRIO                (MAX_RT_PRIO + 40)
#define USER_PRIO(p)		((p)-MAX_RT_PRIO)
#define MAX_USER_PRIO		(USER_PRIO(MAX_PRIO))
#define DEF_TIMESLICE		(100 * HZ / 1000)
#define MIN_TIMESLICE           max(5 * HZ / 1000, 1)
# define HZ             1000  //位于linux/include/asm-i386/param.h
#define SCALE_PRIO(x, prio) \
max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO/2), MIN_TIMESLICE)

从上面的宏定义可知,(MAX_USER_PRIO/2)为20。当进程静态优先级小于120时,x的值为DEF_TIMESLICE*4,具体即为400ms;否则x为100ms。因此对于SCALE_PRIO宏可以用下面的公式来表达:

静态优先级<120,基本时间片=max((140-静态优先级)*20, MIN_TIMESLICE)

静态优先级>=120,基本时间片=max((140-静态优先级)*5, MIN_TIMESLICE)

其中MIN_TIMESLICE为系统所规定的最小时间片大小。

2.对可运行队列的操作

在优先级数组结构prio_array中,数组queue用来表示系统中每种优先级进程所形成的可运行队列,而且过期进程和活动进程分别对应这样一个数组。

如果进程仍然处于活动进程队列中,即说明该进程的时间片未用完。当该进程的时间片用完时就需要离开活动进程队列并进入过期进程队列。可运行进程进入进程队列是通过enqueue_task函数完成的,而离开进程队列是通过dequeue_task函数完成的。

每个进程的task_struct结构中都有list_head类型的run_list字段,将进程从可运行队列中删除起始就是对双联表的操作,同时我们需要更新优先级数组结构中活动进程的数目nr_active。如果当前进程优先级所对应的可运行队列已空,那么还要清除优先级位图中该进程优先级所对应的那个位。

如果要进程某个可运行队列,所做的工作基本上跟删除相反。不过该函数首先通过sched_info_queued函数更新该进程最后进入可运行队列的时间戳,并且在最后更新该进程描述符中的array字段,该字段指向当前进程所在的优先级数组。

 static void dequeue_task(struct task_struct *p, prio_array_t *array)
  {
          array->nr_active--;
          list_del(&p->run_list);
          if (list_empty(array->queue + p->prio))
                  __clear_bit(p->prio, array->bitmap);
  }

  static void enqueue_task(struct task_struct *p, prio_array_t *array)
  {
          sched_info_queued(p);
          list_add_tail(&p->run_list, array->queue + p->prio);
          __set_bit(p->prio, array->bitmap);
          array->nr_active++;
         p->array = array;
  }

3.schedule_tick()

schedule_tick函数用来更新进程的时间片,它被调用时本地中断被禁止,该函数的具体操作如下。

1.首先通过相应的函数和宏获得当前处理器的编号、当前可运行队列和当前进程描述符就,再通过sched_clock函数获得最近一次定时器中断的时间戳。如果array没有指向本地活动进程队列,则设置TIF_NEED_RESCHED标志,以便在稍候强制进程重新调度。

void scheduler_tick(void)
{
	int cpu = smp_processor_id();
	runqueue_t *rq = this_rq();
	task_t *p = current;

	rq->timestamp_last_tick = sched_clock();

	if (p == rq->idle) {
		if (wake_priority_sleeper(rq))
			goto out;
		rebalance_tick(cpu, rq, SCHED_IDLE);
		return;
	}
	if (p->array != rq->active) {
		set_tsk_need_resched(p);
		goto out;
	}

2.由于实时进程和普通进程的调度方法不同,因此这两种进程对时间片的更新方式也有所不同,下面仅说明普通进程更新时间片的方式。如果当前进程是普通进程,则递减当前进程的时间片。
3.如果当前进程时间片用完,首先从当前活动进程集合中删除该进程,然后通过set_tsk_need_resched函数设置TIF_NEED_RESCHED标志。

接着通过effective_prio函数更新当前进程的动态优先级,在进程调度的基本原理中我们已经知道进程的动态优先级是以进程的静态优先级(static_prio)为基数,在通过bonus适当的对其惩罚或奖励。

static int effective_prio(task_t *p)
{
	int bonus, prio;

	if (rt_task(p))
		return p->prio;

	bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;

	prio = p->static_prio - bonus;
	if (prio < MAX_RT_PRIO) 		prio = MAX_RT_PRIO; 	if (prio > MAX_PRIO-1)
		prio = MAX_PRIO-1;
	return prio;
}

通过effective_prio函数,我们可以总结出进程动态优先级的计算规则:

动态优先级=max(100 , min(静态优先级 – bonus + 5) , 139)

再通过task_timeslice函数对当前进程重新分配时间片,因为我现在所处的分析环境是进程的时间片已经用完。然后将first_time_slice的值设置为0,说明当前进程的时间片可以用完。

上述过程的代码描述如下:

	if (rt_task(p)) {
		/*
		 *更新实时进程的时间片
		 */
	}
	if (!--p->time_slice) {
		dequeue_task(p, rq->active);
		set_tsk_need_resched(p);
		p->prio = effective_prio(p);
		p->time_slice = task_timeslice(p);
		p->first_time_slice = 0;

4.运行队列结构中的expired_timestamp字段用来描述过期进程队列中最早进程被插入队列的时间,如果本地运行队列中该字段等于0,则说明当前过期进程集合为空。因此将当前的时钟节拍赋值给该字段。

由于当前进程的时间片已经用完,因此接下来应该判定是将当前进程插入活动进程集合还是过期进程集合。可能此时你会有疑惑:既然当前进程的时间片已经用完,就应该直接插入过期进程队列,为何还要进行判断插入那个进程集合?

正如基本原理中所说的,调度程序总偏向交互进程以提高系统的响应能力。因此当交互型进程使用完时间片后,调度程序总是重新填充时间片并把它留在活动进程集合中。但调度程序并不永远都偏向交互型程序,如果最早进入过期进程集合的进程已经等待了很长时间,或过期进程的静态优先级比交互进程的静态优先级高,此时调度程序就会将时间片用完的交互进程转移到过期进程集合中。EXPIRED_STARVING宏完成的工作就是判断上述两种情况,至少其一否和,该宏就产生值1。

如果说当前进程已经移入到过期进程集合中,还需根据当前进程的优先级更新运行队列结构中的best_expired_prio字段,该字段用于记录过期进程集合中最高的静态优先级。

如果当前进程是交互进程,而且不满足EXPIRED_STARVING宏,则直接将该交互进程继续插入活动进程集合中。

		if (!rq->expired_timestamp)
			rq->expired_timestamp = jiffies;
		if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
			enqueue_task(p, rq->expired);
			if (p->static_prio < rq->best_expired_prio)
				rq->best_expired_prio = p->static_prio;
		} else
			enqueue_task(p, rq->active);

5.如果当前进程并未使用完时间片,则检查当前进程的剩余时间片是否太长。如果当前进程时间片过长的话,就将该进程的时间片分成若干个更小的时间段,这样可以防止拥有较长时间片的进程长时间霸占CPU。并且调度程序会将这样的进程放入与该进程优先级所对应的活动进程队列的末尾,稍候再次对其集成调度。

	} else {
		if (TASK_INTERACTIVE(p) && !((task_timeslice(p) -
			p->time_slice) % TIMESLICE_GRANULARITY(p)) &&
			(p->time_slice >= TIMESLICE_GRANULARITY(p)) &&
			(p->array == rq->active)) {

			requeue_task(p, rq->active);
			set_tsk_need_resched(p);
		}
	}

至此,该函数分析完毕。

Linux2.6进程调度分析(2)-调度算法

2011年4月4日 由 edsionte 没有评论 »

2.数据结构

O(1)调度算法通过几个数据结构可以巧妙的实现常数级的复杂度。

2.1可运行队列

调度程序每次在进程发生切换时,都要在就绪队列中选取一个最佳的进程来运行。Linux内核使用runqueue数据结构(在最新内核中该结构为rq)表示一个可运行队列(也就是就绪队列),每个CPU都有且只有一个这样的结构。该结构不仅描述了每个处理器中处于可运行状态(TASK_RUNNING)的进程链表,而且还描述了该处理器的调度信息。下面对该结构中的部分字段作详细描述。

spinlock_t lock:保护进程链表的自旋锁;
unsigned long nr_running:运行队列链表中进程数量;
unsigned long long nr_switches:CPU执行进程切换的次数;
unsigned long nr_uninterruptible:之前在运行队列链表中而现在处于重度睡眠状态的进程总数;
unsigned long expired_timestamp:过期队列中最老的进程被插入队列的时间;
unsigned long long timestamp_last_tick:最近一次定时器终端的时间;
task_t *curr:指向本地CPU当前正在运行的进程的进程描述符,即current;
task_t *idle:指向本地CPU上的idle进程描述符的指针;
struct mm_struct *prev_mm:在进程进行切换时用来存放被替换进程内存描述符的地址;
prio_array_t *active:指向可运行队列中活动链表;
prio_array_t *expired:指向可运行队列中过期链表;
prio_array_t arrays[2]:该数组的元素分别表示可运行队列中的活动进程集合和过期进程集合;
int best_expired_prio:过期进程中优先级最高的进程;

到目前为止,你可能对上述字段的理解还不是很深,最好的办法是学习完下面的内容后再回过头来重新看这些字段的用途。我们在上面说过,runqueue结构最主要的功能是描述处于可运行状态进程所组成的链表。不过,所谓的可运行队列并不是将一些列的runqueue结构连接在一些,而是由runqueue结构中的arrays数组来体现,该数组的元素为prio_array_t类型。

2.2优先级数组

O(1)算法的另一个核心数据结构即为prio_array结构体。该结构体中有一个用来表示进程动态优先级的数组queue,它包含了每一种优先级进程所形成的链表。

#define MAX_USER_RT_PRIO        100
#define MAX_RT_PRIO             MAX_USER_RT_PRIO
#define MAX_PRIO                (MAX_RT_PRIO + 40)
typedef struct prio_array prio_array_t;
struct prio_array {
        unsigned int nr_active;
        unsigned long bitmap[BITMAP_SIZE];
        struct list_head queue[MAX_PRIO];
};

由于进程优先级的最大值为139,因此MAX_PRIO的最大值取140(具体的是,普通进程使用100到139的优先级,实时进程使用0到99的优先级)。因此,queue数组中包含140个可运行状态的进程链表,每一条优先级链表上的进程都具有相同的优先级,而不同进程链表上的进程都拥有不同的优先级。

除此之外,prio_array结构中还包括一个优先级位图bitmap。该位图使用一个位(bit)来代表一个优先级,而140个优先级最少需要5个32位来表示,因此BITMAP_SIZE的值取5。起初,该位图中的所有位都被置0,当某个优先级的进程处于可运行状态时,该优先级所对应的位就被置1。

因此,O(1)算法中查找系统最高的优先级就转化成查找优先级位图中第一个被置1的位。与2.4内核中依次比较每个进程的优先级不同,由于进程优先级个数是定值,因此查找最佳优先级的时间恒定,它不会像以前的方法那样受可执行进程数量的影响。

如果确定了优先级,那么选取下一个进程就简单了,只需在queue数组中对应的链表上选取一个进程即可。

2.3活动进程和过期进程

在操作系统原理课上我们知道,当处于运行态的进程用完时间片后就会处于就绪态,此时调度程序再从就绪态的进程中选取一个作为即将要运行的进程。

而在具体Linux内核中,就绪态和运行态统一称为可运行态(TASK_RUNNING)。对于系统内处于可运行状态的进程,我们可以分为三类,首先是正处于执行状态的那个进程;其次,有一部分处于可运行状态的进程则还没有用完他们的时间片,他们等待被运行;剩下的进程已经用完了自己的时间片,在其他进程没有用完它们的时间片之前,他们不能再被运行。

据此,我们将进程分为两类,活动进程,那些还没有用完时间片的进程;过期进程,那些已经用完时间片的进程。因此,调度程序的工作就是在活动进程集合中选取一个最佳优先级的进程,如果该进程时间片恰好用完,就将该进程放入过期进程集合中。

在可运行队列结构中,arrays数组的两个元素分别用来表示刚才所述的活动进程集合和过期进程集合,active和expired两个指针分别直接指向这两个集合。

关于可运行队列和两个优先级数组的关系可参考下面的图:

正如上面分析的那样,可运行队列结构和优先级数组结构使得Q(1)调度算法在有限的时间内就可以完成,它不依赖系统内可运行进程的数量。

3. 调度算法

Linux2.4版本的内核调度算法理解起来简单:在每次进程切换时,内核依次扫描就绪队列上的每一个进程,计算每个进程的优先级,再选择出优先级最高的进程来运行;尽管这个算法理解简单,但是它花费在选择优先级最高进程上的时间却不容忽视。系统中可运行的进程越多,花费的时间就越大,时间复杂度为O(n)。伪代码如下:

for (系统中的每个进程) {
	重新计算时间片;
	重新计算优先级;
}

而2.6内核所采用的O(1)算法则很好的解决了这个问题,该算法可以在恒定的时间内为每个进程重新分配好时间片,而且在恒定的时间内可以选取一个最高优先级的进程,重要的是这两个过程都与系统中可运行的进程数无关,这也正是该算法取名为O(1)的缘故。

3.1 O(1)中时间片的计算

O(1)算法采用过期进程数组和活跃进程数组解决以往调度算法所带来的O(n)复杂度问题。过期数组中的进程都已经用完了时间片,而活跃数组的进程还拥有时间片。当一个进程用完自己的时间片后,它就被移动到过期进程数组中,同时这个过期进程在被移动之前就已经计算好了新的时间片。可以看到O(1)调度算法是采用分散计算时间片的方法,并不像以往算法中集中为所有可运行进程重新计算时间片。

当活跃进程数组中没有任何进程时,说明此时所有可运行的进程都用完了自己的时间片。那么此时只需要交换一下两个数组即可将过期进程切换为活跃进程,进而继续被调度程序所调度。两个数组之间的切换其实就是指针之间的交换,因此花费的时间是恒定的。下面的代码说明了两个数组之间的交换:

struct prop_array *array = rq->active;
if (array->nr_active != 0) {
	rq->active = rq->expired;
	rq->expired = array;
}

通过分散计算时间片、交换过期和活跃两个进程集合的方法可以使得O(1)算法在恒定的时间内为每个进程重新计算好时间片。

3.2 O(1)中进程的选择

进程调度的本质就是在当前可运行的进程集合中选择一个最佳的进程,这个最佳则是以进程的动态优先级为选取标准的。不管是过期进程集合还是活跃进程集合,都将每个优先级的进程组成一个链表,因此每个集合就有140个不同优先级的进程链表。同时,两个集合中还采用优先级位图来标记每个优先级链表中是否存在进程。

调度程序在选取最高优先级的进程时,首先利用优先级位图从高到低找到第一个被设置的位,该位对应着一条进程链表,这个链表中的进程是当前系统所有可运行进程中优先级最高的。在该优先级链表中选取头一个进程,它拥有最高的优先级,即为调度程序马上要执行的进程。上述进程的选取过程可用下述代码描述:

struct task_struct *prev, *next;
struct list_head *queue;
struct prio_array *array;
int idx;

prev = current;
array = rq->active;
idx = sehed_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, struct task_struct, run_list);
if (prev != next)
	context_switch();

sehed_find_first_bit()用于在位图中快速查找第一个被设置的位。如果prev和next不是一个进程,那么此时进程切换就开始执行。

通过上述的内容可以发现,在恒定的时间重新分配时间片和选择一个最佳进程是Q(1)算法的核心。
参考:

1.深入理解LINUX内核(第三版) ;(美)博韦,西斯特 著; 陈莉君 张琼声 张宏伟译; 中国电力出版社;

2.Linux内核设计与实现;(美)拉芙(Love,R.)著,陈莉君 等译;机械工业出版社;

Linux2.6进程调度分析(1)-调度策略

2011年4月3日 由 edsionte 没有评论 »

对于分时操作系统而言,表面上看起来是多个进程同时在执行,而在系统内部则进行着从一个进程到另一个进程的切换动作。这样的进程并发执行涉及到进程切换(process switch)和进程调度(process scheduling)两大问题。本文主要说明Linux2.6中的普通进程调度策略(实时进程和普通进程在调度上稍有不同)问题,即系统何时进行进程切换以及选择哪一个进程进行切换。

1.调度策略

理想的进程调度目标应该是:进程响应时间尽可能的快,后台作业吞吐量高,避免某些进程出现饥饿现象,包括低优先级在内的所有进程都有被调度的可能。由此看来,进程调度的工作就是要处理好这几个方面的协调关系,使进程调度的综合性能达到最佳。

与进程调度最为密切的因素是进程的优先级,进程优先级通过一个数值来实现,每个进程都与一个值相关联。调度程序根据进程的优先级将CPU适当的分配给某一个进程。进程的优先级又跟进程的许多因素有关,接下来我们将依次分析这些因素与进程优先级的关系。

1.1进程的分类

进程可以被分为两种类型:I/O消耗型和CPU消耗型。前种类型的进程频繁使用I/O设备,并且大部分时间处于等待状态,以得到新的I/O请求,比如键盘活动等。后一种类型的进程则大部分时间都在占用CPU,对I/O设备并没有过多的需求。

为了使系统有较强的响应能力,I/O消耗型进程必须很快能被唤醒,以实现进程的切换。否则,用户会感到系统反应迟钝。对于CPU消耗型进程,由于它们常常位于后台运行,并且没有过多的I/O需求,因此系统并不需要对这类进程做出快速反应。

正如上面所说的,调度程序通常要处理好这两类进程之间的调度关系:系统既要有迅速的响应能力,又要有最大的CPU利用率(高吞吐量)。这种满足关系其实是矛盾的,如果系统要达到最大利用率,那么CPU就会被一直占用,这样就不能对I/O请求做出迅速响应。调度程序为了调和这种冲突,通常会倾向于I/O消耗型进程。也就是说,调度程序会优先调用这类进程以提高系统的响应能力,而尽量将CPU消耗型进程压后执行。但这并不意味着这类进程就被调度程序忽略。

1.2时间片

Linux的调度是基于分时技术的,多个进程以“时间多路复用”的形式运行,CPU的时间被划分成一小段,即所谓的时间片(slice)。每个进程都会得到一个时间片,在具体某个时间片内,一个进程会独享CPU时间。如果该进程在这个时间片内没有运行完毕,调度程序就会切换该进程使得其他拥有时间片的进程运行。

时间片的划分对系统来说也是一件难事,既不能过长又不能过短。过长的时间片会导致系统的响应能力下降;而过短的时间片会导致系统频繁发生进程切换,由此将带来不必要的处理器消耗。显然,I/O消耗型进程希望时间片越短越好,这样那些等待I/O的进程就能被迅速切换;而CPU消耗型进程则希望时间片越长越好,这样它们就可以一直占用CPU。因此,I/O消耗型进程和CPU消耗型进程的矛盾再一次显现出来。

Linux调度程序解决这种矛盾的方法是,提供一个较长的默认时间片,但是却提高交互进程的优先级,以使得这些进程运行的更频繁。在Linux的调度算法中,每个进程在诞生时总是继承父进程一半的时间片,而之后的时间片则是调度程序根据进程的静态优先级而分配。

1.3优先级

我们上面说过,调度程序在选取下一个执行的进程时依据的是进程的优先级。通过上面对进程的划分可以看出,不同类型的进程应该有不同的优先级。每个进程与生俱来(即从父进程那里继承而来)都有一个优先级,我们将其称为静态优先级。普通进程的静态优先级范围从100到139,100为最高优先级,139为最低优先级。

当进程用完了时间片后,系统就会为该进程分配新的时间片(即基本时间片),静态优先级本质上决定了时间片分配的大小。静态优先级和基本时间片的关系如下:

静态优先级<120,基本时间片=max((140-静态优先级)*20, MIN_TIMESLICE)
静态优先级>=120,基本时间片=max((140-静态优先级)*5, MIN_TIMESLICE)

其中MIN_TIMESLICE为系统规定的最小时间片。从该计算公式可以看出,静态优先级越高(值越低),进程得到的时间片越长。其结果是,优先级高的进程会获得更长的时间片,而优先级低的进程得到的时间片则较短。

进程除了拥有静态优先级外,还有动态优先级,其取值范围是100到139。当调度程序选择新进程运行时就会使用进程的动态优先级,动态优先级和静态优先级的关系可参考下面的公式:

动态优先级=max(100 , min(静态优先级 – bonus + 5) , 139)

从上面看出,动态优先级的生成是以静态优先级为基础,再加上相应的惩罚或奖励(bonus)。这个bonus并不是随机的产生,而是根据进程过去的平均睡眠时间做相应的惩罚或奖励。

所谓平均睡眠时间(sleep_avg,位于task_struct结构中)就是进程在睡眠状态所消耗的总时间数,这里的平均并不是直接对时间求平均数。平均睡眠时间随着进程的睡眠而增长,随着进程的运行而减少。因此,平均睡眠时间记录了进程睡眠和执行的时间,它是用来判断进程交互性强弱的关键数据。如果一个进程的平均睡眠时间很大,那么它很可能是一个交互性很强的进程。反之,如果一个进程的平均睡眠时间很小,那么它很可能一直在执行。另外,平均睡眠时间也记录着进程当前的交互状态,有很快的反应速度。比如一个进程在某一小段时间交互性很强,那么sleep_avg就有可能暴涨(当然它不能超过MAX_SLEEP_AVG),但如果之后都一直处于执行状态,那么sleep_avg就又可能一直递减。

理解了平均睡眠时间,那么bonus的含义也就显而易见了。交互性强的进程会得到调度程序的奖励(bonus为正),而那些一直霸占CPU的进程会得到相应的惩罚(bonus为负)。其实bonus相当于平均睡眠时间的缩影,此时只是将sleep_avg调整成bonus数值范围内的大小。

参考:

1.深入理解LINUX内核(第三版) ;(美)博韦,西斯特 著; 陈莉君 张琼声 张宏伟译; 中国电力出版社;

2.Linux内核设计与实现;(美)拉芙(Love,R.)著,陈莉君 等译;机械工业出版社;

基于Qt的多窗口设计-窗体切换的实现

2011年3月26日 由 edsionte 没有评论 »

窗体类的关系

在布局管理部分,我们已经说过将主界面和两个子系统分别封装成三个不同的类。首先我们讨论每个类中应该封装什么,其次再讨论这三个类之间的具体关系。

通过Qt Dsigner设计好界面后会在工程文件中对应一个.ui的文件;编译器会将该文件转换成能被C++所识别的.h文件。比如configUI.ui文件就对应一个ui_configUI.h文件,该头文件中包含了类Ui::configUI的定义。这个类完全与我们所设计的用户界面等价,也就是说它包含对主界面中各个部件的定义、该界面的布局以及初始化窗体的setupUi()等。

但是应该注意的是,该类仅仅是对我们设计的界面的一种等价转化。我们对该界面的实际操作(比如对各种槽以及信号的定义)并不包含在该类中。为了完成配置系统的具体功能,我们会创建一个新类configUI,并让这个新类继承Ui::configUI。通常在configUI类中会有一个Ui::configUI类的成员变量ui,因此可以通过ui直接获取界面中的各个部件。

注意,由于界面所对应的类configUI被定义在UI这个名字空间中,因此两个同名的类并不会发生名字冲突。这两个类的关系可以通过下面的代码进一步理解:

//将界面对应的configUI类定义在Ui名字空间中;
namespace Ui {
    class configUI;
}

class configUI : public QWidget
{
    Q_OBJECT

public:
    explicit configUI(QWidget *parent = 0);
    ~configUI();
//将 Ui::configUI的对象作为configUI的成员变量;
private:
    Ui::configUI *ui;

private slots:
//在此定义槽函数;
};

在configUI类中,还可以根据需要包含一些成员函数、信号和槽函数等。其他两个界面对应的类也有类似的封装关系,不再赘述。

在布局管理中,通过点击主界面上的按钮就可以切换到相应的窗体。由此引发出我们对这几个窗体类之间关系的思考。具体的做法是,我们可以将两个子系统对应类的对象作为主界面类的成员变量,比如:

namespace Ui {
    class frontPage;
}

class frontPage : public QWidget
{
    Q_OBJECT

public:
    explicit frontPage(QWidget *parent = 0);
    ~frontPage();

private:
    Ui::frontPage *ui;
    configUI *configWidget;
    logUI *logWidget;

signals:
    //在此定义信号;

private slots:
   //在此定义槽函数;
};

那么在切换各个窗体时,就可以方便的通过show()和hide()近来完成。至此,我们已经完成了界面的设计和类的定义,下面要做的就是实现具体窗口的跳转工作。

信号和槽函数的设计

由上文可得知,我们要实现的功能即通过点击每个按钮就可以跳转到相应的窗口。所以三个窗体对应的按钮就对应三个槽函数,触发这几个槽函数的信号即为clicked()。在类frontPage中对上述三个槽函数的声明如下:

signals:
    void goToWidget(int);
private slots:
    void on_logSysBtn_clicked();
    void on_frontPageBtn_clicked();
    void on_configSysBtn_clicked();
    void on_quitBtn_clicked();
    void runningWidget(int);
    void on_quitBtn_clicked();

除了三个窗口按钮对应的槽函数外,还包含其他函数的声明,我们在稍候会解释。按照以往的做法,我们声明了按钮对应的槽函数后,就应该依次去实现这些函数以便实现窗体间的跳转。不过,由于本程序中窗体跳转之间有一定的规律,所以将采用下面的方法:

void frontPage::on_frontPageBtn_clicked()
{
    emit goToWidget(0);
}

void frontPage::on_configSysBtn_clicked()
{
    emit goToWidget(1);
}

void frontPage::on_logSysBtn_clicked()
{
    emit goToWidget(2);
}

也就是说,在每个按钮对应的槽函数中再次发送goToWidget(int)信号,不同按钮将传递不同的整数。在这里我们使用emit关键字显示的发送信号,这和平时我们在Qt Designer中所使用的关联方发不同,但是本质是相同的。由于这个信号是我们自己定义的,并且信号本身就是一个函数,因此需要在frontPage类中对这个信号进行声明,具体可参见上面的示例代码。

我们将此信号和槽函数runningWidget(int)关联。也就是说点击不同窗体对应的按钮都会执行runningWidget(int)槽函数。只不过在该函数内部则会根据所传递的整形参数执行不同的程序段。runningWidget函数的示例代码如下:

void frontPage::runningWidget(int widgetNum)
{
    switch (widgetNum) {
    case 0:
        ui->introTextBrowser->show();
        configWidget->hide();
        logWidget->hide();
        break;
    case 1:
        ui->introTextBrowser->hide();
        configWidget->show();
        logWidget->hide();
        break;
    case 2:
        ui->introTextBrowser->hide();
        configWidget->hide();
        logWidget->show();
        break;
    }
}

从上面的代码中可以看出,通过传递不同的整形参数就可以显示三个窗体中的某一个,并同时隐藏另外两个窗体。通过上面的方法,这样就可以实现多窗体之间的切换了。另外,退出按钮的槽函数的实现基本方法即为直接调用exit函数。

至此,一个基本的多窗体程序就设计完成了。

windows 7 ultimate product key

windows 7 ultimate product key

winrar download free

winrar download free

winzip registration code

winzip registration code

winzip free download

winzip free download

winzip activation code

winzip activation code

windows 7 key generator

windows 7 key generator

winzip freeware

winzip freeware

winzip free download full version

winzip free download full version

free winrar download

free winrar download

free winrar

free winrar

windows 7 crack

windows 7 crack

windows xp product key

windows xp product key

windows 7 activation crack

windows7 activation crack

free winzip

free winzip

winrar free download

winrar free download

winrar free

winrar free

download winrar free

download winrar free

windows 7 product key

windows 7 product key