Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1376475 > unrolled thread

[PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

Back to article view | Back to linux.kernel

Contents

  [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC "Bill Huey (hui)" <bill.huey@gmail.com> - 2016-04-12 07:30 +0200
    [PATCH RFC v0 01/12] Kconfig change "Bill Huey (hui)" <bill.huey@gmail.com> - 2016-04-12 07:40 +0200
    [PATCH RFC v0 03/12] Add cyclic support to rtc-dev.c "Bill Huey (hui)" <bill.huey@gmail.com> - 2016-04-12 07:40 +0200
    [PATCH RFC v0 10/12] Export SCHED_FIFO/RT requeuing functions "Bill Huey (hui)" <bill.huey@gmail.com> - 2016-04-12 07:40 +0200
    [PATCH RFC v0 07/12] kernel/userspace additions for addition ioctl() support for rtc "Bill Huey (hui)" <bill.huey@gmail.com> - 2016-04-12 07:40 +0200
    [PATCH RFC v0 08/12] Compilation support "Bill Huey (hui)" <bill.huey@gmail.com> - 2016-04-12 07:40 +0200
    [PATCH RFC v0 02/12] Reroute rtc update irqs to the cyclic scheduler handler "Bill Huey (hui)" <bill.huey@gmail.com> - 2016-04-12 07:40 +0200
    [PATCH RFC v0 12/12] Cyclic/rtc documentation "Bill Huey (hui)" <bill.huey@gmail.com> - 2016-04-12 07:40 +0200
    [PATCH RFC v0 06/12] Add anonymous struct to sched_rt_entity "Bill Huey (hui)" <bill.huey@gmail.com> - 2016-04-12 07:40 +0200
    [PATCH RFC v0 05/12] Task tracking per file descriptor "Bill Huey (hui)" <bill.huey@gmail.com> - 2016-04-12 07:40 +0200
    Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC Mike Galbraith <umgwanakikbuti@gmail.com> - 2016-04-12 08:00 +0200
      Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC Mike Galbraith <umgwanakikbuti@gmail.com> - 2016-04-12 08:10 +0200
    Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC Juri Lelli <juri.lelli@arm.com> - 2016-04-13 11:00 +0200
      Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC "Bill Huey (hui)" <bill.huey@gmail.com> - 2016-04-13 11:40 +0200
        Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC Juri Lelli <juri.lelli@arm.com> - 2016-04-13 12:10 +0200
          Re: [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC "Bill Huey (hui)" <bill.huey@gmail.com> - 2016-04-13 12:40 +0200

#1376475 — [PATCH RFC v0 00/12] Cyclic Scheduler Against RTC

Hi,

This a crude cyclic scheduler implementation. It uses SCHED_FIFO tasks
and runs them according to a map pattern specified by a 64 bit mask. Each
bit corresponds to an entry into an 64 entry array of
'struct task_struct'. This works single core CPU 0 only for now.

Threads are 'admitted' to this map by an extension to the ioctl() via the
of (rtc) real-time clock interface. The bit pattern then determines when
the task will run or activate next.

The /dev/rtc interface is choosen for this purpose because of its
accessibilty to userspace. For example, the mplayer program already use
it as a timer source and could possibly benefit from being sync to a
vertical retrace interrupt during decoding. Could be an OpenGL program
needing precisely scheduler support for those same handling vertical
retrace interrupts, low latency audio and timely handling of touch
events amognst other uses.

There is also a need for some kind of blocking/yielding interface that can
return an overrun count for when the thread utilizes more time than
allocated for that frame. The read() function in rtc is overloaded for this
purpose and reports overrun events. Yield functionality has yet to be fully
tested.

I apologize for any informal or misused of terminology as I haven't fully
reviewed all of the academic literature regarding these kind of schedulers.
I welcome suggestions and corrects etc

Special thanks to includes...

Peter Ziljstra (Intel), Steve Rostedt (Red Hat), Rik van Riel (Red Hat) for
encouraging me to continue working in the Linux kernel community and being
generally positive and supportive.

KY Srinivasan (formerly Novell now Microsoft) for discussion of real-time
schedulers and pointers to specifics on that topic. It was just a single
discussion but was basically the inspiration for this kind of work.

Amir Frenkel (Palm), Kenneth Albanowski (Palm), Bdale Garbee (HP) for the
amazing place that was Palm, Kenneth for being a co-conspirator with this
scheduler. This scheduler was inspired by performance work that I did
at Palm's kernel group along with discussions with the multimedia team
before HP kill webOS off. Sad and infuriating moment.

Maybe, in a short while, the community will understand the value of these
patches for -rt and start solving the general phenomenon of high performance
multi-media and user interactivity problems more properly with both a
scheduler like this and -rt shipped as default in the near future.

[Also, I'd love some kind of sponsorship to continue what I think is
critical work versus heading back into the valley]

---

Bill Huey (hui) (12):
  Kconfig change
  Reroute rtc update irqs to the cyclic scheduler handler
  Add cyclic support to rtc-dev.c
  Anonymous struct initialization
  Task tracking per file descriptor
  Add anonymous struct to sched_rt_entity
  kernel/userspace additions for addition ioctl() support for rtc
  Compilation support
  Add priority support for the cyclic scheduler
  Export SCHED_FIFO/RT requeuing functions
  Cyclic scheduler support
  Cyclic/rtc documentation

 Documentation/scheduler/sched-cyclic-rtc.txt | 468 ++++++++++++++++++++
 drivers/rtc/Kconfig                          |   5 +
 drivers/rtc/class.c                          |   3 +
 drivers/rtc/interface.c                      |  23 +
 drivers/rtc/rtc-dev.c                        | 161 +++++++
 include/linux/init_task.h                    |  18 +
 include/linux/rtc.h                          |   3 +
 include/linux/sched.h                        |  15 +
 include/uapi/linux/rtc.h                     |   4 +
 kernel/sched/Makefile                        |   1 +
 kernel/sched/core.c                          |  13 +
 kernel/sched/cyclic.c                        | 620 +++++++++++++++++++++++++++
 kernel/sched/cyclic.h                        |  86 ++++
 kernel/sched/cyclic_rt.h                     |   7 +
 kernel/sched/rt.c                            |  41 ++
 15 files changed, 1468 insertions(+)
 create mode 100644 Documentation/scheduler/sched-cyclic-rtc.txt
 create mode 100644 kernel/sched/cyclic.c
 create mode 100644 kernel/sched/cyclic.h
 create mode 100644 kernel/sched/cyclic_rt.h

-- 
2.5.0

[toc] | [next] | [standalone]

#1376476 — [PATCH RFC v0 01/12] Kconfig change

Add the selection options for the cyclic scheduler

Signed-off-by: Bill Huey (hui) <bill.huey@gmail.com>
---
 drivers/rtc/Kconfig | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/drivers/rtc/Kconfig b/drivers/rtc/Kconfig
index 544bd34..8a1b704 100644
--- a/drivers/rtc/Kconfig
+++ b/drivers/rtc/Kconfig
@@ -73,6 +73,11 @@ config RTC_DEBUG
 	  Say yes here to enable debugging support in the RTC framework
 	  and individual RTC drivers.
 
+config RTC_CYCLIC
+	bool "RTC cyclic executive scheduler support"
+	help
+	  Frame/Cyclic executive scheduler support through the RTC interface
+
 comment "RTC interfaces"
 
 config RTC_INTF_SYSFS
-- 
2.5.0

[toc] | [prev] | [next] | [standalone]

#1376477 — [PATCH RFC v0 03/12] Add cyclic support to rtc-dev.c

wait-queue changes to rtc_dev_read so that it can support overrun count
reporting when multiple threads are blocked against a single wait object.

ioctl() additions to allow for those calling it to admit the thread to the
cyclic scheduler.

Signed-off-by: Bill Huey (hui) <bill.huey@gmail.com>
---
 drivers/rtc/rtc-dev.c | 161 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 161 insertions(+)

diff --git a/drivers/rtc/rtc-dev.c b/drivers/rtc/rtc-dev.c
index a6d9434..0fc9a8c 100644
--- a/drivers/rtc/rtc-dev.c
+++ b/drivers/rtc/rtc-dev.c
@@ -18,6 +18,15 @@
 #include <linux/sched.h>
 #include "rtc-core.h"
 
+#ifdef CONFIG_RTC_CYCLIC
+#include <linux/proc_fs.h>
+#include <linux/seq_file.h>
+
+#include <../kernel/sched/sched.h>
+#include <../kernel/sched/cyclic.h>
+//#include <../kernel/sched/cyclic_rt.h>
+#endif
+
 static dev_t rtc_devt;
 
 #define RTC_DEV_MAX 16 /* 16 RTCs should be enough for everyone... */
@@ -29,6 +38,10 @@ static int rtc_dev_open(struct inode *inode, struct file *file)
 					struct rtc_device, char_dev);
 	const struct rtc_class_ops *ops = rtc->ops;
 
+#ifdef CONFIG_RTC_CYCLIC
+	reset_rt_overrun();
+#endif
+
 	if (test_and_set_bit_lock(RTC_DEV_BUSY, &rtc->flags))
 		return -EBUSY;
 
@@ -153,13 +166,26 @@ rtc_dev_read(struct file *file, char __user *buf, size_t count, loff_t *ppos)
 {
 	struct rtc_device *rtc = file->private_data;
 
+#ifdef CONFIG_RTC_CYCLIC
+	DEFINE_WAIT_FUNC(wait, single_default_wake_function);
+#else
 	DECLARE_WAITQUEUE(wait, current);
+#endif
 	unsigned long data;
+	unsigned long flags;
+#ifdef CONFIG_RTC_CYCLIC
+	int wake = 0, block = 0;
+#endif
 	ssize_t ret;
 
 	if (count != sizeof(unsigned int) && count < sizeof(unsigned long))
 		return -EINVAL;
 
+#ifdef CONFIG_RTC_CYCLIC
+	if (rt_overrun_task_yield(current))
+		goto yield;
+#endif
+printk("%s: 0 color = %d \n", __func__, current->rt.rt_overrun.color);
 	add_wait_queue(&rtc->irq_queue, &wait);
 	do {
 		__set_current_state(TASK_INTERRUPTIBLE);
@@ -169,23 +195,59 @@ rtc_dev_read(struct file *file, char __user *buf, size_t count, loff_t *ppos)
 		rtc->irq_data = 0;
 		spin_unlock_irq(&rtc->irq_lock);
 
+if (block) {
+	block = 0;
+	if (wake) {
+		printk("%s: wake \n", __func__);
+		wake = 0;
+	} else {
+		printk("%s: ~wake \n", __func__);
+	}
+}
 		if (data != 0) {
+#ifdef CONFIG_RTC_CYCLIC
+			/* overrun reporting */
+			raw_spin_lock_irqsave(&rt_overrun_lock, flags);
+			if (_on_rt_overrun_admitted(current)) {
+				/* pass back to userspace */
+				data = rt_task_count(current);
+				rt_task_count(current) = 0;
+			}
+			raw_spin_unlock_irqrestore(&rt_overrun_lock, flags);
+			ret = 0;
+printk("%s: 1 color = %d \n", __func__, current->rt.rt_overrun.color);
+			break;
+		}
+#else
 			ret = 0;
 			break;
 		}
+#endif
 		if (file->f_flags & O_NONBLOCK) {
 			ret = -EAGAIN;
+printk("%s: 2 color = %d \n", __func__, current->rt.rt_overrun.color);
 			break;
 		}
 		if (signal_pending(current)) {
+printk("%s: 3 color = %d \n", __func__, current->rt.rt_overrun.color);
 			ret = -ERESTARTSYS;
 			break;
 		}
+#ifdef CONFIG_RTC_CYCLIC
+		block = 1;
+#endif
 		schedule();
+#ifdef CONFIG_RTC_CYCLIC
+		/* debugging */
+		wake = 1;
+#endif
 	} while (1);
 	set_current_state(TASK_RUNNING);
 	remove_wait_queue(&rtc->irq_queue, &wait);
 
+#ifdef CONFIG_RTC_CYCLIC
+ret:
+#endif
 	if (ret == 0) {
 		/* Check for any data updates */
 		if (rtc->ops->read_callback)
@@ -201,6 +263,29 @@ rtc_dev_read(struct file *file, char __user *buf, size_t count, loff_t *ppos)
 				sizeof(unsigned long);
 	}
 	return ret;
+
+#ifdef CONFIG_RTC_CYCLIC
+yield:
+
+	spin_lock_irq(&rtc->irq_lock);
+	data = rtc->irq_data;
+	rtc->irq_data = 0;
+	spin_unlock_irq(&rtc->irq_lock);
+
+	raw_spin_lock_irqsave(&rt_overrun_lock, flags);
+	if (_on_rt_overrun_admitted(current)) {
+		/* pass back to userspace */
+		data = rt_task_count(current);
+		rt_task_count(current) = 0;
+	}
+	else {
+	}
+
+	raw_spin_unlock_irqrestore(&rt_overrun_lock, flags);
+	ret = 0;
+
+	goto ret;
+#endif
 }
 
 static unsigned int rtc_dev_poll(struct file *file, poll_table *wait)
@@ -215,6 +300,56 @@ static unsigned int rtc_dev_poll(struct file *file, poll_table *wait)
 	return (data != 0) ? (POLLIN | POLLRDNORM) : 0;
 }
 
