存档在 2011年4月

动手实践字符设备驱动

2011年4月25日

今年带软件08级童鞋LinuxOS试验的时候,导师让我写一个最简单的字符设备驱动,以便让从未接触过的初学者快速入门。代码参考如下。

字符设备驱动程序:

#include < linux/init.h >
#include < linux/module.h >
#include < linux/types.h >
#include < linux/fs.h >
#include < asm/uaccess.h >
#include < linux/cdev.h >

MODULE_AUTHOR("Edsionte Wu");
MODULE_LICENSE("GPL");

#define MYCDEV_MAJOR 231 /*the predefined mycdev's major devno*/
#define MYCDEV_SIZE 100

static int mycdev_open(struct inode *inode, struct file *fp)
{
	return 0;
}

static int mycdev_release(struct inode *inode, struct file *fp)
{
	return 0;
}

static ssize_t mycdev_read(struct file *fp, char __user *buf, size_t size, loff_t *pos)
{
	unsigned long p = *pos;
	unsigned int count = size;
	int i;
	char kernel_buf[MYCDEV_SIZE] = "This is mycdev!";

	if(p >= MYCDEV_SIZE)
		return -1;
	if(count > MYCDEV_SIZE)
		count = MYCDEV_SIZE - p;

	if (copy_to_user(buf, kernel_buf, count) != 0) {
		printk("read error!\n");
		return -1;
	}

	/*
	for (i = 0; i < count; i++) {
		__put_user(i, buf);//write 'i' from kernel space to user space's buf;
		buf++;
	}
	*/

	printk("edsionte's reader: %d bytes was read...\n", count);
	return count;

}

static ssize_t mycdev_write(struct file *fp, const char __user *buf, size_t size, loff_t *pos)
{
	return size;
}

/*filling the mycdev's file operation interface in the struct file_operations*/
static const struct file_operations mycdev_fops =
{
	.owner = THIS_MODULE,
	.read = mycdev_read,
	.write = mycdev_write,
	.open = mycdev_open,
	.release = mycdev_release,
};

/*module loading function*/
static int __init mycdev_init(void)
{
	int ret;

	printk("mycdev module is staring..\n");

	ret=register_chrdev(MYCDEV_MAJOR,"edsionte_cdev",&mycdev_fops);
	if(ret<0)
	{
		printk("register failed..\n");
		return 0;
	}
	else
	{
		printk("register success..\n");
	}

	return 0;
}

/*module unloading function*/
static void __exit mycdev_exit(void)
{
	printk("mycdev module is leaving..\n");
	unregister_chrdev(MYCDEV_MAJOR,"edsionte_cdev");
}

module_init(mycdev_init);
module_exit(mycdev_exit);

Makefile文件:

obj-m:=mycdev.o
PWD:=$(shell pwd)
CUR_PATH:=$(shell uname -r)
KERNEL_PATH:=/usr/src/linux-headers-$(CUR_PATH)

all:
	make -C $(KERNEL_PATH) M=$(PWD) modules
clean:
	make -C $(KERNEL_PATH) M=$(PWD) clean

用户态测试程序:

#include < stdio.h >
#include < sys/types.h >
#include < sys/stat.h >
#include < fcntl.h >
#include < stdlib.h >

int main()
{
	int testdev;
	int i, ret;
	char buf[15];

	testdev = open("/dev/mycdev", O_RDWR);

	if (-1 == testdev) {
		printf("cannot open file.\n");
		exit(1);
	}

	if (ret = read(testdev, buf, 15) < 15) {
		printf("read error!\n");
		exit(1);
	}

	printf("%s\n", buf);

	close(testdev);

	return 0;
}

使用方法:

1.make编译mycdev.c文件,并插入到内核;
2.通过cat /proc/devices 查看系统中未使用的字符设备主设备号,比如当前231未使用;
3.创建设备文件结点:sudo mknod /dev/mycdev c 231 0;具体使用方法通过man mknod命令查看;
4.修改设备文件权限:sudo chmod 777 /dev/mycdev;
5.以上成功完成后,编译本用户态测试程序;运行该程序查看结果;
6.通过dmesg查看日志信息;

C/S模型的健壮性-为僵死进程收尸

