Вот такая задачка по программированию, есть ли решение ?

← →
esu © (2005-02-09 14:32) [0]

Есть 2 процессора, одновременно работают, могут писать чего-то в общую память (скажем программы использовать общие переменные). Задача написать программы для процессоров которые бы по символу вывели в общую переменную "Hello world!" и буквы гарантированно не перепутались.
Для примера скажем первая программа просто выводит H, а вторая e и получается у нас нет гарантии что в общей переменной появится "He", а не "eH"

Без использования прерываний.

← →
Vaitek © (2005-02-09 14:35) [1]

А на фига?

← →
kaZaNoVa © (2005-02-09 14:36) [2]

критические секции попробуй

← →
BiN © (2005-02-09 14:37) [3]

читать про кодовые потоки

← →
КаПиБаРа © (2005-02-09 14:38) [4]

Думаю что у процессоров есть средства разграничения доступа к памяти. Изучай комманды процессоров и аппаратную часть.

← →
esu © (2005-02-09 14:39) [5]

Это теоретически, а не практически. Есть только то что есть.

← →
esu © (2005-02-09 14:41) [6]

> Vaitek © (09.02.05 14:35) [1]
> А на фига?

Узнать возможно ли это

← →
esu © (2005-02-09 14:42) [7]

> BiN © (09.02.05 14:37) [3]
> читать про кодовые потоки

Так возможно ? Пример можешь написать ? Вроде ж простое условие

← →
BiN © (2005-02-09 14:45) [8]

esu © (09.02.05 14:42) [7]

Так возможно ? Пример можешь написать ? Вроде ж простое условие

Если честно, то лень :) А в чем конкретные затруднения?

← →
esu © (2005-02-09 14:52) [9]

> Если честно, то лень :) А в чем конкретные затруднения?

Ну у нас нет ни таймера ничего. Есть только общая память и усе. Затреднение в том что скажем заведя флажок который будет говорить о том чья очередь выводит помоему не спасает
1ая:
if f then
f := false
чем выводим
f := true
2ая:
if f then
f := false
чем выводим
f := true
фишка в том что и на первой и на второй f может провериться одновременно и на обоих процессорах мы перескочим на вывод чего не должно произойти.

← →
BiN © (2005-02-09 15:02) [10]

Есть 2 процессора, одновременно работают, могут писать чего-то в общую память

Откуда это известно? Кстати, какая ОС подразумевается?

← →
esu © (2005-02-09 15:14) [11]

> Откуда это известно? Кстати, какая ОС подразумевается?

Я же писал что известно это из условия. Никакой OS можно сказать нет и соответственно нет CriticalSection etc. Это вообще гипотетически все. А цель узнать можно ли это сделать при таких условия впринципе или нельзя никак.

← →
BiN © (2005-02-09 15:22) [12]

esu © (09.02.05 15:14) [11]

Никакой OS можно сказать нет и соответственно нет CriticalSection etc. Это вообще гипотетически все. А цель узнать можно ли это сделать при таких условия впринципе или нельзя никак.

Windows же как-то позволяет это делать - с помощью всё тех же критических секций, например.

← →
Игорь Шевченко © (2005-02-09 15:27) [13]

> А цель узнать можно ли это сделать при таких условия впринципе
> или нельзя никак.

Можно, если у процессоров есть средства блокировки доступа к памяти. Одной командой. Если у этих процессоров такого средства нет, то нельзя.

← →
Digitman © (2005-02-09 15:52) [14]

> esu © (09.02.05 14:32)

галиматья полная.

особливо в части термина "буквы".

← →
msguns © (2005-02-09 16:07) [15]