+#ifdef CONFIG_RTC_CYCLIC
+extern asmlinkage __visible void __sched notrace preempt_schedule(void);
+
+/* yield behavior * /
+int rt_overrun_task_yield_block(struct task_struct *p)
+{
+	struct rq *rq = task_rq(p);
+	unsigned int block = 1;
+
+	if (test_case)
+	else
+		return 1;
+
+	if (rt_overrun_task_is_best_effort(p)) {
+		// assert that it should be on the rq
+		// move to the end, let pick_next_task_rt() deal with the next runnable task
+		requeue_task_rt2(rq, p, false);
+
+		//clear_overrun_log();
+
+		if (_cond_resched()) {
+			// we reschedule here
+		}
+
+		block = 0;
+	}
+
+	return block;
+} */
+
+int test_admit(u64 slots)
+{
+	/* Only allow the current task to be admitted for now
+	 * and allow for /proc to show the slot pattern
+	 * in a global fashion */
+	return rt_overrun_task_admit(current, slots);
+}
+
+int test_yield(u64 slots)
+{
+	rt_task_yield(current) = slots;
+	return 0;
+}
+
+void test_replenish(void)
+{
+	rt_overrun_task_replenish(current);
+}
+#endif
+
 static long rtc_dev_ioctl(struct file *file,
 		unsigned int cmd, unsigned long arg)
 {
@@ -223,6 +358,9 @@ static long rtc_dev_ioctl(struct file *file,
 	const struct rtc_class_ops *ops = rtc->ops;
 	struct rtc_time tm;
 	struct rtc_wkalrm alarm;
+#ifdef CONFIG_RTC_CYCLIC
+	u64 slots;
+#endif
 	void __user *uarg = (void __user *) arg;
 
 	err = mutex_lock_interruptible(&rtc->ops_lock);
@@ -250,6 +388,12 @@ static long rtc_dev_ioctl(struct file *file,
 				!capable(CAP_SYS_RESOURCE))
 			err = -EACCES;
 		break;
+#ifdef CONFIG_RTC_CYCLIC
+	case RTC_OV_REPLEN:
+		test_replenish();
+		err = -EACCES;
+		break;
+#endif
 	}
 
 	if (err)
@@ -380,7 +524,21 @@ static long rtc_dev_ioctl(struct file *file,
 	case RTC_IRQP_READ:
 		err = put_user(rtc->irq_freq, (unsigned long __user *)uarg);
 		break;
+#ifdef CONFIG_RTC_CYCLIC
+	case RTC_OV_YIELD:
+		mutex_unlock(&rtc->ops_lock);
+		if (copy_from_user(&slots, uarg, sizeof(u64)))
+			return -EFAULT;
+
+		return test_yield(slots);
+
+	case RTC_OV_ADMIT:
+		mutex_unlock(&rtc->ops_lock);
+		if (copy_from_user(&slots, uarg, sizeof(u64)))
+			return -EFAULT;
 
+		return test_admit(slots);
+#endif
 	case RTC_WKALM_SET:
 		mutex_unlock(&rtc->ops_lock);
 		if (copy_from_user(&alarm, uarg, sizeof(alarm)))
@@ -424,6 +582,9 @@ static int rtc_dev_release(struct inode *inode, struct file *file)
 {
 	struct rtc_device *rtc = file->private_data;
 
+#ifdef CONFIG_RTC_CYCLIC
+	rt_overrun_entries_delete_all(rtc);
+#endif
 	/* We shut down the repeating IRQs that userspace enabled,
 	 * since nothing is listening to them.
 	 *  - Update (UIE) ... currently only managed through ioctls
-- 
2.5.0

[toc] | [prev] | [next] | [standalone]

#1376478 — [PATCH RFC v0 10/12] Export SCHED_FIFO/RT requeuing functions

SCHED_FIFO/RT tail/head runqueue insertion support, initial thread death
support via a hook to the scheduler class. Thread death must include
additional semantics to remove/discharge an admitted task properly.

Signed-off-by: Bill Huey (hui) <bill.huey@gmail.com>
---
 kernel/sched/rt.c | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)

diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index c41ea7a..1d77adc 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -8,6 +8,11 @@
 #include <linux/slab.h>
 #include <linux/irq_work.h>
 
+#ifdef CONFIG_RTC_CYCLIC
+#include "cyclic.h"
+extern int rt_overrun_task_admitted1(struct rq *rq, struct task_struct *p);
+#endif
+
 int sched_rr_timeslice = RR_TIMESLICE;
 
 static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun);
@@ -1321,8 +1326,18 @@ enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags)
 
 	if (flags & ENQUEUE_WAKEUP)
 		rt_se->timeout = 0;
+#ifdef CONFIG_RTC_CYCLIC
+	/* if admitted and the current slot then head, otherwise tail */
+	if (rt_overrun_task_admitted1(rq, p)) {
+		if (rt_overrun_task_active(p)) {
+			flags |= ENQUEUE_HEAD;
+		}
+	}
 
 	enqueue_rt_entity(rt_se, flags);
+#else
+	enqueue_rt_entity(rt_se, flags & ENQUEUE_HEAD);
+#endif
 
 	if (!task_current(rq, p) && p->nr_cpus_allowed > 1)
 		enqueue_pushable_task(rq, p);
@@ -1367,6 +1382,18 @@ static void requeue_task_rt(struct rq *rq, struct task_struct *p, int head)
 	}
 }
 
+#ifdef CONFIG_RTC_CYCLIC
+void dequeue_task_rt2(struct rq *rq, struct task_struct *p, int flags)
+{
+	dequeue_task_rt(rq, p, flags);
+}
+
+void requeue_task_rt2(struct rq *rq, struct task_struct *p, int head)
+{
+	requeue_task_rt(rq, p, head);
+}
+#endif
+
 static void yield_task_rt(struct rq *rq)
 {
 	requeue_task_rt(rq, rq->curr, 0);
@@ -2177,6 +2204,10 @@ void __init init_sched_rt_class(void)
 		zalloc_cpumask_var_node(&per_cpu(local_cpu_mask, i),
 					GFP_KERNEL, cpu_to_node(i));
 	}
+
+#ifdef CONFIG_RTC_CYCLIC
+	init_rt_overrun();
+#endif
 }
 #endif /* CONFIG_SMP */
 
