Tag: Allocation

memory allocation & illegal access

In a practice question, we had to give examples of three different types of wrong memory access in C or C++:

Which I identified as the following:

• Reading/Writing without allocation

• Read/Writing after de-allocation

• Reading/Writing without previous write

Since I haven’t done much work in these languages before, I couldn’t come up with appropriate examples. For example, I understand that we deallocate in C like this:

int main(void)  {      int *ptr = (int*)malloc(10);       return 0;  }

but how could I modify it to show an example of the second type?

Similarly, for the first type, I think this should suffice, but does it?

void foo() {    int i = 5;    MyClass obj;  ... }

Does XP allocation double as a catch-up mechanic?

The D&D 3.5e DMG has the following for giving out exp:

To determine the XP award for an encounter, follow these steps.

  1. Determine each character’s level. Don’t forget to account for ECL (see Monsters as Races, page 172) if any of the characters are of a powerful race.

  2. For each monster defeated, determine that single monster’s Challenge Rating.

  3. Use Table 2–6: Experience Point Awards (Single Monster) to crossreference one character’s level with the Challenge Rating for each defeated monster to find the base XP award.

  4. Divide the base XP award by the number of characters in the party. This is the amount of XP that one character receives for helping defeat that monster.

  5. Add up all the XP awards for all the monsters the character helped defeat.

  6. Repeat the process for each character

Given rule 6, you do this for each character. This means it uses each characters ECL. If your group has level difference among party members, would the lower levels gain more exp than the higher levels? Or am I looking at this wrong?

fair chore allocation with qualification


Background

There are $ n$ indivisible heterogenous bads (chores).
There are $ m$ agents.
The subjective utility functions of the agents are additive and identical. e.g $ \forall X,i,j\ V_i(X) = V_j(X)$ .
The agents have different entitlements over the chores.
Finally, there is an additional constraint: there are chores that some agents cannot be assigned to perform (i.e the qualification constraint)

The task

I would like to be able to:

  1. define some fairness criterion that matches the problem
  2. find an algorithm that provides an allocation that implements it.

I believe that due to the qualification constraint some standard fairness criteria, like $ EF1$ , may not exist. This is why I am also asking for a fairness criterion.

Constraint satisfaction in a resource allocation problem optimized using evolutionary algorithms

I am working on an allocation problem where a resource $ R$ needs to be allocated to $ n$ users each with demand $ d_i$ . The problem has two objectives: objective 1 – maximize user utility given by $ f_1(e_i)=log(1+e_i/d_i)$ and objective 2 – minimize $ f_2(e_i) = {e_i}^2/c_i$ where $ e_i$ is the allocation to the $ ith$ user $ d_i$ and $ c_i$ are constants. The problem has two constraints i.e., $ e_i \le d_i$ (allocation is ≤ demand) and $ \sum_i^{n} e_i = R$ (sum of all allocations equals total available resource). I am using an evolutionary algorithm for this problem. But, after the evolution is complete, the algorithm leaves unallocated resource while there is still unmet user demand. I am curious if it is an expected outcome or it is due to some algorithmic or implementation flaw. I would appreciate any guidance

How to manage disk space allocation for materialized views?

Summary: I have materialized views in oracle 11g that seem to hog disk space, unlike normal tables that mark rows as deleted and stats eventually show them as free space (allocated to the table, allowing reuse). Tablespace usage only grows for materialized views unlike stats for origin tables. Tested in Oracle 12c with same results. How to ensure MV reuse space from deleted rows?

What have I done? I have these partitioned materialized views set up in a separate schema, separate tablespace from the origin tables (i know they could have partitions created dynamically, call it technical debt).

CREATE MATERIALIZED VIEW replication_schema.origin_table PARTITION BY RANGE(tbl_timestamp)  (     PARTITION tbl_before_2016 VALUES LESS THAN (TO_TIMESTAMP('2016-01-01 00:00:00','YYYY-MM-DD HH24:MI:SS')),     PARTITION tbl_2016_01 VALUES LESS THAN (TO_TIMESTAMP('2016-02-01 00:00:00','YYYY-MM-DD HH24:MI:SS')),     PARTITION tbl_2016_02 VALUES LESS THAN (TO_TIMESTAMP('2016-03-01 00:00:00','YYYY-MM-DD HH24:MI:SS')), ...  PARTITION tbl_after_2025 VALUES LESS THAN (MAXVALUE) ) REFRESH FORCE ON DEMAND START WITH SYSDATE NEXT sysdate+1/1440 AS SELECT * FROM origin_schema.table;

And they have some indexes on them as well, some global and some are local.

CREATE INDEX tbl_account_index ON replication_schema.origin_table (tbl_account DESC) LOCAL; CREATE INDEX tbl_column1_index ON replication_schema.origin_table (tbl_column1 DESC) LOCAL; CREATE INDEX tbl_column2_index ON replication_schema.origin_table (tbl_column2 DESC) LOCAL; CREATE INDEX tbl_column3_index ON replication_schema.origin_table (tbl_column3 DESC); CREATE INDEX tbl_column4_index ON replication_schema.origin_table (tbl_column4 DESC);