С т.зр. ОС (а любые процы работают не сами по себе, а обрабатывают команды, "подсунутые" системой (это не совсем так, но по смыслу данного контекста можно применить эту терминологию)
любая работающая программа представляет собою некий процесс (задачу), который упрощенно можно представить как ленту, несущую последовательность команд процессору, и изпользуемые (предоставляемые) ею ресурсы.
Во избежание влияния друг на друга одновременно (с т.зр. внешнего наблюдателя, но никак не процессора или ОС) выполняющихся задач в любой боле-менее солидной мультизадачной ОС есть средства защиты, как свои, программные, так и управления аппаратными, в частности ключами защиты памяти.
При этом для одной задачи фиолетово, сколько процессоров будет обрабатывать ее "ленту": один или поочередно (параллельно) два или четыре.

Отсюда следует то, что две запущенные программы (для ОС-задачи) в принципе не могут использовать одну и ту же память. Если, конечно, они не запущены с нулевым ключом защиты. При попытке программы А "влезть" в участок памяти программы "Б" (по барабону каким процем, первым или четвертым) просто возникнет прерывание по защите. Я уже молчу о том, что программе "А" практически невозможно определить нужный "целевой" адрес памяти из-за особенностей системы управления памятью.

Если все же попытаться реализовать такую задачу, то ИМХО, через обмен данными через внешние каналы (не ОП), например, дисковые файлы или порты I/O, а "порядок" действий разруливать таймером. Без прерываний ну никак не получится хотя бы потому, что любое обращение к любому порту будет сопровождено прерыванием, и не одним ! Плюс в процессе выполнения даже самого маленького участка кода в одной проге (задаче) может возникать n-е кол-во прерываний, о которых данная задача даже не подозревает, и процессор (процессоры) будут многократно переключены на выполнение совершенно неизвестных проге действий.

Интересно, а откуда возникла такая любопытная задачка ?

← →
msguns © (2005-02-09 16:12) [16]

>Игорь Шевченко © (09.02.05 15:27) [13]
>Можно, если у процессоров есть средства блокировки доступа к памяти. Одной командой. Если у этих процессоров такого средства нет, то нельзя.

Игорь, поясни, пожалуйста, какие средства блокировки доступа к памяти есть у процессоров и почему у некоторых из них (хоть пара примеров) их нет.
Или ты имеешь в виду работу процессоров в разных режимах адресации ?

← →
wal © (2005-02-09 16:22) [17]

Для первого:
1: if s="" then s:="H"; if s="He" then s:=s+"l"; if s="Hell" then s:=s+"o"; if s="Hello " then s:=s+"w"; if s="Hello wo" then s:=s+"r"; if s="Hello worl" then begin s:=s+"d"; exit end; goto 1: Для второго аналогично, только буквы другие. :) С уважением.

← →
MBo © (2005-02-09 16:24) [18]

>msguns © (09.02.05 16:12) [16]
префикс LOCK
Interlocked*** функции Windows

← →
Игорь Шевченко © (2005-02-09 16:25) [19]

msguns © (09.02.05 16:12) [16]

> Игорь, поясни, пожалуйста, какие средства блокировки доступа
> к памяти есть у процессоров

Например, префикс lock у команды.

> и почему у некоторых из них (хоть пара примеров) их нет.

У Z80, насколько мне помнится, нет :)

← →
esu © (2005-02-09 16:40) [20]

> wal © (09.02.05 16:22) [17]

О, значит можно таки без блокировок память и прерываний :)

← →
msguns © (2005-02-09 17:21) [21]

>MBo © (09.02.05 16:24) [18]

А причем здесь винда ? Базар о процессорах.

>Игорь Шевченко © (09.02.05 16:25) [19]

Т.е. в наборе команд проца есть такая, которая блокирует доступ к ОП. После чего он не обрабатывет команды, адресующиеся к памяти. А откуда он тогда "вытаскивает" очередную, как не из памяти ? И что подразумевается под "памятью": стек, кэши или непосредственно банки ОЗУ.
Поясни, пожалуйста, я асмил на интел-системах давно и немного. Мне больше знакома система команд IBM.

← →
Sha © (2005-02-09 17:28) [22]