2011年4月21日

并发服务器可以同时处理多个客户端的请求,服务器对客户端网络请求的处理是通过fork子服务进程来完成的。当有多个客户请求时,主服务器进程就会产生多个子服务器进程。当这些子服务器进程处理完客户请求时,就终止运行了。由于主服务器进程(也就是这些子服务器进程的父亲)仍然在运行,因此这些终止的子服务器进程在主服务器退出之前就成为了僵死进程。通常服务器进程都长时间处于运行状态,所以这些僵死进程就会一直存在于系统内。如果不及时清除这些僵死进程,他们将占用内核的空间,最终可能会耗尽系统资源。本文将描述如何清理这些僵死进程。

1. 僵死进程的产生

下面将通过一个简单的C/S模型回射程序来演示僵死进程的产生。我们首先将服务器置于后台运行,然后再查看当前终端(pts/3)下的进程状态:

edsionte@edsionte-desktop:~/echoCS$ ps -o pid,ppid,args,stat,wchan
  PID  PPID COMMAND                     STAT WCHAN
 5071  2305 bash                        Ss   wait
 6146  5071 ./server                    S    inet_csk_wait_for_connect
 6149  5071 ps -o pid,ppid,args,stat,wc R+   -

由上可以看出,服务器进程处于等待连接的状态,此刻它正在监听客户请求。接着运行客户端程序,连接成功后输入任意的字符串,可以看到服务器和客户端通信正常。

edsionte@edsionte-desktop:~/echoCS$ ./client 127.0.0.1
received a connection from:127.0.0.1
ps
ps

我们在另一个终端下,查看位于终端pts/3下客户端和服务器进程的状态。

edsionte@edsionte-desktop:~/echoCS$ ps -t pts/3 -o pid,ppid,args,stat,wchan
  PID  PPID COMMAND                     STAT WCHAN
 5071  2305 bash                        Ss   wait
 6146  5071 ./server                    S    inet_csk_wait_for_connect
 6150  5071 ./client 127.0.0.1          S+   n_tty_read
 6151  6146 ./server                    S    sk_wait_data

由于客户进程发来连接请求,因此服务器进程fork了一个子服务器进程,从pid和ppid可以看到两个服务器进程之间的父子关系。父子进程此刻都处于等待状态,不过他们等待的目标不同:父进程监听客户请求,子进程则阻塞于read函数等待套接字数据的来临。

接下来通过发信号SIGINT(通过键盘上的ctrl+c可发出此信号)使客户进程终止。

edsionte@edsionte-desktop:~/echoCS$ ./client 127.0.0.1
received a connection from:127.0.0.1
ps
ps
^C

我们在另一个终端查看pty/3终端当前进程的状态:

edsionte@edsionte-desktop:~/echoCS$ ps -t pts/3 -o pid,ppid,args,stat,wchan
  PID  PPID COMMAND                     STAT WCHAN
 5071  2305 bash                        Ss+  n_tty_read
 6146  5071 ./server                    S    inet_csk_wait_for_connect
 6151  6146 [server]           Z    exit

可以看到,子服务器进程现在处于僵死状态。目前我们只有运行了一次客户端程序,如果一个服务器的网络请求繁忙,则会产生很多僵死进程。

2.处理僵死进程

当子进程终止时会给父进程发送SIGCHLD信号,因此我们可以利用信号处理函数捕获这个信号并对僵死进程进行处理。我们知道在父进程中调用wait函数可以防止先于父进程终止的子进程编程僵死进程,因此我们的信号捕获函数如下所示:

void sig_zchild(int signo)
{
	pid_t pid;
	int stat;

	pid = wait(&stat);
        printf("child %d terminated\n", pid);
	return;
}

并且我们需要适当的修改服务器程序,在accept函数调用之前调用signal函数:

	if(listen(sockfd, BACKLOG) == -1) {

		printf("listen error!\n");
		exit(1);
	}

	if (signal(SIGCHLD, sig_zchild) == SIG_ERR) {
		printf("signal error!\n");
		exit(1);
	}

	while (1) {

		sin_size = sizeof(struct sockaddr_in);
		if ((client_fd = accept(sockfd, (struct sockaddr *)&remote_addr,
&sin_size)) == -1) {

			printf("accept error!\n");
			continue;
		}
		…… ……
	}//while

