Ingo Molnar wrote:
* Li Yu <[email protected]> wrote:
Also, I have want to know what's real meaning of
add_wait_runtime(rq, curr, delta_mine - delta_exec);
in update_curr(), IMHO, it should be
add_wait_runtime(rq, curr, delta_mine - delta_fair);
Is this just another heuristics? or my opinion is wrong again? :-)
well, ->wait_runtime is in real time units. If a task executes
delta_exec time on the CPU, we deduct "-delta_exec" 1:1. But during that
time the task also got entitled to a bit more CPU time, that is
+delta_mine. The calculation above expresses this. I'm not sure what
sense '-delta_fair' would make - "delta_fair" is the amount of time a
nice-0 task would be entitled to - but this task might not be a nice-0
task. Furthermore, even for a nice-0 task why deduct -delta_fair - it
spent delta_exec on the CPU.
Eh, I wrong again~ I even took an experiment in last week end, this idea
is really bad! ;(
I think the most inner of source of my wrong again and again is
misunderstanding virtual time. For more better understanding this, I try
to write one python script to simulate CFS behavior. However, It can not
implement the fairness as I want. I really confuse here.
Would you like help me point out what's wrong in it? Any suggestion is
welcome. Thanks in advanced.
#! /usr/bin/python
# htucfs.py - Hard-To-Understand-CFS.py ;)
# Wrote by Li Yu / 20070604
#
# only support static load on UP.
#
# Usage:
# ./htucfs.py nr_clock_ticks_to_run
#
import sys
class task_struct:
def __init__(self, name, load_weight):
self.name = name
self.wait_runtime = 0
self.fair_clock = 0
self.fair_key = 0
self.load_weight = float(load_weight)
def __repr__(self):
return "%s/C%.2f" % (self.name, self.fair_clock)
idle_task = task_struct("idle", 0)
class run_queue:
def __init__(self):
self.raw_weighted_load = 0
self.wall_clock = 0
self.fair_clock = 0
self.ready_queue = {}
self.run_history = []
self.task_list = []
self.curr = None
self.debug = 0
def snapshot(self):
if self.debug:
print "%.2f" % self.fair_clock, self.ready_queue, self.curr
def enqueue(self, task):
task.fair_key = self.fair_clock-task.wait_runtime
task.fair_key = int(100 * task.fair_key)
if not self.ready_queue.get(task.fair_key):
self.ready_queue[task.fair_key] = [task]
else:
# keep FIFO for same fair_key tasks.
self.ready_queue[task.fair_key].append(task)
self.raw_weighted_load += task.load_weight
self.task_list.append(task)
def dequeue(self, task):
self.raw_weighted_load -= task.load_weight
self.ready_queue[task.fair_key].remove(task)
if not self.ready_queue[task.fair_key]:
del self.ready_queue[task.fair_key]
self.task_list.remove(task)
def other_wait_runtime(self):
for task in self.task_list:
self.dequeue(task)
task.wait_runtime += 1
self.enqueue(task)
def clock_tick(self):
# clock_tick = 1.0
self.fair_clock += 1.0/self.raw_weighted_load
# delta_exec = 1.0
delta_mine = self.curr.load_weight / self.raw_weighted_load
self.curr.wait_runtime += (delta_mine-1.0)
self.curr.fair_clock += 1.0/self.curr.load_weight
self.dequeue(self.curr)
self.other_wait_runtime()
self.enqueue(self.curr)
self.pick_next_task()
def pick_next_task(self):
key_seq = self.ready_queue.keys()
if key_seq:
key_seq.sort()
self.curr = self.ready_queue[key_seq[0]][0]
else:
self.curr = idle_task
self.snapshot()
self.record_run_history()
def record_run_history(self):
task = self.curr
if not self.run_history:
self.run_history.append([task, 1])
return
curr = self.run_history[-1]
if curr[0] != task:
self.run_history.append([task, 1])
else:
curr[1] += 1
def show_history(self):
stat = {}
for entry in self.run_history:
task = entry[0]
nsec = entry[1]
print "%s run %d sec" % (task, nsec)
if task not in stat.keys():
stat[task] = nsec
else:
stat[task] += nsec
print "=============================="
tasks = stat.keys()
tasks.sort()
for task in tasks:
print task, "/", task.load_weight, ":", stat[task], "sec"
print "=============================="
def run(self, delta=0, debug=0):
self.debug = debug
until = self.wall_clock + delta
print "-----------------------------"
self.pick_next_task()
while self.wall_clock < until:
self.wall_clock += 1
self.clock_tick()
print "-----------------------------"
#
# To turn this, display verbose runtime information.
#
debug = True
if __name__ == "__main__":
rq = run_queue()
task1 = task_struct("TASK_1", 1)
task2 = task_struct("TASK_2", 1)
task3 = task_struct("TASK_3", 2)
rq.enqueue(task1)
rq.enqueue(task2)
rq.enqueue(task3)
rq.run(int(sys.argv[1]), debug)
rq.show_history()
#EOF
Good luck
- Li Yu
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
