Интервью: Интересные вопросы

[idle0]

Я получил вот такой вопрос, на который честно говоря сам не знаю как ответить

"Напишите программу которая позволяет замерить время context switch в Linux-е"

Есть какие-то идеи?

[Andriy777]

Если взять цикл от 0 до Х. Так, чтобы выполнялся несколько секунд. Не трогать память. Минимальные инструкции инкремента и сравнения с Х. Предположим он бежит время T. Если другие процессы программу не прерывают, то она будет бежать на одном ядре. Дать программе приоритет выше обычного и тогда она будет прерываться меньше.

Предположим, что на машине N ядер. Тогда программа с N потоками (threads) и этим простейшим алгоритмом будет бежать тоже время T, т.к. каждое ядро будет делать ту же работу. Высокий приоритет, чтобы другие процессы не мешали.

Если в программе запустить N*2 параллельных потока, то при идеальном context switch of 0, время будет T * 2. Но будет время побольше. От результата времени R отнять T * 2 => время которое ушло на все переключения. Суммарное время уже хорошо для оценки многих вещей и цена одного, может, и не нужна.

Чтобы оценить цену одного, можно почитать доку про ихний Kernel и узнать как часто ОС делает переключения. На Windows, если я помню правильно, дается 20мс выполниться потоку без прерывания другим потоком этого же приоритета.

Про Kernel Linux-a я не читал.

[Херовимчик]

Вот тут неплохо про разные нюансы:
https://stackoverflow.com/questions/23 ... n-linux-os

[alex_127]

Я получил вот такой вопрос, на который честно говоря сам не знаю как ответить

"Напишите программу которая позволяет замерить время context switch в Linux-е"

Есть какие-то идеи?

написать прогу что в цикле на 2 треадах зовет RDTSC (убедится в инварианте), аффинитизировать на один logical core, дальше статистика по длине прыжка.
нет RDTSC - больше статистики или циклы считаль.

[Mmodel]

alex_127, а у вас там в Вашингтоне не записывают?

[idle0]

Я получил вот такой вопрос, на который честно говоря сам не знаю как ответить

"Напишите программу которая позволяет замерить время context switch в Linux-е"

Есть какие-то идеи?

написать прогу что в цикле на 2 треадах зовет RDTSC (убедится в инварианте), аффинитизировать на один logical core, дальше статистика по длине прыжка.
нет RDTSC - больше статистики или циклы считаль.

Вот что пишет Википедия

The Time Stamp Counter was once an excellent high-resolution, low-overhead way for a program to get CPU timing information. With the advent of multi-core/hyper-threaded CPUs, systems with multiple CPUs, and hibernating operating systems, the TSC cannot be relied upon to provide accurate results — unless great care is taken to correct the possible flaws: rate of tick and whether all cores (processors) have identical values in their time-keeping registers. There is no promise that the timestamp counters of multiple CPUs on a single motherboard will be synchronized. Therefore, a program can get reliable results only by limiting itself to run on one specific CPU. Even then, the CPU speed may change because of power-saving measures taken by the OS or BIOS, or the system may be hibernated and later resumed, resetting the TSC. In those latter cases, to stay relevant, the program must re-calibrate the counter periodically.