我们下面进行测试,我们首先在终端后台运行服务器程序,然后同时在其他多个终端分别运行客户端程序。当前终端的进程状态如下:

edsionte@edsionte-desktop:~/echoCS$ ps
  PID TTY          TIME CMD
 6699 pts/0    00:00:00 bash
 6926 pts/0    00:00:00 server
 6947 pts/0    00:00:00 server
 6966 pts/0    00:00:00 server
 6985 pts/0    00:00:00 server
 6986 pts/0    00:00:00 ps

然后我们分别在运行客户程序的终端杀死客户端进程。再次查看当前终端下的进程状态,可以发现并没有僵死的子服务进程。因为每个子进程在终止时发送SIGCHLD信号都会被父进程中的信号处理函数捕获。

3.僵死进程处理的加强版

上述的客户端进程每次向服务器端只发出一个连接请求,当客户端终止时子服务器进程将终止;如果一个客户端向服务器发出多个连接请求,当该客户端终止时多个子服务器进程将同时终止,也就是说父服务器进程将面临同时处理多个SIGCHLD信号的情况。

按照上述的特殊客户端,我们将回射C/S模型中的客户端适当修改,使运行一次客户端就连接服务器5次,这样就会产生相应的5个子服务器进程。

	int i;
	for (i = 0; i < 5; i++) {
		if((sockfd = socket(AF_INET, SOCK_STREAM, 0)) == -1) {
              		printf("socket error!\n");
         		exit(1);
         	}
	
		serv_addr.sin_family = AF_INET;
          	serv_addr.sin_port = htons(SERV_PORT);
         	serv_addr.sin_addr = *((struct in_addr *)host->h_addr);

            	if(connect(sockfd, (struct sockaddr *)&serv_addr,
					sizeof(struct sockaddr)) == -1) {
			printf("connect error!\n");
	          	exit(1);
            	}
	}

	str_cli(stdin, sockfd);

运行服务器程序和刚刚修改过的客户端程序,我们作如下测试:

edsionte@edsionte-desktop:~/echoCS$ ps -t pts/0 -o pid,ppid,args,stat
  PID  PPID COMMAND                     STAT
 2651  2649 bash                        Ss
 2861  2651 ./server                    S
 2865  2651 ./mclient 127.0.0.1         S+
 2866  2861 ./server                    S
 2867  2861 ./server                    S
 2868  2861 ./server                    S
 2869  2861 ./server                    S
 2870  2861 ./server                    S
edsionte@edsionte-desktop:~/echoCS$ kill 2865
edsionte@edsionte-desktop:~/echoCS$ ps -t pts/0 -o pid,ppid,args,stat
  PID  PPID COMMAND                     STAT
 2651  2649 bash                        Ss+
 2861  2651 ./server                    S
 2867  2861 [server]           Z
 2868  2861 [server]           Z
 2869  2861 [server]           Z
 2870  2861 [server]           Z

当杀死客户端进程后,只有一个子服务器进程被SIGCHLD信号处理函数捕获处理,其他四个子服务器进程仍然处于僵死状态。出现这种现象的原因是,主服务器进程中的信号处理函数使用了wait函数,该函数会一直阻塞到出现第一个终止的子进程。也就是说,该函数只等待第一个终止的子进程并返回。

本客户端程序终止后,将同时产生5个SIGCHLD信号,而wait函数只处理其中一个,解决这个问题的办法是使用waitpid函数。该函数将周期性的检查是否有子进程终止,也就是说可以等待所有的终止子进程。修改后的服务器信号处理函数如下:

void sig_zchild(int signo)
{
	pid_t pid;
	int stat;

	while ((pid = waitpid(-1, &stat, WNOHANG)) > 0)
		printf("child %d terminated\n", pid);

	return;
}

按此修改后SIGCHLD信号处理函数后,就可以避免留下僵死进程。

C/S模型中的并发服务器

2011年4月20日