@@ -2322,6 +2353,13 @@ static unsigned int get_rr_interval_rt(struct rq *rq, struct task_struct *task)
 		return 0;
 }
 
+#ifdef CONFIG_RTC_CYCLIC
+static void task_dead_rt(struct task_struct *p)
+{
+	rt_overrun_entry_delete(p);
+}
+#endif
+
 const struct sched_class rt_sched_class = {
 	.next			= &fair_sched_class,
 	.enqueue_task		= enqueue_task_rt,
@@ -2344,6 +2382,9 @@ const struct sched_class rt_sched_class = {
 #endif
 
 	.set_curr_task          = set_curr_task_rt,
+#ifdef CONFIG_RTC_CYCLIC
+	.task_dead              = task_dead_rt,
+#endif
 	.task_tick		= task_tick_rt,
 
 	.get_rr_interval	= get_rr_interval_rt,
-- 
2.5.0

[toc] | [prev] | [next] | [standalone]

#1376479 — [PATCH RFC v0 07/12] kernel/userspace additions for addition ioctl() support for rtc

Add additional ioctl() values to rtc so that it can 'admit' the calling
thread into a red-black tree for tracking, set the execution slot pattern,
support for setting whether read() will yield or block.

Signed-off-by: Bill Huey (hui) <bill.huey@gmail.com>
---
 include/uapi/linux/rtc.h | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/include/uapi/linux/rtc.h b/include/uapi/linux/rtc.h
index f8c82e6..76c9254 100644
--- a/include/uapi/linux/rtc.h
+++ b/include/uapi/linux/rtc.h
@@ -94,6 +94,10 @@ struct rtc_pll_info {
 #define RTC_VL_READ	_IOR('p', 0x13, int)	/* Voltage low detector */
 #define RTC_VL_CLR	_IO('p', 0x14)		/* Clear voltage low information */
 
+#define RTC_OV_ADMIT	_IOW('p', 0x15, unsigned long)	 /* Set test       */
+#define RTC_OV_REPLEN	_IOW('p', 0x16, unsigned long)	 /* Set test       */
+#define RTC_OV_YIELD	_IOW('p', 0x17, unsigned long)	 /* Set test       */
+
 /* interrupt flags */
 #define RTC_IRQF 0x80	/* Any of the following is active */
 #define RTC_PF 0x40	/* Periodic interrupt */
-- 
2.5.0

[toc] | [prev] | [next] | [standalone]

#1376480 — [PATCH RFC v0 08/12] Compilation support

Makefile changes to support the menuconfig option

Signed-off-by: Bill Huey (hui) <bill.huey@gmail.com>
---
 kernel/sched/Makefile | 1 +
 1 file changed, 1 insertion(+)

diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
index 302d6eb..df8e131 100644
--- a/kernel/sched/Makefile
+++ b/kernel/sched/Makefile
@@ -19,4 +19,5 @@ obj-$(CONFIG_SCHED_AUTOGROUP) += auto_group.o
 obj-$(CONFIG_SCHEDSTATS) += stats.o
 obj-$(CONFIG_SCHED_DEBUG) += debug.o
 obj-$(CONFIG_CGROUP_CPUACCT) += cpuacct.o
+obj-$(CONFIG_RTC_CYCLIC) += cyclic.o
 obj-$(CONFIG_CPU_FREQ) += cpufreq.o
-- 
2.5.0

[toc] | [prev] | [next] | [standalone]

#1376481 — [PATCH RFC v0 02/12] Reroute rtc update irqs to the cyclic scheduler handler

Redirect rtc update irqs so that it drives the cyclic scheduler timer
handler instead. Let the handler determine which slot to activate next.
Similar to scheduler tick handling but just for the cyclic scheduler.

Signed-off-by: Bill Huey (hui) <bill.huey@gmail.com>
---
 drivers/rtc/interface.c | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

diff --git a/drivers/rtc/interface.c b/drivers/rtc/interface.c
index 9ef5f6f..6d39d40 100644
--- a/drivers/rtc/interface.c
+++ b/drivers/rtc/interface.c
@@ -17,6 +17,10 @@
 #include <linux/log2.h>
 #include <linux/workqueue.h>
 
+#ifdef CONFIG_RTC_CYCLIC
+#include "../kernel/sched/cyclic.h"
+#endif
+
 static int rtc_timer_enqueue(struct rtc_device *rtc, struct rtc_timer *timer);
 static void rtc_timer_remove(struct rtc_device *rtc, struct rtc_timer *timer);
 
@@ -488,6 +492,9 @@ EXPORT_SYMBOL_GPL(rtc_update_irq_enable);
 void rtc_handle_legacy_irq(struct rtc_device *rtc, int num, int mode)
 {
 	unsigned long flags;
+#ifdef CONFIG_RTC_CYCLIC
+	int handled = 0;
+#endif
 
 	/* mark one irq of the appropriate mode */
 	spin_lock_irqsave(&rtc->irq_lock, flags);
@@ -500,7 +507,23 @@ void rtc_handle_legacy_irq(struct rtc_device *rtc, int num, int mode)
 		rtc->irq_task->func(rtc->irq_task->private_data);
 	spin_unlock_irqrestore(&rtc->irq_task_lock, flags);
 
+#ifdef CONFIG_RTC_CYCLIC
+	/* wake up slot_curr if overrun task */
+	if (RTC_PF) {
+		if (rt_overrun_rq_admitted()) {
+			/* advance the cursor, overrun report */
+			rt_overrun_timer_handler(rtc);
+			handled = 1;
+		}
+	}
+
+	if (!handled) {
+		wake_up_interruptible(&rtc->irq_queue);
+	}
+#else
 	wake_up_interruptible(&rtc->irq_queue);
+#endif
+
 	kill_fasync(&rtc->async_queue, SIGIO, POLL_IN);
 }
 
-- 
2.5.0

[toc] | [prev] | [next] | [standalone]

#1376482 — [PATCH RFC v0 12/12] Cyclic/rtc documentation

Initial attempt at documentation with a test program

Signed-off-by: Bill Huey (hui) <bill.huey@gmail.com>
---
 Documentation/scheduler/sched-cyclic-rtc.txt | 468 +++++++++++++++++++++++++++
 1 file changed, 468 insertions(+)
 create mode 100644 Documentation/scheduler/sched-cyclic-rtc.txt

diff --git a/Documentation/scheduler/sched-cyclic-rtc.txt b/Documentation/scheduler/sched-cyclic-rtc.txt
new file mode 100644
index 0000000..4d22381
--- /dev/null
+++ b/Documentation/scheduler/sched-cyclic-rtc.txt
@@ -0,0 +1,468 @@
+[in progress]
+
+"Work Conserving"
+
+When a task is active and calls read(), it will block/yield depending on
+is requested from the cyclic scheduler. A RT_OV_YIELD call to ioctl()
+specifies the behavior for the calling thread.
+
+In the case where read() is called before the time slice is over, it will
+allow other tasks to run with the leftover time.
+
+"Overrun Reporting/Apps"
+
+Calls to read() will return the overrun count and zero the counter. This
+can be used to adjust the execution time of the thread so that it can run
+within that slot so that thread can meet some deadline constraint.
+
+[no decision has been made to return a more meaningful set of numbers as
+you can just get time stamps and do the math in userspace but it could
+be changed to do so]
+
+The behavior of the read() depends on whether it has been admitted or not
+via an ioctl() using RTC_OV_ADMIT. If it is then it will return the overrun
+count. If this is not admitted then it returns value corresponding to the
+default read() behavior for rtc.
+
+See the sample test sources for details.
+
+Using a video game as an example, having a rendering engine overrunning its
+slot driving by a vertical retrace interrupt can cause visual skipping and
+hurt interactivity. Adapting the computation from the read() result can
+allow for the frame buffer swap at the frame interrupt. If read() reports
+and it can simplify calculations and adapt to fit within that slot.
+It would then allow the program to respond to events (touches, buttons)
+minimizing the possibility of perceived pauses.
+
+The slot allocation scheme for the video game must have some inherit
+definition of interactivity. That determines appropriate slot allocation
+amognst a mixture of soft/hard real-time. A general policy must be created
+for the system, and all programs, to meet a real-time criteria.
+
+"Admittance"
+
+Admittance of a task is done through a ioctl() call using RTC_OV_ADMIT.
+This passes 64 bit wide bitmap that maps onto a entries in the slot map.
+
+(slot map of two threads)
+execution direction ->
+
+1000 1000 1000 1000...
+0100 0100 0100 0100...
+
+(bit pattern of two threads)
+0001 0001 0001 0001...
+0010 0010 0010 0010...
+
+(hex)
+0x1111
+0x2222
+
+The slot map is an array of 64 entries of threads. An index is increment
+through determine what the next active thread-slot will be. The end of the
+index set in /proc/rt_overrun_proc
+
+"Slot/slice activation"
+
+Move the task to the front of the SCHED_FIFO list when active, the tail when
+inactive.
+
+"RTC Infrastructure and Interrupt Routing"
+
+The cyclic scheduler is driven by the update interrupt in the RTC
+infrastructure but can be rerouted to any periodic interrupt source.
+
+One of those applications could be when interrupts from a display refresh
+happen or some interval where an external controller such as a drum pad,
+touch event or whatever.
+
+"Embedded Environments"
+
+This is single run queue only and targeting embedded scenarios where not all
+cores are guaranteed to be available. Older Qualcomm MSM kernels have a very
+aggressive cpu hotplug as a means of fully powering off cores. The only
+guaranteed CPU to run is CPU 0.
+
+"Project History"
+
+This was originally created when I was at HP/Palm to solve issues related
+to touch event handling and lag working with the real-time media subsystem.
+The typical workaround used to prevent skipping is to use large buffers to
+prevent data underruns. The programs running at SCHED_FIFO which can
+starve the system from handling external events in a timely manner like
+buttons or touch events. The lack of a globally defined policy of how to
+use real-time resources can causes long pauses between handling touch
+events and other kinds of implicit deadline misses.
+
+By choosing some kind of slot execution pattern, it was hoped that it that
+can be controlled globally across the system so that some basic interactive
+guarantees can be met. Whether the tasks be some combination of soft or
+hard real-time, a mechanism like this can help guide how SCHED_FIFO tasks
+are run versus letting SCHED_FIFO tasks run wildly.
+
+"Future work"
+
+Possible integration with the deadline scheduler. Power management
+awareness, CPU clock governor. Turning off the scheduler tick when there
+are no runnable tasks, other things...
+
+"Power management"
+
+Governor awareness...
+
+[more]
+
+----------------------------
+
+/*
+ *	Based on the:
+ *
+ *      Real Time Clock Driver Test/Example Program
+ *      by Copyright (C) 1996, Paul Gortmaker.
+ * 
+ *	Simplification and multi-threading support for interrupt event testing
+ *	by Bill Huey at <bill.huey@gmail.com>
+ *
+ *      Released under the GNU General Public License, version 2,
+ *      included herein by reference.
+ */
+
+#include <stdio.h>
+#include <linux/rtc.h>
+#include <sys/ioctl.h>
+#include <sys/time.h>
+#include <sys/types.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <pthread.h>
+#include <linux/types.h>
+#include <sys/mman.h>
+#include <sched.h>
+#include <errno.h>
+
+/*
+ * This expects the new RTC class driver framework, working with
+ * clocks that will often not be clones of what the PC-AT had.
+ * Use the command line to specify another RTC if you need one.
+ */
+static const char default_rtc[] = "/dev/rtc0";
+
+#define RTC_OV_ADMIT	_IOW('p', 0x15, unsigned long)
+#define RTC_OV_REPLEN	_IOW('p', 0x16, unsigned long)
+#define RTC_OV_YIELD	_IOW('p', 0x17, unsigned long)
+
+//#if 0
+#define THREADS	(3)
+#define handle_error_en(en, msg) \
+               do { errno = en; perror(msg); exit(EXIT_FAILURE); } while (0)
+
+#define OBJ (THREADS + 1)
+
+//#define LARGE (1000 * 1000)
+
+pthread_mutex_t mutex[OBJ];
+pthread_cond_t condvar[OBJ];
+
+pthread_mutex_t start_mutex = PTHREAD_MUTEX_INITIALIZER;
+pthread_cond_t start_condvar = PTHREAD_COND_INITIALIZER;
+int start[OBJ];
+
+pthread_t threads[OBJ];
+volatile int die = 0;
+int fd;
+
+#define ioctl_enotty_err(a, b, c, label, ret)			\
+	retval = ioctl(fd, a, ret);				\
+	if (retval == -1) {					\
+		if (errno == ENOTTY) {				\
+			fprintf(stderr, b);			\
+			goto label;				\
+		}						\
+		perror(c);					\
+		exit(errno);					\
+	}
+
+#define ioctl_err(a, b, c)					\
+	retval = ioctl(fd, a, c);				\
+	if (retval == -1) {					\
+		perror(b);					\
+		exit(errno);					\
+	}
+
+#define read_err(a) 						\
+	retval = read(fd, &data, sizeof(unsigned long));	\
+	if (retval == -1) {					\
+		perror("read");					\
+		exit(errno);					\
+	}
+
+void init_pthreads(void)
+{
+	int i;
+
+	for (i = 0; i < OBJ; ++i) {
+		start[i] = 1;
+		pthread_mutex_init(&mutex[i], NULL);
+		pthread_cond_init(&condvar[i], NULL);
+	}
+}
+
+/* Just loop and exit */
+void *thread(void *threadid)
+{
+	long tid = (unsigned long)threadid;
+	pthread_t self = pthread_self();
+	unsigned int i,j;
+	pid_t pid;
+	struct sched_param param;
+	int retval;
+	__aligned_u64 slots = 0;
+	unsigned long data;
+
+	fprintf(stderr, "\tthread id = %ld\n", tid);
+	param.sched_priority = sched_get_priority_min(SCHED_RR);
+	if (sched_setscheduler( 0, SCHED_RR, &param) == -1)
+		perror("sched_setscheduler failed\n");
+
+	pid = getpid();
+
+	if (start) {
+		start[tid] = 0;
+		pthread_mutex_lock(&start_mutex);
+		pthread_cond_signal(&start_condvar);
+		pthread_mutex_unlock(&start_mutex);
+	}
+
+	/* admit the task before doing yields */
+//	fprintf(stderr, "\n");
+	for (i = 0; i < 64; ++i) {
+		if (((tid + i) % THREADS) == 0) {
+//			fprintf(stderr, "%d\n", i);
+			slots |= ((long long unsigned) 1 << i);
+		}
+	}
+
+	fprintf(stderr, "slots = 0x%016llx\n", slots);
+	ioctl_err(RTC_OV_ADMIT, "RTC_OV_ADMIT ioctl", &slots);
+
+//	slots = 1; /* set yield instead of block */
+//	ioctl_err(RTC_OV_YIELD, "RTC_OV_YIELD ioctl", &slots);
+
+	while (!die)
+		;
+
+	read_err();
+	fprintf(stderr, "tid %ld, 0x%04lx\n", tid, data);
+
+#if 0
+	ioctl_enotty_err(RTC_IRQP_SET,
+		"\n...Periodic IRQ rate is fixed\n",
+		"RTC_IRQP_SET ioctl",
+		done, (unsigned long ) slots);
+
+	ioctl_err(RTC_PIE_ON, "RTC_PIE_ON ioctl", 0);
+
+	while (!die)
+		;
+
+	ioctl_err(RTC_PIE_OFF, "RTC_PIE_OFF ioctl", 0);
+#endif
+	/* body */
+
+	fprintf(stderr, "\tthread exited running SCHED_RR = %ld\n", tid);
+	pthread_exit(NULL);
+}
+
+void thread_spawn(int val)
+{
+	int result, retval;
+	long tid;
+	int i;
+	pthread_attr_t threads_attr[OBJ];
+	cpu_set_t cpuset;
+
+	struct sched_param schedparam;
+
+	schedparam.sched_priority = 3;
+
+	init_pthreads();
+
+	tid = 0;
+	while(tid < THREADS) {
+		fprintf(stderr, "\ncreated thread %ld\n", tid);
+		pthread_attr_init(&threads_attr[tid]);
+		pthread_attr_setinheritsched(&threads_attr[tid], PTHREAD_EXPLICIT_SCHED);
+		pthread_attr_setschedpolicy(&threads_attr[tid], SCHED_RR);
+		pthread_attr_setschedparam(&threads_attr[tid], &schedparam);
+		pthread_attr_destroy(&threads_attr[tid]);
+
+		pthread_mutex_lock(&start_mutex);
+		result = pthread_create(&threads[tid], &threads_attr[tid], thread, (void *)tid);
+		pthread_cond_wait(&start_condvar, &start_mutex);
+		pthread_mutex_unlock(&start_mutex);
+
+		if (result != 0)
+			handle_error_en(result, "pthread_create");
+		++tid;
+	}
+
+	ioctl_err(RTC_PIE_ON, "RTC_PIE_ON ioctl", 0);
+
+	sleep(3);
+	
+//	10/val; // deliberate divide by zero
+
+	sleep(1);
+	die = 1;
+
+	for (i = 0; i < THREADS; i++)
+		pthread_join(threads[i], NULL);
+
+	ioctl_err(RTC_PIE_OFF, "RTC_PIE_OFF ioctl", 0);
+
+	fprintf(stderr, "pthread done\n");
+}
+//#endif
+
+int main(int argc, char **argv)
+{
+	int	i,j,k,
+		blocking,
+		delay,
+		retval, irqcount = 0;
+	unsigned long data;
+	__aligned_u64 slots;
+	struct rtc_time rtc_tm;
+	const char *rtc = default_rtc;
+	struct timeval start, end, diff;
+
+	struct sched_param param;
+	pid_t pid = getpid();
+
+	/* testing thread should be SCHED_FIFO or RR */
+	param.sched_priority = sched_get_priority_min(SCHED_RR);
+
+	if (sched_setscheduler(pid, SCHED_RR, &param) == -1)
+
+		perror("sched_setscheduler failed\n");
+
+	switch (argc) {
+	case 2:
+		rtc = argv[1];
+		/* FALLTHROUGH */
+	case 1:
+		break;
+	default:
+		fprintf(stderr, "usage:  rtctest [rtcdev]\n");
+		return 1;
+	}
+
+	fd = open(rtc, O_RDONLY);
+	if (fd ==  -1) {
+		perror(rtc);
+		exit(errno);
+	}
+
+	fprintf(stderr, "\n\t\t\tRTC Driver Test Example.\n\n");
+
+	/* Admit this task, enable tick tracking and set the slots */
+//	slots = 0xFFFFffffFFFFffff;
+	slots = 0x3333333333333333;
+	ioctl_err(RTC_OV_ADMIT, "RTC_OV_ADMIT ioctl", &slots);
+
+#if 0
+#endif
+test_PIE:
+	/* Read periodic IRQ rate */
+	ioctl_enotty_err(RTC_IRQP_READ,
+		"\nNo periodic IRQ support\n",
+		"RTC_IRQP_READ ioctl",
+		done, &slots);
+
+	fprintf(stderr, "\nPeriodic IRQ rate is %ldHz.\n", (unsigned long) slots);
+
+	fprintf(stderr, "Counting 20 interrupts at:");
+	fflush(stderr);
+
+	/* The frequencies 128Hz, 256Hz, ... 8192Hz are only allowed for root. */
+	for (slots=2; slots<=64; slots*=2) {
+		/* not all RTCs can change their periodic IRQ rate */
+		ioctl_enotty_err(RTC_IRQP_SET,
+			"\n...Periodic IRQ rate is fixed\n",
+			"RTC_IRQP_SET ioctl",
+			done, (unsigned long ) slots);
+
+		fprintf(stderr, "\n%ldHz:\t", (unsigned long ) slots);
+		fflush(stderr);
+
+		/* Enable periodic interrupts */
+		ioctl_err(RTC_PIE_ON, "RTC_PIE_ON ioctl", 0);
+
+//		blocking = 0; delay = 0;
+		blocking = 0; delay = 1;
+//		blocking = 1; delay = 0;
+//		blocking = 1; delay = 1;
+		for (i=1; i<6; i++) {
+
+#define LARGE 5000
+#define LARGE2 50000
+#define work() 									\
+										\
+			/* This blocks */					\
+			if (blocking) {						\
+				if (delay)					\
+					fprintf(stderr, " ignoring delay ");	\
+										\
+				gettimeofday(&start, NULL);			\
+				fprintf(stderr, " ");				\
+				read_err()					\
+			} else {						\
+				/* delay for testing yield only	*/		\
+				if (delay) {					\
+					fprintf(stderr, ".");			\
+					for(j = LARGE; j > 0; --j)		\
+						for(k = LARGE2; k > 0; --k)	\
+							;			\
+				} else						\
+					fprintf(stderr, "`");			\
+										\
+				/* really a yield */				\
+				read_err()					\
+				/* fake diff values on a yield  */		\
+				gettimeofday(&start, NULL);			\
+			}							\
+										\
+			gettimeofday(&end, NULL);				\
+										\
+			timersub(&end, &start, &diff);				\
+			if (!blocking && (diff.tv_sec > 0 ||			\
+			    diff.tv_usec > ((1000000L / slots) * 1.10))) {	\
+				fprintf(stderr,					\
+					"\nPIE delta error: %ld.%06ld should be close to 0.%06ld\n", \
+				       diff.tv_sec, diff.tv_usec,		\
+				       (1000000L / (unsigned long) slots));	\
+				fflush(stdout);					\
+				exit(-1);					\
+			}							\
+										\
+			fprintf(stderr, "%d 0x%04lx,", i, data);		\
+			fflush(stderr);						\
+			irqcount++;					
+
+			work()
+		}
+		/* Disable periodic interrupts */
+		ioctl_err(RTC_PIE_OFF, "RTC_PIE_OFF ioctl", 0);
+	}
+
+done:
+	fprintf(stderr, "\n\n\t\t\t *** Test complete ***\n");
+
+	thread_spawn(0);
+
+	close(fd);
+
+	return 0;
+}
-- 
2.5.0

[toc] | [prev] | [next] | [standalone]

#1376484 — [PATCH RFC v0 06/12] Add anonymous struct to sched_rt_entity

Add an anonymous struct to support admittance using a red-black tree,
overrun tracking, state for whether or not to yield or block, debugging
support, execution slot pattern for the scheduler.

Signed-off-by: Bill Huey (hui) <bill.huey@gmail.com>
---
 include/linux/sched.h | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 084ed9f..cff56c6 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1305,6 +1305,21 @@ struct sched_rt_entity {
 	/* rq "owned" by this entity/group: */
 	struct rt_rq		*my_q;
 #endif
+#ifdef CONFIG_RTC_CYCLIC
+	struct {
+		struct rb_node node; /* admittance structure */
+		struct list_head task_list;
+		unsigned long count; /* overrun count per slot */
+		int type, color, yield;
+		u64 slots;
+
+		/* debug */
+		unsigned long last_task_state;
+
+		/* instrumentation  */
+		unsigned int machine_state, last_machine_state;
+	} rt_overrun;
+#endif
 };
 
 struct sched_dl_entity {
-- 
2.5.0

[toc] | [prev] | [next] | [standalone]

#1376487 — [PATCH RFC v0 05/12] Task tracking per file descriptor

Task tracking per file descriptor for thread death clean up.

Signed-off-by: Bill Huey (hui) <bill.huey@gmail.com>
---
 drivers/rtc/class.c | 3 +++
 include/linux/rtc.h | 3 +++
 2 files changed, 6 insertions(+)

diff --git a/drivers/rtc/class.c b/drivers/rtc/class.c
index 74fd974..ad570b9 100644
--- a/drivers/rtc/class.c
+++ b/drivers/rtc/class.c
@@ -201,6 +201,9 @@ struct rtc_device *rtc_device_register(const char *name, struct device *dev,
 	rtc->irq_freq = 1;
 	rtc->max_user_freq = 64;
 	rtc->dev.parent = dev;
+#ifdef CONFIG_RTC_CYCLIC
+	INIT_LIST_HEAD(&rtc->rt_overrun_tasks); //struct list_head
+#endif
 	rtc->dev.class = rtc_class;
 	rtc->dev.groups = rtc_get_dev_attribute_groups();
 	rtc->dev.release = rtc_device_release;
diff --git a/include/linux/rtc.h b/include/linux/rtc.h
index b693ada..1424550 100644
--- a/include/linux/rtc.h
+++ b/include/linux/rtc.h
@@ -114,6 +114,9 @@ struct rtc_timer {
 struct rtc_device {
 	struct device dev;
 	struct module *owner;
+#ifdef CONFIG_RTC_CYCLIC
+	struct list_head rt_overrun_tasks;
+#endif
 
 	int id;
 	char name[RTC_DEVICE_NAME_SIZE];
-- 
2.5.0

[toc] | [prev] | [next] | [standalone]

#1376493

On Mon, 2016-04-11 at 22:29 -0700, Bill Huey (hui) wrote:
> Hi,
> 
> This a crude cyclic scheduler implementation. It uses SCHED_FIFO tasks
> and runs them according to a map pattern specified by a 64 bit mask. Each
> bit corresponds to an entry into an 64 entry array of
> 'struct task_struct'. This works single core CPU 0 only for now.
> 
> Threads are 'admitted' to this map by an extension to the ioctl() via the
> of (rtc) real-time clock interface. The bit pattern then determines when
> the task will run or activate next.
> 
> The /dev/rtc interface is choosen for this purpose because of its
> accessibilty to userspace. For example, the mplayer program already use
> it as a timer source and could possibly benefit from being sync to a
> vertical retrace interrupt during decoding. Could be an OpenGL program
> needing precisely scheduler support for those same handling vertical
> retrace interrupts, low latency audio and timely handling of touch
> events amognst other uses.

Sounds like you want SGI's frame rate scheduler.

	-Mike

[toc] | [prev] | [next] | [standalone]

#1376496

On Mon, 2016-04-11 at 22:59 -0700, Bill Huey (hui) wrote:
> 
> 
> On Mon, Apr 11, 2016 at 10:58 PM, Mike Galbraith <umgwanakikbuti@gmail.com> wrote:
> > On Mon, 2016-04-11 at 22:29 -0700, Bill Huey (hui) wrote:
> > > Hi,
> > >
> > > This a crude cyclic scheduler implementation. It uses SCHED_FIFO tasks
> > > and runs them according to a map pattern specified by a 64 bit mask. Each
> > > bit corresponds to an entry into an 64 entry array of
> > > 'struct task_struct'. This works single core CPU 0 only for now.
> > >
> > > Threads are 'admitted' to this map by an extension to the ioctl() via the
> > > of (rtc) real-time clock interface. The bit pattern then determines when
> > > the task will run or activate next.
> > >
> > > The /dev/rtc interface is choosen for this purpose because of its
> > > accessibilty to userspace. For example, the mplayer program already use
> > > it as a timer source and could possibly benefit from being sync to a
> > > vertical retrace interrupt during decoding. Could be an OpenGL program
> > > needing precisely scheduler support for those same handling vertical
> > > retrace interrupts, low latency audio and timely handling of touch
> > > events amognst other uses.
> > 
> > Sounds like you want SGI's frame rate scheduler.

And an echo free mailer :)

[toc] | [prev] | [next] | [standalone]

#1377664

[+Luca, as he might be interested]

Hi,

On 11/04/16 22:29, Bill Huey (hui) wrote:
> Hi,
> 
> This a crude cyclic scheduler implementation. It uses SCHED_FIFO tasks
> and runs them according to a map pattern specified by a 64 bit mask. Each
> bit corresponds to an entry into an 64 entry array of
> 'struct task_struct'. This works single core CPU 0 only for now.
> 
> Threads are 'admitted' to this map by an extension to the ioctl() via the
> of (rtc) real-time clock interface. The bit pattern then determines when
> the task will run or activate next.
> 
> The /dev/rtc interface is choosen for this purpose because of its
> accessibilty to userspace. For example, the mplayer program already use
> it as a timer source and could possibly benefit from being sync to a
> vertical retrace interrupt during decoding. Could be an OpenGL program
> needing precisely scheduler support for those same handling vertical
> retrace interrupts, low latency audio and timely handling of touch
> events amognst other uses.
> 

Interesting! I read doc patch and only skimmed through the others, but
I seem to already have a general type of question.

Since you seem familiar with SCHED_DEADLINE [1] (you refer to deadline
scheduling in the doc patch and Dario is in CC :-)), what do you think
is wrong with just use that for this type of workloads?

AFAIK, mplayer (like) type of workloads already play well with deadline
scheduling, and SCHED_DEADLINE is mainline and actively maintained and
developed [2].

Best,

- Juri

[1] http://onlinelibrary.wiley.com/doi/10.1002/spe.2335/abstract
[2] http://events.linuxfoundation.org/sites/events/files/slides/SCHED_DEADLINE-20160404.pdf

> There is also a need for some kind of blocking/yielding interface that can
> return an overrun count for when the thread utilizes more time than
> allocated for that frame. The read() function in rtc is overloaded for this
> purpose and reports overrun events. Yield functionality has yet to be fully
> tested.
> 
> I apologize for any informal or misused of terminology as I haven't fully
> reviewed all of the academic literature regarding these kind of schedulers.
> I welcome suggestions and corrects etc
> 
> Special thanks to includes...
> 
> Peter Ziljstra (Intel), Steve Rostedt (Red Hat), Rik van Riel (Red Hat) for
> encouraging me to continue working in the Linux kernel community and being
> generally positive and supportive.
> 
> KY Srinivasan (formerly Novell now Microsoft) for discussion of real-time
> schedulers and pointers to specifics on that topic. It was just a single
> discussion but was basically the inspiration for this kind of work.
> 
> Amir Frenkel (Palm), Kenneth Albanowski (Palm), Bdale Garbee (HP) for the
> amazing place that was Palm, Kenneth for being a co-conspirator with this
> scheduler. This scheduler was inspired by performance work that I did
> at Palm's kernel group along with discussions with the multimedia team
> before HP kill webOS off. Sad and infuriating moment.
> 
> Maybe, in a short while, the community will understand the value of these
> patches for -rt and start solving the general phenomenon of high performance
> multi-media and user interactivity problems more properly with both a
> scheduler like this and -rt shipped as default in the near future.
> 
> [Also, I'd love some kind of sponsorship to continue what I think is
> critical work versus heading back into the valley]
> 
> ---
> 
> Bill Huey (hui) (12):
>   Kconfig change
>   Reroute rtc update irqs to the cyclic scheduler handler
>   Add cyclic support to rtc-dev.c
>   Anonymous struct initialization
>   Task tracking per file descriptor
>   Add anonymous struct to sched_rt_entity
>   kernel/userspace additions for addition ioctl() support for rtc
>   Compilation support
>   Add priority support for the cyclic scheduler
>   Export SCHED_FIFO/RT requeuing functions
>   Cyclic scheduler support
>   Cyclic/rtc documentation
> 
>  Documentation/scheduler/sched-cyclic-rtc.txt | 468 ++++++++++++++++++++
>  drivers/rtc/Kconfig                          |   5 +
>  drivers/rtc/class.c                          |   3 +
>  drivers/rtc/interface.c                      |  23 +
>  drivers/rtc/rtc-dev.c                        | 161 +++++++
>  include/linux/init_task.h                    |  18 +
>  include/linux/rtc.h                          |   3 +
>  include/linux/sched.h                        |  15 +
>  include/uapi/linux/rtc.h                     |   4 +
>  kernel/sched/Makefile                        |   1 +
>  kernel/sched/core.c                          |  13 +
>  kernel/sched/cyclic.c                        | 620 +++++++++++++++++++++++++++
>  kernel/sched/cyclic.h                        |  86 ++++
>  kernel/sched/cyclic_rt.h                     |   7 +
>  kernel/sched/rt.c                            |  41 ++
>  15 files changed, 1468 insertions(+)
>  create mode 100644 Documentation/scheduler/sched-cyclic-rtc.txt
>  create mode 100644 kernel/sched/cyclic.c
>  create mode 100644 kernel/sched/cyclic.h
>  create mode 100644 kernel/sched/cyclic_rt.h
> 
> -- 
> 2.5.0
> 

[toc] | [prev] | [next] | [standalone]

#1377695

[Trying to resend this so that linux-kernel mailer doesn't reject it.
ok just found plain text mode. Will cull the CC list in future
responses]

Hi Juri,

It's not for replacing deadline first of all. I'm not fully aware of the
kind of things being done with deadline and I would like links so that I
have some kind of reference

The original motivation for doing this was for a number of reasons:

1) Current FIFO/RR policies aren't exact enough for a lot of the mixed
modern multimedia scenarios I saw working a real-world load on an Android
like system. Insufficient feedback to interactive UX tasks that include
things like jackd and pulse audio for low latency applications (music,
keyboard controllers, touch events...) across a span of tasks across the
system.

Deadline seems to be more localized to a specific application's need and
seems to be hard to use but I'm inexperienced with it. The problems would
benefit from a simpler solution.

2) The need for a scheduler to be driven by an external interrupt from a
number sources directly.

3) The need for a global view of the system so that power management
decisions can be made sensibly made in multicore systems. It's not a
scheduler alone but ideal would have more influence over power management
decision on battery powered devices, etc...

4) other reasons that should be in the docs but I got sick of writing
exhaustive documentation on the matter...

That's the best I can do for now. I need to post new version with
compilations fixes. There's a lot of problems with code regarding
portability and other issues with the initial revision.

bill

[toc] | [prev] | [next] | [standalone]

#1377719

On 13/04/16 02:37, Bill Huey (hui) wrote:
> [Trying to resend this so that linux-kernel mailer doesn't reject it.
> ok just found plain text mode. Will cull the CC list in future
> responses]
> 
> Hi Juri,
> 
> It's not for replacing deadline first of all. I'm not fully aware of the
> kind of things being done with deadline and I would like links so that I
> have some kind of reference
> 

OK. You can find references in Documentation, in my first reply and
embedded in the ELC slides as well. Please, let me know if you need more
:-).