Relying on the TSC also reduces portability, as other processors may not have a similar feature. Recent Intel processors include a constant rate TSC (identified by the kern.timecounter.invariant_tsc sysctl on FreeBSD or by the "constant_tsc" flag in Linux's /proc/cpuinfo). With these processors, the TSC ticks at the processor's nominal frequency, regardless of the actual CPU clock frequency due to turbo or power saving states. Hence TSC ticks are counting the passage of time, not the number of CPU clock cycles elapsed.

On Windows platforms, Microsoft strongly discourages using the TSC for high-resolution timing for exactly these reasons, providing instead the Windows APIs QueryPerformanceCounter and QueryPerformanceFrequency.[2] On POSIX systems, a program can get similar function by reading the value of CLOCK_MONOTONIC_RAW clock using the clock_gettime function.[3]

Starting with the Pentium Pro, Intel processors have practiced out-of-order execution, where instructions are not necessarily performed in the order they appear in the program. This can cause the processor to execute RDTSC earlier than a simple program expects, producing a misleading cycle count.[4] The programmer can solve this problem by inserting a serializing instruction, such as CPUID, to force every preceding instruction to complete before allowing the program to continue. The RDTSCP instruction is a variant of RDTSC that features partial serialization of the instruction stream, but should not be considered as serializing.

[rx300]

Я получил вот такой вопрос, на который честно говоря сам не знаю как ответить

"Напишите программу которая позволяет замерить время context switch в Linux-е"

Есть какие-то идеи?

Это, скорее всего, про базовые знания, а не про архитектуру процессора, да?
Тогда, все просто:

gettimeofday(&time_before, 0);
if (fork() != 0) {
gettimeofday(&time_after, 0);
switch_time = time_after.tv_usec - time_before.tv_usec;
}

[idle0]

Я получил вот такой вопрос, на который честно говоря сам не знаю как ответить

"Напишите программу которая позволяет замерить время context switch в Linux-е"

Есть какие-то идеи?

Это, скорее всего, про базовые знания, а не про архитектуру процессора, да?
Тогда, все просто:

gettimeofday(&time_before, 0);
if (fork() != 0) {
gettimeofday(&time_after, 0);
switch_time = time_after.tv_usec - time_before.tv_usec;
}

Это не про архитектуру процессора но и не про замер времени выполнения fork-a

context switch - это когда scheduler заменяет один из процессов выполняющийся на CPU на другой.


A context switch (also sometimes referred to as a process switch or a task switch) is the switching of the CPU (central processing unit) from one process or thread to another.

A process (also sometimes referred to as a task) is an executing (i.e., running) instance of a program. In Linux, threads are lightweight processes that can run in parallel and share an address space (i.e., a range of memory locations) and other resources with their parent processes (i.e., the processes that created them).

A context is the contents of a CPU's registers and program counter at any point in time. A register is a small amount of very fast memory inside of a CPU (as opposed to the slower RAM main memory outside of the CPU) that is used to speed the execution of computer programs by providing quick access to commonly used values, generally those in the midst of a calculation. A program counter is a specialized register that indicates the position of the CPU in its instruction sequence and which holds either the address of the instruction being executed or the address of the next instruction to be executed, depending on the specific system.

Context switching can be described in slightly more detail as the kernel (i.e., the core of the operating system) performing the following activities with regard to processes (including threads) on the CPU: (1) suspending the progression of one process and storing the CPU's state (i.e., the context) for that process somewhere in memory, (2) retrieving the context of the next process from memory and restoring it in the CPU's registers and (3) returning to the location indicated by the program counter (i.e., returning to the line of code at which the process was interrupted) in order to resume the process.

A context switch is sometimes described as the kernel suspending execution of one process on the CPU and resuming execution of some other process that had previously been suspended. Although this wording can help clarify the concept, it can be confusing in itself because a process is, by definition, an executing instance of a program. Thus the wording suspending progression of a process might be preferable.

[idle0]

Вот нужно замерять - сколько времени на это уходит

[rx300]

Это не про архитектуру процессора но и не про замер времени выполнения fork-a

По тому как описано, это именно замер скорости fork'а. Есть низкоуровневые способы, но вряд ли они имелись в виду постановщиками задачи.

[idle0]

Это не про архитектуру процессора но и не про замер времени выполнения fork-a

По тому как описано, это именно замер скорости fork'а. Есть низкоуровневые способы, но вряд ли они имелись в виду постановщиками задачи.

Вот в авторском варианте

"Write a C program which measures the the speed of a context switch on a Linux system."


Во время fork-a конечно происходит context switch, но тут мне кажется другое

[valchkou]

Я получил вот такой вопрос, на который честно говоря сам не знаю как ответить

"Напишите программу которая позволяет замерить время context switch в Linux-е"

на какую позицию дают такие вопросы?

[Херовимчик]

Это не про архитектуру процессора но и не про замер времени выполнения fork-a

По тому как описано, это именно замер скорости fork'а. Есть низкоуровневые способы, но вряд ли они имелись в виду постановщиками задачи.

Вот в авторском варианте

"Write a C program which measures the the speed of a context switch on a Linux system."


Во время fork-a конечно происходит context switch, но тут мне кажется другое

Это больше похоже на open-ended вопрос, где от вас ожидают рассуждения о причинах context switch, об очередях и приоритетах. Скорее о дизайне операционных систем, а не где нужно бросаться писать код за условные 30 минут

(Это у вас домашка такая? Или уже прошло интервью?)

[alex_127]

Recent Intel processors include a constant rate TSC (identified by the kern.timecounter.invariant_tsc sysctl on FreeBSD or by the "constant_tsc"

друг, других не осталось. все старьё остальное как минимум 10 летней давности. я просто в этой битве принимал некоторое участие...

[idle0]

Я получил вот такой вопрос, на который честно говоря сам не знаю как ответить

"Напишите программу которая позволяет замерить время context switch в Linux-е"

на какую позицию дают такие вопросы?

UNIX System Administrator

[idle0]

Recent Intel processors include a constant rate TSC (identified by the kern.timecounter.invariant_tsc sysctl on FreeBSD or by the "constant_tsc"

друг, других не осталось. все старьё остальное как минимум 10 летней давности. я просто в этой битве принимал некоторое участие...

Что за битва?

[valchkou]

Я получил вот такой вопрос, на который честно говоря сам не знаю как ответить

"Напишите программу которая позволяет замерить время context switch в Linux-е"

на какую позицию дают такие вопросы?

UNIX System Administrator

UNIX System Administrator который пишет программы? Интересно где такие мастодонты требуются.
я думал уже все кто умеет кодить превратились в девопсов а кто не умеет в клауд архитекторов.

[uncle_Pasha]

Если взять цикл от 0 до Х. Так, чтобы выполнялся несколько секунд. Не трогать память. Минимальные инструкции инкремента и сравнения с Х. Предположим он бежит время T. Если другие процессы программу не прерывают, то она будет бежать на одном ядре. Дать программе приоритет выше обычного и тогда она будет прерываться меньше.

Скажите сразу, если прилетит interrupt - это будет context switch или нет? И повлияет ли это на время?

[Komissar]

Скажите сразу, если прилетит interrupt

это будет нашествие с помойки?

[idle0]

А есть ли какое-то прерывание которое работает как NOP?

[Andriy777]

Если взять цикл от 0 до Х. Так, чтобы выполнялся несколько секунд. Не трогать память. Минимальные инструкции инкремента и сравнения с Х. Предположим он бежит время T. Если другие процессы программу не прерывают, то она будет бежать на одном ядре. Дать программе приоритет выше обычного и тогда она будет прерываться меньше.

Скажите сразу, если прилетит interrupt - это будет context switch или нет? И повлияет ли это на время?

Память мне говорит, что даже сам context switch сделан на interrupt-е определенного типа. Т.е. если во время моего теста не двигать мышью, не лезть в интернет и пр., применить максимум усилий к уменьшению этих прерываний от периферии, то есть надежда, что останутся в большинстве только те прерывания, которые делают эти context переходы.

Предпшоложим, что уменьшили другие прерывания. Метод посчитает цены всего, что входит в context switch. Т.е. сам interrupt, плюс вся байда для согранения регистров и всего, что нужно для вышибания одного потока и восстановление другого потока на определенное ядро процессора.

Естесственно будет погрешность. Погрешность можно определить и вычесть. Например, при первом запуске с N threads, при 2N threads, при 4N threads можно ожидать, что остальные прерывания от периферии идут с такой же частотой как они были при N-запуске. И прикинуть формулы избавления.

Еще сами прерывания могут быть очень быстрыми и они что-нибудь добавят в queue. А само действие должно будет делаться на потоке с нормальным приоритетом. А мы, ведь, свой приоритет повысим. Может, цена ненужных прерываний и уменьшится.

Я про эту проблему подумал тогда 10 сек и сейчас еще 10 сек. Дольше печатать. Сейчас, извините, бегу в качалку. Мозги настроены на другое.

В интернет за помощью не лез и никаких Stack Overflow не читал. Может, как на Windows, так и на Linux есть средства поточнее. Скорее всего, есть какие-нибудь статистики в самом ядре и их можно получить.

[valchkou]

Естесственно будет погрешность. Погрешность можно определить и вычесть. Например, при первом запуске с N threads, при 2N threads, при 4N threads можно ожидать, что остальные прерывания от периферии идут с такой же частотой как они были при N-запуске. И прикинуть формулы избавления.

это все очень интересно но непонятно нафига это нужно UNIX System Administrator?
я так понимаю ожидалось решение типа

Code: Select all

find /var/www/my_website -type f -exec chmod 0644 {} \;

[uncle_Pasha]

если во время моего теста не двигать мышью, не лезть в интернет и пр., применить максимум усилий к уменьшению этих прерываний от периферии

Часы тоже отключить?

[kostik78]

Вопрос дурной ибо для ответа нужно знать ещё какой scheduler используется. В кернеле их несколько

[idle0]

Вопрос дурной ибо для ответа нужно знать ещё какой scheduler используется. В кернеле их несколько

Ну время то замерить можно при любом, нет?