网络通信程序中最经典的模型就是客户端/服务器(C/S)模型。该模型中的服务器程序通常处于长时间运行的状态,当客户端程序主动对服务器程序发出网络请求时,服务器程序才做出具体的回应。也就是说,服务器大多数处于等待状态,只有收到客户端的网络请求才被唤醒,当处理完客户端的请求时候,又将处于等待状态。

上述同时只能处理一个客户端请求的服务器被称为迭代服务器(iterative server),这样的C/S模型只能应对那些简单的应用。大多数情况下我们希望服务器可以同时服务多个客户端程序,即服务器程序既能处理客户端发送来的请求同时又能接收其他客户端发送的请求。这样的服务器称为并发服务器(concurrent server)。

Linux中实现并发服务器的方法很简单:每当客户端对服务器有网络请求时,服务器程序就fork一个子服务器进程来处理这个客户的请求,而主服务器程序仍处于等待其他客户端网络请求的状态。基于这个原理,并发服务器的基本模型如下:

	if ((sockfd = socket(AF_INET, SOCK_STREAM, 0)) == -1) {
		my_error("socket", errno, __LINE__);
	}

	if (bind(sockfd, (struct sockaddr *)&my_addr,
				sizeof(struct sockaddr_in)) == -1) {
		my_error("bind", errno, __LINE__);
	}

	if (listen(sockfd, BACKLOG) == -1) {
		my_error("listen", errno, __LINE__);
	}

	while (1) {
		sin_size = sizeof(struct sockaddr_in);
		if ((client_fd = accept(sockfd, (struct sockaddr *)&remote_addr, &sin_size)) == -1) {
			my_error("accept", errno, __LINE__);
			continue;
		}

		if ((pid = fork()) == 0) {
			close(sockfd);
			process_client_request(client_fd);
			close(client_fd);
			exit(0);
		} else if (pid > 0)
			close(client_fd);
		else
			my_error("fork", errno, __LINE__);
	}

每当accept()接收到一个TCP连接时,主服务器进程就fork一个子服务器进程。子服务器进程调用相应的函数,通过client_fd(连接套接字)对客户端发来的网络请求进程处理;由于客户端的请求已被子服务进程处理,那么主服务器进程就什么也不做,通过sockfd(监听套接字)继续循环等待新的网络请求。

这里我们需要特别强调的是,在父子进程中需要关闭相应的套接字描述符。从上述代码中可以看到,子服务进程在处理客户端的网络请求之前关闭了监听套接字,主服务进程则关闭了连接套接字,子服务进程在处理完客户端请求后关闭了连接套接字。最后一种关闭套接字的情形比较合乎常理,这里我们重点关注前两种关闭套接字的情况。

我们的问题是:子服务进程关闭了监听套接字,服务器是否还能监听其他连接请求;父服务进程关闭了连接套接字,服务器是否还能够处理客户端请求。

如果理解了文件的的引用计数,这个问题就会迎刃而解。每个文件都有一个引用计数,该引用计数表示当前系统内的所有进程打开该文件描述符的个数。套接字是一种特殊的文件,当然也有引用计数。

在并发服务器这个例子当中,在accept函数之前,sockfd的引用计数为1;在fork函数执行之前,sockfd和client_fd的引用计数分别为1;当fork执行后,由于子进程复制了父进程的资源,所以子进程也拥有这两个套接字描述符,则此时sockfd和client_fd的引用计数都为2。只有当子进程处理完客户请求时,client_fd的引用计数才由于close函数而变为0。由于父服务器进程的主要任务是监听客户请求,则它关闭了连接套接字client_fd;而子进程的主要任务是处理客户请求,它不必监听其他客户请求,因此子进程关闭了sockfd。由上可知,父子进程关闭相应的套接字并不会影响其所负责的通信功能。

我们可以通过下面的两幅示意图更进一步了解fork函数执行前后的客户端和服务器之间的状态。

父子进程关闭相应套接字后客户端和服务器端的状态如下:

这就是监听套接字和连接套接字两者的最终状态,子进程处理客户请求,父进程监听其他客户请求。这样的并发服务器看似完美,但是会产生许多僵死进程,这是为什么?下文将会分析。

分治算法之合并排序

2011年4月13日

分治算法的基本思想是将一个规模为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日

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

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);
		}
	}

至此,该函数分析完毕。

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