> The original motivation for doing this was for a number of reasons:
> 
> 1) Current FIFO/RR policies aren't exact enough for a lot of the mixed
> modern multimedia scenarios I saw working a real-world load on an Android
> like system. Insufficient feedback to interactive UX tasks that include
> things like jackd and pulse audio for low latency applications (music,
> keyboard controllers, touch events...) across a span of tasks across the
> system.
> 
> Deadline seems to be more localized to a specific application's need and
> seems to be hard to use but I'm inexperienced with it. The problems would
> benefit from a simpler solution.
> 

I'm not sure what you mean by "localized", but I believe DEADLINE should
be used more widely to service the same kind of applications you are
referring to. It's still a quite new addition to the scheduler, so it is
understandable that we still have some legacy to fight. But we can get
better in the future.

> 2) The need for a scheduler to be driven by an external interrupt from a
> number sources directly.
> 

If you use DEADLINE to service the activity an interrupt source might
trigger, I think you can already do this.

> 3) The need for a global view of the system so that power management
> decisions can be made sensibly made in multicore systems. It's not a
> scheduler alone but ideal would have more influence over power management
> decision on battery powered devices, etc...
> 

That's true. But it is also already something we currently are working on.
I don't know if you are following the schedfreq/schedutil threads [1], for
example, but there we are discussing how to integrate scheduler and
cpufreq more closely. And you might also be interested in the EAS effort
[2].