unit TwoButtonsF; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls; type TForm1 = class(TForm) bStart0: TButton; bStart1: TButton; Edit1: TEdit; bClear: TButton; procedure bStartClick(Sender: TObject); procedure bClearClick(Sender: TObject); private public end; var Form1: TForm1; implementation {$R *.dfm} type TMyThread = class(TThread) private FId: integer; protected procedure Execute; override; published constructor MyCreate(Id: integer); end; var Hello: string= "Hello world!"; ch: char; //общая переменная для вывода no: integer= 0; //количество выведенных символов procedure TForm1.bClearClick(Sender: TObject); begin; Edit1.Text:=""; no:=0; end; procedure TForm1.bStartClick(Sender: TObject); begin; if Sender is TButton then begin; TButton(Sender).Enabled:=false; TMyThread.MyCreate(ord(Sender=bStart1)); TButton(Sender).Enabled:=true; end; end; constructor TMyThread.MyCreate(Id: integer); begin; inherited Create(false); FId:=Id; FreeOnTerminate:=true; end; procedure TMyThread.Execute; var len: byte; begin; len:=length(Hello); while no<len do begin; while (no and 1)<>FId do begin; sleep(1); if Terminated then exit; end; if no<len then begin; ch:=Hello[no+1]; PostMessage(Form1.Edit1.Handle,wm_char,ord(ch),0); inc(no); end; end; end; end. object Form1: TForm1 Left = 313 Top = 249 Width = 221 Height = 124 Caption = "Form1" Color = clBtnFace Font.Charset = DEFAULT_CHARSET Font.Color = clWindowText Font.Height = -11 Font.Name = "MS Sans Serif" Font.Style = [] OldCreateOrder = False PixelsPerInch = 96 TextHeight = 13 object bStart0: TButton Left = 24 Top = 48 Width = 75 Height = 25 Caption = "bStart0" TabOrder = 0 OnClick = bStartClick end object bStart1: TButton Left = 112 Top = 48 Width = 75 Height = 25 Caption = "bStart1" TabOrder = 1 OnClick = bStartClick end object Edit1: TEdit Left = 24 Top = 16 Width = 81 Height = 21 TabOrder = 2 Text = "Edit1" end object bClear: TButton Left = 112 Top = 16 Width = 75 Height = 25 Caption = "bClear" TabOrder = 3 OnClick = bClearClick end end

← →
begin...end © (2005-02-09 17:32) [23]

> msguns © (09.02.05 17:21) [21]

Перед машинной командой может быть до четырёх однобайтовых префиксов. Один из них (LOCK - префикс блокировки шины), насколько я помню, используется для монополизации доступа данного процессора к системной шине (в многопроцессорной системе).

Могу ошибаться, конечно.

← →
Игорь Шевченко © (2005-02-09 17:39) [24]

msguns © (09.02.05 17:21) [21]

> Т.е. в наборе команд проца есть такая, которая блокирует
> доступ к ОП.

Блокировка подразумевает запрет доступа остальным процессорам к памяти.

> Поясни, пожалуйста, я асмил на интел-системах давно и немного.
> Мне больше знакома система команд IBM.

Тогда тебе должно быть знакомо понятие "двухмашинный комплекс с общей памятью". Типа ВКМ-45, если память не изменяет, за 20 лет и я могу многое забыть.

← →
MBo © (2005-02-09 17:47) [25]

>msguns © (09.02.05 17:21) [21]
>А причем здесь винда ? Базар о процессорах
Просто для пояснения. InterLocked как раз используют LOCK, обеспечиваемый X86 процессорами.

← →
Sha © (2005-02-09 17:48) [26]

> Sha © (09.02.05 17:28) [22]

Только Enabled/Disabled надо убрать:

procedure TForm1.bStartClick(Sender: TObject); begin; if Sender is TButton then TMyThread.MyCreate(ord(Sender=bStart1)); end;

← →
msguns © (2005-02-09 17:57) [27]

>Игорь Шевченко © (09.02.05 17:39) [24]
>MBo © (09.02.05 17:47) [25]