Most of the time they get new rows (about 4M/mo) but users have set up a process to delete old rows from the origin table every two weeks. They can delete up to 500K/1M rows from each replicated table, every time.

There are seven materialized views in this schema. Each one extract data from one origin table.

What we see is that, contrary to what happens with the origin table, the space reported as free in dba_ tables does not change over time and tablespace usage only grows from these materialized views.

If I wait a while after deleting rows and run this query:

select df.tablespace_name "Tablespace", totalusedspace "Used MB", (df.totalspace - tu.totalusedspace) "Free MB", df.totalspace "Total MB", round(100 * ( (df.totalspace - tu.totalusedspace)/ df.totalspace)) "Pct. Free" from (select tablespace_name, round(sum(bytes) / 1048576) TotalSpace from dba_data_files  group by tablespace_name) df, (select round(sum(bytes)/(1024*1024)) totalusedspace, tablespace_name from dba_segments  group by tablespace_name) tu where df.tablespace_name = tu.tablespace_name and df.totalspace <>0 ;

It shows an increase in the Free MB column (space in dba_data_files minus allocation declared in dba_segment) for origin tablespace but the used MB for replication never decrease, only increase on new rows (over three years now)

Tablespace      Used MB    Free MB  Total MB   Pct. Free SYSTEM          491        9        500        2 SYSAUX          1628       162      1790       9 UNDOTBS1        0          9645     9645       100 ORIGIN_DATA     2705       1391     4096       34 ORIGIN_REP_DATA **1975**   2121     4096       52

That tablespace only holds these materialized views. There’s no other object there being used.

I tried the advisor to see what can I do:

variable id number; begin   declare   name varchar2(100);   descr varchar2(500);   obj_id number;   begin   name:='REPCHECK';   descr:='Replication advisory';    dbms_advisor.create_task (     advisor_name     => 'Segment Advisor',     task_id          => :id,     task_name        => name,     task_desc        => descr);    dbms_advisor.create_object (     task_name        => name,     object_type      => 'TABLE',     attr1            => 'REPLICATION_SCHEMA',     attr2            => 'ORIGIN_TABLE',     attr3            => NULL,     attr4            => NULL,     attr5            => NULL,     object_id        => obj_id);    dbms_advisor.set_task_parameter(     task_name        => name,     parameter        => 'recommend_all',     value            => 'TRUE');    dbms_advisor.execute_task(name);   end; end;  /

And it says

Perform re-org on the origin_table object, estimated savings is xxx bytes

If I try querying recommendations through procedure:

select    tablespace_name,    allocated_space,    used_space reclaimable_space from    table(dbms_space.asa_recommendations('TRUE', 'TRUE', 'ALL'))

It returns

ORIGIN_REP_DATA 100663296   38419844

But I only get errors when trying to run SHRINK SPACE or COMPRESS options

ORA-10635: Invalid segment or tablespace type 10635. 00000 – “Invalid segment or tablespace type” *Cause: Cannot shrink the segment because it is not in auto segment space managed tablespace or it is not a data, index or lob segment. *Action: Check the tablespace and segment type and reissue the statement

Long story short: What can I do to avoiding disk space wasting in this materialized views? How to perform maintenance on them? Shall I drop them and recreate them? Datafiles usage in tablespace is growing about 10GB per month and I’m running out of time (and space). Thanks.

Banker’s Algorithm Question (Creating your own Available // Allocation)

Question:

My question is, how or what is the best way to “determine” an Available and an allocation matrix such that it satisfies (1), and how to “prove” it. And the same for (2). I understand how to do banker’s algorithm questions given to us when we were given the Available and allocation matrix, but I am unsure the best way of going about this question. I am aware that there are multiple answers, I am just unsure of how to prove it so to say, or where to even start. Any help is greatly appreciated, thank you!

Answer Given by Professor:

Solution1

Solution2

Solution3

Solution4

Parallel Merge Sort – No memory allocation

I am implementing a parallel merge sort in C++ that is based off P-Merge-Sort algorithm from Introduction to Algorithms, CLRS on page 803. Here’s the algorithm: P-Merge-Sort

And the associated algorithms:

P-Merge

Binary-Search

And my problem is that I am trying avoid creating a $ T[1 \, ..\, n]$ for each invocation of P-Merge-Sort. I am told that it should be done via global arrays. So I have tried utilizing a single array for working which is the same size as the array being sorted where it would be used as ‘B’ in P-Merge-Sort.

How can I make this work without dynamically allocating memory during Merge Sorting?

Advantage of Stack-Based Allocation for Local Variables

While learning stack allocation, I came across this paragraph in the textbook (Programming Language Pragmatics – 3rd Edition):

Even in a language without recursion, it can be advantageous to use a stack for local variables, rather than allocating them statically. In most programs the pattern of potential calls among subroutines does not permit all of those subroutines to be active at the same time. As a result, the total space needed for local variables of currently active subroutines is seldom as large as the total space across all subroutines, active or not. A stack may therefore require substantially less memory at run time than would be required for static allocation.

I would appreciate if anyone could explain how stack allocation would save memory when used for allocating local variables. I tried reading this many times. But I can’t understand the author meant.