> 4) other reasons that should be in the docs but I got sick of writing
> exhaustive documentation on the matter...
> 

:-)

> That's the best I can do for now. I need to post new version with
> compilations fixes. There's a lot of problems with code regarding
> portability and other issues with the initial revision.
> 

OK. Feel free to ask if you also decide to experiment with DEADLINE and
find any problem with it.

Best,

- Juri

[1] https://lkml.org/lkml/2016/3/17/420
    https://lkml.org/lkml/2016/2/22/1037
[2] https://lkml.org/lkml/2015/7/7/754

[toc] | [prev] | [next] | [standalone]

#1377744

Hi,

On Wed, Apr 13, 2016 at 3:08 AM, Juri Lelli <juri.lelli@arm.com> wrote:
> I'm not sure what you mean by "localized", but I believe DEADLINE should
> be used more widely to service the same kind of applications you are
> referring to. It's still a quite new addition to the scheduler, so it is
> understandable that we still have some legacy to fight. But we can get
> better in the future.

Yeah, I've known about it for a while but it's just so hard for me to imagine
using that for the kinds of cases that I'm thinking about for mixed tasks.
I just don't have an example in my head how that would work since I don't
have a view of how something like EDF would solve some of the basic
cases. That's mostly my ignorance.

The original inspiration for this was problems with how FIFO tasks would
run for long periods of time will stall with touch event handlers. The solution
in multi-media circles seemed to be that (1) using larger buffers to avoid
dropouts were the solution only to cause starvation and other problems
with other important threads.