Спасибо за пояснения. С многопроцессорными системами на уровня системного программирования не работал ;( Инструкции кое-какие, помнится, были в 360/370 (позже в 390), но я их не брал во внимание. Кроме того, все эти команды (имеется в виду управляющие команды) выполнялись только в режиме супервизора, в котором, если я и работал, то оооочень осторожно, дабы не подвесить весь центр.

ЗЫ. Да-с. С этим оопом вообще позабудешь "железо" нафик ;((

← →
Soft © (2005-02-09 19:01) [28]

Классическая задачка для троечинков третьего курса или отличников первого.

Заводишь флаговую переменную в общей памяти(физической), которая отвечаает за разграничение доступа к определенному участку памяти. 1 -занято 0 свободно.

При установку флага в 1 используешь ассемблерные команды:
MOV AL,1;
XCHG переменная,AL;
Далее проверяешь AL если 1 то проверяешь еще раз(можно с таймоутом), пока в AL не получишь 0. Команда XCHG применяется для того чтобы не было одновременного захвата ресурса, или ресурс уже захвачен или он захватывается командой XCHG - при обмене значением из памяти и AL лочится шина.

Игорь Шевченко и где ваше LMD :)

← →
Soft © (2005-02-09 19:06) [29]

>>Sha © (09.02.05 20:01) [30]
>>Лочить необязательно.

Вы не системщик, это сразу видно, так как вы стараетсь оперировать математикой, а не реальными командами процессора.

PS
Иногда после переписывания кода, написанного мастерами, производительность(в некоторых участках) возрастает на 1000%, хотя читабельность... Все зависит от пожелаинй заказчика.

>Soft © (09.02.05 19:01) [28]

Первый поток записал и сбросил флаг. После этого начинает заново пытаться захватить. Пусть даже и с задержкой. Но за время задержки второй поток по каким-то причинам так и не получил управление и не захватил ресурс. Что увидит первый поток? Что ресурс свободен и можно писать дальше. Т.е. блокировка есть, а вот четкой очередности нет.
Для решения первый поток должен ждать 1 и сбрасывать флаг в 0. Второй должен ждать 0 и устанавливать 1.

> Soft © (09.02.05 20:40) [31]
> Вы не системщик, это сразу видно, так как вы стараетсь
> оперировать математикой, а не реальными командами процессора.

Более осторожно и математически более точно было бы сказать,
что один из нас точно не системщик :)

> Soft © (09.02.05 20:40) [31]
> Иногда после переписывания кода, написанного мастерами,
> производительность(в некоторых участках) возрастает на 1000%,
> хотя читабельность... Все зависит от пожелаинй заказчика.

Ко мне это имеет какое-то отношение?
Если да, то хотелось бы увидеть примерчик.

По сабжу:
Если доступ процессора к общему полю памяти
организован через арбитра одиночными циклами
"чтение-модификация-запись", а сам орбитраж
между процессорами за доступ к систнмной шине
памяти основан на состязательном принципе:
"первый по времени - получает первым, а при
одновременном обращении получает тот кто
ближе к арбитру (как один из вариантов), то
задача решения не имеет. Кроме случая, когда
P1 пишет четные (по положению) символы, а Р2
соответственно нечетные.

1 процессор
if f1 then
begin
вывод
f1 = not f1;
end;

2 процессор
if not f1 then
begin
вывод
f1 = not f1;
end;

Если не брать во внимание конкретную реализацию, то для любого процессора задача решается с использованием N флагов (Для случая 2-х процессов - 2 флага) Не 1-го!. С одним флагом не выйдет. Называется Алгоритм Деккера, и не предполагает о железе совсем ничего. Вот, даже нащёл ссылку:
http://www.hardline.ru/selfteachers/Info/Programming/Teoria_OS/Glava%207/Index3.htm
Если есть аппраратный или программный механизм семафоров (т.е. если аппаратно - неделимая операция изменения-чтения) - решение с семафорами, конечно, более эффективно.

>С одним флагом тоже можно
Если флагом называется обычная ячейка памяти (не семафор) - нельзя.
Пусть флаг = 0 означает, что доступ в секцию разрешён.
Пусть 1-й процесс проверяет состояние фага, и видит 0. Он решает записать туда 1. Но не успевает - перед этим второй процесс тоже проверяет флаг, и тоже получает 0.
Кстати, во многих ОС "флагом" называют именно семафор. Пример - RSX. Там то, что называется "флаг" обладает всеми свойствами семафора ;).

>КаПиБаРа
Ну да, Ваш пример в данном конкретном случае (вывод строго по очереди) конечно, заработает ;).

MOA © (10.02.05 9:49) [39]
Пусть 1-й процесс проверяет состояние фага, и видит 0. Он решает записать туда 1. Но не успевает - перед этим второй процесс тоже проверяет флаг, и тоже получает 0.

Вот она, кардинальная ошибка!
Пример исключающий эту проблему я привел в КаПиБаРа © (10.02.05 6:13) [36]

Вот такая задачка по программированию, есть ли решение ? Найти похожие ветки