There has to be some kind of global view of how a system should run.
It's hard for me (self ignorance) to see how something like deadline would
run for continuously running tasks like that under those scenarios and
have that define some kind of global running policy in the system.

That's why I created this for a brain dead view of how to hack this stuff,
with some kind of crude execution pattern, to somehow get some level of
acceptable interactivity yet meet basic hard requirements with audio etc.

Might be a scenario where one would use sched_switch data to help with
deciding that. We ran into a lot of problems with the Qualcomm MSM
architecture and their power management code. Some of the hacks were
pretty brutal and wasted processor time polling the second core aggressively.

I wanted to solve all of these problems more completely and outside of the
current work being done for better or worse.

>> 2) The need for a scheduler to be driven by an external interrupt from a
>> number sources directly.
>
> If you use DEADLINE to service the activity an interrupt source might
> trigger, I think you can already do this.

I'll have to think about this. Would might having a simple example here.

>> 3) The need for a global view of the system so that power management
>> decisions can be made sensibly made in multicore systems. It's not a
>> scheduler alone but ideal would have more influence over power management
>> decision on battery powered devices, etc...
>
> That's true. But it is also already something we currently are working on.
> I don't know if you are following the schedfreq/schedutil threads [1], for
> example, but there we are discussing how to integrate scheduler and
> cpufreq more closely. And you might also be interested in the EAS effort
> [2].

Not yet but I'll look for them.

> OK. Feel free to ask if you also decide to experiment with DEADLINE and
> find any problem with it.

> [1] https://lkml.org/lkml/2016/3/17/420
>     https://lkml.org/lkml/2016/2/22/1037
> [2] https://lkml.org/lkml/2015/7/7/754

Thanks, reading them now but they're quite complicated and the threads
are quite long. It'll take time to digest it all

Thanks

bill

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web